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