1*9525b14bSRao Shoaib /*%
27c478bd9Sstevel@tonic-gate  * tree - balanced binary tree library
37c478bd9Sstevel@tonic-gate  *
47c478bd9Sstevel@tonic-gate  * vix 05apr94 [removed vixie.h dependencies; cleaned up formatting, names]
57c478bd9Sstevel@tonic-gate  * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes]
67c478bd9Sstevel@tonic-gate  * vix 23jun86 [added delete uar to add for replaced nodes]
77c478bd9Sstevel@tonic-gate  * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224]
87c478bd9Sstevel@tonic-gate  * vix 06feb86 [added tree_mung()]
97c478bd9Sstevel@tonic-gate  * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221]
107c478bd9Sstevel@tonic-gate  * vix 14dec85 [written]
117c478bd9Sstevel@tonic-gate  */
127c478bd9Sstevel@tonic-gate 
13*9525b14bSRao Shoaib /*%
147c478bd9Sstevel@tonic-gate  * This program text was created by Paul Vixie using examples from the book:
157c478bd9Sstevel@tonic-gate  * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN
167c478bd9Sstevel@tonic-gate  * 0-13-022005-1.  Any errors in the conversion from Modula-2 to C are Paul
177c478bd9Sstevel@tonic-gate  * Vixie's.
187c478bd9Sstevel@tonic-gate  */
197c478bd9Sstevel@tonic-gate 
207c478bd9Sstevel@tonic-gate /*
21*9525b14bSRao Shoaib  * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC")
227c478bd9Sstevel@tonic-gate  * Portions Copyright (c) 1996-1999 by Internet Software Consortium.
237c478bd9Sstevel@tonic-gate  *
247c478bd9Sstevel@tonic-gate  * Permission to use, copy, modify, and distribute this software for any
257c478bd9Sstevel@tonic-gate  * purpose with or without fee is hereby granted, provided that the above
267c478bd9Sstevel@tonic-gate  * copyright notice and this permission notice appear in all copies.
277c478bd9Sstevel@tonic-gate  *
28*9525b14bSRao Shoaib  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
29*9525b14bSRao Shoaib  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
30*9525b14bSRao Shoaib  * MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR
31*9525b14bSRao Shoaib  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
32*9525b14bSRao Shoaib  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
33*9525b14bSRao Shoaib  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
34*9525b14bSRao Shoaib  * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
357c478bd9Sstevel@tonic-gate  */
367c478bd9Sstevel@tonic-gate 
377c478bd9Sstevel@tonic-gate /*#define		DEBUG	"tree"*/
387c478bd9Sstevel@tonic-gate 
397c478bd9Sstevel@tonic-gate #include "port_before.h"
407c478bd9Sstevel@tonic-gate 
417c478bd9Sstevel@tonic-gate #include <stdio.h>
427c478bd9Sstevel@tonic-gate #include <stdlib.h>
437c478bd9Sstevel@tonic-gate 
447c478bd9Sstevel@tonic-gate #include "port_after.h"
457c478bd9Sstevel@tonic-gate 
467c478bd9Sstevel@tonic-gate #include <isc/memcluster.h>
477c478bd9Sstevel@tonic-gate #include <isc/tree.h>
487c478bd9Sstevel@tonic-gate 
497c478bd9Sstevel@tonic-gate #ifdef DEBUG
507c478bd9Sstevel@tonic-gate static int	debugDepth = 0;
517c478bd9Sstevel@tonic-gate static char	*debugFuncs[256];
527c478bd9Sstevel@tonic-gate # define ENTER(proc) { \
537c478bd9Sstevel@tonic-gate 			debugFuncs[debugDepth] = proc; \
547c478bd9Sstevel@tonic-gate 			fprintf(stderr, "ENTER(%d:%s.%s)\n", \
557c478bd9Sstevel@tonic-gate 				debugDepth, DEBUG, \
567c478bd9Sstevel@tonic-gate 				debugFuncs[debugDepth]); \
577c478bd9Sstevel@tonic-gate 			debugDepth++; \
587c478bd9Sstevel@tonic-gate 		}
597c478bd9Sstevel@tonic-gate # define RET(value) { \
607c478bd9Sstevel@tonic-gate 			debugDepth--; \
617c478bd9Sstevel@tonic-gate 			fprintf(stderr, "RET(%d:%s.%s)\n", \
627c478bd9Sstevel@tonic-gate 				debugDepth, DEBUG, \
637c478bd9Sstevel@tonic-gate 				debugFuncs[debugDepth]); \
647c478bd9Sstevel@tonic-gate 			return (value); \
657c478bd9Sstevel@tonic-gate 		}
667c478bd9Sstevel@tonic-gate # define RETV { \
677c478bd9Sstevel@tonic-gate 			debugDepth--; \
687c478bd9Sstevel@tonic-gate 			fprintf(stderr, "RETV(%d:%s.%s)\n", \
697c478bd9Sstevel@tonic-gate 				debugDepth, DEBUG, \
707c478bd9Sstevel@tonic-gate 				debugFuncs[debugDepth]); \
717c478bd9Sstevel@tonic-gate 			return; \
727c478bd9Sstevel@tonic-gate 		}
737c478bd9Sstevel@tonic-gate # define MSG(msg)	fprintf(stderr, "MSG(%s)\n", msg);
747c478bd9Sstevel@tonic-gate #else
757c478bd9Sstevel@tonic-gate # define ENTER(proc)	;
767c478bd9Sstevel@tonic-gate # define RET(value)	return (value);
777c478bd9Sstevel@tonic-gate # define RETV		return;
787c478bd9Sstevel@tonic-gate # define MSG(msg)	;
797c478bd9Sstevel@tonic-gate #endif
807c478bd9Sstevel@tonic-gate 
817c478bd9Sstevel@tonic-gate #ifndef TRUE
827c478bd9Sstevel@tonic-gate # define TRUE		1
837c478bd9Sstevel@tonic-gate # define FALSE		0
847c478bd9Sstevel@tonic-gate #endif
857c478bd9Sstevel@tonic-gate 
867c478bd9Sstevel@tonic-gate static tree *	sprout(tree **, tree_t, int *, int (*)(), void (*)());
877c478bd9Sstevel@tonic-gate static int	delete(tree **, int (*)(), tree_t, void (*)(), int *, int *);
887c478bd9Sstevel@tonic-gate static void	del(tree **, int *, tree **, void (*)(), int *);
897c478bd9Sstevel@tonic-gate static void	bal_L(tree **, int *);
907c478bd9Sstevel@tonic-gate static void	bal_R(tree **, int *);
917c478bd9Sstevel@tonic-gate 
927c478bd9Sstevel@tonic-gate void
tree_init(tree ** ppr_tree)937c478bd9Sstevel@tonic-gate tree_init(tree **ppr_tree) {
947c478bd9Sstevel@tonic-gate 	ENTER("tree_init")
957c478bd9Sstevel@tonic-gate 	*ppr_tree = NULL;
967c478bd9Sstevel@tonic-gate 	RETV
977c478bd9Sstevel@tonic-gate }
987c478bd9Sstevel@tonic-gate 
997c478bd9Sstevel@tonic-gate tree_t
tree_srch(tree ** ppr_tree,int (* pfi_compare)(tree_t,tree_t),tree_t p_user)1007c478bd9Sstevel@tonic-gate tree_srch(tree **ppr_tree, int (*pfi_compare)(tree_t, tree_t), tree_t	p_user) {
1017c478bd9Sstevel@tonic-gate 	ENTER("tree_srch")
1027c478bd9Sstevel@tonic-gate 
1037c478bd9Sstevel@tonic-gate 	if (*ppr_tree) {
1047c478bd9Sstevel@tonic-gate 		int i_comp = (*pfi_compare)(p_user, (**ppr_tree).data);
1057c478bd9Sstevel@tonic-gate 
1067c478bd9Sstevel@tonic-gate 		if (i_comp > 0)
1077c478bd9Sstevel@tonic-gate 			RET(tree_srch(&(**ppr_tree).right,
1087c478bd9Sstevel@tonic-gate 				      pfi_compare,
1097c478bd9Sstevel@tonic-gate 				      p_user))
1107c478bd9Sstevel@tonic-gate 
1117c478bd9Sstevel@tonic-gate 		if (i_comp < 0)
1127c478bd9Sstevel@tonic-gate 			RET(tree_srch(&(**ppr_tree).left,
1137c478bd9Sstevel@tonic-gate 				      pfi_compare,
1147c478bd9Sstevel@tonic-gate 				      p_user))
1157c478bd9Sstevel@tonic-gate 
1167c478bd9Sstevel@tonic-gate 		/* not higher, not lower... this must be the one.
1177c478bd9Sstevel@tonic-gate 		 */
1187c478bd9Sstevel@tonic-gate 		RET((**ppr_tree).data)
1197c478bd9Sstevel@tonic-gate 	}
1207c478bd9Sstevel@tonic-gate 
1217c478bd9Sstevel@tonic-gate 	/* grounded. NOT found.
1227c478bd9Sstevel@tonic-gate 	 */
1237c478bd9Sstevel@tonic-gate 	RET(NULL)
1247c478bd9Sstevel@tonic-gate }
1257c478bd9Sstevel@tonic-gate 
1267c478bd9Sstevel@tonic-gate tree_t
tree_add(tree ** ppr_tree,int (* pfi_compare)(tree_t,tree_t),tree_t p_user,void (* pfv_uar)())1277c478bd9Sstevel@tonic-gate tree_add(tree **ppr_tree, int (*pfi_compare)(tree_t, tree_t),
1287c478bd9Sstevel@tonic-gate 	 tree_t p_user, void (*pfv_uar)())
1297c478bd9Sstevel@tonic-gate {
1307c478bd9Sstevel@tonic-gate 	int i_balance = FALSE;
1317c478bd9Sstevel@tonic-gate 
1327c478bd9Sstevel@tonic-gate 	ENTER("tree_add")
1337c478bd9Sstevel@tonic-gate 	if (!sprout(ppr_tree, p_user, &i_balance, pfi_compare, pfv_uar))
1347c478bd9Sstevel@tonic-gate 		RET(NULL)
1357c478bd9Sstevel@tonic-gate 	RET(p_user)
1367c478bd9Sstevel@tonic-gate }
1377c478bd9Sstevel@tonic-gate 
1387c478bd9Sstevel@tonic-gate int
tree_delete(tree ** ppr_p,int (* pfi_compare)(tree_t,tree_t),tree_t p_user,void (* pfv_uar)())1397c478bd9Sstevel@tonic-gate tree_delete(tree **ppr_p, int (*pfi_compare)(tree_t, tree_t),
1407c478bd9Sstevel@tonic-gate 	    tree_t p_user, void	(*pfv_uar)())
1417c478bd9Sstevel@tonic-gate {
1427c478bd9Sstevel@tonic-gate 	int i_balance = FALSE, i_uar_called = FALSE;
1437c478bd9Sstevel@tonic-gate 
1447c478bd9Sstevel@tonic-gate 	ENTER("tree_delete");
1457c478bd9Sstevel@tonic-gate 	RET(delete(ppr_p, pfi_compare, p_user, pfv_uar,
1467c478bd9Sstevel@tonic-gate 		   &i_balance, &i_uar_called))
1477c478bd9Sstevel@tonic-gate }
1487c478bd9Sstevel@tonic-gate 
1497c478bd9Sstevel@tonic-gate int
tree_trav(tree ** ppr_tree,int (* pfi_uar)(tree_t))1507c478bd9Sstevel@tonic-gate tree_trav(tree **ppr_tree, int (*pfi_uar)(tree_t)) {
1517c478bd9Sstevel@tonic-gate 	ENTER("tree_trav")
1527c478bd9Sstevel@tonic-gate 
1537c478bd9Sstevel@tonic-gate 	if (!*ppr_tree)
1547c478bd9Sstevel@tonic-gate 		RET(TRUE)
1557c478bd9Sstevel@tonic-gate 
1567c478bd9Sstevel@tonic-gate 	if (!tree_trav(&(**ppr_tree).left, pfi_uar))
1577c478bd9Sstevel@tonic-gate 		RET(FALSE)
1587c478bd9Sstevel@tonic-gate 	if (!(*pfi_uar)((**ppr_tree).data))
1597c478bd9Sstevel@tonic-gate 		RET(FALSE)
1607c478bd9Sstevel@tonic-gate 	if (!tree_trav(&(**ppr_tree).right, pfi_uar))
1617c478bd9Sstevel@tonic-gate 		RET(FALSE)
1627c478bd9Sstevel@tonic-gate 	RET(TRUE)
1637c478bd9Sstevel@tonic-gate }
1647c478bd9Sstevel@tonic-gate 
1657c478bd9Sstevel@tonic-gate void
tree_mung(tree ** ppr_tree,void (* pfv_uar)(tree_t))1667c478bd9Sstevel@tonic-gate tree_mung(tree **ppr_tree, void	(*pfv_uar)(tree_t)) {
1677c478bd9Sstevel@tonic-gate 	ENTER("tree_mung")
1687c478bd9Sstevel@tonic-gate 	if (*ppr_tree) {
1697c478bd9Sstevel@tonic-gate 		tree_mung(&(**ppr_tree).left, pfv_uar);
1707c478bd9Sstevel@tonic-gate 		tree_mung(&(**ppr_tree).right, pfv_uar);
1717c478bd9Sstevel@tonic-gate 		if (pfv_uar)
1727c478bd9Sstevel@tonic-gate 			(*pfv_uar)((**ppr_tree).data);
1737c478bd9Sstevel@tonic-gate 		memput(*ppr_tree, sizeof(tree));
1747c478bd9Sstevel@tonic-gate 		*ppr_tree = NULL;
1757c478bd9Sstevel@tonic-gate 	}
1767c478bd9Sstevel@tonic-gate 	RETV
1777c478bd9Sstevel@tonic-gate }
1787c478bd9Sstevel@tonic-gate 
1797c478bd9Sstevel@tonic-gate static tree *
sprout(tree ** ppr,tree_t p_data,int * pi_balance,int (* pfi_compare)(tree_t,tree_t),void (* pfv_delete)(tree_t))1807c478bd9Sstevel@tonic-gate sprout(tree **ppr, tree_t p_data, int *pi_balance,
1817c478bd9Sstevel@tonic-gate        int (*pfi_compare)(tree_t, tree_t), void (*pfv_delete)(tree_t))
1827c478bd9Sstevel@tonic-gate {
1837c478bd9Sstevel@tonic-gate 	tree *p1, *p2, *sub;
1847c478bd9Sstevel@tonic-gate 	int cmp;
1857c478bd9Sstevel@tonic-gate 
1867c478bd9Sstevel@tonic-gate 	ENTER("sprout")
1877c478bd9Sstevel@tonic-gate 
1887c478bd9Sstevel@tonic-gate 	/* are we grounded?  if so, add the node "here" and set the rebalance
1897c478bd9Sstevel@tonic-gate 	 * flag, then exit.
1907c478bd9Sstevel@tonic-gate 	 */
1917c478bd9Sstevel@tonic-gate 	if (!*ppr) {
1927c478bd9Sstevel@tonic-gate 		MSG("grounded. adding new node, setting h=true")
1937c478bd9Sstevel@tonic-gate 		*ppr = (tree *) memget(sizeof(tree));
1947c478bd9Sstevel@tonic-gate 		if (*ppr) {
1957c478bd9Sstevel@tonic-gate 			(*ppr)->left = NULL;
1967c478bd9Sstevel@tonic-gate 			(*ppr)->right = NULL;
1977c478bd9Sstevel@tonic-gate 			(*ppr)->bal = 0;
1987c478bd9Sstevel@tonic-gate 			(*ppr)->data = p_data;
1997c478bd9Sstevel@tonic-gate 			*pi_balance = TRUE;
2007c478bd9Sstevel@tonic-gate 		}
2017c478bd9Sstevel@tonic-gate 		RET(*ppr);
2027c478bd9Sstevel@tonic-gate 	}
2037c478bd9Sstevel@tonic-gate 
2047c478bd9Sstevel@tonic-gate 	/* compare the data using routine passed by caller.
2057c478bd9Sstevel@tonic-gate 	 */
2067c478bd9Sstevel@tonic-gate 	cmp = (*pfi_compare)(p_data, (*ppr)->data);
2077c478bd9Sstevel@tonic-gate 
2087c478bd9Sstevel@tonic-gate 	/* if LESS, prepare to move to the left.
2097c478bd9Sstevel@tonic-gate 	 */
2107c478bd9Sstevel@tonic-gate 	if (cmp < 0) {
2117c478bd9Sstevel@tonic-gate 		MSG("LESS. sprouting left.")
2127c478bd9Sstevel@tonic-gate 		sub = sprout(&(*ppr)->left, p_data, pi_balance,
2137c478bd9Sstevel@tonic-gate 			     pfi_compare, pfv_delete);
214*9525b14bSRao Shoaib 		if (sub && *pi_balance) {	/*%< left branch has grown */
2157c478bd9Sstevel@tonic-gate 			MSG("LESS: left branch has grown")
2167c478bd9Sstevel@tonic-gate 			switch ((*ppr)->bal) {
2177c478bd9Sstevel@tonic-gate 			case 1:
2187c478bd9Sstevel@tonic-gate 				/* right branch WAS longer; bal is ok now */
2197c478bd9Sstevel@tonic-gate 				MSG("LESS: case 1.. bal restored implicitly")
2207c478bd9Sstevel@tonic-gate 				(*ppr)->bal = 0;
2217c478bd9Sstevel@tonic-gate 				*pi_balance = FALSE;
2227c478bd9Sstevel@tonic-gate 				break;
2237c478bd9Sstevel@tonic-gate 			case 0:
2247c478bd9Sstevel@tonic-gate 				/* balance WAS okay; now left branch longer */
2257c478bd9Sstevel@tonic-gate 				MSG("LESS: case 0.. balnce bad but still ok")
2267c478bd9Sstevel@tonic-gate 				(*ppr)->bal = -1;
2277c478bd9Sstevel@tonic-gate 				break;
2287c478bd9Sstevel@tonic-gate 			case -1:
2297c478bd9Sstevel@tonic-gate 				/* left branch was already too long. rebal */
2307c478bd9Sstevel@tonic-gate 				MSG("LESS: case -1: rebalancing")
2317c478bd9Sstevel@tonic-gate 				p1 = (*ppr)->left;
232*9525b14bSRao Shoaib 				if (p1->bal == -1) {		/*%< LL */
2337c478bd9Sstevel@tonic-gate 					MSG("LESS: single LL")
2347c478bd9Sstevel@tonic-gate 					(*ppr)->left = p1->right;
2357c478bd9Sstevel@tonic-gate 					p1->right = *ppr;
2367c478bd9Sstevel@tonic-gate 					(*ppr)->bal = 0;
2377c478bd9Sstevel@tonic-gate 					*ppr = p1;
238*9525b14bSRao Shoaib 				} else {			/*%< double LR */
2397c478bd9Sstevel@tonic-gate 					MSG("LESS: double LR")
2407c478bd9Sstevel@tonic-gate 
2417c478bd9Sstevel@tonic-gate 					p2 = p1->right;
2427c478bd9Sstevel@tonic-gate 					p1->right = p2->left;
2437c478bd9Sstevel@tonic-gate 					p2->left = p1;
2447c478bd9Sstevel@tonic-gate 
2457c478bd9Sstevel@tonic-gate 					(*ppr)->left = p2->right;
2467c478bd9Sstevel@tonic-gate 					p2->right = *ppr;
2477c478bd9Sstevel@tonic-gate 
2487c478bd9Sstevel@tonic-gate 					if (p2->bal == -1)
2497c478bd9Sstevel@tonic-gate 						(*ppr)->bal = 1;
2507c478bd9Sstevel@tonic-gate 					else
2517c478bd9Sstevel@tonic-gate 						(*ppr)->bal = 0;
2527c478bd9Sstevel@tonic-gate 
2537c478bd9Sstevel@tonic-gate 					if (p2->bal == 1)
2547c478bd9Sstevel@tonic-gate 						p1->bal = -1;
2557c478bd9Sstevel@tonic-gate 					else
2567c478bd9Sstevel@tonic-gate 						p1->bal = 0;
2577c478bd9Sstevel@tonic-gate 					*ppr = p2;
2587c478bd9Sstevel@tonic-gate 				} /*else*/
2597c478bd9Sstevel@tonic-gate 				(*ppr)->bal = 0;
2607c478bd9Sstevel@tonic-gate 				*pi_balance = FALSE;
2617c478bd9Sstevel@tonic-gate 			} /*switch*/
2627c478bd9Sstevel@tonic-gate 		} /*if*/
2637c478bd9Sstevel@tonic-gate 		RET(sub)
2647c478bd9Sstevel@tonic-gate 	} /*if*/
2657c478bd9Sstevel@tonic-gate 
2667c478bd9Sstevel@tonic-gate 	/* if MORE, prepare to move to the right.
2677c478bd9Sstevel@tonic-gate 	 */
2687c478bd9Sstevel@tonic-gate 	if (cmp > 0) {
2697c478bd9Sstevel@tonic-gate 		MSG("MORE: sprouting to the right")
2707c478bd9Sstevel@tonic-gate 		sub = sprout(&(*ppr)->right, p_data, pi_balance,
2717c478bd9Sstevel@tonic-gate 			     pfi_compare, pfv_delete);
2727c478bd9Sstevel@tonic-gate 		if (sub && *pi_balance) {
2737c478bd9Sstevel@tonic-gate 			MSG("MORE: right branch has grown")
2747c478bd9Sstevel@tonic-gate 
2757c478bd9Sstevel@tonic-gate 			switch ((*ppr)->bal) {
2767c478bd9Sstevel@tonic-gate 			case -1:
2777c478bd9Sstevel@tonic-gate 				MSG("MORE: balance was off, fixed implicitly")
2787c478bd9Sstevel@tonic-gate 				(*ppr)->bal = 0;
2797c478bd9Sstevel@tonic-gate 				*pi_balance = FALSE;
2807c478bd9Sstevel@tonic-gate 				break;
2817c478bd9Sstevel@tonic-gate 			case 0:
2827c478bd9Sstevel@tonic-gate 				MSG("MORE: balance was okay, now off but ok")
2837c478bd9Sstevel@tonic-gate 				(*ppr)->bal = 1;
2847c478bd9Sstevel@tonic-gate 				break;
2857c478bd9Sstevel@tonic-gate 			case 1:
2867c478bd9Sstevel@tonic-gate 				MSG("MORE: balance was off, need to rebalance")
2877c478bd9Sstevel@tonic-gate 				p1 = (*ppr)->right;
288*9525b14bSRao Shoaib 				if (p1->bal == 1) {		/*%< RR */
2897c478bd9Sstevel@tonic-gate 					MSG("MORE: single RR")
2907c478bd9Sstevel@tonic-gate 					(*ppr)->right = p1->left;
2917c478bd9Sstevel@tonic-gate 					p1->left = *ppr;
2927c478bd9Sstevel@tonic-gate 					(*ppr)->bal = 0;
2937c478bd9Sstevel@tonic-gate 					*ppr = p1;
294*9525b14bSRao Shoaib 				} else {			/*%< double RL */
2957c478bd9Sstevel@tonic-gate 					MSG("MORE: double RL")
2967c478bd9Sstevel@tonic-gate 
2977c478bd9Sstevel@tonic-gate 					p2 = p1->left;
2987c478bd9Sstevel@tonic-gate 					p1->left = p2->right;
2997c478bd9Sstevel@tonic-gate 					p2->right = p1;
3007c478bd9Sstevel@tonic-gate 
3017c478bd9Sstevel@tonic-gate 					(*ppr)->right = p2->left;
3027c478bd9Sstevel@tonic-gate 					p2->left = *ppr;
3037c478bd9Sstevel@tonic-gate 
3047c478bd9Sstevel@tonic-gate 					if (p2->bal == 1)
3057c478bd9Sstevel@tonic-gate 						(*ppr)->bal = -1;
3067c478bd9Sstevel@tonic-gate 					else
3077c478bd9Sstevel@tonic-gate 						(*ppr)->bal = 0;
3087c478bd9Sstevel@tonic-gate 
3097c478bd9Sstevel@tonic-gate 					if (p2->bal == -1)
3107c478bd9Sstevel@tonic-gate 						p1->bal = 1;
3117c478bd9Sstevel@tonic-gate 					else
3127c478bd9Sstevel@tonic-gate 						p1->bal = 0;
3137c478bd9Sstevel@tonic-gate 
3147c478bd9Sstevel@tonic-gate 					*ppr = p2;
3157c478bd9Sstevel@tonic-gate 				} /*else*/
3167c478bd9Sstevel@tonic-gate 				(*ppr)->bal = 0;
3177c478bd9Sstevel@tonic-gate 				*pi_balance = FALSE;
3187c478bd9Sstevel@tonic-gate 			} /*switch*/
3197c478bd9Sstevel@tonic-gate 		} /*if*/
3207c478bd9Sstevel@tonic-gate 		RET(sub)
3217c478bd9Sstevel@tonic-gate 	} /*if*/
3227c478bd9Sstevel@tonic-gate 
3237c478bd9Sstevel@tonic-gate 	/* not less, not more: this is the same key!  replace...
3247c478bd9Sstevel@tonic-gate 	 */
3257c478bd9Sstevel@tonic-gate 	MSG("FOUND: Replacing data value")
3267c478bd9Sstevel@tonic-gate 	*pi_balance = FALSE;
3277c478bd9Sstevel@tonic-gate 	if (pfv_delete)
3287c478bd9Sstevel@tonic-gate 		(*pfv_delete)((*ppr)->data);
3297c478bd9Sstevel@tonic-gate 	(*ppr)->data = p_data;
3307c478bd9Sstevel@tonic-gate 	RET(*ppr)
3317c478bd9Sstevel@tonic-gate }
3327c478bd9Sstevel@tonic-gate 
3337c478bd9Sstevel@tonic-gate static int
delete(tree ** ppr_p,int (* pfi_compare)(tree_t,tree_t),tree_t p_user,void (* pfv_uar)(tree_t),int * pi_balance,int * pi_uar_called)3347c478bd9Sstevel@tonic-gate delete(tree **ppr_p, int (*pfi_compare)(tree_t, tree_t), tree_t p_user,
3357c478bd9Sstevel@tonic-gate        void (*pfv_uar)(tree_t), int *pi_balance, int *pi_uar_called)
3367c478bd9Sstevel@tonic-gate {
3377c478bd9Sstevel@tonic-gate 	tree *pr_q;
3387c478bd9Sstevel@tonic-gate 	int i_comp, i_ret;
3397c478bd9Sstevel@tonic-gate 
3407c478bd9Sstevel@tonic-gate 	ENTER("delete")
3417c478bd9Sstevel@tonic-gate 
3427c478bd9Sstevel@tonic-gate 	if (*ppr_p == NULL) {
3437c478bd9Sstevel@tonic-gate 		MSG("key not in tree")
3447c478bd9Sstevel@tonic-gate 		RET(FALSE)
3457c478bd9Sstevel@tonic-gate 	}
3467c478bd9Sstevel@tonic-gate 
3477c478bd9Sstevel@tonic-gate 	i_comp = (*pfi_compare)((*ppr_p)->data, p_user);
3487c478bd9Sstevel@tonic-gate 	if (i_comp > 0) {
3497c478bd9Sstevel@tonic-gate 		MSG("too high - scan left")
3507c478bd9Sstevel@tonic-gate 		i_ret = delete(&(*ppr_p)->left, pfi_compare, p_user, pfv_uar,
3517c478bd9Sstevel@tonic-gate 			       pi_balance, pi_uar_called);
3527c478bd9Sstevel@tonic-gate 		if (*pi_balance)
3537c478bd9Sstevel@tonic-gate 			bal_L(ppr_p, pi_balance);
3547c478bd9Sstevel@tonic-gate 	} else if (i_comp < 0) {
3557c478bd9Sstevel@tonic-gate 		MSG("too low - scan right")
3567c478bd9Sstevel@tonic-gate 		i_ret = delete(&(*ppr_p)->right, pfi_compare, p_user, pfv_uar,
3577c478bd9Sstevel@tonic-gate 			       pi_balance, pi_uar_called);
3587c478bd9Sstevel@tonic-gate 		if (*pi_balance)
3597c478bd9Sstevel@tonic-gate 			bal_R(ppr_p, pi_balance);
3607c478bd9Sstevel@tonic-gate 	} else {
3617c478bd9Sstevel@tonic-gate 		MSG("equal")
3627c478bd9Sstevel@tonic-gate 		pr_q = *ppr_p;
3637c478bd9Sstevel@tonic-gate 		if (pr_q->right == NULL) {
3647c478bd9Sstevel@tonic-gate 			MSG("right subtree null")
3657c478bd9Sstevel@tonic-gate 			*ppr_p = pr_q->left;
3667c478bd9Sstevel@tonic-gate 			*pi_balance = TRUE;
3677c478bd9Sstevel@tonic-gate 		} else if (pr_q->left == NULL) {
3687c478bd9Sstevel@tonic-gate 			MSG("right subtree non-null, left subtree null")
3697c478bd9Sstevel@tonic-gate 			*ppr_p = pr_q->right;
3707c478bd9Sstevel@tonic-gate 			*pi_balance = TRUE;
3717c478bd9Sstevel@tonic-gate 		} else {
3727c478bd9Sstevel@tonic-gate 			MSG("neither subtree null")
3737c478bd9Sstevel@tonic-gate 			del(&pr_q->left, pi_balance, &pr_q,
3747c478bd9Sstevel@tonic-gate 			    pfv_uar, pi_uar_called);
3757c478bd9Sstevel@tonic-gate 			if (*pi_balance)
3767c478bd9Sstevel@tonic-gate 				bal_L(ppr_p, pi_balance);
3777c478bd9Sstevel@tonic-gate 		}
3787c478bd9Sstevel@tonic-gate 		if (!*pi_uar_called && pfv_uar)
3797c478bd9Sstevel@tonic-gate 			(*pfv_uar)(pr_q->data);
3807c478bd9Sstevel@tonic-gate 		/* Thanks to wuth@castrov.cuc.ab.ca for the following stmt. */
3817c478bd9Sstevel@tonic-gate 		memput(pr_q, sizeof(tree));
3827c478bd9Sstevel@tonic-gate 		i_ret = TRUE;
3837c478bd9Sstevel@tonic-gate 	}
3847c478bd9Sstevel@tonic-gate 	RET(i_ret)
3857c478bd9Sstevel@tonic-gate }
3867c478bd9Sstevel@tonic-gate 
3877c478bd9Sstevel@tonic-gate static void
del(tree ** ppr_r,int * pi_balance,tree ** ppr_q,void (* pfv_uar)(tree_t),int * pi_uar_called)3887c478bd9Sstevel@tonic-gate del(tree **ppr_r, int *pi_balance, tree **ppr_q,
3897c478bd9Sstevel@tonic-gate     void (*pfv_uar)(tree_t), int *pi_uar_called)
3907c478bd9Sstevel@tonic-gate {
3917c478bd9Sstevel@tonic-gate 	ENTER("del")
3927c478bd9Sstevel@tonic-gate 
3937c478bd9Sstevel@tonic-gate 	if ((*ppr_r)->right != NULL) {
3947c478bd9Sstevel@tonic-gate 		del(&(*ppr_r)->right, pi_balance, ppr_q,
3957c478bd9Sstevel@tonic-gate 		    pfv_uar, pi_uar_called);
3967c478bd9Sstevel@tonic-gate 		if (*pi_balance)
3977c478bd9Sstevel@tonic-gate 			bal_R(ppr_r, pi_balance);
3987c478bd9Sstevel@tonic-gate 	} else {
3997c478bd9Sstevel@tonic-gate 		if (pfv_uar)
4007c478bd9Sstevel@tonic-gate 			(*pfv_uar)((*ppr_q)->data);
4017c478bd9Sstevel@tonic-gate 		*pi_uar_called = TRUE;
4027c478bd9Sstevel@tonic-gate 		(*ppr_q)->data = (*ppr_r)->data;
4037c478bd9Sstevel@tonic-gate 		*ppr_q = *ppr_r;
4047c478bd9Sstevel@tonic-gate 		*ppr_r = (*ppr_r)->left;
4057c478bd9Sstevel@tonic-gate 		*pi_balance = TRUE;
4067c478bd9Sstevel@tonic-gate 	}
4077c478bd9Sstevel@tonic-gate 
4087c478bd9Sstevel@tonic-gate 	RETV
4097c478bd9Sstevel@tonic-gate }
4107c478bd9Sstevel@tonic-gate 
4117c478bd9Sstevel@tonic-gate static void
bal_L(tree ** ppr_p,int * pi_balance)4127c478bd9Sstevel@tonic-gate bal_L(tree **ppr_p, int *pi_balance) {
4137c478bd9Sstevel@tonic-gate 	tree *p1, *p2;
4147c478bd9Sstevel@tonic-gate 	int b1, b2;
4157c478bd9Sstevel@tonic-gate 
4167c478bd9Sstevel@tonic-gate 	ENTER("bal_L")
4177c478bd9Sstevel@tonic-gate 	MSG("left branch has shrunk")
4187c478bd9Sstevel@tonic-gate 
4197c478bd9Sstevel@tonic-gate 	switch ((*ppr_p)->bal) {
4207c478bd9Sstevel@tonic-gate 	case -1:
4217c478bd9Sstevel@tonic-gate 		MSG("was imbalanced, fixed implicitly")
4227c478bd9Sstevel@tonic-gate 		(*ppr_p)->bal = 0;
4237c478bd9Sstevel@tonic-gate 		break;
4247c478bd9Sstevel@tonic-gate 	case 0:
4257c478bd9Sstevel@tonic-gate 		MSG("was okay, is now one off")
4267c478bd9Sstevel@tonic-gate 		(*ppr_p)->bal = 1;
4277c478bd9Sstevel@tonic-gate 		*pi_balance = FALSE;
4287c478bd9Sstevel@tonic-gate 		break;
4297c478bd9Sstevel@tonic-gate 	case 1:
4307c478bd9Sstevel@tonic-gate 		MSG("was already off, this is too much")
4317c478bd9Sstevel@tonic-gate 		p1 = (*ppr_p)->right;
4327c478bd9Sstevel@tonic-gate 		b1 = p1->bal;
4337c478bd9Sstevel@tonic-gate 		if (b1 >= 0) {
4347c478bd9Sstevel@tonic-gate 			MSG("single RR")
4357c478bd9Sstevel@tonic-gate 			(*ppr_p)->right = p1->left;
4367c478bd9Sstevel@tonic-gate 			p1->left = *ppr_p;
4377c478bd9Sstevel@tonic-gate 			if (b1 == 0) {
4387c478bd9Sstevel@tonic-gate 				MSG("b1 == 0")
4397c478bd9Sstevel@tonic-gate 				(*ppr_p)->bal = 1;
4407c478bd9Sstevel@tonic-gate 				p1->bal = -1;
4417c478bd9Sstevel@tonic-gate 				*pi_balance = FALSE;
4427c478bd9Sstevel@tonic-gate 			} else {
4437c478bd9Sstevel@tonic-gate 				MSG("b1 != 0")
4447c478bd9Sstevel@tonic-gate 				(*ppr_p)->bal = 0;
4457c478bd9Sstevel@tonic-gate 				p1->bal = 0;
4467c478bd9Sstevel@tonic-gate 			}
4477c478bd9Sstevel@tonic-gate 			*ppr_p = p1;
4487c478bd9Sstevel@tonic-gate 		} else {
4497c478bd9Sstevel@tonic-gate 			MSG("double RL")
4507c478bd9Sstevel@tonic-gate 			p2 = p1->left;
4517c478bd9Sstevel@tonic-gate 			b2 = p2->bal;
4527c478bd9Sstevel@tonic-gate 			p1->left = p2->right;
4537c478bd9Sstevel@tonic-gate 			p2->right = p1;
4547c478bd9Sstevel@tonic-gate 			(*ppr_p)->right = p2->left;
4557c478bd9Sstevel@tonic-gate 			p2->left = *ppr_p;
4567c478bd9Sstevel@tonic-gate 			if (b2 == 1)
4577c478bd9Sstevel@tonic-gate 				(*ppr_p)->bal = -1;
4587c478bd9Sstevel@tonic-gate 			else
4597c478bd9Sstevel@tonic-gate 				(*ppr_p)->bal = 0;
4607c478bd9Sstevel@tonic-gate 			if (b2 == -1)
4617c478bd9Sstevel@tonic-gate 				p1->bal = 1;
4627c478bd9Sstevel@tonic-gate 			else
4637c478bd9Sstevel@tonic-gate 				p1->bal = 0;
4647c478bd9Sstevel@tonic-gate 			*ppr_p = p2;
4657c478bd9Sstevel@tonic-gate 			p2->bal = 0;
4667c478bd9Sstevel@tonic-gate 		}
4677c478bd9Sstevel@tonic-gate 	}
4687c478bd9Sstevel@tonic-gate 	RETV
4697c478bd9Sstevel@tonic-gate }
4707c478bd9Sstevel@tonic-gate 
4717c478bd9Sstevel@tonic-gate static void
bal_R(tree ** ppr_p,int * pi_balance)4727c478bd9Sstevel@tonic-gate bal_R(tree **ppr_p, int *pi_balance) {
4737c478bd9Sstevel@tonic-gate 	tree *p1, *p2;
4747c478bd9Sstevel@tonic-gate 	int b1, b2;
4757c478bd9Sstevel@tonic-gate 
4767c478bd9Sstevel@tonic-gate 	ENTER("bal_R")
4777c478bd9Sstevel@tonic-gate 	MSG("right branch has shrunk")
4787c478bd9Sstevel@tonic-gate 	switch ((*ppr_p)->bal) {
4797c478bd9Sstevel@tonic-gate 	case 1:
4807c478bd9Sstevel@tonic-gate 		MSG("was imbalanced, fixed implicitly")
4817c478bd9Sstevel@tonic-gate 		(*ppr_p)->bal = 0;
4827c478bd9Sstevel@tonic-gate 		break;
4837c478bd9Sstevel@tonic-gate 	case 0:
4847c478bd9Sstevel@tonic-gate 		MSG("was okay, is now one off")
4857c478bd9Sstevel@tonic-gate 		(*ppr_p)->bal = -1;
4867c478bd9Sstevel@tonic-gate 		*pi_balance = FALSE;
4877c478bd9Sstevel@tonic-gate 		break;
4887c478bd9Sstevel@tonic-gate 	case -1:
4897c478bd9Sstevel@tonic-gate 		MSG("was already off, this is too much")
4907c478bd9Sstevel@tonic-gate 		p1 = (*ppr_p)->left;
4917c478bd9Sstevel@tonic-gate 		b1 = p1->bal;
4927c478bd9Sstevel@tonic-gate 		if (b1 <= 0) {
4937c478bd9Sstevel@tonic-gate 			MSG("single LL")
4947c478bd9Sstevel@tonic-gate 			(*ppr_p)->left = p1->right;
4957c478bd9Sstevel@tonic-gate 			p1->right = *ppr_p;
4967c478bd9Sstevel@tonic-gate 			if (b1 == 0) {
4977c478bd9Sstevel@tonic-gate 				MSG("b1 == 0")
4987c478bd9Sstevel@tonic-gate 				(*ppr_p)->bal = -1;
4997c478bd9Sstevel@tonic-gate 				p1->bal = 1;
5007c478bd9Sstevel@tonic-gate 				*pi_balance = FALSE;
5017c478bd9Sstevel@tonic-gate 			} else {
5027c478bd9Sstevel@tonic-gate 				MSG("b1 != 0")
5037c478bd9Sstevel@tonic-gate 				(*ppr_p)->bal = 0;
5047c478bd9Sstevel@tonic-gate 				p1->bal = 0;
5057c478bd9Sstevel@tonic-gate 			}
5067c478bd9Sstevel@tonic-gate 			*ppr_p = p1;
5077c478bd9Sstevel@tonic-gate 		} else {
5087c478bd9Sstevel@tonic-gate 			MSG("double LR")
5097c478bd9Sstevel@tonic-gate 			p2 = p1->right;
5107c478bd9Sstevel@tonic-gate 			b2 = p2->bal;
5117c478bd9Sstevel@tonic-gate 			p1->right = p2->left;
5127c478bd9Sstevel@tonic-gate 			p2->left = p1;
5137c478bd9Sstevel@tonic-gate 			(*ppr_p)->left = p2->right;
5147c478bd9Sstevel@tonic-gate 			p2->right = *ppr_p;
5157c478bd9Sstevel@tonic-gate 			if (b2 == -1)
5167c478bd9Sstevel@tonic-gate 				(*ppr_p)->bal = 1;
5177c478bd9Sstevel@tonic-gate 			else
5187c478bd9Sstevel@tonic-gate 				(*ppr_p)->bal = 0;
5197c478bd9Sstevel@tonic-gate 			if (b2 == 1)
5207c478bd9Sstevel@tonic-gate 				p1->bal = -1;
5217c478bd9Sstevel@tonic-gate 			else
5227c478bd9Sstevel@tonic-gate 				p1->bal = 0;
5237c478bd9Sstevel@tonic-gate 			*ppr_p = p2;
5247c478bd9Sstevel@tonic-gate 			p2->bal = 0;
5257c478bd9Sstevel@tonic-gate 		}
5267c478bd9Sstevel@tonic-gate 	}
5277c478bd9Sstevel@tonic-gate 	RETV
5287c478bd9Sstevel@tonic-gate }
529*9525b14bSRao Shoaib 
530*9525b14bSRao Shoaib /*! \file */
531