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