aboutsummaryrefslogtreecommitdiff
path: root/posix
diff options
context:
space:
mode:
authorUlrich Drepper <drepper@redhat.com>2002-12-17 10:58:04 +0000
committerUlrich Drepper <drepper@redhat.com>2002-12-17 10:58:04 +0000
commita7d5c29129aab547faff1fd2cfe0d9095ec4689b (patch)
tree9890ba8c05b46ae778b6529a095f32d12096a459 /posix
parent0bc02a400815ace6f0f9265a681e2b0bd92ad683 (diff)
downloadglibc-a7d5c29129aab547faff1fd2cfe0d9095ec4689b.tar
glibc-a7d5c29129aab547faff1fd2cfe0d9095ec4689b.tar.gz
glibc-a7d5c29129aab547faff1fd2cfe0d9095ec4689b.tar.bz2
glibc-a7d5c29129aab547faff1fd2cfe0d9095ec4689b.zip
Update.
2002-12-17 Isamu Hasegawa <isamu@yamato.ibm.com> * posix/regcomp.c (free_workarea_compile): Free the new member ORG_INDICES. (analyze): Initialize ORG_INDICES. (duplicate_node_closure): Search for a existing node, which is duplicated from the node ORG_DEST and satisfies the constraint CONSTRAINT. And use it to avoid inifimite loop. (search_duplicated_node): New function. (duplicate_node): Store the index of the original node. * posix/regex_internal.c (re_dfa_add_node): Realloc ORG_INDICES if needed. * posix/regex_internal.h (re_dfa_t): Add new members.
Diffstat (limited to 'posix')
-rw-r--r--posix/regcomp.c65
-rw-r--r--posix/regex_internal.c9
-rw-r--r--posix/regex_internal.h1
3 files changed, 59 insertions, 16 deletions
diff --git a/posix/regcomp.c b/posix/regcomp.c
index 876c45c674..97ec6e32f0 100644
--- a/posix/regcomp.c
+++ b/posix/regcomp.c
@@ -90,6 +90,8 @@ static reg_errcode_t duplicate_node_closure (re_dfa_t *dfa, int top_org_node,
unsigned int constraint);
static reg_errcode_t duplicate_node (int *new_idx, re_dfa_t *dfa, int org_idx,
unsigned int constraint);
+static int search_duplicated_node (re_dfa_t *dfa, int org_node,
+ unsigned int constraint);
static reg_errcode_t calc_eclosure (re_dfa_t *dfa);
static reg_errcode_t calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa,
int node, int root);
@@ -865,6 +867,8 @@ free_workarea_compile (preg)
re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
free_bin_tree (dfa->str_tree);
dfa->str_tree = NULL;
+ re_free (dfa->org_indices);
+ dfa->org_indices = NULL;
}
/* Create initial states for all contexts. */
@@ -959,10 +963,11 @@ analyze (dfa)
/* Allocate arrays. */
dfa->nexts = re_malloc (int, dfa->nodes_alloc);
+ dfa->org_indices = re_malloc (int, dfa->nodes_alloc);
dfa->edests = re_malloc (re_node_set, dfa->nodes_alloc);
dfa->eclosures = re_malloc (re_node_set, dfa->nodes_alloc);
dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_alloc);
- if (BE (dfa->nexts == NULL || dfa->edests == NULL
+ if (BE (dfa->nexts == NULL || dfa->org_indices == NULL || dfa->edests == NULL
|| dfa->eclosures == NULL || dfa->inveclosures == NULL, 0))
return REG_ESPACE;
/* Initialize them. */
@@ -1261,20 +1266,33 @@ duplicate_node_closure (dfa, top_org_node, top_clone_node, root_node,
else /* dfa->edests[org_node].nelem == 2 */
{
/* In case of the node can epsilon-transit, and it has two
- destinations. */
+ destinations. E.g. '|', '*', '+', '?'. */
org_dest = dfa->edests[org_node].elems[0];
re_node_set_empty (dfa->edests + clone_node);
- err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
- if (BE (err != REG_NOERROR, 0))
- return err;
- ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
- if (BE (ret < 0, 0))
- return REG_ESPACE;
-
- err = duplicate_node_closure (dfa, org_dest, clone_dest, root_node,
- constraint);
- if (BE (err != REG_NOERROR, 0))
- return err;
+ /* Search for a duplicated node which satisfies the constraint. */
+ clone_dest = search_duplicated_node (dfa, org_dest, constraint);
+ if (clone_dest == -1)
+ {
+ /* There are no such a duplicated node, create a new one. */
+ err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
+ if (BE (err != REG_NOERROR, 0))
+ return err;
+ ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
+ if (BE (ret < 0, 0))
+ return REG_ESPACE;
+ err = duplicate_node_closure (dfa, org_dest, clone_dest,
+ root_node, constraint);
+ if (BE (err != REG_NOERROR, 0))
+ return err;
+ }
+ else
+ {
+ /* There are a duplicated node which satisfy the constraint,
+ use it to avoid infinite loop. */
+ ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
+ if (BE (ret < 0, 0))
+ return REG_ESPACE;
+ }
org_dest = dfa->edests[org_node].elems[1];
err = duplicate_node (&clone_dest, dfa, org_dest, constraint);
@@ -1290,6 +1308,25 @@ duplicate_node_closure (dfa, top_org_node, top_clone_node, root_node,
return REG_NOERROR;
}
+/* Search for a node which is duplicated from the node ORG_NODE, and
+ satisfies the constraint CONSTRAINT. */
+
+static int
+search_duplicated_node (dfa, org_node, constraint)
+ re_dfa_t *dfa;
+ int org_node;
+ unsigned int constraint;
+{
+ int idx;
+ for (idx = dfa->nodes_len - 1; dfa->nodes[idx].duplicated && idx > 0; --idx)
+ {
+ if (org_node == dfa->org_indices[idx]
+ && constraint == dfa->nodes[idx].constraint)
+ return idx; /* Found. */
+ }
+ return -1; /* Not found. */
+}
+
/* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.
The new index will be stored in NEW_IDX and return REG_NOERROR if succeeded,
otherwise return the error code. */
@@ -1315,6 +1352,8 @@ duplicate_node (new_idx, dfa, org_idx, constraint)
re_node_set_init_empty (dfa->eclosures + dup_idx);
re_node_set_init_empty (dfa->inveclosures + dup_idx);
+ /* Store the index of the original node. */
+ dfa->org_indices[dup_idx] = org_idx;
*new_idx = dup_idx;
return REG_NOERROR;
}
diff --git a/posix/regex_internal.c b/posix/regex_internal.c
index a9559e2768..a3ce236c54 100644
--- a/posix/regex_internal.c
+++ b/posix/regex_internal.c
@@ -986,19 +986,22 @@ re_dfa_add_node (dfa, token, mode)
dfa->nodes = new_array;
if (mode)
{
- int *new_nexts;
+ int *new_nexts, *new_indices;
re_node_set *new_edests, *new_eclosures, *new_inveclosures;
new_nexts = re_realloc (dfa->nexts, int, dfa->nodes_alloc);
+ new_indices = re_realloc (dfa->org_indices, int, dfa->nodes_alloc);
new_edests = re_realloc (dfa->edests, re_node_set, dfa->nodes_alloc);
new_eclosures = re_realloc (dfa->eclosures, re_node_set,
dfa->nodes_alloc);
new_inveclosures = re_realloc (dfa->inveclosures, re_node_set,
dfa->nodes_alloc);
- if (BE (new_nexts == NULL || new_edests == NULL
- || new_eclosures == NULL || new_inveclosures == NULL, 0))
+ if (BE (new_nexts == NULL || new_indices == NULL
+ || new_edests == NULL || new_eclosures == NULL
+ || new_inveclosures == NULL, 0))
return -1;
dfa->nexts = new_nexts;
+ dfa->org_indices = new_indices;
dfa->edests = new_edests;
dfa->eclosures = new_eclosures;
dfa->inveclosures = new_inveclosures;
diff --git a/posix/regex_internal.h b/posix/regex_internal.h
index 50867878ed..ea04a6f61a 100644
--- a/posix/regex_internal.h
+++ b/posix/regex_internal.h
@@ -508,6 +508,7 @@ struct re_dfa_t
int nodes_len;
bin_tree_t *str_tree;
int *nexts;
+ int *org_indices;
re_node_set *edests;
re_node_set *eclosures;
re_node_set *inveclosures;