Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
$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. */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.