Subject: bug#17136: [PATCH] dfa: speed up memory allocation, port to IRIX

From: Paul Eggert <[email-masked]>
Date: Fri, 28 Mar 2014 18:28:57 -0700

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-masked]>
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