faster_grep_patch.diff

$diff -u ~/tmp/grep-2.14/src/dfa.c.prev ~/tmp/grep-2.14/src/dfa.c
--- /home/dobrokot/tmp/grep-2.14/src/dfa.c.prev 2013-08-05 16:53:47.824514544 +0400
+++ /home/dobrokot/tmp/grep-2.14/src/dfa.c      2013-08-05 16:50:41.435058597 +0400
@@ -1978,6 +1978,52 @@
     m->elems[m->nelem++] = s2->elems[j++];
 }

+static void
+merge_inplace (position_set const *src, position_set *dst)
+{
+  size_t new_elems = 0;
+  size_t copy_from = 0;
+  size_t copy_to = 0;
+
+  size_t j, k = 0;
+
+  size_t src_count = src->nelem;
+  size_t dst_count = dst->nelem;
+
+  const position *src_elems = src->elems;
+  position *dst_elems = dst->elems;
+
+  for (j = 0; j < src_count; ++j) {
+    size_t jp = src_elems[j].index;
+    while (k < dst_count && jp < dst_elems[k].index) {
+      ++k;
+    }
+    if (k == dst_count || jp != dst_elems[k].index)
+      new_elems += 1;
+    else
+      dst->elems[k].constraint |= src->elems[j].constraint;
+  }
+  if (new_elems) {
+    copy_from = dst_count - 1;
+    dst->nelem = dst_count + new_elems;
+    REALLOC_IF_NECESSARY(dst->elems, dst->alloc, dst->nelem);
+    dst_elems = dst->elems;
+    copy_to = dst->nelem - 1;
+    j = src_count - 1;
+    while (copy_from != copy_to) {
+      if ((int)copy_from > (int)copy_to) { fprintf(stderr, "%d %d\n", (int)copy_from, (int)copy_to); abort(); }
+      if (j + 1 != 0 && (copy_from + 1 == 0 || dst_elems[copy_from].index >= src_elems[j].index)) {
+        if (copy_from + 1 == 0 || dst_elems[copy_from].index > src_elems[j].index) {
+          dst_elems[copy_to--] = src_elems[j];
+        }
+        --j;
+      } else {
+        dst_elems[copy_to--] = dst_elems[copy_from--];
+      }
+    }
+  }
+}
+
 /* Delete a position from a set. */
 static void
 delete (position p, position_set * s)
@@ -2680,9 +2726,7 @@
          of state 0 as well. */
       if (d->searchflag
           && (!MBS_SUPPORT || (d->mb_cur_max == 1 || !next_isnt_1st_byte))) {
-        for (j = 0; j < d->states[0].elems.nelem; ++j) {
-          insert(d->states[0].elems.elems[j], &follows);
-        }
+        merge_inplace(&d->states[0].elems, &follows);
       }

       /* Find out if the new state will want any context information. */