Fix memmem to avoid O(n^2) worst-case complexity.
[gnulib.git] / m4 / memmem.m4
1 # memmem.m4 serial 6
2 dnl Copyright (C) 2002, 2003, 2004, 2007 Free Software Foundation, Inc.
3 dnl This file is free software; the Free Software Foundation
4 dnl gives unlimited permission to copy and/or distribute it,
5 dnl with or without modifications, as long as this notice is preserved.
6
7 AC_DEFUN([gl_FUNC_MEMMEM],
8 [
9   dnl Persuade glibc <string.h> to declare memmem().
10   AC_REQUIRE([AC_USE_SYSTEM_EXTENSIONS])
11
12   AC_REQUIRE([gl_HEADER_STRING_H_DEFAULTS])
13   AC_REPLACE_FUNCS(memmem)
14   AC_CHECK_DECLS_ONCE(memmem)
15   if test $ac_cv_have_decl_memmem = no; then
16     HAVE_DECL_MEMMEM=0
17   else
18     AC_CACHE_CHECK([whether memmem works], [gl_cv_func_memmem_works],
19       [AC_RUN_IFELSE([AC_LANG_PROGRAM([#include <string.h>],
20           [return !memmem ("a", 1, NULL, 0);])],
21         [gl_cv_func_memmem_works=yes], [gl_cv_func_memmem_works=no],
22         [dnl pessimistically assume the worst, since even glibc 2.6.1
23          dnl has quadratic complexity in its memmem
24          gl_cv_func_memmem_works=no])])
25     if test $gl_cv_func_memmem_works = no; then
26       REPLACE_MEMMEM=1
27       AC_LIBOBJ([memmem])
28     fi
29   fi
30   gl_PREREQ_MEMMEM
31 ])
32
33 # Prerequisites of lib/memmem.c.
34 AC_DEFUN([gl_PREREQ_MEMMEM], [:])