/* * CDDL HEADER START * * The contents of this file are subject to the terms of the * Common Development and Distribution License (the "License"). * You may not use this file except in compliance with the License. * * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE * or http://www.opensolaris.org/os/licensing. * See the License for the specific language governing permissions * and limitations under the License. * * When distributing Covered Code, include this CDDL HEADER in each * file and include the License file at usr/src/OPENSOLARIS.LICENSE. * If applicable, add the following below this CDDL HEADER, with the * fields enclosed by brackets "[]" replaced with your own identifying * information: Portions Copyright [yyyy] [name of copyright owner] * * CDDL HEADER END */ /* * Copyright 2009 Sun Microsystems, Inc. All rights reserved. * Use is subject to license terms. */ /* * Copyright 2015 Nexenta Systems, Inc. All rights reserved. * Copyright (c) 2015 by Delphix. All rights reserved. */ /* * AVL - generic AVL tree implementation for kernel use * * A complete description of AVL trees can be found in many CS textbooks. * * Here is a very brief overview. An AVL tree is a binary search tree that is * almost perfectly balanced. By "almost" perfectly balanced, we mean that at * any given node, the left and right subtrees are allowed to differ in height * by at most 1 level. * * This relaxation from a perfectly balanced binary tree allows doing * insertion and deletion relatively efficiently. Searching the tree is * still a fast operation, roughly O(log(N)). * * The key to insertion and deletion is a set of tree manipulations called * rotations, which bring unbalanced subtrees back into the semi-balanced state. * * This implementation of AVL trees has the following peculiarities: * * - The AVL specific data structures are physically embedded as fields * in the "using" data structures. To maintain generality the code * must constantly translate between "avl_node_t *" and containing * data structure "void *"s by adding/subtracting the avl_offset. * * - Since the AVL data is always embedded in other structures, there is * no locking or memory allocation in the AVL routines. This must be * provided for by the enclosing data structure's semantics. Typically, * avl_insert()/_add()/_remove()/avl_insert_here() require some kind of * exclusive write lock. Other operations require a read lock. * * - The implementation uses iteration instead of explicit recursion, * since it is intended to run on limited size kernel stacks. Since * there is no recursion stack present to move "up" in the tree, * there is an explicit "parent" link in the avl_node_t. * * - The left/right children pointers of a node are in an array. * In the code, variables (instead of constants) are used to represent * left and right indices. The implementation is written as if it only * dealt with left handed manipulations. By changing the value assigned * to "left", the code also works for right handed trees. The * following variables/terms are frequently used: * * int left; // 0 when dealing with left children, * // 1 for dealing with right children * * int left_heavy; // -1 when left subtree is taller at some node, * // +1 when right subtree is taller * * int right; // will be the opposite of left (0 or 1) * int right_heavy;// will be the opposite of left_heavy (-1 or 1) * * int direction; // 0 for "<" (ie. left child); 1 for ">" (right) * * Though it is a little more confusing to read the code, the approach * allows using half as much code (and hence cache footprint) for tree * manipulations and eliminates many conditional branches. * * - The avl_index_t is an opaque "cookie" used to find nodes at or * adjacent to where a new value would be inserted in the tree. The value * is a modified "avl_node_t *". The bottom bit (normally 0 for a * pointer) is set to indicate if that the new node has a value greater * than the value of the indicated "avl_node_t *". * * Note - in addition to userland (e.g. libavl and libutil) and the kernel * (e.g. genunix), avl.c is compiled into ld.so and kmdb's genunix module, * which each have their own compilation environments and subsequent * requirements. Each of these environments must be considered when adding * dependencies from avl.c. */ #include <sys/types.h> #include <sys/param.h> #include <sys/debug.h> #include <sys/avl.h> #include <sys/cmn_err.h> /* * Walk from one node to the previous valued node (ie. an infix walk * towards the left). At any given node we do one of 2 things: * * - If there is a left child, go to it, then to it's rightmost descendant. * * - otherwise we return through parent nodes until we've come from a right * child. * * Return Value: * NULL - if at the end of the nodes * otherwise next node */ void * avl_walk(avl_tree_t *tree, void *oldnode, int left) { size_t off = tree->avl_offset; avl_node_t *node = AVL_DATA2NODE(oldnode, off); int right = 1 - left; int was_child; /* * nowhere to walk to if tree is empty */ if (node == NULL) return (NULL); /* * Visit the previous valued node. There are two possibilities: * * If this node has a left child, go down one left, then all * the way right. */ if (node->avl_child[left] != NULL) { for (node = node->avl_child[left]; node->avl_child[right] != NULL; node = node->avl_child[right]) ; /* * Otherwise, return thru left children as far as we can. */ } else { for (;;) { was_child = AVL_XCHILD(node); node = AVL_XPARENT(node); if (node == NULL) return (NULL); if (was_child == right) break; } } return (AVL_NODE2DATA(node, off)); } /* * Return the lowest valued node in a tree or NULL. * (leftmost child from root of tree) */ void * avl_first(avl_tree_t *tree) { avl_node_t *node; avl_node_t *prev = NULL; size_t off = tree->avl_offset; for (node = tree->avl_root; node != NULL; node = node->avl_child[0]) prev = node; if (prev != NULL) return (AVL_NODE2DATA(prev, off)); return (NULL); } /* * Return the highest valued node in a tree or NULL. * (rightmost child from root of tree) */ void * avl_last(avl_tree_t *tree) { avl_node_t *node; avl_node_t *prev = NULL; size_t off = tree->avl_offset; for (node = tree->avl_root; node != NULL; node = node->avl_child[1]) prev = node; if (prev != NULL) return (AVL_NODE2DATA(prev, off)); return (NULL); } /* * Access the node immediately before or after an insertion point. * * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child * * Return value: * NULL: no node in the given direction * "void *" of the found tree node */ void * avl_nearest(avl_tree_t *tree, avl_index_t where, int direction) { int child = AVL_INDEX2CHILD(where); avl_node_t *node = AVL_INDEX2NODE(where); void *data; size_t off = tree->avl_offset; if (node == NULL) { ASSERT(tree->avl_root == NULL); return (NULL); } data = AVL_NODE2DATA(node, off); if (child != direction) return (data); return (avl_walk(tree, data, direction)); } /* * Search for the node which contains "value". The algorithm is a * simple binary tree search. * * return value: * NULL: the value is not in the AVL tree * *where (if not NULL) is set to indicate the insertion point * "void *" of the found tree node */ void * avl_find(avl_tree_t *tree, const void *value, avl_index_t *where) { avl_node_t *node; avl_node_t *prev = NULL; int child = 0; int diff; size_t off = tree->avl_offset; for (node = tree->avl_root; node != NULL; node = node->avl_child[child]) { prev = node; diff = tree->avl_compar(value, AVL_NODE2DATA(node, off)); ASSERT(-1 <= diff && diff <= 1); if (diff == 0) { #ifdef DEBUG if (where != NULL) *where = 0; #endif return (AVL_NODE2DATA(node, off)); } child = (diff > 0); } if (where != NULL) *where = AVL_MKINDEX(prev, child); return (NULL); } /* * Perform a rotation to restore balance at the subtree given by depth. * * This routine is used by both insertion and deletion. The return value * indicates: * 0 : subtree did not change height * !0 : subtree was reduced in height * * The code is written as if handling left rotations, right rotations are * symmetric and handled by swapping values of variables right/left[_heavy] * * On input balance is the "new" balance at "node". This value is either * -2 or +2. */ static int avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance) { int left = !(balance < 0); /* when balance = -2, left will be 0 */ int right = 1 - left; int left_heavy = balance >> 1; int right_heavy = -left_heavy; avl_node_t *parent = AVL_XPARENT(node); avl_node_t *child = node->avl_child[left]; avl_node_t *cright; avl_node_t *gchild; avl_node_t *gright; avl_node_t *gleft; int which_child = AVL_XCHILD(node); int child_bal = AVL_XBALANCE(child); /* BEGIN CSTYLED */ /* * case 1 : node is overly left heavy, the left child is balanced or * also left heavy. This requires the following rotation. * * (node bal:-2) * / \ * / \ * (child bal:0 or -1) * / \ * / \ * cright * * becomes: * * (child bal:1 or 0) * / \ * / \ * (node bal:-1 or 0) * / \ * / \ * cright * * we detect this situation by noting that child's balance is not * right_heavy. */ /* END CSTYLED */ if (child_bal != right_heavy) { /* * compute new balance of nodes * * If child used to be left heavy (now balanced) we reduced * the height of this sub-tree -- used in "return...;" below */ child_bal += right_heavy; /* adjust towards right */ /* * move "cright" to be node's left child */ cright = child->avl_child[right]; node->avl_child[left] = cright; if (cright != NULL) { AVL_SETPARENT(cright, node); AVL_SETCHILD(cright, left); } /* * move node to be child's right child */ child->avl_child[right] = node; AVL_SETBALANCE(node, -child_bal); AVL_SETCHILD(node, right); AVL_SETPARENT(node, child); /* * update the pointer into this subtree */ AVL_SETBALANCE(child, child_bal); AVL_SETCHILD(child, which_child); AVL_SETPARENT(child, parent); if (parent != NULL) parent->avl_child[which_child] = child; else tree->avl_root = child; return (child_bal == 0); } /* BEGIN CSTYLED */ /* * case 2 : When node is left heavy, but child is right heavy we use * a different rotation. * * (node b:-2) * / \ * / \ * / \ * (child b:+1) * / \ * / \ * (gchild b: != 0) * / \ * / \ * gleft gright * * becomes: * * (gchild b:0) * / \ * / \ * / \ * (child b:?) (node b:?) * / \ / \ * / \ / \ * gleft gright * * computing the new balances is more complicated. As an example: * if gchild was right_heavy, then child is now left heavy * else it is balanced */ /* END CSTYLED */ gchild = child->avl_child[right]; gleft = gchild->avl_child[left]; gright = gchild->avl_child[right]; /* * move gright to left child of node and * * move gleft to right child of node */ node->avl_child[left] = gright; if (gright != NULL) { AVL_SETPARENT(gright, node); AVL_SETCHILD(gright, left); } child->avl_child[right] = gleft; if (gleft != NULL) { AVL_SETPARENT(gleft, child); AVL_SETCHILD(gleft, right); } /* * move child to left child of gchild and * * move node to right child of gchild and * * fixup parent of all this to point to gchild */ balance = AVL_XBALANCE(gchild); gchild->avl_child[left] = child; AVL_SETBALANCE(child, (balance == right_heavy ? left_heavy : 0)); AVL_SETPARENT(child, gchild); AVL_SETCHILD(child, left); gchild->avl_child[right] = node; AVL_SETBALANCE(node, (balance == left_heavy ? right_heavy : 0)); AVL_SETPARENT(node, gchild); AVL_SETCHILD(node, right); AVL_SETBALANCE(gchild, 0); AVL_SETPARENT(gchild, parent); AVL_SETCHILD(gchild, which_child); if (parent != NULL) parent->avl_child[which_child] = gchild; else tree->avl_root = gchild; return (1); /* the new tree is always shorter */ } /* * Insert a new node into an AVL tree at the specified (from avl_find()) place. * * Newly inserted nodes are always leaf nodes in the tree, since avl_find() * searches out to the leaf positions. The avl_index_t indicates the node * which will be the parent of the new node. * * After the node is inserted, a single rotation further up the tree may * be necessary to maintain an acceptable AVL balance. */ void avl_insert(avl_tree_t *tree, void *new_data, avl_index_t where) { avl_node_t *node; avl_node_t *parent = AVL_INDEX2NODE(where); int old_balance; int new_balance; int which_child = AVL_INDEX2CHILD(where); size_t off = tree->avl_offset; ASSERT(tree); #ifdef _LP64 ASSERT(((uintptr_t)new_data & 0x7) == 0); #endif node = AVL_DATA2NODE(new_data, off); /* * First, add the node to the tree at the indicated position. */ ++tree->avl_numnodes; node->avl_child[0] = NULL; node->avl_child[1] = NULL; AVL_SETCHILD(node, which_child); AVL_SETBALANCE(node, 0); AVL_SETPARENT(node, parent); if (parent != NULL) { ASSERT(parent->avl_child[which_child] == NULL); parent->avl_child[which_child] = node; } else { ASSERT(tree->avl_root == NULL); tree->avl_root = node; } /* * Now, back up the tree modifying the balance of all nodes above the * insertion point. If we get to a highly unbalanced ancestor, we * need to do a rotation. If we back out of the tree we are done. * If we brought any subtree into perfect balance (0), we are also done. */ for (;;) { node = parent; if (node == NULL) return; /* * Compute the new balance */ old_balance = AVL_XBALANCE(node); new_balance = old_balance + (which_child ? 1 : -1); /* * If we introduced equal balance, then we are done immediately */ if (new_balance == 0) { AVL_SETBALANCE(node, 0); return; } /* * If both old and new are not zero we went * from -1 to -2 balance, do a rotation. */ if (old_balance != 0) break; AVL_SETBALANCE(node, new_balance); parent = AVL_XPARENT(node); which_child = AVL_XCHILD(node); } /* * perform a rotation to fix the tree and return */ (void) avl_rotation(tree, node, new_balance); } /* * Insert "new_data" in "tree" in the given "direction" either after or * before (AVL_AFTER, AVL_BEFORE) the data "here". * * Insertions can only be done at empty leaf points in the tree, therefore * if the given child of the node is already present we move to either * the AVL_PREV or AVL_NEXT and reverse the insertion direction. Since * every other node in the tree is a leaf, this always works. * * To help developers using this interface, we assert that the new node * is correctly ordered at every step of the way in DEBUG kernels. */ void avl_insert_here( avl_tree_t *tree, void *new_data, void *here, int direction) { avl_node_t *node; int child = direction; /* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */ #ifdef DEBUG int diff; #endif ASSERT(tree != NULL); ASSERT(new_data != NULL); ASSERT(here != NULL); ASSERT(direction == AVL_BEFORE || direction == AVL_AFTER); /* * If corresponding child of node is not NULL, go to the neighboring * node and reverse the insertion direction. */ node = AVL_DATA2NODE(here, tree->avl_offset); #ifdef DEBUG diff = tree->avl_compar(new_data, here); ASSERT(-1 <= diff && diff <= 1); ASSERT(diff != 0); ASSERT(diff > 0 ? child == 1 : child == 0); #endif if (node->avl_child[child] != NULL) { node = node->avl_child[child]; child = 1 - child; while (node->avl_child[child] != NULL) { #ifdef DEBUG diff = tree->avl_compar(new_data, AVL_NODE2DATA(node, tree->avl_offset)); ASSERT(-1 <= diff && diff <= 1); ASSERT(diff != 0); ASSERT(diff > 0 ? child == 1 : child == 0); #endif node = node->avl_child[child]; } #ifdef DEBUG diff = tree->avl_compar(new_data, AVL_NODE2DATA(node, tree->avl_offset)); ASSERT(-1 <= diff && diff <= 1); ASSERT(diff != 0); ASSERT(diff > 0 ? child == 1 : child == 0); #endif } ASSERT(node->avl_child[child] == NULL); avl_insert(tree, new_data, AVL_MKINDEX(node, child)); } /* * Add a new node to an AVL tree. */ void avl_add(avl_tree_t *tree, void *new_node) { avl_index_t where; /* * This is unfortunate. We want to call panic() here, even for * non-DEBUG kernels. In userland, however, we can't depend on anything * in libc or else the rtld build process gets confused. * Thankfully, rtld provides us with its own assfail() so we can use * that here. We use assfail() directly to get a nice error message * in the core - much like what panic() does for crashdumps. */ if (avl_find(tree, new_node, &where) != NULL) #ifdef _KERNEL panic("avl_find() succeeded inside avl_add()"); #else (void) assfail("avl_find() succeeded inside avl_add()", __FILE__, __LINE__); #endif avl_insert(tree, new_node, where); } /* * Delete a node from the AVL tree. Deletion is similar to insertion, but * with 2 complications. * * First, we may be deleting an interior node. Consider the following subtree: * * d c c * / \ / \ / \ * b e b e b e * / \ / \ / * a c a a * * When we are deleting node (d), we find and bring up an adjacent valued leaf * node, say (c), to take the interior node's place. In the code this is * handled by temporarily swapping (d) and (c) in the tree and then using * common code to delete (d) from the leaf position. * * Secondly, an interior deletion from a deep tree may require more than one * rotation to fix the balance. This is handled by moving up the tree through * parents and applying rotations as needed. The return value from * avl_rotation() is used to detect when a subtree did not change overall * height due to a rotation. */ void avl_remove(avl_tree_t *tree, void *data) { avl_node_t *delete; avl_node_t *parent; avl_node_t *node; avl_node_t tmp; int old_balance; int new_balance; int left; int right; int which_child; size_t off = tree->avl_offset; ASSERT(tree); delete = AVL_DATA2NODE(data, off); /* * Deletion is easiest with a node that has at most 1 child. * We swap a node with 2 children with a sequentially valued * neighbor node. That node will have at most 1 child. Note this * has no effect on the ordering of the remaining nodes. * * As an optimization, we choose the greater neighbor if the tree * is right heavy, otherwise the left neighbor. This reduces the * number of rotations needed. */ if (delete->avl_child[0] != NULL && delete->avl_child[1] != NULL) { /* * choose node to swap from whichever side is taller */ old_balance = AVL_XBALANCE(delete); left = (old_balance > 0); right = 1 - left; /* * get to the previous value'd node * (down 1 left, as far as possible right) */ for (node = delete->avl_child[left]; node->avl_child[right] != NULL; node = node->avl_child[right]) ; /* * create a temp placeholder for 'node' * move 'node' to delete's spot in the tree */ tmp = *node; *node = *delete; if (node->avl_child[left] == node) node->avl_child[left] = &tmp; parent = AVL_XPARENT(node); if (parent != NULL) parent->avl_child[AVL_XCHILD(node)] = node; else tree->avl_root = node; AVL_SETPARENT(node->avl_child[left], node); AVL_SETPARENT(node->avl_child[right], node); /* * Put tmp where node used to be (just temporary). * It always has a parent and at most 1 child. */ delete = &tmp; parent = AVL_XPARENT(delete); parent->avl_child[AVL_XCHILD(delete)] = delete; which_child = (delete->avl_child[1] != 0); if (delete->avl_child[which_child] != NULL) AVL_SETPARENT(delete->avl_child[which_child], delete); } /* * Here we know "delete" is at least partially a leaf node. It can * be easily removed from the tree. */ ASSERT(tree->avl_numnodes > 0); --tree->avl_numnodes; parent = AVL_XPARENT(delete); which_child = AVL_XCHILD(delete); if (delete->avl_child[0] != NULL) node = delete->avl_child[0]; else node = delete->avl_child[1]; /* * Connect parent directly to node (leaving out delete). */ if (node != NULL) { AVL_SETPARENT(node, parent); AVL_SETCHILD(node, which_child); } if (parent == NULL) { tree->avl_root = node; return; } parent->avl_child[which_child] = node; /* * Since the subtree is now shorter, begin adjusting parent balances * and performing any needed rotations. */ do { /* * Move up the tree and adjust the balance * * Capture the parent and which_child values for the next * iteration before any rotations occur. */ node = parent; old_balance = AVL_XBALANCE(node); new_balance = old_balance - (which_child ? 1 : -1); parent = AVL_XPARENT(node); which_child = AVL_XCHILD(node); /* * If a node was in perfect balance but isn't anymore then * we can stop, since the height didn't change above this point * due to a deletion. */ if (old_balance == 0) { AVL_SETBALANCE(node, new_balance); break; } /* * If the new balance is zero, we don't need to rotate * else * need a rotation to fix the balance. * If the rotation doesn't change the height * of the sub-tree we have finished adjusting. */ if (new_balance == 0) AVL_SETBALANCE(node, new_balance); else if (!avl_rotation(tree, node, new_balance)) break; } while (parent != NULL); } #define AVL_REINSERT(tree, obj) \ avl_remove((tree), (obj)); \ avl_add((tree), (obj)) boolean_t avl_update_lt(avl_tree_t *t, void *obj) { void *neighbor; ASSERT(((neighbor = AVL_NEXT(t, obj)) == NULL) || (t->avl_compar(obj, neighbor) <= 0)); neighbor = AVL_PREV(t, obj); if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) { AVL_REINSERT(t, obj); return (B_TRUE); } return (B_FALSE); } boolean_t avl_update_gt(avl_tree_t *t, void *obj) { void *neighbor; ASSERT(((neighbor = AVL_PREV(t, obj)) == NULL) || (t->avl_compar(obj, neighbor) >= 0)); neighbor = AVL_NEXT(t, obj); if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) { AVL_REINSERT(t, obj); return (B_TRUE); } return (B_FALSE); } boolean_t avl_update(avl_tree_t *t, void *obj) { void *neighbor; neighbor = AVL_PREV(t, obj); if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) { AVL_REINSERT(t, obj); return (B_TRUE); } neighbor = AVL_NEXT(t, obj); if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) { AVL_REINSERT(t, obj); return (B_TRUE); } return (B_FALSE); } void avl_swap(avl_tree_t *tree1, avl_tree_t *tree2) { avl_node_t *temp_node; ulong_t temp_numnodes; ASSERT3P(tree1->avl_compar, ==, tree2->avl_compar); ASSERT3U(tree1->avl_offset, ==, tree2->avl_offset); ASSERT3U(tree1->avl_size, ==, tree2->avl_size); temp_node = tree1->avl_root; temp_numnodes = tree1->avl_numnodes; tree1->avl_root = tree2->avl_root; tree1->avl_numnodes = tree2->avl_numnodes; tree2->avl_root = temp_node; tree2->avl_numnodes = temp_numnodes; } /* * initialize a new AVL tree */ void avl_create(avl_tree_t *tree, int (*compar) (const void *, const void *), size_t size, size_t offset) { ASSERT(tree); ASSERT(compar); ASSERT(size > 0); ASSERT(size >= offset + sizeof (avl_node_t)); #ifdef _LP64 ASSERT((offset & 0x7) == 0); #endif tree->avl_compar = compar; tree->avl_root = NULL; tree->avl_numnodes = 0; tree->avl_size = size; tree->avl_offset = offset; } /* * Delete a tree. */ /* ARGSUSED */ void avl_destroy(avl_tree_t *tree) { ASSERT(tree); ASSERT(tree->avl_numnodes == 0); ASSERT(tree->avl_root == NULL); } /* * Return the number of nodes in an AVL tree. */ ulong_t avl_numnodes(avl_tree_t *tree) { ASSERT(tree); return (tree->avl_numnodes); } boolean_t avl_is_empty(avl_tree_t *tree) { ASSERT(tree); return (tree->avl_numnodes == 0); } #define CHILDBIT (1L) /* * Post-order tree walk used to visit all tree nodes and destroy the tree * in post order. This is used for removing all the nodes from a tree without * paying any cost for rebalancing it. * * example: * * void *cookie = NULL; * my_data_t *node; * * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL) * free(node); * avl_destroy(tree); * * The cookie is really an avl_node_t to the current node's parent and * an indication of which child you looked at last. * * On input, a cookie value of CHILDBIT indicates the tree is done. */ void * avl_destroy_nodes(avl_tree_t *tree, void **cookie) { avl_node_t *node; avl_node_t *parent; int child; void *first; size_t off = tree->avl_offset; /* * Initial calls go to the first node or it's right descendant. */ if (*cookie == NULL) { first = avl_first(tree); /* * deal with an empty tree */ if (first == NULL) { *cookie = (void *)CHILDBIT; return (NULL); } node = AVL_DATA2NODE(first, off); parent = AVL_XPARENT(node); goto check_right_side; } /* * If there is no parent to return to we are done. */ parent = (avl_node_t *)((uintptr_t)(*cookie) & ~CHILDBIT); if (parent == NULL) { if (tree->avl_root != NULL) { ASSERT(tree->avl_numnodes == 1); tree->avl_root = NULL; tree->avl_numnodes = 0; } return (NULL); } /* * Remove the child pointer we just visited from the parent and tree. */ child = (uintptr_t)(*cookie) & CHILDBIT; parent->avl_child[child] = NULL; ASSERT(tree->avl_numnodes > 1); --tree->avl_numnodes; /* * If we just did a right child or there isn't one, go up to parent. */ if (child == 1 || parent->avl_child[1] == NULL) { node = parent; parent = AVL_XPARENT(parent); goto done; } /* * Do parent's right child, then leftmost descendent. */ node = parent->avl_child[1]; while (node->avl_child[0] != NULL) { parent = node; node = node->avl_child[0]; } /* * If here, we moved to a left child. It may have one * child on the right (when balance == +1). */ check_right_side: if (node->avl_child[1] != NULL) { ASSERT(AVL_XBALANCE(node) == 1); parent = node; node = node->avl_child[1]; ASSERT(node->avl_child[0] == NULL && node->avl_child[1] == NULL); } else { ASSERT(AVL_XBALANCE(node) <= 0); } done: if (parent == NULL) { *cookie = (void *)CHILDBIT; ASSERT(node == tree->avl_root); } else { *cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node)); } return (AVL_NODE2DATA(node, off)); }
