xref: /illumos-gate/usr/src/cmd/oawk/b.c (revision 8aafd47d0dbabbca4365c9565fbe0e051e7346dd)

/*
 * 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 2004 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
/*	  All Rights Reserved  	*/

#include "awk.def"
#include "stdio.h"
#include "awk.h"
#include <stdlib.h>


extern NODE *op2();
extern struct fa *cgotofn();
#define	MAXLIN 256
#define	NCHARS 128
#define	NSTATES 256


#define	type(v)	v->nobj
#define	left(v)	v->narg[0]
#define	right(v)	v->narg[1]
#define	parent(v)	v->nnext


#define	LEAF	case CCL: case NCCL: case CHAR: case DOT:
#define	UNARY	case FINAL: case STAR: case PLUS: case QUEST:


/*
 * encoding in tree NODEs:
 * leaf (CCL, NCCL, CHAR, DOT): left is index,
 * right contains value or pointer to value
 * unary (FINAL, STAR, PLUS, QUEST): left is child, right is null
 * binary (CAT, OR): left and right are children
 * parent contains pointer to parent
 */


struct fa {
union {
		ccl_chars_t s;
		int h;
	} cc;
#define	MLCMPLT(m1, l1, m2, l2) ((m1 != m2 &&\
				(int)m1 < (int)m2) ||\
				(m1 == m2 && (int)l1 < (int)l2))
#define	MLCMPLE(m1, l1, m2, l2) ((m1 != m2 &&\
				(int)m1 <= (int)m2) ||\
				(m1 == m2 && (int)l1 <= (int)l2))
#define	MLCMPGT(m1, l1, m2, l2) ((m1 != m2 &&\
				(int)m1 > (int)m2) ||\
				(m1 == m2 && (int)l1 > (int)l2))
#define	MAX_CODESET	3
	struct fa *st;
};


int	*state[NSTATES];
int	*foll[MAXLIN];
int	setvec[MAXLIN];
NODE	*point[MAXLIN];


int	setcnt;
int	line;


static int	ccln_member();
static int	insert_table();
static int	delete_table();
static void	penter(NODE *p);
static void	follow(NODE *v);
static void	overflo(void);
static void	cfoll(NODE *v);
static void	freetr(NODE *p);
#ifdef DEBUG
#define	ddump_table(t, s)	dump_table(t, s)
#else
#define	ddump_table(t, s)
#endif

struct fa *
makedfa(p)	/* returns dfa for tree pointed to by p */
NODE *p;
{
	NODE *p1;
	struct fa *fap;
	p1 = op2(CAT, op2(STAR, op2(DOT, (NODE *) 0,
		(NODE *) 0), (NODE *) 0), p);
		/* put DOT STAR in front of reg. exp. */
	p1 = op2(FINAL, p1, (NODE *) 0);	/* install FINAL NODE */


	line = 0;
	penter(p1);	/* enter parent pointers and leaf indices */
	point[line] = p1;	/* FINAL NODE */
	setvec[0] = 1;		/* for initial DOT STAR */
	cfoll(p1);	/* set up follow sets */
	fap = cgotofn();
	freetr(p1);	/* add this when alloc works */
	return (fap);
}

static void
penter(NODE *p)	/* set up parent pointers and leaf indices */
{
	switch (type(p)) {
		LEAF
			left(p) = (NODE *)line;
			point[line++] = p;
			break;
		UNARY
			penter(left(p));
			parent(left(p)) = p;
			break;
		case CAT:
		case OR:
			penter(left(p));
			penter(right(p));
			parent(left(p)) = p;
			parent(right(p)) = p;
			break;
		default:
			error(FATAL, "unknown type %d in penter\n", type(p));
			break;
	}
}

