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: "jakub at redhat dot com" <sourceware-bugzilla at sourceware dot org>
- To: glibc-bugs at sources dot redhat dot com
- Date: 21 Dec 2007 14:00:13 -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 jakub at redhat dot com 2007-12-21 14:00 -------
> Can you explain why?
Because the malloc call makes the function no longer async-signal safe.
While POSIX says nothing about memmem, it is quite desirable to let
the basic mem* and str*/stp* memory/string ops are async-signal safe (of course
strdup is an exception here). So the code should do:
if (__libc_use_alloca (size_needed_to_allocate))
{
ptr = alloca (size_needed_to_allocate);
// optimized algorithm
}
else
// current O(m*n) search
--
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.