-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 According to Jim Meyering on 12/20/2007 12:33 AM: > Eric Blake <[EMAIL PROTECTED]> 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 [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 iD8DBQFHam/V84KuGfSFAYARAtB2AJ4lN0eL7BO+g7B2Hal5rwthVMCxcACcDILB ajVo1OS8ZCgEYPQ8AdfTa/A= =qNje -----END PGP SIGNATURE-----
