[Bug libc/5514] memmem is O(n^2), but should be O(n)

[bruno at clisp dot org]

------- Additional Comments From bruno at clisp dot org  2007-12-21 13:50 -------
> it is not really feasible to have functions like memmem and strstr
> calling malloc.

When the call to malloc fails, the proposed memmem code falls back to the
O(n^2) code, so degrades gracefully, still returning the correct result
(just slower).

> Such functions have always been simple reentrant code before,
> and we can't go introducing locking and so forth there.

Can you explain why? The locking is done inside malloc(). The performance
will not suffer in most cases, since malloc() is called only when the
algorithm has hints that it is running on one of the worst-case scenarios.

> post the patch to libc-alpha.

Our experience with submissions via bugzilla has been better than with
posts to libc-alpha.

-- 


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.