Hash :
fc068cf4
Author :
Date :
2007-12-19T16:09:03
Fix memmem to avoid O(n^2) worst-case complexity. * lib/memmem.c (knuth_morris_pratt): New function. (memmem): Use it if first few naive iterations fail. * m4/memmem.m4 (gl_FUNC_MEMMEM): Detect cygwin bug. * modules/memcmp (License): Set to LGPLv2+, not LGPL. * modules/memchr (License): Likewise. * modules/memmem (Depends-on): Add memcmp, memchr, stdbool, and malloca. * tests/test-memmem.c: Rewrite, borrowing ideas from test-mbsstr1.c; the old version wouldn't even compile! * modules/memmem-tests: New file. * lib/string.in.h (rpl_memmem): Add declaration. * modules/string (Makefile.am): Substitute REPLACE_MEMMEM. * m4/string_h.m4 (gl_HEADER_STRING_H_DEFAULTS): Default for REPLACE_MEMMEM. Signed-off-by: Eric Blake <ebb9@byu.net>