Re: strstr speedup

[Eric Blake]

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

According to Eric Blake on 1/10/2008 10:25 PM:
| How's this for strcasestr?

|  #define TOLOWER(Ch) (isupper (Ch) ? tolower (Ch) : (Ch))
|
| -/* Knuth-Morris-Pratt algorithm.  */
| +/* Two-Way algorithm.  */
| +#define RETURN_TYPE char *
| +#define AVAILABLE(h, h_l, j, n_l)                    \
| +  (!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l))  \
| +   && ((h_l) = (j) + (n_l)))
|  #define CANON_ELEMENT(c) TOLOWER (c)

In testing this, I noticed that TOLOWER evaluates its argument more than
once.  Are there still broken platforms out there where tolower() disobeys
the POSIX requirement that it leave the argument unchanged if it was not
already an upper-case letter?  And if so, shouldn't the correct action be
adding ctype and/or tolower/toupper/... modules to work around those
deficiencies, so we can directly use tolower() here without expanding the
argument multiple times?

| cygwin 1.5.x does not have strcasestr but
| CVS cygwin does, and it is quadratic (as of today, although I've posted a
| similar patch there).

My patch for non-quadratic memmem, strstr, and strcasestr was accepted
into cygwin CVS yesterday, so the next version of Cygwin will pass the
gnulib tests without needing replacement.

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

iD8DBQFHiNBV84KuGfSFAYARAtONAKCrai+OMAfnTWCih+ThblQJed0sSwCglU/x
XSZsVo6Tvs1VPydImz+RXKU=
=VZ13
-----END PGP SIGNATURE-----