Implement twalk(3), add unit tests.

I've also added insque(3) and remque(3) (from NetBSD because the OpenBSD
ones are currently broken for non-circular lists).

I've not added the three hash table functions that should be in this header
because they operate on a single global hash table and thus aren't likely
to be useful.

Bug: https://code.google.com/p/android/issues/detail?id=73719
Change-Id: I97397a7b921e2e860fd9c8032cafd9097380498a

12 files changed, 323 insertions, 213 deletions

diff --git a/libc/Android.mk b/libc/Android.mk
index 0bdf1a5..1fb5e84 100644
--- a/libc/Android.mk
+++ b/libc/Android.mk
@@ -287,20 +287,18 @@ libc_upstream_netbsd_src_files := \
     upstream-netbsd/lib/libc/stdlib/div.c \
     upstream-netbsd/lib/libc/stdlib/drand48.c \
     upstream-netbsd/lib/libc/stdlib/erand48.c \
+    upstream-netbsd/lib/libc/stdlib/insque.c \
     upstream-netbsd/lib/libc/stdlib/jrand48.c \
     upstream-netbsd/lib/libc/stdlib/ldiv.c \
     upstream-netbsd/lib/libc/stdlib/lldiv.c \
     upstream-netbsd/lib/libc/stdlib/lrand48.c \
-    upstream-netbsd/lib/libc/stdlib/lsearch.c \
     upstream-netbsd/lib/libc/stdlib/mrand48.c \
     upstream-netbsd/lib/libc/stdlib/nrand48.c \
     upstream-netbsd/lib/libc/stdlib/_rand48.c \
     upstream-netbsd/lib/libc/stdlib/rand_r.c \
+    upstream-netbsd/lib/libc/stdlib/remque.c \
     upstream-netbsd/lib/libc/stdlib/seed48.c \
     upstream-netbsd/lib/libc/stdlib/srand48.c \
-    upstream-netbsd/lib/libc/stdlib/tdelete.c \
-    upstream-netbsd/lib/libc/stdlib/tfind.c \
-    upstream-netbsd/lib/libc/stdlib/tsearch.c \
     upstream-netbsd/lib/libc/string/memccpy.c \
     upstream-netbsd/lib/libc/string/strcasestr.c \
     upstream-netbsd/lib/libc/string/strcoll.c \
@@ -469,6 +467,7 @@ libc_upstream_openbsd_src_files := \
     upstream-openbsd/lib/libc/stdlib/atoll.c \
     upstream-openbsd/lib/libc/stdlib/exit.c \
     upstream-openbsd/lib/libc/stdlib/getenv.c \
+    upstream-openbsd/lib/libc/stdlib/lsearch.c \
     upstream-openbsd/lib/libc/stdlib/setenv.c \
     upstream-openbsd/lib/libc/stdlib/strtoimax.c \
     upstream-openbsd/lib/libc/stdlib/strtol.c \
@@ -477,6 +476,8 @@ libc_upstream_openbsd_src_files := \
     upstream-openbsd/lib/libc/stdlib/strtoull.c \
     upstream-openbsd/lib/libc/stdlib/strtoumax.c \
     upstream-openbsd/lib/libc/stdlib/system.c \
+    upstream-openbsd/lib/libc/stdlib/tfind.c \
+    upstream-openbsd/lib/libc/stdlib/tsearch.c \
     upstream-openbsd/lib/libc/string/strcasecmp.c \
     upstream-openbsd/lib/libc/string/strcspn.c \
     upstream-openbsd/lib/libc/string/strdup.c \
diff --git a/libc/NOTICE b/libc/NOTICE
index 7f0195f..80d9a27 100644
--- a/libc/NOTICE
+++ b/libc/NOTICE
@@ -57,6 +57,34 @@
 
 -------------------------------------------------------------------
 
+ Copyright (c) 1993 John Brezak
+ All rights reserved.
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions
+ are met:
+ 1. Redistributions of source code must retain the above copyright
+    notice, this list of conditions and the following disclaimer.
+ 2. Redistributions in binary form must reproduce the above copyright
+    notice, this list of conditions and the following disclaimer in the
+    documentation and/or other materials provided with the distribution.
+ 3. The name of the author may be used to endorse or promote products
+    derived from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS'' AND ANY EXPRESS OR
+IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
+INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGE.
+
+-------------------------------------------------------------------
+
 ====================================================
 Copyright (C) 1993 by Sun Microsystems, Inc. All rights reserved.
 
