-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
[adding bug-gnulib]
According to Peter Miller on 1/7/2008 5:15 PM:
| On Sat, 2008-01-05 at 21:51 -0700, Eric Blake wrote:
|> glibc 2.6.1 is quadratic, gnulib is linear. For worst-case scenarios,
|> gnulib's implementation is hands-down better, although the hope is that
|> future glibc releases will eventually import the gnulib implementation..
|
| Looking at the code (from the git head revision) the knuth_morris_pratt
| function appears to return false positives, which could, in turn, cause
| memmem to return an uninitialised result pointer.
| Or am I missing something subtle?
|
| --- memmem.c 2008-01-08 11:09:47.000000000 +1100
| +++ new-memmem.c 2008-01-08 11:10:36.000000000 +1100
| @@ -130,7 +130,8 @@
| {
| /* The entire needle has been found. */
| *resultp = rhaystack;
| - break;
| + freea (table);
| + return true;
| }
| }
| else if (j > 0)
| @@ -148,7 +149,7 @@
| }
|
| freea (table);
| - return true;
| + return false;
| }
|
| /* Return the first occurrence of NEEDLE in HAYSTACK. Return HAYSTACK
You were missing something subtle. Right after phaystack is declared,
*resultp is unconditionally initialized to NULL. And *resultp is valid
only if the function returns true; your patch would break the code by
returning false when KMP has successfully discovered the lack of a match.
That said, the KMP algorithm is not ideal; and what you should be
reviewing is my Two-Way/Boyer-Moore hybrid instead. I will be checking
that in soon:
http://lists.gnu.org/archive/html/bug-gnulib/2008-01/msg00031.html
once I've folded in the comments in that thread. I'm also working on
generalizing my patch to be used in strstr, strcasestr, and strncasestr.
- --
Don't work too hard, make some time for fun as well!
Eric Blake [EMAIL PROTECTED]
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHguWE84KuGfSFAYARAm+CAJ0cb9I2IA5VH9Gs9ObsEdYOfeSdWQCgzLMg
aA51aBsd4SWaGix6oaS4kWw=
=fn1o
-----END PGP SIGNATURE-----
