8000 minix/minix/commands/grep/util.c at R3.3.0 · nirs/minix · GitHub
[go: up one dir, main page]

Skip to content

Latest commit

 

History

History
594 lines (528 loc) · 13.6 KB

util.c

File metadata and controls

594 lines (528 loc) · 13.6 KB
firstHalfDot = i;
} else {
/* Closest dot to the end of the pattern. */
lastHalfDot = i;
if (firstLastHalfDot < 0)
firstLastHalfDot = i;
}
} else {
/* Free memory and let others know this is empty. */
free(fg->pattern);
fg->pattern = NULL;
return (-1);
}
}
/*
* Determine if a reverse search would be faster based on the placement
* of the dots.
*/
if ((!(lflag || cflag)) && ((!(bol || eol)) &&
((lastHalfDot) && ((firstHalfDot < 0) ||
((fg->patternLen - (lastHalfDot + 1)) < firstHalfDot))))) {
fg->reversedSearch = 1;
hasDot = fg->patternLen - (firstHalfDot < 0 ?
firstLastHalfDot : firstHalfDot) - 1;
grep_revstr(fg->pattern, fg->patternLen);
}
/*
* Normal Quick Search would require a shift based on the position the
* next character after the comparison is within the pattern. With
* wildcards, the position of the last dot effects the maximum shift
* distance.
* The closer to the end the wild card is the slower the search. A
* reverse version of this algorithm would be useful for wildcards near
* the end of the string.
*
* Examples:
* Pattern Max shift
* ------- ---------
* this 5
* .his 4
* t.is 3
* th.s 2
* thi. 1
*/
/* Adjust the shift based on location of the last dot ('.'). */
shiftPatternLen = fg->patternLen - hasDot;
/* Preprocess pattern. */
for (i = 0; i <= UCHAR_MAX; i++)
fg->qsBc[i] = shiftPatternLen;
for (i = hasDot + 1; i < fg->patternLen; i++) {
fg->qsBc[fg->pattern[i]] = fg->patternLen - i;
/*
* If case is ignored, make the jump apply to both upper and
* lower cased characters. As the pattern is stored in upper
* case, apply the same to the lower case equivalents.
*/
if (iflag)
fg->qsBc[tolower(fg->pattern[i])] = fg->patternLen - i;
}
/*
* Put pattern back to normal after pre-processing to allow for easy
* comparisons later.
*/
if (fg->reversedSearch)
grep_revstr(fg->pattern, fg->patternLen);
return (0);
}
/*
* Word boundaries using regular expressions are defined as the point
* of transition from a non-word char to a word char, or vice versa.
* This means that grep -w +a and grep -w a+ never match anything,
* because they lack a starting or ending transition, but grep -w a+b
* does match a line containing a+b.
*/
#define wmatch(d, l, s, e) \
((s == 0 || !isword(d[s-1])) && (e == l || !isword(d[e])) && \
e > s && isword(d[s]) && isword(d[e-1]))
static int
grep_search(fastgrep_t *fg, unsigned char *data, size_t dataLen, regmatch_t *pmatch)
{
int j;
int rtrnVal = REG_NOMATCH;
pmatch->rm_so = -1;
pmatch->rm_eo = -1;
/* No point in going farther if we do not have enough data. */
if (dataLen < fg->patternLen)
return (rtrnVal);
/* Only try once at the beginning or ending of the line. */
if (fg->bol || fg->eol) {
/* Simple text comparison. */
/* Verify data is >= pattern length before searching on it. */
if (dataLen >= fg->patternLen) {
/* Determine where in data to start search at. */
if (fg->eol)
j = dataLen - fg->patternLen;
else
j = 0;
if (!((fg->bol && fg->eol) && (dataLen != fg->patternLen)))
if (grep_cmp(fg->pattern, data + j,
fg->patternLen) == -1) {
pmatch->rm_so = j;
pmatch->rm_eo = j + fg->patternLen;
if (!fg->wmatch || wmatch(data, dataLen,
pmatch->rm_so, pmatch->rm_eo))
rtrnVal = 0;
}
}
} else if (fg->reversedSearch) {
/* Quick Search algorithm. */
j = dataLen;
do {
if (grep_cmp(fg->pattern, data + j - fg->patternLen,
fg->patternLen) == -1) {
pmatch->rm_so = j - fg->patternLen;
pmatch->rm_eo = j;
if (!fg->wmatch || wmatch(data, dataLen,
pmatch->rm_so, pmatch->rm_eo)) {
rtrnVal = 0;
break;
}
}
/* Shift if within bounds, otherwise, we are done. */
if (j == fg->patternLen)
break;
j -= fg->qsBc[data[j - fg->patternLen - 1]];
} while (j >= fg->patternLen);
} else {
/* Quick Search algorithm. */
j = 0;
do {
if (grep_cmp(fg->pattern, data + j, fg->patternLen) == -1) {
pmatch->rm_so = j;
pmatch->rm_eo = j + fg->patternLen;
if (fg->patternLen == 0 || !fg->wmatch ||
wmatch(data, dataLen, pmatch->rm_so,
pmatch->rm_eo)) {
rtrnVal = 0;
break;
}
}
/* Shift if within bounds, otherwise, we are done. */
if (j + fg->patternLen == dataLen)
break;
else
j += fg->qsBc[data[j + fg->patternLen]];
} while (j <= (dataLen - fg->patternLen));
}
return (rtrnVal);
}
void *
grep_malloc(size_t size)
{
void *ptr;
if ((ptr = malloc(size)) == NULL)
err(2, "malloc");
return ptr;
}
void *
grep_calloc(size_t nmemb, size_t size)
{
void *ptr;
if ((ptr = calloc(nmemb, size)) == NULL && (size > 0) && (nmemb > 0))
err(2, "calloc");
return ptr;
}
void *
grep_realloc(void *ptr, size_t size)
{
if ((ptr = realloc(ptr, size)) == NULL)
err(2, "realloc");
return ptr;
}
/*
* Returns: i >= 0 on failure (position that it failed)
* -1 on success
*/
static int
grep_cmp(const unsigned char *pattern, const unsigned char *data, size_t len)
{
int i;
for (i = 0; i < len; i++) {
if (((pattern[i] == data[i]) || (!Fflag && pattern[i] == '.'))
|| (iflag && pattern[i] == toupper(data[i])))
continue;
return (i);
}
return (-1);
}
static void
grep_revstr(unsigned char *str, int len)
{
int i;
char c;
for (i = 0; i < len / 2; i++) {
c = str[i];
str[i] = str[len - i - 1];
str[len - i - 1] = c;
}
}
void
printline(str_t *line, int sep)
{
int n;
n = 0;
if (!hflag) {
fputs(line->file, stdout);
++n;
}
if (nflag) {
if (n)
putchar(sep);
printf("%d", line->line_no);
++n;
}
if (bflag) {
if (n)
putchar(sep);
#ifndef __minix
printf("%lld", (long long)line->off);
#else
printf("%ld", (long)line->off);
#endif
++n;
}
if (n)
putchar(sep);
fwrite(line->dat, line->len, 1, stdout);
putchar('\n');
}
0