diff --git a/libc/bionic/tdestroy.cpp b/libc/bionic/tdestroy.cpp
index decde4d..49614b8 100644
--- a/libc/bionic/tdestroy.cpp
+++ b/libc/bionic/tdestroy.cpp
@@ -19,7 +19,7 @@
 #include <stdlib.h>
 
 // Destroy a tree and free all allocated resources.
-// This is a GNU extension, not available from NetBSD.
+// This is a GNU extension, not available from BSD.
 void tdestroy(void* root, void (*destroy_func)(void*)) {
   node_t* root_node = (node_t*) root;
   if (root_node == NULL) {
diff --git a/libc/include/search.h b/libc/include/search.h
index b2c0e6b..9b01e12 100644
--- a/libc/include/search.h
+++ b/libc/include/search.h
@@ -29,6 +29,9 @@ typedef struct node {
 
 __BEGIN_DECLS
 
+void insque(void*, void*);
+void remque(void*);
+
 void* lfind(const void*, const void*, size_t*, size_t, int (*)(const void*, const void*));
 void* lsearch(const void*, void*, size_t*, size_t, int (*)(const void*, const void*));
 
diff --git a/libc/upstream-netbsd/lib/libc/stdlib/insque.c b/libc/upstream-netbsd/lib/libc/stdlib/insque.c
new file mode 100644
index 0000000..09020ae
--- /dev/null
+++ b/libc/upstream-netbsd/lib/libc/stdlib/insque.c
@@ -0,0 +1,58 @@
+/*
+ *  Copyright (c) 1993 John Brezak
+ *  All rights reserved.
+ *
+ *  Redistribution and use in source and binary forms, with or without
+ *  modification, are permitted provided that the following conditions
+ *  are met:
+ *  1. Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer.
+ *  2. Redistributions in binary form must reproduce the above copyright
+ *     notice, this list of conditions and the following disclaimer in the
+ *     documentation and/or other materials provided with the distribution.
+ *  3. The name of the author may be used to endorse or promote products
+ *     derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+#if defined(LIBC_SCCS) && !defined(lint)
+__RCSID("$NetBSD: insque.c,v 1.3 2012/06/25 22:32:45 abs Exp $");
+#endif /* LIBC_SCCS and not lint */
+
+#include <assert.h>
+#include <search.h>
+
+struct qelem {
+        struct qelem *q_forw;
+        struct qelem *q_back;
+};
+
+void
+insque(void *entry, void *pred)
+{
+	struct qelem *e = (struct qelem *) entry;
+	struct qelem *p = (struct qelem *) pred;
+
+	_DIAGASSERT(e != 0);
+
+	e->q_back = p;
+	if (p) {
+		e->q_forw = p->q_forw;
+		if (p->q_forw)
+			p->q_forw->q_back = e;
+		p->q_forw = e;
+	} else
+		e->q_forw = 0;
+}
diff --git a/libc/upstream-netbsd/lib/libc/stdlib/remque.c b/libc/upstream-netbsd/lib/libc/stdlib/remque.c
new file mode 100644
index 0000000..6060ad8
--- /dev/null
+++ b/libc/upstream-netbsd/lib/libc/stdlib/remque.c
@@ -0,0 +1,53 @@
+/*
+ *  Copyright (c) 1993 John Brezak
+ *  All rights reserved.
+ *
+ *  Redistribution and use in source and binary forms, with or without
+ *  modification, are permitted provided that the following conditions
+ *  are met:
+ *  1. Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer.
+ *  2. Redistributions in binary form must reproduce the above copyright
+ *     notice, this list of conditions and the following disclaimer in the
+ *     documentation and/or other materials provided with the distribution.
+ *  3. The name of the author may be used to endorse or promote products
+ *     derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+#if defined(LIBC_SCCS) && !defined(lint)
+__RCSID("$NetBSD: remque.c,v 1.3 2012/06/25 22:32:45 abs Exp $");
+#endif /* LIBC_SCCS and not lint */
+
+#include <assert.h>
+#include <search.h>
+
+struct qelem {
+        struct qelem *q_forw;
+        struct qelem *q_back;
+};
+
+void
+remque(void *element)
+{
+	struct qelem *e = (struct qelem *) element;
+
+	_DIAGASSERT(e != 0);
+
+	if (e->q_forw)
+		e->q_forw->q_back = e->q_back;
+	if (e->q_back)
+		e->q_back->q_forw = e->q_forw;
+}
diff --git a/libc/upstream-netbsd/lib/libc/stdlib/tdelete.c b/libc/upstream-netbsd/lib/libc/stdlib/tdelete.c
deleted file mode 100644
index 84017dc..0000000
--- a/libc/upstream-netbsd/lib/libc/stdlib/tdelete.c
+++ /dev/null
@@ -1,67 +0,0 @@
-/*	$NetBSD: tdelete.c,v 1.6 2012/06/25 22:32:45 abs Exp $	*/
-
-/*
- * Tree search generalized from Knuth (6.2.2) Algorithm T just like
- * the AT&T man page says.
- *
- * The node_t structure is for internal use only, lint doesn't grok it.
- *
- * Written by reading the System V Interface Definition, not the code.
- *
- * Totally public domain.
- */
-
-#include <sys/cdefs.h>
-#if defined(LIBC_SCCS) && !defined(lint)
-__RCSID("$NetBSD: tdelete.c,v 1.6 2012/06/25 22:32:45 abs Exp $");
-#endif /* LIBC_SCCS and not lint */
-
-#include <assert.h>
-#define _SEARCH_PRIVATE
-#include <search.h>
-#include <stdlib.h>
-
-
-/* find a node with key "vkey" in tree "vrootp" */
-void *
-tdelete(const void *vkey, void **vrootp,
-    int (*compar)(const void *, const void *))
-{
-	node_t **rootp = (node_t **)vrootp;
-	node_t *p, *q, *r;
-	int  cmp;
-
-	_DIAGASSERT(vkey != NULL);
-	_DIAGASSERT(compar != NULL);
-
-	if (rootp == NULL || (p = *rootp) == NULL)
-		return NULL;
-
-	while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) {
-		p = *rootp;
-		rootp = (cmp < 0) ?
-		    &(*rootp)->llink :		/* follow llink branch */
-		    &(*rootp)->rlink;		/* follow rlink branch */
-		if (*rootp == NULL)
-			return NULL;		/* key not found */
-	}
-	r = (*rootp)->rlink;			/* D1: */
-	if ((q = (*rootp)->llink) == NULL)	/* Left NULL? */
-		q = r;
-	else if (r != NULL) {			/* Right link is NULL? */
-		if (r->llink == NULL) {		/* D2: Find successor */
-			r->llink = q;
-			q = r;
-		} else {			/* D3: Find NULL link */
-			for (q = r->llink; q->llink != NULL; q = r->llink)
-				r = q;
-			r->llink = q->rlink;
-			q->llink = (*rootp)->llink;
-			q->rlink = (*rootp)->rlink;
-		}
-	}
-	if (p != *rootp)
-		free(*rootp);			/* D4: Free node */
-	*rootp = q;				/* link parent to new node */
-	return p;
-}
diff --git a/libc/upstream-netbsd/lib/libc/stdlib/tfind.c b/libc/upstream-netbsd/lib/libc/stdlib/tfind.c
deleted file mode 100644
index fd3f362..0000000
--- a/libc/upstream-netbsd/lib/libc/stdlib/tfind.c
+++ /dev/null
@@ -1,47 +0,0 @@
-/*	$NetBSD: tfind.c,v 1.7 2012/06/25 22:32:45 abs Exp $	*/
-
-/*
- * Tree search generalized from Knuth (6.2.2) Algorithm T just like
- * the AT&T man page says.
- *
- * The node_t structure is for internal use only, lint doesn't grok it.
- *
- * Written by reading the System V Interface Definition, not the code.
- *
- * Totally public domain.
- */
-
-#include <sys/cdefs.h>
-#if defined(LIBC_SCCS) && !defined(lint)
-__RCSID("$NetBSD: tfind.c,v 1.7 2012/06/25 22:32:45 abs Exp $");
-#endif /* LIBC_SCCS and not lint */
-
-#include <assert.h>
-#define _SEARCH_PRIVATE
-#include <stdlib.h>
-#include <search.h>
-
-/* find a node by key "vkey" in tree "vrootp", or return 0 */
-void *
-tfind(const void *vkey, void * const *vrootp,
-    int (*compar)(const void *, const void *))
-{
-	node_t * const *rootp = (node_t * const*)vrootp;
-
-	_DIAGASSERT(vkey != NULL);
-	_DIAGASSERT(compar != NULL);
-
-	if (rootp == NULL)
-		return NULL;
-
-	while (*rootp != NULL) {		/* T1: */
-		int r;
-
-		if ((r = (*compar)(vkey, (*rootp)->key)) == 0)	/* T2: */
-			return *rootp;		/* key found */
-		rootp = (r < 0) ?
-		    &(*rootp)->llink :		/* T3: follow left branch */
-		    &(*rootp)->rlink;		/* T4: follow right branch */
-	}
-	return NULL;
-}
diff --git a/libc/upstream-netbsd/lib/libc/stdlib/tsearch.c b/libc/upstream-netbsd/lib/libc/stdlib/tsearch.c
deleted file mode 100644
index af2fe9c..0000000
--- a/libc/upstream-netbsd/lib/libc/stdlib/tsearch.c
+++ /dev/null
@@ -1,56 +0,0 @@
-/*	$NetBSD: tsearch.c,v 1.7 2012/06/25 22:32:45 abs Exp $	*/
-
-/*
- * Tree search generalized from Knuth (6.2.2) Algorithm T just like
- * the AT&T man page says.
- *
- * The node_t structure is for internal use only, lint doesn't grok it.
- *
- * Written by reading the System V Interface Definition, not the code.
- *
- * Totally public domain.
- */
-
-#include <sys/cdefs.h>
-#if defined(LIBC_SCCS) && !defined(lint)
-__RCSID("$NetBSD: tsearch.c,v 1.7 2012/06/25 22:32:45 abs Exp $");
-#endif /* LIBC_SCCS and not lint */
-
-#include <assert.h>
-#define _SEARCH_PRIVATE
-#include <search.h>
-#include <stdlib.h>
-
-/* find or insert datum into search tree */
-void *
-tsearch(const void *vkey, void **vrootp,
-    int (*compar)(const void *, const void *))
-{
-	node_t *q;
-	node_t **rootp = (node_t **)vrootp;
-
-	_DIAGASSERT(vkey != NULL);
-	_DIAGASSERT(compar != NULL);
-
-	if (rootp == NULL)
-		return NULL;
-
-	while (*rootp != NULL) {	/* Knuth's T1: */
-		int r;
-
-		if ((r = (*compar)(vkey, (*rootp)->key)) == 0)	/* T2: */
-			return *rootp;		/* we found it! */
-
-		rootp = (r < 0) ?
-		    &(*rootp)->llink :		/* T3: follow left branch */
-		    &(*rootp)->rlink;		/* T4: follow right branch */
-	}
-
-	q = malloc(sizeof(node_t));		/* T5: key not found */
-	if (q != 0) {				/* make new node */
-		*rootp = q;			/* link new node to old */
-		q->key = __UNCONST(vkey);	/* initialize new node */
-		q->llink = q->rlink = NULL;
-	}
-	return q;
-}
diff --git a/libc/upstream-netbsd/lib/libc/stdlib/lsearch.c b/libc/upstream-openbsd/lib/libc/stdlib/lsearch.c
index e17130b..8cad05f 100644
--- a/libc/upstream-netbsd/lib/libc/stdlib/lsearch.c
+++ b/libc/upstream-openbsd/lib/libc/stdlib/lsearch.c
@@ -1,3 +1,5 @@
+/*	$OpenBSD: lsearch.c,v 1.5 2014/07/18 04:16:09 matthew Exp $	*/
+
 /*
  * Copyright (c) 1989, 1993
  *	The Regents of the University of California.  All rights reserved.
@@ -30,64 +32,39 @@
  * SUCH DAMAGE.
  */
 
-#include <sys/cdefs.h>
-#if defined(LIBC_SCCS) && !defined(lint)
-#if 0
-static char sccsid[] = "@(#)lsearch.c	8.1 (Berkeley) 6/4/93";
-#else
-__RCSID("$NetBSD: lsearch.c,v 1.7 2012/06/25 22:32:45 abs Exp $");
-#endif
-#endif /* LIBC_SCCS and not lint */
-
 #include <sys/types.h>
-
-#include <assert.h>
-#include <errno.h>
 #include <string.h>
 #include <search.h>
 
 typedef int (*cmp_fn_t)(const void *, const void *);
-static void *linear_base(const void *, void *, size_t *, size_t,
-			     cmp_fn_t, int);
+static void *linear_base(const void *, const void *, size_t *, size_t,
+    cmp_fn_t, int);
 
 void *
 lsearch(const void *key, void *base, size_t *nelp, size_t width,
-    cmp_fn_t compar)
+    	cmp_fn_t compar)
 {
 
-	_DIAGASSERT(key != NULL);
-	_DIAGASSERT(base != NULL);
-	_DIAGASSERT(compar != NULL);
-
 	return(linear_base(key, base, nelp, width, compar, 1));
 }
 
 void *
 lfind(const void *key, const void *base, size_t *nelp, size_t width,
-    cmp_fn_t compar)
+	cmp_fn_t compar)
 {
-
-	_DIAGASSERT(key != NULL);
-	_DIAGASSERT(base != NULL);
-	_DIAGASSERT(compar != NULL);
-
-	return(linear_base(key, __UNCONST(base), nelp, width, compar, 0));
+	return(linear_base(key, base, nelp, width, compar, 0));
 }
 
 static void *
