From 5cf1ec52565b19d68c3c0fbd853c0b5de26b27b2 Mon Sep 17 00:00:00 2001 From: Ulrich Drepper Date: Fri, 10 Dec 2004 04:37:58 +0000 Subject: Update. 2004-12-07 Paolo Bonzini * posix/regexec.c (proceed_next_node): Simplify treatment of epsilon nodes. Pass the pushed node to push_fail_stack. (push_fail_stack): Accept a single node rather than an array of two epsilon destinations. (build_sifted_states): Only walk non-epsilon nodes. (check_arrival): Don't pass epsilon nodes to check_arrival_add_next_nodes. (check_arrival_add_next_nodes) [DEBUG]: Abort if an epsilon node is found. (check_node_accept): Do expensive checks later. (add_epsilon_src_nodes): Cache result of merging the inveclosures. * posix/regex_internal.h (re_dfastate_t): Add non_eps_nodes and inveclosure. (re_string_elem_size_at, re_string_char_size_at, re_string_wchar_at, re_string_context_at, re_string_peek_byte_case, re_string_fetch_byte_case, re_node_set_compare, re_node_set_contains): Declare as pure. * posix/regex_internal.c (create_newstate_common): Remove. (register_state): Move part of it here. Initialize non_eps_nodes. (free_state): Free inveclosure and non_eps_nodes. (create_cd_newstate, create_ci_newstate): Allocate the new re_dfastate_t here. --- posix/regex_internal.c | 70 ++++++++++++++++++++++++++------------------------ 1 file changed, 36 insertions(+), 34 deletions(-) (limited to 'posix/regex_internal.c') diff --git a/posix/regex_internal.c b/posix/regex_internal.c index cb439e5d7c..001b50b134 100644 --- a/posix/regex_internal.c +++ b/posix/regex_internal.c @@ -26,9 +26,6 @@ static void re_string_construct_common (const char *str, int len, static int re_string_skip_chars (re_string_t *pstr, int new_raw_idx, wint_t *last_wc) internal_function; #endif /* RE_ENABLE_I18N */ -static re_dfastate_t *create_newstate_common (re_dfa_t *dfa, - const re_node_set *nodes, - unsigned int hash) internal_function; static reg_errcode_t register_state (re_dfa_t *dfa, re_dfastate_t *newstate, unsigned int hash) internal_function; static re_dfastate_t *create_ci_newstate (re_dfa_t *dfa, @@ -1298,7 +1295,7 @@ re_node_set_contains (set, elem) const re_node_set *set; int elem; { - int idx, right, mid; + unsigned int idx, right, mid; if (set->nelem <= 0) return 0; @@ -1484,43 +1481,32 @@ re_acquire_state_context (err, dfa, nodes, context) } } -/* Allocate memory for DFA state and initialize common properties. - Return the new state if succeeded, otherwise return NULL. */ +/* Finish initialization of the new state NEWSTATE, and using its hash value + HASH put in the appropriate bucket of DFA's state table. Return value + indicates the error code if failed. */ -static re_dfastate_t * -create_newstate_common (dfa, nodes, hash) +static reg_errcode_t +register_state (dfa, newstate, hash) re_dfa_t *dfa; - const re_node_set *nodes; + re_dfastate_t *newstate; unsigned int hash; { - re_dfastate_t *newstate; + struct re_state_table_entry *spot; reg_errcode_t err; - newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1); - if (BE (newstate == NULL, 0)) - return NULL; - err = re_node_set_init_copy (&newstate->nodes, nodes); + int i; + + newstate->hash = hash; + err = re_node_set_alloc (&newstate->non_eps_nodes, newstate->nodes.nelem); if (BE (err != REG_NOERROR, 0)) + return REG_ESPACE; + for (i = 0; i < newstate->nodes.nelem; i++) { - re_free (newstate); - return NULL; + int elem = newstate->nodes.elems[i]; + if (!IS_EPSILON_NODE (dfa->nodes[elem].type)) + re_node_set_insert_last (&newstate->non_eps_nodes, elem); } - newstate->trtable = NULL; - newstate->hash = hash; - return newstate; -} -/* Store the new state NEWSTATE whose hash value is HASH in appropriate - position. Return value indicate the error code if failed. */ - -static reg_errcode_t -register_state (dfa, newstate, hash) - re_dfa_t *dfa; - re_dfastate_t *newstate; - unsigned int hash; -{ - struct re_state_table_entry *spot; spot = dfa->state_table + (hash & dfa->state_hash_mask); - if (BE (spot->alloc <= spot->num, 0)) { int new_alloc = 2 * spot->num + 2; @@ -1547,11 +1533,18 @@ create_ci_newstate (dfa, nodes, hash) int i; reg_errcode_t err; re_dfastate_t *newstate; - newstate = create_newstate_common (dfa, nodes, hash); + + newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1); if (BE (newstate == NULL, 0)) return NULL; - newstate->entrance_nodes = &newstate->nodes; + err = re_node_set_init_copy (&newstate->nodes, nodes); + if (BE (err != REG_NOERROR, 0)) + { + re_free (newstate); + return NULL; + } + newstate->entrance_nodes = &newstate->nodes; for (i = 0 ; i < nodes->nelem ; i++) { re_token_t *node = dfa->nodes + nodes->elems[i]; @@ -1595,9 +1588,16 @@ create_cd_newstate (dfa, nodes, context, hash) reg_errcode_t err; re_dfastate_t *newstate; - newstate = create_newstate_common (dfa, nodes, hash); + newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1); if (BE (newstate == NULL, 0)) return NULL; + err = re_node_set_init_copy (&newstate->nodes, nodes); + if (BE (err != REG_NOERROR, 0)) + { + re_free (newstate); + return NULL; + } + newstate->context = context; newstate->entrance_nodes = &newstate->nodes; @@ -1660,6 +1660,8 @@ static void free_state (state) re_dfastate_t *state; { + re_node_set_free (&state->non_eps_nodes); + re_node_set_free (&state->inveclosure); if (state->entrance_nodes != &state->nodes) { re_node_set_free (state->entrance_nodes); -- cgit v1.2.3