This is the mail archive of the glibc-bugs@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


------- 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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]