tools/cscope-fast/cgrep.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*	Copyright (c) 1990 AT&T	*/
/*	  All Rights Reserved	*/

/*
 * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*
 *	cscope - interactive C symbol or text cross-reference
 *
 *	text searching functions
 */

#include <fcntl.h>
#include <setjmp.h>
#include <stdio.h>
#include <string.h>
#include <memory.h>
#include <ctype.h>
#include <unistd.h>
#include "library.h"

typedef enum {
	NO = 0,
	YES = 1
} BOOL;

typedef struct re_bm {
	int delta0[256];
	int *delta2;
	uchar_t *cmap;
	uchar_t *bmpat;
	int patlen;
} re_bm;

typedef struct Link {
	uchar_t lit;
	struct Node *node;
	struct Link *next;
} Link;

typedef struct Node {
	short out;
	short d;
	short shift1;
	short shift2;
	long id;
	struct Node **tab;
	Link *alts;
	struct Node *fail;
} Node;

typedef struct re_cw {
	int maxdepth, mindepth;
	long nodeid;
	int step[256];
	uchar_t *cmap;
	struct Node *root;
} re_cw;

typedef enum {
	/* lit expression types */
	Literal, Dot, Charclass, EOP,

	/* non-lit expression types */
	Cat, Alternate, Star, Plus, Quest,

	/* not really expression types, just helping */
	Lpar, Rpar, Backslash

} Exprtype;

typedef int ID;

typedef struct Expr {
	Exprtype type;	/* Type of expression (in grammar) */
	ID id;		/* unique ID of lit expression  */
	int lit;	/* Literal character or tag */
	int flen;	/* Number of following lit expressions */
	ID *follow;	/* Array of IDs of following lit expressions */
	struct Expr *l; /* pointer to Left child (or ccl count) */
	struct Expr *r; /* pointer to Right child (or ccl mask) */
	struct Expr *parent; /* pointer to Parent */
} Expr;

typedef struct State {
	struct State *tab[256];
	int cnt; /* number of matched chars on full match, -1 otherwise  */
	int npos;	/* number of IDs in position set for this state. */
	int pos;	/* index into posbase for beginning of IDs */
} State;

typedef struct FID {
	ID	id;	/* Lit Expression id */
	int	fcount; /* Number of Lit exp matches before this one. */
} FID;

typedef struct Positionset {
	int count;	/* Number of lit exps in position set */
	ID last;	/* ID of last lit exp in position set */
	FID *base;	/* array of MAXID FIDS */
			/* 0 means not in position set */
			/* -1 means first in position set */
			/* n (>0) is ID of prev member of position set. */
} Positionset;

typedef struct re_re {
	FID  *posbase;	/* Array of IDs from all states */
	int nposalloc;	/* Allocated size of posbase */
	int posnext;	/* Index into free space in posbase */
	int posreset;	/* Index into end of IDs for initial state in posbase */
	int maxid;	/* Number of (also maximum ID of) lit expressions */
	Expr *root;	/* Pointer to root (EOP) expression */
	Expr **ptr;	/* Pointer to array of ptrs to lit expressions. */
	uchar_t *cmap;	/* Character mapping array */
	Positionset firstpos;
	Positionset tmp;
	int nstates;	/* Number of current states defined */
	int statelim;	/* Limit on number of states before flushing */
	State *states;	/* Array of states */
	State istate;	/* Initial state */
} re_re;

typedef struct {
	uchar_t *cmap;
	re_re *re_ptr;
	re_bm *bm_ptr;
	re_cw *cw_ptr;
	BOOL fullmatch;
	BOOL (*procfn)();
	BOOL (*succfn)();
	uchar_t *loc1;
	uchar_t *loc2;
	uchar_t *expression;
} PATTERN;

typedef enum {
	BEGIN,		/* File is not yet in buffer at all */
	MORE,		/* File is partly in buffer */
	NO_MORE		/* File has been completely read into buffer */
} FILE_STAT;

typedef struct {
	uchar_t	*prntbuf; /* current line of input from data file */
	uchar_t	*newline; /* end of line (real or sentinel \n) */
	long	ln;	/* line number */
} LINE;

#define	NL '\n'

#define	CCL_SIZ		32
#define	CCL_SET(a, c)	((a)[(c) >> 3] |= bittab[(c) & 07])
#define	CCL_CLR(a, c)	((a)[(c) >> 3] &= ~bittab[(c) & 07])
#define	CCL_CHK(a, c)	((a)[(c) >> 3] & bittab[(c) & 07])

#define	ESIZE (BUFSIZ)
#define	MAXBUFSIZE (64*BUFSIZ)

#define	MAXMALLOCS	1024
#define	MAXLIT	256	/* is plenty big enough */
#define	LARGE	MAXBUFSIZE+ESIZE+2

#define	CLEAR(r, rps)	(void) memset((char *)(rps)->base, 0, \
			    (int)((r)->maxid * sizeof (FID))), \
			    (rps)->count = 0, (rps)->last = -1
#define	SET(rps, n, cnt) { \
	if ((rps)->base[n].id == 0) {\
		(rps)->count++;\
		(rps)->base[n].fcount = (cnt);\
		(rps)->base[n].id = (rps)->last;\
		(rps)->last = (n);\
	} else if ((cnt) > (rps)->base[n].fcount) {\
		(rps)->base[n].fcount = (cnt);\
	}}

#define	START	{ _p = tmp; }
#define	ADDL(c)	{ if (_p >= &tmp[MAXLIT]) _p--; *_p++ = c; }
#define	FINISH	{ ADDL(0) if ((_p-tmp) > bestlen) \
		    (void) memmove(best, tmp, bestlen = _p-tmp); }


#define	NEW(N)	(froot?(t = froot, froot = froot->next, t->next = NULL, \
		    t->node = N, t): newlink(0, N))
#define	ADD(N)	if (qtail) qtail = qtail->next = NEW(N); \
			else qtail = qhead = NEW(N)
#define	DEL()	{ Link *_l = qhead; if ((qhead = qhead->next) == NULL) \
			{ qtail = NULL; } _l->next = froot; froot = _l; }

