-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
A recent bug report[1] against glibc complains that its current
implementation of strstr is O(m*n), with m the length of the needle, n the
length of the haystack (the report is actually against the
analagous, but non-standardized, memmem, but the issu
Eric Blake byu.net> writes:
> http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
>
> It has the nice property of O(1) preprocessing and O(N) comparisons (strictly
> bounded at 2N-M in the worst case),
correction - O(M) preprocessing, O(1) space, and O(N) comparisons.
It's not
Bruno Haible clisp.org> writes:
>
> But this argument also makes it unimportant to use Boyer-Moore over KMP:
> Once you've spent 5*n cycles on the simple algorithm, you don't care whether
> the computation will be finished in additional 2*n cycles or 2*n/m cycles.
>
> > The main problem
> > tho
Eric Blake wrote:
> + * tests/test-memmem.c (main): Use alarm to declare failure if test
> + is taking too long.
The function alarm() does not exist on mingw. Neither does SIGALRM.
If you are looking for a quick temporary workaround, until you decided
whether to create a 'memmam-fast' mod
Simon Josefsson wrote:
> The strcase module fails to build. It seems to need stuff from the
> string *.m4 file. How about this patch?
Oops, my mistake from 2007-12-02. I'm committing this fix. Thanks
for the report.
2008-01-04 Bruno Haible <[EMAIL PROTECTED]>
* m4/strcase.m4 (gl_FUN
Ralf Wildenhues gmx.de> writes:
>
> I suggest that either the testsuite test use some time limit (alarm?),
> or the configure test tries to expose the quadratic complexity, or the
> configure test assume `no' on systems where we know libc's memmem to be
> insufficient.
I'm still planning on ask
It takes a long time on my autobuild machine as well (debian x86
stable). Running for 14 minutes at 100% CPU and counting. Does it have
to run the long-running self-tests each time?
/Simon
Ralf Wildenhues <[EMAIL PROTECTED]> writes:
> Hello, and a Happy New Year,
>
> quoting memmem.m4:
>
>
The strcase module fails to build. It seems to need stuff from the
string *.m4 file. How about this patch?
2008-01-04 Simon Josefsson <[EMAIL PROTECTED]>
* modules/strcase (Depends-on): Add string, because strcase needs
gl_HEADER_STRING_H_DEFAULTS.
diff --git a/modules/strcas
Bruno Haible <[EMAIL PROTECTED]> writes:
> Simon Josefsson wrote:
>> 2007-12-21 Simon Josefsson <[EMAIL PROTECTED]>
>>
>> * modules/relocatable-prog-wrapper (Depends-on): Add intprops and
>> string, needed by strerror.
>
> Yes, please apply. These two modules can be added because
[dropped [EMAIL PROTECTED] from CC]
On Fri, Jan 04, 2008 at 01:15:15AM +0100, Bruno Haible wrote:
> Colin Watson wrote:
> > I decided to write some documentation for this (diff attached), which I
> > hope you can review and add to Gnulib.
>
> Many thanks for this! I changed the node title and a f
10 matches
Mail list logo
