4 files changed, 174 insertions, 4 deletions

diff --git a/src/lib/libc/stdlib/Makefile.inc b/src/lib/libc/stdlib/Makefile.inc
index f224baed54..4c7f9db834 100644
--- a/src/lib/libc/stdlib/Makefile.inc
+++ b/src/lib/libc/stdlib/Makefile.inc
@@ -1,4 +1,4 @@
-#       $OpenBSD: Makefile.inc,v 1.6 1996/08/21 03:47:21 tholo Exp $
+#       $OpenBDS: Makefile.inc,v 1.6 1996/08/21 03:47:21 tholo Exp $
 
 # stdlib sources
 .PATH: ${.CURDIR}/arch/${MACHINE_ARCH}/stdlib ${.CURDIR}/stdlib
@@ -7,6 +7,7 @@ SRCS+=	a64l.c abort.c atexit.c atoi.c atof.c atol.c bsearch.c calloc.c \
         cfree.c exit.c getenv.c getopt.c heapsort.c l64a.c malloc.c merge.c \
         multibyte.c putenv.c qsort.c radixsort.c rand.c random.c realpath.c \
         setenv.c strtod.c strtol.c strtoq.c strtoul.c strtouq.c system.c \
+        tfind.c tsearch.c \
         _rand48.c drand48.c erand48.c jrand48.c lcong48.c lrand48.c \
         mrand48.c nrand48.c seed48.c srand48.c qabs.c qdiv.c
 
@@ -34,7 +35,7 @@ SRCS+=	abs.c div.c labs.c ldiv.c
 MAN+=   abort.3 abs.3 alloca.3 atexit.3 atof.3 atoi.3 atol.3 bsearch.3 \
         calloc.3 div.3 exit.3 getenv.3 getopt.3 labs.3 ldiv.3 malloc.3 \
         memory.3 qabs.3 qdiv.3 qsort.3 radixsort.3 rand48.3 rand.3 \
-        random.3 realpath.3 strtod.3 strtol.3 strtoul.3 system.3
+        random.3 realpath.3 strtod.3 strtol.3 strtoul.3 system.3 tsearch.3
 
 MLINKS+=getenv.3 setenv.3 getenv.3 unsetenv.3 getenv.3 putenv.3
 MLINKS+=malloc.3 free.3 malloc.3 realloc.3
@@ -47,3 +48,6 @@ MLINKS+=rand48.3 mrand48.3 rand48.3 nrand48.3 rand48.3 jrand48.3
 MLINKS+=rand48.3 srand48.3 rand48.3 seed48.3 rand48.3 lcong48.3
 MLINKS+=strtol.3 strtoq.3
 MLINKS+=strtoul.3 strtouq.3
+MLINKS+=tsearch.3 tfind.3
+MLINKS+=tsearch.3 tdelete.3
+MLINKS+=tsearch.3 twalk.3
diff --git a/src/lib/libc/stdlib/bsearch.3 b/src/lib/libc/stdlib/bsearch.3
index 7cfa7162d3..570a4227b4 100644
--- a/src/lib/libc/stdlib/bsearch.3
+++ b/src/lib/libc/stdlib/bsearch.3
@@ -33,7 +33,7 @@
 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 .\" SUCH DAMAGE.
 .\"
-.\"     $OpenBSD: bsearch.3,v 1.2 1996/08/10 04:52:52 tholo Exp $
+.\"     $OpenBSD: bsearch.3,v 1.3 1997/06/13 23:41:35 deraadt Exp $
 .\"
 .Dd April 19, 1994
 .Dt BSEARCH 3
@@ -82,7 +82,7 @@ If two members compare as equal, which member is matched is unspecified.
 .Xr db 3 ,
 .Xr lsearch 3 ,
 .Xr qsort 3 ,
-.\" .Xr tsearch 3
+.Xr tsearch 3
 .Sh STANDARDS
 The
 .Fn bsearch
diff --git a/src/lib/libc/stdlib/tfind.c b/src/lib/libc/stdlib/tfind.c
new file mode 100644
index 0000000000..8e77527bf5
--- /dev/null
+++ b/src/lib/libc/stdlib/tfind.c
@@ -0,0 +1,41 @@
+/*
+ * 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.
+ */
+/*LINTLIBRARY*/
+#include <search.h>
+
+typedef struct node_t
+{
+    char          *key;
+    struct node_t *llink, *rlink;
+} node;
+
+/* find a node, or return 0 */
+void *
+tfind(vkey, vrootp, compar)
+        const void      *vkey;          /* key to be found */
+        void            **vrootp;       /* address of the tree root */
+        int             (*compar) __P((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/src/lib/libc/stdlib/tsearch.c b/src/lib/libc/stdlib/tsearch.c
new file mode 100644
index 0000000000..defa8a3006
--- /dev/null
+++ b/src/lib/libc/stdlib/tsearch.c
@@ -0,0 +1,125 @@
+/*
+ * 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.
+ */
+/*LINTLIBRARY*/
+
+#include <search.h>
+
+typedef struct node_t {
+    char          *key;
+    struct node_t *left, *right;
+} node;
+
+/* find or insert datum into search tree */
+void *
+tsearch(vkey, vrootp, compar)
+        const void      *vkey;          /* key to be located */
+        void            **vrootp;       /* address of tree root */
+        int             (*compar) __P((const void *, const void *));
+{
+    register 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(vkey, vrootp, compar)
+        const void      *vkey;          /* key to be deleted */
+        void            **vrootp;       /* address of the root of tree */
+        int             (*compar) __P((const void *, const void *));
+{
+    node **rootp = (node **)vrootp;
+    char *key = (char *)vkey;
+    node *p;
+    register node *q;
+    register node *r;
+    int cmp;
+
+    if (rootp == (struct node_t **)0 || (p = *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(root, action, level)
+        register node   *root;          /* Root of the tree to be walked */
+        register void   (*action)();    /* Function to be called at each node */
+        register 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(vroot, action)
+        const void      *vroot;         /* Root of the tree to be walked */
+        void            (*action) __P((const void *, VISIT, int));
+{
+    node *root = (node *)vroot;
+
+    if (root != (node *)0 && action != (void(*)())0)
+        trecurse(root, action, 0);
+}