static uchar_t	*buffer;
static uchar_t	*bufend;
static FILE	*output;
static char	*format;
static char	*file;
static int	file_desc;
static FILE_STAT file_stat;
static PATTERN	match_pattern;
static uchar_t	char_map[2][256];
static int	iflag;
static Exprtype	toktype;
static int	toklit, parno, maxid;
static uchar_t	tmp[MAXLIT], best[MAXLIT];
static uchar_t	*_p;
static int	bestlen;
static Node	*next_node;
static Link	*froot, *next_link;
static jmp_buf	env;

static int nmalloc;
static uchar_t	*mallocs[MAXMALLOCS];

static uchar_t	bittab[] = { 1, 2, 4, 8, 16, 32, 64, 128 };

#ifdef	DEBUG
#define		TRACE(n)	(n < debug)
#define		EPRINTSIZE	50000
static void spr(int c, int *p, uchar_t *buf);
void epr(Expr *e, uchar_t *res);
static int debug = 12;
#endif

static void init_file(LINE *cur_ptr);
static void get_line(LINE *cur_ptr, uchar_t *s);
static void get_ncount(LINE *cur_ptr, uchar_t *s);
static int execute(void);
static State *startstate(re_re *r);
static State *stateof(re_re *r, Positionset *ps);
static State *nextstate(re_re *r, State *s, int a);
static State *addstate(re_re *r, Positionset *ps, int cnt);
static BOOL match(Expr *e, int a);
static BOOL first_lit(Positionset *fpos, Expr *e);
static void eptr(re_re *r, Expr *e);
static void efollow(re_re *r, Positionset *fpos, Expr *e);
static void follow(Positionset *fpos, Expr *e);
static void followstate(re_re *r, State *s, int a, Positionset *fpos);
static Expr *eall(re_re *r, PATTERN *pat);
static Expr *d0(re_re *r, PATTERN *pat);
static Expr *d1(re_re *r, PATTERN *pat);
static Expr *d2(re_re *r, PATTERN *pat);
static Expr *d3(re_re *r, PATTERN *pat);
static Expr *newexpr(Exprtype t, int lit, Expr *left, Expr *right);
static void lex(re_re *r, PATTERN *pat);
static int re_lit(PATTERN *pat, uchar_t **b, uchar_t **e);
static void traverse(PATTERN *pat, Expr *e);
static int ccl(PATTERN *pat, uchar_t *tab);
static BOOL altlist(), word();
static BOOL altlist(Expr *e, uchar_t *buf, re_cw *pat);
static Node *newnode(re_cw *c, int d);
static Link *newlink(uchar_t lit, Node *n);
static void fail(Node *root);
static void zeroroot(Node *root, Node *n);
static void shift(re_cw *c);
static void shifttab(Node *n);
static void shiftprop(re_cw *c, Node *n);
static void delta_2(re_bm *b);
static int getstate(re_re *r, Positionset *ps);
static void savestate(re_re *r);
static void stateinit(re_re *r);
static re_bm *re_bmcomp(uchar_t *pb, uchar_t *pe, uchar_t *cmap);
static re_cw *re_cwinit(uchar_t *cmap);
static re_cw *re_recw(re_re *r, uchar_t *map);
static re_re *egprep(PATTERN *pat);
static void re_cwadd(re_cw *c, uchar_t *s, uchar_t *e);
static void re_cwcomp(re_cw *c);
static void eginit(re_re *r);
static BOOL re_bmexec(PATTERN *pat, uchar_t *s, uchar_t *e, uchar_t **mb,
    uchar_t **me);
static BOOL re_cwexec(PATTERN *pat, uchar_t *rs, uchar_t *re, uchar_t **mb,
    uchar_t **me);
static BOOL re_reexec(PATTERN *pat, uchar_t *b, uchar_t *e, uchar_t **mb,
    uchar_t **me);
static uchar_t *egmalloc(size_t n);
static void fgetfile(LINE *cur_ptr);
static void dogre(PATTERN *pat);
static BOOL pattern_match(PATTERN *pat, LINE *lptr);
static BOOL fixloc(uchar_t **mb, uchar_t **me);
static BOOL grepmatch(PATTERN *pat, uchar_t **mb, uchar_t **me);
static void err(char *s);

static char *message;

void
egrepcaseless(int i)
{
	iflag = i;	/* simulate "egrep -i" */
}

char *
egrepinit(char *expression)
{
	static int firsttime = 1;
	int i;

	if (firsttime) {
		firsttime = 0;
		for (i = 0; i < 256; i++) {
			char_map[0][i] = (uchar_t)i;
			char_map[1][i] = tolower(i);
		}
	}
	for (i = 0; i < nmalloc; i ++)
		free(mallocs[i]);
	nmalloc = 0;
	message = NULL;

	match_pattern.expression = (uchar_t *)expression;
	match_pattern.cmap = char_map[iflag];
	if (setjmp(env) == 0) {
		dogre(&match_pattern);
#ifdef	DEBUG
		{
		PATTERN *p = match_pattern;
		if (p->procfn == re_bmexec)
			if (!p->fullmatch)
				if (p->succfn == re_reexec)
					printf("PARTIAL BOYER_MOORE\n");
				else
					printf("PARTIAL B_M with GREP\n");
			else
				printf("FULL BOYER_MOORE\n");
		else if (p->procfn == re_cwexec)
			printf("C_W\n");
		else
			printf("GENERAL\n");
		}
#endif
	}
	return (message);
}

static void
dogre(PATTERN *pat)
{
	uchar_t *lb, *le;

#ifdef	DEBUG
	printf("PATTERN %s\n", pat->expression);
#endif
	pat->re_ptr = egprep(pat);
	bestlen = re_lit(pat, &lb, &le);

	if (bestlen && pat->fullmatch) { /* Full Boyer Moore */
#ifdef	DEBUG
		printf("BESTLEN %d\n", bestlen);
		{
			uchar_t *p;
			for (p = lb; p < le; p++) printf("%c", *p);
			printf("\n");
		}
#endif
		pat->bm_ptr = re_bmcomp(lb, le, pat->cmap);
		pat->procfn = re_bmexec;
		return;
	}
	if (bestlen > 1) {
			/* Partial Boyer Moore */
		pat->bm_ptr = re_bmcomp(lb, le, pat->cmap);
		pat->procfn = re_bmexec;
		pat->fullmatch = NO;
	} else {
		pat->fullmatch = YES;
		if ((pat->cw_ptr = re_recw(pat->re_ptr, pat->cmap)) != NULL) {
			pat->procfn = re_cwexec; /* CW */
			return;
		}
	}
	/* general egrep regular expression */
	pat->succfn = re_reexec;

	if (pat->fullmatch) {
		pat->procfn = pat->succfn;
		pat->succfn = NULL;
	}
}

