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