static void
freetr(NODE *p)	/* free parse tree and follow sets */
{
	switch (type(p)) {
		LEAF
			xfree(foll[(int)left(p)]);
			xfree(p);
			break;
		UNARY
			freetr(left(p));
			xfree(p);
			break;
		case CAT:
		case OR:
			freetr(left(p));
			freetr(right(p));
			xfree(p);
			break;
		default:
			error(FATAL, "unknown type %d in freetr", type(p));
			break;
	}
}
ccl_chars_t *
cclenter(wchar_t *p)
{
	int 		i, cn;
	wchar_t		c, pc;
	wchar_t		*op;
	ccl_chars_t	*new;
	ccl_chars_t	chars[MAXLIN];

	op = p;
	i = 0;
	while ((c = *p++) != 0) {
		if (c == '-' && i > 0)  {
			if (*p != 0) {
				/*
				 * If there are not in same code set,  the
				 * class should be ignore (make two independent
				 * characters)!
				 */
				c = *p++;
				cn = wcsetno(pc);
				if (cn != wcsetno(c) || pc > c)
					goto char_array;
				i = insert_table(chars, i, cn, pc, cn, c);
				continue;
			}
		}
char_array:
		if (i >= MAXLIN)
			overflo();
		cn = wcsetno(c);
		i = insert_table(chars, i, cn, c, cn, c);
		pc = c;
	}
	dprintf("cclenter: in = |%ws|, ", op, NULL, NULL);
	xfree(op);
	i = (i + 1) * sizeof (ccl_chars_t);
	if ((new = (ccl_chars_t *)malloc(i)) == NULL)
		error(FATAL, "out of space in cclenter on %s", op);
	(void) memcpy((char *)new, (char *)chars, i);
	ddump_table(chars, i / 4);


	return (new);
}

static void
overflo(void)
{
	error(FATAL, "regular expression too long\n");
}

static void
cfoll(NODE *v)	/* enter follow set of each leaf of vertex v into foll[leaf] */
{
	int i;
	int prev;
	int *add();


	switch (type(v)) {
		LEAF
			setcnt = 0;
			for (i = 1; i <= line; i++)
				setvec[i] = 0;
			follow(v);
			foll[(int)left(v)] = add(setcnt);
			break;
		UNARY
			cfoll(left(v));
			break;
		case CAT:
		case OR:
			cfoll(left(v));
			cfoll(right(v));
			break;
		default:
			error(FATAL, "unknown type %d in cfoll", type(v));
	}
}

int
first(NODE *p)		/* collects initially active leaves of p into setvec */
	/* returns 0 or 1 depending on whether p matches empty string */
{
	int b;


	switch (type(p)) {
		LEAF
			if (setvec[(int)left(p)] != 1) {
				setvec[(int)left(p)] = 1;
				setcnt++;
			}
			if (type(p) == CCL &&
			(*(ccl_chars_t *)right(p)).cc_cs == (wchar_t)0x0)
				return (0);		/* empty CCL */
			else return (1);
		case FINAL:
		case PLUS:
			if (first(left(p)) == 0)
				return (0);
			return (1);
		case STAR:
		case QUEST:
			first(left(p));
			return (0);
		case CAT:
			if (first(left(p)) == 0 && first(right(p)) == 0)
				return (0);
			return (1);
		case OR:
			b = first(right(p));
			if (first(left(p)) == 0 || b == 0)
				return (0);
			return (1);
	}
	error(FATAL, "unknown type %d in first\n", type(p));
	return (-1);
}

static void
follow(NODE *v)
		/* collects leaves that can follow v into setvec */
{
	NODE *p;


	if (type(v) == FINAL)
		return;
	p = parent(v);
	switch (type(p)) {
		case STAR:
		case PLUS:	first(v);
				follow(p);
				return;


		case OR:
		case QUEST:	follow(p);
				return;


		case CAT:	if (v == left(p)) { /* v is left child of p */
					if (first(right(p)) == 0) {
						follow(p);
						return;
					}
				} else		/* v is right child */
					follow(p);
				return;
		case FINAL:	if (setvec[line] != 1) {
					setvec[line] = 1;
					setcnt++;
				}
				return;
	}
}


/*
 * There are three type of functions for checking member ship.  Because I have
 * been changed structure of CCL tables.  And some CCL tables end up with NULLs
 * but someone has length and will includes NULLs in table as one of data.
 * Please note, CCL table which has a length data and data will include NULLs,
 * it only used within a this source file("b.c").
 */

