2 static const char rcsid[] = "$Id: tree.c,v 1.2.206.1 2004/03/09 08:33:43 marka Exp $";
6 * tree - balanced binary tree library
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]
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
25 * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC")
26 * Portions Copyright (c) 1996-1999 by Internet Software Consortium.
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.
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.
41 /*#define DEBUG "tree"*/
43 #include "port_before.h"
48 #include "port_after.h"
50 #include <isc/memcluster.h>
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", \
60 debugFuncs[debugDepth]); \
63 # define RET(value) { \
65 fprintf(stderr, "RET(%d:%s.%s)\n", \
67 debugFuncs[debugDepth]); \
72 fprintf(stderr, "RETV(%d:%s.%s)\n", \
74 debugFuncs[debugDepth]); \
77 # define MSG(msg) fprintf(stderr, "MSG(%s)\n", msg);
79 # define ENTER(proc) ;
80 # define RET(value) return (value);
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 *);
97 tree_init(tree **ppr_tree) {
104 tree_srch(tree **ppr_tree, int (*pfi_compare)(tree_t, tree_t), tree_t p_user) {
108 int i_comp = (*pfi_compare)(p_user, (**ppr_tree).data);
111 RET(tree_srch(&(**ppr_tree).right,
116 RET(tree_srch(&(**ppr_tree).left,
120 /* not higher, not lower... this must be the one.
122 RET((**ppr_tree).data)
125 /* grounded. NOT found.
131 tree_add(tree **ppr_tree, int (*pfi_compare)(tree_t, tree_t),
132 tree_t p_user, void (*pfv_uar)())
134 int i_balance = FALSE;
137 if (!sprout(ppr_tree, p_user, &i_balance, pfi_compare, pfv_uar))
143 tree_delete(tree **ppr_p, int (*pfi_compare)(tree_t, tree_t),
144 tree_t p_user, void (*pfv_uar)())
146 int i_balance = FALSE, i_uar_called = FALSE;
148 ENTER("tree_delete");
149 RET(delete(ppr_p, pfi_compare, p_user, pfv_uar,
150 &i_balance, &i_uar_called))
154 tree_trav(tree **ppr_tree, int (*pfi_uar)(tree_t)) {
160 if (!tree_trav(&(**ppr_tree).left, pfi_uar))
162 if (!(*pfi_uar)((**ppr_tree).data))
164 if (!tree_trav(&(**ppr_tree).right, pfi_uar))
170 tree_mung(tree **ppr_tree, void (*pfv_uar)(tree_t)) {
173 tree_mung(&(**ppr_tree).left, pfv_uar);
174 tree_mung(&(**ppr_tree).right, pfv_uar);
176 (*pfv_uar)((**ppr_tree).data);
177 memput(*ppr_tree, sizeof(tree));
184 sprout(tree **ppr, tree_t p_data, int *pi_balance,
185 int (*pfi_compare)(tree_t, tree_t), void (*pfv_delete)(tree_t))
192 /* are we grounded? if so, add the node "here" and set the rebalance
196 MSG("grounded. adding new node, setting h=true")
197 *ppr = (tree *) memget(sizeof(tree));
200 (*ppr)->right = NULL;
202 (*ppr)->data = p_data;
208 /* compare the data using routine passed by caller.
210 cmp = (*pfi_compare)(p_data, (*ppr)->data);
212 /* if LESS, prepare to move to the left.
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) {
222 /* right branch WAS longer; bal is ok now */
223 MSG("LESS: case 1.. bal restored implicitly")
228 /* balance WAS okay; now left branch longer */
229 MSG("LESS: case 0.. balnce bad but still ok")
233 /* left branch was already too long. rebal */
234 MSG("LESS: case -1: rebalancing")
236 if (p1->bal == -1) { /* LL */
237 MSG("LESS: single LL")
238 (*ppr)->left = p1->right;
242 } else { /* double LR */
243 MSG("LESS: double LR")
246 p1->right = p2->left;
249 (*ppr)->left = p2->right;
270 /* if MORE, prepare to move to the right.
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")
279 switch ((*ppr)->bal) {
281 MSG("MORE: balance was off, fixed implicitly")
286 MSG("MORE: balance was okay, now off but ok")
290 MSG("MORE: balance was off, need to rebalance")
292 if (p1->bal == 1) { /* RR */
293 MSG("MORE: single RR")
294 (*ppr)->right = p1->left;
298 } else { /* double RL */
299 MSG("MORE: double RL")
302 p1->left = p2->right;
305 (*ppr)->right = p2->left;
327 /* not less, not more: this is the same key! replace...
329 MSG("FOUND: Replacing data value")
332 (*pfv_delete)((*ppr)->data);
333 (*ppr)->data = p_data;
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)
346 if (*ppr_p == NULL) {
347 MSG("key not in tree")
351 i_comp = (*pfi_compare)((*ppr_p)->data, p_user);
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);
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);
363 bal_R(ppr_p, pi_balance);
367 if (pr_q->right == NULL) {
368 MSG("right subtree null")
371 } else if (pr_q->left == NULL) {
372 MSG("right subtree non-null, left subtree null")
373 *ppr_p = pr_q->right;
376 MSG("neither subtree null")
377 del(&pr_q->left, pi_balance, &pr_q,
378 pfv_uar, pi_uar_called);
380 bal_L(ppr_p, pi_balance);
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));
392 del(tree **ppr_r, int *pi_balance, tree **ppr_q,
393 void (*pfv_uar)(tree_t), int *pi_uar_called)
397 if ((*ppr_r)->right != NULL) {
398 del(&(*ppr_r)->right, pi_balance, ppr_q,
399 pfv_uar, pi_uar_called);
401 bal_R(ppr_r, pi_balance);
404 (*pfv_uar)((*ppr_q)->data);
405 *pi_uar_called = TRUE;
406 (*ppr_q)->data = (*ppr_r)->data;
408 *ppr_r = (*ppr_r)->left;
416 bal_L(tree **ppr_p, int *pi_balance) {
421 MSG("left branch has shrunk")
423 switch ((*ppr_p)->bal) {
425 MSG("was imbalanced, fixed implicitly")
429 MSG("was okay, is now one off")
434 MSG("was already off, this is too much")
435 p1 = (*ppr_p)->right;
439 (*ppr_p)->right = p1->left;
456 p1->left = p2->right;
458 (*ppr_p)->right = p2->left;
476 bal_R(tree **ppr_p, int *pi_balance) {
481 MSG("right branch has shrunk")
482 switch ((*ppr_p)->bal) {
484 MSG("was imbalanced, fixed implicitly")
488 MSG("was okay, is now one off")
493 MSG("was already off, this is too much")
498 (*ppr_p)->left = p1->right;
515 p1->right = p2->left;
517 (*ppr_p)->left = p2->right;