[PATCH 9/9] dfa: automatically resize position_sets

[Paolo Bonzini]

* src/dfa.c (insert, copy, merge): Resize arrays here.
(dfaanalyze): Do not track number of allocated elements here.
(dfastate): Allocate mbps with only one element.
---
 src/dfa.c |   26 ++++++++++++--------------
 1 files changed, 12 insertions(+), 14 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index 491f447..0db93cd 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -1828,6 +1828,7 @@ dfaparse (char const *s, size_t len, struct dfa *d)
 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);
   dst->nelem = src->nelem;
 }
@@ -1849,6 +1850,7 @@ insert (position p, position_set *s)
 {
   int count = s->nelem;
   int lo = 0, hi = count;
+  int i;
   while (lo < hi)
     {
       int mid = ((unsigned) lo + (unsigned) hi) >> 1;
@@ -1859,15 +1861,16 @@ insert (position p, position_set *s)
     }
 
   if (lo < count && p.index == s->elems[lo].index)
-    s->elems[lo].constraint |= p.constraint;
-  else
     {
-      int i;
-      for (i = count; i > lo; i--)
-        s->elems[i] = s->elems[i - 1];
-      s->elems[lo] = p;
-      ++s->nelem;
+      s->elems[lo].constraint |= p.constraint;
+      return;
     }
+
+  REALLOC_IF_NECESSARY(s->elems, s->alloc, count + 1);
+  for (i = count; i > lo; i--)
+    s->elems[i] = s->elems[i - 1];
+  s->elems[lo] = p;
+  ++s->nelem;
 }
 
 /* Merge two sets of positions into a third.  The result is exactly as if
@@ -1877,6 +1880,7 @@ merge (position_set const *s1, position_set const *s2, 
position_set *m)
 {
   int i = 0, j = 0;
 
+  REALLOC_IF_NECESSARY(m->elems, m->alloc, s1->nelem + s2->nelem);
   m->nelem = 0;
   while (i < s1->nelem && j < s2->nelem)
     if (s1->elems[i].index > s2->elems[j].index)
@@ -2162,8 +2166,6 @@ dfaanalyze (struct dfa *d, int searchflag)
         for (j = 0; j < nlastpos[-1]; ++j)
           {
             merge(&tmp, &d->follows[pos[j].index], &merged);
-            REALLOC_IF_NECESSARY(d->follows[pos[j].index].elems,
-                                 d->follows[pos[j].index].alloc, merged.nelem);
             copy(&merged, &d->follows[pos[j].index]);
           }
 
@@ -2182,8 +2184,6 @@ dfaanalyze (struct dfa *d, int searchflag)
         for (j = 0; j < nlastpos[-2]; ++j)
           {
             merge(&tmp, &d->follows[pos[j].index], &merged);
-            REALLOC_IF_NECESSARY(d->follows[pos[j].index].elems,
-                                 d->follows[pos[j].index].alloc, merged.nelem);
             copy(&merged, &d->follows[pos[j].index]);
           }
 
@@ -2291,8 +2291,6 @@ dfaanalyze (struct dfa *d, int searchflag)
 #endif
         copy(&d->follows[i], &merged);
         epsclosure(&merged, d);
-        REALLOC_IF_NECESSARY(d->follows[i].elems, d->follows[i].alloc,
-                            merged.nelem);
         copy(&merged, &d->follows[i]);
       }
 
@@ -2410,7 +2408,7 @@ dfastate (int s, struct dfa *d, int trans[])
              must put it to d->states[s].mbps, which contains the positions
              which can match with a single character not a byte.  */
           if (d->states[s].mbps.nelem == 0)
-            alloc_posset(&d->states[s].mbps, d->states[s].elems.nelem);
+            alloc_posset(&d->states[s].mbps, 1);
           insert(pos, &(d->states[s].mbps));
           continue;
         }
-- 
1.7.7.1