int				/* is cs thru ce in s? */
ccl_member(int ns, wchar_t cs, int ne, wchar_t ce, ccl_chars_t *s)
{
	/*
	 * The specified range(cs, ce) must be beside the range between
	 * s->cc_start and s->cc_end to determine member.
	 */
	while (s->cc_cs || s->cc_ce) {
		if (MLCMPLE(s->cc_ns, s->cc_cs, ns, cs) &&
				MLCMPLE(ne, ce, s->cc_ne, s->cc_ce))
			return (1);
		s++;
	}
	return (0);
}


static int			/* is cs thru ce in s? */
ccln_member(int ns, wchar_t cs, int ne, wchar_t ce, ccl_chars_t *s, int n)
{
	/*
	 * The specified range(cs, ce) must be beside the range between
	 * s->cc_start and s->cc_end to determine member.
	 */
	while (n-- > 0) {
		if (MLCMPLE(s->cc_ns, s->cc_cs, ns, cs) &&
				MLCMPLE(ne, ce, s->cc_ne, s->cc_ce))
			return (1);
		s++;
	}
	return (0);
}


int
member(wchar_t c, wchar_t *s)	/* is c in s? */
{
	while (*s)
		if (c == *s++)
			return (1);
	return (0);
}

int
notin(int **array, int n, int *prev) /* is setvec in array[0] thru array[n]? */
{
	int i, j;
	int *ptr;
	for (i = 0; i <= n; i++) {
		ptr = array[i];
		if (*ptr == setcnt) {
			for (j = 0; j < setcnt; j++)
				if (setvec[*(++ptr)] != 1) goto nxt;
			*prev = i;
			return (0);
		}
		nxt: /* dummy */;
	}
	return (1);
}


int *
add(int n)
{		/* remember setvec */
	int *ptr, *p;
	int i;
	if ((p = ptr = (int *)malloc((n+1)*sizeof (int))) == NULL)
		overflo();
	*ptr = n;
	dprintf("add(%d)\n", n, NULL, NULL);
	for (i = 1; i <= line; i++)
		if (setvec[i] == 1) {
			*(++ptr) = i;
		dprintf("  ptr = %o, *ptr = %d, i = %d\n", ptr, *ptr, i);
		}
	dprintf("\n", NULL, NULL, NULL);
	return (p);
}


