From 8503c987b63bd8badff1e4c9286949b025cecdb3 Mon Sep 17 00:00:00 2001 From: Ulrich Drepper Date: Fri, 2 Jan 2004 11:08:23 +0000 Subject: Update. 2004-01-01 Paolo Bonzini * posix/regex_internal.h (re_dfastate_t): Fix size of the CONTEXT bitfield. * posix/regex_internal.c (re_node_set_insert): Rewrite. --- posix/regex_internal.c | 50 +++++++++++++++++++++++--------------------------- posix/regex_internal.h | 7 ++----- 2 files changed, 25 insertions(+), 32 deletions(-) (limited to 'posix') diff --git a/posix/regex_internal.c b/posix/regex_internal.c index 4cff96f6d6..f07d4a2e7f 100644 --- a/posix/regex_internal.c +++ b/posix/regex_internal.c @@ -1,5 +1,5 @@ /* Extended regular expression matching and search library. - Copyright (C) 2002, 2003 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc. This file is part of the GNU C Library. Contributed by Isamu Hasegawa . @@ -1148,7 +1148,7 @@ re_node_set_merge (dest, src) } /* Insert the new element ELEM to the re_node_set* SET. - return 0 if SET already has ELEM, + SET should not already have ELEM. return -1 if an error is occured, return 1 otherwise. */ static int @@ -1157,8 +1157,8 @@ re_node_set_insert (set, elem) int elem; { int idx, right, mid; - /* In case of the set is empty. */ - if (set->elems == NULL || set->alloc == 0) + /* In case the set is empty. */ + if (set->alloc == 0) { if (BE (re_node_set_init_1 (set, elem) == REG_NOERROR, 1)) return 1; @@ -1166,43 +1166,39 @@ re_node_set_insert (set, elem) return -1; } - /* Binary search the spot we will add the new element. */ - idx = 0; - right = set->nelem; - while (idx < right) + if (BE (set->nelem, 0) == 0) { - mid = (idx + right) / 2; - if (set->elems[mid] < elem) - idx = mid + 1; - else - right = mid; + /* We already guaranteed above that set->alloc != 0. */ + set->elems[0] = elem; + ++set->nelem; + return 1; } /* Realloc if we need. */ - if (set->alloc < set->nelem + 1) + if (set->alloc == set->nelem) { int *new_array; set->alloc = set->alloc * 2; - new_array = re_malloc (int, set->alloc); + new_array = re_realloc (set->elems, int, set->alloc); if (BE (new_array == NULL, 0)) return -1; - /* Copy the elements they are followed by the new element. */ - if (idx > 0) - memcpy (new_array, set->elems, sizeof (int) * (idx)); - /* Copy the elements which follows the new element. */ - if (set->nelem - idx > 0) - memcpy (new_array + idx + 1, set->elems + idx, - sizeof (int) * (set->nelem - idx)); - re_free (set->elems); set->elems = new_array; } + + /* Move the elements which follows the new element. Test the + first element separately to skip a check in the inner loop. */ + if (elem < set->elems[0]) + { + idx = 0; + memmove (set->elems + 1, set->elems, + sizeof (int) * set->nelem); + } else { - /* Move the elements which follows the new element. */ - if (set->nelem - idx > 0) - memmove (set->elems + idx + 1, set->elems + idx, - sizeof (int) * (set->nelem - idx)); + for (idx = set->nelem; set->elems[idx - 1] > elem; idx--) + set->elems[idx] = set->elems[idx - 1]; } + /* Insert the new element. */ set->elems[idx] = elem; ++set->nelem; diff --git a/posix/regex_internal.h b/posix/regex_internal.h index 18414a58cc..c2824ed977 100644 --- a/posix/regex_internal.h +++ b/posix/regex_internal.h @@ -1,5 +1,5 @@ /* Extended regular expression matching and search library. - Copyright (C) 2002, 2003 Free Software Foundation, Inc. + Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc. This file is part of the GNU C Library. Contributed by Isamu Hasegawa . @@ -471,10 +471,7 @@ struct re_dfastate_t re_node_set nodes; re_node_set *entrance_nodes; struct re_dfastate_t **trtable; - /* If this state is a special state. - A state is a special state if the state is the halt state, or - a anchor. */ - unsigned int context : 2; + unsigned int context : 10; unsigned int halt : 1; /* If this state can accept `multi byte'. Note that we refer to multibyte characters, and multi character -- cgit v1.2.3