From a43f8e6e833288b88023b1edcc19bd6c9ba730ec Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Fri, 9 Dec 2016 15:09:03 -0800 Subject: [PATCH] dfa: fix performance bug that recomputes trans * lib/dfa.c (build_state): Fix performance bug introduced in Nov 25 on-demand changes. The bug caused build_state to reset all d->trans elements to -2 even when d->trans was already non-null. Use C99 style decls after statements in this function. --- ChangeLog | 6 ++++++ lib/dfa.c | 46 ++++++++++++++++++++-------------------------- 2 files changed, 26 insertions(+), 26 deletions(-) diff --git a/ChangeLog b/ChangeLog index fd3e9d8d71..a05fa6b13b 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,11 @@ 2016-12-09 Paul Eggert + dfa: fix performance bug that recomputes trans + * lib/dfa.c (build_state): Fix performance bug introduced in Nov + 25 on-demand changes. The bug caused build_state to reset all + d->trans elements to -2 even when d->trans was already non-null. + Use C99 style decls after statements in this function. + same-inode: port to MinGW Here st_ino is always 0, so change the definition of SAME_INODE so that 1 means the two files are the same, 0 with st_ino != 0 means diff --git a/lib/dfa.c b/lib/dfa.c index 0412b2c7ce..33754fca9d 100644 --- a/lib/dfa.c +++ b/lib/dfa.c @@ -2807,39 +2807,33 @@ realloc_trans_if_necessary (struct dfa *d, state_num new_state) static state_num build_state (state_num s, struct dfa *d, unsigned char uc) { - state_num *trans; /* The new transition table. */ - state_num i, maxstate; + /* A pointer to the new transition table, and the table itself. */ + state_num **ptrans = (ACCEPTING (s, *d) ? d->fails : d->trans) + s; + state_num *trans = *ptrans; - if (d->fails[s] != NULL) - trans = d->fails[s]; - else + if (!trans) { - state_num **ptrans = (ACCEPTING (s, *d) ? d->fails : d->trans) + s; - if (!*ptrans) + /* MAX_TRCOUNT is an arbitrary upper limit on the number of + transition tables that can exist at once, other than for + initial states. Often-used transition tables are quickly + rebuilt, whereas rarely-used ones are cleared away. */ + if (MAX_TRCOUNT <= d->trcount) { - /* MAX_TRCOUNT is an arbitrary upper limit on the number of - transition tables that can exist at once, other than for - initial states. Often-used transition tables are quickly - rebuilt, whereas rarely-used ones are cleared away. */ - if (MAX_TRCOUNT <= d->trcount) + for (state_num i = d->min_trcount; i < d->tralloc; i++) { - for (i = d->min_trcount; i < d->tralloc; i++) - { - free (d->trans[i]); - free (d->fails[i]); - d->trans[i] = d->fails[i] = NULL; - } - d->trcount = 0; + free (d->trans[i]); + free (d->fails[i]); + d->trans[i] = d->fails[i] = NULL; } - - d->trcount++; - *ptrans = xmalloc (NOTCHAR * sizeof *trans); + d->trcount = 0; } - trans = *ptrans; + + d->trcount++; + *ptrans = trans = xmalloc (NOTCHAR * sizeof *trans); /* Fill transition table with a default value which means that the transited state has not been calculated yet. */ - for (i = 0; i < NOTCHAR; i++) + for (int i = 0; i < NOTCHAR; i++) trans[i] = -2; } @@ -2857,8 +2851,8 @@ build_state (state_num s, struct dfa *d, unsigned char uc) /* Now go through the new transition table, and make sure that the trans and fail arrays are allocated large enough to hold a pointer for the largest state mentioned in the table. */ - maxstate = -1; - for (i = 0; i < NOTCHAR; ++i) + state_num maxstate = -1; + for (int i = 0; i < NOTCHAR; i++) if (maxstate < trans[i]) maxstate = trans[i]; realloc_trans_if_necessary (d, maxstate); -- 2.39.5