struct fa *
cgotofn()
{
	int i, k;
	int *ptr;
	int ns, ne;
	wchar_t cs, ce;
	ccl_chars_t *p;
	NODE *cp;
	int j, n, s, ind, numtrans;
	int finflg;
	int curpos, num, prev;
	struct fa *where[NSTATES];


	struct {
		ccl_chars_t	cc;
		int		n;
	} fatab[257];
	struct fa *pfa;


	char index[MAXLIN];
	char iposns[MAXLIN];
	int sposns[MAXLIN];
	int spmax, spinit;
	ccl_chars_t symbol[NCHARS];
	ccl_chars_t isyms[NCHARS];
	ccl_chars_t ssyms[NCHARS];
	int ssmax, symax, ismax, ssinit;


	wchar_t hat;
	int hatcn;


	for (i = 0; i <= line; i++) index[i] = iposns[i] = setvec[i] = 0;
	isyms[0].cc_cs = isyms[0].cc_ce = (wchar_t)0x0;
	for (i = 0; i < NCHARS; i++)
		isyms[i] = symbol[i] = ssyms[i] = isyms[0];
	symax = 0;
	setcnt = 0;
	/* compute initial positions and symbols of state 0 */
	ismax = 0;
	ssmax = 0;
	ptr = state[0] = foll[0];
	spinit = *ptr;
	hat = HAT;
	hatcn = wcsetno(hat);
	for (i = 0; i < spinit; i++) {
		curpos = *(++ptr);
		sposns[i] = curpos;
		iposns[curpos] = 1;
		cp = point[curpos];
		dprintf("i= %d, spinit = %d, curpos = %d\n", i, spinit, curpos);
		switch (type(cp)) {
			case CHAR:
				k = (int)right(cp);
				ns = wcsetno(k);
				if (! ccln_member(ns, k, ns, k,
							isyms, ismax)) {
					ismax = insert_table(isyms, ismax,
								ns, k, ns, k);
				}
				ssyms[ssmax].cc_ns = ns;
				ssyms[ssmax].cc_cs = k;
				ssyms[ssmax].cc_ne = ns;
				ssyms[ssmax++].cc_ce = k;
				break;
			case DOT:
				cs = WC_VERY_SMALL;
				ns = 0;
				ce = HAT - 1;
				ne = hatcn;
				if (! ccln_member(ns, cs, ne, ce,
							isyms, ismax)) {
					ismax = insert_table(isyms, ismax,
								ns, cs, ne, ce);
				}
				ssyms[ssmax].cc_cs = cs;
				ssyms[ssmax].cc_ns = ns;
				ssyms[ssmax].cc_ce = ce;
				ssyms[ssmax++].cc_ne = ne;
				cs = HAT + 1;
				ns = hatcn;
				ce = WC_VERY_LARGE;
				ne = MAX_CODESET;
				if (! ccln_member(ns, cs, ne, ce,
							isyms, ismax)) {
					ismax = insert_table(isyms, ismax,
								ns, cs, ne, ce);
				}
				ssyms[ssmax].cc_cs = cs;
				ssyms[ssmax].cc_ns = ns;
				ssyms[ssmax].cc_ce = ce;
				ssyms[ssmax++].cc_ne = ne;
				break;
			case CCL:
				cs = HAT;
				ns = hatcn;
				for (p = (ccl_chars_t *)right(cp);
					p->cc_cs; p++) {
					if ((p->cc_ns != ns ||\
					p->cc_cs != cs) &&\
				!ccln_member(p->cc_ns, p->cc_cs,
				p->cc_ne, p->cc_ce, isyms, ismax)) {
						ismax = insert_table(isyms,
				ismax, p->cc_ns, p->cc_cs, p->cc_ne, p->cc_ce);
					}
					ssyms[ssmax++] = *p;
				}
				break;
			case NCCL:
				ns = 0;
				cs = WC_VERY_SMALL;
				for (p = (ccl_chars_t *)right(cp);
					p->cc_cs; p++) {
					if ((ns != hatcn || p->cc_cs != HAT) &&
						! ccln_member(ns, cs,
							p->cc_ns, p->cc_cs-1,
								isyms, ismax)) {
						ismax = insert_table(isyms,
								ismax,
								ns, cs,
								p->cc_ns,
								p->cc_cs-1);
					}
					ssyms[ssmax].cc_ns = ns;
					ssyms[ssmax].cc_cs = cs;
					ssyms[ssmax].cc_ne = p->cc_ns;
					ssyms[ssmax++].cc_ce = p->cc_cs-1;
					if (p->cc_ce == (wchar_t)0x0) {
						ns = p->cc_ns;
						cs = p->cc_cs + 1;

					} else {
						ns = p->cc_ne;
						cs = p->cc_ce + 1;
					}
				}
				if ((ns != hatcn || cs != HAT) &&
					! ccln_member(ns, cs,
						MAX_CODESET, WC_VERY_LARGE,
							isyms, ismax)) {
					ismax = insert_table(isyms, ismax,
							ns, cs, MAX_CODESET,
							WC_VERY_LARGE);
				}
				ssyms[ssmax].cc_ns = ns;
				ssyms[ssmax].cc_cs = cs;
				ssyms[ssmax].cc_ne = MAX_CODESET;
				ssyms[ssmax++].cc_ce = WC_VERY_LARGE;
				break;
		}
	}
	ssinit = ssmax;
	symax = 0;
	n = 0;
	for (s = 0; s <= n; s++)  {
		dprintf("s = %d\n", s, NULL, NULL);
		ind = 0;
		numtrans = 0;
		finflg = 0;
		if (*(state[s] + *state[s]) == line) {		/* s final? */
			finflg = 1;
			goto tenter;
		}
		spmax = spinit;
		ssmax = ssinit;
		ptr = state[s];
		num = *ptr;
		for (i = 0; i < num; i++) {
			curpos = *(++ptr);
			if (iposns[curpos] != 1 && index[curpos] != 1) {
				index[curpos] = 1;
				sposns[spmax++] = curpos;
			}
			cp = point[curpos];
			switch (type(cp)) {
				case CHAR:
					k = (int)right(cp);
					ns = wcsetno(k);
					if (! ccln_member(ns, k, ns, k,
							isyms, ismax) &&
						! ccln_member(ns, k, ns, k,
							symbol, symax)) {
						symax = insert_table(symbol,
									symax,
									ns, k,
									ns, k);
					}
					ssyms[ssmax].cc_ns = ns;
					ssyms[ssmax].cc_cs = k;
					ssyms[ssmax].cc_ne = ns;
					ssyms[ssmax++].cc_ce = k;
					break;
				case DOT:
					cs = WC_VERY_SMALL;
					ns = 0;
					ce = HAT - 1;
					ne = hatcn;
					if (! ccln_member(ns, cs, ne, ce,
							isyms, ismax) &&
						! ccln_member(ns, cs, ne, ce,
							symbol, symax)) {
						symax = insert_table(symbol,
									symax,
									ns, cs,
									ne, ce);
					}
					ssyms[ssmax].cc_cs = cs;
					ssyms[ssmax].cc_ns = ns;
					ssyms[ssmax].cc_ce = ce;
					ssyms[ssmax++].cc_ne = ne;
					cs = HAT + 1;
					ns = hatcn;
					ce = WC_VERY_LARGE;
					ne = MAX_CODESET;
					if (! ccln_member(ns, cs, ne, ce,
								isyms, ismax) &&
						! ccln_member(ns, cs, ne, ce,
							symbol, symax)) {
						symax = insert_table(symbol,
									symax,
									ns, cs,
									ne, ce);
					}
					ssyms[ssmax].cc_cs = cs;
					ssyms[ssmax].cc_ns = ns;
					ssyms[ssmax].cc_ce = ce;
					ssyms[ssmax++].cc_ne = ne;
					break;
				case CCL:
					cs = HAT;
					ns = hatcn;
					for (p = (ccl_chars_t *)right(cp);
						p->cc_cs; p++) {
						if ((p->cc_ns != ns ||
							p->cc_cs != cs) &&
							! ccln_member(p->cc_ns,
							p->cc_cs, p->cc_ne,
						p->cc_ce, isyms, ismax) &&
						!ccln_member(p->cc_ns, p->cc_cs,
						p->cc_ne, p->cc_ce, symbol,
						symax)) {
							symax = insert_table(
						symbol, symax, p->cc_ns,
						p->cc_cs, p->cc_ne, p->cc_ce);
						}
						ssyms[ssmax++] = *p;
					}
					break;
				case NCCL:
					ns = 0;
					cs = WC_VERY_SMALL;
		for (p = (ccl_chars_t *)right(cp); p->cc_cs; p++) {
			if ((p->cc_ns != hatcn || p->cc_cs != HAT) &&
					! ccln_member(ns, cs, p->cc_ns,
					p->cc_cs-1, isyms, ismax) &&
					! ccln_member(ns, cs, p->cc_ns,
					p->cc_cs-1, symbol, symax)) {
				symax = insert_table(symbol,
					symax, ns, cs, p->cc_ns, p->cc_cs-1);
						}
						ssyms[ssmax].cc_ns = ns;
						ssyms[ssmax].cc_cs = cs;
						ssyms[ssmax].cc_ne = p->cc_ns;
						ssyms[ssmax++].cc_ce
								= p->cc_cs-1;
						if (p->cc_ce == (wchar_t)0x0) {
							ns = p->cc_ns;
							cs = p->cc_cs + 1;

						} else {
							ns = p->cc_ne;
							cs = p->cc_ce + 1;
						}
					}
		if ((ns != hatcn || cs != HAT) && ! ccln_member(ns, cs,
				MAX_CODESET, WC_VERY_LARGE, isyms, ismax) &&
				! ccln_member(ns, cs, MAX_CODESET,
					WC_VERY_LARGE, symbol, symax)) {
			symax = insert_table(symbol, symax, ns, cs,
								MAX_CODESET,
								WC_VERY_LARGE);
					}
					ssyms[ssmax].cc_ns = ns;
					ssyms[ssmax].cc_cs = cs;
					ssyms[ssmax].cc_ne = MAX_CODESET;
					ssyms[ssmax++].cc_ce = WC_VERY_LARGE;
					break;
			}
		}
		for (j = 0; j < ssmax; j++) {	/* nextstate(s, ssyms[j]) */
			ns = ssyms[j].cc_ns;
			cs = ssyms[j].cc_cs;
			ne = ssyms[j].cc_ne;
			ce = ssyms[j].cc_ce;
dprintf("j = %d, cs = %o, ce = %o\n", j, cs, ce);
			symax = delete_table(symbol, symax, ns, cs, ne, ce);
			setcnt = 0;
			for (k = 0; k <= line; k++) setvec[k] = 0;
			for (i = 0; i < spmax; i++) {
				index[sposns[i]] = 0;
				cp = point[sposns[i]];
				if ((k = type(cp)) != FINAL) {
					if (k == CHAR && ns == ne && cs == ce &&
						cs == (int)right(cp) ||
						k == DOT || k == CCL &&
						ccl_member(ns, cs, ne, ce,
						(ccl_chars_t *)right(cp)) ||
						k == NCCL &&
						!ccl_member(ns, cs, ne, ce,
						(ccl_chars_t *)right(cp))) {
						ptr = foll[sposns[i]];
						num = *ptr;
						for (k = 0; k < num; k++) {
						if (setvec[*(++ptr)] != 1 &&
							iposns[*ptr] != 1) {
							setvec[*ptr] = 1;
								setcnt++;
							}
						}
					}
				}
			} /* end nextstate */
			if (notin(state, n, &prev)) {
				if (n >= NSTATES - 1) {
		printf("cgotofn: notin; state = %d, n = %d\n", state, n, NULL);
					overflo();
				}
				state[++n] = add(setcnt);
				dprintf("	delta(%d,[%o,%o])",
					s, cs, ce);
				dprintf(" = %d, ind = %d\n", n, ind+1, NULL);
				fatab[++ind].cc.cc_ns = ns;
				fatab[ind].cc.cc_cs = cs;
				fatab[ind].cc.cc_ne = ne;
				fatab[ind].cc.cc_ce = ce;
				fatab[ind].n = n;
				numtrans++;
			} else {
				if (prev != 0) {
					dprintf("	delta(%d,[%o,%o])",
						s, cs, ce);
					dprintf("= %d, ind = %d\n",
						prev, ind+1, NULL);
					fatab[++ind].cc.cc_ns = ns;
					fatab[ind].cc.cc_cs = cs;
					fatab[ind].cc.cc_ne = ne;
					fatab[ind].cc.cc_ce = ce;
					fatab[ind].n = prev;
					numtrans++;
				}
			}
		}
	tenter:
		if ((pfa = (struct fa *)malloc((numtrans + 1)
						* sizeof (struct fa))) == NULL)
			overflo();
		where[s] = pfa;
		if (finflg)
			pfa->cc.h = -1;		/* s is a final state */
		else
			pfa->cc.h = numtrans;
		pfa->st = 0;
		for (i = 1, pfa += 1; i <= numtrans; i++, pfa++) {
			pfa->cc.s = fatab[i].cc;
			pfa->st = (struct fa *)fatab[i].n;
		}
	}
	for (i = 0; i <= n; i++) {
		if (i != 0)	/* state[0] is freed later in freetr() */
			xfree(state[i]);	/* free state[i] */
		pfa = where[i];
		pfa->st = where[0];
		dprintf("state %d: (%o)\n", i, pfa, NULL);
		dprintf("	numtrans = %d,	default = %o\n",
			pfa->cc.h, pfa->st, NULL);
		for (k = 1; k <= pfa->cc.h; k++) {
			(pfa+k)->st = where[(int)(pfa+k)->st];
			dprintf("	char = [%o,%o],	nextstate = %o\n",
				(pfa+k)->cc.s.cc_cs, (pfa+k)->cc.s.cc_ce,
				(pfa+k)->st);
		}
	}
	pfa = where[0];
	if ((num = pfa->cc.h) < 0)
		return (where[0]);
	for (pfa += num; num; num--, pfa--)
		if (pfa->cc.s.cc_ns == hatcn && pfa->cc.s.cc_cs == HAT) {
			return (pfa->st);
		}
	return (where[0]);
}


