--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2008-01-09  Bruno Haible  <bruno@clisp.org>
+
+	Work around OpenBSD 4.0 tdelete() bug.
+	* m4/tsearch.m4 (gl_FUNC_TSEARCH): Also check tdelete's return value.
+	* lib/search.in.h: If REPLACE_TSEARCH is 1, define tsearch etc. as
+	macros and don't redefine the enum values.
+	* m4/search_h.m4 (gl_SEARCH_H_DEFAULTS): Initialize REPLACE_TSEARCH.
+	* modules/search (Makefile.am): Also substitute REPLACE_TSEARCH.
+	* doc/functions/tdelete.texi: Document the OpenBSD 4.0 bug.
+
 2008-01-09  Bruno Haible  <bruno@clisp.org>
 
 	* tests/test-wcwidth.c: Include <string.h> and localcharset.h.

--- a/doc/functions/tdelete.texi
+++ b/doc/functions/tdelete.texi
@@ -11,6 +11,10 @@
 @item
 This function is missing on some platforms:
 mingw, BeOS.
+@item
+@code{tdelete} returns @code{NULL} when removing the last element of a tree
+on some platforms:
+OpenBSD 4.0.
 @end itemize
 
 Portability problems not fixed by Gnulib:

--- a/lib/search.in.h
+++ b/lib/search.in.h
@@ -1,6 +1,6 @@
 /* A GNU-like <search.h>.
 
-   Copyright (C) 2007 Free Software Foundation, Inc.
+   Copyright (C) 2007-2008 Free Software Foundation, Inc.
 
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
@@ -35,12 +35,19 @@
 
 
 #if @GNULIB_TSEARCH@
-# if !@HAVE_TSEARCH@
+# if @REPLACE_TSEARCH@
+#  define tsearch rpl_tsearch
+#  define tfind rpl_tfind
+#  define tdelete rpl_tdelete
+#  define twalk rpl_twalk
+# endif
+# if !@HAVE_TSEARCH@ || @REPLACE_TSEARCH@
 
 /* See <http://www.opengroup.org/susv3xbd/search.h.html>,
        <http://www.opengroup.org/susv3xsh/tsearch.html>
    for details.  */
 
+#  if !@HAVE_TSEARCH@
 typedef enum
 {
   preorder,
@@ -49,6 +56,7 @@
   leaf
 }
 VISIT;
+#  endif
 
 /* Searches an element in the tree *VROOTP that compares equal to KEY.
    If one is found, it is returned.  Otherwise, a new element equal to KEY

--- a/m4/search_h.m4
+++ b/m4/search_h.m4
@@ -1,5 +1,5 @@
-# search_h.m4 serial 2
-dnl Copyright (C) 2007 Free Software Foundation, Inc.
+# search_h.m4 serial 3
+dnl Copyright (C) 2007-2008 Free Software Foundation, Inc.
 dnl This file is free software; the Free Software Foundation
 dnl gives unlimited permission to copy and/or distribute it,
 dnl with or without modifications, as long as this notice is preserved.
@@ -27,5 +27,6 @@
 [
   GNULIB_TSEARCH=0; AC_SUBST([GNULIB_TSEARCH])
   dnl Assume proper GNU behavior unless another module says otherwise.
-  HAVE_TSEARCH=1; AC_SUBST([HAVE_TSEARCH])
+  HAVE_TSEARCH=1;    AC_SUBST([HAVE_TSEARCH])
+  REPLACE_TSEARCH=0; AC_SUBST([REPLACE_TSEARCH])
 ])

--- a/m4/tsearch.m4
+++ b/m4/tsearch.m4
@@ -1,5 +1,5 @@
-# tsearch.m4 serial 2
-dnl Copyright (C) 2006-2007 Free Software Foundation, Inc.
+# tsearch.m4 serial 3
+dnl Copyright (C) 2006-2008 Free Software Foundation, Inc.
 dnl This file is free software; the Free Software Foundation
 dnl gives unlimited permission to copy and/or distribute it,
 dnl with or without modifications, as long as this notice is preserved.
@@ -8,7 +8,45 @@
 [
   AC_REQUIRE([gl_SEARCH_H_DEFAULTS])
   AC_CHECK_FUNCS([tsearch])
-  if test $ac_cv_func_tsearch = no; then
+  if test $ac_cv_func_tsearch = yes; then
+    dnl On OpenBSD 4.0, the return value of tdelete() is incorrect.
+    AC_REQUIRE([AC_PROG_CC])
+    AC_REQUIRE([AC_CANONICAL_HOST]) dnl for cross-compiles
+    AC_CACHE_CHECK([whether tdelete works], [gl_cv_func_tdelete_works],
+      [
+        AC_TRY_RUN([
+#include <stddef.h>
+#include <search.h>
+static int
+cmp_fn (const void *a, const void *b)
+{
+  return *(const int *) a - *(const int *) b;
+}
+int
+main ()
+{
+  int x = 0;
+  void *root = NULL;
+  if (!(tfind (&x, &root, cmp_fn) == NULL)) return 1;
+  tsearch (&x, &root, cmp_fn);
+  if (!(tfind (&x, &root, cmp_fn) != NULL)) return 1;
+  if (!(tdelete (&x, &root, cmp_fn) != NULL)) return 1;
+  return 0;
+}], [gl_cv_func_tdelete_works=yes], [gl_cv_func_tdelete_works=no],
+            [case "$host_os" in
+               openbsd*) gl_cv_func_tdelete_works="guessing no";;
+               *)        gl_cv_func_tdelete_works="guessing yes";;
+             esac
+            ])
+      ])
+    case "$gl_cv_func_tdelete_works" in
+      *no)
+        REPLACE_TSEARCH=1
+        AC_LIBOBJ([tsearch])
+        gl_PREREQ_TSEARCH
+        ;;
+    esac
+  else
     HAVE_TSEARCH=0
     AC_LIBOBJ([tsearch])
     gl_PREREQ_TSEARCH

--- a/modules/search
+++ b/modules/search
@@ -25,6 +25,7 @@
 	      -e 's|@''NEXT_SEARCH_H''@|$(NEXT_SEARCH_H)|g' \
 	      -e 's|@''GNULIB_TSEARCH''@|$(GNULIB_TSEARCH)|g' \
 	      -e 's|@''HAVE_TSEARCH''@|$(HAVE_TSEARCH)|g' \
+	      -e 's|@''REPLACE_TSEARCH''@|$(REPLACE_TSEARCH)|g' \
 	      -e '/definition of GL_LINK_WARNING/r $(LINK_WARNING_H)' \
 	      < $(srcdir)/search.in.h; \
 	} > $@-t