static BOOL
fixloc(uchar_t **mb, uchar_t **me)
{
	/* Handle match to null string */

	while (*me <= *mb)
		(*me)++;

	if (*(*me - 1) != NL)
		while (**me != NL)
			(*me)++;

	/* Handle match to new-line only */

	if (*mb == *me - 1 && **mb == NL) {
		(*me)++;
	}

	/* Handle match including beginning or ending new-line */

	if (**mb == NL)
		(*mb)++;
	if (*(*me - 1) == NL)
		(*me)--;
	return (YES);
}

static BOOL
grepmatch(PATTERN *pat, uchar_t **mb, uchar_t **me)
{
	uchar_t *s, *f;

	if (pat->fullmatch)
		return (fixloc(mb, me));

	for (f = *me - 1; *f != NL; f++) {
	}
	f++;
	for (s = *mb; *s != NL; s--) {
	}

	if ((*pat->succfn)(pat, s, f, mb, me)) {
		return (YES);
	} else {
		*mb = f;
		return (NO);
	}
}

static void
eginit(re_re *r)
{
	unsigned int n;

	r->ptr = (Expr **)egmalloc(r->maxid * sizeof (Expr *));
	eptr(r, r->root);
	n = r->maxid * sizeof (FID);
	r->firstpos.base = (FID *)egmalloc(n);
	r->tmp.base = (FID *)egmalloc(n);
	CLEAR(r, &r->firstpos);
	if (!first_lit(&r->firstpos, r->root->l)) {
		/*
		 * This expression matches the null string!!!!
		 * Add EOP to beginning position set.
		 */
		SET(&r->firstpos, r->root->id, 0)
		/* (void) printf("first of root->l == 0, b=%s\n", b); */
	}
	stateinit(r);
	(void) addstate(r, &r->firstpos, 0);
	savestate(r);
}

static void
eptr(re_re *r, Expr *e)
{
	if ((e->id < 0) || (e->id >= r->maxid)) {
		err("internal error");
	}
	r->ptr[e->id] = e;
	if (e->type != Charclass) {
		if (e->l) eptr(r, e->l);
		if (e->r) eptr(r, e->r);
	}
}

static BOOL
re_reexec(PATTERN *pat, uchar_t *b, uchar_t *e, uchar_t **mb, uchar_t **me)
{
	re_re *r = pat->re_ptr;
	State *s, *t;

#ifdef	DEBUG
	if (TRACE(10)) {
		uchar_t buf[EPRINTSIZE];
		epr(r->root, buf);
		(void) printf("expr='%s'\n", buf);
	}
#endif
	s = startstate(r);

	for (;;) {
		uchar_t c;

		if (s->cnt >= 0) {
#ifdef	DEBUG
			if (TRACE(6))
				(void) printf("match at input '%s'\n", b);
#endif
			*mb = b - s->cnt;
			*me = b;
			if (fixloc(mb, me))
				return (YES);
		}

		if (b >= e) break;
		c = pat->cmap[*b];
#ifdef	DEBUG
		if (TRACE(4))
			(void) printf("state %d: char '%c'\n", s-r->states, *b);
#endif
		if ((t = s->tab[c]) != NULL) s = t;
		else s = nextstate(r, s, (int)c);
		b++;
	}
#ifdef	DEBUG
	if (TRACE(3)) {
		uchar_t buf[EPRINTSIZE];

		epr(r->root, buf);
		(void) printf("pat = %s\n", buf);
	}
#endif
	return (NO);
}

static BOOL
match(Expr *e, int a)
{
	switch (e->type) {
	case Dot:	return ((BOOL)(a != NL));
	case Literal:	return ((BOOL)(a == e->lit));
	case Charclass:	return ((BOOL)(CCL_CHK((uchar_t *)e->r, a)));
	default:	return (NO);
	}
}

/*
 * generates the followset for a node in fpos
 */
static void
follow(Positionset *fpos, Expr *e)
{
	Expr *p;

	if (e->type == EOP)
		return;
	else
		p = e->parent;
	switch (p->type) {
	case EOP:
		SET(fpos, p->id, 0)
		break;
	case Plus:
	case Star:
		(void) first_lit(fpos, e);
		follow(fpos, p);
		break;
	case Quest:
	case Alternate:
		follow(fpos, p);
		break;
	case Cat:
		if (e == p->r || !first_lit(fpos, p->r))
			follow(fpos, p);
		break;
	default:
		break;
	}
}

/*
 * first_lit returns NO if e is nullable and in the process,
 * ets up fpos.
 */
static BOOL
first_lit(Positionset *fpos, Expr *e)
{
	BOOL k;

	switch (e->type) {
	case Literal:
	case Dot:
	case Charclass:
		SET(fpos, e->id, 0)
		return (YES);
	case EOP:
	case Star:
	case Quest:
		(void) first_lit(fpos, e->l);
		return (NO);
	case Plus:
		return (first_lit(fpos, e->l));
	case Cat:
		return ((BOOL)(first_lit(fpos, e->l) || first_lit(fpos, e->r)));
	case Alternate:
		k = first_lit(fpos, e->r);
		return ((BOOL)(first_lit(fpos, e->l) && k));
	default:
		err("internal error");
	}
	return (NO);
}

static void
efollow(re_re *r, Positionset *fpos, Expr *e)
{
	ID i, *p;

	CLEAR(r, fpos);
	follow(fpos, e);
	e->flen = fpos->count;
	e->follow = (ID *)egmalloc(e->flen * sizeof (ID));
	p = e->follow;
#ifdef	DEBUG
	printf("ID = %d LIT %c FLEN = %d\n", e->id, e->lit, e->flen);
#endif
	for (i = fpos->last; i > 0; i = fpos->base[i].id) {
		*p++ = i;
#ifdef	DEBUG
	printf("FOLLOW ID = %d LIT %c\n", r->ptr[i]->id, r->ptr[i]->lit);
#endif
	}
	if (p != e->follow + e->flen) {
		err("internal error");
	}
}

