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