1 /* Copyright (C) 1994 Free Software Foundation, Inc.
2 This file is part of the GNU C Library.
3
4 The GNU C Library is free software; you can redistribute it and/or
5 modify it under the terms of the GNU Library General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
8
9 The GNU C Library is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 Library General Public License for more details.
13
14 You should have received a copy of the GNU Library General Public
15 License along with the GNU C Library; see the file COPYING.LIB. If
16 not, see <http://www.gnu.org/licenses/>. */
17
18 /*
19 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
20 * the AT&T man page says.
21 *
22 * The node_t structure is for internal use only, lint doesn't grok it.
23 *
24 * Written by reading the System V Interface Definition, not the code.
25 *
26 * Totally public domain.
27 */
28 /*LINTLIBRARY*/
29
30 #include <search.h>
31 #include <stdlib.h>
32
33 /* This routine is not very bad. It makes many assumptions about
34 * the compiler. It assumpts that the first field in node must be
35 * the "key" field, which points to the datum. It is a very trick
36 * stuff. H.J.
37 */
38
39 typedef struct node_t
40 {
41 void *key;
42 struct node_t *left, *right;
43 } node;
44
45 #ifdef L_tsearch
46 /* find or insert datum into search tree.
47 char *key; key to be located
48 register node **rootp; address of tree root
49 int (*compar)(); ordering function
50 */
51
tsearch(const void * key,void ** vrootp,__compar_fn_t compar)52 void *tsearch(const void *key, void **vrootp, __compar_fn_t compar)
53 {
54 register node *q;
55 register node **rootp = (node **) vrootp;
56
57 if (rootp == (struct node_t **)0)
58 return ((struct node_t *)0);
59 while (*rootp != (struct node_t *)0) /* Knuth's T1: */
60 {
61 int r;
62
63 if ((r = (*compar)(key, (*rootp)->key)) == 0) /* T2: */
64 return (*rootp); /* we found it! */
65 rootp = (r < 0) ?
66 &(*rootp)->left : /* T3: follow left branch */
67 &(*rootp)->right; /* T4: follow right branch */
68 }
69 q = (node *) malloc(sizeof(node)); /* T5: key not found */
70 if (q != (struct node_t *)0) /* make new node */
71 {
72 *rootp = q; /* link new node to old */
73 q->key = (void *)key; /* initialize new node */
74 q->left = q->right = (struct node_t *)0;
75 }
76 return (q);
77 }
libc_hidden_def(tsearch)78 libc_hidden_def(tsearch)
79 #endif
80
81 #ifdef L_tfind
82 void *tfind(const void *key, void * const *vrootp, __compar_fn_t compar)
83 {
84 register node **rootp = (node **) vrootp;
85
86 if (rootp == (struct node_t **)0)
87 return ((struct node_t *)0);
88 while (*rootp != (struct node_t *)0) /* Knuth's T1: */
89 {
90 int r;
91
92 if ((r = (*compar)(key, (*rootp)->key)) == 0) /* T2: */
93 return (*rootp); /* we found it! */
94 rootp = (r < 0) ?
95 &(*rootp)->left : /* T3: follow left branch */
96 &(*rootp)->right; /* T4: follow right branch */
97 }
98 return NULL;
99 }
libc_hidden_def(tfind)100 libc_hidden_def(tfind)
101 #endif
102
103 #ifdef L_tdelete
104 /* delete node with given key
105 char *key; key to be deleted
106 register node **rootp; address of the root of tree
107 int (*compar)(); comparison function
108 */
109 void *tdelete(const void *key, void ** vrootp, __compar_fn_t compar)
110 {
111 node *p;
112 register node *q;
113 register node *r;
114 int cmp;
115 register node **rootp = (node **) vrootp;
116
117 if (rootp == (struct node_t **)0 || (p = *rootp) == (struct node_t *)0)
118 return ((struct node_t *)0);
119 while ((cmp = (*compar)(key, (*rootp)->key)) != 0)
120 {
121 p = *rootp;
122 rootp = (cmp < 0) ?
123 &(*rootp)->left : /* follow left branch */
124 &(*rootp)->right; /* follow right branch */
125 if (*rootp == (struct node_t *)0)
126 return ((struct node_t *)0); /* key not found */
127 }
128 r = (*rootp)->right; /* D1: */
129 if ((q = (*rootp)->left) == (struct node_t *)0) /* Left (struct node_t *)0? */
130 q = r;
131 else if (r != (struct node_t *)0) /* Right link is null? */
132 {
133 if (r->left == (struct node_t *)0) /* D2: Find successor */
134 {
135 r->left = q;
136 q = r;
137 }
138 else
139 { /* D3: Find (struct node_t *)0 link */
140 for (q = r->left; q->left != (struct node_t *)0; q = r->left)
141 r = q;
142 r->left = q->right;
143 q->left = (*rootp)->left;
144 q->right = (*rootp)->right;
145 }
146 }
147 free((struct node_t *) *rootp); /* D4: Free node */
148 *rootp = q; /* link parent to new node */
149 return(p);
150 }
151 #endif
152
153 #ifdef L_twalk
154 /* Walk the nodes of a tree
155 register node *root; Root of the tree to be walked
156 register void (*action)(); Function to be called at each node
157 register int level;
158 */
trecurse(const void * vroot,__action_fn_t action,int level)159 static void trecurse(const void *vroot, __action_fn_t action, int level)
160 {
161 register node *root = (node *) vroot;
162
163 if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0)
164 (*action)(root, leaf, level);
165 else
166 {
167 (*action)(root, preorder, level);
168 if (root->left != (struct node_t *)0)
169 trecurse(root->left, action, level + 1);
170 (*action)(root, postorder, level);
171 if (root->right != (struct node_t *)0)
172 trecurse(root->right, action, level + 1);
173 (*action)(root, endorder, level);
174 }
175 }
176
177 /* void twalk(root, action) Walk the nodes of a tree
178 node *root; Root of the tree to be walked
179 void (*action)(); Function to be called at each node
180 PTR
181 */
twalk(const void * vroot,__action_fn_t action)182 void twalk(const void *vroot, __action_fn_t action)
183 {
184 register const node *root = (node *) vroot;
185
186 if (root != (node *)0 && action != (__action_fn_t) 0)
187 trecurse(root, action, 0);
188 }
189 #endif
190
191 #ifdef __USE_GNU
192 #ifdef L_tdestroy
193 /* The standardized functions miss an important functionality: the
194 tree cannot be removed easily. We provide a function to do this. */
195 static void
196 internal_function
tdestroy_recurse(node * root,__free_fn_t freefct)197 tdestroy_recurse (node *root, __free_fn_t freefct)
198 {
199 if (root->left != NULL)
200 tdestroy_recurse (root->left, freefct);
201 if (root->right != NULL)
202 tdestroy_recurse (root->right, freefct);
203 (*freefct) ((void *) root->key);
204 /* Free the node itself. */
205 free (root);
206 }
207
tdestroy(void * vroot,__free_fn_t freefct)208 void tdestroy (void *vroot, __free_fn_t freefct)
209 {
210 node *root = (node *) vroot;
211 if (root != NULL) {
212 tdestroy_recurse (root, freefct);
213 }
214 }
215 libc_hidden_def(tdestroy)
216 #endif
217 #endif
218
219 /* tsearch.c ends here */
220