-linear_base(const void *key, void *base, size_t *nelp, size_t width,
+linear_base(const void *key, const void *base, size_t *nelp, size_t width,
 	cmp_fn_t compar, int add_flag)
 {
-	char *element, *end;
-
-	_DIAGASSERT(key != NULL);
-	_DIAGASSERT(base != NULL);
-	_DIAGASSERT(compar != NULL);
+	const char *element, *end;
 
-	end = (char *)base + *nelp * width;
-	for (element = (char *)base; element < end; element += width)
-		if (!compar(element, key))		/* key found */
-			return element;
+	end = (const char *)base + *nelp * width;
+	for (element = base; element < end; element += width)
+		if (!compar(key, element))		/* key found */
+			return((void *)element);
 
 	if (!add_flag)					/* key not found */
 		return(NULL);
@@ -102,6 +79,6 @@ linear_base(const void *key, void *base, size_t *nelp, size_t width,
 	 * manual.
 	 */
 	++*nelp;
-	memcpy(end, key, width);
-	return end;
+	memcpy((void *)end, key, width);
+	return((void *)end);
 }
diff --git a/libc/upstream-openbsd/lib/libc/stdlib/tfind.c b/libc/upstream-openbsd/lib/libc/stdlib/tfind.c
new file mode 100644
index 0000000..0d1d519
--- /dev/null
+++ b/libc/upstream-openbsd/lib/libc/stdlib/tfind.c
@@ -0,0 +1,41 @@
+/*	$OpenBSD: tfind.c,v 1.6 2014/03/16 18:38:30 guenther Exp $	*/
+
+/*
+ * Tree search generalized from Knuth (6.2.2) Algorithm T just like
+ * the AT&T man page says.
+ *
+ * The node_t structure is for internal use only
+ *
+ * Written by reading the System V Interface Definition, not the code.
+ *
+ * Totally public domain.
+ */
+/*LINTLIBRARY*/
+#include <search.h>
+
+typedef struct node_t
+{
+    char	  *key;
+    struct node_t *llink, *rlink;
+} node;
+
+/* find a node, or return 0 */
+void *
+tfind(const void *vkey, void * const *vrootp,
+    int (*compar)(const void *, const void *))
+{
+    char *key = (char *)vkey;
+    node **rootp = (node **)vrootp;
+
+    if (rootp == (struct node_t **)0)
+	return ((struct node_t *)0);
+    while (*rootp != (struct node_t *)0) {	/* T1: */
+	int r;
+	if ((r = (*compar)(key, (*rootp)->key)) == 0)	/* T2: */
+	    return (*rootp);		/* key found */
+	rootp = (r < 0) ?
+	    &(*rootp)->llink :		/* T3: follow left branch */
+	    &(*rootp)->rlink;		/* T4: follow right branch */
+    }
+    return (node *)0;
+}
diff --git a/libc/upstream-openbsd/lib/libc/stdlib/tsearch.c b/libc/upstream-openbsd/lib/libc/stdlib/tsearch.c
new file mode 100644
index 0000000..a141085
--- /dev/null
+++ b/libc/upstream-openbsd/lib/libc/stdlib/tsearch.c
@@ -0,0 +1,119 @@
+/*	$OpenBSD: tsearch.c,v 1.8 2014/03/16 18:38:30 guenther Exp $	*/
+
+/*
+ * Tree search generalized from Knuth (6.2.2) Algorithm T just like
+ * the AT&T man page says.
+ *
+ * The node_t structure is for internal use only
+ *
+ * Written by reading the System V Interface Definition, not the code.
+ *
+ * Totally public domain.
+ */
+/*LINTLIBRARY*/
+
+#include <search.h>
+#include <stdlib.h>
+
+typedef struct node_t {
+    char	  *key;
+    struct node_t *left, *right;
+} node;
+
+/* find or insert datum into search tree */
+void *
+tsearch(const void *vkey, void **vrootp,
+    int (*compar)(const void *, const void *))
+{
+    node *q;
+    char *key = (char *)vkey;
+    node **rootp = (node **)vrootp;
+
+    if (rootp == (struct node_t **)0)
+	return ((void *)0);
+    while (*rootp != (struct node_t *)0) {	/* Knuth's T1: */
+	int r;
+
+	if ((r = (*compar)(key, (*rootp)->key)) == 0)	/* T2: */
+	    return ((void *)*rootp);		/* we found it! */
+	rootp = (r < 0) ?
+	    &(*rootp)->left :		/* T3: follow left branch */
+	    &(*rootp)->right;		/* T4: follow right branch */
+    }
+    q = (node *) malloc(sizeof(node));	/* T5: key not found */
+    if (q != (struct node_t *)0) {	/* make new node */
+	*rootp = q;			/* link new node to old */
+	q->key = key;			/* initialize new node */
+	q->left = q->right = (struct node_t *)0;
+    }
+    return ((void *)q);
+}
+
+/* delete node with given key */
+void *
+tdelete(const void *vkey, void **vrootp,
+    int (*compar)(const void *, const void *))
+{
+    node **rootp = (node **)vrootp;
+    char *key = (char *)vkey;
+    node *p = (node *)1;
+    node *q;
+    node *r;
+    int cmp;
+
+    if (rootp == (struct node_t **)0 || *rootp == (struct node_t *)0)
+	return ((struct node_t *)0);
+    while ((cmp = (*compar)(key, (*rootp)->key)) != 0) {
+	p = *rootp;
+	rootp = (cmp < 0) ?
+	    &(*rootp)->left :		/* follow left branch */
+	    &(*rootp)->right;		/* follow right branch */
+	if (*rootp == (struct node_t *)0)
+	    return ((void *)0);		/* key not found */
+    }
+    r = (*rootp)->right;			/* D1: */
+    if ((q = (*rootp)->left) == (struct node_t *)0)	/* Left (struct node_t *)0? */
+	q = r;
+    else if (r != (struct node_t *)0) {		/* Right link is null? */
+	if (r->left == (struct node_t *)0) {	/* D2: Find successor */
+	    r->left = q;
+	    q = r;
+	} else {			/* D3: Find (struct node_t *)0 link */
+	    for (q = r->left; q->left != (struct node_t *)0; q = r->left)
+		r = q;
+	    r->left = q->right;
+	    q->left = (*rootp)->left;
+	    q->right = (*rootp)->right;
+	}
+    }
+    free((struct node_t *) *rootp);	/* D4: Free node */
+    *rootp = q;				/* link parent to new node */
+    return(p);
+}
+
+/* Walk the nodes of a tree */
+static void
+trecurse(node *root, void (*action)(const void *, VISIT, int), int level)
+{
+    if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0)
+	(*action)(root, leaf, level);
+    else {
+	(*action)(root, preorder, level);
+	if (root->left != (struct node_t *)0)
+	    trecurse(root->left, action, level + 1);
+	(*action)(root, postorder, level);
+	if (root->right != (struct node_t *)0)
+	    trecurse(root->right, action, level + 1);
+	(*action)(root, endorder, level);
+    }
+}
+
+/* Walk the nodes of a tree */
+void
+twalk(const void *vroot, void (*action)(const void *, VISIT, int))
+{
+    node *root = (node *)vroot;
+
+    if (root != (node *)0 && action != (void (*)(const void *, VISIT, int))0)
+	trecurse(root, action, 0);
+}