/*
 * Insert CCL entry to CCL table with maintain optimized order.
 */
static int
insert_table(ccl_chars_t *table_base, int table_size, int ns, wchar_t cs,
	int ne, wchar_t ce)
{
	int		i;
	int		tns, tne;
	wchar_t		tcs, tce;
	ccl_chars_t	*table;
	ccl_chars_t	*saved_table;
	int		saved_i;




	dprintf("Inserting {%o, %o} to table %o\n", cs, ce, table_base);
	/*
	 * Searching the table to find out where should put the new item.
	 */
	for (i = 0, table = table_base; i < table_size; i++, table++) {
		tns = table->cc_ns;
		tcs = table->cc_cs;
		tne = table->cc_ne;
		tce = table->cc_ce;
		if (MLCMPLT(ne, ce, tns, (tcs - 1))) {
			/*
			 * Quick! insert to font of current table entries.
			 */
qinsert:
			table_size++;
			for (; i < table_size; i++, table++) {
				tns = table->cc_ns;
				tcs = table->cc_cs;
				tne = table->cc_ne;
				tce = table->cc_ce;
				table->cc_ns = ns;
				table->cc_cs = cs;
				table->cc_ne = ne;
				table->cc_ce = ce;
				ns = tns;
				cs = tcs;
				ne = tne;
				ce = tce;
			}
			goto add_null;
		} else if (MLCMPLE(tns, (tcs - 1), ns, cs) &&
				MLCMPLE(ns, cs, tne, (tce + 1))) {
			/*
			 * Starting point is within the current entry.
			 */
			if (MLCMPGT(tns, tcs, ns, cs)) {
				table->cc_ns = ns;
				table->cc_cs = cs;
			}
			if (MLCMPLE(ne, ce, tne, tce)) {
				return (table_size);
			}
			goto combine;
		}
	}


	/*
	 * Adding new one to end of table.
	 */
	table->cc_ns = ns;
	table->cc_cs = cs;
	table->cc_ne = ne;
	table->cc_ce = ce;


	table_size++;
	goto add_null;




	combine:
	/*
	 * Check and try to combine the new entry with rest of entries.
	 */
	if ((i + 1) >= table_size) {
		table->cc_ne = ne;
		table->cc_ce = ce;
		return (table_size);
	}


	saved_table = table++;
	saved_i = i++;


	/*
	 * Finding the spot where we should put the end point.
	 */
	for (; i < table_size; i++, table++) {
		if (MLCMPLT(ne, ce, table->cc_ns, (table->cc_cs - 1))) {
			break;
		} else
		if (MLCMPLE(table->cc_ns, (table->cc_cs - 1), ne, ce) &&
			MLCMPLE(ne, ce, table->cc_ne, (table->cc_ce + 1))) {
			/*
			 * Tack with this table.
			 */
			if (MLCMPLT(ne, ce, table->cc_ne, table->cc_ce)) {
				ne = table->cc_ne;
				ce = table->cc_ce;
			}
			table++;
			i++;
			break;
		}
	}


	saved_table->cc_ne = ne;
	saved_table->cc_ce = ce;
	saved_i = table_size - (i - saved_i - 1);


	/*
	 * Moving the rest of entries.
	 */
	for (; i < table_size; i++, table++)
		*(++saved_table) = *table;
	table_size = saved_i;


add_null:
	table_base[table_size].cc_cs = (wchar_t)0x0;
	table_base[table_size].cc_ce = (wchar_t)0x0;


	return (table_size);
}




