This is the mail archive of the
glibc-bugs@sourceware.org
mailing list for the glibc project.
[Bug libc/5514] memmem is O(n^2), but should be O(n)
- From: "ebb9 at byu dot net" <sourceware-bugzilla at sourceware dot org>
- To: glibc-bugs at sources dot redhat dot com
- Date: 8 Jan 2008 21:50:35 -0000
- Subject: [Bug libc/5514] memmem is O(n^2), but should be O(n)
- References: <20071220133012.5514.ebb9@byu.net>
- Reply-to: sourceware-bugzilla at sourceware dot org
------- Additional Comments From ebb9 at byu dot net 2008-01-08 21:50 -------
Gnulib now has a reentrant linear-time constant-space solution for memmem, which
has the added benefit of sublinear speed for large enough needles:
http://git.sv.gnu.org/gitweb/?p=gnulib.git;a=blob;f=lib/memmem.c;h=622a034;hb=9d8d6cd
It also has a testsuite that exposes a couple of cases where the current glibc
takes orders of magnitude longer than the gnulib implementation to come up with
the same answer:
http://git.sv.gnu.org/gitweb/?p=gnulib.git;a=blob;f=tests/test-memmem.c
I'm still working on factoring the code to reuse the bulk of the algorithm in
strstr, strcasestr, strncasestr, and wcsstr (although sublinear speed there is
not an option, since the search for the NUL ending the haystack is an
unavoidable linear task), before posting the same code back here as a diff
against the glibc code base.
--
http://sourceware.org/bugzilla/show_bug.cgi?id=5514
------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.