[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
grep branch, master, updated. v2.9-6-g3c3bdac
From: |
Jim Meyering |
Subject: |
grep branch, master, updated. v2.9-6-g3c3bdac |
Date: |
Tue, 28 Jun 2011 15:55:26 +0000 |
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
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- grep branch, master, updated. v2.9-6-g3c3bdac,
Jim Meyering <=