1 files changed, 119 insertions, 0 deletions

diff --git a/src/lib/libc/stdlib/tsearch.c b/src/lib/libc/stdlib/tsearch.c
new file mode 100644
index 0000000000..a141085d2b
--- /dev/null
+++ b/src/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);
+}