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