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