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