39 #define NISERR() VISERR(nfa->v) 40 #define NERR(e) VERR(nfa->v, (e)) 53 nfa = (
struct nfa *)
MALLOC(
sizeof(
struct nfa));
102 while ((s = nfa->
states) != NULL)
107 while ((s = nfa->
free) != NULL)
123 static struct state *
139 if (nfa->
free != NULL)
174 if (nfa->
slast != NULL)
187 static struct state *
194 s->
flag = (char) flag;
207 while ((a = s->
ins) != NULL)
209 while ((a = s->
outs) != NULL)
256 for (ab = s->
oas.
next; ab != NULL; ab = abnext)
284 assert(from != NULL && to != NULL);
301 if (a->
to == to && a->
co == co && a->
type == t)
307 if (a->
from == from && a->
co == co && a->
type == t)
402 for (i = 0; i <
ABSIZE; i++)
405 newAb->
a[
i].freechain = &newAb->
a[i + 1];
407 newAb->
a[ABSIZE - 1].freechain = NULL;
408 s->
free = &newAb->
a[0];
413 s->
free = a->freechain;
426 struct arc *predecessor;
437 if (predecessor == NULL)
457 if (predecessor == NULL)
482 victim->freechain = from->
free;
498 struct arc *predecessor;
505 if (predecessor == NULL)
561 if (a->
type == type && a->
co == co)
585 struct arc **sortarray;
593 sortarray = (
struct arc **)
MALLOC(n *
sizeof(
struct arc *));
594 if (sortarray == NULL)
611 for (i = 1; i < n - 1; i++)
626 const struct arc *aa = *((
const struct arc *
const *) a);
627 const struct arc *bb = *((
const struct arc *
const *) b);
652 struct arc **sortarray;
660 sortarray = (
struct arc **)
MALLOC(n *
sizeof(
struct arc *));
661 if (sortarray == NULL)
678 for (i = 1; i < n - 1; i++)
693 const struct arc *aa = *((
const struct arc *
const *) a);
694 const struct arc *bb = *((
const struct arc *
const *) b);
720 #define BULK_ARC_OP_USE_SORT(nsrcarcs, ndestarcs) \ 721 ((nsrcarcs) < 4 ? 0 : ((nsrcarcs) > 32 || (ndestarcs) > 32)) 737 struct state *oldState,
738 struct state *newState)
740 assert(oldState != newState);
747 while ((a = oldState->
ins) != NULL)
779 while (oa != NULL && na != NULL)
829 struct state *oldState,
830 struct state *newState)
832 assert(oldState != newState);
839 for (a = oldState->
ins; a != NULL; a = a->
inchain)
868 while (oa != NULL && na != NULL)
912 struct arc **arcarray,
944 for (i = 1; i < arccount; i++)
950 arcarray[++j] = arcarray[
i];
969 while (i < arccount && na != NULL)
971 struct arc *a = arcarray[
i];
996 struct arc *a = arcarray[
i];
1008 struct state *oldState,
1009 struct state *newState)
1011 assert(oldState != newState);
1018 while ((a = oldState->
outs) != NULL)
1020 cparc(nfa, a, newState, a->
to);
1048 oa = oldState->
outs;
1049 na = newState->
outs;
1050 while (oa != NULL && na != NULL)
1097 struct state *oldState,
1098 struct state *newState)
1100 assert(oldState != newState);
1108 cparc(nfa, a, newState, a->
to);
1134 oa = oldState->
outs;
1135 na = newState->
outs;
1136 while (oa != NULL && na != NULL)
1186 newarc(nfa, type, a->
co, from, to);
1220 struct state *leftend,
1240 while ((a = s->
outs) != NULL)
1248 if (to->
nins == 0 && to->
tmp == NULL)
1271 struct state *start,
1367 static struct state *
1382 if (s1->
outs == NULL)
1441 int verbose = (f != NULL) ? 1 : 0;
1444 fprintf(f,
"\ninitial cleanup:\n");
1451 fprintf(f,
"\nempties:\n");
1456 fprintf(f,
"\nconstraints:\n");
1463 fprintf(f,
"\nfinal cleanup:\n");
1481 struct state *nexts;
1484 struct state *intermediates;
1491 for (s = nfa->
states; s != NULL && !
NISERR(); s = nexts)
1494 intermediates = NULL;
1495 for (a = s->
outs; a != NULL && !
NISERR(); a = nexta)
1499 if (
pull(nfa, a, &intermediates))
1503 while (intermediates != NULL)
1505 struct state *ns = intermediates->
tmp;
1507 intermediates->
tmp = NULL;
1514 if (progress && f != NULL)
1516 }
while (progress && !
NISERR());
1526 for (a = nfa->
pre->
outs; a != NULL; a = nexta)
1559 struct state **intermediates)
1570 if (from->
nins == 0)
1581 if (from->
nouts > 1)
1587 cparc(nfa, con, s, to);
1597 for (a = from->
ins; a != NULL && !
NISERR(); a = nexta)
1609 for (s = *intermediates; s != NULL; s = s->
tmp)
1620 s->
tmp = *intermediates;
1624 cparc(nfa, a, s, to);
1648 struct state *nexts;
1651 struct state *intermediates;
1658 for (s = nfa->
states; s != NULL && !
NISERR(); s = nexts)
1661 intermediates = NULL;
1662 for (a = s->
ins; a != NULL && !
NISERR(); a = nexta)
1666 if (
push(nfa, a, &intermediates))
1670 while (intermediates != NULL)
1672 struct state *ns = intermediates->
tmp;
1674 intermediates->
tmp = NULL;
1681 if (progress && f != NULL)
1683 }
while (progress && !
NISERR());
1693 for (a = nfa->
post->
ins; a != NULL; a = nexta)
1726 struct state **intermediates)
1754 cparc(nfa, con, from, s);
1764 for (a = to->
outs; a != NULL && !
NISERR(); a = nexta)
1776 for (s = *intermediates; s != NULL; s = s->
tmp)
1787 s->
tmp = *intermediates;
1791 cparc(nfa, a, from, s);
1818 #define CA(ct,at) (((ct)<<CHAR_BIT) | (at)) 1828 if (con->
co == a->
co)
1836 if (con->
co == a->
co)
1874 struct state *nexts;
1878 struct arc **inarcsorig;
1879 struct arc **arcarray;
1889 for (s = nfa->
states; s != NULL && !
NISERR(); s = nexts)
1907 for (s = nfa->
states; s != NULL && !
NISERR(); s = nexts)
1980 if (inarcsorig == NULL)
1986 for (s = nfa->
states; s != NULL; s = s->
next)
1988 inarcsorig[s->
no] = s->
ins;
1989 totalinarcs += s->
nins;
1998 arcarray = (
struct arc **)
MALLOC(totalinarcs *
sizeof(
struct arc *));
1999 if (arcarray == NULL)
2015 for (s2 =
emptyreachable(nfa, s, s, inarcsorig); s2 != s; s2 = nexts)
2018 for (a = inarcsorig[s2->
no]; a != NULL; a = a->
inchain)
2021 arcarray[arccount++] = a;
2029 assert(arccount <= totalinarcs);
2035 mergeins(nfa, s, arcarray, arccount);
2038 nskip = s->
nins - prevnins;
2042 inarcsorig[s->
no] = a;
2054 for (s = nfa->
states; s != NULL; s = s->
next)
2056 for (a = s->
outs; a != NULL; a = nexta)
2069 for (s = nfa->
states; s != NULL; s = nexts)
2095 static struct state *
2098 struct state *lastfound,
2099 struct arc **inarcsorig)
2112 for (a = inarcsorig[s->
no]; a != NULL; a = a->
inchain)
2167 struct state *nexts;
2179 for (s = nfa->
states; s != NULL && !
NISERR(); s = nexts)
2184 for (a = s->
outs; a != NULL && !
NISERR(); a = nexta)
2201 if (
NISERR() || !hasconstraints)
2230 for (s = nfa->
states; s != NULL; s = nexts)
2354 struct state *shead;
2355 struct state *stail;
2356 struct state *sclone;
2357 struct state *nexts;
2391 }
while (s != sinitial);
2396 shead = refarc->
from;
2404 stail = sinitial->
tmp;
2412 for (s = nfa->
states; s != NULL; s = s->
next)
2436 if (sclone->
nouts == 0)
2446 for (a = shead->
outs; a != NULL; a = nexta)
2452 cparc(nfa, a, shead, sclone);
2498 struct state *ssource,
2499 struct state *sclone,
2500 struct state *spredecessor,
2517 donemap = curdonemap;
2518 if (donemap == NULL)
2520 donemap = (
char *)
MALLOC(nstates *
sizeof(
char));
2521 if (donemap == NULL)
2527 if (outerdonemap != NULL)
2535 memcpy(donemap, outerdonemap, nstates *
sizeof(
char));
2540 memset(donemap, 0, nstates *
sizeof(
char));
2541 assert(spredecessor->
no < nstates);
2542 donemap[spredecessor->
no] = 1;
2549 donemap[ssource->
no] = 1;
2582 struct state *prevclone;
2591 if (donemap[sto->
no] != 0)
2601 if (a2->
to->
tmp == sto)
2614 if (refarc && a->
type == refarc->
type && a->
co == refarc->
co)
2661 cparc(nfa, a, sclone, prevclone);
2668 struct state *stoclone;
2671 if (stoclone == NULL)
2677 stoclone->
tmp = sto;
2679 cparc(nfa, a, sclone, stoclone);
2688 cparc(nfa, a, sclone, sto);
2699 if (curdonemap == NULL)
2703 struct state *stoclone = a->
to;
2708 stoclone->
tmp = NULL;
2732 struct state *nexts;
2742 for (s = nfa->
states; s != NULL && !
NISERR(); s = nexts)
2755 for (s = nfa->
states; s != NULL; s = s->
next)
2851 for (s = nfa->
states; s != NULL; s = s->
next)
2854 narcs += s->
nouts + 1;
2864 if (cnfa->
states != NULL)
2866 if (cnfa->
arcs != NULL)
2874 cnfa->
bos[0] = nfa->
bos[0];
2875 cnfa->
bos[1] = nfa->
bos[1];
2876 cnfa->
eos[0] = nfa->
eos[0];
2877 cnfa->
eos[1] = nfa->
eos[1];
2882 for (s = nfa->
states; s != NULL; s = s->
next)
2934 const struct carc *aa = (
const struct carc *) a;
2935 const struct carc *bb = (
const struct carc *) b;
2937 if (aa->
co < bb->
co)
2939 if (aa->
co > bb->
co)
2941 if (aa->
to < bb->
to)
2943 if (aa->
to > bb->
to)
2973 fprintf(f,
"pre %d, post %d", nfa->
pre->
no, nfa->
post->
no);
2975 fprintf(f,
", bos [%ld]", (
long) nfa->
bos[0]);
2977 fprintf(f,
", bol [%ld]", (
long) nfa->
bos[1]);
2979 fprintf(f,
", eos [%ld]", (
long) nfa->
eos[0]);
2981 fprintf(f,
", eol [%ld]", (
long) nfa->
eos[1]);
2983 for (s = nfa->
states; s != NULL; s = s->
next)
2989 fprintf(f,
"total of %d states, %d arcs\n", nstates, narcs);
2991 dumpcolors(nfa->
cm, f);
3002 dumpstate(
struct state *s,
3007 fprintf(f,
"%d%s%c", s->
no, (s->
tmp != NULL) ?
"T" :
"",
3010 fprintf(f,
"\tstate chain bad\n");
3012 fprintf(f,
"\tno out arcs\n");
3019 fprintf(f,
"\tlink from %d to %d on %d's in-chain\n",
3028 dumparcs(
struct state *s,
3051 }
while (a != NULL);
3060 dumparc(
struct arc *a,
3071 fprintf(f,
"[%ld]", (
long) a->
co);
3074 fprintf(f,
">%ld>", (
long) a->
co);
3077 fprintf(f,
"<%ld<", (
long) a->
co);
3080 fprintf(f,
":%ld:", (
long) a->
co);
3084 fprintf(f,
"%c%d", a->
type, (
int) a->
co);
3089 fprintf(f,
"0x%x/0%lo", a->
type, (
long) a->
co);
3093 fprintf(f,
"?%d?", a->
from->
no);
3094 for (ab = &a->
from->
oas; ab != NULL; ab = ab->
next)
3096 for (aa = &ab->
a[0]; aa < &ab->a[
ABSIZE]; aa++)
3110 fprintf(f,
"%d", a->
to->
no);
3129 fprintf(f,
"pre %d, post %d", cnfa->
pre, cnfa->
post);
3131 fprintf(f,
", bos [%ld]", (
long) cnfa->
bos[0]);
3133 fprintf(f,
", bol [%ld]", (
long) cnfa->
bos[1]);
3135 fprintf(f,
", eos [%ld]", (
long) cnfa->
eos[0]);
3137 fprintf(f,
", eol [%ld]", (
long) cnfa->
eos[1]);
3139 fprintf(f,
", haslacons");
3141 for (st = 0; st < cnfa->
nstates; st++)
3142 dumpcstate(st, cnfa, f);
3165 fprintf(f,
"\t[%ld]->%d", (
long) ca->
co, ca->
to);
3167 fprintf(f,
"\t:%ld:->%d", (
long) (ca->
co - cnfa->
ncolors), ca->
to);
3176 if (ca == cnfa->
states[st] || pos != 1)
static void fixconstraintloops(struct nfa *nfa, FILE *f)
static void markreachable(struct nfa *nfa, struct state *s, struct state *okay, struct state *mark)
static void moveouts(struct nfa *nfa, struct state *oldState, struct state *newState)
static long optimize(struct nfa *nfa, FILE *f)
static void fixempties(struct nfa *nfa, FILE *f)
static struct nfa * newnfa(struct vars *v, struct colormap *cm, struct nfa *parent)
static int push(struct nfa *nfa, struct arc *con, struct state **intermediates)
static void pullback(struct nfa *nfa, FILE *f)
static int carc_cmp(const void *a, const void *b)
static void changearctarget(struct arc *a, struct state *newto)
static void deltraverse(struct nfa *nfa, struct state *leftend, struct state *s)
static void copyins(struct nfa *nfa, struct state *oldState, struct state *newState)
static struct state * emptyreachable(struct nfa *nfa, struct state *s, struct state *lastfound, struct arc **inarcsorig)
static void dumpnfa(struct nfa *nfa, FILE *f)
static void mergeins(struct nfa *nfa, struct state *s, struct arc **arcarray, int arccount)
static void freecnfa(struct cnfa *cnfa)
#define REG_MAX_COMPILE_SPACE
static struct state * newfstate(struct nfa *nfa, int flag)
static color pseudocolor(struct colormap *cm)
#define BULK_ARC_OP_USE_SORT(nsrcarcs, ndestarcs)
static void pushfwd(struct nfa *nfa, FILE *f)
static void markcanreach(struct nfa *nfa, struct state *s, struct state *okay, struct state *mark)
static void copyouts(struct nfa *nfa, struct state *oldState, struct state *newState)
static void breakconstraintloop(struct nfa *nfa, struct state *sinitial)
static void cloneouts(struct nfa *nfa, struct state *old, struct state *from, struct state *to, int type)
static void dupnfa(struct nfa *nfa, struct state *start, struct state *stop, struct state *from, struct state *to)
static int hasnonemptyout(struct state *s)
static void colorchain(struct colormap *cm, struct arc *a)
static int isconstraintarc(struct arc *a)
static struct arc * allocarc(struct nfa *nfa, struct state *s)
static struct state * single_color_transition(struct state *s1, struct state *s2)
static int hasconstraintout(struct state *s)
static void clonesuccessorstates(struct nfa *nfa, struct state *ssource, struct state *sclone, struct state *spredecessor, struct arc *refarc, char *curdonemap, char *outerdonemap, int nstates)
static int sortins_cmp(const void *a, const void *b)
static void freearc(struct nfa *nfa, struct arc *victim)
static void freenfa(struct nfa *nfa)
static void specialcolors(struct nfa *nfa)
static void cleartraverse(struct nfa *nfa, struct state *s)
static void rainbow(struct nfa *nfa, struct colormap *cm, int type, color but, struct state *from, struct state *to)
static void moveins(struct nfa *nfa, struct state *oldState, struct state *newState)
static struct arc * findarc(struct state *s, int type, color co)
static int findconstraintloop(struct nfa *nfa, struct state *s)
static struct state * newstate(struct nfa *nfa)
static void delsub(struct nfa *nfa, struct state *lp, struct state *rp)
static void createarc(struct nfa *nfa, int t, color co, struct state *from, struct state *to)
static int pull(struct nfa *nfa, struct arc *con, struct state **intermediates)
static void cleanup(struct nfa *nfa)
static void newarc(struct nfa *nfa, int t, color co, struct state *from, struct state *to)
static void sortouts(struct nfa *nfa, struct state *s)
static int sortouts_cmp(const void *a, const void *b)
static void dropstate(struct nfa *nfa, struct state *s)
static void compact(struct nfa *nfa, struct cnfa *cnfa)
static void uncolorchain(struct colormap *cm, struct arc *a)
static void duptraverse(struct nfa *nfa, struct state *s, struct state *stmp)
static void cparc(struct nfa *nfa, struct arc *oa, struct state *from, struct state *to)
static color maxcolor(struct colormap *cm)
static void carcsort(struct carc *first, size_t n)
#define CANCEL_REQUESTED(re)
static void destroystate(struct nfa *nfa, struct state *s)
#define qsort(a, b, c, d)
static void freestate(struct nfa *nfa, struct state *s)
static long analyze(struct nfa *nfa)
#define STACK_TOO_DEEP(re)
static int combine(struct arc *con, struct arc *a)
static FormData_pg_attribute a2
static void sortins(struct nfa *nfa, struct state *s)