2 static const char rcsid
[] = "$Id: tree.c,v 1.4 2005/04/27 04:56:39 sra 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
;