[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: memmem issues
From: |
Bruno Haible |
Subject: |
Re: memmem issues |
Date: |
Fri, 21 Dec 2007 14:42:11 +0100 |
User-agent: |
KMail/1.9.1 |
Eric Blake wrote:
> - It uses memcmp without depending on the memcmp module, making it needlessly
> fail on some older platforms.
If memory serves me well, the platforms where memcmp was incorrect (comparing
signed instead of unsigned byte values) were SunOS 4 and possibly IRIX 4.
*Very* ancient.
That's the reason why so many modules use memcmp without requiring the module.
> - It passed up on using optimizations built into memchr when needle_len is 1.
>
> Is it okay with everyone that this patch relicenses memchr as LGPLv2+?
Yes.
> - test-memmem.c was flat-out broken (calling memmem with 3 instead of 4
> arguments). The reason it was never compiled was the lack of a memmem-tests
> module.
Thanks for finding this!
> - There are platform-specific bugs in existing memmem implementations.
> Cygwin,
> for example, returns NULL instead of haystack for memmem(haystack,len,"",0).
Ouch.
> How best do I document platform bugs in non-standardized functions?
I would put such info as comments into lib/string.h.
> - The implementation was naively quadratic in the worst-case complexity. ...
> glibc still uses the naive implementation - should we file a bug with them
> to fix it?
It's worth a try. When fnmatch turned out to be exponential and I reported it,
Jakub fixed it.
> Should we update memmem.m4 to reject known-quadratic implementations?
I would say no, since memmem is rarely applied to memory regions larger than
a few hundred bytes. Make it optional, by creating a 'memmem-fast' module
that requires the O(n) implementation.
> + precisely, when
> + - the outer loop count is >= 10,
> + - the average number of comparisons per outer loop is >= 5,
> + - the total number of comparisons is >= m.
These comments are out of sync with the code.
> + /* The first character matches. */
Better write "byte" here, not "character", so that people remember i18n
issues.
> + [AC_RUN_IFELSE([AC_LANG_PROGRAM([#include <string.h>],
> + [return !memmem ("a", 1, NULL, 0);])],
<string.h> does not define NULL. Better write (void*)0 or "" instead of NULL.
> +TESTS += test-memmem
> +TESTS_ENVIRONMENT += EXEEXT='@EXEEXT@'
> +check_PROGRAMS += test-memmem
You can drop the TESTS_ENVIRONMENT line.
Bruno
- Re: memmem issues, (continued)
- Re: memmem issues, Paul Eggert, 2007/12/29
- Re: memmem issues, Bruno Haible, 2007/12/31
- Re: memmem issues, Bruno Haible, 2007/12/31
- Re: memmem issues, Paul Eggert, 2007/12/29
- Re: memmem issues, Bruno Haible, 2007/12/31
- Re: memmem issues, Paul Eggert, 2007/12/31
Re: memmem issues, Bruno Haible, 2007/12/26
Re: memmem issues, Bruno Haible, 2007/12/26
Re: memmem issues,
Bruno Haible <=