grep branch, master, updated. v2.9-6-g3c3bdac

[Jim Meyering]

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "grep".

The branch, master has been updated
       via  3c3bdace487c2c961ab3126d9a573af29c449c8b (commit)
      from  ee9c7844147c001004f4b87171c26238d24f8194 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
http://git.savannah.gnu.org/cgit/grep.git/commit/?id=3c3bdace487c2c961ab3126d9a573af29c449c8b


commit 3c3bdace487c2c961ab3126d9a573af29c449c8b
Author: Jim Meyering <address@hidden>
Date:   Tue Jun 28 14:20:57 2011 +0200

    dfa: fix the root cause of the heap overrun
    
    dfa's "insert" function was supposed to be maintaining the position
    list sorted on *decreasing* index, but since the 2009-12-09 "Speed
    up insert" commit, 62458291, it was using code that assumed the data
    were sorted on *increasing* index.  As such, sometimes it would no
    longer merge constraints (not finding a match) and would append
    entries that normally would have matched and been merged.  Those
    erroneous append operations resulted in the heap overrun fixed by
    2011-06-17 commit 0b91d692 by doubling the array size.
    * src/dfa.c (insert): Fix the comparison.
    (dfaanalyze): Now that that's fixed, revert commit 0b91d692,
    allocating space for only d->nleaves entries, not double that.
    As far as I can tell, this change has no effect other than
    decreased memory usage, although it may improve performance
    slightly, since the resulting list of positions is half as long
    as it used to be.

diff --git a/src/dfa.c b/src/dfa.c
index a36b80a..f6b9f59 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -1835,9 +1835,9 @@ copy (position_set const *src, position_set *dst)
   dst->nelem = src->nelem;
 }
 
-/* Insert a position in a set.  Position sets are maintained in sorted
-   order according to index.  If position already exists in the set with
-   the same index then their constraints are logically or'd together.
+/* Insert position P in set S.  S is maintained in sorted order on
+   decreasing index.  If there is already an entry in S with P.index
+   then merge (logically-OR) P's constraints into the one in S.
    S->elems must point to an array large enough to hold the resulting set. */
 static void
 insert (position p, position_set *s)
@@ -1847,7 +1847,7 @@ insert (position p, position_set *s)
   while (lo < hi)
     {
       int mid = ((unsigned) lo + (unsigned) hi) >> 1;
-      if (s->elems[mid].index < p.index)
+      if (s->elems[mid].index > p.index)
         lo = mid + 1;
       else
         hi = mid;
@@ -2132,7 +2132,7 @@ dfaanalyze (struct dfa *d, int searchflag)
   MALLOC(lastpos, position, d->nleaves);
   o_lastpos = lastpos, lastpos += d->nleaves;
   CALLOC(nalloc, int, d->tindex);
-  MALLOC(merged.elems, position, 2 * d->nleaves);
+  MALLOC(merged.elems, position, d->nleaves);
 
   CALLOC(d->follows, position_set, d->tindex);
 

-----------------------------------------------------------------------

Summary of changes:
 src/dfa.c |   10 +++++-----
 1 files changed, 5 insertions(+), 5 deletions(-)


hooks/post-receive
-- 
grep