diff options
Diffstat (limited to 'lib/regex_internal.c')
-rw-r--r-- | lib/regex_internal.c | 328 |
1 files changed, 173 insertions, 155 deletions
diff --git a/lib/regex_internal.c b/lib/regex_internal.c index 385de6ffc..ad618cf66 100644 --- a/lib/regex_internal.c +++ b/lib/regex_internal.c @@ -17,17 +17,17 @@ with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ -static void re_string_construct_common (const char *str, int len, +static void re_string_construct_common (const char *str, Idx len, re_string_t *pstr, - RE_TRANSLATE_TYPE trans, int icase, + REG_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa) internal_function; -static re_dfastate_t *create_ci_newstate (re_dfa_t *dfa, +static re_dfastate_t *create_ci_newstate (const re_dfa_t *dfa, const re_node_set *nodes, - unsigned int hash) internal_function; -static re_dfastate_t *create_cd_newstate (re_dfa_t *dfa, + re_hashval_t hash) internal_function; +static re_dfastate_t *create_cd_newstate (const re_dfa_t *dfa, const re_node_set *nodes, unsigned int context, - unsigned int hash) internal_function; + re_hashval_t hash) internal_function; /* Functions for string operation. */ @@ -36,11 +36,11 @@ static re_dfastate_t *create_cd_newstate (re_dfa_t *dfa, static reg_errcode_t internal_function -re_string_allocate (re_string_t *pstr, const char *str, int len, int init_len, - RE_TRANSLATE_TYPE trans, int icase, const re_dfa_t *dfa) +re_string_allocate (re_string_t *pstr, const char *str, Idx len, Idx init_len, + REG_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa) { reg_errcode_t ret; - int init_buf_len; + Idx init_buf_len; /* Ensure at least one character fits into the buffers. */ if (init_len < dfa->mb_cur_max) @@ -64,8 +64,8 @@ re_string_allocate (re_string_t *pstr, const char *str, int len, int init_len, static reg_errcode_t internal_function -re_string_construct (re_string_t *pstr, const char *str, int len, - RE_TRANSLATE_TYPE trans, int icase, const re_dfa_t *dfa) +re_string_construct (re_string_t *pstr, const char *str, Idx len, + REG_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa) { reg_errcode_t ret; memset (pstr, '\0', sizeof (re_string_t)); @@ -127,18 +127,18 @@ re_string_construct (re_string_t *pstr, const char *str, int len, static reg_errcode_t internal_function -re_string_realloc_buffers (re_string_t *pstr, int new_buf_len) +re_string_realloc_buffers (re_string_t *pstr, Idx new_buf_len) { #ifdef RE_ENABLE_I18N if (pstr->mb_cur_max > 1) { - wint_t *new_wcs = re_realloc (pstr->wcs, wint_t, new_buf_len); + wint_t *new_wcs = re_xrealloc (pstr->wcs, wint_t, new_buf_len); if (BE (new_wcs == NULL, 0)) return REG_ESPACE; pstr->wcs = new_wcs; if (pstr->offsets != NULL) { - int *new_offsets = re_realloc (pstr->offsets, int, new_buf_len); + Idx *new_offsets = re_xrealloc (pstr->offsets, Idx, new_buf_len); if (BE (new_offsets == NULL, 0)) return REG_ESPACE; pstr->offsets = new_offsets; @@ -160,15 +160,15 @@ re_string_realloc_buffers (re_string_t *pstr, int new_buf_len) static void internal_function -re_string_construct_common (const char *str, int len, re_string_t *pstr, - RE_TRANSLATE_TYPE trans, int icase, +re_string_construct_common (const char *str, Idx len, re_string_t *pstr, + REG_TRANSLATE_TYPE trans, bool icase, const re_dfa_t *dfa) { pstr->raw_mbs = (const unsigned char *) str; pstr->len = len; pstr->raw_len = len; - pstr->trans = (unsigned RE_TRANSLATE_TYPE) trans; - pstr->icase = icase ? 1 : 0; + pstr->trans = (unsigned REG_TRANSLATE_TYPE) trans; + pstr->icase = icase; pstr->mbs_allocated = (trans != NULL || icase); pstr->mb_cur_max = dfa->mb_cur_max; pstr->is_utf8 = dfa->is_utf8; @@ -201,7 +201,7 @@ build_wcs_buffer (re_string_t *pstr) unsigned char buf[64]; #endif mbstate_t prev_st; - int byte_idx, end_idx, remain_len; + Idx byte_idx, end_idx, remain_len; size_t mbclen; /* Build the buffers from pstr->valid_len to either pstr->len or @@ -258,12 +258,12 @@ build_wcs_buffer (re_string_t *pstr) /* Build wide character buffer PSTR->WCS like build_wcs_buffer, but for REG_ICASE. */ -static int +static reg_errcode_t internal_function build_wcs_upper_buffer (re_string_t *pstr) { mbstate_t prev_st; - int src_idx, byte_idx, end_idx, remain_len; + Idx src_idx, byte_idx, end_idx, remain_len; size_t mbclen; #ifdef _LIBC char buf[MB_LEN_MAX]; @@ -301,7 +301,7 @@ build_wcs_upper_buffer (re_string_t *pstr) mbclen = mbrtowc (&wc, ((const char *) pstr->raw_mbs + pstr->raw_mbs_idx + byte_idx), remain_len, &pstr->cur_state); - if (BE (mbclen + 2 > 2, 1)) + if (BE ((size_t) (mbclen + 2) > 2, 1)) { wchar_t wcu = wc; if (iswlower (wc)) @@ -369,7 +369,7 @@ build_wcs_upper_buffer (re_string_t *pstr) else p = (const char *) pstr->raw_mbs + pstr->raw_mbs_idx + src_idx; mbclen = mbrtowc (&wc, p, remain_len, &pstr->cur_state); - if (BE (mbclen + 2 > 2, 1)) + if (BE ((size_t) (mbclen + 2) > 2, 1)) { wchar_t wcu = wc; if (iswlower (wc)) @@ -392,7 +392,7 @@ build_wcs_upper_buffer (re_string_t *pstr) if (pstr->offsets == NULL) { - pstr->offsets = re_malloc (int, pstr->bufs_len); + pstr->offsets = re_xmalloc (Idx, pstr->bufs_len); if (pstr->offsets == NULL) return REG_ESPACE; @@ -474,12 +474,12 @@ build_wcs_upper_buffer (re_string_t *pstr) /* Skip characters until the index becomes greater than NEW_RAW_IDX. Return the index. */ -static int +static Idx internal_function -re_string_skip_chars (re_string_t *pstr, int new_raw_idx, wint_t *last_wc) +re_string_skip_chars (re_string_t *pstr, Idx new_raw_idx, wint_t *last_wc) { mbstate_t prev_st; - int rawbuf_idx; + Idx rawbuf_idx; size_t mbclen; wchar_t wc = 0; @@ -487,7 +487,7 @@ re_string_skip_chars (re_string_t *pstr, int new_raw_idx, wint_t *last_wc) for (rawbuf_idx = pstr->raw_mbs_idx + pstr->valid_raw_len; rawbuf_idx < new_raw_idx;) { - int remain_len; + Idx remain_len; remain_len = pstr->len - rawbuf_idx; prev_st = pstr->cur_state; mbclen = mbrtowc (&wc, (const char *) pstr->raw_mbs + rawbuf_idx, @@ -513,7 +513,7 @@ static void internal_function build_upper_buffer (re_string_t *pstr) { - int char_idx, end_idx; + Idx char_idx, end_idx; end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len; for (char_idx = pstr->valid_len; char_idx < end_idx; ++char_idx) @@ -536,7 +536,7 @@ static void internal_function re_string_translate_buffer (re_string_t *pstr) { - int buf_idx, end_idx; + Idx buf_idx, end_idx; end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len; for (buf_idx = pstr->valid_len; buf_idx < end_idx; ++buf_idx) @@ -555,10 +555,13 @@ re_string_translate_buffer (re_string_t *pstr) static reg_errcode_t internal_function -re_string_reconstruct (re_string_t *pstr, int idx, int eflags) +re_string_reconstruct (re_string_t *pstr, Idx idx, int eflags) { - int offset = idx - pstr->raw_mbs_idx; - if (BE (offset < 0, 0)) + Idx offset; + + if (BE (pstr->raw_mbs_idx <= idx, 0)) + offset = idx - pstr->raw_mbs_idx; + else { /* Reset buffer. */ #ifdef RE_ENABLE_I18N @@ -621,7 +624,7 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags) #ifdef RE_ENABLE_I18N if (pstr->mb_cur_max > 1) { - int wcs_idx; + Idx wcs_idx; wint_t wc = WEOF; if (pstr->is_utf8) @@ -637,8 +640,9 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags) { mbstate_t cur_state; wchar_t wc2; - int mlen = raw + pstr->len - p; + Idx mlen = raw + pstr->len - p; unsigned char buf[6]; + size_t mbclen; q = p; if (BE (pstr->trans != NULL, 0)) @@ -651,14 +655,13 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags) /* XXX Don't use mbrtowc, we know which conversion to use (UTF-8 -> UCS4). */ memset (&cur_state, 0, sizeof (cur_state)); - mlen = (mbrtowc (&wc2, (const char *) p, mlen, - &cur_state) - - (raw + offset - p)); - if (mlen >= 0) + mbclen = mbrtowc (&wc2, (const char *) p, mlen, + &cur_state); + if (raw + offset - p <= mbclen && mbclen < (size_t) -2) { memset (&pstr->cur_state, '\0', sizeof (mbstate_t)); - pstr->valid_len = mlen; + pstr->valid_len = mbclen - (raw + offset - p); wc = wc2; } break; @@ -672,7 +675,7 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags) for (wcs_idx = 0; wcs_idx < pstr->valid_len; ++wcs_idx) pstr->wcs[wcs_idx] = WEOF; if (pstr->mbs_allocated) - memset (pstr->mbs, 255, pstr->valid_len); + memset (pstr->mbs, -1, pstr->valid_len); } pstr->valid_raw_len = pstr->valid_len; pstr->tip_context = ((BE (pstr->word_ops_used != 0, 0) @@ -707,7 +710,7 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags) { if (pstr->icase) { - int ret = build_wcs_upper_buffer (pstr); + reg_errcode_t ret = build_wcs_upper_buffer (pstr); if (BE (ret != REG_NOERROR, 0)) return ret; } @@ -731,10 +734,11 @@ re_string_reconstruct (re_string_t *pstr, int idx, int eflags) } static unsigned char -internal_function -re_string_peek_byte_case (const re_string_t *pstr, int idx) +internal_function __attribute ((pure)) +re_string_peek_byte_case (const re_string_t *pstr, Idx idx) { - int ch, off; + int ch; + Idx off; /* Handle the common (easiest) cases first. */ if (BE (!pstr->mbs_allocated, 1)) @@ -767,7 +771,7 @@ re_string_peek_byte_case (const re_string_t *pstr, int idx) } static unsigned char -internal_function +internal_function __attribute ((pure)) re_string_fetch_byte_case (re_string_t *pstr) { if (BE (!pstr->mbs_allocated, 1)) @@ -776,7 +780,8 @@ re_string_fetch_byte_case (re_string_t *pstr) #ifdef RE_ENABLE_I18N if (pstr->offsets_needed) { - int off, ch; + Idx off; + int ch; /* For tr_TR.UTF-8 [[:islower:]] there is [[: CAPITAL LETTER I WITH DOT lower:]] in mbs. Skip @@ -819,10 +824,10 @@ re_string_destruct (re_string_t *pstr) static unsigned int internal_function -re_string_context_at (const re_string_t *input, int idx, int eflags) +re_string_context_at (const re_string_t *input, Idx idx, int eflags) { int c; - if (BE (idx < 0, 0)) + if (BE (! REG_VALID_INDEX (idx), 0)) /* In this case, we use the value stored in input->tip_context, since we can't know the character in input->mbs[-1] here. */ return input->tip_context; @@ -833,15 +838,15 @@ re_string_context_at (const re_string_t *input, int idx, int eflags) if (input->mb_cur_max > 1) { wint_t wc; - int wc_idx = idx; + Idx wc_idx = idx; while(input->wcs[wc_idx] == WEOF) { #ifdef DEBUG /* It must not happen. */ - assert (wc_idx >= 0); + assert (REG_VALID_INDEX (wc_idx)); #endif --wc_idx; - if (wc_idx < 0) + if (! REG_VALID_INDEX (wc_idx)) return input->tip_context; } wc = input->wcs[wc_idx]; @@ -864,11 +869,11 @@ re_string_context_at (const re_string_t *input, int idx, int eflags) static reg_errcode_t internal_function -re_node_set_alloc (re_node_set *set, int size) +re_node_set_alloc (re_node_set *set, Idx size) { set->alloc = size; set->nelem = 0; - set->elems = re_malloc (int, size); + set->elems = re_xmalloc (Idx, size); if (BE (set->elems == NULL, 0)) return REG_ESPACE; return REG_NOERROR; @@ -876,11 +881,11 @@ re_node_set_alloc (re_node_set *set, int size) static reg_errcode_t internal_function -re_node_set_init_1 (re_node_set *set, int elem) +re_node_set_init_1 (re_node_set *set, Idx elem) { set->alloc = 1; set->nelem = 1; - set->elems = re_malloc (int, 1); + set->elems = re_malloc (Idx, 1); if (BE (set->elems == NULL, 0)) { set->alloc = set->nelem = 0; @@ -892,10 +897,10 @@ re_node_set_init_1 (re_node_set *set, int elem) static reg_errcode_t internal_function -re_node_set_init_2 (re_node_set *set, int elem1, int elem2) +re_node_set_init_2 (re_node_set *set, Idx elem1, Idx elem2) { set->alloc = 2; - set->elems = re_malloc (int, 2); + set->elems = re_malloc (Idx, 2); if (BE (set->elems == NULL, 0)) return REG_ESPACE; if (elem1 == elem2) @@ -928,13 +933,13 @@ re_node_set_init_copy (re_node_set *dest, const re_node_set *src) if (src->nelem > 0) { dest->alloc = dest->nelem; - dest->elems = re_malloc (int, dest->alloc); + dest->elems = re_malloc (Idx, dest->alloc); if (BE (dest->elems == NULL, 0)) { dest->alloc = dest->nelem = 0; return REG_ESPACE; } - memcpy (dest->elems, src->elems, src->nelem * sizeof (int)); + memcpy (dest->elems, src->elems, src->nelem * sizeof dest->elems[0]); } else re_node_set_init_empty (dest); @@ -950,7 +955,7 @@ internal_function re_node_set_add_intersect (re_node_set *dest, const re_node_set *src1, const re_node_set *src2) { - int i1, i2, is, id, delta, sbase; + Idx i1, i2, is, id, delta, sbase; if (src1->nelem == 0 || src2->nelem == 0) return REG_NOERROR; @@ -958,8 +963,13 @@ re_node_set_add_intersect (re_node_set *dest, const re_node_set *src1, conservative estimate. */ if (src1->nelem + src2->nelem + dest->nelem > dest->alloc) { - int new_alloc = src1->nelem + src2->nelem + dest->alloc; - int *new_elems = re_realloc (dest->elems, int, new_alloc); + Idx new_alloc = src1->nelem + src2->nelem + dest->alloc; + Idx *new_elems; + if (sizeof (Idx) < 3 + && (new_alloc < dest->alloc + || ((Idx) (src1->nelem + src2->nelem) < src1->nelem))) + return REG_ESPACE; + new_elems = re_xrealloc (dest->elems, Idx, new_alloc); if (BE (new_elems == NULL, 0)) return REG_ESPACE; dest->elems = new_elems; @@ -977,25 +987,25 @@ re_node_set_add_intersect (re_node_set *dest, const re_node_set *src1, if (src1->elems[i1] == src2->elems[i2]) { /* Try to find the item in DEST. Maybe we could binary search? */ - while (id >= 0 && dest->elems[id] > src1->elems[i1]) + while (REG_VALID_INDEX (id) && dest->elems[id] > src1->elems[i1]) --id; - if (id < 0 || dest->elems[id] != src1->elems[i1]) + if (! REG_VALID_INDEX (id) || dest->elems[id] != src1->elems[i1]) dest->elems[--sbase] = src1->elems[i1]; - if (--i1 < 0 || --i2 < 0) + if (! REG_VALID_INDEX (--i1) || ! REG_VALID_INDEX (--i2)) break; } /* Lower the highest of the two items. */ else if (src1->elems[i1] < src2->elems[i2]) { - if (--i2 < 0) + if (! REG_VALID_INDEX (--i2)) break; } else { - if (--i1 < 0) + if (! REG_VALID_INDEX (--i1)) break; } } @@ -1008,7 +1018,7 @@ re_node_set_add_intersect (re_node_set *dest, const re_node_set *src1, DEST elements are already in place; this is more or less the same loop that is in re_node_set_merge. */ dest->nelem += delta; - if (delta > 0 && id >= 0) + if (delta > 0 && REG_VALID_INDEX (id)) for (;;) { if (dest->elems[is] > dest->elems[id]) @@ -1022,13 +1032,13 @@ re_node_set_add_intersect (re_node_set *dest, const re_node_set *src1, { /* Slide from the bottom. */ dest->elems[id + delta] = dest->elems[id]; - if (--id < 0) + if (! REG_VALID_INDEX (--id)) break; } } /* Copy remaining SRC elements. */ - memcpy (dest->elems, dest->elems + sbase, delta * sizeof (int)); + memcpy (dest->elems, dest->elems + sbase, delta * sizeof dest->elems[0]); return REG_NOERROR; } @@ -1041,11 +1051,13 @@ internal_function re_node_set_init_union (re_node_set *dest, const re_node_set *src1, const re_node_set *src2) { - int i1, i2, id; + Idx i1, i2, id; if (src1 != NULL && src1->nelem > 0 && src2 != NULL && src2->nelem > 0) { dest->alloc = src1->nelem + src2->nelem; - dest->elems = re_malloc (int, dest->alloc); + if (sizeof (Idx) < 2 && dest->alloc < src1->nelem) + return REG_ESPACE; + dest->elems = re_xmalloc (Idx, dest->alloc); if (BE (dest->elems == NULL, 0)) return REG_ESPACE; } @@ -1073,13 +1085,13 @@ re_node_set_init_union (re_node_set *dest, const re_node_set *src1, if (i1 < src1->nelem) { memcpy (dest->elems + id, src1->elems + i1, - (src1->nelem - i1) * sizeof (int)); + (src1->nelem - i1) * sizeof dest->elems[0]); id += src1->nelem - i1; } else if (i2 < src2->nelem) { memcpy (dest->elems + id, src2->elems + i2, - (src2->nelem - i2) * sizeof (int)); + (src2->nelem - i2) * sizeof dest->elems[0]); id += src2->nelem - i2; } dest->nelem = id; @@ -1093,13 +1105,20 @@ static reg_errcode_t internal_function re_node_set_merge (re_node_set *dest, const re_node_set *src) { - int is, id, sbase, delta; + Idx is, id, sbase, delta; if (src == NULL || src->nelem == 0) return REG_NOERROR; + if (sizeof (Idx) < 3 + && ((Idx) (2 * src->nelem) < src->nelem + || (Idx) (2 * src->nelem + dest->nelem) < dest->nelem)) + return REG_ESPACE; if (dest->alloc < 2 * src->nelem + dest->nelem) { - int new_alloc = 2 * (src->nelem + dest->alloc); - int *new_buffer = re_realloc (dest->elems, int, new_alloc); + Idx new_alloc = src->nelem + dest->alloc; + Idx *new_buffer; + if (sizeof (Idx) < 4 && new_alloc < dest->alloc) + return REG_ESPACE; + new_buffer = re_x2realloc (dest->elems, Idx, &new_alloc); if (BE (new_buffer == NULL, 0)) return REG_ESPACE; dest->elems = new_buffer; @@ -1109,14 +1128,15 @@ re_node_set_merge (re_node_set *dest, const re_node_set *src) if (BE (dest->nelem == 0, 0)) { dest->nelem = src->nelem; - memcpy (dest->elems, src->elems, src->nelem * sizeof (int)); + memcpy (dest->elems, src->elems, src->nelem * sizeof dest->elems[0]); return REG_NOERROR; } /* Copy into the top of DEST the items of SRC that are not found in DEST. Maybe we could binary search in DEST? */ for (sbase = dest->nelem + 2 * src->nelem, - is = src->nelem - 1, id = dest->nelem - 1; is >= 0 && id >= 0; ) + is = src->nelem - 1, id = dest->nelem - 1; + REG_VALID_INDEX (is) && REG_VALID_INDEX (id); ) { if (dest->elems[id] == src->elems[is]) is--, id--; @@ -1126,11 +1146,12 @@ re_node_set_merge (re_node_set *dest, const re_node_set *src) --id; } - if (is >= 0) + if (REG_VALID_INDEX (is)) { /* If DEST is exhausted, the remaining items of SRC must be unique. */ sbase -= is + 1; - memcpy (dest->elems + sbase, src->elems, (is + 1) * sizeof (int)); + memcpy (dest->elems + sbase, src->elems, + (is + 1) * sizeof dest->elems[0]); } id = dest->nelem - 1; @@ -1155,11 +1176,11 @@ re_node_set_merge (re_node_set *dest, const re_node_set *src) { /* Slide from the bottom. */ dest->elems[id + delta] = dest->elems[id]; - if (--id < 0) + if (! REG_VALID_INDEX (--id)) { /* Copy remaining SRC elements. */ memcpy (dest->elems, dest->elems + sbase, - delta * sizeof (int)); + delta * sizeof dest->elems[0]); break; } } @@ -1170,38 +1191,31 @@ re_node_set_merge (re_node_set *dest, const re_node_set *src) /* Insert the new element ELEM to the re_node_set* SET. SET should not already have ELEM. - return -1 if an error is occured, return 1 otherwise. */ + Return true if successful. */ -static int +static bool internal_function -re_node_set_insert (re_node_set *set, int elem) +re_node_set_insert (re_node_set *set, Idx elem) { - int idx; + Idx idx; /* In case the set is empty. */ if (set->alloc == 0) - { - if (BE (re_node_set_init_1 (set, elem) == REG_NOERROR, 1)) - return 1; - else - return -1; - } + return re_node_set_init_1 (set, elem) == REG_NOERROR; if (BE (set->nelem, 0) == 0) { /* We already guaranteed above that set->alloc != 0. */ set->elems[0] = elem; ++set->nelem; - return 1; + return true; } /* Realloc if we need. */ if (set->alloc == set->nelem) { - int *new_elems; - set->alloc = set->alloc * 2; - new_elems = re_realloc (set->elems, int, set->alloc); + Idx *new_elems = re_x2realloc (set->elems, Idx, &set->alloc); if (BE (new_elems == NULL, 0)) - return -1; + return false; set->elems = new_elems; } @@ -1222,57 +1236,56 @@ re_node_set_insert (re_node_set *set, int elem) /* Insert the new element. */ set->elems[idx] = elem; ++set->nelem; - return 1; + return true; } /* Insert the new element ELEM to the re_node_set* SET. SET should not already have any element greater than or equal to ELEM. - Return -1 if an error is occured, return 1 otherwise. */ + Return true if successful. */ -static int +static bool internal_function -re_node_set_insert_last (re_node_set *set, int elem) +re_node_set_insert_last (re_node_set *set, Idx elem) { /* Realloc if we need. */ if (set->alloc == set->nelem) { - int *new_elems; - set->alloc = (set->alloc + 1) * 2; - new_elems = re_realloc (set->elems, int, set->alloc); + Idx *new_elems; + new_elems = re_x2realloc (set->elems, Idx, &set->alloc); if (BE (new_elems == NULL, 0)) - return -1; + return false; set->elems = new_elems; } /* Insert the new element. */ set->elems[set->nelem++] = elem; - return 1; + return true; } /* Compare two node sets SET1 and SET2. - return 1 if SET1 and SET2 are equivalent, return 0 otherwise. */ + Return true if SET1 and SET2 are equivalent. */ -static int -internal_function +static bool +internal_function __attribute ((pure)) re_node_set_compare (const re_node_set *set1, const re_node_set *set2) { - int i; + Idx i; if (set1 == NULL || set2 == NULL || set1->nelem != set2->nelem) - return 0; - for (i = set1->nelem ; --i >= 0 ; ) + return false; + for (i = set1->nelem ; REG_VALID_INDEX (--i) ; ) if (set1->elems[i] != set2->elems[i]) - return 0; - return 1; + return false; + return true; } /* Return (idx + 1) if SET contains the element ELEM, return 0 otherwise. */ -static int -internal_function -re_node_set_contains (const re_node_set *set, int elem) +static Idx +internal_function __attribute ((pure)) +re_node_set_contains (const re_node_set *set, Idx elem) { - unsigned int idx, right, mid; - if (set->nelem <= 0) + __re_size_t idx, right, mid; + if (! REG_VALID_NONZERO_INDEX (set->nelem)) return 0; /* Binary search the element. */ @@ -1291,7 +1304,7 @@ re_node_set_contains (const re_node_set *set, int elem) static void internal_function -re_node_set_remove_at (re_node_set *set, int idx) +re_node_set_remove_at (re_node_set *set, Idx idx) { if (idx < 0 || idx >= set->nelem) return; @@ -1302,31 +1315,31 @@ re_node_set_remove_at (re_node_set *set, int idx) /* Add the token TOKEN to dfa->nodes, and return the index of the token. - Or return -1, if an error will be occured. */ + Or return REG_MISSING if an error occurred. */ -static int +static Idx internal_function re_dfa_add_node (re_dfa_t *dfa, re_token_t token) { int type = token.type; if (BE (dfa->nodes_len >= dfa->nodes_alloc, 0)) { - int new_nodes_alloc = dfa->nodes_alloc * 2; - int *new_nexts, *new_indices; + Idx new_nodes_alloc = dfa->nodes_alloc; + Idx *new_nexts, *new_indices; re_node_set *new_edests, *new_eclosures; - re_token_t *new_nodes = re_realloc (dfa->nodes, re_token_t, - new_nodes_alloc); + re_token_t *new_nodes = re_x2realloc (dfa->nodes, re_token_t, + &new_nodes_alloc); if (BE (new_nodes == NULL, 0)) - return -1; + return REG_MISSING; dfa->nodes = new_nodes; - new_nexts = re_realloc (dfa->nexts, int, new_nodes_alloc); - new_indices = re_realloc (dfa->org_indices, int, new_nodes_alloc); - new_edests = re_realloc (dfa->edests, re_node_set, new_nodes_alloc); + new_nexts = re_realloc (dfa->nexts, Idx, new_nodes_alloc); + new_indices = re_realloc (dfa->org_indices, Idx, new_nodes_alloc); + new_edests = re_xrealloc (dfa->edests, re_node_set, new_nodes_alloc); new_eclosures = re_realloc (dfa->eclosures, re_node_set, new_nodes_alloc); if (BE (new_nexts == NULL || new_indices == NULL || new_edests == NULL || new_eclosures == NULL, 0)) - return -1; + return REG_MISSING; dfa->nexts = new_nexts; dfa->org_indices = new_indices; dfa->edests = new_edests; @@ -1339,18 +1352,18 @@ re_dfa_add_node (re_dfa_t *dfa, re_token_t token) dfa->nodes[dfa->nodes_len].accept_mb = (type == OP_PERIOD && dfa->mb_cur_max > 1) || type == COMPLEX_BRACKET; #endif - dfa->nexts[dfa->nodes_len] = -1; + dfa->nexts[dfa->nodes_len] = REG_MISSING; re_node_set_init_empty (dfa->edests + dfa->nodes_len); re_node_set_init_empty (dfa->eclosures + dfa->nodes_len); return dfa->nodes_len++; } -static inline unsigned int +static inline re_hashval_t internal_function calc_state_hash (const re_node_set *nodes, unsigned int context) { - unsigned int hash = nodes->nelem + context; - int i; + re_hashval_t hash = nodes->nelem + context; + Idx i; for (i = 0 ; i < nodes->nelem ; i++) hash += nodes->elems[i]; return hash; @@ -1369,10 +1382,10 @@ static re_dfastate_t* internal_function re_acquire_state (reg_errcode_t *err, re_dfa_t *dfa, const re_node_set *nodes) { - unsigned int hash; + re_hashval_t hash; re_dfastate_t *new_state; struct re_state_table_entry *spot; - int i; + Idx i; #ifdef lint /* Suppress bogus uninitialized-variable warnings. */ *err = REG_NOERROR; @@ -1420,10 +1433,10 @@ internal_function re_acquire_state_context (reg_errcode_t *err, re_dfa_t *dfa, const re_node_set *nodes, unsigned int context) { - unsigned int hash; + re_hashval_t hash; re_dfastate_t *new_state; struct re_state_table_entry *spot; - int i; + Idx i; #ifdef lint /* Suppress bogus uninitialized-variable warnings. */ *err = REG_NOERROR; @@ -1461,11 +1474,11 @@ re_acquire_state_context (reg_errcode_t *err, re_dfa_t *dfa, static reg_errcode_t internal_function -register_state (re_dfa_t *dfa, re_dfastate_t *newstate, unsigned int hash) +register_state (const re_dfa_t *dfa, re_dfastate_t *newstate, re_hashval_t hash) { struct re_state_table_entry *spot; reg_errcode_t err; - int i; + Idx i; newstate->hash = hash; err = re_node_set_alloc (&newstate->non_eps_nodes, newstate->nodes.nelem); @@ -1473,17 +1486,21 @@ register_state (re_dfa_t *dfa, re_dfastate_t *newstate, unsigned int hash) return REG_ESPACE; for (i = 0; i < newstate->nodes.nelem; i++) { - int elem = newstate->nodes.elems[i]; + Idx elem = newstate->nodes.elems[i]; if (!IS_EPSILON_NODE (dfa->nodes[elem].type)) - re_node_set_insert_last (&newstate->non_eps_nodes, elem); + { + bool ok = re_node_set_insert_last (&newstate->non_eps_nodes, elem); + if (BE (! ok, 0)) + return REG_ESPACE; + } } spot = dfa->state_table + (hash & dfa->state_hash_mask); if (BE (spot->alloc <= spot->num, 0)) { - int new_alloc = 2 * spot->num + 2; - re_dfastate_t **new_array = re_realloc (spot->array, re_dfastate_t *, - new_alloc); + Idx new_alloc = spot->num; + re_dfastate_t **new_array = re_x2realloc (spot->array, re_dfastate_t *, + &new_alloc); if (BE (new_array == NULL, 0)) return REG_ESPACE; spot->array = new_array; @@ -1498,13 +1515,14 @@ register_state (re_dfa_t *dfa, re_dfastate_t *newstate, unsigned int hash) static re_dfastate_t * internal_function -create_ci_newstate (re_dfa_t *dfa, const re_node_set *nodes, unsigned int hash) +create_ci_newstate (const re_dfa_t *dfa, const re_node_set *nodes, + re_hashval_t hash) { - int i; + Idx i; reg_errcode_t err; re_dfastate_t *newstate; - newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1); + newstate = re_calloc (re_dfastate_t, 1); if (BE (newstate == NULL, 0)) return NULL; err = re_node_set_init_copy (&newstate->nodes, nodes); @@ -1547,14 +1565,14 @@ create_ci_newstate (re_dfa_t *dfa, const re_node_set *nodes, unsigned int hash) static re_dfastate_t * internal_function -create_cd_newstate (re_dfa_t *dfa, const re_node_set *nodes, - unsigned int context, unsigned int hash) +create_cd_newstate (const re_dfa_t *dfa, const re_node_set *nodes, + unsigned int context, re_hashval_t hash) { - int i, nctx_nodes = 0; + Idx i, nctx_nodes = 0; reg_errcode_t err; re_dfastate_t *newstate; - newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1); + newstate = re_calloc (re_dfastate_t, 1); if (BE (newstate == NULL, 0)) return NULL; err = re_node_set_init_copy (&newstate->nodes, nodes); |