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 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 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 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 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 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 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 * 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 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 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 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 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