cddl/contrib/opensolaris/common/avl/avl.c

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