[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Sat, 05 Jan 2008 19:25:21 -0700
Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:188.8.131.52) Gecko/20071031 Thunderbird/184.108.40.206 Mnenhy/0.7.5.666
-----BEGIN PGP SIGNED MESSAGE-----
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.
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
-----END PGP SIGNATURE-----