avl.c revision 168404
1/* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License (the "License"). 6 * You may not use this file except in compliance with the License. 7 * 8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9 * or http://www.opensolaris.org/os/licensing. 10 * See the License for the specific language governing permissions 11 * and limitations under the License. 12 * 13 * When distributing Covered Code, include this CDDL HEADER in each 14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15 * If applicable, add the following below this CDDL HEADER, with the 16 * fields enclosed by brackets "[]" replaced with your own identifying 17 * information: Portions Copyright [yyyy] [name of copyright owner] 18 * 19 * CDDL HEADER END 20 */ 21/* 22 * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 23 * Use is subject to license terms. 24 */ 25 26#pragma ident "%Z%%M% %I% %E% SMI" 27 28 29/* 30 * AVL - generic AVL tree implementation for kernel use 31 * 32 * A complete description of AVL trees can be found in many CS textbooks. 33 * 34 * Here is a very brief overview. An AVL tree is a binary search tree that is 35 * almost perfectly balanced. By "almost" perfectly balanced, we mean that at 36 * any given node, the left and right subtrees are allowed to differ in height 37 * by at most 1 level. 38 * 39 * This relaxation from a perfectly balanced binary tree allows doing 40 * insertion and deletion relatively efficiently. Searching the tree is 41 * still a fast operation, roughly O(log(N)). 42 * 43 * The key to insertion and deletion is a set of tree maniuplations called 44 * rotations, which bring unbalanced subtrees back into the semi-balanced state. 45 * 46 * This implementation of AVL trees has the following peculiarities: 47 * 48 * - The AVL specific data structures are physically embedded as fields 49 * in the "using" data structures. To maintain generality the code 50 * must constantly translate between "avl_node_t *" and containing 51 * data structure "void *"s by adding/subracting the avl_offset. 52 * 53 * - Since the AVL data is always embedded in other structures, there is 54 * no locking or memory allocation in the AVL routines. This must be 55 * provided for by the enclosing data structure's semantics. Typically, 56 * avl_insert()/_add()/_remove()/avl_insert_here() require some kind of 57 * exclusive write lock. Other operations require a read lock. 58 * 59 * - The implementation uses iteration instead of explicit recursion, 60 * since it is intended to run on limited size kernel stacks. Since 61 * there is no recursion stack present to move "up" in the tree, 62 * there is an explicit "parent" link in the avl_node_t. 63 * 64 * - The left/right children pointers of a node are in an array. 65 * In the code, variables (instead of constants) are used to represent 66 * left and right indices. The implementation is written as if it only 67 * dealt with left handed manipulations. By changing the value assigned 68 * to "left", the code also works for right handed trees. The 69 * following variables/terms are frequently used: 70 * 71 * int left; // 0 when dealing with left children, 72 * // 1 for dealing with right children 73 * 74 * int left_heavy; // -1 when left subtree is taller at some node, 75 * // +1 when right subtree is taller 76 * 77 * int right; // will be the opposite of left (0 or 1) 78 * int right_heavy;// will be the opposite of left_heavy (-1 or 1) 79 * 80 * int direction; // 0 for "<" (ie. left child); 1 for ">" (right) 81 * 82 * Though it is a little more confusing to read the code, the approach 83 * allows using half as much code (and hence cache footprint) for tree 84 * manipulations and eliminates many conditional branches. 85 * 86 * - The avl_index_t is an opaque "cookie" used to find nodes at or 87 * adjacent to where a new value would be inserted in the tree. The value 88 * is a modified "avl_node_t *". The bottom bit (normally 0 for a 89 * pointer) is set to indicate if that the new node has a value greater 90 * than the value of the indicated "avl_node_t *". 91 */ 92 93#include <sys/types.h> 94#include <sys/param.h> 95#include <sys/debug.h> 96#include <sys/avl.h> 97 98/* 99 * Small arrays to translate between balance (or diff) values and child indeces. 100 * 101 * Code that deals with binary tree data structures will randomly use 102 * left and right children when examining a tree. C "if()" statements 103 * which evaluate randomly suffer from very poor hardware branch prediction. 104 * In this code we avoid some of the branch mispredictions by using the 105 * following translation arrays. They replace random branches with an 106 * additional memory reference. Since the translation arrays are both very 107 * small the data should remain efficiently in cache. 108 */ 109static const int avl_child2balance[2] = {-1, 1}; 110static const int avl_balance2child[] = {0, 0, 1}; 111 112 113/* 114 * Walk from one node to the previous valued node (ie. an infix walk 115 * towards the left). At any given node we do one of 2 things: 116 * 117 * - If there is a left child, go to it, then to it's rightmost descendant. 118 * 119 * - otherwise we return thru parent nodes until we've come from a right child. 120 * 121 * Return Value: 122 * NULL - if at the end of the nodes 123 * otherwise next node 124 */ 125void * 126avl_walk(avl_tree_t *tree, void *oldnode, int left) 127{ 128 size_t off = tree->avl_offset; 129 avl_node_t *node = AVL_DATA2NODE(oldnode, off); 130 int right = 1 - left; 131 int was_child; 132 133 134 /* 135 * nowhere to walk to if tree is empty 136 */ 137 if (node == NULL) 138 return (NULL); 139 140 /* 141 * Visit the previous valued node. There are two possibilities: 142 * 143 * If this node has a left child, go down one left, then all 144 * the way right. 145 */ 146 if (node->avl_child[left] != NULL) { 147 for (node = node->avl_child[left]; 148 node->avl_child[right] != NULL; 149 node = node->avl_child[right]) 150 ; 151 /* 152 * Otherwise, return thru left children as far as we can. 153 */ 154 } else { 155 for (;;) { 156 was_child = AVL_XCHILD(node); 157 node = AVL_XPARENT(node); 158 if (node == NULL) 159 return (NULL); 160 if (was_child == right) 161 break; 162 } 163 } 164 165 return (AVL_NODE2DATA(node, off)); 166} 167 168/* 169 * Return the lowest valued node in a tree or NULL. 170 * (leftmost child from root of tree) 171 */ 172void * 173avl_first(avl_tree_t *tree) 174{ 175 avl_node_t *node; 176 avl_node_t *prev = NULL; 177 size_t off = tree->avl_offset; 178 179 for (node = tree->avl_root; node != NULL; node = node->avl_child[0]) 180 prev = node; 181 182 if (prev != NULL) 183 return (AVL_NODE2DATA(prev, off)); 184 return (NULL); 185} 186 187/* 188 * Return the highest valued node in a tree or NULL. 189 * (rightmost child from root of tree) 190 */ 191void * 192avl_last(avl_tree_t *tree) 193{ 194 avl_node_t *node; 195 avl_node_t *prev = NULL; 196 size_t off = tree->avl_offset; 197 198 for (node = tree->avl_root; node != NULL; node = node->avl_child[1]) 199 prev = node; 200 201 if (prev != NULL) 202 return (AVL_NODE2DATA(prev, off)); 203 return (NULL); 204} 205 206/* 207 * Access the node immediately before or after an insertion point. 208 * 209 * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child 210 * 211 * Return value: 212 * NULL: no node in the given direction 213 * "void *" of the found tree node 214 */ 215void * 216avl_nearest(avl_tree_t *tree, avl_index_t where, int direction) 217{ 218 int child = AVL_INDEX2CHILD(where); 219 avl_node_t *node = AVL_INDEX2NODE(where); 220 void *data; 221 size_t off = tree->avl_offset; 222 223 if (node == NULL) { 224 ASSERT(tree->avl_root == NULL); 225 return (NULL); 226 } 227 data = AVL_NODE2DATA(node, off); 228 if (child != direction) 229 return (data); 230 231 return (avl_walk(tree, data, direction)); 232} 233 234 235/* 236 * Search for the node which contains "value". The algorithm is a 237 * simple binary tree search. 238 * 239 * return value: 240 * NULL: the value is not in the AVL tree 241 * *where (if not NULL) is set to indicate the insertion point 242 * "void *" of the found tree node 243 */ 244void * 245avl_find(avl_tree_t *tree, void *value, avl_index_t *where) 246{ 247 avl_node_t *node; 248 avl_node_t *prev = NULL; 249 int child = 0; 250 int diff; 251 size_t off = tree->avl_offset; 252 253 for (node = tree->avl_root; node != NULL; 254 node = node->avl_child[child]) { 255 256 prev = node; 257 258 diff = tree->avl_compar(value, AVL_NODE2DATA(node, off)); 259 ASSERT(-1 <= diff && diff <= 1); 260 if (diff == 0) { 261#ifdef DEBUG 262 if (where != NULL) 263 *where = 0; 264#endif 265 return (AVL_NODE2DATA(node, off)); 266 } 267 child = avl_balance2child[1 + diff]; 268 269 } 270 271 if (where != NULL) 272 *where = AVL_MKINDEX(prev, child); 273 274 return (NULL); 275} 276 277 278/* 279 * Perform a rotation to restore balance at the subtree given by depth. 280 * 281 * This routine is used by both insertion and deletion. The return value 282 * indicates: 283 * 0 : subtree did not change height 284 * !0 : subtree was reduced in height 285 * 286 * The code is written as if handling left rotations, right rotations are 287 * symmetric and handled by swapping values of variables right/left[_heavy] 288 * 289 * On input balance is the "new" balance at "node". This value is either 290 * -2 or +2. 291 */ 292static int 293avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance) 294{ 295 int left = !(balance < 0); /* when balance = -2, left will be 0 */ 296 int right = 1 - left; 297 int left_heavy = balance >> 1; 298 int right_heavy = -left_heavy; 299 avl_node_t *parent = AVL_XPARENT(node); 300 avl_node_t *child = node->avl_child[left]; 301 avl_node_t *cright; 302 avl_node_t *gchild; 303 avl_node_t *gright; 304 avl_node_t *gleft; 305 int which_child = AVL_XCHILD(node); 306 int child_bal = AVL_XBALANCE(child); 307 308 /* BEGIN CSTYLED */ 309 /* 310 * case 1 : node is overly left heavy, the left child is balanced or 311 * also left heavy. This requires the following rotation. 312 * 313 * (node bal:-2) 314 * / \ 315 * / \ 316 * (child bal:0 or -1) 317 * / \ 318 * / \ 319 * cright 320 * 321 * becomes: 322 * 323 * (child bal:1 or 0) 324 * / \ 325 * / \ 326 * (node bal:-1 or 0) 327 * / \ 328 * / \ 329 * cright 330 * 331 * we detect this situation by noting that child's balance is not 332 * right_heavy. 333 */ 334 /* END CSTYLED */ 335 if (child_bal != right_heavy) { 336 337 /* 338 * compute new balance of nodes 339 * 340 * If child used to be left heavy (now balanced) we reduced 341 * the height of this sub-tree -- used in "return...;" below 342 */ 343 child_bal += right_heavy; /* adjust towards right */ 344 345 /* 346 * move "cright" to be node's left child 347 */ 348 cright = child->avl_child[right]; 349 node->avl_child[left] = cright; 350 if (cright != NULL) { 351 AVL_SETPARENT(cright, node); 352 AVL_SETCHILD(cright, left); 353 } 354 355 /* 356 * move node to be child's right child 357 */ 358 child->avl_child[right] = node; 359 AVL_SETBALANCE(node, -child_bal); 360 AVL_SETCHILD(node, right); 361 AVL_SETPARENT(node, child); 362 363 /* 364 * update the pointer into this subtree 365 */ 366 AVL_SETBALANCE(child, child_bal); 367 AVL_SETCHILD(child, which_child); 368 AVL_SETPARENT(child, parent); 369 if (parent != NULL) 370 parent->avl_child[which_child] = child; 371 else 372 tree->avl_root = child; 373 374 return (child_bal == 0); 375 } 376 377 /* BEGIN CSTYLED */ 378 /* 379 * case 2 : When node is left heavy, but child is right heavy we use 380 * a different rotation. 381 * 382 * (node b:-2) 383 * / \ 384 * / \ 385 * / \ 386 * (child b:+1) 387 * / \ 388 * / \ 389 * (gchild b: != 0) 390 * / \ 391 * / \ 392 * gleft gright 393 * 394 * becomes: 395 * 396 * (gchild b:0) 397 * / \ 398 * / \ 399 * / \ 400 * (child b:?) (node b:?) 401 * / \ / \ 402 * / \ / \ 403 * gleft gright 404 * 405 * computing the new balances is more complicated. As an example: 406 * if gchild was right_heavy, then child is now left heavy 407 * else it is balanced 408 */ 409 /* END CSTYLED */ 410 gchild = child->avl_child[right]; 411 gleft = gchild->avl_child[left]; 412 gright = gchild->avl_child[right]; 413 414 /* 415 * move gright to left child of node and 416 * 417 * move gleft to right child of node 418 */ 419 node->avl_child[left] = gright; 420 if (gright != NULL) { 421 AVL_SETPARENT(gright, node); 422 AVL_SETCHILD(gright, left); 423 } 424 425 child->avl_child[right] = gleft; 426 if (gleft != NULL) { 427 AVL_SETPARENT(gleft, child); 428 AVL_SETCHILD(gleft, right); 429 } 430 431 /* 432 * move child to left child of gchild and 433 * 434 * move node to right child of gchild and 435 * 436 * fixup parent of all this to point to gchild 437 */ 438 balance = AVL_XBALANCE(gchild); 439 gchild->avl_child[left] = child; 440 AVL_SETBALANCE(child, (balance == right_heavy ? left_heavy : 0)); 441 AVL_SETPARENT(child, gchild); 442 AVL_SETCHILD(child, left); 443 444 gchild->avl_child[right] = node; 445 AVL_SETBALANCE(node, (balance == left_heavy ? right_heavy : 0)); 446 AVL_SETPARENT(node, gchild); 447 AVL_SETCHILD(node, right); 448 449 AVL_SETBALANCE(gchild, 0); 450 AVL_SETPARENT(gchild, parent); 451 AVL_SETCHILD(gchild, which_child); 452 if (parent != NULL) 453 parent->avl_child[which_child] = gchild; 454 else 455 tree->avl_root = gchild; 456 457 return (1); /* the new tree is always shorter */ 458} 459 460 461/* 462 * Insert a new node into an AVL tree at the specified (from avl_find()) place. 463 * 464 * Newly inserted nodes are always leaf nodes in the tree, since avl_find() 465 * searches out to the leaf positions. The avl_index_t indicates the node 466 * which will be the parent of the new node. 467 * 468 * After the node is inserted, a single rotation further up the tree may 469 * be necessary to maintain an acceptable AVL balance. 470 */ 471void 472avl_insert(avl_tree_t *tree, void *new_data, avl_index_t where) 473{ 474 avl_node_t *node; 475 avl_node_t *parent = AVL_INDEX2NODE(where); 476 int old_balance; 477 int new_balance; 478 int which_child = AVL_INDEX2CHILD(where); 479 size_t off = tree->avl_offset; 480 481 ASSERT(tree); 482#ifdef _LP64 483 ASSERT(((uintptr_t)new_data & 0x7) == 0); 484#endif 485 486 node = AVL_DATA2NODE(new_data, off); 487 488 /* 489 * First, add the node to the tree at the indicated position. 490 */ 491 ++tree->avl_numnodes; 492 493 node->avl_child[0] = NULL; 494 node->avl_child[1] = NULL; 495 496 AVL_SETCHILD(node, which_child); 497 AVL_SETBALANCE(node, 0); 498 AVL_SETPARENT(node, parent); 499 if (parent != NULL) { 500 ASSERT(parent->avl_child[which_child] == NULL); 501 parent->avl_child[which_child] = node; 502 } else { 503 ASSERT(tree->avl_root == NULL); 504 tree->avl_root = node; 505 } 506 /* 507 * Now, back up the tree modifying the balance of all nodes above the 508 * insertion point. If we get to a highly unbalanced ancestor, we 509 * need to do a rotation. If we back out of the tree we are done. 510 * If we brought any subtree into perfect balance (0), we are also done. 511 */ 512 for (;;) { 513 node = parent; 514 if (node == NULL) 515 return; 516 517 /* 518 * Compute the new balance 519 */ 520 old_balance = AVL_XBALANCE(node); 521 new_balance = old_balance + avl_child2balance[which_child]; 522 523 /* 524 * If we introduced equal balance, then we are done immediately 525 */ 526 if (new_balance == 0) { 527 AVL_SETBALANCE(node, 0); 528 return; 529 } 530 531 /* 532 * If both old and new are not zero we went 533 * from -1 to -2 balance, do a rotation. 534 */ 535 if (old_balance != 0) 536 break; 537 538 AVL_SETBALANCE(node, new_balance); 539 parent = AVL_XPARENT(node); 540 which_child = AVL_XCHILD(node); 541 } 542 543 /* 544 * perform a rotation to fix the tree and return 545 */ 546 (void) avl_rotation(tree, node, new_balance); 547} 548 549/* 550 * Insert "new_data" in "tree" in the given "direction" either after or 551 * before (AVL_AFTER, AVL_BEFORE) the data "here". 552 * 553 * Insertions can only be done at empty leaf points in the tree, therefore 554 * if the given child of the node is already present we move to either 555 * the AVL_PREV or AVL_NEXT and reverse the insertion direction. Since 556 * every other node in the tree is a leaf, this always works. 557 * 558 * To help developers using this interface, we assert that the new node 559 * is correctly ordered at every step of the way in DEBUG kernels. 560 */ 561void 562avl_insert_here( 563 avl_tree_t *tree, 564 void *new_data, 565 void *here, 566 int direction) 567{ 568 avl_node_t *node; 569 int child = direction; /* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */ 570#ifdef DEBUG 571 int diff; 572#endif 573 574 ASSERT(tree != NULL); 575 ASSERT(new_data != NULL); 576 ASSERT(here != NULL); 577 ASSERT(direction == AVL_BEFORE || direction == AVL_AFTER); 578 579 /* 580 * If corresponding child of node is not NULL, go to the neighboring 581 * node and reverse the insertion direction. 582 */ 583 node = AVL_DATA2NODE(here, tree->avl_offset); 584 585#ifdef DEBUG 586 diff = tree->avl_compar(new_data, here); 587 ASSERT(-1 <= diff && diff <= 1); 588 ASSERT(diff != 0); 589 ASSERT(diff > 0 ? child == 1 : child == 0); 590#endif 591 592 if (node->avl_child[child] != NULL) { 593 node = node->avl_child[child]; 594 child = 1 - child; 595 while (node->avl_child[child] != NULL) { 596#ifdef DEBUG 597 diff = tree->avl_compar(new_data, 598 AVL_NODE2DATA(node, tree->avl_offset)); 599 ASSERT(-1 <= diff && diff <= 1); 600 ASSERT(diff != 0); 601 ASSERT(diff > 0 ? child == 1 : child == 0); 602#endif 603 node = node->avl_child[child]; 604 } 605#ifdef DEBUG 606 diff = tree->avl_compar(new_data, 607 AVL_NODE2DATA(node, tree->avl_offset)); 608 ASSERT(-1 <= diff && diff <= 1); 609 ASSERT(diff != 0); 610 ASSERT(diff > 0 ? child == 1 : child == 0); 611#endif 612 } 613 ASSERT(node->avl_child[child] == NULL); 614 615 avl_insert(tree, new_data, AVL_MKINDEX(node, child)); 616} 617 618/* 619 * Add a new node to an AVL tree. 620 */ 621void 622avl_add(avl_tree_t *tree, void *new_node) 623{ 624 avl_index_t where; 625 626 /* 627 * This is unfortunate. We want to call panic() here, even for 628 * non-DEBUG kernels. In userland, however, we can't depend on anything 629 * in libc or else the rtld build process gets confused. So, all we can 630 * do in userland is resort to a normal ASSERT(). 631 */ 632 if (avl_find(tree, new_node, &where) != NULL) 633#ifdef _KERNEL 634 panic("avl_find() succeeded inside avl_add()"); 635#else 636 ASSERT(0); 637#endif 638 avl_insert(tree, new_node, where); 639} 640 641/* 642 * Delete a node from the AVL tree. Deletion is similar to insertion, but 643 * with 2 complications. 644 * 645 * First, we may be deleting an interior node. Consider the following subtree: 646 * 647 * d c c 648 * / \ / \ / \ 649 * b e b e b e 650 * / \ / \ / 651 * a c a a 652 * 653 * When we are deleting node (d), we find and bring up an adjacent valued leaf 654 * node, say (c), to take the interior node's place. In the code this is 655 * handled by temporarily swapping (d) and (c) in the tree and then using 656 * common code to delete (d) from the leaf position. 657 * 658 * Secondly, an interior deletion from a deep tree may require more than one 659 * rotation to fix the balance. This is handled by moving up the tree through 660 * parents and applying rotations as needed. The return value from 661 * avl_rotation() is used to detect when a subtree did not change overall 662 * height due to a rotation. 663 */ 664void 665avl_remove(avl_tree_t *tree, void *data) 666{ 667 avl_node_t *delete; 668 avl_node_t *parent; 669 avl_node_t *node; 670 avl_node_t tmp; 671 int old_balance; 672 int new_balance; 673 int left; 674 int right; 675 int which_child; 676 size_t off = tree->avl_offset; 677 678 ASSERT(tree); 679 680 delete = AVL_DATA2NODE(data, off); 681 682 /* 683 * Deletion is easiest with a node that has at most 1 child. 684 * We swap a node with 2 children with a sequentially valued 685 * neighbor node. That node will have at most 1 child. Note this 686 * has no effect on the ordering of the remaining nodes. 687 * 688 * As an optimization, we choose the greater neighbor if the tree 689 * is right heavy, otherwise the left neighbor. This reduces the 690 * number of rotations needed. 691 */ 692 if (delete->avl_child[0] != NULL && delete->avl_child[1] != NULL) { 693 694 /* 695 * choose node to swap from whichever side is taller 696 */ 697 old_balance = AVL_XBALANCE(delete); 698 left = avl_balance2child[old_balance + 1]; 699 right = 1 - left; 700 701 /* 702 * get to the previous value'd node 703 * (down 1 left, as far as possible right) 704 */ 705 for (node = delete->avl_child[left]; 706 node->avl_child[right] != NULL; 707 node = node->avl_child[right]) 708 ; 709 710 /* 711 * create a temp placeholder for 'node' 712 * move 'node' to delete's spot in the tree 713 */ 714 tmp = *node; 715 716 *node = *delete; 717 if (node->avl_child[left] == node) 718 node->avl_child[left] = &tmp; 719 720 parent = AVL_XPARENT(node); 721 if (parent != NULL) 722 parent->avl_child[AVL_XCHILD(node)] = node; 723 else 724 tree->avl_root = node; 725 AVL_SETPARENT(node->avl_child[left], node); 726 AVL_SETPARENT(node->avl_child[right], node); 727 728 /* 729 * Put tmp where node used to be (just temporary). 730 * It always has a parent and at most 1 child. 731 */ 732 delete = &tmp; 733 parent = AVL_XPARENT(delete); 734 parent->avl_child[AVL_XCHILD(delete)] = delete; 735 which_child = (delete->avl_child[1] != 0); 736 if (delete->avl_child[which_child] != NULL) 737 AVL_SETPARENT(delete->avl_child[which_child], delete); 738 } 739 740 741 /* 742 * Here we know "delete" is at least partially a leaf node. It can 743 * be easily removed from the tree. 744 */ 745 ASSERT(tree->avl_numnodes > 0); 746 --tree->avl_numnodes; 747 parent = AVL_XPARENT(delete); 748 which_child = AVL_XCHILD(delete); 749 if (delete->avl_child[0] != NULL) 750 node = delete->avl_child[0]; 751 else 752 node = delete->avl_child[1]; 753 754 /* 755 * Connect parent directly to node (leaving out delete). 756 */ 757 if (node != NULL) { 758 AVL_SETPARENT(node, parent); 759 AVL_SETCHILD(node, which_child); 760 } 761 if (parent == NULL) { 762 tree->avl_root = node; 763 return; 764 } 765 parent->avl_child[which_child] = node; 766 767 768 /* 769 * Since the subtree is now shorter, begin adjusting parent balances 770 * and performing any needed rotations. 771 */ 772 do { 773 774 /* 775 * Move up the tree and adjust the balance 776 * 777 * Capture the parent and which_child values for the next 778 * iteration before any rotations occur. 779 */ 780 node = parent; 781 old_balance = AVL_XBALANCE(node); 782 new_balance = old_balance - avl_child2balance[which_child]; 783 parent = AVL_XPARENT(node); 784 which_child = AVL_XCHILD(node); 785 786 /* 787 * If a node was in perfect balance but isn't anymore then 788 * we can stop, since the height didn't change above this point 789 * due to a deletion. 790 */ 791 if (old_balance == 0) { 792 AVL_SETBALANCE(node, new_balance); 793 break; 794 } 795 796 /* 797 * If the new balance is zero, we don't need to rotate 798 * else 799 * need a rotation to fix the balance. 800 * If the rotation doesn't change the height 801 * of the sub-tree we have finished adjusting. 802 */ 803 if (new_balance == 0) 804 AVL_SETBALANCE(node, new_balance); 805 else if (!avl_rotation(tree, node, new_balance)) 806 break; 807 } while (parent != NULL); 808} 809 810/* 811 * initialize a new AVL tree 812 */ 813void 814avl_create(avl_tree_t *tree, int (*compar) (const void *, const void *), 815 size_t size, size_t offset) 816{ 817 ASSERT(tree); 818 ASSERT(compar); 819 ASSERT(size > 0); 820 ASSERT(size >= offset + sizeof (avl_node_t)); 821#ifdef _LP64 822 ASSERT((offset & 0x7) == 0); 823#endif 824 825 tree->avl_compar = compar; 826 tree->avl_root = NULL; 827 tree->avl_numnodes = 0; 828 tree->avl_size = size; 829 tree->avl_offset = offset; 830} 831 832/* 833 * Delete a tree. 834 */ 835/* ARGSUSED */ 836void 837avl_destroy(avl_tree_t *tree) 838{ 839 ASSERT(tree); 840 ASSERT(tree->avl_numnodes == 0); 841 ASSERT(tree->avl_root == NULL); 842} 843 844 845/* 846 * Return the number of nodes in an AVL tree. 847 */ 848ulong_t 849avl_numnodes(avl_tree_t *tree) 850{ 851 ASSERT(tree); 852 return (tree->avl_numnodes); 853} 854 855 856#define CHILDBIT (1L) 857 858/* 859 * Post-order tree walk used to visit all tree nodes and destroy the tree 860 * in post order. This is used for destroying a tree w/o paying any cost 861 * for rebalancing it. 862 * 863 * example: 864 * 865 * void *cookie = NULL; 866 * my_data_t *node; 867 * 868 * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL) 869 * free(node); 870 * avl_destroy(tree); 871 * 872 * The cookie is really an avl_node_t to the current node's parent and 873 * an indication of which child you looked at last. 874 * 875 * On input, a cookie value of CHILDBIT indicates the tree is done. 876 */ 877void * 878avl_destroy_nodes(avl_tree_t *tree, void **cookie) 879{ 880 avl_node_t *node; 881 avl_node_t *parent; 882 int child; 883 void *first; 884 size_t off = tree->avl_offset; 885 886 /* 887 * Initial calls go to the first node or it's right descendant. 888 */ 889 if (*cookie == NULL) { 890 first = avl_first(tree); 891 892 /* 893 * deal with an empty tree 894 */ 895 if (first == NULL) { 896 *cookie = (void *)CHILDBIT; 897 return (NULL); 898 } 899 900 node = AVL_DATA2NODE(first, off); 901 parent = AVL_XPARENT(node); 902 goto check_right_side; 903 } 904 905 /* 906 * If there is no parent to return to we are done. 907 */ 908 parent = (avl_node_t *)((uintptr_t)(*cookie) & ~CHILDBIT); 909 if (parent == NULL) { 910 if (tree->avl_root != NULL) { 911 ASSERT(tree->avl_numnodes == 1); 912 tree->avl_root = NULL; 913 tree->avl_numnodes = 0; 914 } 915 return (NULL); 916 } 917 918 /* 919 * Remove the child pointer we just visited from the parent and tree. 920 */ 921 child = (uintptr_t)(*cookie) & CHILDBIT; 922 parent->avl_child[child] = NULL; 923 ASSERT(tree->avl_numnodes > 1); 924 --tree->avl_numnodes; 925 926 /* 927 * If we just did a right child or there isn't one, go up to parent. 928 */ 929 if (child == 1 || parent->avl_child[1] == NULL) { 930 node = parent; 931 parent = AVL_XPARENT(parent); 932 goto done; 933 } 934 935 /* 936 * Do parent's right child, then leftmost descendent. 937 */ 938 node = parent->avl_child[1]; 939 while (node->avl_child[0] != NULL) { 940 parent = node; 941 node = node->avl_child[0]; 942 } 943 944 /* 945 * If here, we moved to a left child. It may have one 946 * child on the right (when balance == +1). 947 */ 948check_right_side: 949 if (node->avl_child[1] != NULL) { 950 ASSERT(AVL_XBALANCE(node) == 1); 951 parent = node; 952 node = node->avl_child[1]; 953 ASSERT(node->avl_child[0] == NULL && 954 node->avl_child[1] == NULL); 955 } else { 956 ASSERT(AVL_XBALANCE(node) <= 0); 957 } 958 959done: 960 if (parent == NULL) { 961 *cookie = (void *)CHILDBIT; 962 ASSERT(node == tree->avl_root); 963 } else { 964 *cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node)); 965 } 966 967 return (AVL_NODE2DATA(node, off)); 968} 969