Previously, I fixed it in dfamust(). Now fix them in epsclosure() and dfastate().
I tested it with below, running vmstat. $ echo a | env LC_ALL=C src/grep -f /usr/share/dict/linux.words Norihiro
From 01b8adb4470d9e7fe0dd8c3b8bf8622fd0875841 Mon Sep 17 00:00:00 2001 From: Norihiro Tanaka <[email protected]> Date: Wed, 30 Apr 2014 16:53:44 +0900 Subject: [PATCH] dfa: optimization of memory allocation * src/dfa.c (epsclosure): get the value of `visited' from the argument. (dfaanalyze): Define and allocate variable `visited'. (dfastate): Use not `insert' but `merge' to insert of positions for state 0 of DFA. --- src/dfa.c | 28 ++++++++++++++++------------ 1 file changed, 16 insertions(+), 12 deletions(-) diff --git a/src/dfa.c b/src/dfa.c index 362de2c..d532b81 100644 --- a/src/dfa.c +++ b/src/dfa.c @@ -2129,13 +2129,11 @@ state_index (struct dfa *d, position_set const *s, int context) constraint. Repeat exhaustively until no funny positions are left. S->elems must be large enough to hold the result. */ static void -epsclosure (position_set * s, struct dfa const *d) +epsclosure (position_set * s, struct dfa const *d, char *visited) { size_t i, j; position p, old; - - /* Array of booleans, large enough to use char, not int. */ - char *visited = xzalloc (d->tindex); + bool initialized = false; for (i = 0; i < s->nelem; ++i) if (d->tokens[s->elems[i].index] >= NOTCHAR @@ -2144,6 +2142,11 @@ epsclosure (position_set * s, struct dfa const *d) && d->tokens[s->elems[i].index] != MBCSET && d->tokens[s->elems[i].index] < CSET) { + if (!initialized) + { + memset (visited, 0, d->tindex * sizeof (*visited)); + initialized = true; + } old = s->elems[i]; p.constraint = old.constraint; delete (s->elems[i], s); @@ -2184,8 +2187,6 @@ epsclosure (position_set * s, struct dfa const *d) /* Force rescan to start at the beginning. */ i = -1; } - - free (visited); } /* Returns the set of contexts for which there is at least one @@ -2312,6 +2313,7 @@ dfaanalyze (struct dfa *d, int searchflag) int separate_contexts; /* Context wanted by some position. */ size_t i, j; position *pos; + char *visited = xnmalloc (d->tindex, sizeof *visited); #ifdef DEBUG fprintf (stderr, "dfaanalyze:\n"); @@ -2470,7 +2472,7 @@ dfaanalyze (struct dfa *d, int searchflag) putc ('\n', stderr); #endif copy (&d->follows[i], &merged); - epsclosure (&merged, d); + epsclosure (&merged, d, visited); copy (&merged, &d->follows[i]); } @@ -2479,7 +2481,7 @@ dfaanalyze (struct dfa *d, int searchflag) merged.nelem = 0; for (i = 0; i < stk[-1].nfirstpos; ++i) insert (firstpos[i], &merged); - epsclosure (&merged, d); + epsclosure (&merged, d, visited); /* Build the initial state. */ separate_contexts = state_separate_contexts (&merged); @@ -2490,6 +2492,7 @@ dfaanalyze (struct dfa *d, int searchflag) free (posalloc); free (stkalloc); free (merged.elems); + free (visited); } @@ -2733,10 +2736,11 @@ dfastate (state_num s, struct dfa *d, state_num trans[]) /* If we are building a searching matcher, throw in the positions of state 0 as well. */ - if (d->searchflag - && (!d->multibyte || !next_isnt_1st_byte)) - for (j = 0; j < d->states[0].elems.nelem; ++j) - insert (d->states[0].elems.elems[j], &follows); + if (d->searchflag && (!d->multibyte || !next_isnt_1st_byte)) + { + merge (&d->states[0].elems, &follows, &tmp); + copy (&tmp, &follows); + } /* Find out if the new state will want any context information. */ possible_contexts = charclass_context (labels[i]); -- 1.9.2