static State *
addstate(re_re *r, Positionset *ps, int cnt)
{
	ID j;
	FID *p, *q;
	State *s;

	if (cnt) {
		s = r->states + getstate(r, ps);
		(void) memset((char *)s->tab, 0, sizeof (s->tab));
		s->cnt = r->istate.cnt;
	} else {
		s = &r->istate;
		s->cnt = -1;
	}
	s->pos = r->posnext;
	r->posnext += ps->count;
	s->npos = ps->count;
	p = r->posbase + s->pos;
	for (j = ps->last; j > 0; p++, j = q->id) {
		q = &ps->base[j];
		p->id = j;
		p->fcount = q->fcount;
		if (p->id == r->root->id && s->cnt < p->fcount)
			s->cnt = p->fcount;
	}
#ifdef	DEBUG
	if (TRACE(3)) {
		uchar_t buf[2000];
		spr(s->npos, s->pos+r->posbase, buf);
		(void) printf("new state[%d] %s%s\n", s-r->states, buf,
		    s->cnt?" cnt":"");
	}
#endif
	return (s);
}

static State *
nextstate(re_re *r, State *s, int a)
{
	State *news;

	CLEAR(r, &r->tmp);
	followstate(r, s, a, &r->tmp);
	if (s != &r->istate) followstate(r, &r->istate, a, &r->tmp);

#ifdef	DEBUG
	if (TRACE(5)) {
		uchar_t buf[2000];
		ppr(&r->tmp, buf);
		(void) printf("nextstate(%d, '%c'): found %s\n", s-r->states,
		    a, buf);
	}
#endif
	if (r->tmp.count == 0)
		news = &r->istate;
	else if ((news = stateof(r, &r->tmp)) == NULL)
		news = addstate(r, &r->tmp, 1);
	s->tab[a] = news;
#ifdef	DEBUG
	if (TRACE(5)) {
		(void) printf("nextstate(%d, '%c'): returning %ld\n",
		    s-r->states, a, news);
	}
#endif
	return (news);
}

static void
followstate(re_re *r, State *s, int a, Positionset *fpos)
{
	int j;
	ID *q, *eq;
	Expr *e;

	for (j = s->pos; j < (s->pos + s->npos); j++) {
		e = r->ptr[r->posbase[j].id];
		if (e->type == EOP) continue;
		if (match(e, a)) {
			if (e->follow == NULL) efollow(r, &r->firstpos, e);
			for (q = e->follow, eq = q + e->flen; q < eq; q++) {
				SET(fpos, *q, r->posbase[j].fcount + 1)
#ifdef	DEBUG
				printf("CHAR %c FC %c COUNT %d\n", a,
				    r->ptr[*q]->lit, r->posbase[j].fcount+1);
#endif
			}
		}
	}
}

static uchar_t *
egmalloc(size_t n)
{
	uchar_t *x;

	x = (uchar_t *)mymalloc(n);
	mallocs[nmalloc++] = x;
	if (nmalloc >= MAXMALLOCS)
		nmalloc = MAXMALLOCS - 1;
	return (x);
}

#ifdef	DEBUG
void
ppr(Positionse *ps, char *p)
{
	ID n;

	if (ps->count < 1) {
		(void) sprintf(p, "{}");
		return;
	}
	*p++ = '{';
	for (n = ps->last; n > 0; n = ps->base[n].id) {
		(void) sprintf(p, "%d,", n);
		p = strchr(p, 0);
	}
	p[-1] = '}';
}

void
epr(Expr *e, uchar_t *res)
{
	uchar_t r1[EPRINTSIZE], r2[EPRINTSIZE];
	int i;

	if (e == NULL) {
		(void) sprintf(res, "!0!");
		return;
	}
	switch (e->type) {
	case Dot:
	case Literal:
		spr(e->flen, e->follow, r1);
		(void) sprintf(res, "%c%s", e->lit, r1);
		break;
	case Charclass:
		*res++ = '[';
		for (i = 0; i < 256; i++)
			if (CCL_CHK((uchar_t *)e->r, i)) {
				*res++ = i;
			}
		*res++ = ']';
		*res = '\0';
		break;
	case Cat:
		epr(e->l, r1);
		epr(e->r, r2);
		(void) sprintf(res, "%s%s", r1, r2);
		break;
	case Alternate:
		epr(e->l, r1);
		epr(e->r, r2);
		(void) sprintf(res, "(%s|%s)", r1, r2);
		break;
	case Star:
		epr(e->l, r1);
		(void) sprintf(res, "(%s)*", r1);
		break;
	case Plus:
		epr(e->l, r1);
		(void) sprintf(res, "(%s)+", r1);
		break;
	case Quest:
		epr(e->l, r1);
		(void) sprintf(res, "(%s)?", r1);
		break;
	case EOP:
		epr(e->l, r1);
		(void) sprintf(res, "%s<EOP>", r1);
		break;
	default:
		(void) sprintf(res, "<undef type %d>", e->type);
		err(res);
		break;
	}
}

static void
spr(int c, int *p, uchar_t *buf)
{
	if (c > 0) {
		*buf++ = '{';
		*buf = '\0';
		while (--c > 0) {
			(void) sprintf(buf, "%d,", *p++);
			buf = strchr(buf, 0);
		}
		(void) sprintf(buf, "%d}", *p);
	} else
		(void) sprintf(buf, "{}");
}
#endif

static void
stateinit(re_re *r)
{
	/* CONSTANTCONDITION */
	r->statelim = (sizeof (int) < 4 ? 32 : 128);
	r->states = (State *)egmalloc(r->statelim * sizeof (State));

	/* CONSTANTCONDITION */
	r->nposalloc = (sizeof (int) < 4 ? 2048 : 8192);
	r->posbase = (FID *)egmalloc(r->nposalloc * sizeof (FID));
	r->nstates = r->posnext = 0;
}

static void
clrstates(re_re *r)
{
	r->nstates = 0;		/* reclaim space for states and positions */
	r->posnext = r->posreset;
	(void) memset((char *)r->istate.tab, 0, sizeof (r->istate.tab));
}

static void
savestate(re_re *r)
{
	r->posreset = r->posnext;	/* save for reset */
}

static State *
startstate(re_re *r)
{
	return (&r->istate);
}

static int
getstate(re_re *r, Positionset *ps)
{
	if (r->nstates >= r->statelim ||
	    r->posnext + ps->count >= r->nposalloc) {
		clrstates(r);
#ifdef	DEBUG
		printf("%d STATES FLUSHED\n", r->statelim);
#endif
	}
	return (r->nstates++);
}