static int
delete_table(ccl_chars_t *table_base, int table_size, int ns, wchar_t cs,
		int ne, wchar_t ce)
{
	int		i;
	int		saved_i;
	ccl_chars_t	*table;
	ccl_chars_t	*saved_table;
	int		tns;
	wchar_t		tcs;
	int		tne;
	wchar_t		tce;




	for (i = 0, table = table_base; i < table_size; i++, table++) {
		tns = table->cc_ns;
		tcs = table->cc_cs;
		tne = table->cc_ne;
		tce = table->cc_ce;
		if (MLCMPLT(ne, ce, tns, tcs))
			return (table_size);
		else if (MLCMPLT(ne, ce, tne, tce)) {
			if (MLCMPLE(ns, cs, tns, tcs)) {
				/*
				 * Shrink type 1.
				 */
				table->cc_ns = ne;
				table->cc_cs = ce + 1;
				return (table_size);

			} else {
				/*
				 * Spliting !!
				 */
				table->cc_ns = ne;
				table->cc_cs = ce + 1;
				tne = ns;
				tce = cs - 1;
				table_size++;
				for (; i < table_size; i++, table++) {
					ns = table->cc_ns;
					cs = table->cc_cs;
					ne = table->cc_ne;
					ce = table->cc_ce;
					table->cc_ns = tns;
					table->cc_cs = tcs;
					table->cc_ne = tne;
					table->cc_ce = tce;
					tns = ns;
					tcs = cs;
					tne = ne;
					tce = ce;
				}
				return (table_size);
			}

		} else if (MLCMPLE(ns, cs, tne, tce)) {
			if (MLCMPGT(ns, cs, tns, tcs)) {
				/*
				 * Shrink current table(type 2).
				 */
				table->cc_ne = ns;
				table->cc_ce = cs - 1;
				table++;
				i++;
			}
			/*
			 * Search for the end point.
			 */
			saved_i = i;
			saved_table = table;
			for (; i < table_size; i++, table++) {
				if (MLCMPLT(ne, ce,
						table->cc_ns, table->cc_cs)) {
					/*
					 * Easy point, no shrinks!
					 */
					break;

				} else if (MLCMPGT(table->cc_ne, table->cc_ce,
						ne, ce)) {
					/*
					 * Shrinking...
					 */
					table->cc_ns = ne;
					table->cc_cs = ce + 1;
					break;
				}


			}
			/*
			 * Moving(removing) backword.
			 */
			saved_i = table_size - (i - saved_i);
			for (; i < table_size; i++)
				*saved_table++ = *table++;
			return (saved_i);
		}
	}
	return (table_size);
}


