diff options
| author | Eric Blake <ebb9@byu.net> | 2007-12-19 16:09:03 -0700 |
|---|---|---|
| committer | Eric Blake <ebb9@byu.net> | 2007-12-20 06:02:01 -0700 |
| commit | fc068cf4eb6814e848e4dc54e1c5cf4c30a79a6f (patch) | |
| tree | a195a67b5ddd7d22b8c62277871cab7435cc7b54 /m4 | |
| parent | e323f261972032e4a1eeee6102c2327e97c808df (diff) | |
| download | gnulib-fc068cf4eb6814e848e4dc54e1c5cf4c30a79a6f.tar.gz | |
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>
Diffstat (limited to 'm4')
| -rw-r--r-- | m4/memmem.m4 | 14 | ||||
| -rw-r--r-- | m4/string_h.m4 | 3 |
2 files changed, 16 insertions, 1 deletions
diff --git a/m4/memmem.m4 b/m4/memmem.m4 index e6a3da193c..a529af3bec 100644 --- a/m4/memmem.m4 +++ b/m4/memmem.m4 @@ -1,4 +1,4 @@ -# memmem.m4 serial 5 +# memmem.m4 serial 6 dnl Copyright (C) 2002, 2003, 2004, 2007 Free Software Foundation, Inc. dnl This file is free software; the Free Software Foundation dnl gives unlimited permission to copy and/or distribute it, @@ -14,6 +14,18 @@ AC_DEFUN([gl_FUNC_MEMMEM], AC_CHECK_DECLS_ONCE(memmem) if test $ac_cv_have_decl_memmem = no; then HAVE_DECL_MEMMEM=0 + else + AC_CACHE_CHECK([whether memmem works], [gl_cv_func_memmem_works], + [AC_RUN_IFELSE([AC_LANG_PROGRAM([#include <string.h>], + [return !memmem ("a", 1, NULL, 0);])], + [gl_cv_func_memmem_works=yes], [gl_cv_func_memmem_works=no], + [dnl pessimistically assume the worst, since even glibc 2.6.1 + dnl has quadratic complexity in its memmem + gl_cv_func_memmem_works=no])]) + if test $gl_cv_func_memmem_works = no; then + REPLACE_MEMMEM=1 + AC_LIBOBJ([memmem]) + fi fi gl_PREREQ_MEMMEM ]) diff --git a/m4/string_h.m4 b/m4/string_h.m4 index 83711799a1..99a0dabbcb 100644 --- a/m4/string_h.m4 +++ b/m4/string_h.m4 @@ -5,6 +5,8 @@ # gives unlimited permission to copy and/or distribute it, # with or without modifications, as long as this notice is preserved. +# serial 2 + # Written by Paul Eggert. AC_DEFUN([gl_HEADER_STRING_H], @@ -75,4 +77,5 @@ AC_DEFUN([gl_HEADER_STRING_H_DEFAULTS], HAVE_DECL_STRTOK_R=1; AC_SUBST([HAVE_DECL_STRTOK_R]) HAVE_DECL_STRERROR=1; AC_SUBST([HAVE_DECL_STRERROR]) REPLACE_STRERROR=0; AC_SUBST([REPLACE_STRERROR]) + REPLACE_MEMMEM=0; AC_SUBST([REPLACE_MEMMEM]) ]) |