static State *
stateof(re_re *r, Positionset *ps)
{
	State *s;
	int i;
	FID *p, *e;

	for (i = 0, s = r->states; i < r->nstates; i++, s++) {
		if (s->npos == ps->count) {
			for (p = s->pos+r->posbase, e = p+s->npos; p < e; p++)
				if (ps->base[p->id].id == 0 ||
				    ps->base[p->id].fcount != p->fcount)
					goto next;
			return (s);
		}
	next:;
	}
	return (NULL);
}

static re_re *
egprep(PATTERN *pat)
{
	re_re *r;

	r = (re_re *)egmalloc(sizeof (re_re));
	(void) memset((char *)r, 0, sizeof (re_re));

	pat->loc1 = pat->expression;
	pat->loc2 = pat->expression + strlen((char *)pat->expression);

	parno = 0;
	maxid = 1;
	r->cmap = pat->cmap;
	lex(r, pat);
	r->root = newexpr(EOP, '#', eall(r, pat), (Expr *)NULL);
	r->maxid = maxid;

	eginit(r);
	return (r);
}

static Expr *
newexpr(Exprtype t, int lit, Expr *left, Expr *right)
{
	Expr *e = (Expr *)egmalloc(sizeof (Expr));

	e->type = t;
	e->parent = NULL;
	e->lit = lit;

	if (e->lit) e->id = maxid++;
	else e->id = 0;

	if ((e->l = left) != NULL) {
		left->parent = e;
	}
	if ((e->r = right) != NULL) {
		right->parent = e;
	}
	e->follow = NULL;
	e->flen = 0;
	return (e);
}

static void
lex(re_re *r, PATTERN *pat)
{
	if (pat->loc1 == pat->loc2) {
		toktype = EOP;
		toklit = -1;
	} else switch (toklit = *pat->loc1++) {
	case '.':	toktype = Dot; break;
	case '*':	toktype = Star; break;
	case '+':	toktype = Plus; break;
	case '?':	toktype = Quest; break;
	case '[':	toktype = Charclass; break;
	case '|':	toktype = Alternate; break;
	case '(':	toktype = Lpar; break;
	case ')':	toktype = Rpar; break;
	case '\\':	toktype = Backslash;
			if (pat->loc1 == pat->loc2) {
				err("syntax error - missing character "
				    "after \\");
			} else {
				toklit = r->cmap[*pat->loc1++];
			}
			break;
	case '^': case '$':	toktype = Literal; toklit = NL; break;
	default:	toktype = Literal; toklit = r->cmap[toklit]; break;
	}
}

static int
ccl(PATTERN *pat, uchar_t *tab)
{
	int i;
	int range = 0;
	int lastc = -1;
	int count = 0;
	BOOL comp = NO;

	(void) memset((char *)tab, 0, CCL_SIZ * sizeof (uchar_t));
	if (*pat->loc1 == '^') {
		pat->loc1++;
		comp = YES;
	}
	if (*pat->loc1 == ']') {
		uchar_t c = pat->cmap[*pat->loc1];
		CCL_SET(tab, c);
		lastc = *pat->loc1++;
	}
	/* scan for chars */
	for (; (pat->loc1 < pat->loc2) && (*pat->loc1 != ']'); pat->loc1++) {
		if (*pat->loc1 == '-') {
			if (lastc < 0) CCL_SET(tab, pat->cmap['-']);
			else range = 1;
			continue;
		}
		if (range) {
			for (i = *pat->loc1; i >= lastc; i--) {
				CCL_SET(tab, pat->cmap[i]);
			}
		} else {
			uchar_t c = pat->cmap[*pat->loc1];
			CCL_SET(tab, c);
		}

		range = 0;

		lastc = *pat->loc1;
	}
	if (range) CCL_SET(tab, pat->cmap['-']);

	if (pat->loc1 < pat->loc2) pat->loc1++;
	else err("syntax error - missing ]");

	if (comp) {
		CCL_SET(tab, pat->cmap[NL]);
		for (i = 0; i < CCL_SIZ; i++) tab[i] ^= 0xff;
	}
	for (i = 0; i < 256; i++) {
		if (pat->cmap[i] != i) CCL_CLR(tab, i);
		if (CCL_CHK(tab, i)) {
			lastc = i;
			count++;
		}
	}
	if (count == 1)
		*tab = (char)lastc;
	return (count);
}

/*
 * egrep patterns:
 *
 * Alternation:	d0:	d1 { '|' d1 }*
 * Concatenation:	d1:	d2 { d2 }*
 * Repetition:	d2:	d3 { '*' | '?' | '+' }
 * Literal:	d3:	lit | '.' | '[]' | '(' d0 ')'
 */

static Expr *
d3(re_re *r, PATTERN *pat)
{
	Expr *e;
	uchar_t *tab;
	int count;

	switch (toktype) {
	case Backslash:
	case Literal:
		e = newexpr(Literal, toklit, (Expr *)NULL, (Expr *)NULL);
		lex(r, pat);
		break;
	case Dot:
		e = newexpr(Dot, '.', (Expr *)NULL, (Expr *)NULL);
		lex(r, pat);
		break;
	case Charclass:
		tab = egmalloc(CCL_SIZ * sizeof (uchar_t));
		count = ccl(pat, tab);
		if (count == 1) {
			toklit = *tab;
			e = newexpr(Literal, toklit, (Expr *)NULL,
			    (Expr *)NULL);
		} else {
			e = newexpr(Charclass, '[', (Expr *)NULL, (Expr *)NULL);
			e->l = (Expr *)count;	/* number of chars */
			e->r = (Expr *)tab;	/* bitmap of chars */
		}
		lex(r, pat);
		break;
	case Lpar:
		lex(r, pat);
		count = ++parno;
		e = d0(r, pat);
		if (toktype == Rpar)
			lex(r, pat);
		else
			err("syntax error - missing )");
		return (e);
	default:
		err("syntax error");
		e = NULL;
	}
	return (e);
}

static Expr *
d2(re_re *r, PATTERN *pat)
{
	Expr *e;
	Exprtype t;

	e = d3(r, pat);
	while ((toktype == Star) || (toktype == Plus) || (toktype == Quest)) {
		t = toktype;
		lex(r, pat);
		e = newexpr(t, 0, e, (Expr *)NULL);
	}
	return (e);
}

