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

From: [email-masked] (GNU bug Tracking System)
Date: Fri, 18 Apr 2014 06:00:06 +0000

Your bug report

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

which was filed against the grep package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
17136: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=17136
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#17136: [PATCH] dfa: speed up memory allocation, port to IRIX
From: Paul Eggert <[email-masked]>
To: [email-masked]
Date: Thu, 17 Apr 2014 22:59:17 -0700
List-Id: <debbugs-submit.debbugs.gnu.org>

I merged that patch into the grep trunk and am closing this bug report. 
  While merging, I removed one part of the patch that had a small but 
measurable performance degradation, namely, the introduction of struct 
dfatab.  I found some other minor simplifications and threw them in. 
There seems to be no significant change in CPU performance.  The patch's 
causes the dfa module's text size to shrink by 8% on my platform (x86-64 
Fedora 20), which I suppose is a small win, but the main point of the 
patch is simplifying the source.  I'm attaching what I installed, broken 
into 12 little patches to ease review.

From 6620b54ed3f485e6ae652df9c8b8a23c8f6311b5 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Tue, 15 Apr 2014 17:29:47 -0700
Subject: [PATCH 01/12] dfa: clarify memory allocation and port to IRIX

This change was prompted by a porting problem:
IRIX 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 the code a bit here it'll make other
simplifications easier.
* src/dfa.c (XNMALLOC, XCALLOC, CALLOC, MALLOC, REALLOC): Remove.
All uses replaced by xnmalloc etc.
(REALLOC_IF_NECESSARY): Remove; all uses replaced by ....
(maybe_realloc): New function.
(copy, merge): Free and allocate rather than realloc, as we
needn't save the contents.
---
 src/dfa.c | 211 ++++++++++++++++++++++++++++++++------------------------------
 1 file changed, 110 insertions(+), 101 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index 2b6c5d6..9e88742 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -457,40 +457,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)
 {
@@ -671,6 +637,19 @@ equal (charclass const s1, charclass const s2)
   return memcmp (s1, s2, sizeof (charclass)) == 0;
 }
 
+/* If needed, reallocate *PTR so that it holds at least NITEMS items.
+   The array holds *NALLOC items; *NALLOC is updated on reallocation.
+   ITEMSIZE is the size of one item.  Avoid O(N**2) behavior on arrays
+   growing linearly.  */
+static void *
+maybe_realloc (void *ptr, size_t nitems, size_t *nalloc, size_t itemsize)
+{
+  if (nitems < *nalloc)
+    return ptr;
+  *nalloc = nitems;
+  return x2nrealloc (ptr, nalloc, itemsize);
+}
+
 /* In DFA D, find the index of charclass S, or allocate a new one.  */
 static size_t
 dfa_charclass_index (struct dfa *d, charclass const s)
@@ -680,7 +659,8 @@ dfa_charclass_index (struct dfa *d, charclass const s)
   for (i = 0; i < d->cindex; ++i)
     if (equal (s, d->charclasses[i]))
       return i;
-  REALLOC_IF_NECESSARY (d->charclasses, d->calloc, d->cindex + 1);
+  d->charclasses = maybe_realloc (d->charclasses, d->cindex, &d->calloc,
+                                  sizeof *d->charclasses);
   ++d->cindex;
   copyset (s, d->charclasses[i]);
   return i;
@@ -1031,8 +1011,9 @@ parse_bracket_exp (void)
   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);
+      dfa->mbcsets = maybe_realloc (dfa->mbcsets, dfa->nmbcsets,
+                                    &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
@@ -1109,9 +1090,10 @@ 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);
+                      work_mbc->ch_classes
+                        = maybe_realloc (work_mbc->ch_classes,
+                                         work_mbc->nch_classes, &ch_classes_al,
+                                         sizeof *work_mbc->ch_classes);
                       work_mbc->ch_classes[work_mbc->nch_classes++] = wt;
                     }
 
@@ -1164,10 +1146,14 @@ 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
+                    = maybe_realloc (work_mbc->range_sts,
+                                     work_mbc->nranges, &range_sts_al,
+                                     sizeof *work_mbc->range_sts);
+                  work_mbc->range_ends
+                    = maybe_realloc (work_mbc->range_ends,
+                                     work_mbc->nranges, &range_ends_al,
+                                     sizeof *work_mbc->range_ends);
                   work_mbc->range_sts[work_mbc->nranges] =
                     case_fold ? towlower (wc) : (wchar_t) wc;
                   work_mbc->range_ends[work_mbc->nranges++] =
@@ -1175,11 +1161,15 @@ parse_bracket_exp (void)
 
                   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
+                        = maybe_realloc (work_mbc->range_sts,
+                                         work_mbc->nranges, &range_sts_al,
+                                         sizeof *work_mbc->range_sts);
                       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
+                        = maybe_realloc (work_mbc->range_ends,
+                                         work_mbc->nranges, &range_ends_al,
+                                         sizeof *work_mbc->range_ends);
                       work_mbc->range_ends[work_mbc->nranges++] = towupper (wc2);
                     }
                 }
@@ -1228,16 +1218,17 @@ 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);
+          work_mbc->chars = maybe_realloc (work_mbc->chars,
+                                           work_mbc->nchars + n, &chars_al,
+                                           sizeof *work_mbc->chars);
           for (i = 0; i < n; i++)
             if (!setbit_wc (folded[i], ccl))
               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);
+          work_mbc->chars = maybe_realloc (work_mbc->chars, work_mbc->nchars,
+                                           &chars_al, sizeof *work_mbc->chars);
           work_mbc->chars[work_mbc->nchars++] = wc;
         }
     }
@@ -1604,12 +1595,14 @@ addtok_mb (token t, int mbprop)
 {
   if (MB_CUR_MAX > 1)
     {
-      REALLOC_IF_NECESSARY (dfa->multibyte_prop, dfa->nmultibyte_prop,
-                            dfa->tindex + 1);
+      dfa->multibyte_prop = maybe_realloc (dfa->multibyte_prop, dfa->tindex,
+                                           &dfa->nmultibyte_prop,
+                                           sizeof *dfa->multibyte_prop);
       dfa->multibyte_prop[dfa->tindex] = mbprop;
     }
 
-  REALLOC_IF_NECESSARY (dfa->tokens, dfa->talloc, dfa->tindex + 1);
+  dfa->tokens = maybe_realloc (dfa->tokens, dfa->tindex, &dfa->talloc,
+                               sizeof *dfa->tokens);
   dfa->tokens[dfa->tindex++] = t;
 
   switch (t)
@@ -2000,19 +1993,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->nelem;
+      dst->elems = x2nrealloc (NULL, &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;
 }
@@ -2042,7 +2040,7 @@ insert (position p, position_set * s)
       return;
     }
 
