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