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