Adaptation of re-oNsquared.patch from Tom Lane @ postgres.

3 files changed, 720 insertions, 99 deletions

diff --git a/generic/regc_nfa.c b/generic/regc_nfa.c
index 20eb3ba..0f572b8 100644
--- a/generic/regc_nfa.c
+++ b/generic/regc_nfa.c
@@ -35,6 +35,8 @@
 #define	NISERR()	VISERR(nfa->v)
 #define	NERR(e)		VERR(nfa->v, (e))
 #define STACK_TOO_DEEP(x) (0)
+#define CANCEL_REQUESTED(x) (0)
+#define REG_CANCEL 777
 
 /*
  - newnfa - set up an NFA
@@ -322,6 +324,10 @@ destroystate(
  ^ static VOID newarc(struct nfa *, int, pcolor, struct state *,
  ^	struct state *);
  */
+/*
+ * This function checks to make sure that no duplicate arcs are created.
+ * In general we never want duplicates.
+ */
 static void
 newarc(
     struct nfa *nfa,
@@ -334,16 +340,42 @@ newarc(
 
     assert(from != NULL && to != NULL);
 
-    /*
-     * Check for duplicates.
-     */
-
-    for (a=from->outs ; a!=NULL ; a=a->outchain) {
-	if (a->to == to && a->co == co && a->type == t) {
-	    return;
+    /* check for duplicate arc, using whichever chain is shorter */
+    if (from->nouts <= to->nins) {
+	for (a = from->outs; a != NULL; a = a->outchain) {
+	    if (a->to == to && a->co == co && a->type == t) {
+		return;
+	    }
+	}
+    } else {
+	for (a = to->ins; a != NULL; a = a->inchain) {
+	    if (a->from == from && a->co == co && a->type == t) {
+		return;
+	    }
 	}
     }
+  
+    /* no dup, so create the arc */
+    createarc(nfa, t, co, from, to);
+}
 
+/*
+ * createarc - create a new arc within an NFA
+ *
+ * This function must *only* be used after verifying that there is no existing
+ * identical arc (same type/color/from/to).
+ */
+static void
+createarc(
+    struct nfa * nfa,
+    int t,
+    pcolor co,
+    struct state * from,
+    struct state * to)
+{
+    struct arc *a;
+
+    /* the arc is physically allocated within its from-state */
     a = allocarc(nfa, from);
     if (NISERR()) {
 	return;
@@ -356,15 +388,21 @@ newarc(
     a->from = from;
 
     /*
-     * Put the new arc on the beginning, not the end, of the chains. Not only
-     * is this easier, it has the very useful side effect that deleting the
-     * most-recently-added arc is the cheapest case rather than the most
-     * expensive one.
+     * Put the new arc on the beginning, not the end, of the chains; it's
+     * simpler here, and freearc() is the same cost either way.  See also the
+     * logic in moveins() and its cohorts, as well as fixempties().
      */
-
     a->inchain = to->ins;
+    a->inchainRev = NULL;
+    if (to->ins) {
+	to->ins->inchainRev = a;
+    }
     to->ins = a;
     a->outchain = from->outs;
+    a->outchainRev = NULL;
+    if (from->outs) {
+	from->outs->outchainRev = a;
+    }
     from->outs = a;
 
     from->nouts++;
@@ -437,7 +475,7 @@ freearc(
 {
     struct state *from = victim->from;
     struct state *to = victim->to;
-    struct arc *a;
+    struct arc *predecessor;
 
     assert(victim->type != 0);
 
@@ -454,16 +492,17 @@ freearc(
      */
 
     assert(from != NULL);
-    assert(from->outs != NULL);
-    a = from->outs;
-    if (a == victim) {		/* simple case: first in chain */
+    predecessor = victim->outchainRev;
+    if (predecessor == NULL) {
+	assert(from->outs == victim);
 	from->outs = victim->outchain;
     } else {
-	for (; a!=NULL && a->outchain!=victim ; a=a->outchain) {
-	    continue;
-	}
-	assert(a != NULL);
-	a->outchain = victim->outchain;
+	assert(predecessor->outchain == victim);
+	predecessor->outchain = victim->outchain;
+    }
+    if (victim->outchain != NULL) {
+	assert(victim->outchain->outchainRev == victim);
+	victim->outchain->outchainRev = predecessor;
     }
     from->nouts--;
 
@@ -472,31 +511,78 @@ freearc(
      */
 
     assert(to != NULL);
-    assert(to->ins != NULL);
-    a = to->ins;
-    if (a == victim) {		/* simple case: first in chain */
+    predecessor = victim->inchainRev;
+    if (predecessor == NULL) {
+	assert(to->ins == victim);
 	to->ins = victim->inchain;
     } else {
-	for (; a->inchain!=victim ; a=a->inchain) {
-	    assert(a->inchain != NULL);
-	    continue;
-	}
-	a->inchain = victim->inchain;
+	assert(predecessor->inchain == victim);
+	predecessor->inchain = victim->inchain;
+    }
+    if (victim->inchain != NULL) {
+	assert(victim->inchain->inchainRev == victim);
+	victim->inchain->inchainRev = predecessor;
     }
     to->nins--;
 
     /*
-     * Clean up and place on free list.
+     * Clean up and place on from-state's free list.
      */
 
     victim->type = 0;
     victim->from = NULL;	/* precautions... */
     victim->to = NULL;
     victim->inchain = NULL;
+    victim->inchainRev = NULL;
     victim->outchain = NULL;
+    victim->outchainRev = NULL;
     victim->freechain = from->free;
     from->free = victim;
 }
+
+/*
+ * changearctarget - flip an arc to have a different to state
+ *
+ * Caller must have verified that there is no pre-existing duplicate arc.
+ *
+ * Note that because we store arcs in their from state, we can't easily have
+ * a similar changearcsource function.
+ */
+static void
+changearctarget(struct arc * a, struct state * newto)
+{
+    struct state *oldto = a->to;
+    struct arc *predecessor;
+
+    assert(oldto != newto);
+
+    /* take it off old target's in-chain */
+    assert(oldto != NULL);
+    predecessor = a->inchainRev;
+    if (predecessor == NULL) {
+	assert(oldto->ins == a);
+	oldto->ins = a->inchain;
+    } else {
+	assert(predecessor->inchain == a);
+	predecessor->inchain = a->inchain;
+    }
+    if (a->inchain != NULL) {
+	assert(a->inchain->inchainRev == a);
+	a->inchain->inchainRev = predecessor;
+    }
+    oldto->nins--;
+
+    a->to = newto;
+
+    /* prepend it to new target's in-chain */
+    a->inchain = newto->ins;
+    a->inchainRev = NULL;
+    if (newto->ins) {
+	newto->ins->inchainRev = a;
+    }
+    newto->ins = a;
+    newto->nins++;
+}
 
 /*
  - hasnonemptyout - Does state have a non-EMPTY out arc?
@@ -589,13 +675,181 @@ cparc(
 {
     newarc(nfa, oa->type, oa->co, from, to);
 }
+
+/*
+ * sortins - sort the in arcs of a state by from/color/type
+ */
+static void
+sortins(
+    struct nfa * nfa,
+    struct state * s)
+{
+    struct arc **sortarray;
+    struct arc *a;
+    int n = s->nins;
+    int i;
+
+    if (n <= 1) {
+	return;		/* nothing to do */
+    }
+    /* make an array of arc pointers ... */
+    sortarray = (struct arc **) MALLOC(n * sizeof(struct arc *));
+    if (sortarray == NULL) {
+	NERR(REG_ESPACE);
+	return;
+    }
+    i = 0;
+    for (a = s->ins; a != NULL; a = a->inchain) {
+	sortarray[i++] = a;
+    }
+    assert(i == n);
+    /* ... sort the array */
+    qsort(sortarray, n, sizeof(struct arc *), sortins_cmp);
+    /* ... and rebuild arc list in order */
+    /* it seems worth special-casing first and last items to simplify loop */
+    a = sortarray[0];
+    s->ins = a;
+    a->inchain = sortarray[1];
+    a->inchainRev = NULL;
+    for (i = 1; i < n - 1; i++) {
+	a = sortarray[i];
+	a->inchain = sortarray[i + 1];
+	a->inchainRev = sortarray[i - 1];
+    }
+    a = sortarray[i];
+    a->inchain = NULL;
+    a->inchainRev = sortarray[i - 1];
+    FREE(sortarray);
+}
+
+static int
+sortins_cmp(
+    const void *a,
+    const void *b)
+{
+    const struct arc *aa = *((const struct arc * const *) a);
+    const struct arc *bb = *((const struct arc * const *) b);
+
+    /* we check the fields in the order they are most likely to be different */
+    if (aa->from->no < bb->from->no) {
+	return -1;
+    }
+    if (aa->from->no > bb->from->no) {
+ 	return 1;
+    }
+    if (aa->co < bb->co) {
+ 	return -1;
+    }
+    if (aa->co > bb->co) {
+ 	return 1;
+    }
+    if (aa->type < bb->type) {
+ 	return -1;
+    }
+    if (aa->type > bb->type) {
+ 	return 1;
+    }
+    return 0;
+}
+ 
+/*
+ * sortouts - sort the out arcs of a state by to/color/type
+ */
+static void
+sortouts(
+    struct nfa * nfa,
+    struct state * s)
+{
+    struct arc **sortarray;
+    struct arc *a;
+    int	n = s->nouts;
+    int	i;
+
+    if (n <= 1) {
+	return;					/* nothing to do */
+    }
+    /* make an array of arc pointers ... */
+    sortarray = (struct arc **) MALLOC(n * sizeof(struct arc *));
+    if (sortarray == NULL) {
+	NERR(REG_ESPACE);
+	return;
+    }
+    i = 0;
+    for (a = s->outs; a != NULL; a = a->outchain) {
+	sortarray[i++] = a;
+    }
+    assert(i == n);
+    /* ... sort the array */
+    qsort(sortarray, n, sizeof(struct arc *), sortouts_cmp);
+    /* ... and rebuild arc list in order */
+    /* it seems worth special-casing first and last items to simplify loop */
+    a = sortarray[0];
+    s->outs = a;
+    a->outchain = sortarray[1];
+    a->outchainRev = NULL;
+    for (i = 1; i < n - 1; i++) {
+	a = sortarray[i];
+	a->outchain = sortarray[i + 1];
+	a->outchainRev = sortarray[i - 1];
+    }
+    a = sortarray[i];
+    a->outchain = NULL;
+    a->outchainRev = sortarray[i - 1];
+    FREE(sortarray);
+}
+
+static int
+sortouts_cmp(
+    const void *a,
+    const void *b)
+{
+    const struct arc *aa = *((const struct arc * const *) a);
+    const struct arc *bb = *((const struct arc * const *) b);
+
+    /* we check the fields in the order they are most likely to be different */
+    if (aa->to->no < bb->to->no) {
+	return -1;
+    }
+    if (aa->to->no > bb->to->no) {
+	return 1;
+    }
+    if (aa->co < bb->co) {
+	return -1;
+    }
+    if (aa->co > bb->co) {
+	return 1;
+    }
+    if (aa->type < bb->type) {
+	return -1;
+    }
+    if (aa->type > bb->type) {
+	return 1;
+    }
+    return 0;
+}
+
+/*
+ * Common decision logic about whether to use arc-by-arc operations or
+ * sort/merge.  If there's just a few source arcs we cannot recoup the
+ * cost of sorting the destination arc list, no matter how large it is.
+ * Otherwise, limit the number of arc-by-arc comparisons to about 1000
+ * (a somewhat arbitrary choice, but the breakeven point would probably
+ * be machine dependent anyway).
+ */
+#define BULK_ARC_OP_USE_SORT(nsrcarcs, ndestarcs) \
+	((nsrcarcs) < 4 ? 0 : ((nsrcarcs) > 32 || (ndestarcs) > 32))
 
 /*
  - moveins - move all in arcs of a state to another state
  * You might think this could be done better by just updating the
- * existing arcs, and you would be right if it weren't for the desire
+ * existing arcs, and you would be right if it weren't for the need
  * for duplicate suppression, which makes it easier to just make new
  * ones to exploit the suppression built into newarc.
+ *
+ * However, if we have a whole lot of arcs to deal with, retail duplicate
+ * checks become too slow.  In that case we proceed by sorting and merging
+ * the arc lists, and then we can indeed just update the arcs in-place.
+ *
  ^ static VOID moveins(struct nfa *, struct state *, struct state *);
  */
 static void
@@ -604,14 +858,79 @@ moveins(
     struct state *oldState,
     struct state *newState)
 {
-    struct arc *a;
-
     assert(oldState != newState);
 
-    while ((a = oldState->ins) != NULL) {
-	cparc(nfa, a, a->from, newState);
-	freearc(nfa, a);
+    if (!BULK_ARC_OP_USE_SORT(oldState->nins, newState->nins)) {
+	/* With not too many arcs, just do them one at a time */
+	struct arc *a;
+
+	while ((a = oldState->ins) != NULL) {
+	    cparc(nfa, a, a->from, newState);
+	    freearc(nfa, a);
+	}
+    } else {
+	/*
+	 * With many arcs, use a sort-merge approach.  Note changearctarget()
+	 * will put the arc onto the front of newState's chain, so it does not
+	 * break our walk through the sorted part of the chain.
+	 */
+	struct arc *oa;
+	struct arc *na;
+
+	/*
+	 * Because we bypass newarc() in this code path, we'd better include a
+	 * cancel check.
+	 */
+	if (CANCEL_REQUESTED(nfa->v->re)) {
+	    NERR(REG_CANCEL);
+	    return;
+	}
+
+	sortins(nfa, oldState);
+	sortins(nfa, newState);
+	if (NISERR()) {
+	    return;		/* might have failed to sort */
+	}
+	oa = oldState->ins;
+	na = newState->ins;
+	while (oa != NULL && na != NULL) {
+	    struct arc *a = oa;
+
+	    switch (sortins_cmp(&oa, &na)) {
+		case -1:
+		    /* newState does not have anything matching oa */
+		    oa = oa->inchain;
+
+		    /*
+		     * Rather than doing createarc+freearc, we can just unlink
+		     * and relink the existing arc struct.
+		     */
+		    changearctarget(a, newState);
+		    break;
+		case 0:
+		    /* match, advance in both lists */
+		    oa = oa->inchain;
+		    na = na->inchain;
+		    /* ... and drop duplicate arc from oldState */
+		    freearc(nfa, a);
+		    break;
+		case +1:
+		    /* advance only na; oa might have a match later */
+		    na = na->inchain;
+		    break;
+		default:
+		    assert(NOTREACHED);
+	    }
+	}
+	while (oa != NULL) {
+	    /* newState does not have anything matching oa */
+	    struct arc *a = oa;
+
+	    oa = oa->inchain;
+	    changearctarget(a, newState);
+	}
     }
+
     assert(oldState->nins == 0);
     assert(oldState->ins == NULL);
 }
@@ -628,14 +947,178 @@ copyins(
     struct state *newState,
     int all)
 {
-    struct arc *a;
-
     assert(oldState != newState);
 
-    for (a=oldState->ins ; a!=NULL ; a=a->inchain) {
-	if (all || a->type != EMPTY) {
-	    cparc(nfa, a, a->from, newState);
+    if (!BULK_ARC_OP_USE_SORT(oldState->nins, newState->nins)) {
+	/* With not too many arcs, just do them one at a time */
+	struct arc *a;
+
+	for (a = oldState->ins; a != NULL; a = a->inchain) {
+	    if (all || a->type != EMPTY) {
+		cparc(nfa, a, a->from, newState);
+	    }
+	}
+    } else {
+	/*
+	 * With many arcs, use a sort-merge approach.  Note that createarc()
+	 * will put new arcs onto the front of newState's chain, so it does
+	 * not break our walk through the sorted part of the chain.
+	 */
+	struct arc *oa;
+	struct arc *na;
+
+	/*
+	 * Because we bypass newarc() in this code path, we'd better include a
+	 * cancel check.
+	 */
+	if (CANCEL_REQUESTED(nfa->v->re)) {
+	    NERR(REG_CANCEL);
+	    return;
 	}
+
+	sortins(nfa, oldState);
+	sortins(nfa, newState);
+	if (NISERR()) {
+	    return;		/* might have failed to sort */
+	}
+	oa = oldState->ins;
+	na = newState->ins;
+	while (oa != NULL && na != NULL) {
+	    struct arc *a = oa;
+
+	    if (!all && a->type == EMPTY) {
+		oa = oa->inchain;
+		continue;
+	    }
+
+	    switch (sortins_cmp(&oa, &na)) {
+		case -1:
+		    /* newState does not have anything matching oa */
+		    oa = oa->inchain;
+		    createarc(nfa, a->type, a->co, a->from, newState);
+		    break;
+		case 0:
+		    /* match, advance in both lists */
+		    oa = oa->inchain;
+		    na = na->inchain;
+		    break;
+		case +1:
+		    /* advance only na; oa might have a match later */
+		    na = na->inchain;
+		    break;
+		default:
+		    assert(NOTREACHED);
+	    }
+	}
+	while (oa != NULL) {
+	    /* newState does not have anything matching oa */
+	    struct arc *a = oa;
+
+	    if (!all && a->type == EMPTY) {
+		oa = oa->inchain;
+		continue;
+	    }
+
+	    oa = oa->inchain;
+	    createarc(nfa, a->type, a->co, a->from, newState);
+	}
+    }
+}
+
+/*
+ * mergeins - merge a list of inarcs into a state
+ *
+ * This is much like copyins, but the source arcs are listed in an array,
+ * and are not guaranteed unique.  It's okay to clobber the array contents.
+ */
+static void
+mergeins(
+    struct nfa * nfa,
+    struct state * s,
+    struct arc ** arcarray,
+    int arccount)
+{
+    struct arc *na;
+    int	i;
+    int	j;
+
+    if (arccount <= 0) {
+	return;
+    }
+
+    /*
+     * Because we bypass newarc() in this code path, we'd better include a
+     * cancel check.
+     */
+    if (CANCEL_REQUESTED(nfa->v->re)) {
+	NERR(REG_CANCEL);
+	return;
+    }
+
+    /* Sort existing inarcs as well as proposed new ones */
+    sortins(nfa, s);
+    if (NISERR()) {
+	return;			/* might have failed to sort */
+    }
+
+    qsort(arcarray, arccount, sizeof(struct arc *), sortins_cmp);
+
+    /*
+     * arcarray very likely includes dups, so we must eliminate them.  (This
+     * could be folded into the next loop, but it's not worth the trouble.)
+     */
+    j = 0;
+    for (i = 1; i < arccount; i++) {
+	switch (sortins_cmp(&arcarray[j], &arcarray[i])) {
+	    case -1:
+		/* non-dup */
+		arcarray[++j] = arcarray[i];
+		break;
+	    case 0:
+		/* dup */
+		break;
+	    default:
+		/* trouble */
+		assert(NOTREACHED);
+	}
+    }
+    arccount = j + 1;
+
+    /*
+     * Now merge into s' inchain.  Note that createarc() will put new arcs
+     * onto the front of s's chain, so it does not break our walk through the
+     * sorted part of the chain.
+     */
+    i = 0;
+    na = s->ins;
+    while (i < arccount && na != NULL) {
+	struct arc *a = arcarray[i];
+
+	switch (sortins_cmp(&a, &na)) {
+	    case -1:
+		/* s does not have anything matching a */
+		createarc(nfa, a->type, a->co, a->from, s);
+		i++;
+		break;
+	    case 0:
+		/* match, advance in both lists */
+		i++;
+		na = na->inchain;
+		break;
+	    case +1:
+		/* advance only na; array might have a match later */
+		na = na->inchain;
+		break;
+	    default:
+		assert(NOTREACHED);
+	}
+    }
+    while (i < arccount) {
+	/* s does not have anything matching a */
+	struct arc *a = arcarray[i];
+
+	createarc(nfa, a->type, a->co, a->from, s);
+	i++;
     }
 }
 
@@ -649,14 +1132,78 @@ moveouts(
     struct state *oldState,
     struct state *newState)
 {
-    struct arc *a;
-
     assert(oldState != newState);
 
-    while ((a = oldState->outs) != NULL) {
-	cparc(nfa, a, newState, a->to);
-	freearc(nfa, a);
+    if (!BULK_ARC_OP_USE_SORT(oldState->nouts, newState->nouts)) {
+	/* With not too many arcs, just do them one at a time */
+	struct arc *a;
+
+	while ((a = oldState->outs) != NULL) {
+	    cparc(nfa, a, newState, a->to);
+	    freearc(nfa, a);
+	}
+    } else {
+	/*
+	 * With many arcs, use a sort-merge approach.  Note that createarc()
+	 * will put new arcs onto the front of newState's chain, so it does
+	 * not break our walk through the sorted part of the chain.
+	 */
+	struct arc *oa;
+	struct arc *na;
+
+	/*
+	 * Because we bypass newarc() in this code path, we'd better include a
+	 * cancel check.
+	 */
+	if (CANCEL_REQUESTED(nfa->v->re)) {
+	    NERR(REG_CANCEL);
+	    return;
+	}
+
+	sortouts(nfa, oldState);
+	sortouts(nfa, newState);
+	if (NISERR()) {
+	    return;	/* might have failed to sort */
+	}
+	oa = oldState->outs;
+	na = newState->outs;
+	while (oa != NULL && na != NULL) {
+	    struct arc *a = oa;
+
+	    switch (sortouts_cmp(&oa, &na)) {
+		case -1:
+		    /* newState does not have anything matching oa */
+		    oa = oa->outchain;
+		    createarc(nfa, a->type, a->co, newState, a->to);
+		    freearc(nfa, a);
+		    break;
+		case 0:
+		    /* match, advance in both lists */
+		    oa = oa->outchain;
+		    na = na->outchain;
+		    /* ... and drop duplicate arc from oldState */
+		    freearc(nfa, a);
+		    break;
+		case +1:
+		    /* advance only na; oa might have a match later */
+		    na = na->outchain;
+		    break;
+		default:
+		    assert(NOTREACHED);
+	    }
+	}
+	while (oa != NULL) {
+	    /* newState does not have anything matching oa */
+	    struct arc *a = oa;
+
+	    oa = oa->outchain;
+	    createarc(nfa, a->type, a->co, newState, a->to);
+	    freearc(nfa, a);
+	}
     }
+
+    assert(oldState->nouts == 0);
+    assert(oldState->outs == NULL);
 }
 
 /*
@@ -671,13 +1218,80 @@ copyouts(
     struct state *newState,
     int all)
 {
-    struct arc *a;
-
     assert(oldState != newState);
 
-    for (a=oldState->outs ; a!=NULL ; a=a->outchain) {
-	if (all || a->type != EMPTY) {
-	    cparc(nfa, a, newState, a->to);
+    if (!BULK_ARC_OP_USE_SORT(oldState->nouts, newState->nouts)) {
+	/* With not too many arcs, just do them one at a time */
+	struct arc *a;
+
+	for (a = oldState->outs; a != NULL; a = a->outchain) {
+	    if (all || a->type != EMPTY) {
+		cparc(nfa, a, newState, a->to);
+	    }
+	}
+    } else {
+ 	/*
+	 * With many arcs, use a sort-merge approach.  Note that createarc()
+	 * will put new arcs onto the front of newState's chain, so it does
+	 * not break our walk through the sorted part of the chain.
+	 */
+	struct arc *oa;
+	struct arc *na;
+
+	/*
+	 * Because we bypass newarc() in this code path, we'd better include a
+	 * cancel check.
+	 */
+	if (CANCEL_REQUESTED(nfa->v->re)) {
+	    NERR(REG_CANCEL);
+	    return;
+	}
+
+	sortouts(nfa, oldState);
+	sortouts(nfa, newState);
+	if (NISERR()) {
+	    return;		/* might have failed to sort */
+	}
+	oa = oldState->outs;
+	na = newState->outs;
+	while (oa != NULL && na != NULL) {
+	    struct arc *a = oa;
+
+	    if (!all && a->type == EMPTY) {
+		oa = oa->outchain;
+		continue;
+	    }
+
+	    switch (sortouts_cmp(&oa, &na)) {
+		case -1:
+		    /* newState does not have anything matching oa */
+		    oa = oa->outchain;
+		    createarc(nfa, a->type, a->co, newState, a->to);
+		    break;
+		case 0:
+		    /* match, advance in both lists */
+		    oa = oa->outchain;
+		    na = na->outchain;
+		    break;
+		case +1:
+		    /* advance only na; oa might have a match later */
+		    na = na->outchain;
+		    break;
+		default:
+		    assert(NOTREACHED);
+	    }
+	}
+	while (oa != NULL) {
+	    /* newState does not have anything matching oa */
+	    struct arc *a = oa;
+
+	    if (!all && a->type == EMPTY){
+		oa = oa->outchain;
+		continue;
+	    }
+
+	    oa = oa->outchain;
+	    createarc(nfa, a->type, a->co, newState, a->to);
 	}
     }
 }
@@ -2238,7 +2852,7 @@ compact(
 		break;
 	    }
 	}
-	carcsort(first, ca-1);
+	carcsort(first, ca - first);
 	ca->co = COLORLESS;
 	ca->to = 0;
 	ca++;
@@ -2258,33 +2872,39 @@ compact(
 
 /*
  - carcsort - sort compacted-NFA arcs by color
- * Really dumb algorithm, but if the list is long enough for that to matter,
- * you're in real trouble anyway.
  ^ static VOID carcsort(struct carc *, struct carc *);
  */
 static void
 carcsort(
     struct carc *first,
-    struct carc *last)
+    size_t n)
 {
-    struct carc *p;
-    struct carc *q;
-    struct carc tmp;
-
-    if (last - first <= 1) {
-	return;
+    if (n > 1) {
+	qsort(first, n, sizeof(struct carc), carc_cmp);
     }
+}
 
-    for (p = first; p <= last; p++) {
-	for (q = p; q <= last; q++) {
-	    if (p->co > q->co || (p->co == q->co && p->to > q->to)) {
-		assert(p != q);
-		tmp = *p;
-		*p = *q;
-		*q = tmp;
-	    }
-	}
+static int
+carc_cmp(
+    const void *a,
+    const void *b)
+{
+    const struct carc *aa = (const struct carc *) a;
+    const struct carc *bb = (const struct carc *) b;
+  
+    if (aa->co < bb->co) {
+	return -1;
+    }
+    if (aa->co > bb->co) {
+	return +1;
+    }
+    if (aa->to < bb->to) {
+	return -1;
     }
+    if (aa->to > bb->to) {
+	return +1;
+    }
+    return 0;
 }
 
 /*
@@ -2382,37 +3002,28 @@ dumparcs(
     FILE *f)
 {
     int pos;
+    struct arc *a;
 
-    assert(s->nouts > 0);
-    /* printing arcs in reverse order is usually clearer */
-    pos = dumprarcs(s->outs, s, f, 1);
-    if (pos != 1) {
-	fprintf(f, "\n");
-    }
-}
-
-/*
- - dumprarcs - dump remaining outarcs, recursively, in reverse order
- ^ static int dumprarcs(struct arc *, struct state *, FILE *, int);
- */
-static int			/* resulting print position */
-dumprarcs(
-    struct arc *a,
-    struct state *s,
-    FILE *f,
-    int pos)			/* initial print position */
-{
-    if (a->outchain != NULL) {
-	pos = dumprarcs(a->outchain, s, f, pos);
+    /* printing oldest arcs first is usually clearer */
+    a = s->outs;
+    assert(a != NULL);
+    while (a->outchain != NULL) {
+	a = a->outchain;
     }
-    dumparc(a, s, f);
-    if (pos == 5) {
+    pos = 1;
+    do {
+	dumparc(a, s, f);
+	if (pos == 5) {
+	    fprintf(f, "\n");
+	    pos = 1;
+	} else {
+	    pos++;
+	}
+	a = a->outchainRev;
+    } while (a != NULL);
+    if (pos != 1) {
 	fprintf(f, "\n");
-	pos = 1;
-    } else {
-	pos++;
     }
-    return pos;
 }
 
 /*
diff --git a/generic/regcomp.c b/generic/regcomp.c
index 27bb736..b01311b 100644
--- a/generic/regcomp.c
+++ b/generic/regcomp.c
@@ -119,15 +119,22 @@ static void dropstate(struct nfa *, struct state *);
 static void freestate(struct nfa *, struct state *);
 static void destroystate(struct nfa *, struct state *);
 static void newarc(struct nfa *, int, pcolor, struct state *, struct state *);
+static void createarc(struct nfa *, int, pcolor, struct state *, struct state *);
 static struct arc *allocarc(struct nfa *, struct state *);
 static void freearc(struct nfa *, struct arc *);
+static void changearctarget(struct arc *, struct state *);
 static int hasnonemptyout(struct state *);
 static int nonemptyouts(struct state *);
 static int nonemptyins(struct state *);
 static struct arc *findarc(struct state *, int, pcolor);
 static void cparc(struct nfa *, struct arc *, struct state *, struct state *);
+static void sortins(struct nfa *, struct state *);
+static int sortins_cmp(const void *, const void *);
+static void sortouts(struct nfa *, struct state *);
+static int sortouts_cmp(const void *, const void *);
 static void moveins(struct nfa *, struct state *, struct state *);
 static void copyins(struct nfa *, struct state *, struct state *, int);
+static void mergeins(struct nfa *, struct state *, struct arc **, int);
 static void moveouts(struct nfa *, struct state *, struct state *);
 static void copyouts(struct nfa *, struct state *, struct state *, int);
 static void cloneouts(struct nfa *, struct state *, struct state *, struct state *, int);
@@ -161,7 +168,8 @@ static void markreachable(struct nfa *, struct state *, struct state *, struct s
 static void markcanreach(struct nfa *, struct state *, struct state *, struct state *);
 static long analyze(struct nfa *);
 static void compact(struct nfa *, struct cnfa *);
-static void carcsort(struct carc *, struct carc *);
+static void carcsort(struct carc *, size_t);
+static int carc_cmp(const void *, const void *);
 static void freecnfa(struct cnfa *);
 static void dumpnfa(struct nfa *, FILE *);
 #ifdef REG_DEBUG
diff --git a/generic/regguts.h b/generic/regguts.h
index ac625d5..7ed8ec1 100644
--- a/generic/regguts.h
+++ b/generic/regguts.h
@@ -265,8 +265,10 @@ struct arc {
     struct state *from;		/* where it's from (and contained within) */
     struct state *to;		/* where it's to */
     struct arc *outchain;	/* *from's outs chain or free chain */
-#define	freechain	outchain
+    struct arc *outchainRev;	/* back-link in *from's outs chain */
+#define	freechain outchain	/* we do not maintain "freechainRev" */
     struct arc *inchain;	/* *to's ins chain */
+    struct arc *inchainRev;	/* back-link in *to's ins chain */
     struct arc *colorchain;	/* color's arc chain */
     struct arc *colorchainRev;	/* back-link in color's arc chain */
 };