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