Re: AC_FUNC_MEMMEM

[Eric Blake]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

According to Ralf Wildenhues on 1/2/2008 12:27 PM:
|> It would be very helpful if GNU Autoconf had a AC_FUNC_MEMMEM macro to
|> detect correct memmem(3) implementations.
|
| FWIW, gnulib has a module memmem that provides a macro gl_FUNC_MEMMEM
| that should test for at least the first issue.
|
| Please note that even glibc 2.6.1 provides an implementation of memmem
| that scales quadratically in the worst case, unlike the gnulib version.

Furthermore, I've just proposed a patch to gnulib that speeds up memmem to
always be O(n+m) in time and O(1) in space, and as fast as O(n/m) for long
needles, using a hybrid of the Two-Way algorithm (published in 1991) and
Boyer-Moore (1977).  I don't know of any system implementation that has
all of these perks simultaneously, and my web search did not turn up any
code similar to mine.  Once it is tested by the gnulib team, it will be
pushed back to the glibc team for glibc > 2.6.1, but that may be a while
off, so at the present, you almost always want to replace the system
memmem with a better implementation.

http://thread.gmane.org/gmane.comp.lib.gnulib.bugs/12340

- --
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

iD8DBQFHgDwR84KuGfSFAYARAre8AJ0TtSxacKUn2kMCkMnxBB6qOtwpYQCgjtxS
GVnsNo3Uy7KIrxS9/6kZN1s=
=+4a/
-----END PGP SIGNATURE-----