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
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 @@
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 @@
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 @@
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 @@
__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
similarity index 70%
rename from libc/upstream-netbsd/lib/libc/stdlib/lsearch.c
rename to 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;
+ const 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;
+ 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 @@
* 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);
+}