Re: memmem issues

[Eric Blake]

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

According to Jim Meyering on 12/20/2007 12:33 AM:
> Eric Blake <address@hidden> wrote:
> ...
>> - The implementation was naively quadratic in the worst-case complexity.  I
>> lifted Bruno's KMP ideas in mbsstr to make it linear+delayed allocation.  
>> glibc
>> still uses the naive implementation - should we file a bug with them to fix
>> it?
> 
> This is the part I was replying to when I said
> it's worth a try.

http://sourceware.org/bugzilla/show_bug.cgi?id=5514

I've committed my initial patch.  I'm not sure how to best go about
writing a test that determines if memmem is worst-case quadratic (perhaps
write a runtime test that compares time for running the algorithm on 100,
1000, then 10000 bytes, and assume quadratic when cross-compiling), so we
can tackle that later.

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

iD8DBQFHam/V84KuGfSFAYARAtB2AJ4lN0eL7BO+g7B2Hal5rwthVMCxcACcDILB
ajVo1OS8ZCgEYPQ8AdfTa/A=
=qNje
-----END PGP SIGNATURE-----