static Expr *
d1(re_re *r, PATTERN *pat)
{
	Expr *e, *f;

	e = d2(r, pat);
	while ((toktype == Literal) || (toktype == Dot) || (toktype == Lpar) ||
	    (toktype == Backslash) || (toktype == Charclass)) {
		f = d2(r, pat);
		e = newexpr(Cat, 0, e, f);
	}
	return (e);
}

static Expr *
d0(re_re *r, PATTERN *pat)
{
	Expr *e, *f;

	e = d1(r, pat);
	while (toktype == Alternate) {
		lex(r, pat);
		if (toktype == EOP)
			continue;
		f = d1(r, pat);
		e = newexpr(Alternate, 0, e, f);
	}
	return (e);
}

static Expr *
eall(re_re *r, PATTERN *pat)
{
	Expr *e;

	while (toktype == Alternate)	/* bogus but user-friendly */
		lex(r, pat);
	e = d0(r, pat);
	while (toktype == Alternate)	/* bogus but user-friendly */
		lex(r, pat);
	if (toktype != EOP)
		err("syntax error");
	return (e);
}

static void
err(char *s)
{
	message = s;
	longjmp(env, 1);
}

static int
re_lit(PATTERN *pat, uchar_t **b, uchar_t **e)
{
	bestlen = 0;
	pat->fullmatch = YES;
	START
	traverse(pat, pat->re_ptr->root->l);
	FINISH
	if (bestlen < 2)
		return (0);
	*b = egmalloc(bestlen * sizeof (uchar_t));
	(void) memmove(*b, best, bestlen);
	*e = *b + bestlen - 1;
	return (bestlen - 1);
}

static void
traverse(PATTERN *pat, Expr *e)
{
	switch (e->type) {
	case Literal:
		ADDL(e->lit)
		break;
	case Cat:
		traverse(pat, e->l);
		traverse(pat, e->r);
		break;
	case Plus:
		traverse(pat, e->l);
		FINISH	/* can't go on past a + */
		pat->fullmatch = NO;
		START	/* but we can start with one! */
		traverse(pat, e->l);
		break;
	default:
		FINISH
		pat->fullmatch = NO;
		START
		break;
	}
}

static re_bm *
re_bmcomp(uchar_t *pb, uchar_t *pe, uchar_t *cmap)
{
	int j;
	int delta[256];
	re_bm *b;

	b = (re_bm *)egmalloc(sizeof (*b));

	b->patlen = pe - pb;
	b->cmap = cmap;
	b->bmpat = pb;

	delta_2(b);

	for (j = 0; j < 256; j++)
		delta[j] = b->patlen;

	for (pe--; pb < pe; pb++)
		delta[b->cmap[*pb]] = pe - pb;

	delta[b->cmap[*pb]] = LARGE;

	for (j = 0; j < 256; j++)
		b->delta0[j] = delta[b->cmap[j]];
	return (b);
}

static void
delta_2(re_bm *b)
{
	int m = b->patlen;
	int i, k, j;

	b->delta2 = (int *)egmalloc(m * sizeof (int));

	for (j = 0; j < m; j++) {
		k = 1;
again:
		while (k <= j && b->bmpat[j-k] == b->bmpat[j]) k++;

		for (i = j + 1; i < m; i++) {
			if (k <= i && b->bmpat[i-k] != b->bmpat[i]) {
				k++;
				goto again;
			}
		}
		b->delta2[j] = k + m - j - 1;
	}
}

static BOOL
re_bmexec(PATTERN *pat, uchar_t *s, uchar_t *e, uchar_t **mb, uchar_t **me)
{
	re_bm *b = pat->bm_ptr;
	uchar_t *sp;
	int k;

	s += b->patlen - 1;
	while ((unsigned long)s < (unsigned long)e) {
		while ((unsigned long)(s += b->delta0[*s]) < (unsigned long)e)
			;
		if ((unsigned long)s < (unsigned long)(e + b->patlen))
			return (NO); /* no match */
		s -= LARGE;
		for (k = b->patlen-2, sp = s-1; k >= 0; k--) {
			if (b->cmap[*sp--] != b->bmpat[k]) break;
		}
		if (k < 0) {
			*mb = ++sp;
			*me = s+1;
			if (grepmatch(pat, mb, me))
				return (YES);
			s = *mb;
		} else if (k < 0) {
			s++;
		} else {
			int j;
			j = b->delta2[k];
			k = b->delta0[*++sp];
			if ((j > k) || (k == (int)LARGE))
				k = j;
			s = sp + k;
		}
	}
	return (NO);
}

static re_cw *
re_recw(re_re *r, uchar_t *map)
{
	Expr *e, *root = r->root;
	re_cw *pat;
	uchar_t *buf;

	if (root->type != EOP)
		return (NULL);
	e = root->l;
	pat = re_cwinit(map);
	buf = (uchar_t *)egmalloc(20000 * sizeof (uchar_t));
	if (!altlist(e, buf, pat)) {
		return (NULL);
	}
	re_cwcomp(pat);
	return (pat);
}

static BOOL
altlist(Expr *e, uchar_t *buf, re_cw *pat)
{
	if (e->type == Alternate)
		return ((BOOL)(altlist(e->l, buf, pat) &&
		    altlist(e->r, buf, pat)));
	return (word(e, buf, pat));
}

static BOOL
word(Expr *e, uchar_t *buf, re_cw *pat)
{
	static uchar_t *p;

	if (buf) p = buf;

	if (e->type == Cat) {
		if (!word(e->l, (uchar_t *)NULL, pat))
			return (NO);
		if (!word(e->r, (uchar_t *)NULL, pat))
			return (NO);
	} else if (e->type == Literal)
		*p++ = e->lit;
	else
		return (NO);

	if (buf)
		re_cwadd(pat, buf, p);
	return (YES);
}

static re_cw *
re_cwinit(uchar_t *cmap)
{
	re_cw *c;

	froot = NULL;
	next_node = NULL;
	next_link = NULL;
	c = (re_cw *)egmalloc(sizeof (*c));
	c->nodeid = 0;
	c->maxdepth = 0;
	c->mindepth = 10000;
	c->root = newnode(c, 0);
	c->cmap = cmap;
	return (c);
}

