Tags: patch
I'm not going to install the attached memory-management changes yet, as
they're fairly intrusive and I want to give them a chance to cool off.
The benefits are minor but are there, e.g., this shrinks the overall
grep text size by 1.2% on my platform (Fedora 20 x86-64). Mostly,
though, I wanted the memory management to be clearer.
From 57379463bda50eed024dc22fab8325acf02314db Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email protected]>
Date: Fri, 28 Mar 2014 18:13:33 -0700
Subject: [PATCH] dfa: speed up memory allocation, port to IRIX
This change was prompted by a porting problem on IRIX: it
defines its own MALLOC macro, which clashes with ours.
More generally, the MALLOC etc. macros are confusing, as they
look like functions but do not have C-function semantics.
A functional style makes the code easier to read, and though
it lengthens some calls it shortens the code overall.
* src/dfa.c (struct dfa): Combine two vectors 'range_sts' and
'range_ends' into a single vector 'ranges'. Similarly, combine
four vectors 'trans', 'fails', 'success', 'newlines' into a single
vector 'tab'. This simplifies memory allocation. Remove member
nmultibyte_prop; not needed, as it's the same as talloc.
Remove member realtrans, as it's deducible from trans.
All uses changed.
(XNMALLOC, XCALLOC, CALLOC, MALLOC, REALLOC, REALLOC_IF_NECESSARY):
Remove. All uses changed to use xnmalloc etc.
(copy, merge): Don't try to preserve old data with realloc, as we'll
be overwriting it anyway. Use free+malloc isntead.
(dfastate): Allocate grps and labels on the stack, as their
size is known at compile time.
(realloc_trans_if_necessary): Move earlier, to avoid forward decl.
(build_state): Use it, to avoid duplicate code.
(dfainit): Omit no-longer-needed initialization.
---
src/dfa.c | 385 +++++++++++++++++++++++++++-----------------------------------
1 file changed, 170 insertions(+), 215 deletions(-)
diff --git a/src/dfa.c b/src/dfa.c
index 4ed2189..e702ac5 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -324,8 +324,11 @@ struct mb_char_classes
size_t nchars;
wctype_t *ch_classes; /* Character classes. */
size_t nch_classes;
- wchar_t *range_sts; /* Range characters (start of the range). */
- wchar_t *range_ends; /* Range characters (end of the range). */
+ struct /* Range characters. */
+ {
+ wchar_t beg; /* Range start. */
+ wchar_t end; /* Range end. */
+ } *ranges;
size_t nranges;
char **equivs; /* Equivalence classes. */
size_t nequivs;
@@ -373,7 +376,6 @@ struct dfa
multibyte_prop
= 3 , 1 , 0 , 2 , 3
*/
- size_t nmultibyte_prop;
int *multibyte_prop;
#if MBS_SUPPORT
@@ -412,27 +414,30 @@ struct dfa
/* Fields filled by dfaexec. */
state_num tralloc; /* Number of transition tables that have
- slots so far. */
+ slots so far, not counting tab[-1]. */
int trcount; /* Number of transition tables that have
actually been built. */
- state_num **trans; /* Transition tables for states that can
+ /* Tables indexed by state. */
+ struct dfatab
+ {
+ state_num *trans; /* Transition table for states that can
never accept. If the transitions for a
state have not yet been computed, or the
state could possibly accept, its entry in
- this table is NULL. */
- state_num **realtrans; /* Trans always points to realtrans + 1; this
- is so trans[-1] can contain NULL. */
- state_num **fails; /* Transition tables after failing to accept
+ this table is NULL. tab[-1].trans is always
+ NULL. */
+ state_num *fails; /* Transition table after failing to accept
on a state that potentially could do so. */
- int *success; /* Table of acceptance conditions used in
+ int success; /* Acceptance conditions used in
dfaexec and computed in build_state. */
- state_num *newlines; /* Transitions on newlines. The entry for a
+ state_num newlines; /* Transition on newlines. The entry for a
newline in any transition table is always
-1 so we can count lines without wasting
too many cycles. The transition for a
newline is stored separately and handled
as a special case. Newline is also used
as a sentinel at the end of the buffer. */
+ } *tab;
struct dfamust *musts; /* List of strings, at least one of which
is known to appear in any r.e. matching
the dfa. */
@@ -451,40 +456,6 @@ struct dfa
static void dfamust (struct dfa *dfa);
static void regexp (void);
-/* These two macros are identical to the ones in gnulib's xalloc.h,
- except that they do not cast the result to "(t *)", and thus may
- be used via type-free CALLOC and MALLOC macros. */
-#undef XNMALLOC
-#undef XCALLOC
-
-/* Allocate memory for N elements of type T, with error checking. */
-/* extern t *XNMALLOC (size_t n, typename t); */
-# define XNMALLOC(n, t) \
- (sizeof (t) == 1 ? xmalloc (n) : xnmalloc (n, sizeof (t)))
-
-/* Allocate memory for N elements of type T, with error checking,
- and zero it. */
-/* extern t *XCALLOC (size_t n, typename t); */
-# define XCALLOC(n, t) \
- (sizeof (t) == 1 ? xzalloc (n) : xcalloc (n, sizeof (t)))
-
-#define CALLOC(p, n) do { (p) = XCALLOC (n, *(p)); } while (0)
-#define MALLOC(p, n) do { (p) = XNMALLOC (n, *(p)); } while (0)
-#define REALLOC(p, n) do {(p) = xnrealloc (p, n, sizeof (*(p))); } while (0)
-
-/* Reallocate an array of type *P if N_ALLOC is <= N_REQUIRED. */
-#define REALLOC_IF_NECESSARY(p, n_alloc, n_required) \
- do \
- { \
- if ((n_alloc) <= (n_required)) \
- { \
- size_t new_n_alloc = (n_required) + !(p); \
- (p) = x2nrealloc (p, &new_n_alloc, sizeof (*(p))); \
- (n_alloc) = new_n_alloc; \
- } \
- } \
- while (false)
-
static void
dfambcache (struct dfa *d)
{
@@ -682,7 +653,9 @@ charclass_index (charclass const s)
for (i = 0; i < dfa->cindex; ++i)
if (equal (s, dfa->charclasses[i]))
return i;
- REALLOC_IF_NECESSARY (dfa->charclasses, dfa->calloc, dfa->cindex + 1);
+ if (dfa->cindex == dfa->calloc)
+ dfa->charclasses = x2nrealloc (dfa->charclasses, &dfa->calloc,
+ sizeof *dfa->charclasses);
++dfa->cindex;
copyset (s, dfa->charclasses[i]);
return i;
@@ -1050,16 +1023,16 @@ parse_bracket_exp (void)
/* Work area to build a mb_char_classes. */
struct mb_char_classes *work_mbc;
- size_t chars_al, range_sts_al, range_ends_al, ch_classes_al,
- equivs_al, coll_elems_al;
+ size_t chars_al, ranges_al, ch_classes_al, equivs_al, coll_elems_al;
chars_al = 0;
- range_sts_al = range_ends_al = 0;
+ ranges_al = 0;
ch_classes_al = equivs_al = coll_elems_al = 0;
if (MB_CUR_MAX > 1)
{
- REALLOC_IF_NECESSARY (dfa->mbcsets, dfa->mbcsets_alloc,
- dfa->nmbcsets + 1);
+ if (dfa->nmbcsets == dfa->mbcsets_alloc)
+ dfa->mbcsets = x2nrealloc (dfa->mbcsets, &dfa->mbcsets_alloc,
+ sizeof *dfa->mbcsets);
/* dfa->multibyte_prop[] hold the index of dfa->mbcsets.
We will update dfa->multibyte_prop[] in addtok, because we can't
@@ -1136,9 +1109,11 @@ parse_bracket_exp (void)
/* Store the character class as wctype_t. */
wctype_t wt = wctype (class);
- REALLOC_IF_NECESSARY (work_mbc->ch_classes,
- ch_classes_al,
- work_mbc->nch_classes + 1);
+ if (work_mbc->nch_classes == ch_classes_al)
+ work_mbc->ch_classes
+ = x2nrealloc (work_mbc->ch_classes,
+ &ch_classes_al,
+ sizeof *work_mbc->ch_classes);
work_mbc->ch_classes[work_mbc->nch_classes++] = wt;
}
@@ -1191,23 +1166,24 @@ parse_bracket_exp (void)
to the pair of ranges, [m-z] [M-Z]. Although this code
is wrong in multiple ways, it's never used in practice.
FIXME: Remove this (and related) unused code. */
- REALLOC_IF_NECESSARY (work_mbc->range_sts,
- range_sts_al, work_mbc->nranges + 1);
- REALLOC_IF_NECESSARY (work_mbc->range_ends,
- range_ends_al, work_mbc->nranges + 1);
- work_mbc->range_sts[work_mbc->nranges] =
- case_fold ? towlower (wc) : (wchar_t) wc;
- work_mbc->range_ends[work_mbc->nranges++] =
- case_fold ? towlower (wc2) : (wchar_t) wc2;
+ if (ranges_al - work_mbc->nranges <= 1)
+ work_mbc->ranges = x2nrealloc (work_mbc->ranges,
+ &ranges_al,
+ sizeof *work_mbc->ranges);
+ work_mbc->ranges[work_mbc->nranges].beg
+ = case_fold ? towlower (wc) : wc;
+ work_mbc->ranges[work_mbc->nranges].end
+ = case_fold ? towlower (wc2) : wc2;
+ work_mbc->nranges++;
if (case_fold && (iswalpha (wc) || iswalpha (wc2)))
{
- REALLOC_IF_NECESSARY (work_mbc->range_sts,
- range_sts_al, work_mbc->nranges +
1);
- work_mbc->range_sts[work_mbc->nranges] = towupper (wc);
- REALLOC_IF_NECESSARY (work_mbc->range_ends,
- range_ends_al, work_mbc->nranges +
1);
- work_mbc->range_ends[work_mbc->nranges++] = towupper
(wc2);
+ work_mbc->ranges = x2nrealloc (work_mbc->ranges,
+ &ranges_al,
+ sizeof *work_mbc->ranges);
+ work_mbc->ranges[work_mbc->nranges].beg = towupper (wc);
+ work_mbc->ranges[work_mbc->nranges].end = towupper (wc2);
+ work_mbc->nranges++;
}
}
else if (using_simple_locale ())
@@ -1255,16 +1231,20 @@ parse_bracket_exp (void)
{
wchar_t folded[CASE_FOLDED_BUFSIZE];
int i, n = case_folded_counterparts (wc, folded);
- REALLOC_IF_NECESSARY (work_mbc->chars, chars_al,
- work_mbc->nchars + n);
for (i = 0; i < n; i++)
if (!setbit_wc (folded[i], ccl))
- work_mbc->chars[work_mbc->nchars++] = folded[i];
+ {
+ if (work_mbc->nchars == chars_al)
+ work_mbc->chars = x2nrealloc (work_mbc->chars, &chars_al,
+ sizeof *work_mbc->chars);
+ work_mbc->chars[work_mbc->nchars++] = folded[i];
+ }
}
if (!setbit_wc (wc, ccl))
{
- REALLOC_IF_NECESSARY (work_mbc->chars, chars_al,
- work_mbc->nchars + 1);
+ if (work_mbc->nchars == chars_al)
+ work_mbc->chars = x2nrealloc (work_mbc->chars, &chars_al,
+ sizeof *work_mbc->chars);
work_mbc->chars[work_mbc->nchars++] = wc;
}
}
@@ -1629,15 +1609,17 @@ static size_t depth; /* Current depth of a
hypothetical stack
static void
addtok_mb (token t, int mbprop)
{
- if (MB_CUR_MAX > 1)
+ if (dfa->tindex == dfa->talloc)
{
- REALLOC_IF_NECESSARY (dfa->multibyte_prop, dfa->nmultibyte_prop,
- dfa->tindex + 1);
- dfa->multibyte_prop[dfa->tindex] = mbprop;
+ dfa->tokens = x2nrealloc (dfa->tokens, &dfa->talloc, sizeof
*dfa->tokens);
+ if (MB_CUR_MAX > 1)
+ dfa->multibyte_prop = xnrealloc (dfa->multibyte_prop, dfa->talloc,
+ sizeof *dfa->multibyte_prop);
}
-
- REALLOC_IF_NECESSARY (dfa->tokens, dfa->talloc, dfa->tindex + 1);
- dfa->tokens[dfa->tindex++] = t;
+ dfa->tokens[dfa->tindex] = t;
+ if (MB_CUR_MAX > 1)
+ dfa->multibyte_prop[dfa->tindex] = mbprop;
+ dfa->tindex++;
switch (t)
{
@@ -2038,19 +2020,24 @@ dfaparse (char const *s, size_t len, struct dfa *d)
/* Some primitives for operating on sets of positions. */
-/* Copy one set to another; the destination must be large enough. */
+/* Copy one set to another. */
static void
copy (position_set const *src, position_set * dst)
{
- REALLOC_IF_NECESSARY (dst->elems, dst->alloc, src->nelem);
- memcpy (dst->elems, src->elems, sizeof (dst->elems[0]) * src->nelem);
+ if (dst->alloc < src->nelem)
+ {
+ free (dst->elems);
+ dst->alloc = src->alloc;
+ dst->elems = xnmalloc (dst->alloc, sizeof *dst->elems);
+ }
+ memcpy (dst->elems, src->elems, src->nelem * sizeof *dst->elems);
dst->nelem = src->nelem;
}
static void
alloc_position_set (position_set * s, size_t size)
{
- MALLOC (s->elems, size);
+ s->elems = xnmalloc (size, sizeof *s->elems);
s->alloc = size;
s->nelem = 0;
}
@@ -2080,7 +2067,8 @@ insert (position p, position_set * s)
return;
}
- REALLOC_IF_NECESSARY (s->elems, s->alloc, count + 1);
+ if (count == s->alloc)
+ s->elems = x2nrealloc (s->elems, &s->alloc, sizeof *s->elems);
for (i = count; i > lo; i--)
s->elems[i] = s->elems[i - 1];
s->elems[lo] = p;
@@ -2094,7 +2082,12 @@ merge (position_set const *s1, position_set const *s2,
position_set * m)
{
size_t i = 0, j = 0;
- REALLOC_IF_NECESSARY (m->elems, m->alloc, s1->nelem + s2->nelem);
+ if (m->alloc < s1->nelem + s2->nelem)
+ {
+ free (m->elems);
+ m->alloc = s1->alloc + s2->alloc;
+ m->elems = xnmalloc (m->alloc, sizeof *m->elems);
+ }
m->nelem = 0;
while (i < s1->nelem && j < s2->nelem)
if (s1->elems[i].index > s2->elems[j].index)
@@ -2155,7 +2148,8 @@ state_index (struct dfa *d, position_set const *s, int
context)
}
/* We'll have to create a new state. */
- REALLOC_IF_NECESSARY (d->states, d->salloc, d->sindex + 1);
+ if (d->sindex == d->salloc)
+ d->states = x2nrealloc (d->states, &d->salloc, sizeof *d->states);
d->states[i].hash = hash;
alloc_position_set (&d->states[i].elems, s->nelem);
copy (s, &d->states[i].elems);
@@ -2197,10 +2191,10 @@ static void
epsclosure (position_set * s, struct dfa const *d)
{
size_t i, j;
- char *visited; /* Array of booleans, enough to use char, not int. */
position p, old;
- CALLOC (visited, d->tindex);
+ /* Array of booleans, large enough to use char, not int. */
+ char *visited = xzalloc (d->tindex);
for (i = 0; i < s->nelem; ++i)
if (d->tokens[s->elems[i].index] >= NOTCHAR
@@ -2383,19 +2377,19 @@ dfaanalyze (struct dfa *d, int searchflag)
d->searchflag = searchflag;
- MALLOC (nullable, d->depth);
+ nullable = xnmalloc (d->depth, sizeof *nullable);
o_nullable = nullable;
- MALLOC (nfirstpos, d->depth);
+ nfirstpos = xnmalloc (d->depth, sizeof *nfirstpos);
o_nfirst = nfirstpos;
- MALLOC (firstpos, d->nleaves);
+ firstpos = xnmalloc (d->nleaves, sizeof *firstpos);
o_firstpos = firstpos, firstpos += d->nleaves;
- MALLOC (nlastpos, d->depth);
+ nlastpos = xnmalloc (d->depth, sizeof *nlastpos);
o_nlast = nlastpos;
- MALLOC (lastpos, d->nleaves);
+ lastpos = xnmalloc (d->nleaves, sizeof *lastpos);
o_lastpos = lastpos, lastpos += d->nleaves;
alloc_position_set (&merged, d->nleaves);
- CALLOC (d->follows, d->tindex);
+ d->follows = xcalloc (d->tindex, sizeof *d->follows);
for (i = 0; i < d->tindex; ++i)
{
@@ -2556,7 +2550,7 @@ dfaanalyze (struct dfa *d, int searchflag)
/* Build the initial state. */
d->salloc = 1;
d->sindex = 0;
- MALLOC (d->states, d->salloc);
+ d->states = xnmalloc (d->salloc, sizeof *d->states);
separate_contexts = state_separate_contexts (&merged);
state_index (d, &merged,
@@ -2605,8 +2599,8 @@ dfaanalyze (struct dfa *d, int searchflag)
void
dfastate (state_num s, struct dfa *d, state_num trans[])
{
- leaf_set *grps; /* As many as will ever be needed. */
- charclass *labels; /* Labels corresponding to the groups. */
+ leaf_set grps[NOTCHAR]; /* As many as will ever be needed. */
+ charclass labels[NOTCHAR]; /* Labels corresponding to the groups. */
size_t ngrps = 0; /* Number of groups actually used. */
position pos; /* Current position being considered. */
charclass matches; /* Set of matching characters. */
@@ -2625,9 +2619,6 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
int next_isnt_1st_byte = 0; /* Flag if we can't add state0. */
size_t i, j, k;
- MALLOC (grps, NOTCHAR);
- MALLOC (labels, NOTCHAR);
-
zeroset (matches);
for (i = 0; i < d->states[s].elems.nelem; ++i)
@@ -2710,7 +2701,8 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
{
copyset (leftovers, labels[ngrps]);
copyset (intersect, labels[j]);
- MALLOC (grps[ngrps].elems, d->nleaves);
+ grps[ngrps].elems = xnmalloc (d->nleaves,
+ sizeof *grps[ngrps].elems);
memcpy (grps[ngrps].elems, grps[j].elems,
sizeof (grps[j].elems[0]) * grps[j].nelem);
grps[ngrps].nelem = grps[j].nelem;
@@ -2733,7 +2725,7 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
{
copyset (matches, labels[ngrps]);
zeroset (matches);
- MALLOC (grps[ngrps].elems, d->nleaves);
+ grps[ngrps].elems = xnmalloc (d->nleaves, sizeof *grps[ngrps].elems);
grps[ngrps].nelem = 1;
grps[ngrps].elems[0] = pos.index;
++ngrps;
@@ -2855,22 +2847,40 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
free (grps[i].elems);
free (follows.elems);
free (tmp.elems);
- free (grps);
- free (labels);
+}
+
+static void
+realloc_trans_if_necessary (struct dfa *d, state_num new_state)
+{
+ /* Make sure that the trans and fail arrays are allocated large enough
+ to hold a pointer for the new state. */
+ if (d->tralloc <= new_state)
+ {
+ struct dfatab *tab_1 = d->tab - 1;
+ state_num oldalloc = d->tralloc + 1;
+ state_num newalloc;
+
+ d->tralloc = new_state + 1;
+ tab_1 = x2nrealloc (tab_1, &d->tralloc, sizeof *tab_1);
+ newalloc = d->tralloc--;
+ d->tab = tab_1 + 1;
+ for (; oldalloc < newalloc; oldalloc++)
+ tab_1[oldalloc].trans = tab_1[oldalloc].fails = NULL;
+ }
}
/* Some routines for manipulating a compiled dfa's transition tables.
Each state may or may not have a transition table; if it does, and it
- is a non-accepting state, then d->trans[state] points to its table.
- If it is an accepting state then d->fails[state] points to its table.
- If it has no table at all, then d->trans[state] is NULL.
+ is a non-accepting state, then d->tab[state].trans points to its table.
+ If it is an accepting state then d->tab[state].fails points to its table.
+ If it has no table at all, then d->tab[state].trans is NULL.
TODO: Improve this comment, get rid of the unnecessary redundancy. */
static void
build_state (state_num s, struct dfa *d)
{
state_num *trans; /* The new transition table. */
- state_num i;
+ state_num i, maxstate;
/* Set an upper limit on the number of transition tables that will ever
exist at once. 1024 is arbitrary. The idea is that the frequently
@@ -2880,9 +2890,9 @@ build_state (state_num s, struct dfa *d)
{
for (i = 0; i < d->tralloc; ++i)
{
- free (d->trans[i]);
- free (d->fails[i]);
- d->trans[i] = d->fails[i] = NULL;
+ free (d->tab[i].trans);
+ free (d->tab[i].fails);
+ d->tab[i].trans = d->tab[i].fails = NULL;
}
d->trcount = 0;
}
@@ -2890,60 +2900,49 @@ build_state (state_num s, struct dfa *d)
++d->trcount;
/* Set up the success bits for this state. */
- d->success[s] = 0;
+ d->tab[s].success = 0;
if (ACCEPTS_IN_CONTEXT (d->states[s].context, CTX_NEWLINE, s, *d))
- d->success[s] |= CTX_NEWLINE;
+ d->tab[s].success |= CTX_NEWLINE;
if (ACCEPTS_IN_CONTEXT (d->states[s].context, CTX_LETTER, s, *d))
- d->success[s] |= CTX_LETTER;
+ d->tab[s].success |= CTX_LETTER;
if (ACCEPTS_IN_CONTEXT (d->states[s].context, CTX_NONE, s, *d))
- d->success[s] |= CTX_NONE;
+ d->tab[s].success |= CTX_NONE;
- MALLOC (trans, NOTCHAR);
+ trans = xmalloc (NOTCHAR * sizeof *trans);
dfastate (s, d, trans);
/* Now go through the new transition table, and make sure that the trans
and fail arrays are allocated large enough to hold a pointer for the
largest state mentioned in the table. */
+ maxstate = -1;
for (i = 0; i < NOTCHAR; ++i)
- if (trans[i] >= d->tralloc)
- {
- state_num oldalloc = d->tralloc;
-
- while (trans[i] >= d->tralloc)
- d->tralloc *= 2;
- REALLOC (d->realtrans, d->tralloc + 1);
- d->trans = d->realtrans + 1;
- REALLOC (d->fails, d->tralloc);
- REALLOC (d->success, d->tralloc);
- REALLOC (d->newlines, d->tralloc);
- while (oldalloc < d->tralloc)
- {
- d->trans[oldalloc] = NULL;
- d->fails[oldalloc++] = NULL;
- }
- }
+ if (maxstate < trans[i])
+ maxstate = trans[i];
+ realloc_trans_if_necessary (d, maxstate);
/* Keep the newline transition in a special place so we can use it as
a sentinel. */
- d->newlines[s] = trans[eolbyte];
+ d->tab[s].newlines = trans[eolbyte];
trans[eolbyte] = -1;
if (ACCEPTING (s, *d))
- d->fails[s] = trans;
+ d->tab[s].fails = trans;
else
- d->trans[s] = trans;
+ d->tab[s].trans = trans;
}
static void
build_state_zero (struct dfa *d)
{
- d->tralloc = 1;
+ struct dfatab *tab_1;
+ size_t i, newalloc;
d->trcount = 0;
- CALLOC (d->realtrans, d->tralloc + 1);
- d->trans = d->realtrans + 1;
- CALLOC (d->fails, d->tralloc);
- MALLOC (d->success, d->tralloc);
- MALLOC (d->newlines, d->tralloc);
+ d->tralloc = 0;
+ tab_1 = x2nrealloc (NULL, &d->tralloc, sizeof *tab_1);
+ newalloc = d->tralloc--;
+ d->tab = tab_1 + 1;
+ for (i = 0; i < newalloc; i++)
+ tab_1[i].trans = tab_1[i].fails = NULL;
build_state (0, d);
}
@@ -2972,30 +2971,6 @@ build_state_zero (struct dfa *d)
} \
}
-static void
-realloc_trans_if_necessary (struct dfa *d, state_num new_state)
-{
- /* Make sure that the trans and fail arrays are allocated large enough
- to hold a pointer for the new state. */
- if (new_state >= d->tralloc)
- {
- state_num oldalloc = d->tralloc;
-
- while (new_state >= d->tralloc)
- d->tralloc *= 2;
- REALLOC (d->realtrans, d->tralloc + 1);
- d->trans = d->realtrans + 1;
- REALLOC (d->fails, d->tralloc);
- REALLOC (d->success, d->tralloc);
- REALLOC (d->newlines, d->tralloc);
- while (oldalloc < d->tralloc)
- {
- d->trans[oldalloc] = NULL;
- d->fails[oldalloc++] = NULL;
- }
- }
-}
-
/* Return values of transit_state_singlebyte, and
transit_state_consume_1char. */
typedef enum
@@ -3013,14 +2988,14 @@ static status_transit_state
transit_state_singlebyte (struct dfa *d, state_num s, unsigned char const *p,
state_num * next_state)
{
- state_num *t;
state_num works = s;
status_transit_state rval = TRANSIT_STATE_IN_PROGRESS;
while (rval == TRANSIT_STATE_IN_PROGRESS)
{
- if ((t = d->trans[works]) != NULL)
+ state_num *t = d->tab[works].trans;
+ if (t)
{
works = t[*p];
rval = TRANSIT_STATE_DONE;
@@ -3036,9 +3011,9 @@ transit_state_singlebyte (struct dfa *d, state_num s,
unsigned char const *p,
}
works = 0;
}
- else if (d->fails[works])
+ else if (d->tab[works].fails)
{
- works = d->fails[works][*p];
+ works = d->tab[works].fails[*p];
rval = TRANSIT_STATE_DONE;
}
else
@@ -3170,7 +3145,7 @@ match_mb_charset (struct dfa *d, state_num s, position
pos, size_t idx)
/* match with a range? */
for (i = 0; i < work_mbc->nranges; i++)
{
- if (work_mbc->range_sts[i] <= wc && wc <= work_mbc->range_ends[i])
+ if (work_mbc->ranges[i].beg <= wc && wc <= work_mbc->ranges[i].end)
goto charset_matched;
}
@@ -3199,9 +3174,8 @@ static int *
check_matching_with_multibyte_ops (struct dfa *d, state_num s, size_t idx)
{
size_t i;
- int *rarray;
+ int *rarray = xnmalloc (d->states[s].mbps.nelem, sizeof *rarray);
- MALLOC (rarray, d->states[s].mbps.nelem);
for (i = 0; i < d->states[s].mbps.nelem; ++i)
{
position pos = d->states[s].mbps.elems[i];
@@ -3410,8 +3384,8 @@ dfaexec (struct dfa *d, char const *begin, char *end,
{
state_num s, s1; /* Current state. */
unsigned char const *p; /* Current input character. */
- state_num **trans, *t; /* Copy of d->trans so it can be optimized
- into a register. */
+ struct dfatab *tab; /* Help the compiler. */
+ state_num *t;
unsigned char eol = eolbyte; /* Likewise for eolbyte. */
unsigned char saved_end;
@@ -3420,14 +3394,14 @@ dfaexec (struct dfa *d, char const *begin, char *end,
s = s1 = 0;
p = (unsigned char const *) begin;
- trans = d->trans;
+ tab = d->tab;
saved_end = *(unsigned char *) end;
*end = eol;
if (d->mb_cur_max > 1)
{
- MALLOC (mblen_buf, end - begin + 2);
- MALLOC (inputwcs, end - begin + 2);
+ mblen_buf = xnmalloc (end - begin + 2, sizeof *mblen_buf);
+ inputwcs = xnmalloc (end - begin + 2, sizeof *inputwcs);
memset (&mbs, 0, sizeof (mbstate_t));
prepare_wc_buf (d, (const char *) p, end);
}
@@ -3436,7 +3410,7 @@ dfaexec (struct dfa *d, char const *begin, char *end,
{
if (d->mb_cur_max > 1)
{
- while ((t = trans[s]) != NULL)
+ while ((t = tab[s].trans) != NULL)
{
if (p > buf_end)
break;
@@ -3465,15 +3439,15 @@ dfaexec (struct dfa *d, char const *begin, char *end,
/* Can match with a multibyte character (and multi character
collating element). Transition table might be updated. */
s = transit_state (d, s, &p);
- trans = d->trans;
+ tab = d->tab;
}
}
else
{
- while ((t = trans[s]) != NULL)
+ while ((t = tab[s].trans) != NULL)
{
s1 = t[*p++];
- if ((t = trans[s1]) == NULL)
+ if ((t = tab[s1].trans) == NULL)
{
state_num tmp = s;
s = s1;
@@ -3484,9 +3458,9 @@ dfaexec (struct dfa *d, char const *begin, char *end,
}
}
- if (s >= 0 && (char *) p <= end && d->fails[s])
+ if (s >= 0 && (char *) p <= end && d->tab[s].fails)
{
- if (d->success[s] & sbit[*p])
+ if (d->tab[s].success & sbit[*p])
{
if (backref)
*backref = (d->states[s].backref != 0);
@@ -3505,10 +3479,10 @@ dfaexec (struct dfa *d, char const *begin, char *end,
/* Can match with a multibyte character (and multicharacter
collating element). Transition table might be updated. */
s = transit_state (d, s, &p);
- trans = d->trans;
+ tab = d->tab;
}
else
- s = d->fails[s][*p++];
+ s = d->tab[s].fails[*p++];
continue;
}
@@ -3537,13 +3511,13 @@ dfaexec (struct dfa *d, char const *begin, char *end,
if (s >= 0)
{
build_state (s, d);
- trans = d->trans;
+ tab = d->tab;
continue;
}
if (p[-1] == eol && allow_nl)
{
- s = d->newlines[s1];
+ s = d->tab[s1].newlines;
continue;
}
@@ -3565,8 +3539,7 @@ free_mbdata (struct dfa *d)
struct mb_char_classes *p = &(d->mbcsets[i]);
free (p->chars);
free (p->ch_classes);
- free (p->range_sts);
- free (p->range_ends);
+ free (p->ranges);
for (j = 0; j < p->nequivs; ++j)
free (p->equivs[j]);
@@ -3588,22 +3561,7 @@ void
dfainit (struct dfa *d)
{
memset (d, 0, sizeof *d);
-
- d->calloc = 1;
- MALLOC (d->charclasses, d->calloc);
-
- d->talloc = 1;
- MALLOC (d->tokens, d->talloc);
-
d->mb_cur_max = MB_CUR_MAX;
-
- if (d->mb_cur_max > 1)
- {
- d->nmultibyte_prop = 1;
- MALLOC (d->multibyte_prop, d->nmultibyte_prop);
- d->mbcsets_alloc = 1;
- MALLOC (d->mbcsets, d->mbcsets_alloc);
- }
}
static void
@@ -3670,13 +3628,10 @@ dfafree (struct dfa *d)
free (d->follows);
for (i = 0; i < d->tralloc; ++i)
{
- free (d->trans[i]);
- free (d->fails[i]);
+ free (d->tab[i].trans);
+ free (d->tab[i].fails);
}
- free (d->realtrans);
- free (d->fails);
- free (d->newlines);
- free (d->success);
+ free (d->tab - 1);
for (dm = d->musts; dm; dm = ndm)
{
ndm = dm->next;
@@ -3849,7 +3804,7 @@ enlist (char **cpp, char *new, size_t len)
cpp[i] = NULL;
}
/* Add the new string. */
- REALLOC (cpp, i + 2);
+ cpp = xnrealloc (cpp, i + 2, sizeof *cpp);
cpp[i] = new;
cpp[i + 1] = NULL;
return cpp;
@@ -3982,7 +3937,7 @@ dfamust (struct dfa *d)
result = empty_string;
exact = 0;
- MALLOC (musts, d->tindex + 1);
+ musts = xnmalloc (d->tindex + 1, sizeof *musts);
mp = musts;
for (i = 0; i <= d->tindex; ++i)
mp[i] = must0;
@@ -4169,7 +4124,7 @@ dfamust (struct dfa *d)
done:
if (strlen (result))
{
- MALLOC (dm, 1);
+ dm = xmalloc (sizeof *dm);
dm->exact = exact;
dm->must = xmemdup (result, strlen (result) + 1);
dm->next = d->musts;
--
1.9.0