-  REALLOC_IF_NECESSARY (s->elems, s->alloc, count + 1);
+  s->elems = maybe_realloc (s->elems, count, &s->alloc, sizeof *s->elems);
   for (i = count; i > lo; i--)
     s->elems[i] = s->elems[i - 1];
   s->elems[lo] = p;
@@ -2056,7 +2054,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->elems = maybe_realloc (NULL, s1->nelem + s2->nelem, &m->alloc,
+                                sizeof *m->elems);
+    }
   m->nelem = 0;
   while (i < s1->nelem && j < s2->nelem)
     if (s1->elems[i].index > s2->elems[j].index)
@@ -2117,7 +2120,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);
+  d->states = maybe_realloc (d->states, d->sindex, &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);
@@ -2158,10 +2162,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
@@ -2342,19 +2346,19 @@ dfaanalyze (struct dfa *d, int searchflag)
 
   d->searchflag = searchflag != 0;
 
-  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)
     {
@@ -2513,7 +2517,7 @@ dfaanalyze (struct dfa *d, int searchflag)
   /* Build the initial state.  */
   d->salloc = 1;
   d->sindex = 0;
-  MALLOC (d->states, d->salloc);
+  d->states = xmalloc (sizeof *d->states);
 
   separate_contexts = state_separate_contexts (&merged);
   state_index (d, &merged,
@@ -2582,8 +2586,8 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
   bool next_isnt_1st_byte = false; /* Flag if we can't add state0.  */
   size_t i, j, k;
 
-  MALLOC (grps, NOTCHAR);
-  MALLOC (labels, NOTCHAR);
+  grps = xnmalloc (NOTCHAR, sizeof *grps);
+  labels = xnmalloc (NOTCHAR, sizeof *labels);
 
   zeroset (matches);
 
@@ -2669,7 +2673,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;
@@ -2692,7 +2697,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;
@@ -2857,7 +2862,7 @@ build_state (state_num s, struct dfa *d)
   if (ACCEPTS_IN_CONTEXT (d->states[s].context, CTX_NONE, s, *d))
     d->success[s] |= CTX_NONE;
 
-  MALLOC (trans, NOTCHAR);
+  trans = xnmalloc (NOTCHAR, sizeof *trans);
   dfastate (s, d, trans);
 
   /* Now go through the new transition table, and make sure that the trans
@@ -2870,11 +2875,12 @@ build_state (state_num s, struct dfa *d)
 
         while (trans[i] >= d->tralloc)
           d->tralloc *= 2;
-        REALLOC (d->realtrans, d->tralloc + 1);
+        d->realtrans = xnrealloc (d->realtrans, d->tralloc + 1,
+                                  sizeof *d->realtrans);
         d->trans = d->realtrans + 1;
-        REALLOC (d->fails, d->tralloc);
-        REALLOC (d->success, d->tralloc);
-        REALLOC (d->newlines, d->tralloc);
+        d->fails = xnrealloc (d->fails, d->tralloc, sizeof *d->fails);
+        d->success = xnrealloc (d->success, d->tralloc, sizeof *d->success);
+        d->newlines = xnrealloc (d->newlines, d->tralloc, sizeof *d->newlines);
         while (oldalloc < d->tralloc)
           {
             d->trans[oldalloc] = NULL;
@@ -2898,11 +2904,11 @@ build_state_zero (struct dfa *d)
 {
   d->tralloc = 1;
   d->trcount = 0;
-  CALLOC (d->realtrans, d->tralloc + 1);
+  d->realtrans = xcalloc (d->tralloc + 1, sizeof *d->realtrans);
   d->trans = d->realtrans + 1;
-  CALLOC (d->fails, d->tralloc);
-  MALLOC (d->success, d->tralloc);
-  MALLOC (d->newlines, d->tralloc);
+  d->fails = xcalloc (d->tralloc, sizeof *d->fails);
+  d->success = xnmalloc (d->tralloc, sizeof *d->success);
+  d->newlines = xnmalloc (d->tralloc, sizeof *d->newlines);
   build_state (0, d);
 }
 
@@ -2940,11 +2946,12 @@ realloc_trans_if_necessary (struct dfa *d, state_num new_state)
 
       while (new_state >= d->tralloc)
         d->tralloc *= 2;
-      REALLOC (d->realtrans, d->tralloc + 1);
+      d->realtrans = xnrealloc (d->realtrans, d->tralloc + 1,
+                                sizeof *d->realtrans);
       d->trans = d->realtrans + 1;
-      REALLOC (d->fails, d->tralloc);
-      REALLOC (d->success, d->tralloc);
-      REALLOC (d->newlines, d->tralloc);
+      d->fails = xnrealloc (d->fails, d->tralloc, sizeof *d->fails);
+      d->success = xnrealloc (d->success, d->tralloc, sizeof *d->success);
+      d->newlines = xnrealloc (d->newlines, d->tralloc, sizeof *d->newlines);
       while (oldalloc < d->tralloc)
         {
           d->trans[oldalloc] = NULL;
@@ -3377,14 +3384,16 @@ dfaexec (struct dfa *d, char const *begin, char *end,
   if (d->mb_cur_max > 1)
     {
       static bool mb_alloc = false;
-      REALLOC_IF_NECESSARY (d->mblen_buf, d->nmblen_buf, end - begin + 2);
-      REALLOC_IF_NECESSARY (d->inputwcs, d->ninputwcs, end - begin + 2);
+      d->mblen_buf = maybe_realloc (d->mblen_buf, end - begin + 2,
+                                    &d->nmblen_buf, sizeof *d->mblen_buf);
+      d->inputwcs = maybe_realloc (d->inputwcs, end - begin + 2,
+                                   &d->ninputwcs, sizeof *d->inputwcs);
       memset (&mbs, 0, sizeof (mbstate_t));
       prepare_wc_buf (d, (const char *) p, end);
       if (!mb_alloc)
         {
-          MALLOC (d->mb_match_lens, d->nleaves);
-          MALLOC (d->mb_follows, 1);
+          d->mb_match_lens = xnmalloc (d->nleaves, sizeof *d->mb_match_lens);
+          d->mb_follows = xmalloc (sizeof *d->mb_follows);
           alloc_position_set (d->mb_follows, d->nleaves);
           mb_alloc = true;
         }
@@ -3566,19 +3575,19 @@ dfainit (struct dfa *d)
   memset (d, 0, sizeof *d);
 
   d->calloc = 1;
-  MALLOC (d->charclasses, d->calloc);
+  d->charclasses = xmalloc (sizeof *d->charclasses);
 
   d->talloc = 1;
-  MALLOC (d->tokens, d->talloc);
+  d->tokens = xmalloc (sizeof *d->tokens);
 
   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->multibyte_prop = xmalloc (sizeof *d->multibyte_prop);
       d->mbcsets_alloc = 1;
-      MALLOC (d->mbcsets, d->mbcsets_alloc);
+      d->mbcsets = xmalloc (sizeof *d->mbcsets);
     }
 }
 
@@ -3633,12 +3642,12 @@ dfasuperset (struct dfa *d)
   sup->newlines = NULL;
   sup->musts = NULL;
 
-  MALLOC (sup->charclasses, sup->calloc);
+  sup->charclasses = xnmalloc (sup->calloc, sizeof *sup->charclasses);
   memcpy (sup->charclasses, d->charclasses,
           d->cindex * sizeof *sup->charclasses);
 
   sup->talloc = d->tindex * 2;
-  MALLOC (sup->tokens, sup->talloc);
+  sup->tokens = xnmalloc (sup->talloc, sizeof *sup->tokens);
 
   for (i = j = 0; i < d->tindex; i++)
     {
@@ -3910,7 +3919,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;
@@ -4042,7 +4051,7 @@ dfamust (struct dfa *d)
 
   result = empty_string;
   exact = false;
-  MALLOC (musts, d->tindex + 1);
+  musts = xnmalloc (d->tindex + 1, sizeof *musts);
   mp = musts;
   for (i = 0; i <= d->tindex; ++i)
     mp[i] = must0;
@@ -4246,7 +4255,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

From e6f95e891ac3cfc8f4e28d6fd6b777bc61abe35c Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Tue, 15 Apr 2014 17:50:06 -0700
Subject: [PATCH 02/12] dfa: avoid unnecessary work and other initialization

* src/dfa.c (dfaanalyze, dfainit):
Don't bother allocating when x2nrealloc will do it for us.
(dfastate): Allocate grps and labels on the stack, as their
size is known at compile time.
(build_state): Use xmalloc, not xnmalloc, since the multiplication
can be done at compile-time.
---
 src/dfa.c | 30 +++---------------------------
 1 file changed, 3 insertions(+), 27 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index 9e88742..caf9b07 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -2515,10 +2515,6 @@ dfaanalyze (struct dfa *d, int searchflag)
   epsclosure (&merged, d);
 
   /* Build the initial state.  */
-  d->salloc = 1;
-  d->sindex = 0;
-  d->states = xmalloc (sizeof *d->states);
-
   separate_contexts = state_separate_contexts (&merged);
   state_index (d, &merged,
                (separate_contexts & CTX_NEWLINE
@@ -2566,8 +2562,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.  */
@@ -2586,9 +2582,6 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
   bool next_isnt_1st_byte = false; /* Flag if we can't add state0.  */
   size_t i, j, k;
 
-  grps = xnmalloc (NOTCHAR, sizeof *grps);
-  labels = xnmalloc (NOTCHAR, sizeof *labels);
-
   zeroset (matches);
 
   for (i = 0; i < d->states[s].elems.nelem; ++i)
@@ -2819,8 +2812,6 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
     free (grps[i].elems);
   free (follows.elems);
   free (tmp.elems);
-  free (grps);
-  free (labels);
 }
 
 /* Some routines for manipulating a compiled dfa's transition tables.
@@ -2862,7 +2853,7 @@ build_state (state_num s, struct dfa *d)
   if (ACCEPTS_IN_CONTEXT (d->states[s].context, CTX_NONE, s, *d))
     d->success[s] |= CTX_NONE;
 
-  trans = xnmalloc (NOTCHAR, sizeof *trans);
+  trans = xmalloc (NOTCHAR * sizeof *trans);
   dfastate (s, d, trans);
 
   /* Now go through the new transition table, and make sure that the trans
@@ -3573,22 +3564,7 @@ void
 dfainit (struct dfa *d)
 {
   memset (d, 0, sizeof *d);
-
-  d->calloc = 1;
-  d->charclasses = xmalloc (sizeof *d->charclasses);
-
-  d->talloc = 1;
-  d->tokens = xmalloc (sizeof *d->tokens);
-
   d->mb_cur_max = MB_CUR_MAX;
-
-  if (d->mb_cur_max > 1)
-    {
-      d->nmultibyte_prop = 1;
-      d->multibyte_prop = xmalloc (sizeof *d->multibyte_prop);
-      d->mbcsets_alloc = 1;
-      d->mbcsets = xmalloc (sizeof *d->mbcsets);
-    }
 }
 
 static void
-- 
1.9.0

From f7dc5b515c33947cb4cae4c7ad21b9258caa2f12 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Tue, 15 Apr 2014 17:51:25 -0700
Subject: [PATCH 03/12] dfa: better size-overflow check

* src/dfa.c (dfasuperset): Let xnmalloc do the multiplication,
to check for size arithmetic overflow better.
---
 src/dfa.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/dfa.c b/src/dfa.c
index caf9b07..c816774 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3622,8 +3622,8 @@ dfasuperset (struct dfa *d)
   memcpy (sup->charclasses, d->charclasses,
           d->cindex * sizeof *sup->charclasses);
 
+  sup->tokens = xnmalloc (d->tindex, 2 * sizeof *sup->tokens);
   sup->talloc = d->tindex * 2;
-  sup->tokens = xnmalloc (sup->talloc, sizeof *sup->tokens);
 
   for (i = j = 0; i < d->tindex; i++)
     {
-- 
1.9.0

From d43285e6be77fc8210caf553f3b2f4b64b5ec193 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Tue, 15 Apr 2014 19:04:40 -0700
Subject: [PATCH 04/12] dfa: simplify transition table allocation

* src/dfa.c (struct dfa): Remove member 'realtrans', as it can
be computed from 'trans'.  All uses changed.
(realloc_trans_if_necessary): Move earlier, to avoid a forward decl.
Use x2nrealloc to compute new size, rather than doing it by hand,
which omits a check for unlikely overflow.
(realloc_trans_if_necessary, dfafree): Adjust to the fact that
d->trans now might be either NULL, or 1 + the pointer to free.
(build_state, build_state_zero): Use realloc_trans_if_necessary
instead of duplicating its code.
---
 src/dfa.c | 117 +++++++++++++++++++++++++++++---------------------------------
 1 file changed, 54 insertions(+), 63 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index c816774..c47f3e0 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -396,16 +396,16 @@ struct dfa
 
   /* Fields filled by dfaexec.  */
   state_num tralloc;            /* Number of transition tables that have
-                                   slots so far.  */
+                                   slots so far, not counting trans[-1].  */
   int trcount;                  /* Number of transition tables that have
                                    actually been built.  */
   state_num **trans;            /* Transition tables 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.  */
+                                   this table is NULL.  This points to one
+                                   past the start of the allocated array,
+                                   and trans[-1] is always NULL.  */
   state_num **fails;            /* Transition tables after failing to accept
                                    on a state that potentially could do so.  */
   int *success;                 /* Table of acceptance conditions used in
@@ -2814,6 +2814,30 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
   free (tmp.elems);
 }
 
+/* Make sure D's state arrays are large enough to hold NEW_STATE.  */
+static void
+realloc_trans_if_necessary (struct dfa *d, state_num new_state)
+{
+  if (d->tralloc <= new_state)
+    {
+      state_num **realtrans = d->trans ? d->trans - 1 : NULL;
+      state_num oldalloc = d->tralloc;
+      d->tralloc = new_state + 1;
+      realtrans = x2nrealloc (realtrans, &d->tralloc, sizeof *realtrans);
+      realtrans[0] = NULL;
+      d->trans = realtrans + 1;
+      d->tralloc--;
+      d->fails = xnrealloc (d->fails, d->tralloc, sizeof *d->fails);
+      d->success = xnrealloc (d->success, d->tralloc, sizeof *d->success);
+      d->newlines = xnrealloc (d->newlines, d->tralloc, sizeof *d->newlines);
+      for (; oldalloc < d->tralloc; oldalloc++)
+        {
+          d->trans[oldalloc] = NULL;
+          d->fails[oldalloc] = 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.
@@ -2825,7 +2849,7 @@ 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
@@ -2859,25 +2883,11 @@ build_state (state_num s, struct dfa *d)
   /* 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;
-        d->realtrans = xnrealloc (d->realtrans, d->tralloc + 1,
-                                  sizeof *d->realtrans);
-        d->trans = d->realtrans + 1;
-        d->fails = xnrealloc (d->fails, d->tralloc, sizeof *d->fails);
-        d->success = xnrealloc (d->success, d->tralloc, sizeof *d->success);
-        d->newlines = xnrealloc (d->newlines, d->tralloc, sizeof *d->newlines);
-        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.  */
@@ -2893,13 +2903,16 @@ build_state (state_num s, struct dfa *d)
 static void
 build_state_zero (struct dfa *d)
 {
-  d->tralloc = 1;
+  /* Initial size of the transition tables; must be positive.  */
+  int initial_tab_size = 1;
+
+  d->tralloc = 0;
   d->trcount = 0;
-  d->realtrans = xcalloc (d->tralloc + 1, sizeof *d->realtrans);
-  d->trans = d->realtrans + 1;
-  d->fails = xcalloc (d->tralloc, sizeof *d->fails);
-  d->success = xnmalloc (d->tralloc, sizeof *d->success);
-  d->newlines = xnmalloc (d->tralloc, sizeof *d->newlines);
+  d->trans = NULL;
+  d->fails = NULL;
+  d->success = NULL;
+  d->newlines = NULL;
+  realloc_trans_if_necessary (d, initial_tab_size);
   build_state (0, d);
 }
 
@@ -2926,31 +2939,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;
-      d->realtrans = xnrealloc (d->realtrans, d->tralloc + 1,
-                                sizeof *d->realtrans);
-      d->trans = d->realtrans + 1;
-      d->fails = xnrealloc (d->fails, d->tralloc, sizeof *d->fails);
-      d->success = xnrealloc (d->success, d->tralloc, sizeof *d->success);
-      d->newlines = xnrealloc (d->newlines, d->tralloc, sizeof *d->newlines);
-      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
@@ -3612,7 +3600,7 @@ dfasuperset (struct dfa *d)
   sup->sindex = 0;
   sup->follows = NULL;
   sup->tralloc = 0;
-  sup->realtrans = NULL;
+  sup->trans = NULL;
   sup->fails = NULL;
   sup->success = NULL;
   sup->newlines = NULL;
@@ -3709,16 +3697,19 @@ dfafree (struct dfa *d)
       free (d->follows);
     }
 
-  for (i = 0; i < d->tralloc; ++i)
+  if (d->trans)
     {
-      free (d->trans[i]);
-      free (d->fails[i]);
-    }
+      for (i = 0; i < d->tralloc; ++i)
+        {
+          free (d->trans[i]);
+          free (d->fails[i]);
+        }
 
-  free (d->realtrans);
-  free (d->fails);
-  free (d->newlines);
-  free (d->success);
+      free (d->trans - 1);
+      free (d->fails);
+      free (d->newlines);
+      free (d->success);
+    }
 
   for (dm = d->musts; dm; dm = ndm)
     {
-- 
1.9.0

From 93bdff061bb6192ddd9f89b90ac15797a9ce1ed4 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Tue, 15 Apr 2014 19:20:21 -0700
Subject: [PATCH 05/12] dfa: simplify range char allocation

* src/dfa.c (struct dfa): Simplify by allocating one array of ranges
rather than one for range starts and another for range ends.
All uses changed.
---
 src/dfa.c | 51 +++++++++++++++++++--------------------------------
 1 file changed, 19 insertions(+), 32 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index c47f3e0..a3e8bd0 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -307,8 +307,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;
@@ -1003,12 +1006,9 @@ 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;
-  ch_classes_al = equivs_al = coll_elems_al = 0;
+  chars_al = ranges_al = ch_classes_al = equivs_al = coll_elems_al = 0;
   if (MB_CUR_MAX > 1)
     {
       dfa->mbcsets = maybe_realloc (dfa->mbcsets, dfa->nmbcsets,
@@ -1146,31 +1146,19 @@ 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.  */
-                  work_mbc->range_sts
-                    = maybe_realloc (work_mbc->range_sts,
-                                     work_mbc->nranges, &range_sts_al,
-                                     sizeof *work_mbc->range_sts);
-                  work_mbc->range_ends
-                    = maybe_realloc (work_mbc->range_ends,
-                                     work_mbc->nranges, &range_ends_al,
-                                     sizeof *work_mbc->range_ends);
-                  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;
+                  work_mbc->ranges
+                    = maybe_realloc (work_mbc->ranges, work_mbc->nranges + 1,
+                                     &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;
 
                   if (case_fold && (iswalpha (wc) || iswalpha (wc2)))
                     {
-                      work_mbc->range_sts
-                        = maybe_realloc (work_mbc->range_sts,
-                                         work_mbc->nranges, &range_sts_al,
-                                         sizeof *work_mbc->range_sts);
-                      work_mbc->range_sts[work_mbc->nranges] = towupper (wc);
-                      work_mbc->range_ends
-                        = maybe_realloc (work_mbc->range_ends,
-                                         work_mbc->nranges, &range_ends_al,
-                                         sizeof *work_mbc->range_ends);
-                      work_mbc->range_ends[work_mbc->nranges++] = towupper (wc2);
+                      work_mbc->ranges[work_mbc->nranges].beg = towupper (wc);
+                      work_mbc->ranges[work_mbc->nranges++].end
+                        = towupper (wc2);
                     }
                 }
               else if (using_simple_locale ())
@@ -3113,7 +3101,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;
     }
 
@@ -3520,8 +3508,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]);
-- 
1.9.0

From ed7a8821e38d5a5fdd64f0f5cfca6cf89e331ca1 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Tue, 15 Apr 2014 22:59:25 -0700
Subject: [PATCH 06/12] dfa: simplify multibyte_prop allocation

* src/dfa.c (struct dfa): Simplify by removing nmultibyte_prop;
it should always be the same as talloc.  All uses changed.
---
 src/dfa.c | 17 ++++++++---------
 1 file changed, 8 insertions(+), 9 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index a3e8bd0..050a180 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -359,7 +359,6 @@ struct dfa
      multibyte_prop
      = 3     , 1               ,  0              ,  2              , 3
    */
-  size_t nmultibyte_prop;
   int *multibyte_prop;
 
   /* A table indexed by byte values that contains the corresponding wide
@@ -1581,16 +1580,16 @@ 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->talloc == dfa->tindex)
     {
-      dfa->multibyte_prop = maybe_realloc (dfa->multibyte_prop, dfa->tindex,
-                                           &dfa->nmultibyte_prop,
-                                           sizeof *dfa->multibyte_prop);
-      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);
     }
-
-  dfa->tokens = maybe_realloc (dfa->tokens, dfa->tindex, &dfa->talloc,
-                               sizeof *dfa->tokens);
+  if (MB_CUR_MAX > 1)
+    dfa->multibyte_prop[dfa->tindex] = mbprop;
   dfa->tokens[dfa->tindex++] = t;
 
   switch (t)
-- 
1.9.0

From f7e9200bcf5f1a021637e17225f7e69bf0b9c405 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Thu, 17 Apr 2014 17:50:55 -0700
Subject: [PATCH 07/12] dfa: simplify position set and element count allocation

* src/dfa.c (dfaanalyze): Allocation position set info all at one go,
and similarly for element count info.
---
 src/dfa.c | 110 +++++++++++++++++++++++++++++---------------------------------
 1 file changed, 52 insertions(+), 58 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index 050a180..4b0e7f2 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -2307,17 +2307,26 @@ state_separate_contexts (position_set const *s)
 void
 dfaanalyze (struct dfa *d, int searchflag)
 {
-  bool *nullable;               /* Nullable stack.  */
-  size_t *nfirstpos;            /* Element count stack for firstpos sets.  */
-  position *firstpos;           /* Array where firstpos elements are stored.  */
-  size_t *nlastpos;             /* Element count stack for lastpos sets.  */
-  position *lastpos;            /* Array where lastpos elements are stored.  */
+  /* Array allocated to hold position sets.  */
+  position *posalloc = xnmalloc (d->nleaves, 2 * sizeof *posalloc);
+  /* Firstpos and lastpos elements.  */
+  position *firstpos = posalloc + d->nleaves;
+  position *lastpos = firstpos + d->nleaves;
+
+  /* Stack for element counts and nullable flags.  */
+  struct
+  {
+    /* Whether the entry is nullable.  */
+    bool nullable;
+
+    /* Counts of firstpos and lastpos sets.  */
+    size_t nfirstpos;
+    size_t nlastpos;
+  } *stkalloc = xnmalloc (d->depth, sizeof *stkalloc), *stk = stkalloc;
+
   position_set tmp;             /* Temporary set for merging sets.  */
   position_set merged;          /* Result of merging sets.  */
   int separate_contexts;        /* Context wanted by some position.  */
-  bool *o_nullable;
-  size_t *o_nfirst, *o_nlast;
-  position *o_firstpos, *o_lastpos;
   size_t i, j;
   position *pos;
 
@@ -2332,19 +2341,7 @@ dfaanalyze (struct dfa *d, int searchflag)
 #endif
 
   d->searchflag = searchflag != 0;
-
-  nullable = xnmalloc (d->depth, sizeof *nullable);
-  o_nullable = nullable;
-  nfirstpos = xnmalloc (d->depth, sizeof *nfirstpos);
-  o_nfirst = nfirstpos;
-  firstpos = xnmalloc (d->nleaves, sizeof *firstpos);
-  o_firstpos = firstpos, firstpos += d->nleaves;
-  nlastpos = xnmalloc (d->depth, sizeof *nlastpos);
-  o_nlast = nlastpos;
-  lastpos = xnmalloc (d->nleaves, sizeof *lastpos);
-  o_lastpos = lastpos, lastpos += d->nleaves;
   alloc_position_set (&merged, d->nleaves);
-
   d->follows = xcalloc (d->tindex, sizeof *d->follows);
 
   for (i = 0; i < d->tindex; ++i)
@@ -2353,20 +2350,21 @@ dfaanalyze (struct dfa *d, int searchflag)
         {
         case EMPTY:
           /* The empty set is nullable.  */
-          *nullable++ = true;
+          stk->nullable = true;
 
           /* The firstpos and lastpos of the empty leaf are both empty.  */
-          *nfirstpos++ = *nlastpos++ = 0;
+          stk->nfirstpos = stk->nlastpos = 0;
+          stk++;
           break;
 
         case STAR:
         case PLUS:
           /* Every element in the firstpos of the argument is in the follow
              of every element in the lastpos.  */
-          tmp.nelem = nfirstpos[-1];
+          tmp.nelem = stk[-1].nfirstpos;
           tmp.elems = firstpos;
           pos = lastpos;
-          for (j = 0; j < nlastpos[-1]; ++j)
+          for (j = 0; j < stk[-1].nlastpos; ++j)
             {
               merge (&tmp, &d->follows[pos[j].index], &merged);
               copy (&merged, &d->follows[pos[j].index]);
@@ -2375,16 +2373,16 @@ dfaanalyze (struct dfa *d, int searchflag)
         case QMARK:
           /* A QMARK or STAR node is automatically nullable.  */
           if (d->tokens[i] != PLUS)
-            nullable[-1] = true;
+            stk[-1].nullable = true;
           break;
 
         case CAT:
           /* Every element in the firstpos of the second argument is in the
              follow of every element in the lastpos of the first argument.  */
-          tmp.nelem = nfirstpos[-1];
+          tmp.nelem = stk[-1].nfirstpos;
           tmp.elems = firstpos;
-          pos = lastpos + nlastpos[-1];
-          for (j = 0; j < nlastpos[-2]; ++j)
+          pos = lastpos + stk[-1].nlastpos;
+          for (j = 0; j < stk[-2].nlastpos; ++j)
             {
               merge (&tmp, &d->follows[pos[j].index], &merged);
               copy (&merged, &d->follows[pos[j].index]);
@@ -2392,43 +2390,39 @@ dfaanalyze (struct dfa *d, int searchflag)
 
           /* The firstpos of a CAT node is the firstpos of the first argument,
              union that of the second argument if the first is nullable.  */
-          if (nullable[-2])
-            nfirstpos[-2] += nfirstpos[-1];
+          if (stk[-2].nullable)
+            stk[-2].nfirstpos += stk[-1].nfirstpos;
           else
-            firstpos += nfirstpos[-1];
-          --nfirstpos;
+            firstpos += stk[-1].nfirstpos;
 
           /* The lastpos of a CAT node is the lastpos of the second argument,
              union that of the first argument if the second is nullable.  */
-          if (nullable[-1])
-            nlastpos[-2] += nlastpos[-1];
+          if (stk[-1].nullable)
+            stk[-2].nlastpos += stk[-1].nlastpos;
           else
             {
-              pos = lastpos + nlastpos[-2];
-              for (j = nlastpos[-1]; j-- > 0;)
+              pos = lastpos + stk[-2].nlastpos;
+              for (j = stk[-1].nlastpos; j-- > 0;)
                 pos[j] = lastpos[j];
-              lastpos += nlastpos[-2];
-              nlastpos[-2] = nlastpos[-1];
+              lastpos += stk[-2].nlastpos;
+              stk[-2].nlastpos = stk[-1].nlastpos;
             }
-          --nlastpos;
 
           /* A CAT node is nullable if both arguments are nullable.  */
-          nullable[-2] &= nullable[-1];
-          --nullable;
+          stk[-2].nullable &= stk[-1].nullable;
+          stk--;
           break;
 
         case OR:
           /* The firstpos is the union of the firstpos of each argument.  */
-          nfirstpos[-2] += nfirstpos[-1];
-          --nfirstpos;
+          stk[-2].nfirstpos += stk[-1].nfirstpos;
 
           /* The lastpos is the union of the lastpos of each argument.  */
-          nlastpos[-2] += nlastpos[-1];
-          --nlastpos;
+          stk[-2].nlastpos += stk[-1].nlastpos;
 
           /* An OR node is nullable if either argument is nullable.  */
-          nullable[-2] |= nullable[-1];
-          --nullable;
+          stk[-2].nullable |= stk[-1].nullable;
+          stk--;
           break;
 
         default:
@@ -2437,10 +2431,12 @@ dfaanalyze (struct dfa *d, int searchflag)
              an "epsilon closure" effectively makes them nullable later.
              Backreferences have to get a real position so we can detect
              transitions on them later.  But they are nullable.  */
-          *nullable++ = d->tokens[i] == BACKREF;
+          stk->nullable = d->tokens[i] == BACKREF;
 
           /* This position is in its own firstpos and lastpos.  */
-          *nfirstpos++ = *nlastpos++ = 1;
+          stk->nfirstpos = stk->nlastpos = 1;
+          stk++;
+
           --firstpos, --lastpos;
           firstpos->index = lastpos->index = i;
           firstpos->constraint = lastpos->constraint = NO_CONSTRAINT;
@@ -2454,15 +2450,16 @@ dfaanalyze (struct dfa *d, int searchflag)
       fprintf (stderr, "node %zd:", i);
       prtok (d->tokens[i]);
       putc ('\n', stderr);
-      fprintf (stderr, nullable[-1] ? " nullable: yes\n" : " nullable: no\n");
+      fprintf (stderr,
+               stk[-1].nullable ? " nullable: yes\n" : " nullable: no\n");
       fprintf (stderr, " firstpos:");
-      for (j = nfirstpos[-1]; j-- > 0;)
+      for (j = stk[-1].nfirstpos; j-- > 0;)
         {
           fprintf (stderr, " %zd:", firstpos[j].index);
           prtok (d->tokens[firstpos[j].index]);
         }
       fprintf (stderr, "\n lastpos:");
-      for (j = nlastpos[-1]; j-- > 0;)
+      for (j = stk[-1].nlastpos; j-- > 0;)
         {
           fprintf (stderr, " %zd:", lastpos[j].index);
           prtok (d->tokens[lastpos[j].index]);
@@ -2497,7 +2494,7 @@ dfaanalyze (struct dfa *d, int searchflag)
   /* Get the epsilon closure of the firstpos of the regexp.  The result will
      be the set of positions of state 0.  */
   merged.nelem = 0;
-  for (i = 0; i < nfirstpos[-1]; ++i)
+  for (i = 0; i < stk[-1].nfirstpos; ++i)
     insert (firstpos[i], &merged);
   epsclosure (&merged, d);
 
@@ -2507,11 +2504,8 @@ dfaanalyze (struct dfa *d, int searchflag)
                (separate_contexts & CTX_NEWLINE
                 ? CTX_NEWLINE : separate_contexts ^ CTX_ANY));
 
-  free (o_nullable);
-  free (o_nfirst);
-  free (o_firstpos);
-  free (o_nlast);
-  free (o_lastpos);
+  free (posalloc);
+  free (stkalloc);
   free (merged.elems);
 }
 
-- 
1.9.0

From 821a6ca19803cd68b21c63f0c51914fed1dbc02c Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Thu, 17 Apr 2014 19:44:37 -0700
Subject: [PATCH 08/12] dfa: simplify memory allocation

* src/dfa.c (icatalloc, freelist, enlist, comsubs, addlists, inboth)
(dfamust): Don't worry about null arguments or results,
as memory allocators no longer can return null pointers.
(dfamust): Invoke malloc just once when building a concatenated string.
---
 src/dfa.c | 119 +++++++++++++-------------------------------------------------
 1 file changed, 24 insertions(+), 95 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index 4b0e7f2..444af56 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3790,21 +3790,16 @@ static char *
 icatalloc (char *old, char const *new)
 {
   char *result;
-  size_t oldsize = old == NULL ? 0 : strlen (old);
-  size_t newsize = new == NULL ? 0 : strlen (new);
+  size_t oldsize;
+  size_t newsize = strlen (new);
   if (newsize == 0)
     return old;
+  oldsize = strlen (old);
   result = xrealloc (old, oldsize + newsize + 1);
   memcpy (result + oldsize, new, newsize + 1);
   return result;
 }
 
-static char *
-icpyalloc (char const *string)
-{
-  return icatalloc (NULL, string);
-}
-
 static char *_GL_ATTRIBUTE_PURE
 istrstr (char const *lookin, char const *lookfor)
 {
@@ -3823,8 +3818,6 @@ freelist (char **cpp)
 {
   size_t i;
 
-  if (cpp == NULL)
-    return;
   for (i = 0; cpp[i] != NULL; ++i)
     {
       free (cpp[i]);
@@ -3836,14 +3829,7 @@ static char **
 enlist (char **cpp, char *new, size_t len)
 {
   size_t i, j;
-
-  if (cpp == NULL)
-    return NULL;
-  if ((new = icpyalloc (new)) == NULL)
-    {
-      freelist (cpp);
-      return NULL;
-    }
+  new = memcpy (xmalloc (len + 1), new, len);
   new[len] = '\0';
   /* Is there already something in the list that's new (or longer)?  */
   for (i = 0; cpp[i] != NULL; ++i)
@@ -3873,46 +3859,28 @@ enlist (char **cpp, char *new, size_t len)
 }
 
 /* Given pointers to two strings, return a pointer to an allocated
-   list of their distinct common substrings.  Return NULL if something
-   seems wild.  */
+   list of their distinct common substrings.  */
 static char **
 comsubs (char *left, char const *right)
 {
-  char **cpp;
+  char **cpp = xzalloc (sizeof *cpp);
   char *lcp;
-  char *rcp;
-  size_t i, len;
-
-  if (left == NULL || right == NULL)
-    return NULL;
-  cpp = malloc (sizeof *cpp);
-  if (cpp == NULL)
-    return NULL;
-  cpp[0] = NULL;
+
   for (lcp = left; *lcp != '\0'; ++lcp)
     {
-      len = 0;
-      rcp = strchr (right, *lcp);
+      size_t len = 0;
+      char *rcp = strchr (right, *lcp);
       while (rcp != NULL)
         {
+          size_t i;
           for (i = 1; lcp[i] != '\0' && lcp[i] == rcp[i]; ++i)
             continue;
           if (i > len)
             len = i;
           rcp = strchr (rcp + 1, *lcp);
         }
-      if (len == 0)
-        continue;
-      {
-        char **p = enlist (cpp, lcp, len);
-        if (p == NULL)
-          {
-            freelist (cpp);
-            cpp = NULL;
-            break;
-          }
-        cpp = p;
-      }
+      if (len != 0)
+        cpp = enlist (cpp, lcp, len);
     }
   return cpp;
 }
@@ -3920,16 +3888,8 @@ comsubs (char *left, char const *right)
 static char **
 addlists (char **old, char **new)
 {
-  size_t i;
-
-  if (old == NULL || new == NULL)
-    return NULL;
-  for (i = 0; new[i] != NULL; ++i)
-    {
-      old = enlist (old, new[i], strlen (new[i]));
-      if (old == NULL)
-        break;
-    }
+  for (; *new; new++)
+    old = enlist (old, *new, strlen (*new));
   return old;
 }
 
@@ -3938,31 +3898,17 @@ addlists (char **old, char **new)
 static char **
 inboth (char **left, char **right)
 {
-  char **both;
-  char **temp;
+  char **both = xzalloc (sizeof *both);
   size_t lnum, rnum;
 
-  if (left == NULL || right == NULL)
-    return NULL;
-  both = malloc (sizeof *both);
-  if (both == NULL)
-    return NULL;
-  both[0] = NULL;
   for (lnum = 0; left[lnum] != NULL; ++lnum)
     {
       for (rnum = 0; right[rnum] != NULL; ++rnum)
         {
-          temp = comsubs (left[lnum], right[rnum]);
-          if (temp == NULL)
-            {
-              freelist (both);
-              return NULL;
-            }
+          char **temp = comsubs (left[lnum], right[rnum]);
           both = addlists (both, temp);
           freelist (temp);
           free (temp);
-          if (both == NULL)
-            return NULL;
         }
     }
   return both;
@@ -4078,8 +4024,6 @@ dfamust (struct dfa *d)
               lmp->right[j] = lmp->right[(ln - i) + j];
             lmp->right[j] = '\0';
             new = inboth (lmp->in, rmp->in);
-            if (new == NULL)
-              goto done;
             freelist (lmp->in);
             free (lmp->in);
             lmp->in = new;
@@ -4113,39 +4057,26 @@ dfamust (struct dfa *d)
                right, plus concatenation of
                left's right and right's left.  */
             lmp->in = addlists (lmp->in, rmp->in);
-            if (lmp->in == NULL)
-              goto done;
             if (lmp->right[0] != '\0' && rmp->left[0] != '\0')
               {
-                char *tp;
-
-                tp = icpyalloc (lmp->right);
-                tp = icatalloc (tp, rmp->left);
-                lmp->in = enlist (lmp->in, tp, strlen (tp));
+                size_t lrlen = strlen (lmp->right);
+                size_t rllen = strlen (rmp->left);
+                char *tp = xmalloc (lrlen + rllen + 1);
+                memcpy (tp, lmp->right, lrlen);
+                memcpy (tp + lrlen, rmp->left, rllen + 1);
+                lmp->in = enlist (lmp->in, tp, lrlen + rllen);
                 free (tp);
-                if (lmp->in == NULL)
-                  goto done;
               }
             /* Left-hand */
             if (lmp->is[0] != '\0')
-              {
-                lmp->left = icatalloc (lmp->left, rmp->left);
-                if (lmp->left == NULL)
-                  goto done;
-              }
+              lmp->left = icatalloc (lmp->left, rmp->left);
             /* Right-hand */
             if (rmp->is[0] == '\0')
               lmp->right[0] = '\0';
             lmp->right = icatalloc (lmp->right, rmp->right);
-            if (lmp->right == NULL)
-              goto done;
             /* Guaranteed to be */
             if (lmp->is[0] != '\0' && rmp->is[0] != '\0')
-              {
-                lmp->is = icatalloc (lmp->is, rmp->is);
-                if (lmp->is == NULL)
-                  goto done;
-              }
+              lmp->is = icatalloc (lmp->is, rmp->is);
             else
               lmp->is[0] = '\0';
           }
@@ -4183,8 +4114,6 @@ dfamust (struct dfa *d)
             = case_fold && MB_CUR_MAX == 1 ? toupper (t) : t;
           mp->is[1] = mp->left[1] = mp->right[1] = '\0';
           mp->in = enlist (mp->in, mp->is, 1);
-          if (mp->in == NULL)
-            goto done;
           break;
         }
 #ifdef DEBUG
-- 
1.9.0

From a13cee564fa734bfdf5f59656d4e84a6075d3b3f Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Thu, 17 Apr 2014 21:04:24 -0700
Subject: [PATCH 09/12] dfa: avoid duplicate strlen when allocating memory

* src/dfa.c (dfamust): Use xstrdup, not strlen (twice) + xmemdup.
---
 src/dfa.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index 444af56..f8dbc7f 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -4061,9 +4061,9 @@ dfamust (struct dfa *d)
               {
                 size_t lrlen = strlen (lmp->right);
                 size_t rllen = strlen (rmp->left);
-                char *tp = xmalloc (lrlen + rllen + 1);
+                char *tp = xmalloc (lrlen + rllen);
                 memcpy (tp, lmp->right, lrlen);
-                memcpy (tp + lrlen, rmp->left, rllen + 1);
+                memcpy (tp + lrlen, rmp->left, rllen);
                 lmp->in = enlist (lmp->in, tp, lrlen + rllen);
                 free (tp);
               }
@@ -4129,11 +4129,11 @@ dfamust (struct dfa *d)
       ++mp;
     }
 done:
-  if (strlen (result))
+  if (*result)
     {
       dm = xmalloc (sizeof *dm);
       dm->exact = exact;
-      dm->must = xmemdup (result, strlen (result) + 1);
+      dm->must = xstrdup (result);
       dm->next = d->musts;
       d->musts = dm;
     }
-- 
1.9.0

From f6f19ff318188eb3fc4e9bb5e9ae56b99fae9d31 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Thu, 17 Apr 2014 21:52:00 -0700
Subject: [PATCH 10/12] dfa: simplify freelist

* src/dfa.c (freelist): Don't null out array while freeing its
pointers; the caller can do that if needed.
(resetmust): Null out zeroth entry of array.
---
 src/dfa.c | 12 ++++--------
 1 file changed, 4 insertions(+), 8 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index f8dbc7f..fc82ad9 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3816,13 +3816,8 @@ istrstr (char const *lookin, char const *lookfor)
 static void
 freelist (char **cpp)
 {
-  size_t i;
-
-  for (i = 0; cpp[i] != NULL; ++i)
-    {
-      free (cpp[i]);
-      cpp[i] = NULL;
-    }
+  while (*cpp)
+    free (*cpp++);
 }
 
 static char **
@@ -3925,8 +3920,9 @@ typedef struct
 static void
 resetmust (must * mp)
 {
-  mp->left[0] = mp->right[0] = mp->is[0] = '\0';
   freelist (mp->in);
+  mp->in[0] = NULL;
+  mp->left[0] = mp->right[0] = mp->is[0] = '\0';
 }
 
 static void
-- 
1.9.0

From 0f080095942b81819b521c611851ef2dbcacda99 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Thu, 17 Apr 2014 22:13:31 -0700
Subject: [PATCH 11/12] dfa: simplify dfmust initialization

* src/dfa.c (dfamust): Don't initialize musts twice.
Use zcalloc, not xmalloc followed by zeroing.
Make result a const pointer.
---
 src/dfa.c | 26 ++++++++------------------
 1 file changed, 8 insertions(+), 18 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index fc82ad9..618a8bc 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3928,30 +3928,20 @@ resetmust (must * mp)
 static void
 dfamust (struct dfa *d)
 {
-  must *musts;
-  must *mp;
-  char *result;
+  must *musts = xnmalloc (d->tindex + 1, sizeof *musts);
+  must *mp = musts;
+  char const *result = "";
   size_t ri;
   size_t i;
-  bool exact;
-  static must must0;
+  bool exact = false;
   struct dfamust *dm;
-  static char empty_string[] = "";
 
-  result = empty_string;
-  exact = false;
-  musts = xnmalloc (d->tindex + 1, sizeof *musts);
-  mp = musts;
-  for (i = 0; i <= d->tindex; ++i)
-    mp[i] = must0;
   for (i = 0; i <= d->tindex; ++i)
     {
-      mp[i].in = xmalloc (sizeof *mp[i].in);
-      mp[i].left = xmalloc (2);
-      mp[i].right = xmalloc (2);
-      mp[i].is = xmalloc (2);
-      mp[i].left[0] = mp[i].right[0] = mp[i].is[0] = '\0';
-      mp[i].in[0] = NULL;
+      mp[i].in = xzalloc (sizeof *mp[i].in);
+      mp[i].left = xzalloc (2);
+      mp[i].right = xzalloc (2);
+      mp[i].is = xzalloc (2);
     }
 #ifdef DEBUG
   fprintf (stderr, "dfamust:\n");
-- 
1.9.0

From 3bd7336806152a6d1e129e83d514be9fb935facd Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Thu, 17 Apr 2014 22:30:10 -0700
Subject: [PATCH 12/12] dfa: trans reallocation microoptimization

* src/dfa.c (realloc_trans_if_necessary):
Help the compiler avoid unnecessary reloads.
---
 src/dfa.c | 15 ++++++++-------
 1 file changed, 8 insertions(+), 7 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index 618a8bc..24355d8 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -2799,19 +2799,20 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
 static void
 realloc_trans_if_necessary (struct dfa *d, state_num new_state)
 {
-  if (d->tralloc <= new_state)
+  state_num oldalloc = d->tralloc;
+  if (oldalloc <= new_state)
     {
       state_num **realtrans = d->trans ? d->trans - 1 : NULL;
-      state_num oldalloc = d->tralloc;
+      size_t newalloc;
       d->tralloc = new_state + 1;
       realtrans = x2nrealloc (realtrans, &d->tralloc, sizeof *realtrans);
       realtrans[0] = NULL;
       d->trans = realtrans + 1;
-      d->tralloc--;
-      d->fails = xnrealloc (d->fails, d->tralloc, sizeof *d->fails);
-      d->success = xnrealloc (d->success, d->tralloc, sizeof *d->success);
-      d->newlines = xnrealloc (d->newlines, d->tralloc, sizeof *d->newlines);
-      for (; oldalloc < d->tralloc; oldalloc++)
+      newalloc = --d->tralloc;
+      d->fails = xnrealloc (d->fails, newalloc, sizeof *d->fails);
+      d->success = xnrealloc (d->success, newalloc, sizeof *d->success);
+      d->newlines = xnrealloc (d->newlines, newalloc, sizeof *d->newlines);
+      for (; oldalloc < newalloc; oldalloc++)
         {
           d->trans[oldalloc] = NULL;
           d->fails[oldalloc] = NULL;
-- 
1.9.0

Subject: [PATCH] dfa: speed up memory allocation, port to IRIX
From: Paul Eggert <[email-masked]>
To: grep mailing list <[email-masked]>
Date: Fri, 28 Mar 2014 18:28:57 -0700
List-Id: <debbugs-submit.debbugs.gnu.org>

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