static void
re_cwadd(re_cw *c, uchar_t *s, uchar_t *e)
{
	Node *p, *state;
	Link *l;
	int depth;

	state = c->root;
	while (s <= --e) {
		for (l = state->alts; l; l = l->next)
			if (l->lit == *e)
				break;
		if (l == NULL)
			break;
		else
			state = l->node;
	}
	if (s <= e) {
		depth = state->d+1;
		l = newlink(*e--, p = newnode(c, depth++));
		l->next = state->alts;
		state->alts = l;
		state = p;
		while (s <= e) {
			state->alts = newlink(*e--, p = newnode(c, depth++));
			state = p;
		}
		if (c->mindepth >= depth) c->mindepth = depth-1;
	}
	state->out = 1;
}

#ifdef	DEBUG
static
pr(Node *n)
{
	Link *l;

	printf("%d[%d,%d]: ", n->id, n->shift1, n->shift2);
	for (l = n->alts; l; l = l->next) {
		printf("edge from \"%d\" to \"%d\" label {\"%c\"};",
		    n->id, l->node->id, l->lit);
		if (l->node->out) {
			printf(" draw \"%d\" as Doublecircle;", l->node->id);
		}
		if (l->node->fail) {
			printf(" edge from \"%d\" to \"%d\" dashed;",
			    l->node->id, l->node->fail->id);
		}
		printf("\n");
		pr(l->node);
	}
}
#endif

static void
fail(Node *root)
{
	Link *qhead = NULL, *qtail = NULL;
	Link *l, *ll;
	Link *t;
	Node *state, *r, *s;
	int a;

	for (l = root->alts; l; l = l->next) {
		ADD(l->node);
		l->node->fail = root;
	}
	while (qhead) {
		r = qhead->node;
		DEL();
		for (l = r->alts; l; l = l->next) {
			s = l->node;
			a = l->lit;
			ADD(s);
			state = r->fail;
			while (state) {
				for (ll = state->alts; ll; ll = ll->next)
					if (ll->lit == a)
						break;
				if (ll || (state == root)) {
					if (ll)
						state = ll->node;
					/*
					 *	do it here as only other exit is
					 *	state 0
					 */
					if (state->out) {
						s->out = 1;
					}
					break;
				} else
					state = state->fail;
			}
			s->fail = state;
		}
	}
	zeroroot(root, root);
}

static void
zeroroot(Node *root, Node *n)
{
	Link *l;

	if (n->fail == root)
		n->fail = NULL;
	for (l = n->alts; l; l = l->next)
		zeroroot(root, l->node);
}

static void
shift(re_cw *c)
{
	Link *qhead = NULL, *qtail = NULL;
	Link *l;
	Link *t;
	Node *state, *r, *s;
	int k;

	for (k = 0; k < 256; k++)
		c->step[k] = c->mindepth+1;
	c->root->shift1 = 1;
	c->root->shift2 = c->mindepth;
	for (l = c->root->alts; l; l = l->next) {
		l->node->shift2 = c->root->shift2;
		ADD(l->node);
		l->node->fail = NULL;
	}
	while (qhead) {
		r = qhead->node;
		DEL();
		r->shift1 = c->mindepth;
		r->shift2 = c->mindepth;
		if ((state = r->fail) != NULL) {
			do {
				k = r->d - state->d;
				if (k < state->shift1) {
					state->shift1 = k;
				}
				if (r->out && (k < state->shift2)) {
					state->shift2 = k;
				}
			} while ((state = state->fail) != NULL);
		}
		for (l = r->alts; l; l = l->next) {
			s = l->node;
			ADD(s);
		}
	}
	shiftprop(c, c->root);
	shifttab(c->root);
	c->step[0] = 1;
}

static void
shifttab(Node *n)
{
	Link *l;
	Node **nn;

	n->tab = nn = (Node **)egmalloc(256 * sizeof (Node *));
	(void) memset((char *)n->tab, 0, 256 * sizeof (Node *));
	for (l = n->alts; l; l = l->next)
		nn[l->lit] = l->node;
}

static void
shiftprop(re_cw *c, Node *n)
{
	Link *l;
	Node *nn;

	for (l = n->alts; l; l = l->next) {
		if (c->step[l->lit] > l->node->d)
			c->step[l->lit] = l->node->d;
		nn = l->node;
		if (n->shift2 < nn->shift2)
			nn->shift2 = n->shift2;
		shiftprop(c, nn);
	}
}

static void
re_cwcomp(re_cw *c)
{
	fail(c->root);
	shift(c);
}

static BOOL
re_cwexec(PATTERN *pat, uchar_t *rs, uchar_t *re, uchar_t **mb, uchar_t **me)
{
	Node *state;
	Link *l;
	uchar_t *sp;
	uchar_t *s;
	uchar_t *e;
	Node *ostate;
	int k;
	re_cw *c = pat->cw_ptr;
	uchar_t fake[1];
	uchar_t mappedsp;

	fake[0] = 0;
	state = c->root;

	s = rs+c->mindepth-1;
	e = re;
	while (s < e) {
		/* scan */
		for (sp = s; (ostate = state) != NULL; ) {
			mappedsp = c->cmap[*sp];
			if (state->tab) {
				if ((state = state->tab[mappedsp]) == NULL)
					goto nomatch;
			} else {
				for (l = state->alts; ; l = l->next) {
					if (l == NULL)
						goto nomatch;
					if (l->lit == mappedsp) {
						state = l->node;
						break;
					}
				}
			}
			if (state->out) {
				*mb = sp;
				*me = s+1;
				if (fixloc(mb, me))
					return (YES);
			}
			if (--sp < rs) {
				sp = fake;
				break;
			}
		}
	nomatch:
		k = c->step[c->cmap[*sp]] - ostate->d - 1;
		if (k < ostate->shift1)
			k = ostate->shift1;
		if (k > ostate->shift2)
			k = ostate->shift2;
		s += k;
		state = c->root;
	}
	return (NO);
}

static Node *
newnode(re_cw *c, int d)
{
	static Node *lim = NULL;
	static int incr = 256;

	if (!next_node) lim = NULL;
	if (next_node == lim) {
		next_node = (Node *)egmalloc(incr * sizeof (Node));
		lim = next_node + incr;
	}
	next_node->d = d;
	if (d > c->maxdepth) c->maxdepth = d;
	next_node->id = c->nodeid++;
	next_node->alts = NULL;
	next_node->tab = NULL;
	next_node->out = 0;
	return (next_node++);
}

