This is the mail archive of the
mailing list for the Cygwin project.
- From: Eric Blake <ebb9 at byu dot net>
- To: cygwin at cygwin dot com
- Date: Wed, 19 Dec 2007 21:22:17 +0000 (UTC)
- Subject: memmem issues
memmem isn't standardized, but even so, it has some bugs based on comparison
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.
Unsubscribe info: http://cygwin.com/ml/#unsubscribe-simple
Problem reports: http://cygwin.com/problems.html