Re: AC_FUNC_MEMMEM

[Eric Blake]

-----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             address@hidden
-----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-----