static Link *
newlink(uchar_t lit, Node *n)
{
	static Link *lim = NULL;
	static int incr = 256;

	if (!next_link) lim = NULL;
	if (next_link == lim) {
		next_link = (Link *)egmalloc(incr * sizeof (Link));
		lim = next_link + incr;
	}
	next_link->lit = lit;
	next_link->node = n;
	next_link->next = NULL;
	return (next_link++);
}

int
egrep(char *f, FILE *o, char *fo)
{
	uchar_t		buff[MAXBUFSIZE + ESIZE];

	buffer = buff;
	*buffer++ = NL;  /* New line precedes buffer to prevent runover */
	file = f;
	output = o;
	format = fo;
	return (execute());
}

static int
execute(void)
{
	LINE		current;
	BOOL		matched;
	BOOL	all_searched; /* file being matched until end */

	if ((file_desc = open(file, O_RDONLY)) < 0) {
		return (-1);
	}
	init_file(&current);
		/* while there is more get more text from the data stream */
	for (;;) {
		all_searched = NO;

		/*
		 * Find next new-line in buffer.
		 * Begin after previous new line character
		 */

		current.prntbuf = current.newline + 1;
		current.ln++; /* increment line number */

		if (current.prntbuf < bufend) {
			/* There is more text in buffer */

			/*
			 * Take our next
			 * "line" as the entire remaining buffer.
			 * However, if there is more of the file yet
			 * to be read in, exclude any incomplete
			 * line at end.
			 */
			if (file_stat == NO_MORE) {
				all_searched = YES;
				current.newline = bufend - 1;
				if (*current.newline != NL) {
					current.newline = bufend;
				}
			} else {
				/*
				 * Find end of the last
				 * complete line in the buffer.
				 */
				current.newline = bufend;
				while (*--current.newline != NL) {
				}
				if (current.newline < current.prntbuf) {
					/* end not found */
					current.newline = bufend;
				}
			}
		} else {
			/* There is no more text in the buffer. */
			current.newline = bufend;
		}
		if (current.newline >= bufend) {
			/*
			 * There is no more text in the buffer,
			 * or no new line was found.
			 */
			switch (file_stat) {
			case MORE:	/* file partly unread */
			case BEGIN:
				fgetfile(&current);

				current.ln--;
				continue; /* with while loop */
			case NO_MORE:
				break;
			}
			/* Nothing more to read in for this file. */
			if (current.newline <= current.prntbuf) {
				/* Nothing in the buffer, either */
				/* We are done with the file. */
				current.ln--;
				break; /* out of while loop */
			}
			/* There is no NL at the end of the file */
		}

		matched = pattern_match(&match_pattern, &current);
		if (matched) {
			int nc;

			get_ncount(&current, match_pattern.loc1);
			get_line(&current, match_pattern.loc2);

			nc = current.newline + 1 - current.prntbuf;
			(void) fprintf(output, format, file, current.ln);
			(void) fwrite((char *)current.prntbuf, 1, nc, output);
		} else {
			if (all_searched)
				break; /* out of while loop */

			get_ncount(&current, current.newline + 1);
		}
	}

	(void) close(file_desc);
	return (0);
}

static void
init_file(LINE *cur_ptr)
{
	file_stat = BEGIN;
	cur_ptr->ln = 0;
	bufend = buffer;
	cur_ptr->newline = buffer - 1;
}

static BOOL
pattern_match(PATTERN *pat, LINE *lptr)
{
	if ((*pat->procfn)(pat, lptr->prntbuf - 1, lptr->newline + 1,
	    &pat->loc1, &pat->loc2)) {
		return (YES);
	} else {
		pat->loc1 = lptr->prntbuf;
		pat->loc2 = lptr->newline - 1;
		return (NO);
	}
} /* end of function pattern_match() */

static void
fgetfile(LINE *cur_ptr)
{
	/*
	 * This function reads as much of the current file into the buffer
	 * as will fit.
	 */
	int	bytes;	  /* bytes read in current buffer */
	int	bufsize = MAXBUFSIZE; /* free space in data buffer */
	int	save_current;
	uchar_t	*begin = cur_ptr->prntbuf;

	/*
	 * Bytes of current incomplete line, if any, save_current in buffer.
	 * These must be saved.
	 */
	save_current = (int)(bufend - begin);

	if (file_stat == MORE) {
		/*
		 * A portion of the file fills the buffer. We must clear
		 * out the dead wood to make room for more of the file.
		 */

		int k = 0;

		k = begin - buffer;
		if (!k) {
			/*
			 * We have one humungous current line,
			 * which fills the whole buffer.
			 * Toss it.
			 */
			begin = bufend;
			k = begin - buffer;
			save_current = 0;
		}

		begin = buffer;
		bufend = begin + save_current;

		bufsize = MAXBUFSIZE - save_current;

		if (save_current > 0) {
			/*
			 * Must save portion of current line.
			 * Copy to beginning of buffer.
			 */
			(void) memmove(buffer, buffer + k, save_current);
		}
	}

	/* Now read in the file. */

	do {
		bytes = read(file_desc, (char *)bufend, (unsigned int)bufsize);
		if (bytes < 0) {
			/* can't read any more of file */
			bytes = 0;
		}
		bufend += bytes;
		bufsize -= bytes;
	} while (bytes > 0 && bufsize > 0);


	if (begin >= bufend) {
		/* No new lines or incomplete line in buffer */
		file_stat = NO_MORE;
	} else if (bufsize) {
		/* Still space in the buffer, so we have read entire file */
		file_stat = NO_MORE;
	} else {
		/* We filled entire buffer, so there may be more yet to read */
		file_stat = MORE;
	}
		/* Note: bufend is 1 past last good char */
	*bufend = NL;	/* Sentinel new-line character */
	/* Set newline to character preceding the current line */
	cur_ptr->newline = begin - 1;
}

static void
get_line(LINE *cur_ptr, uchar_t *s)
{
	while (*s++ != NL) {
	}
	cur_ptr->newline = --s;
	cur_ptr->ln++;
}

static void
get_ncount(LINE *cur_ptr, uchar_t *s)
{
	uchar_t	*p = cur_ptr->prntbuf;

	while (*--s != NL) {
	}
	cur_ptr->newline = s++;
	while ((s > p) &&
	    (p = (uchar_t *)memchr((char *)p, NL, s - p)) != NULL) {
		cur_ptr->ln++;
		++p;
	}
	cur_ptr->ln--;
	cur_ptr->prntbuf = s;
}