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