This is the mail archive of the
cygwin-patches
mailing list for the Cygwin project.
Re: memmem issues
- From: Corinna Vinschen <corinna-cygwin at cygwin dot com>
- To: cygwin-patches at cygwin dot com
- Date: Thu, 20 Dec 2007 11:11:43 +0100
- Subject: Re: memmem issues
- References: <loom.20071219T210928-910@post.gmane.org> <4769E90D.5090908@byu.net>
- Reply-to: cygwin-patches at cygwin dot com
On Dec 19 21:01, Eric Blake wrote:
> Index: libc/memmem.cc
> ===================================================================
> RCS file: /cvs/src/src/winsup/cygwin/libc/memmem.cc,v
> retrieving revision 1.1
> diff -u -p -r1.1 memmem.cc
> --- libc/memmem.cc 8 Nov 2005 22:08:39 -0000 1.1
> +++ libc/memmem.cc 20 Dec 2007 03:56:35 -0000
> @@ -45,8 +45,8 @@ memmem (const void *l, size_t l_len,
> const char *cs = (const char *)s;
>
> /* we need something to compare */
> - if (l_len == 0 || s_len == 0)
> - return NULL;
> + if (s_len == 0)
> + return l;
Looks like this is actually more correct. Glibc and NetBSD both
agree with you, while only the FreeBSD function seems to return NULL
in this case. However, it's not quite ok. l is const void * while the
function returns void *. I applied this part of your patch with the
obvious cast.
> + /* FIXME - this algorithm is worst-case O(l_len*s_len), but using
> + Knuth-Morris-Pratt would be O(l_len+s_len) at the expense of a
> + memory allocation of s_len bytes. Consider rewriting this to
> + swap over the KMP if the first few iterations fail, and back to
> + this if KMP can't allocate enough memory. */
> for (cur = (char *) cl; cur <= last; cur++)
> if (cur[0] == cs[0] && memcmp (cur, cs, s_len) == 0)
> return cur;
What about just using documented example code, for instance from here:
http://www-igm.univ-mlv.fr/~lecroq/string/node8.html
or here:
http://de.wikipedia.org/wiki/Knuth-Morris-Pratt-Algorithmus (in German)
or what about Boyer-Moore instead:
http://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus (in German)
Using one of them is certainly not a licensing violation since all code
examples are more or less the published examples from well-known
textbooks (Knuth, Sedgewick, et al.). Given that, I don't think you're
actually "tainted". An actual implementation would be much better than
a forlorn comment in an unimpressive file in some subdirectory.
Thanks,
Corinna
--
Corinna Vinschen Please, send mails regarding Cygwin to
Cygwin Project Co-Leader cygwin AT cygwin DOT com
Red Hat