#ifdef DEBUG
dump_table(ccl_chars_t *table, int size)
{
	int	i;




	if (! dbg)
		return;


	printf("Duming table %o with size %d\n", table, size);
	size++;	/* To watch out NULL */
	for (i = 0; i < size; i++, table++) {
		printf("{%3o, %3o}, ", table->cc_cs, table->cc_ce);
	}
	printf("\n");
}
#endif /* DEBUG */



int
match(struct fa *pfa, wchar_t *p)
{
	int count;
	int n, ns, ne;
	wchar_t c, cs, ce;


	if (p == 0)
		return (0);
	if (pfa->cc.h == 1) { /* fast test for first character, if possible */
		ns = (++pfa)->cc.s.cc_ns;
		cs = (pfa)->cc.s.cc_cs;
		ne = (pfa)->cc.s.cc_ne;
		ce = (pfa)->cc.s.cc_ce;
		do {
			c = *p;
			n = wcsetno(c);
			if (MLCMPLE(ns, cs, n, c) &&
				MLCMPLE(n, c, ne, ce)) {
				p++;
				pfa = pfa->st;
				goto adv;
			}
		} while (*p++ != 0);
		return (0);
	}
	adv: if ((count = pfa->cc.h) < 0)
		return (1);
	do {
		c = *p;
		n = wcsetno(c);
		for (pfa += count; count; count--, pfa--) {
			ns = (pfa)->cc.s.cc_ns;
			cs = (pfa)->cc.s.cc_cs;
			ne = (pfa)->cc.s.cc_ne;
			ce = (pfa)->cc.s.cc_ce;
			if (MLCMPLE(ns, cs, n, c) && MLCMPLE(n, c, ne, ce))
				break;
		}
		pfa = pfa->st;
		if ((count = pfa->cc.h) < 0)
			return (1);
	} while (*p++ != 0);
	return (0);
}