1 /* $OpenBSD: tsearch.c,v 1.10 2015/09/26 16:03:48 guenther Exp $ */
2
3 /*
4 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
5 * the AT&T man page says.
6 *
7 * The node_t structure is for internal use only
8 *
9 * Written by reading the System V Interface Definition, not the code.
10 *
11 * Totally public domain.
12 */
13
14 #include <search.h>
15 #include <stdlib.h>
16
17 typedef struct node_t {
18 char *key;
19 struct node_t *left, *right;
20 } node;
21
22 /* find or insert datum into search tree */
23 void *
tsearch(const void * vkey,void ** vrootp,int (* compar)(const void *,const void *))24 tsearch(const void *vkey, void **vrootp,
25 int (*compar)(const void *, const void *))
26 {
27 node *q;
28 char *key = (char *)vkey;
29 node **rootp = (node **)vrootp;
30
31 if (rootp == (struct node_t **)0)
32 return ((void *)0);
33 while (*rootp != (struct node_t *)0) { /* Knuth's T1: */
34 int r;
35
36 if ((r = (*compar)(key, (*rootp)->key)) == 0) /* T2: */
37 return ((void *)*rootp); /* we found it! */
38 rootp = (r < 0) ?
39 &(*rootp)->left : /* T3: follow left branch */
40 &(*rootp)->right; /* T4: follow right branch */
41 }
42 q = malloc(sizeof(node)); /* T5: key not found */
43 if (q != (struct node_t *)0) { /* make new node */
44 *rootp = q; /* link new node to old */
45 q->key = key; /* initialize new node */
46 q->left = q->right = (struct node_t *)0;
47 }
48 return ((void *)q);
49 }
50
51 /* delete node with given key */
52 void *
tdelete(const void * vkey,void ** vrootp,int (* compar)(const void *,const void *))53 tdelete(const void *vkey, void **vrootp,
54 int (*compar)(const void *, const void *))
55 {
56 node **rootp = (node **)vrootp;
57 char *key = (char *)vkey;
58 node *p = (node *)1;
59 node *q;
60 node *r;
61 int cmp;
62
63 if (rootp == (struct node_t **)0 || *rootp == (struct node_t *)0)
64 return ((struct node_t *)0);
65 while ((cmp = (*compar)(key, (*rootp)->key)) != 0) {
66 p = *rootp;
67 rootp = (cmp < 0) ?
68 &(*rootp)->left : /* follow left branch */
69 &(*rootp)->right; /* follow right branch */
70 if (*rootp == (struct node_t *)0)
71 return ((void *)0); /* key not found */
72 }
73 r = (*rootp)->right; /* D1: */
74 if ((q = (*rootp)->left) == (struct node_t *)0) /* Left (struct node_t *)0? */
75 q = r;
76 else if (r != (struct node_t *)0) { /* Right link is null? */
77 if (r->left == (struct node_t *)0) { /* D2: Find successor */
78 r->left = q;
79 q = r;
80 } else { /* D3: Find (struct node_t *)0 link */
81 for (q = r->left; q->left != (struct node_t *)0; q = r->left)
82 r = q;
83 r->left = q->right;
84 q->left = (*rootp)->left;
85 q->right = (*rootp)->right;
86 }
87 }
88 free((struct node_t *) *rootp); /* D4: Free node */
89 *rootp = q; /* link parent to new node */
90 return(p);
91 }
92
93 /* Walk the nodes of a tree */
94 static void
trecurse(node * root,void (* action)(const void *,VISIT,int),int level)95 trecurse(node *root, void (*action)(const void *, VISIT, int), int level)
96 {
97 if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0)
98 (*action)(root, leaf, level);
99 else {
100 (*action)(root, preorder, level);
101 if (root->left != (struct node_t *)0)
102 trecurse(root->left, action, level + 1);
103 (*action)(root, postorder, level);
104 if (root->right != (struct node_t *)0)
105 trecurse(root->right, action, level + 1);
106 (*action)(root, endorder, level);
107 }
108 }
109
110 /* Walk the nodes of a tree */
111 void
twalk(const void * vroot,void (* action)(const void *,VISIT,int))112 twalk(const void *vroot, void (*action)(const void *, VISIT, int))
113 {
114 node *root = (node *)vroot;
115
116 if (root != (node *)0 && action != (void (*)(const void *, VISIT, int))0)
117 trecurse(root, action, 0);
118 }
119