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