diff options
author | Paolo Bonzini <bonzini@gnu.org> | 2004-11-22 16:04:47 +0000 |
---|---|---|
committer | Paolo Bonzini <bonzini@gnu.org> | 2008-01-09 16:10:54 +0100 |
commit | 2e543b5d13add8ed8f83a71ec5c31770700d7358 (patch) | |
tree | 03abf0dda85db539e1b00b79a60e0a34449a9597 /lib | |
parent | 611e77d579b58b2cf6da9249d6d850b6fdb8e6e8 (diff) | |
download | sed-2e543b5d13add8ed8f83a71ec5c31770700d7358.tar.gz |
restore transit_state optimization, lost in previous checkin
previous checkin was a merge from glibc
git-archimport-id: bonzini@gnu.org--2004b/sed--stable--4.1--patch-21
Diffstat (limited to 'lib')
-rw-r--r-- | lib/regex_internal.c | 1 | ||||
-rw-r--r-- | lib/regex_internal.h | 3 | ||||
-rw-r--r-- | lib/regexec.c | 81 |
3 files changed, 43 insertions, 42 deletions
diff --git a/lib/regex_internal.c b/lib/regex_internal.c index bb1d73d..d6f44b6 100644 --- a/lib/regex_internal.c +++ b/lib/regex_internal.c @@ -1641,6 +1641,7 @@ free_state (state) re_free (state->entrance_nodes); } re_node_set_free (&state->nodes); + re_free (state->word_trtable); re_free (state->trtable); re_free (state); } diff --git a/lib/regex_internal.h b/lib/regex_internal.h index a778032..da774f8 100644 --- a/lib/regex_internal.h +++ b/lib/regex_internal.h @@ -482,7 +482,7 @@ struct re_dfastate_t unsigned int hash; re_node_set nodes; re_node_set *entrance_nodes; - struct re_dfastate_t **trtable; + struct re_dfastate_t **trtable, **word_trtable; unsigned int context : 4; unsigned int halt : 1; /* If this state can accept `multi byte'. @@ -492,7 +492,6 @@ struct re_dfastate_t /* If this state has backreference node(s). */ unsigned int has_backref : 1; unsigned int has_constraint : 1; - unsigned int word_trtable : 1; }; typedef struct re_dfastate_t re_dfastate_t; diff --git a/lib/regexec.c b/lib/regexec.c index 5877ade..1992f4f 100644 --- a/lib/regexec.c +++ b/lib/regexec.c @@ -175,8 +175,8 @@ static reg_errcode_t check_arrival_expand_ecl_sub (re_dfa_t *dfa, static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes, int cur_str, int subexp_num, int type) internal_function; -static re_dfastate_t **build_trtable (re_dfa_t *dfa, - re_dfastate_t *state) internal_function; +static int build_trtable (re_dfa_t *dfa, + re_dfastate_t *state) internal_function; #ifdef RE_ENABLE_I18N static int check_node_accept_bytes (re_dfa_t *dfa, int node_idx, const re_string_t *input, int idx) internal_function; @@ -2213,7 +2213,6 @@ transit_state (err, mctx, state) re_match_context_t *mctx; re_dfastate_t *state; { - re_dfa_t *const dfa = mctx->dfa; re_dfastate_t **trtable; unsigned char ch; @@ -2228,21 +2227,22 @@ transit_state (err, mctx, state) #endif /* RE_ENABLE_I18N */ /* Then decide the next state with the single byte. */ - if (1) +#if 0 + if (0) + /* don't use transition table */ + return transit_state_sb (err, mctx, state); +#endif + + /* Use transition table */ + ch = re_string_fetch_byte (&mctx->input); + for (;;) { - /* Use transition table */ - ch = re_string_fetch_byte (&mctx->input); trtable = state->trtable; - if (trtable == NULL) - { - trtable = build_trtable (dfa, state); - if (trtable == NULL) - { - *err = REG_ESPACE; - return NULL; - } - } - if (BE (state->word_trtable, 0)) + if (BE (trtable != NULL, 1)) + return trtable[ch]; + + trtable = state->word_trtable; + if (BE (trtable != NULL, 1)) { unsigned int context; context @@ -2254,14 +2254,15 @@ transit_state (err, mctx, state) else return trtable[ch]; } - else - return trtable[ch]; + + if (!build_trtable (mctx->dfa, state)) + { + *err = REG_ESPACE; + return NULL; + } + + /* Retry, we now have a transition table. */ } -#if 0 - else - /* don't use transition table */ - return transit_state_sb (err, mctx, state); -#endif } /* Update the state_log if we need */ @@ -3265,15 +3266,15 @@ expand_bkref_cache (mctx, cur_nodes, cur_str, subexp_num, } /* Build transition table for the state. - Return the new table if succeeded, otherwise return NULL. */ + Return 1 if succeeded, otherwise return NULL. */ -static re_dfastate_t ** +static int build_trtable (dfa, state) re_dfa_t *dfa; re_dfastate_t *state; { reg_errcode_t err; - int i, j, ch; + int i, j, ch, need_word_trtable = 0; unsigned int elem, mask; int dests_node_malloced = 0, dest_states_malloced = 0; int ndests; /* Number of the destination states from `state'. */ @@ -3297,13 +3298,13 @@ build_trtable (dfa, state) dests_node = (re_node_set *) malloc ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX); if (BE (dests_node == NULL, 0)) - return NULL; + return 0; dests_node_malloced = 1; } dests_ch = (bitset *) (dests_node + SBC_MAX); /* Initialize transiton table. */ - state->word_trtable = 0; + state->word_trtable = state->trtable = 0; /* At first, group all nodes belonging to `state' into several destinations. */ @@ -3312,14 +3313,14 @@ build_trtable (dfa, state) { if (dests_node_malloced) free (dests_node); - /* Return NULL in case of an error, trtable otherwise. */ + /* Return 0 in case of an error, 1 otherwise. */ if (ndests == 0) { state->trtable = (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);; - return state->trtable; + return 1; } - return NULL; + return 0; } err = re_node_set_alloc (&follows, ndests + 1); @@ -3346,7 +3347,7 @@ out_free: re_node_set_free (dests_node + i); if (dests_node_malloced) free (dests_node); - return NULL; + return 0; } dest_states_malloced = 1; } @@ -3384,7 +3385,7 @@ out_free: if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1) - state->word_trtable = 1; + need_word_trtable = 1; dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows, CONTEXT_NEWLINE); @@ -3399,13 +3400,14 @@ out_free: bitset_merge (acceptable, dests_ch[i]); } - if (!BE (state->word_trtable, 0)) + if (!BE (need_word_trtable, 0)) { /* We don't care about whether the following character is a word character, or we are in a single-byte character set so we can discern by looking at the character code: allocate a 256-entry transition table. */ - trtable = (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX); + trtable = state->trtable = + (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX); if (BE (trtable == NULL, 0)) goto out_free; @@ -3435,8 +3437,8 @@ out_free: by looking at the character code: build two 256-entry transition tables, one starting at trtable[0] and one starting at trtable[SBC_MAX]. */ - trtable = (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), - 2 * SBC_MAX); + trtable = state->word_trtable = + (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX); if (BE (trtable == NULL, 0)) goto out_free; @@ -3467,7 +3469,7 @@ out_free: { /* k-th destination accepts newline character. */ trtable[NEWLINE_CHAR] = dest_states_nl[j]; - if (state->word_trtable) + if (need_word_trtable) trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j]; /* There must be only one destination which accepts newline. See group_nodes_into_DFAstates. */ @@ -3485,8 +3487,7 @@ out_free: if (dests_node_malloced) free (dests_node); - state->trtable = trtable; - return trtable; + return 1; } /* Group all nodes belonging to STATE into several destinations. |