[PATCH 2/2] Speed up insert.

[Paolo Bonzini]

Suggested by Johan Walles <address@hidden> (bug 23354).

* src/dfa.c (insert): Use binary search.
---
 THANKS    |    1 +
 src/dfa.c |   29 ++++++++++++++++-------------
 2 files changed, 17 insertions(+), 13 deletions(-)

diff --git a/THANKS b/THANKS
index 3c89175..508846f 100644
--- a/THANKS
+++ b/THANKS
@@ -38,6 +38,7 @@ Jim Hand                   <address@hidden>
 Jim Meyering               <address@hidden>
 Jochen Hein                <address@hidden>
 Joel N. Weber II           <address@hidden>
+Johan Walles               <address@hidden>
 John Hughes                <address@hidden>
 Jorge Stolfi               <address@hidden>
 Juan Manuel Guerrero       <address@hidden>
diff --git a/src/dfa.c b/src/dfa.c
index 7d97f30..d1d7f25 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -1433,23 +1433,26 @@ copy (position_set const *src, position_set *dst)
 static void
 insert (position p, position_set *s)
 {
-  int i;
-  position t1, t2;
+  int count = s->nelem;
+  int lo = 0, hi = count;
+  while (lo < hi)
+    {
+      int mid = ((unsigned) lo + (unsigned) hi) >> 1;
+      if (s->elems[mid].index < p.index)
+        lo = mid + 1;
+      else
+        hi = mid;
+    }
 
-  for (i = 0; i < s->nelem && p.index < s->elems[i].index; ++i)
-    continue;
-  if (i < s->nelem && p.index == s->elems[i].index)
-    s->elems[i].constraint |= p.constraint;
+  if (lo < count && p.index == s->elems[lo].index)
+    s->elems[lo].constraint |= p.constraint;
   else
     {
-      t1 = p;
+      int i;
+      for (i = count; i > lo; i--)
+        s->elems[i] = s->elems[i - 1];
+      s->elems[lo] = p;
       ++s->nelem;
-      while (i < s->nelem)
-       {
-         t2 = s->elems[i];
-         s->elems[i++] = t1;
-         t1 = t2;
-       }
     }
 }
 
-- 
1.6.5.2