Mail Archives: cygwin/2007/12/19/18:34:40
memmem isn't standardized, but even so, it has some bugs based on comparison
with strstr.
memmem(haystack,len,"",0) should return haystack, not NULL. This should be an
easy one-line fix.
memmem currently has O(m*n) worst-case complexity (quadratic, when haystack and
needle are both long). But with the Knuth-Morris-Pratt algorithm and a memory
allocation of size n, this could be trimmed to O(m+n) (linear). Gnulib
provides an example of KMP that is only invoked after several unsuccessful
iterations of the naive algorithm, in order to avoid memory allocations, and
which falls back on the naive algorithm if memory allocation fails; however,
the gnulib example is LGPL, so it can't be lifted verbatim into cygwin.
Newlib's strstr could use the same algorithmic speedup. Since I don't have
copyright on file yet, and at any rate have been potentially tainted by reading
the gnulib implementation, I won't be contributing the patch; so I'm less
worried about whether this improvement ever gets added to cygwin. But I can
always wish that someone else could be inspired by this description to write
the improvement from scratch.
--
Eric Blake
--
Unsubscribe info: http://cygwin.com/ml/#unsubscribe-simple
Problem reports: http://cygwin.com/problems.html
Documentation: http://cygwin.com/docs.html
FAQ: http://cygwin.com/faq/
- Raw text -