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

(cherry picked from commit 3e424d0a241f8ae5194514dabc4ad899f5a5416d)

Change-Id: I5882a6b48c80fea8ac6b9c27e7b9de10b202b4ff

6 files changed, 111 insertions, 277 deletions

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 000000000..09020ae2a
--- /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/lsearch.c b/libc/upstream-netbsd/lib/libc/stdlib/lsearch.c
deleted file mode 100644
index e17130b63..000000000
--- a/libc/upstream-netbsd/lib/libc/stdlib/lsearch.c
+++ /dev/null
@@ -1,107 +0,0 @@
-/*
- * Copyright (c) 1989, 1993
- *	The Regents of the University of California.  All rights reserved.
- *
- * This code is derived from software contributed to Berkeley by
- * Roger L. Snyder.
- *
- * 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. Neither the name of the University nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``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 REGENTS OR CONTRIBUTORS 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)
-#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);
-
-void *
-lsearch(const void *key, void *base, size_t *nelp, size_t width,
-    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)
-{
-
-	_DIAGASSERT(key != NULL);
-	_DIAGASSERT(base != NULL);
-	_DIAGASSERT(compar != NULL);
-
-	return(linear_base(key, __UNCONST(base), nelp, width, compar, 0));
-}
-
-static void *
-linear_base(const void *key, 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);
-
-	end = (char *)base + *nelp * width;
-	for (element = (char *)base; element < end; element += width)
-		if (!compar(element, key))		/* key found */
-			return element;
-
-	if (!add_flag)					/* key not found */
-		return(NULL);
-
-	/*
-	 * The UNIX System User's Manual, 1986 edition claims that
-	 * a NULL pointer is returned by lsearch with errno set
-	 * appropriately, if there is not enough room in the table
-	 * to add a new item.  This can't be done as none of these
-	 * routines have any method of determining the size of the
-	 * table.  This comment isn't in the 1986-87 System V
-	 * manual.
-	 */
-	++*nelp;
-	memcpy(end, key, width);
-	return end;
-}
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 000000000..6060ad84b
--- /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 84017dc0e..000000000
--- 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 fd3f362a7..000000000
--- 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 af2fe9c22..000000000
--- 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;
-}