17c478bd9Sstevel@tonic-gate /* 27c478bd9Sstevel@tonic-gate * CDDL HEADER START 37c478bd9Sstevel@tonic-gate * 47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the 5208e825dSsommerfe * Common Development and Distribution License (the "License"). 6208e825dSsommerfe * You may not use this file except in compliance with the License. 77c478bd9Sstevel@tonic-gate * 87c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 97c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 107c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions 117c478bd9Sstevel@tonic-gate * and limitations under the License. 127c478bd9Sstevel@tonic-gate * 137c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 147c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 157c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 167c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 177c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 187c478bd9Sstevel@tonic-gate * 197c478bd9Sstevel@tonic-gate * CDDL HEADER END 207c478bd9Sstevel@tonic-gate */ 217c478bd9Sstevel@tonic-gate /* 22b24ab676SJeff Bonwick * Copyright 2009 Sun Microsystems, Inc. All rights reserved. 237c478bd9Sstevel@tonic-gate * Use is subject to license terms. 247c478bd9Sstevel@tonic-gate */ 257c478bd9Sstevel@tonic-gate 267c478bd9Sstevel@tonic-gate /* 277c478bd9Sstevel@tonic-gate * AVL - generic AVL tree implementation for kernel use 287c478bd9Sstevel@tonic-gate * 297c478bd9Sstevel@tonic-gate * A complete description of AVL trees can be found in many CS textbooks. 307c478bd9Sstevel@tonic-gate * 317c478bd9Sstevel@tonic-gate * Here is a very brief overview. An AVL tree is a binary search tree that is 327c478bd9Sstevel@tonic-gate * almost perfectly balanced. By "almost" perfectly balanced, we mean that at 337c478bd9Sstevel@tonic-gate * any given node, the left and right subtrees are allowed to differ in height 347c478bd9Sstevel@tonic-gate * by at most 1 level. 357c478bd9Sstevel@tonic-gate * 367c478bd9Sstevel@tonic-gate * This relaxation from a perfectly balanced binary tree allows doing 377c478bd9Sstevel@tonic-gate * insertion and deletion relatively efficiently. Searching the tree is 387c478bd9Sstevel@tonic-gate * still a fast operation, roughly O(log(N)). 397c478bd9Sstevel@tonic-gate * 40*6907ca4bSJosef 'Jeff' Sipek * The key to insertion and deletion is a set of tree manipulations called 417c478bd9Sstevel@tonic-gate * rotations, which bring unbalanced subtrees back into the semi-balanced state. 427c478bd9Sstevel@tonic-gate * 437c478bd9Sstevel@tonic-gate * This implementation of AVL trees has the following peculiarities: 447c478bd9Sstevel@tonic-gate * 457c478bd9Sstevel@tonic-gate * - The AVL specific data structures are physically embedded as fields 467c478bd9Sstevel@tonic-gate * in the "using" data structures. To maintain generality the code 477c478bd9Sstevel@tonic-gate * must constantly translate between "avl_node_t *" and containing 48*6907ca4bSJosef 'Jeff' Sipek * data structure "void *"s by adding/subtracting the avl_offset. 497c478bd9Sstevel@tonic-gate * 507c478bd9Sstevel@tonic-gate * - Since the AVL data is always embedded in other structures, there is 517c478bd9Sstevel@tonic-gate * no locking or memory allocation in the AVL routines. This must be 527c478bd9Sstevel@tonic-gate * provided for by the enclosing data structure's semantics. Typically, 53fa9e4066Sahrens * avl_insert()/_add()/_remove()/avl_insert_here() require some kind of 547c478bd9Sstevel@tonic-gate * exclusive write lock. Other operations require a read lock. 557c478bd9Sstevel@tonic-gate * 567c478bd9Sstevel@tonic-gate * - The implementation uses iteration instead of explicit recursion, 577c478bd9Sstevel@tonic-gate * since it is intended to run on limited size kernel stacks. Since 587c478bd9Sstevel@tonic-gate * there is no recursion stack present to move "up" in the tree, 597c478bd9Sstevel@tonic-gate * there is an explicit "parent" link in the avl_node_t. 607c478bd9Sstevel@tonic-gate * 617c478bd9Sstevel@tonic-gate * - The left/right children pointers of a node are in an array. 627c478bd9Sstevel@tonic-gate * In the code, variables (instead of constants) are used to represent 637c478bd9Sstevel@tonic-gate * left and right indices. The implementation is written as if it only 647c478bd9Sstevel@tonic-gate * dealt with left handed manipulations. By changing the value assigned 657c478bd9Sstevel@tonic-gate * to "left", the code also works for right handed trees. The 667c478bd9Sstevel@tonic-gate * following variables/terms are frequently used: 677c478bd9Sstevel@tonic-gate * 687c478bd9Sstevel@tonic-gate * int left; // 0 when dealing with left children, 697c478bd9Sstevel@tonic-gate * // 1 for dealing with right children 707c478bd9Sstevel@tonic-gate * 717c478bd9Sstevel@tonic-gate * int left_heavy; // -1 when left subtree is taller at some node, 727c478bd9Sstevel@tonic-gate * // +1 when right subtree is taller 737c478bd9Sstevel@tonic-gate * 747c478bd9Sstevel@tonic-gate * int right; // will be the opposite of left (0 or 1) 757c478bd9Sstevel@tonic-gate * int right_heavy;// will be the opposite of left_heavy (-1 or 1) 767c478bd9Sstevel@tonic-gate * 777c478bd9Sstevel@tonic-gate * int direction; // 0 for "<" (ie. left child); 1 for ">" (right) 787c478bd9Sstevel@tonic-gate * 797c478bd9Sstevel@tonic-gate * Though it is a little more confusing to read the code, the approach 807c478bd9Sstevel@tonic-gate * allows using half as much code (and hence cache footprint) for tree 817c478bd9Sstevel@tonic-gate * manipulations and eliminates many conditional branches. 827c478bd9Sstevel@tonic-gate * 837c478bd9Sstevel@tonic-gate * - The avl_index_t is an opaque "cookie" used to find nodes at or 847c478bd9Sstevel@tonic-gate * adjacent to where a new value would be inserted in the tree. The value 857c478bd9Sstevel@tonic-gate * is a modified "avl_node_t *". The bottom bit (normally 0 for a 867c478bd9Sstevel@tonic-gate * pointer) is set to indicate if that the new node has a value greater 877c478bd9Sstevel@tonic-gate * than the value of the indicated "avl_node_t *". 887c478bd9Sstevel@tonic-gate */ 897c478bd9Sstevel@tonic-gate 907c478bd9Sstevel@tonic-gate #include <sys/types.h> 917c478bd9Sstevel@tonic-gate #include <sys/param.h> 927c478bd9Sstevel@tonic-gate #include <sys/debug.h> 937c478bd9Sstevel@tonic-gate #include <sys/avl.h> 94fa9e4066Sahrens #include <sys/cmn_err.h> 957c478bd9Sstevel@tonic-gate 967c478bd9Sstevel@tonic-gate /* 97*6907ca4bSJosef 'Jeff' Sipek * Small arrays to translate between balance (or diff) values and child indices. 987c478bd9Sstevel@tonic-gate * 997c478bd9Sstevel@tonic-gate * Code that deals with binary tree data structures will randomly use 1007c478bd9Sstevel@tonic-gate * left and right children when examining a tree. C "if()" statements 1017c478bd9Sstevel@tonic-gate * which evaluate randomly suffer from very poor hardware branch prediction. 1027c478bd9Sstevel@tonic-gate * In this code we avoid some of the branch mispredictions by using the 1037c478bd9Sstevel@tonic-gate * following translation arrays. They replace random branches with an 1047c478bd9Sstevel@tonic-gate * additional memory reference. Since the translation arrays are both very 1057c478bd9Sstevel@tonic-gate * small the data should remain efficiently in cache. 1067c478bd9Sstevel@tonic-gate */ 1077c478bd9Sstevel@tonic-gate static const int avl_child2balance[2] = {-1, 1}; 1087c478bd9Sstevel@tonic-gate static const int avl_balance2child[] = {0, 0, 1}; 1097c478bd9Sstevel@tonic-gate 1107c478bd9Sstevel@tonic-gate 1117c478bd9Sstevel@tonic-gate /* 1127c478bd9Sstevel@tonic-gate * Walk from one node to the previous valued node (ie. an infix walk 1137c478bd9Sstevel@tonic-gate * towards the left). At any given node we do one of 2 things: 1147c478bd9Sstevel@tonic-gate * 1157c478bd9Sstevel@tonic-gate * - If there is a left child, go to it, then to it's rightmost descendant. 1167c478bd9Sstevel@tonic-gate * 117*6907ca4bSJosef 'Jeff' Sipek * - otherwise we return through parent nodes until we've come from a right 118*6907ca4bSJosef 'Jeff' Sipek * child. 1197c478bd9Sstevel@tonic-gate * 1207c478bd9Sstevel@tonic-gate * Return Value: 1217c478bd9Sstevel@tonic-gate * NULL - if at the end of the nodes 1227c478bd9Sstevel@tonic-gate * otherwise next node 1237c478bd9Sstevel@tonic-gate */ 1247c478bd9Sstevel@tonic-gate void * 1257c478bd9Sstevel@tonic-gate avl_walk(avl_tree_t *tree, void *oldnode, int left) 1267c478bd9Sstevel@tonic-gate { 1277c478bd9Sstevel@tonic-gate size_t off = tree->avl_offset; 1287c478bd9Sstevel@tonic-gate avl_node_t *node = AVL_DATA2NODE(oldnode, off); 1297c478bd9Sstevel@tonic-gate int right = 1 - left; 1307c478bd9Sstevel@tonic-gate int was_child; 1317c478bd9Sstevel@tonic-gate 1327c478bd9Sstevel@tonic-gate 1337c478bd9Sstevel@tonic-gate /* 1347c478bd9Sstevel@tonic-gate * nowhere to walk to if tree is empty 1357c478bd9Sstevel@tonic-gate */ 1367c478bd9Sstevel@tonic-gate if (node == NULL) 1377c478bd9Sstevel@tonic-gate return (NULL); 1387c478bd9Sstevel@tonic-gate 1397c478bd9Sstevel@tonic-gate /* 1407c478bd9Sstevel@tonic-gate * Visit the previous valued node. There are two possibilities: 1417c478bd9Sstevel@tonic-gate * 1427c478bd9Sstevel@tonic-gate * If this node has a left child, go down one left, then all 1437c478bd9Sstevel@tonic-gate * the way right. 1447c478bd9Sstevel@tonic-gate */ 1457c478bd9Sstevel@tonic-gate if (node->avl_child[left] != NULL) { 1467c478bd9Sstevel@tonic-gate for (node = node->avl_child[left]; 1477c478bd9Sstevel@tonic-gate node->avl_child[right] != NULL; 1487c478bd9Sstevel@tonic-gate node = node->avl_child[right]) 1497c478bd9Sstevel@tonic-gate ; 1507c478bd9Sstevel@tonic-gate /* 1517c478bd9Sstevel@tonic-gate * Otherwise, return thru left children as far as we can. 1527c478bd9Sstevel@tonic-gate */ 1537c478bd9Sstevel@tonic-gate } else { 1547c478bd9Sstevel@tonic-gate for (;;) { 1557c478bd9Sstevel@tonic-gate was_child = AVL_XCHILD(node); 1567c478bd9Sstevel@tonic-gate node = AVL_XPARENT(node); 1577c478bd9Sstevel@tonic-gate if (node == NULL) 1587c478bd9Sstevel@tonic-gate return (NULL); 1597c478bd9Sstevel@tonic-gate if (was_child == right) 1607c478bd9Sstevel@tonic-gate break; 1617c478bd9Sstevel@tonic-gate } 1627c478bd9Sstevel@tonic-gate } 1637c478bd9Sstevel@tonic-gate 1647c478bd9Sstevel@tonic-gate return (AVL_NODE2DATA(node, off)); 1657c478bd9Sstevel@tonic-gate } 1667c478bd9Sstevel@tonic-gate 1677c478bd9Sstevel@tonic-gate /* 1687c478bd9Sstevel@tonic-gate * Return the lowest valued node in a tree or NULL. 1697c478bd9Sstevel@tonic-gate * (leftmost child from root of tree) 1707c478bd9Sstevel@tonic-gate */ 1717c478bd9Sstevel@tonic-gate void * 1727c478bd9Sstevel@tonic-gate avl_first(avl_tree_t *tree) 1737c478bd9Sstevel@tonic-gate { 1747c478bd9Sstevel@tonic-gate avl_node_t *node; 1757c478bd9Sstevel@tonic-gate avl_node_t *prev = NULL; 1767c478bd9Sstevel@tonic-gate size_t off = tree->avl_offset; 1777c478bd9Sstevel@tonic-gate 1787c478bd9Sstevel@tonic-gate for (node = tree->avl_root; node != NULL; node = node->avl_child[0]) 1797c478bd9Sstevel@tonic-gate prev = node; 1807c478bd9Sstevel@tonic-gate 1817c478bd9Sstevel@tonic-gate if (prev != NULL) 1827c478bd9Sstevel@tonic-gate return (AVL_NODE2DATA(prev, off)); 1837c478bd9Sstevel@tonic-gate return (NULL); 1847c478bd9Sstevel@tonic-gate } 1857c478bd9Sstevel@tonic-gate 1867c478bd9Sstevel@tonic-gate /* 1877c478bd9Sstevel@tonic-gate * Return the highest valued node in a tree or NULL. 1887c478bd9Sstevel@tonic-gate * (rightmost child from root of tree) 1897c478bd9Sstevel@tonic-gate */ 1907c478bd9Sstevel@tonic-gate void * 1917c478bd9Sstevel@tonic-gate avl_last(avl_tree_t *tree) 1927c478bd9Sstevel@tonic-gate { 1937c478bd9Sstevel@tonic-gate avl_node_t *node; 1947c478bd9Sstevel@tonic-gate avl_node_t *prev = NULL; 1957c478bd9Sstevel@tonic-gate size_t off = tree->avl_offset; 1967c478bd9Sstevel@tonic-gate 1977c478bd9Sstevel@tonic-gate for (node = tree->avl_root; node != NULL; node = node->avl_child[1]) 1987c478bd9Sstevel@tonic-gate prev = node; 1997c478bd9Sstevel@tonic-gate 2007c478bd9Sstevel@tonic-gate if (prev != NULL) 2017c478bd9Sstevel@tonic-gate return (AVL_NODE2DATA(prev, off)); 2027c478bd9Sstevel@tonic-gate return (NULL); 2037c478bd9Sstevel@tonic-gate } 2047c478bd9Sstevel@tonic-gate 2057c478bd9Sstevel@tonic-gate /* 2067c478bd9Sstevel@tonic-gate * Access the node immediately before or after an insertion point. 2077c478bd9Sstevel@tonic-gate * 2087c478bd9Sstevel@tonic-gate * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child 2097c478bd9Sstevel@tonic-gate * 2107c478bd9Sstevel@tonic-gate * Return value: 2117c478bd9Sstevel@tonic-gate * NULL: no node in the given direction 2127c478bd9Sstevel@tonic-gate * "void *" of the found tree node 2137c478bd9Sstevel@tonic-gate */ 2147c478bd9Sstevel@tonic-gate void * 2157c478bd9Sstevel@tonic-gate avl_nearest(avl_tree_t *tree, avl_index_t where, int direction) 2167c478bd9Sstevel@tonic-gate { 2177c478bd9Sstevel@tonic-gate int child = AVL_INDEX2CHILD(where); 2187c478bd9Sstevel@tonic-gate avl_node_t *node = AVL_INDEX2NODE(where); 2197c478bd9Sstevel@tonic-gate void *data; 2207c478bd9Sstevel@tonic-gate size_t off = tree->avl_offset; 2217c478bd9Sstevel@tonic-gate 2227c478bd9Sstevel@tonic-gate if (node == NULL) { 2237c478bd9Sstevel@tonic-gate ASSERT(tree->avl_root == NULL); 2247c478bd9Sstevel@tonic-gate return (NULL); 2257c478bd9Sstevel@tonic-gate } 2267c478bd9Sstevel@tonic-gate data = AVL_NODE2DATA(node, off); 2277c478bd9Sstevel@tonic-gate if (child != direction) 2287c478bd9Sstevel@tonic-gate return (data); 2297c478bd9Sstevel@tonic-gate 2307c478bd9Sstevel@tonic-gate return (avl_walk(tree, data, direction)); 2317c478bd9Sstevel@tonic-gate } 2327c478bd9Sstevel@tonic-gate 2337c478bd9Sstevel@tonic-gate 2347c478bd9Sstevel@tonic-gate /* 2357c478bd9Sstevel@tonic-gate * Search for the node which contains "value". The algorithm is a 2367c478bd9Sstevel@tonic-gate * simple binary tree search. 2377c478bd9Sstevel@tonic-gate * 2387c478bd9Sstevel@tonic-gate * return value: 2397c478bd9Sstevel@tonic-gate * NULL: the value is not in the AVL tree 2407c478bd9Sstevel@tonic-gate * *where (if not NULL) is set to indicate the insertion point 2417c478bd9Sstevel@tonic-gate * "void *" of the found tree node 2427c478bd9Sstevel@tonic-gate */ 2437c478bd9Sstevel@tonic-gate void * 244b24ab676SJeff Bonwick avl_find(avl_tree_t *tree, const void *value, avl_index_t *where) 2457c478bd9Sstevel@tonic-gate { 2467c478bd9Sstevel@tonic-gate avl_node_t *node; 2477c478bd9Sstevel@tonic-gate avl_node_t *prev = NULL; 2487c478bd9Sstevel@tonic-gate int child = 0; 2497c478bd9Sstevel@tonic-gate int diff; 2507c478bd9Sstevel@tonic-gate size_t off = tree->avl_offset; 2517c478bd9Sstevel@tonic-gate 2527c478bd9Sstevel@tonic-gate for (node = tree->avl_root; node != NULL; 2537c478bd9Sstevel@tonic-gate node = node->avl_child[child]) { 2547c478bd9Sstevel@tonic-gate 2557c478bd9Sstevel@tonic-gate prev = node; 2567c478bd9Sstevel@tonic-gate 2577c478bd9Sstevel@tonic-gate diff = tree->avl_compar(value, AVL_NODE2DATA(node, off)); 2587c478bd9Sstevel@tonic-gate ASSERT(-1 <= diff && diff <= 1); 2597c478bd9Sstevel@tonic-gate if (diff == 0) { 2607c478bd9Sstevel@tonic-gate #ifdef DEBUG 2617c478bd9Sstevel@tonic-gate if (where != NULL) 2625ad82045Snd *where = 0; 2637c478bd9Sstevel@tonic-gate #endif 2647c478bd9Sstevel@tonic-gate return (AVL_NODE2DATA(node, off)); 2657c478bd9Sstevel@tonic-gate } 2667c478bd9Sstevel@tonic-gate child = avl_balance2child[1 + diff]; 2677c478bd9Sstevel@tonic-gate 2687c478bd9Sstevel@tonic-gate } 2697c478bd9Sstevel@tonic-gate 2707c478bd9Sstevel@tonic-gate if (where != NULL) 2717c478bd9Sstevel@tonic-gate *where = AVL_MKINDEX(prev, child); 2727c478bd9Sstevel@tonic-gate 2737c478bd9Sstevel@tonic-gate return (NULL); 2747c478bd9Sstevel@tonic-gate } 2757c478bd9Sstevel@tonic-gate 2767c478bd9Sstevel@tonic-gate 2777c478bd9Sstevel@tonic-gate /* 2787c478bd9Sstevel@tonic-gate * Perform a rotation to restore balance at the subtree given by depth. 2797c478bd9Sstevel@tonic-gate * 2807c478bd9Sstevel@tonic-gate * This routine is used by both insertion and deletion. The return value 2817c478bd9Sstevel@tonic-gate * indicates: 2827c478bd9Sstevel@tonic-gate * 0 : subtree did not change height 2837c478bd9Sstevel@tonic-gate * !0 : subtree was reduced in height 2847c478bd9Sstevel@tonic-gate * 2857c478bd9Sstevel@tonic-gate * The code is written as if handling left rotations, right rotations are 2867c478bd9Sstevel@tonic-gate * symmetric and handled by swapping values of variables right/left[_heavy] 2877c478bd9Sstevel@tonic-gate * 2887c478bd9Sstevel@tonic-gate * On input balance is the "new" balance at "node". This value is either 2897c478bd9Sstevel@tonic-gate * -2 or +2. 2907c478bd9Sstevel@tonic-gate */ 2917c478bd9Sstevel@tonic-gate static int 2927c478bd9Sstevel@tonic-gate avl_rotation(avl_tree_t *tree, avl_node_t *node, int balance) 2937c478bd9Sstevel@tonic-gate { 2947c478bd9Sstevel@tonic-gate int left = !(balance < 0); /* when balance = -2, left will be 0 */ 2957c478bd9Sstevel@tonic-gate int right = 1 - left; 2967c478bd9Sstevel@tonic-gate int left_heavy = balance >> 1; 2977c478bd9Sstevel@tonic-gate int right_heavy = -left_heavy; 2987c478bd9Sstevel@tonic-gate avl_node_t *parent = AVL_XPARENT(node); 2997c478bd9Sstevel@tonic-gate avl_node_t *child = node->avl_child[left]; 3007c478bd9Sstevel@tonic-gate avl_node_t *cright; 3017c478bd9Sstevel@tonic-gate avl_node_t *gchild; 3027c478bd9Sstevel@tonic-gate avl_node_t *gright; 3037c478bd9Sstevel@tonic-gate avl_node_t *gleft; 3047c478bd9Sstevel@tonic-gate int which_child = AVL_XCHILD(node); 3057c478bd9Sstevel@tonic-gate int child_bal = AVL_XBALANCE(child); 3067c478bd9Sstevel@tonic-gate 3077c478bd9Sstevel@tonic-gate /* BEGIN CSTYLED */ 3087c478bd9Sstevel@tonic-gate /* 3097c478bd9Sstevel@tonic-gate * case 1 : node is overly left heavy, the left child is balanced or 3107c478bd9Sstevel@tonic-gate * also left heavy. This requires the following rotation. 3117c478bd9Sstevel@tonic-gate * 3127c478bd9Sstevel@tonic-gate * (node bal:-2) 3137c478bd9Sstevel@tonic-gate * / \ 3147c478bd9Sstevel@tonic-gate * / \ 3157c478bd9Sstevel@tonic-gate * (child bal:0 or -1) 3167c478bd9Sstevel@tonic-gate * / \ 3177c478bd9Sstevel@tonic-gate * / \ 3187c478bd9Sstevel@tonic-gate * cright 3197c478bd9Sstevel@tonic-gate * 3207c478bd9Sstevel@tonic-gate * becomes: 3217c478bd9Sstevel@tonic-gate * 3227c478bd9Sstevel@tonic-gate * (child bal:1 or 0) 3237c478bd9Sstevel@tonic-gate * / \ 3247c478bd9Sstevel@tonic-gate * / \ 3257c478bd9Sstevel@tonic-gate * (node bal:-1 or 0) 3267c478bd9Sstevel@tonic-gate * / \ 3277c478bd9Sstevel@tonic-gate * / \ 3287c478bd9Sstevel@tonic-gate * cright 3297c478bd9Sstevel@tonic-gate * 3307c478bd9Sstevel@tonic-gate * we detect this situation by noting that child's balance is not 3317c478bd9Sstevel@tonic-gate * right_heavy. 3327c478bd9Sstevel@tonic-gate */ 3337c478bd9Sstevel@tonic-gate /* END CSTYLED */ 3347c478bd9Sstevel@tonic-gate if (child_bal != right_heavy) { 3357c478bd9Sstevel@tonic-gate 3367c478bd9Sstevel@tonic-gate /* 3377c478bd9Sstevel@tonic-gate * compute new balance of nodes 3387c478bd9Sstevel@tonic-gate * 3397c478bd9Sstevel@tonic-gate * If child used to be left heavy (now balanced) we reduced 3407c478bd9Sstevel@tonic-gate * the height of this sub-tree -- used in "return...;" below 3417c478bd9Sstevel@tonic-gate */ 3427c478bd9Sstevel@tonic-gate child_bal += right_heavy; /* adjust towards right */ 3437c478bd9Sstevel@tonic-gate 3447c478bd9Sstevel@tonic-gate /* 3457c478bd9Sstevel@tonic-gate * move "cright" to be node's left child 3467c478bd9Sstevel@tonic-gate */ 3477c478bd9Sstevel@tonic-gate cright = child->avl_child[right]; 3487c478bd9Sstevel@tonic-gate node->avl_child[left] = cright; 3497c478bd9Sstevel@tonic-gate if (cright != NULL) { 3507c478bd9Sstevel@tonic-gate AVL_SETPARENT(cright, node); 3517c478bd9Sstevel@tonic-gate AVL_SETCHILD(cright, left); 3527c478bd9Sstevel@tonic-gate } 3537c478bd9Sstevel@tonic-gate 3547c478bd9Sstevel@tonic-gate /* 3557c478bd9Sstevel@tonic-gate * move node to be child's right child 3567c478bd9Sstevel@tonic-gate */ 3577c478bd9Sstevel@tonic-gate child->avl_child[right] = node; 3587c478bd9Sstevel@tonic-gate AVL_SETBALANCE(node, -child_bal); 3597c478bd9Sstevel@tonic-gate AVL_SETCHILD(node, right); 3607c478bd9Sstevel@tonic-gate AVL_SETPARENT(node, child); 3617c478bd9Sstevel@tonic-gate 3627c478bd9Sstevel@tonic-gate /* 3637c478bd9Sstevel@tonic-gate * update the pointer into this subtree 3647c478bd9Sstevel@tonic-gate */ 3657c478bd9Sstevel@tonic-gate AVL_SETBALANCE(child, child_bal); 3667c478bd9Sstevel@tonic-gate AVL_SETCHILD(child, which_child); 3677c478bd9Sstevel@tonic-gate AVL_SETPARENT(child, parent); 3687c478bd9Sstevel@tonic-gate if (parent != NULL) 3697c478bd9Sstevel@tonic-gate parent->avl_child[which_child] = child; 3707c478bd9Sstevel@tonic-gate else 3717c478bd9Sstevel@tonic-gate tree->avl_root = child; 3727c478bd9Sstevel@tonic-gate 3737c478bd9Sstevel@tonic-gate return (child_bal == 0); 3747c478bd9Sstevel@tonic-gate } 3757c478bd9Sstevel@tonic-gate 3767c478bd9Sstevel@tonic-gate /* BEGIN CSTYLED */ 3777c478bd9Sstevel@tonic-gate /* 3787c478bd9Sstevel@tonic-gate * case 2 : When node is left heavy, but child is right heavy we use 3797c478bd9Sstevel@tonic-gate * a different rotation. 3807c478bd9Sstevel@tonic-gate * 3817c478bd9Sstevel@tonic-gate * (node b:-2) 3827c478bd9Sstevel@tonic-gate * / \ 3837c478bd9Sstevel@tonic-gate * / \ 3847c478bd9Sstevel@tonic-gate * / \ 3857c478bd9Sstevel@tonic-gate * (child b:+1) 3867c478bd9Sstevel@tonic-gate * / \ 3877c478bd9Sstevel@tonic-gate * / \ 3887c478bd9Sstevel@tonic-gate * (gchild b: != 0) 3897c478bd9Sstevel@tonic-gate * / \ 3907c478bd9Sstevel@tonic-gate * / \ 3917c478bd9Sstevel@tonic-gate * gleft gright 3927c478bd9Sstevel@tonic-gate * 3937c478bd9Sstevel@tonic-gate * becomes: 3947c478bd9Sstevel@tonic-gate * 3957c478bd9Sstevel@tonic-gate * (gchild b:0) 3967c478bd9Sstevel@tonic-gate * / \ 3977c478bd9Sstevel@tonic-gate * / \ 3987c478bd9Sstevel@tonic-gate * / \ 3997c478bd9Sstevel@tonic-gate * (child b:?) (node b:?) 4007c478bd9Sstevel@tonic-gate * / \ / \ 4017c478bd9Sstevel@tonic-gate * / \ / \ 4027c478bd9Sstevel@tonic-gate * gleft gright 4037c478bd9Sstevel@tonic-gate * 4047c478bd9Sstevel@tonic-gate * computing the new balances is more complicated. As an example: 4057c478bd9Sstevel@tonic-gate * if gchild was right_heavy, then child is now left heavy 4067c478bd9Sstevel@tonic-gate * else it is balanced 4077c478bd9Sstevel@tonic-gate */ 4087c478bd9Sstevel@tonic-gate /* END CSTYLED */ 4097c478bd9Sstevel@tonic-gate gchild = child->avl_child[right]; 4107c478bd9Sstevel@tonic-gate gleft = gchild->avl_child[left]; 4117c478bd9Sstevel@tonic-gate gright = gchild->avl_child[right]; 4127c478bd9Sstevel@tonic-gate 4137c478bd9Sstevel@tonic-gate /* 4147c478bd9Sstevel@tonic-gate * move gright to left child of node and 4157c478bd9Sstevel@tonic-gate * 4167c478bd9Sstevel@tonic-gate * move gleft to right child of node 4177c478bd9Sstevel@tonic-gate */ 4187c478bd9Sstevel@tonic-gate node->avl_child[left] = gright; 4197c478bd9Sstevel@tonic-gate if (gright != NULL) { 4207c478bd9Sstevel@tonic-gate AVL_SETPARENT(gright, node); 4217c478bd9Sstevel@tonic-gate AVL_SETCHILD(gright, left); 4227c478bd9Sstevel@tonic-gate } 4237c478bd9Sstevel@tonic-gate 4247c478bd9Sstevel@tonic-gate child->avl_child[right] = gleft; 4257c478bd9Sstevel@tonic-gate if (gleft != NULL) { 4267c478bd9Sstevel@tonic-gate AVL_SETPARENT(gleft, child); 4277c478bd9Sstevel@tonic-gate AVL_SETCHILD(gleft, right); 4287c478bd9Sstevel@tonic-gate } 4297c478bd9Sstevel@tonic-gate 4307c478bd9Sstevel@tonic-gate /* 4317c478bd9Sstevel@tonic-gate * move child to left child of gchild and 4327c478bd9Sstevel@tonic-gate * 4337c478bd9Sstevel@tonic-gate * move node to right child of gchild and 4347c478bd9Sstevel@tonic-gate * 4357c478bd9Sstevel@tonic-gate * fixup parent of all this to point to gchild 4367c478bd9Sstevel@tonic-gate */ 4377c478bd9Sstevel@tonic-gate balance = AVL_XBALANCE(gchild); 4387c478bd9Sstevel@tonic-gate gchild->avl_child[left] = child; 4397c478bd9Sstevel@tonic-gate AVL_SETBALANCE(child, (balance == right_heavy ? left_heavy : 0)); 4407c478bd9Sstevel@tonic-gate AVL_SETPARENT(child, gchild); 4417c478bd9Sstevel@tonic-gate AVL_SETCHILD(child, left); 4427c478bd9Sstevel@tonic-gate 4437c478bd9Sstevel@tonic-gate gchild->avl_child[right] = node; 4447c478bd9Sstevel@tonic-gate AVL_SETBALANCE(node, (balance == left_heavy ? right_heavy : 0)); 4457c478bd9Sstevel@tonic-gate AVL_SETPARENT(node, gchild); 4467c478bd9Sstevel@tonic-gate AVL_SETCHILD(node, right); 4477c478bd9Sstevel@tonic-gate 4487c478bd9Sstevel@tonic-gate AVL_SETBALANCE(gchild, 0); 4497c478bd9Sstevel@tonic-gate AVL_SETPARENT(gchild, parent); 4507c478bd9Sstevel@tonic-gate AVL_SETCHILD(gchild, which_child); 4517c478bd9Sstevel@tonic-gate if (parent != NULL) 4527c478bd9Sstevel@tonic-gate parent->avl_child[which_child] = gchild; 4537c478bd9Sstevel@tonic-gate else 4547c478bd9Sstevel@tonic-gate tree->avl_root = gchild; 4557c478bd9Sstevel@tonic-gate 4567c478bd9Sstevel@tonic-gate return (1); /* the new tree is always shorter */ 4577c478bd9Sstevel@tonic-gate } 4587c478bd9Sstevel@tonic-gate 4597c478bd9Sstevel@tonic-gate 4607c478bd9Sstevel@tonic-gate /* 4617c478bd9Sstevel@tonic-gate * Insert a new node into an AVL tree at the specified (from avl_find()) place. 4627c478bd9Sstevel@tonic-gate * 4637c478bd9Sstevel@tonic-gate * Newly inserted nodes are always leaf nodes in the tree, since avl_find() 4647c478bd9Sstevel@tonic-gate * searches out to the leaf positions. The avl_index_t indicates the node 4657c478bd9Sstevel@tonic-gate * which will be the parent of the new node. 4667c478bd9Sstevel@tonic-gate * 4677c478bd9Sstevel@tonic-gate * After the node is inserted, a single rotation further up the tree may 4687c478bd9Sstevel@tonic-gate * be necessary to maintain an acceptable AVL balance. 4697c478bd9Sstevel@tonic-gate */ 4707c478bd9Sstevel@tonic-gate void 4717c478bd9Sstevel@tonic-gate avl_insert(avl_tree_t *tree, void *new_data, avl_index_t where) 4727c478bd9Sstevel@tonic-gate { 4737c478bd9Sstevel@tonic-gate avl_node_t *node; 4747c478bd9Sstevel@tonic-gate avl_node_t *parent = AVL_INDEX2NODE(where); 4757c478bd9Sstevel@tonic-gate int old_balance; 4767c478bd9Sstevel@tonic-gate int new_balance; 4777c478bd9Sstevel@tonic-gate int which_child = AVL_INDEX2CHILD(where); 4787c478bd9Sstevel@tonic-gate size_t off = tree->avl_offset; 4797c478bd9Sstevel@tonic-gate 4807c478bd9Sstevel@tonic-gate ASSERT(tree); 4817c478bd9Sstevel@tonic-gate #ifdef _LP64 4827c478bd9Sstevel@tonic-gate ASSERT(((uintptr_t)new_data & 0x7) == 0); 4837c478bd9Sstevel@tonic-gate #endif 4847c478bd9Sstevel@tonic-gate 4857c478bd9Sstevel@tonic-gate node = AVL_DATA2NODE(new_data, off); 4867c478bd9Sstevel@tonic-gate 4877c478bd9Sstevel@tonic-gate /* 4887c478bd9Sstevel@tonic-gate * First, add the node to the tree at the indicated position. 4897c478bd9Sstevel@tonic-gate */ 4907c478bd9Sstevel@tonic-gate ++tree->avl_numnodes; 4917c478bd9Sstevel@tonic-gate 4927c478bd9Sstevel@tonic-gate node->avl_child[0] = NULL; 4937c478bd9Sstevel@tonic-gate node->avl_child[1] = NULL; 4947c478bd9Sstevel@tonic-gate 4957c478bd9Sstevel@tonic-gate AVL_SETCHILD(node, which_child); 4967c478bd9Sstevel@tonic-gate AVL_SETBALANCE(node, 0); 4977c478bd9Sstevel@tonic-gate AVL_SETPARENT(node, parent); 4987c478bd9Sstevel@tonic-gate if (parent != NULL) { 4997c478bd9Sstevel@tonic-gate ASSERT(parent->avl_child[which_child] == NULL); 5007c478bd9Sstevel@tonic-gate parent->avl_child[which_child] = node; 5017c478bd9Sstevel@tonic-gate } else { 5027c478bd9Sstevel@tonic-gate ASSERT(tree->avl_root == NULL); 5037c478bd9Sstevel@tonic-gate tree->avl_root = node; 5047c478bd9Sstevel@tonic-gate } 5057c478bd9Sstevel@tonic-gate /* 5067c478bd9Sstevel@tonic-gate * Now, back up the tree modifying the balance of all nodes above the 5077c478bd9Sstevel@tonic-gate * insertion point. If we get to a highly unbalanced ancestor, we 5087c478bd9Sstevel@tonic-gate * need to do a rotation. If we back out of the tree we are done. 5097c478bd9Sstevel@tonic-gate * If we brought any subtree into perfect balance (0), we are also done. 5107c478bd9Sstevel@tonic-gate */ 5117c478bd9Sstevel@tonic-gate for (;;) { 5127c478bd9Sstevel@tonic-gate node = parent; 5137c478bd9Sstevel@tonic-gate if (node == NULL) 5147c478bd9Sstevel@tonic-gate return; 5157c478bd9Sstevel@tonic-gate 5167c478bd9Sstevel@tonic-gate /* 5177c478bd9Sstevel@tonic-gate * Compute the new balance 5187c478bd9Sstevel@tonic-gate */ 5197c478bd9Sstevel@tonic-gate old_balance = AVL_XBALANCE(node); 5207c478bd9Sstevel@tonic-gate new_balance = old_balance + avl_child2balance[which_child]; 5217c478bd9Sstevel@tonic-gate 5227c478bd9Sstevel@tonic-gate /* 5237c478bd9Sstevel@tonic-gate * If we introduced equal balance, then we are done immediately 5247c478bd9Sstevel@tonic-gate */ 5257c478bd9Sstevel@tonic-gate if (new_balance == 0) { 5267c478bd9Sstevel@tonic-gate AVL_SETBALANCE(node, 0); 5277c478bd9Sstevel@tonic-gate return; 5287c478bd9Sstevel@tonic-gate } 5297c478bd9Sstevel@tonic-gate 5307c478bd9Sstevel@tonic-gate /* 5317c478bd9Sstevel@tonic-gate * If both old and new are not zero we went 5327c478bd9Sstevel@tonic-gate * from -1 to -2 balance, do a rotation. 5337c478bd9Sstevel@tonic-gate */ 5347c478bd9Sstevel@tonic-gate if (old_balance != 0) 5357c478bd9Sstevel@tonic-gate break; 5367c478bd9Sstevel@tonic-gate 5377c478bd9Sstevel@tonic-gate AVL_SETBALANCE(node, new_balance); 5387c478bd9Sstevel@tonic-gate parent = AVL_XPARENT(node); 5397c478bd9Sstevel@tonic-gate which_child = AVL_XCHILD(node); 5407c478bd9Sstevel@tonic-gate } 5417c478bd9Sstevel@tonic-gate 5427c478bd9Sstevel@tonic-gate /* 5437c478bd9Sstevel@tonic-gate * perform a rotation to fix the tree and return 5447c478bd9Sstevel@tonic-gate */ 5457c478bd9Sstevel@tonic-gate (void) avl_rotation(tree, node, new_balance); 5467c478bd9Sstevel@tonic-gate } 5477c478bd9Sstevel@tonic-gate 5487c478bd9Sstevel@tonic-gate /* 5497c478bd9Sstevel@tonic-gate * Insert "new_data" in "tree" in the given "direction" either after or 5507c478bd9Sstevel@tonic-gate * before (AVL_AFTER, AVL_BEFORE) the data "here". 5517c478bd9Sstevel@tonic-gate * 5527c478bd9Sstevel@tonic-gate * Insertions can only be done at empty leaf points in the tree, therefore 5537c478bd9Sstevel@tonic-gate * if the given child of the node is already present we move to either 5547c478bd9Sstevel@tonic-gate * the AVL_PREV or AVL_NEXT and reverse the insertion direction. Since 5557c478bd9Sstevel@tonic-gate * every other node in the tree is a leaf, this always works. 5567c478bd9Sstevel@tonic-gate * 5577c478bd9Sstevel@tonic-gate * To help developers using this interface, we assert that the new node 5587c478bd9Sstevel@tonic-gate * is correctly ordered at every step of the way in DEBUG kernels. 5597c478bd9Sstevel@tonic-gate */ 5607c478bd9Sstevel@tonic-gate void 5617c478bd9Sstevel@tonic-gate avl_insert_here( 5627c478bd9Sstevel@tonic-gate avl_tree_t *tree, 5637c478bd9Sstevel@tonic-gate void *new_data, 5647c478bd9Sstevel@tonic-gate void *here, 5657c478bd9Sstevel@tonic-gate int direction) 5667c478bd9Sstevel@tonic-gate { 5677c478bd9Sstevel@tonic-gate avl_node_t *node; 5687c478bd9Sstevel@tonic-gate int child = direction; /* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */ 569208e825dSsommerfe #ifdef DEBUG 570208e825dSsommerfe int diff; 571208e825dSsommerfe #endif 5727c478bd9Sstevel@tonic-gate 5737c478bd9Sstevel@tonic-gate ASSERT(tree != NULL); 5747c478bd9Sstevel@tonic-gate ASSERT(new_data != NULL); 5757c478bd9Sstevel@tonic-gate ASSERT(here != NULL); 5767c478bd9Sstevel@tonic-gate ASSERT(direction == AVL_BEFORE || direction == AVL_AFTER); 5777c478bd9Sstevel@tonic-gate 5787c478bd9Sstevel@tonic-gate /* 5797c478bd9Sstevel@tonic-gate * If corresponding child of node is not NULL, go to the neighboring 5807c478bd9Sstevel@tonic-gate * node and reverse the insertion direction. 5817c478bd9Sstevel@tonic-gate */ 5827c478bd9Sstevel@tonic-gate node = AVL_DATA2NODE(here, tree->avl_offset); 583208e825dSsommerfe 584208e825dSsommerfe #ifdef DEBUG 585208e825dSsommerfe diff = tree->avl_compar(new_data, here); 586208e825dSsommerfe ASSERT(-1 <= diff && diff <= 1); 587208e825dSsommerfe ASSERT(diff != 0); 588208e825dSsommerfe ASSERT(diff > 0 ? child == 1 : child == 0); 589208e825dSsommerfe #endif 5907c478bd9Sstevel@tonic-gate 5917c478bd9Sstevel@tonic-gate if (node->avl_child[child] != NULL) { 5927c478bd9Sstevel@tonic-gate node = node->avl_child[child]; 5937c478bd9Sstevel@tonic-gate child = 1 - child; 5947c478bd9Sstevel@tonic-gate while (node->avl_child[child] != NULL) { 595208e825dSsommerfe #ifdef DEBUG 596208e825dSsommerfe diff = tree->avl_compar(new_data, 597208e825dSsommerfe AVL_NODE2DATA(node, tree->avl_offset)); 598208e825dSsommerfe ASSERT(-1 <= diff && diff <= 1); 599208e825dSsommerfe ASSERT(diff != 0); 600208e825dSsommerfe ASSERT(diff > 0 ? child == 1 : child == 0); 601208e825dSsommerfe #endif 6027c478bd9Sstevel@tonic-gate node = node->avl_child[child]; 6037c478bd9Sstevel@tonic-gate } 604208e825dSsommerfe #ifdef DEBUG 605208e825dSsommerfe diff = tree->avl_compar(new_data, 606208e825dSsommerfe AVL_NODE2DATA(node, tree->avl_offset)); 607208e825dSsommerfe ASSERT(-1 <= diff && diff <= 1); 608208e825dSsommerfe ASSERT(diff != 0); 609208e825dSsommerfe ASSERT(diff > 0 ? child == 1 : child == 0); 610208e825dSsommerfe #endif 6117c478bd9Sstevel@tonic-gate } 6127c478bd9Sstevel@tonic-gate ASSERT(node->avl_child[child] == NULL); 6137c478bd9Sstevel@tonic-gate 6147c478bd9Sstevel@tonic-gate avl_insert(tree, new_data, AVL_MKINDEX(node, child)); 6157c478bd9Sstevel@tonic-gate } 6167c478bd9Sstevel@tonic-gate 617fa9e4066Sahrens /* 618fa9e4066Sahrens * Add a new node to an AVL tree. 619fa9e4066Sahrens */ 620fa9e4066Sahrens void 621fa9e4066Sahrens avl_add(avl_tree_t *tree, void *new_node) 622fa9e4066Sahrens { 623fa9e4066Sahrens avl_index_t where; 624fa9e4066Sahrens 625fa9e4066Sahrens /* 626fa9e4066Sahrens * This is unfortunate. We want to call panic() here, even for 627fa9e4066Sahrens * non-DEBUG kernels. In userland, however, we can't depend on anything 628fa9e4066Sahrens * in libc or else the rtld build process gets confused. So, all we can 629fa9e4066Sahrens * do in userland is resort to a normal ASSERT(). 630fa9e4066Sahrens */ 631fa9e4066Sahrens if (avl_find(tree, new_node, &where) != NULL) 632fa9e4066Sahrens #ifdef _KERNEL 633fa9e4066Sahrens panic("avl_find() succeeded inside avl_add()"); 634fa9e4066Sahrens #else 635fa9e4066Sahrens ASSERT(0); 636fa9e4066Sahrens #endif 637fa9e4066Sahrens avl_insert(tree, new_node, where); 638fa9e4066Sahrens } 639fa9e4066Sahrens 6407c478bd9Sstevel@tonic-gate /* 6417c478bd9Sstevel@tonic-gate * Delete a node from the AVL tree. Deletion is similar to insertion, but 6427c478bd9Sstevel@tonic-gate * with 2 complications. 6437c478bd9Sstevel@tonic-gate * 6447c478bd9Sstevel@tonic-gate * First, we may be deleting an interior node. Consider the following subtree: 6457c478bd9Sstevel@tonic-gate * 6467c478bd9Sstevel@tonic-gate * d c c 6477c478bd9Sstevel@tonic-gate * / \ / \ / \ 6487c478bd9Sstevel@tonic-gate * b e b e b e 6497c478bd9Sstevel@tonic-gate * / \ / \ / 6507c478bd9Sstevel@tonic-gate * a c a a 6517c478bd9Sstevel@tonic-gate * 6527c478bd9Sstevel@tonic-gate * When we are deleting node (d), we find and bring up an adjacent valued leaf 6537c478bd9Sstevel@tonic-gate * node, say (c), to take the interior node's place. In the code this is 6547c478bd9Sstevel@tonic-gate * handled by temporarily swapping (d) and (c) in the tree and then using 6557c478bd9Sstevel@tonic-gate * common code to delete (d) from the leaf position. 6567c478bd9Sstevel@tonic-gate * 6577c478bd9Sstevel@tonic-gate * Secondly, an interior deletion from a deep tree may require more than one 6587c478bd9Sstevel@tonic-gate * rotation to fix the balance. This is handled by moving up the tree through 6597c478bd9Sstevel@tonic-gate * parents and applying rotations as needed. The return value from 6607c478bd9Sstevel@tonic-gate * avl_rotation() is used to detect when a subtree did not change overall 6617c478bd9Sstevel@tonic-gate * height due to a rotation. 6627c478bd9Sstevel@tonic-gate */ 6637c478bd9Sstevel@tonic-gate void 6647c478bd9Sstevel@tonic-gate avl_remove(avl_tree_t *tree, void *data) 6657c478bd9Sstevel@tonic-gate { 6667c478bd9Sstevel@tonic-gate avl_node_t *delete; 6677c478bd9Sstevel@tonic-gate avl_node_t *parent; 6687c478bd9Sstevel@tonic-gate avl_node_t *node; 6697c478bd9Sstevel@tonic-gate avl_node_t tmp; 6707c478bd9Sstevel@tonic-gate int old_balance; 6717c478bd9Sstevel@tonic-gate int new_balance; 6727c478bd9Sstevel@tonic-gate int left; 6737c478bd9Sstevel@tonic-gate int right; 6747c478bd9Sstevel@tonic-gate int which_child; 6757c478bd9Sstevel@tonic-gate size_t off = tree->avl_offset; 6767c478bd9Sstevel@tonic-gate 6777c478bd9Sstevel@tonic-gate ASSERT(tree); 6787c478bd9Sstevel@tonic-gate 6797c478bd9Sstevel@tonic-gate delete = AVL_DATA2NODE(data, off); 6807c478bd9Sstevel@tonic-gate 6817c478bd9Sstevel@tonic-gate /* 6827c478bd9Sstevel@tonic-gate * Deletion is easiest with a node that has at most 1 child. 6837c478bd9Sstevel@tonic-gate * We swap a node with 2 children with a sequentially valued 6847c478bd9Sstevel@tonic-gate * neighbor node. That node will have at most 1 child. Note this 6857c478bd9Sstevel@tonic-gate * has no effect on the ordering of the remaining nodes. 6867c478bd9Sstevel@tonic-gate * 6877c478bd9Sstevel@tonic-gate * As an optimization, we choose the greater neighbor if the tree 6887c478bd9Sstevel@tonic-gate * is right heavy, otherwise the left neighbor. This reduces the 6897c478bd9Sstevel@tonic-gate * number of rotations needed. 6907c478bd9Sstevel@tonic-gate */ 6917c478bd9Sstevel@tonic-gate if (delete->avl_child[0] != NULL && delete->avl_child[1] != NULL) { 6927c478bd9Sstevel@tonic-gate 6937c478bd9Sstevel@tonic-gate /* 6947c478bd9Sstevel@tonic-gate * choose node to swap from whichever side is taller 6957c478bd9Sstevel@tonic-gate */ 6967c478bd9Sstevel@tonic-gate old_balance = AVL_XBALANCE(delete); 6977c478bd9Sstevel@tonic-gate left = avl_balance2child[old_balance + 1]; 6987c478bd9Sstevel@tonic-gate right = 1 - left; 6997c478bd9Sstevel@tonic-gate 7007c478bd9Sstevel@tonic-gate /* 7017c478bd9Sstevel@tonic-gate * get to the previous value'd node 7027c478bd9Sstevel@tonic-gate * (down 1 left, as far as possible right) 7037c478bd9Sstevel@tonic-gate */ 7047c478bd9Sstevel@tonic-gate for (node = delete->avl_child[left]; 7057c478bd9Sstevel@tonic-gate node->avl_child[right] != NULL; 7067c478bd9Sstevel@tonic-gate node = node->avl_child[right]) 7077c478bd9Sstevel@tonic-gate ; 7087c478bd9Sstevel@tonic-gate 7097c478bd9Sstevel@tonic-gate /* 7107c478bd9Sstevel@tonic-gate * create a temp placeholder for 'node' 7117c478bd9Sstevel@tonic-gate * move 'node' to delete's spot in the tree 7127c478bd9Sstevel@tonic-gate */ 7137c478bd9Sstevel@tonic-gate tmp = *node; 7147c478bd9Sstevel@tonic-gate 7157c478bd9Sstevel@tonic-gate *node = *delete; 7167c478bd9Sstevel@tonic-gate if (node->avl_child[left] == node) 7177c478bd9Sstevel@tonic-gate node->avl_child[left] = &tmp; 7187c478bd9Sstevel@tonic-gate 7197c478bd9Sstevel@tonic-gate parent = AVL_XPARENT(node); 7207c478bd9Sstevel@tonic-gate if (parent != NULL) 7217c478bd9Sstevel@tonic-gate parent->avl_child[AVL_XCHILD(node)] = node; 7227c478bd9Sstevel@tonic-gate else 7237c478bd9Sstevel@tonic-gate tree->avl_root = node; 7247c478bd9Sstevel@tonic-gate AVL_SETPARENT(node->avl_child[left], node); 7257c478bd9Sstevel@tonic-gate AVL_SETPARENT(node->avl_child[right], node); 7267c478bd9Sstevel@tonic-gate 7277c478bd9Sstevel@tonic-gate /* 7287c478bd9Sstevel@tonic-gate * Put tmp where node used to be (just temporary). 7297c478bd9Sstevel@tonic-gate * It always has a parent and at most 1 child. 7307c478bd9Sstevel@tonic-gate */ 7317c478bd9Sstevel@tonic-gate delete = &tmp; 7327c478bd9Sstevel@tonic-gate parent = AVL_XPARENT(delete); 7337c478bd9Sstevel@tonic-gate parent->avl_child[AVL_XCHILD(delete)] = delete; 7347c478bd9Sstevel@tonic-gate which_child = (delete->avl_child[1] != 0); 7357c478bd9Sstevel@tonic-gate if (delete->avl_child[which_child] != NULL) 7367c478bd9Sstevel@tonic-gate AVL_SETPARENT(delete->avl_child[which_child], delete); 7377c478bd9Sstevel@tonic-gate } 7387c478bd9Sstevel@tonic-gate 7397c478bd9Sstevel@tonic-gate 7407c478bd9Sstevel@tonic-gate /* 7417c478bd9Sstevel@tonic-gate * Here we know "delete" is at least partially a leaf node. It can 7427c478bd9Sstevel@tonic-gate * be easily removed from the tree. 7437c478bd9Sstevel@tonic-gate */ 744208e825dSsommerfe ASSERT(tree->avl_numnodes > 0); 7457c478bd9Sstevel@tonic-gate --tree->avl_numnodes; 7467c478bd9Sstevel@tonic-gate parent = AVL_XPARENT(delete); 7477c478bd9Sstevel@tonic-gate which_child = AVL_XCHILD(delete); 7487c478bd9Sstevel@tonic-gate if (delete->avl_child[0] != NULL) 7497c478bd9Sstevel@tonic-gate node = delete->avl_child[0]; 7507c478bd9Sstevel@tonic-gate else 7517c478bd9Sstevel@tonic-gate node = delete->avl_child[1]; 7527c478bd9Sstevel@tonic-gate 7537c478bd9Sstevel@tonic-gate /* 7547c478bd9Sstevel@tonic-gate * Connect parent directly to node (leaving out delete). 7557c478bd9Sstevel@tonic-gate */ 7567c478bd9Sstevel@tonic-gate if (node != NULL) { 7577c478bd9Sstevel@tonic-gate AVL_SETPARENT(node, parent); 7587c478bd9Sstevel@tonic-gate AVL_SETCHILD(node, which_child); 7597c478bd9Sstevel@tonic-gate } 7607c478bd9Sstevel@tonic-gate if (parent == NULL) { 7617c478bd9Sstevel@tonic-gate tree->avl_root = node; 7627c478bd9Sstevel@tonic-gate return; 7637c478bd9Sstevel@tonic-gate } 7647c478bd9Sstevel@tonic-gate parent->avl_child[which_child] = node; 7657c478bd9Sstevel@tonic-gate 7667c478bd9Sstevel@tonic-gate 7677c478bd9Sstevel@tonic-gate /* 7687c478bd9Sstevel@tonic-gate * Since the subtree is now shorter, begin adjusting parent balances 7697c478bd9Sstevel@tonic-gate * and performing any needed rotations. 7707c478bd9Sstevel@tonic-gate */ 7717c478bd9Sstevel@tonic-gate do { 7727c478bd9Sstevel@tonic-gate 7737c478bd9Sstevel@tonic-gate /* 7747c478bd9Sstevel@tonic-gate * Move up the tree and adjust the balance 7757c478bd9Sstevel@tonic-gate * 7767c478bd9Sstevel@tonic-gate * Capture the parent and which_child values for the next 7777c478bd9Sstevel@tonic-gate * iteration before any rotations occur. 7787c478bd9Sstevel@tonic-gate */ 7797c478bd9Sstevel@tonic-gate node = parent; 7807c478bd9Sstevel@tonic-gate old_balance = AVL_XBALANCE(node); 7817c478bd9Sstevel@tonic-gate new_balance = old_balance - avl_child2balance[which_child]; 7827c478bd9Sstevel@tonic-gate parent = AVL_XPARENT(node); 7837c478bd9Sstevel@tonic-gate which_child = AVL_XCHILD(node); 7847c478bd9Sstevel@tonic-gate 7857c478bd9Sstevel@tonic-gate /* 7867c478bd9Sstevel@tonic-gate * If a node was in perfect balance but isn't anymore then 7877c478bd9Sstevel@tonic-gate * we can stop, since the height didn't change above this point 7887c478bd9Sstevel@tonic-gate * due to a deletion. 7897c478bd9Sstevel@tonic-gate */ 7907c478bd9Sstevel@tonic-gate if (old_balance == 0) { 7917c478bd9Sstevel@tonic-gate AVL_SETBALANCE(node, new_balance); 7927c478bd9Sstevel@tonic-gate break; 7937c478bd9Sstevel@tonic-gate } 7947c478bd9Sstevel@tonic-gate 7957c478bd9Sstevel@tonic-gate /* 7967c478bd9Sstevel@tonic-gate * If the new balance is zero, we don't need to rotate 7977c478bd9Sstevel@tonic-gate * else 7987c478bd9Sstevel@tonic-gate * need a rotation to fix the balance. 7997c478bd9Sstevel@tonic-gate * If the rotation doesn't change the height 8007c478bd9Sstevel@tonic-gate * of the sub-tree we have finished adjusting. 8017c478bd9Sstevel@tonic-gate */ 8027c478bd9Sstevel@tonic-gate if (new_balance == 0) 8037c478bd9Sstevel@tonic-gate AVL_SETBALANCE(node, new_balance); 8047c478bd9Sstevel@tonic-gate else if (!avl_rotation(tree, node, new_balance)) 8057c478bd9Sstevel@tonic-gate break; 8067c478bd9Sstevel@tonic-gate } while (parent != NULL); 8077c478bd9Sstevel@tonic-gate } 8087c478bd9Sstevel@tonic-gate 809b5fca8f8Stomee #define AVL_REINSERT(tree, obj) \ 810b5fca8f8Stomee avl_remove((tree), (obj)); \ 811b5fca8f8Stomee avl_add((tree), (obj)) 812b5fca8f8Stomee 813b5fca8f8Stomee boolean_t 814b5fca8f8Stomee avl_update_lt(avl_tree_t *t, void *obj) 815b5fca8f8Stomee { 816b5fca8f8Stomee void *neighbor; 817b5fca8f8Stomee 818b5fca8f8Stomee ASSERT(((neighbor = AVL_NEXT(t, obj)) == NULL) || 819b5fca8f8Stomee (t->avl_compar(obj, neighbor) <= 0)); 820b5fca8f8Stomee 821b5fca8f8Stomee neighbor = AVL_PREV(t, obj); 822b5fca8f8Stomee if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) { 823b5fca8f8Stomee AVL_REINSERT(t, obj); 824b5fca8f8Stomee return (B_TRUE); 825b5fca8f8Stomee } 826b5fca8f8Stomee 827b5fca8f8Stomee return (B_FALSE); 828b5fca8f8Stomee } 829b5fca8f8Stomee 830b5fca8f8Stomee boolean_t 831b5fca8f8Stomee avl_update_gt(avl_tree_t *t, void *obj) 832b5fca8f8Stomee { 833b5fca8f8Stomee void *neighbor; 834b5fca8f8Stomee 835b5fca8f8Stomee ASSERT(((neighbor = AVL_PREV(t, obj)) == NULL) || 836b5fca8f8Stomee (t->avl_compar(obj, neighbor) >= 0)); 837b5fca8f8Stomee 838b5fca8f8Stomee neighbor = AVL_NEXT(t, obj); 839b5fca8f8Stomee if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) { 840b5fca8f8Stomee AVL_REINSERT(t, obj); 841b5fca8f8Stomee return (B_TRUE); 842b5fca8f8Stomee } 843b5fca8f8Stomee 844b5fca8f8Stomee return (B_FALSE); 845b5fca8f8Stomee } 846b5fca8f8Stomee 847b5fca8f8Stomee boolean_t 848b5fca8f8Stomee avl_update(avl_tree_t *t, void *obj) 849b5fca8f8Stomee { 850b5fca8f8Stomee void *neighbor; 851b5fca8f8Stomee 852b5fca8f8Stomee neighbor = AVL_PREV(t, obj); 853b5fca8f8Stomee if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) { 854b5fca8f8Stomee AVL_REINSERT(t, obj); 855b5fca8f8Stomee return (B_TRUE); 856b5fca8f8Stomee } 857b5fca8f8Stomee 858b5fca8f8Stomee neighbor = AVL_NEXT(t, obj); 859b5fca8f8Stomee if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) { 860b5fca8f8Stomee AVL_REINSERT(t, obj); 861b5fca8f8Stomee return (B_TRUE); 862b5fca8f8Stomee } 863b5fca8f8Stomee 864b5fca8f8Stomee return (B_FALSE); 865b5fca8f8Stomee } 866b5fca8f8Stomee 8677c478bd9Sstevel@tonic-gate /* 8687c478bd9Sstevel@tonic-gate * initialize a new AVL tree 8697c478bd9Sstevel@tonic-gate */ 8707c478bd9Sstevel@tonic-gate void 8717c478bd9Sstevel@tonic-gate avl_create(avl_tree_t *tree, int (*compar) (const void *, const void *), 8727c478bd9Sstevel@tonic-gate size_t size, size_t offset) 8737c478bd9Sstevel@tonic-gate { 8747c478bd9Sstevel@tonic-gate ASSERT(tree); 8757c478bd9Sstevel@tonic-gate ASSERT(compar); 8767c478bd9Sstevel@tonic-gate ASSERT(size > 0); 8777c478bd9Sstevel@tonic-gate ASSERT(size >= offset + sizeof (avl_node_t)); 8787c478bd9Sstevel@tonic-gate #ifdef _LP64 8797c478bd9Sstevel@tonic-gate ASSERT((offset & 0x7) == 0); 8807c478bd9Sstevel@tonic-gate #endif 8817c478bd9Sstevel@tonic-gate 8827c478bd9Sstevel@tonic-gate tree->avl_compar = compar; 8837c478bd9Sstevel@tonic-gate tree->avl_root = NULL; 8847c478bd9Sstevel@tonic-gate tree->avl_numnodes = 0; 8857c478bd9Sstevel@tonic-gate tree->avl_size = size; 8867c478bd9Sstevel@tonic-gate tree->avl_offset = offset; 8877c478bd9Sstevel@tonic-gate } 8887c478bd9Sstevel@tonic-gate 8897c478bd9Sstevel@tonic-gate /* 8907c478bd9Sstevel@tonic-gate * Delete a tree. 8917c478bd9Sstevel@tonic-gate */ 8927c478bd9Sstevel@tonic-gate /* ARGSUSED */ 8937c478bd9Sstevel@tonic-gate void 8947c478bd9Sstevel@tonic-gate avl_destroy(avl_tree_t *tree) 8957c478bd9Sstevel@tonic-gate { 8967c478bd9Sstevel@tonic-gate ASSERT(tree); 8977c478bd9Sstevel@tonic-gate ASSERT(tree->avl_numnodes == 0); 8987c478bd9Sstevel@tonic-gate ASSERT(tree->avl_root == NULL); 8997c478bd9Sstevel@tonic-gate } 9007c478bd9Sstevel@tonic-gate 9017c478bd9Sstevel@tonic-gate 9027c478bd9Sstevel@tonic-gate /* 9037c478bd9Sstevel@tonic-gate * Return the number of nodes in an AVL tree. 9047c478bd9Sstevel@tonic-gate */ 9057c478bd9Sstevel@tonic-gate ulong_t 9067c478bd9Sstevel@tonic-gate avl_numnodes(avl_tree_t *tree) 9077c478bd9Sstevel@tonic-gate { 9087c478bd9Sstevel@tonic-gate ASSERT(tree); 9097c478bd9Sstevel@tonic-gate return (tree->avl_numnodes); 9107c478bd9Sstevel@tonic-gate } 9117c478bd9Sstevel@tonic-gate 912b5fca8f8Stomee boolean_t 913b5fca8f8Stomee avl_is_empty(avl_tree_t *tree) 914b5fca8f8Stomee { 915b5fca8f8Stomee ASSERT(tree); 916b5fca8f8Stomee return (tree->avl_numnodes == 0); 917b5fca8f8Stomee } 9187c478bd9Sstevel@tonic-gate 9197c478bd9Sstevel@tonic-gate #define CHILDBIT (1L) 9207c478bd9Sstevel@tonic-gate 9217c478bd9Sstevel@tonic-gate /* 9227c478bd9Sstevel@tonic-gate * Post-order tree walk used to visit all tree nodes and destroy the tree 923*6907ca4bSJosef 'Jeff' Sipek * in post order. This is used for destroying a tree without paying any cost 9247c478bd9Sstevel@tonic-gate * for rebalancing it. 9257c478bd9Sstevel@tonic-gate * 9267c478bd9Sstevel@tonic-gate * example: 9277c478bd9Sstevel@tonic-gate * 9287c478bd9Sstevel@tonic-gate * void *cookie = NULL; 9297c478bd9Sstevel@tonic-gate * my_data_t *node; 9307c478bd9Sstevel@tonic-gate * 9317c478bd9Sstevel@tonic-gate * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL) 9327c478bd9Sstevel@tonic-gate * free(node); 9337c478bd9Sstevel@tonic-gate * avl_destroy(tree); 9347c478bd9Sstevel@tonic-gate * 9357c478bd9Sstevel@tonic-gate * The cookie is really an avl_node_t to the current node's parent and 9367c478bd9Sstevel@tonic-gate * an indication of which child you looked at last. 9377c478bd9Sstevel@tonic-gate * 9387c478bd9Sstevel@tonic-gate * On input, a cookie value of CHILDBIT indicates the tree is done. 9397c478bd9Sstevel@tonic-gate */ 9407c478bd9Sstevel@tonic-gate void * 9417c478bd9Sstevel@tonic-gate avl_destroy_nodes(avl_tree_t *tree, void **cookie) 9427c478bd9Sstevel@tonic-gate { 9437c478bd9Sstevel@tonic-gate avl_node_t *node; 9447c478bd9Sstevel@tonic-gate avl_node_t *parent; 9457c478bd9Sstevel@tonic-gate int child; 9467c478bd9Sstevel@tonic-gate void *first; 9477c478bd9Sstevel@tonic-gate size_t off = tree->avl_offset; 9487c478bd9Sstevel@tonic-gate 9497c478bd9Sstevel@tonic-gate /* 9507c478bd9Sstevel@tonic-gate * Initial calls go to the first node or it's right descendant. 9517c478bd9Sstevel@tonic-gate */ 9527c478bd9Sstevel@tonic-gate if (*cookie == NULL) { 9537c478bd9Sstevel@tonic-gate first = avl_first(tree); 9547c478bd9Sstevel@tonic-gate 9557c478bd9Sstevel@tonic-gate /* 9567c478bd9Sstevel@tonic-gate * deal with an empty tree 9577c478bd9Sstevel@tonic-gate */ 9587c478bd9Sstevel@tonic-gate if (first == NULL) { 9597c478bd9Sstevel@tonic-gate *cookie = (void *)CHILDBIT; 9607c478bd9Sstevel@tonic-gate return (NULL); 9617c478bd9Sstevel@tonic-gate } 9627c478bd9Sstevel@tonic-gate 9637c478bd9Sstevel@tonic-gate node = AVL_DATA2NODE(first, off); 9647c478bd9Sstevel@tonic-gate parent = AVL_XPARENT(node); 9657c478bd9Sstevel@tonic-gate goto check_right_side; 9667c478bd9Sstevel@tonic-gate } 9677c478bd9Sstevel@tonic-gate 9687c478bd9Sstevel@tonic-gate /* 9697c478bd9Sstevel@tonic-gate * If there is no parent to return to we are done. 9707c478bd9Sstevel@tonic-gate */ 9717c478bd9Sstevel@tonic-gate parent = (avl_node_t *)((uintptr_t)(*cookie) & ~CHILDBIT); 9727c478bd9Sstevel@tonic-gate if (parent == NULL) { 9737c478bd9Sstevel@tonic-gate if (tree->avl_root != NULL) { 9747c478bd9Sstevel@tonic-gate ASSERT(tree->avl_numnodes == 1); 9757c478bd9Sstevel@tonic-gate tree->avl_root = NULL; 9767c478bd9Sstevel@tonic-gate tree->avl_numnodes = 0; 9777c478bd9Sstevel@tonic-gate } 9787c478bd9Sstevel@tonic-gate return (NULL); 9797c478bd9Sstevel@tonic-gate } 9807c478bd9Sstevel@tonic-gate 9817c478bd9Sstevel@tonic-gate /* 9827c478bd9Sstevel@tonic-gate * Remove the child pointer we just visited from the parent and tree. 9837c478bd9Sstevel@tonic-gate */ 9847c478bd9Sstevel@tonic-gate child = (uintptr_t)(*cookie) & CHILDBIT; 9857c478bd9Sstevel@tonic-gate parent->avl_child[child] = NULL; 9867c478bd9Sstevel@tonic-gate ASSERT(tree->avl_numnodes > 1); 9877c478bd9Sstevel@tonic-gate --tree->avl_numnodes; 9887c478bd9Sstevel@tonic-gate 9897c478bd9Sstevel@tonic-gate /* 9907c478bd9Sstevel@tonic-gate * If we just did a right child or there isn't one, go up to parent. 9917c478bd9Sstevel@tonic-gate */ 9927c478bd9Sstevel@tonic-gate if (child == 1 || parent->avl_child[1] == NULL) { 9937c478bd9Sstevel@tonic-gate node = parent; 9947c478bd9Sstevel@tonic-gate parent = AVL_XPARENT(parent); 9957c478bd9Sstevel@tonic-gate goto done; 9967c478bd9Sstevel@tonic-gate } 9977c478bd9Sstevel@tonic-gate 9987c478bd9Sstevel@tonic-gate /* 9997c478bd9Sstevel@tonic-gate * Do parent's right child, then leftmost descendent. 10007c478bd9Sstevel@tonic-gate */ 10017c478bd9Sstevel@tonic-gate node = parent->avl_child[1]; 10027c478bd9Sstevel@tonic-gate while (node->avl_child[0] != NULL) { 10037c478bd9Sstevel@tonic-gate parent = node; 10047c478bd9Sstevel@tonic-gate node = node->avl_child[0]; 10057c478bd9Sstevel@tonic-gate } 10067c478bd9Sstevel@tonic-gate 10077c478bd9Sstevel@tonic-gate /* 10087c478bd9Sstevel@tonic-gate * If here, we moved to a left child. It may have one 10097c478bd9Sstevel@tonic-gate * child on the right (when balance == +1). 10107c478bd9Sstevel@tonic-gate */ 10117c478bd9Sstevel@tonic-gate check_right_side: 10127c478bd9Sstevel@tonic-gate if (node->avl_child[1] != NULL) { 10137c478bd9Sstevel@tonic-gate ASSERT(AVL_XBALANCE(node) == 1); 10147c478bd9Sstevel@tonic-gate parent = node; 10157c478bd9Sstevel@tonic-gate node = node->avl_child[1]; 10167c478bd9Sstevel@tonic-gate ASSERT(node->avl_child[0] == NULL && 10177c478bd9Sstevel@tonic-gate node->avl_child[1] == NULL); 10187c478bd9Sstevel@tonic-gate } else { 10197c478bd9Sstevel@tonic-gate ASSERT(AVL_XBALANCE(node) <= 0); 10207c478bd9Sstevel@tonic-gate } 10217c478bd9Sstevel@tonic-gate 10227c478bd9Sstevel@tonic-gate done: 10237c478bd9Sstevel@tonic-gate if (parent == NULL) { 10247c478bd9Sstevel@tonic-gate *cookie = (void *)CHILDBIT; 10257c478bd9Sstevel@tonic-gate ASSERT(node == tree->avl_root); 10267c478bd9Sstevel@tonic-gate } else { 10277c478bd9Sstevel@tonic-gate *cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node)); 10287c478bd9Sstevel@tonic-gate } 10297c478bd9Sstevel@tonic-gate 10307c478bd9Sstevel@tonic-gate return (AVL_NODE2DATA(node, off)); 10317c478bd9Sstevel@tonic-gate } 1032