1 /*%
2 * tree - balanced binary tree library
3 *
4 * vix 05apr94 [removed vixie.h dependencies; cleaned up formatting, names]
5 * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes]
6 * vix 23jun86 [added delete uar to add for replaced nodes]
7 * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224]
8 * vix 06feb86 [added tree_mung()]
9 * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221]
10 * vix 14dec85 [written]
11 */
12
13 /*%
14 * This program text was created by Paul Vixie using examples from the book:
15 * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN
16 * 0-13-022005-1. Any errors in the conversion from Modula-2 to C are Paul
17 * Vixie's.
18 */
19
20 /*
21 * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC")
22 * Portions Copyright (c) 1996-1999 by Internet Software Consortium.
23 *
24 * Permission to use, copy, modify, and distribute this software for any
25 * purpose with or without fee is hereby granted, provided that the above
26 * copyright notice and this permission notice appear in all copies.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
29 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
30 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR
31 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
32 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
33 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
34 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
35 */
36
37 /*#define DEBUG "tree"*/
38
39 #include "port_before.h"
40
41 #include <stdio.h>
42 #include <stdlib.h>
43
44 #include "port_after.h"
45
46 #include <isc/memcluster.h>
47 #include <isc/tree.h>
48
49 #ifdef DEBUG
50 static int debugDepth = 0;
51 static char *debugFuncs[256];
52 # define ENTER(proc) { \
53 debugFuncs[debugDepth] = proc; \
54 fprintf(stderr, "ENTER(%d:%s.%s)\n", \
55 debugDepth, DEBUG, \
56 debugFuncs[debugDepth]); \
57 debugDepth++; \
58 }
59 # define RET(value) { \
60 debugDepth--; \
61 fprintf(stderr, "RET(%d:%s.%s)\n", \
62 debugDepth, DEBUG, \
63 debugFuncs[debugDepth]); \
64 return (value); \
65 }
66 # define RETV { \
67 debugDepth--; \
68 fprintf(stderr, "RETV(%d:%s.%s)\n", \
69 debugDepth, DEBUG, \
70 debugFuncs[debugDepth]); \
71 return; \
72 }
73 # define MSG(msg) fprintf(stderr, "MSG(%s)\n", msg);
74 #else
75 # define ENTER(proc) ;
76 # define RET(value) return (value);
77 # define RETV return;
78 # define MSG(msg) ;
79 #endif
80
81 #ifndef TRUE
82 # define TRUE 1
83 # define FALSE 0
84 #endif
85
86 static tree * sprout(tree **, tree_t, int *, int (*)(), void (*)());
87 static int delete(tree **, int (*)(), tree_t, void (*)(), int *, int *);
88 static void del(tree **, int *, tree **, void (*)(), int *);
89 static void bal_L(tree **, int *);
90 static void bal_R(tree **, int *);
91
92 void
tree_init(tree ** ppr_tree)93 tree_init(tree **ppr_tree) {
94 ENTER("tree_init")
95 *ppr_tree = NULL;
96 RETV
97 }
98
99 tree_t
tree_srch(tree ** ppr_tree,int (* pfi_compare)(tree_t,tree_t),tree_t p_user)100 tree_srch(tree **ppr_tree, int (*pfi_compare)(tree_t, tree_t), tree_t p_user) {
101 ENTER("tree_srch")
102
103 if (*ppr_tree) {
104 int i_comp = (*pfi_compare)(p_user, (**ppr_tree).data);
105
106 if (i_comp > 0)
107 RET(tree_srch(&(**ppr_tree).right,
108 pfi_compare,
109 p_user))
110
111 if (i_comp < 0)
112 RET(tree_srch(&(**ppr_tree).left,
113 pfi_compare,
114 p_user))
115
116 /* not higher, not lower... this must be the one.
117 */
118 RET((**ppr_tree).data)
119 }
120
121 /* grounded. NOT found.
122 */
123 RET(NULL)
124 }
125
126 tree_t
tree_add(tree ** ppr_tree,int (* pfi_compare)(tree_t,tree_t),tree_t p_user,void (* pfv_uar)())127 tree_add(tree **ppr_tree, int (*pfi_compare)(tree_t, tree_t),
128 tree_t p_user, void (*pfv_uar)())
129 {
130 int i_balance = FALSE;
131
132 ENTER("tree_add")
133 if (!sprout(ppr_tree, p_user, &i_balance, pfi_compare, pfv_uar))
134 RET(NULL)
135 RET(p_user)
136 }
137
138 int
tree_delete(tree ** ppr_p,int (* pfi_compare)(tree_t,tree_t),tree_t p_user,void (* pfv_uar)())139 tree_delete(tree **ppr_p, int (*pfi_compare)(tree_t, tree_t),
140 tree_t p_user, void (*pfv_uar)())
141 {
142 int i_balance = FALSE, i_uar_called = FALSE;
143
144 ENTER("tree_delete");
145 RET(delete(ppr_p, pfi_compare, p_user, pfv_uar,
146 &i_balance, &i_uar_called))
147 }
148
149 int
tree_trav(tree ** ppr_tree,int (* pfi_uar)(tree_t))150 tree_trav(tree **ppr_tree, int (*pfi_uar)(tree_t)) {
151 ENTER("tree_trav")
152
153 if (!*ppr_tree)
154 RET(TRUE)
155
156 if (!tree_trav(&(**ppr_tree).left, pfi_uar))
157 RET(FALSE)
158 if (!(*pfi_uar)((**ppr_tree).data))
159 RET(FALSE)
160 if (!tree_trav(&(**ppr_tree).right, pfi_uar))
161 RET(FALSE)
162 RET(TRUE)
163 }
164
165 void
tree_mung(tree ** ppr_tree,void (* pfv_uar)(tree_t))166 tree_mung(tree **ppr_tree, void (*pfv_uar)(tree_t)) {
167 ENTER("tree_mung")
168 if (*ppr_tree) {
169 tree_mung(&(**ppr_tree).left, pfv_uar);
170 tree_mung(&(**ppr_tree).right, pfv_uar);
171 if (pfv_uar)
172 (*pfv_uar)((**ppr_tree).data);
173 memput(*ppr_tree, sizeof(tree));
174 *ppr_tree = NULL;
175 }
176 RETV
177 }
178
179 static tree *
sprout(tree ** ppr,tree_t p_data,int * pi_balance,int (* pfi_compare)(tree_t,tree_t),void (* pfv_delete)(tree_t))180 sprout(tree **ppr, tree_t p_data, int *pi_balance,
181 int (*pfi_compare)(tree_t, tree_t), void (*pfv_delete)(tree_t))
182 {
183 tree *p1, *p2, *sub;
184 int cmp;
185
186 ENTER("sprout")
187
188 /* are we grounded? if so, add the node "here" and set the rebalance
189 * flag, then exit.
190 */
191 if (!*ppr) {
192 MSG("grounded. adding new node, setting h=true")
193 *ppr = (tree *) memget(sizeof(tree));
194 if (*ppr) {
195 (*ppr)->left = NULL;
196 (*ppr)->right = NULL;
197 (*ppr)->bal = 0;
198 (*ppr)->data = p_data;
199 *pi_balance = TRUE;
200 }
201 RET(*ppr);
202 }
203
204 /* compare the data using routine passed by caller.
205 */
206 cmp = (*pfi_compare)(p_data, (*ppr)->data);
207
208 /* if LESS, prepare to move to the left.
209 */
210 if (cmp < 0) {
211 MSG("LESS. sprouting left.")
212 sub = sprout(&(*ppr)->left, p_data, pi_balance,
213 pfi_compare, pfv_delete);
214 if (sub && *pi_balance) { /*%< left branch has grown */
215 MSG("LESS: left branch has grown")
216 switch ((*ppr)->bal) {
217 case 1:
218 /* right branch WAS longer; bal is ok now */
219 MSG("LESS: case 1.. bal restored implicitly")
220 (*ppr)->bal = 0;
221 *pi_balance = FALSE;
222 break;
223 case 0:
224 /* balance WAS okay; now left branch longer */
225 MSG("LESS: case 0.. balnce bad but still ok")
226 (*ppr)->bal = -1;
227 break;
228 case -1:
229 /* left branch was already too long. rebal */
230 MSG("LESS: case -1: rebalancing")
231 p1 = (*ppr)->left;
232 if (p1->bal == -1) { /*%< LL */
233 MSG("LESS: single LL")
234 (*ppr)->left = p1->right;
235 p1->right = *ppr;
236 (*ppr)->bal = 0;
237 *ppr = p1;
238 } else { /*%< double LR */
239 MSG("LESS: double LR")
240
241 p2 = p1->right;
242 p1->right = p2->left;
243 p2->left = p1;
244
245 (*ppr)->left = p2->right;
246 p2->right = *ppr;
247
248 if (p2->bal == -1)
249 (*ppr)->bal = 1;
250 else
251 (*ppr)->bal = 0;
252
253 if (p2->bal == 1)
254 p1->bal = -1;
255 else
256 p1->bal = 0;
257 *ppr = p2;
258 } /*else*/
259 (*ppr)->bal = 0;
260 *pi_balance = FALSE;
261 } /*switch*/
262 } /*if*/
263 RET(sub)
264 } /*if*/
265
266 /* if MORE, prepare to move to the right.
267 */
268 if (cmp > 0) {
269 MSG("MORE: sprouting to the right")
270 sub = sprout(&(*ppr)->right, p_data, pi_balance,
271 pfi_compare, pfv_delete);
272 if (sub && *pi_balance) {
273 MSG("MORE: right branch has grown")
274
275 switch ((*ppr)->bal) {
276 case -1:
277 MSG("MORE: balance was off, fixed implicitly")
278 (*ppr)->bal = 0;
279 *pi_balance = FALSE;
280 break;
281 case 0:
282 MSG("MORE: balance was okay, now off but ok")
283 (*ppr)->bal = 1;
284 break;
285 case 1:
286 MSG("MORE: balance was off, need to rebalance")
287 p1 = (*ppr)->right;
288 if (p1->bal == 1) { /*%< RR */
289 MSG("MORE: single RR")
290 (*ppr)->right = p1->left;
291 p1->left = *ppr;
292 (*ppr)->bal = 0;
293 *ppr = p1;
294 } else { /*%< double RL */
295 MSG("MORE: double RL")
296
297 p2 = p1->left;
298 p1->left = p2->right;
299 p2->right = p1;
300
301 (*ppr)->right = p2->left;
302 p2->left = *ppr;
303
304 if (p2->bal == 1)
305 (*ppr)->bal = -1;
306 else
307 (*ppr)->bal = 0;
308
309 if (p2->bal == -1)
310 p1->bal = 1;
311 else
312 p1->bal = 0;
313
314 *ppr = p2;
315 } /*else*/
316 (*ppr)->bal = 0;
317 *pi_balance = FALSE;
318 } /*switch*/
319 } /*if*/
320 RET(sub)
321 } /*if*/
322
323 /* not less, not more: this is the same key! replace...
324 */
325 MSG("FOUND: Replacing data value")
326 *pi_balance = FALSE;
327 if (pfv_delete)
328 (*pfv_delete)((*ppr)->data);
329 (*ppr)->data = p_data;
330 RET(*ppr)
331 }
332
333 static int
delete(tree ** ppr_p,int (* pfi_compare)(tree_t,tree_t),tree_t p_user,void (* pfv_uar)(tree_t),int * pi_balance,int * pi_uar_called)334 delete(tree **ppr_p, int (*pfi_compare)(tree_t, tree_t), tree_t p_user,
335 void (*pfv_uar)(tree_t), int *pi_balance, int *pi_uar_called)
336 {
337 tree *pr_q;
338 int i_comp, i_ret;
339
340 ENTER("delete")
341
342 if (*ppr_p == NULL) {
343 MSG("key not in tree")
344 RET(FALSE)
345 }
346
347 i_comp = (*pfi_compare)((*ppr_p)->data, p_user);
348 if (i_comp > 0) {
349 MSG("too high - scan left")
350 i_ret = delete(&(*ppr_p)->left, pfi_compare, p_user, pfv_uar,
351 pi_balance, pi_uar_called);
352 if (*pi_balance)
353 bal_L(ppr_p, pi_balance);
354 } else if (i_comp < 0) {
355 MSG("too low - scan right")
356 i_ret = delete(&(*ppr_p)->right, pfi_compare, p_user, pfv_uar,
357 pi_balance, pi_uar_called);
358 if (*pi_balance)
359 bal_R(ppr_p, pi_balance);
360 } else {
361 MSG("equal")
362 pr_q = *ppr_p;
363 if (pr_q->right == NULL) {
364 MSG("right subtree null")
365 *ppr_p = pr_q->left;
366 *pi_balance = TRUE;
367 } else if (pr_q->left == NULL) {
368 MSG("right subtree non-null, left subtree null")
369 *ppr_p = pr_q->right;
370 *pi_balance = TRUE;
371 } else {
372 MSG("neither subtree null")
373 del(&pr_q->left, pi_balance, &pr_q,
374 pfv_uar, pi_uar_called);
375 if (*pi_balance)
376 bal_L(ppr_p, pi_balance);
377 }
378 if (!*pi_uar_called && pfv_uar)
379 (*pfv_uar)(pr_q->data);
380 /* Thanks to wuth@castrov.cuc.ab.ca for the following stmt. */
381 memput(pr_q, sizeof(tree));
382 i_ret = TRUE;
383 }
384 RET(i_ret)
385 }
386
387 static void
del(tree ** ppr_r,int * pi_balance,tree ** ppr_q,void (* pfv_uar)(tree_t),int * pi_uar_called)388 del(tree **ppr_r, int *pi_balance, tree **ppr_q,
389 void (*pfv_uar)(tree_t), int *pi_uar_called)
390 {
391 ENTER("del")
392
393 if ((*ppr_r)->right != NULL) {
394 del(&(*ppr_r)->right, pi_balance, ppr_q,
395 pfv_uar, pi_uar_called);
396 if (*pi_balance)
397 bal_R(ppr_r, pi_balance);
398 } else {
399 if (pfv_uar)
400 (*pfv_uar)((*ppr_q)->data);
401 *pi_uar_called = TRUE;
402 (*ppr_q)->data = (*ppr_r)->data;
403 *ppr_q = *ppr_r;
404 *ppr_r = (*ppr_r)->left;
405 *pi_balance = TRUE;
406 }
407
408 RETV
409 }
410
411 static void
bal_L(tree ** ppr_p,int * pi_balance)412 bal_L(tree **ppr_p, int *pi_balance) {
413 tree *p1, *p2;
414 int b1, b2;
415
416 ENTER("bal_L")
417 MSG("left branch has shrunk")
418
419 switch ((*ppr_p)->bal) {
420 case -1:
421 MSG("was imbalanced, fixed implicitly")
422 (*ppr_p)->bal = 0;
423 break;
424 case 0:
425 MSG("was okay, is now one off")
426 (*ppr_p)->bal = 1;
427 *pi_balance = FALSE;
428 break;
429 case 1:
430 MSG("was already off, this is too much")
431 p1 = (*ppr_p)->right;
432 b1 = p1->bal;
433 if (b1 >= 0) {
434 MSG("single RR")
435 (*ppr_p)->right = p1->left;
436 p1->left = *ppr_p;
437 if (b1 == 0) {
438 MSG("b1 == 0")
439 (*ppr_p)->bal = 1;
440 p1->bal = -1;
441 *pi_balance = FALSE;
442 } else {
443 MSG("b1 != 0")
444 (*ppr_p)->bal = 0;
445 p1->bal = 0;
446 }
447 *ppr_p = p1;
448 } else {
449 MSG("double RL")
450 p2 = p1->left;
451 b2 = p2->bal;
452 p1->left = p2->right;
453 p2->right = p1;
454 (*ppr_p)->right = p2->left;
455 p2->left = *ppr_p;
456 if (b2 == 1)
457 (*ppr_p)->bal = -1;
458 else
459 (*ppr_p)->bal = 0;
460 if (b2 == -1)
461 p1->bal = 1;
462 else
463 p1->bal = 0;
464 *ppr_p = p2;
465 p2->bal = 0;
466 }
467 }
468 RETV
469 }
470
471 static void
bal_R(tree ** ppr_p,int * pi_balance)472 bal_R(tree **ppr_p, int *pi_balance) {
473 tree *p1, *p2;
474 int b1, b2;
475
476 ENTER("bal_R")
477 MSG("right branch has shrunk")
478 switch ((*ppr_p)->bal) {
479 case 1:
480 MSG("was imbalanced, fixed implicitly")
481 (*ppr_p)->bal = 0;
482 break;
483 case 0:
484 MSG("was okay, is now one off")
485 (*ppr_p)->bal = -1;
486 *pi_balance = FALSE;
487 break;
488 case -1:
489 MSG("was already off, this is too much")
490 p1 = (*ppr_p)->left;
491 b1 = p1->bal;
492 if (b1 <= 0) {
493 MSG("single LL")
494 (*ppr_p)->left = p1->right;
495 p1->right = *ppr_p;
496 if (b1 == 0) {
497 MSG("b1 == 0")
498 (*ppr_p)->bal = -1;
499 p1->bal = 1;
500 *pi_balance = FALSE;
501 } else {
502 MSG("b1 != 0")
503 (*ppr_p)->bal = 0;
504 p1->bal = 0;
505 }
506 *ppr_p = p1;
507 } else {
508 MSG("double LR")
509 p2 = p1->right;
510 b2 = p2->bal;
511 p1->right = p2->left;
512 p2->left = p1;
513 (*ppr_p)->left = p2->right;
514 p2->right = *ppr_p;
515 if (b2 == -1)
516 (*ppr_p)->bal = 1;
517 else
518 (*ppr_p)->bal = 0;
519 if (b2 == 1)
520 p1->bal = -1;
521 else
522 p1->bal = 0;
523 *ppr_p = p2;
524 p2->bal = 0;
525 }
526 }
527 RETV
528 }
529
530 /*! \file */
531