[REGEX] factor _calc_state() out of _calc_states()

1 files changed, 62 insertions, 66 deletions

diff --git a/libdm/regex/matcher.c b/libdm/regex/matcher.c
index 07ba9e4a3..58837399b 100644
--- a/libdm/regex/matcher.c
+++ b/libdm/regex/matcher.c
@@ -38,6 +38,13 @@ struct dm_regex {		/* Instance variables for the lexer */
         int charsets_entered;
         struct rx_node **charsets;
 	struct dm_pool *scratch, *mem;
+
+        /* stuff for on the fly dfa calculation */
+        dm_bitset_t charmap[256];
+        dm_bitset_t dfa_copy;
+        struct ttree *tt;
+        dm_bitset_t bs;
+        struct state_queue *h, *t;
 };
 
 static int _count_nodes(struct rx_node *rx)
@@ -217,26 +224,60 @@ static struct state_queue *_create_state_queue(struct dm_pool *mem,
 	return r;
 }
 
+static void _calc_state(struct dm_regex *m, struct state_queue *h, int a)
+{
+        int set_bits = 0, i;
+        struct dfa_state *dfa = h->s;
+        dm_bitset_t dfa_bits = h->bits;
+        dm_bit_and(m->dfa_copy, m->charmap[a], dfa_bits);
+
+        /* iterate through all the states in firstpos */
+        for (i = dm_bit_get_first(m->dfa_copy); i >= 0; i = dm_bit_get_next(m->dfa_copy, i)) {
+                if (a == TARGET_TRANS)
+                        dfa->final = m->charsets[i]->final;
+
+                dm_bit_union(m->bs, m->bs, m->charsets[i]->followpos);
+                set_bits = 1;
+        }
+
+        if (set_bits) {         /* FIXME: this is always true */
+                struct state_queue *tmp;
+                struct dfa_state *ldfa = ttree_lookup(m->tt, m->bs + 1);
+                if (!ldfa) {
+                        /* push */
+                        ldfa = _create_dfa_state(m->mem);
+                        ttree_insert(m->tt, m->bs + 1, ldfa);
+                        tmp = _create_state_queue(m->scratch, ldfa, m->bs);
+                        if (!m->h)
+                                m->h = m->t = tmp;
+                        else {
+                                m->t->next = tmp;
+                                m->t = tmp;
+                        }
+                }
+
+                dfa->lookup[a] = ldfa;
+                dm_bit_clear_all(m->bs);
+        }
+}
+
 static int _calc_states(struct dm_regex *m, struct rx_node *rx)
 {
 	unsigned iwidth = (m->num_charsets / DM_BITS_PER_INT) + 1;
-	struct ttree *tt = ttree_create(m->scratch, iwidth);
-	struct state_queue *h, *t, *tmp;
-	struct dfa_state *dfa, *ldfa;
-	int i, a, set_bits = 0, count = 0;
-	dm_bitset_t bs, dfa_bits;
+	struct dfa_state *dfa;
+	int i, a;
 
-	if (!tt)
+	m->tt = ttree_create(m->scratch, iwidth);
+	if (!m->tt)
 		return_0;
 
-	if (!(bs = dm_bitset_create(m->scratch, m->num_charsets)))
+	if (!(m->bs = dm_bitset_create(m->scratch, m->num_charsets)))
 		return_0;
 
         /* build some char maps */
-        dm_bitset_t charmap[256];
         for (a = 0; a < 256; a++) {
-                charmap[a] = dm_bitset_create(m->scratch, m->num_charsets);
-                if (!charmap[a])
+                m->charmap[a] = dm_bitset_create(m->scratch, m->num_charsets);
+                if (!m->charmap[a])
                         return_0;
         }
 
@@ -245,76 +286,31 @@ static int _calc_states(struct dm_regex *m, struct rx_node *rx)
                 if (n->type == CHARSET) {
                         for (a = dm_bit_get_first(n->charset);
                              a >= 0; a = dm_bit_get_next(n->charset, a))
-                                dm_bit_set(charmap[a], n->charset_index);
+                                dm_bit_set(m->charmap[a], n->charset_index);
                 }
         }
 
 	/* create first state */
 	dfa = _create_dfa_state(m->mem);
 	m->start = dfa;
-	ttree_insert(tt, rx->firstpos + 1, dfa);
+	ttree_insert(m->tt, rx->firstpos + 1, dfa);
 
 	/* prime the queue */
-	h = t = _create_state_queue(m->scratch, dfa, rx->firstpos);
-        dm_bitset_t dfa_copy = dm_bitset_create(m->scratch, m->num_charsets);
-	while (h) {
-		int elems, idx[h->bits[0]];
+	m->h = m->t = _create_state_queue(m->scratch, dfa, rx->firstpos);
+        m->dfa_copy = dm_bitset_create(m->scratch, m->num_charsets);
 
+        /* keep processing until there's nothing in the queue */
+        struct state_queue *s;
+	while ((s = m->h)) {
 		/* pop state off front of the queue */
-		dfa = h->s;
-		dfa_bits = h->bits;
-		h = h->next;
+		m->h = m->h->next;
 
 		/* iterate through all the inputs for this state */
-		dm_bit_clear_all(bs);
-
-		/* Cache list of locations of bits */
-		elems = 0;
-		for (i = dm_bit_get_first(dfa_bits);
-		     i >= 0; i = dm_bit_get_next(dfa_bits, i))
-			idx[elems++] = i;
-
-		for (a = 0; a < 256; a++) {
-                        dm_bit_and(dfa_copy, charmap[a], dfa_bits);
-
-			/* iterate through all the states in firstpos */
-                        for (i = dm_bit_get_first(dfa_copy);
-                             i >= 0; i = dm_bit_get_next(dfa_copy, i)) {
-                                if (a == TARGET_TRANS)
-                                        dfa->final = m->charsets[i]->final;
-
-                                dm_bit_union(bs, bs,
-                                             m->charsets[i]->followpos);
-                                set_bits = 1;
-                        }
-
-			if (set_bits) {
-				ldfa = ttree_lookup(tt, bs + 1);
-				if (!ldfa) {
-					/* push */
-					ldfa = _create_dfa_state(m->mem);
-					ttree_insert(tt, bs + 1, ldfa);
-					tmp =
-					    _create_state_queue(m->scratch,
-								ldfa, bs);
-					if (!h)
-						h = t = tmp;
-					else {
-						t->next = tmp;
-						t = tmp;
-					}
-
-					count++;
-				}
-
-				dfa->lookup[a] = ldfa;
-				set_bits = 0;
-				dm_bit_clear_all(bs);
-			}
-		}
+		dm_bit_clear_all(m->bs);
+		for (a = 0; a < 256; a++)
+                        _calc_state(m, s, a);
 	}
 
-	log_debug("Matcher built with %d dfa states", count);
 	return 1;
 }