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