1#ifndef LINT
2static 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#ifdef DEBUG
42# define DEBUG_DOMAIN "tree"
43#endif
44
45#include "port_before.h"
46
47#include <stdio.h>
48#include <stdlib.h>
49
50#include "port_after.h"
51
52#include <isc/memcluster.h>
53#include <isc/tree.h>
54
55#ifdef DEBUG
56static int	debugDepth = 0;
57static char	*debugFuncs[256];
58# define ENTER(proc) { \
59			debugFuncs[debugDepth] = proc; \
60			fprintf(stderr, "ENTER(%d:%s.%s)\n", \
61				debugDepth, DEBUG_DOMAIN, \
62				debugFuncs[debugDepth]); \
63			debugDepth++; \
64		}
65# define RET(value) { \
66			debugDepth--; \
67			fprintf(stderr, "RET(%d:%s.%s)\n", \
68				debugDepth, DEBUG_DOMAIN, \
69				debugFuncs[debugDepth]); \
70			return (value); \
71		}
72# define RETV { \
73			debugDepth--; \
74			fprintf(stderr, "RETV(%d:%s.%s)\n", \
75				debugDepth, DEBUG_DOMAIN, \
76				debugFuncs[debugDepth]); \
77			return; \
78		}
79# define MSG(msg)	fprintf(stderr, "MSG(%s)\n", msg);
80#else
81# define ENTER(proc)	;
82# define RET(value)	return (value);
83# define RETV		return;
84# define MSG(msg)	;
85#endif
86
87#ifndef TRUE
88# define TRUE		1
89# define FALSE		0
90#endif
91
92static tree *	sprout(tree **, tree_t, int *, int (*)(), void (*)());
93static int	delete(tree **, int (*)(), tree_t, void (*)(), int *, int *);
94static void	del(tree **, int *, tree **, void (*)(), int *);
95static void	bal_L(tree **, int *);
96static void	bal_R(tree **, int *);
97
98void
99tree_init(tree **ppr_tree) {
100	ENTER("tree_init")
101	*ppr_tree = NULL;
102	RETV
103}
104
105tree_t
106tree_srch(tree **ppr_tree, int (*pfi_compare)(tree_t, tree_t), tree_t	p_user) {
107	ENTER("tree_srch")
108
109	if (*ppr_tree) {
110		int i_comp = (*pfi_compare)(p_user, (**ppr_tree).data);
111
112		if (i_comp > 0)
113			RET(tree_srch(&(**ppr_tree).right,
114				      pfi_compare,
115				      p_user))
116
117		if (i_comp < 0)
118			RET(tree_srch(&(**ppr_tree).left,
119				      pfi_compare,
120				      p_user))
121
122		/* not higher, not lower... this must be the one.
123		 */
124		RET((**ppr_tree).data)
125	}
126
127	/* grounded. NOT found.
128	 */
129	RET(NULL)
130}
131
132tree_t
133tree_add(tree **ppr_tree, int (*pfi_compare)(tree_t, tree_t),
134	 tree_t p_user, void (*pfv_uar)())
135{
136	int i_balance = FALSE;
137
138	ENTER("tree_add")
139	if (!sprout(ppr_tree, p_user, &i_balance, pfi_compare, pfv_uar))
140		RET(NULL)
141	RET(p_user)
142}
143
144int
145tree_delete(tree **ppr_p, int (*pfi_compare)(tree_t, tree_t),
146	    tree_t p_user, void	(*pfv_uar)())
147{
148	int i_balance = FALSE, i_uar_called = FALSE;
149
150	ENTER("tree_delete");
151	RET(delete(ppr_p, pfi_compare, p_user, pfv_uar,
152		   &i_balance, &i_uar_called))
153}
154
155int
156tree_trav(tree **ppr_tree, int (*pfi_uar)(tree_t)) {
157	ENTER("tree_trav")
158
159	if (!*ppr_tree)
160		RET(TRUE)
161
162	if (!tree_trav(&(**ppr_tree).left, pfi_uar))
163		RET(FALSE)
164	if (!(*pfi_uar)((**ppr_tree).data))
165		RET(FALSE)
166	if (!tree_trav(&(**ppr_tree).right, pfi_uar))
167		RET(FALSE)
168	RET(TRUE)
169}
170
171void
172tree_mung(tree **ppr_tree, void	(*pfv_uar)(tree_t)) {
173	ENTER("tree_mung")
174	if (*ppr_tree) {
175		tree_mung(&(**ppr_tree).left, pfv_uar);
176		tree_mung(&(**ppr_tree).right, pfv_uar);
177		if (pfv_uar)
178			(*pfv_uar)((**ppr_tree).data);
179		memput(*ppr_tree, sizeof(tree));
180		*ppr_tree = NULL;
181	}
182	RETV
183}
184
185static tree *
186sprout(tree **ppr, tree_t p_data, int *pi_balance,
187       int (*pfi_compare)(tree_t, tree_t), void (*pfv_delete)(tree_t))
188{
189	tree *p1, *p2, *sub;
190	int cmp;
191
192	ENTER("sprout")
193
194	/* are we grounded?  if so, add the node "here" and set the rebalance
195	 * flag, then exit.
196	 */
197	if (!*ppr) {
198		MSG("grounded. adding new node, setting h=true")
199		*ppr = (tree *) memget(sizeof(tree));
200		if (*ppr) {
201			(*ppr)->left = NULL;
202			(*ppr)->right = NULL;
203			(*ppr)->bal = 0;
204			(*ppr)->data = p_data;
205			*pi_balance = TRUE;
206		}
207		RET(*ppr);
208	}
209
210	/* compare the data using routine passed by caller.
211	 */
212	cmp = (*pfi_compare)(p_data, (*ppr)->data);
213
214	/* if LESS, prepare to move to the left.
215	 */
216	if (cmp < 0) {
217		MSG("LESS. sprouting left.")
218		sub = sprout(&(*ppr)->left, p_data, pi_balance,
219			     pfi_compare, pfv_delete);
220		if (sub && *pi_balance) {	/*%< left branch has grown */
221			MSG("LESS: left branch has grown")
222			switch ((*ppr)->bal) {
223			case 1:
224				/* right branch WAS longer; bal is ok now */
225				MSG("LESS: case 1.. bal restored implicitly")
226				(*ppr)->bal = 0;
227				*pi_balance = FALSE;
228				break;
229			case 0:
230				/* balance WAS okay; now left branch longer */
231				MSG("LESS: case 0.. balnce bad but still ok")
232				(*ppr)->bal = -1;
233				break;
234			case -1:
235				/* left branch was already too long. rebal */
236				MSG("LESS: case -1: rebalancing")
237				p1 = (*ppr)->left;
238				if (p1->bal == -1) {		/*%< LL */
239					MSG("LESS: single LL")
240					(*ppr)->left = p1->right;
241					p1->right = *ppr;
242					(*ppr)->bal = 0;
243					*ppr = p1;
244				} else {			/*%< double LR */
245					MSG("LESS: double LR")
246
247					p2 = p1->right;
248					p1->right = p2->left;
249					p2->left = p1;
250
251					(*ppr)->left = p2->right;
252					p2->right = *ppr;
253
254					if (p2->bal == -1)
255						(*ppr)->bal = 1;
256					else
257						(*ppr)->bal = 0;
258
259					if (p2->bal == 1)
260						p1->bal = -1;
261					else
262						p1->bal = 0;
263					*ppr = p2;
264				} /*else*/
265				(*ppr)->bal = 0;
266				*pi_balance = FALSE;
267			} /*switch*/
268		} /*if*/
269		RET(sub)
270	} /*if*/
271
272	/* if MORE, prepare to move to the right.
273	 */
274	if (cmp > 0) {
275		MSG("MORE: sprouting to the right")
276		sub = sprout(&(*ppr)->right, p_data, pi_balance,
277			     pfi_compare, pfv_delete);
278		if (sub && *pi_balance) {
279			MSG("MORE: right branch has grown")
280
281			switch ((*ppr)->bal) {
282			case -1:
283				MSG("MORE: balance was off, fixed implicitly")
284				(*ppr)->bal = 0;
285				*pi_balance = FALSE;
286				break;
287			case 0:
288				MSG("MORE: balance was okay, now off but ok")
289				(*ppr)->bal = 1;
290				break;
291			case 1:
292				MSG("MORE: balance was off, need to rebalance")
293				p1 = (*ppr)->right;
294				if (p1->bal == 1) {		/*%< RR */
295					MSG("MORE: single RR")
296					(*ppr)->right = p1->left;
297					p1->left = *ppr;
298					(*ppr)->bal = 0;
299					*ppr = p1;
300				} else {			/*%< double RL */
301					MSG("MORE: double RL")
302
303					p2 = p1->left;
304					p1->left = p2->right;
305					p2->right = p1;
306
307					(*ppr)->right = p2->left;
308					p2->left = *ppr;
309
310					if (p2->bal == 1)
311						(*ppr)->bal = -1;
312					else
313						(*ppr)->bal = 0;
314
315					if (p2->bal == -1)
316						p1->bal = 1;
317					else
318						p1->bal = 0;
319
320					*ppr = p2;
321				} /*else*/
322				(*ppr)->bal = 0;
323				*pi_balance = FALSE;
324			} /*switch*/
325		} /*if*/
326		RET(sub)
327	} /*if*/
328
329	/* not less, not more: this is the same key!  replace...
330	 */
331	MSG("FOUND: Replacing data value")
332	*pi_balance = FALSE;
333	if (pfv_delete)
334		(*pfv_delete)((*ppr)->data);
335	(*ppr)->data = p_data;
336	RET(*ppr)
337}
338
339static int
340delete(tree **ppr_p, int (*pfi_compare)(tree_t, tree_t), tree_t p_user,
341       void (*pfv_uar)(tree_t), int *pi_balance, int *pi_uar_called)
342{
343	tree *pr_q;
344	int i_comp, i_ret;
345
346	ENTER("delete")
347
348	if (*ppr_p == NULL) {
349		MSG("key not in tree")
350		RET(FALSE)
351	}
352
353	i_comp = (*pfi_compare)((*ppr_p)->data, p_user);
354	if (i_comp > 0) {
355		MSG("too high - scan left")
356		i_ret = delete(&(*ppr_p)->left, pfi_compare, p_user, pfv_uar,
357			       pi_balance, pi_uar_called);
358		if (*pi_balance)
359			bal_L(ppr_p, pi_balance);
360	} else if (i_comp < 0) {
361		MSG("too low - scan right")
362		i_ret = delete(&(*ppr_p)->right, pfi_compare, p_user, pfv_uar,
363			       pi_balance, pi_uar_called);
364		if (*pi_balance)
365			bal_R(ppr_p, pi_balance);
366	} else {
367		MSG("equal")
368		pr_q = *ppr_p;
369		if (pr_q->right == NULL) {
370			MSG("right subtree null")
371			*ppr_p = pr_q->left;
372			*pi_balance = TRUE;
373		} else if (pr_q->left == NULL) {
374			MSG("right subtree non-null, left subtree null")
375			*ppr_p = pr_q->right;
376			*pi_balance = TRUE;
377		} else {
378			MSG("neither subtree null")
379			del(&pr_q->left, pi_balance, &pr_q,
380			    pfv_uar, pi_uar_called);
381			if (*pi_balance)
382				bal_L(ppr_p, pi_balance);
383		}
384		if (!*pi_uar_called && pfv_uar)
385			(*pfv_uar)(pr_q->data);
386		/* Thanks to wuth@castrov.cuc.ab.ca for the following stmt. */
387		memput(pr_q, sizeof(tree));
388		i_ret = TRUE;
389	}
390	RET(i_ret)
391}
392
393static void
394del(tree **ppr_r, int *pi_balance, tree **ppr_q,
395    void (*pfv_uar)(tree_t), int *pi_uar_called)
396{
397	ENTER("del")
398
399	if ((*ppr_r)->right != NULL) {
400		del(&(*ppr_r)->right, pi_balance, ppr_q,
401		    pfv_uar, pi_uar_called);
402		if (*pi_balance)
403			bal_R(ppr_r, pi_balance);
404	} else {
405		if (pfv_uar)
406			(*pfv_uar)((*ppr_q)->data);
407		*pi_uar_called = TRUE;
408		(*ppr_q)->data = (*ppr_r)->data;
409		*ppr_q = *ppr_r;
410		*ppr_r = (*ppr_r)->left;
411		*pi_balance = TRUE;
412	}
413
414	RETV
415}
416
417static void
418bal_L(tree **ppr_p, int *pi_balance) {
419	tree *p1, *p2;
420	int b1, b2;
421
422	ENTER("bal_L")
423	MSG("left branch has shrunk")
424
425	switch ((*ppr_p)->bal) {
426	case -1:
427		MSG("was imbalanced, fixed implicitly")
428		(*ppr_p)->bal = 0;
429		break;
430	case 0:
431		MSG("was okay, is now one off")
432		(*ppr_p)->bal = 1;
433		*pi_balance = FALSE;
434		break;
435	case 1:
436		MSG("was already off, this is too much")
437		p1 = (*ppr_p)->right;
438		b1 = p1->bal;
439		if (b1 >= 0) {
440			MSG("single RR")
441			(*ppr_p)->right = p1->left;
442			p1->left = *ppr_p;
443			if (b1 == 0) {
444				MSG("b1 == 0")
445				(*ppr_p)->bal = 1;
446				p1->bal = -1;
447				*pi_balance = FALSE;
448			} else {
449				MSG("b1 != 0")
450				(*ppr_p)->bal = 0;
451				p1->bal = 0;
452			}
453			*ppr_p = p1;
454		} else {
455			MSG("double RL")
456			p2 = p1->left;
457			b2 = p2->bal;
458			p1->left = p2->right;
459			p2->right = p1;
460			(*ppr_p)->right = p2->left;
461			p2->left = *ppr_p;
462			if (b2 == 1)
463				(*ppr_p)->bal = -1;
464			else
465				(*ppr_p)->bal = 0;
466			if (b2 == -1)
467				p1->bal = 1;
468			else
469				p1->bal = 0;
470			*ppr_p = p2;
471			p2->bal = 0;
472		}
473	}
474	RETV
475}
476
477static void
478bal_R(tree **ppr_p, int *pi_balance) {
479	tree *p1, *p2;
480	int b1, b2;
481
482	ENTER("bal_R")
483	MSG("right branch has shrunk")
484	switch ((*ppr_p)->bal) {
485	case 1:
486		MSG("was imbalanced, fixed implicitly")
487		(*ppr_p)->bal = 0;
488		break;
489	case 0:
490		MSG("was okay, is now one off")
491		(*ppr_p)->bal = -1;
492		*pi_balance = FALSE;
493		break;
494	case -1:
495		MSG("was already off, this is too much")
496		p1 = (*ppr_p)->left;
497		b1 = p1->bal;
498		if (b1 <= 0) {
499			MSG("single LL")
500			(*ppr_p)->left = p1->right;
501			p1->right = *ppr_p;
502			if (b1 == 0) {
503				MSG("b1 == 0")
504				(*ppr_p)->bal = -1;
505				p1->bal = 1;
506				*pi_balance = FALSE;
507			} else {
508				MSG("b1 != 0")
509				(*ppr_p)->bal = 0;
510				p1->bal = 0;
511			}
512			*ppr_p = p1;
513		} else {
514			MSG("double LR")
515			p2 = p1->right;
516			b2 = p2->bal;
517			p1->right = p2->left;
518			p2->left = p1;
519			(*ppr_p)->left = p2->right;
520			p2->right = *ppr_p;
521			if (b2 == -1)
522				(*ppr_p)->bal = 1;
523			else
524				(*ppr_p)->bal = 0;
525			if (b2 == 1)
526				p1->bal = -1;
527			else
528				p1->bal = 0;
529			*ppr_p = p2;
530			p2->bal = 0;
531		}
532	}
533	RETV
534}
535
536/*! \file */
537