Re: FW: FW: strcasestr() patch proposal

[Eric Blake <ebb9 at byu dot net>]

Olivier Langlois <olivier.langlois <at> streamtheworld.com> writes:

> Nothing is missing in the freebsd implementation. In fact, it might even be
> better than glibc version by being simpler. I took the first implementation
> that Google code returned without knowing all implications.

It is certainly simpler.  But it is O(n*m), whereas O(n+m) algorithms exist.  
We can't use this implementation because it is LGPL, but see gnulib's approach
[1] that uses a hueristic that decides when searching is taking too long (so as 
to avoid malloc for trivial cases), at which point it mallocs memory, 
lowercases the haystack and needle once, then uses Knuth-Morris-Pratt to find 
the needle with a linear traversal (falling back on the quadratic traversal if 
the malloc fails).  Or, better yet, don't look at the implementation, but use 
this description as the guide on how to implement it yourself with the same 
properties, so that you aren't tainted by having looked at the LGPL source for 
inspiration.  Obviously, this becomes a size vs. speed issue, as using gnulib's 
approach consumes more code size, but with the payoff of a huge speedup on 
large strings.

[1] http://cvs.savannah.gnu.org/viewvc/gnulib/lib/strcasestr.c?
revision=1.9&root=gnulib&view=markup

-- 
Eric Blake