Suggested by Johan Walles <[email protected]> (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 <[email protected]> Jim Meyering <[email protected]> Jochen Hein <[email protected]> Joel N. Weber II <[email protected]> +Johan Walles <[email protected]> John Hughes <[email protected]> Jorge Stolfi <[email protected]> Juan Manuel Guerrero <[email protected]> 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
