This is the mail archive of the cygwin mailing list for the Cygwin project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

memmem issues

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:
Problem reports:

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]