avl.c revision 265745
1153758Swollman/* 2205475Sedwin * CDDL HEADER START 3192886Sedwin * 4192886Sedwin * The contents of this file are subject to the terms of the 52744Swollman * Common Development and Distribution License (the "License"). 658782Sru * You may not use this file except in compliance with the License. 758782Sru * 858782Sru * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 958782Sru * or http://www.opensolaris.org/os/licensing. 1043009Swollman * See the License for the specific language governing permissions 1143009Swollman * and limitations under the License. 1243009Swollman * 1358782Sru * When distributing Covered Code, include this CDDL HEADER in each 1443009Swollman * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 1543009Swollman * If applicable, add the following below this CDDL HEADER, with the 1619876Swollman * fields enclosed by brackets "[]" replaced with your own identifying 1719876Swollman * information: Portions Copyright [yyyy] [name of copyright owner] 1830708Swollman * 1919876Swollman * CDDL HEADER END 2075264Swollman */ 212744Swollman/* 2275264Swollman * Copyright 2009 Sun Microsystems, Inc. All rights reserved. 2375264Swollman * Use is subject to license terms. 2475264Swollman */ 2575264Swollman 2675264Swollman/* 2775264Swollman * AVL - generic AVL tree implementation for kernel use 2875264Swollman * 2975264Swollman * A complete description of AVL trees can be found in many CS textbooks. 3075264Swollman * 3175264Swollman * Here is a very brief overview. An AVL tree is a binary search tree that is 3275264Swollman * almost perfectly balanced. By "almost" perfectly balanced, we mean that at 3375264Swollman * any given node, the left and right subtrees are allowed to differ in height 3420091Swollman * by at most 1 level. 3520091Swollman * 3620091Swollman * This relaxation from a perfectly balanced binary tree allows doing 3720091Swollman * insertion and deletion relatively efficiently. Searching the tree is 38169808Swollman * still a fast operation, roughly O(log(N)). 39158417Swollman * 40158417Swollman * The key to insertion and deletion is a set of tree manipulations called 4120091Swollman * rotations, which bring unbalanced subtrees back into the semi-balanced state. 4220091Swollman * 43169808Swollman * This implementation of AVL trees has the following peculiarities: 44169808Swollman * 45169808Swollman * - The AVL specific data structures are physically embedded as fields 46169808Swollman * in the "using" data structures. To maintain generality the code 47169808Swollman * must constantly translate between "avl_node_t *" and containing 48169808Swollman * data structure "void *"s by adding/subtracting the avl_offset. 49169808Swollman * 50169808Swollman * - Since the AVL data is always embedded in other structures, there is 51169808Swollman * no locking or memory allocation in the AVL routines. This must be 52169808Swollman * provided for by the enclosing data structure's semantics. Typically, 53169808Swollman * avl_insert()/_add()/_remove()/avl_insert_here() require some kind of 54169808Swollman * exclusive write lock. Other operations require a read lock. 55169808Swollman * 56169808Swollman * - The implementation uses iteration instead of explicit recursion, 57169808Swollman * since it is intended to run on limited size kernel stacks. Since 58169808Swollman * there is no recursion stack present to move "up" in the tree, 592744Swollman * there is an explicit "parent" link in the avl_node_t. 60205475Sedwin * 61205475Sedwin * - The left/right children pointers of a node are in an array. 62205475Sedwin * In the code, variables (instead of constants) are used to represent 63205475Sedwin * left and right indices. The implementation is written as if it only 64205475Sedwin * dealt with left handed manipulations. By changing the value assigned 65205475Sedwin * to "left", the code also works for right handed trees. The 66205475Sedwin * following variables/terms are frequently used: 67205475Sedwin * 68205475Sedwin * int left; // 0 when dealing with left children, 69205475Sedwin * // 1 for dealing with right children 70205475Sedwin * 71205475Sedwin * int left_heavy; // -1 when left subtree is taller at some node, 72205475Sedwin * // +1 when right subtree is taller 73205475Sedwin * 74205475Sedwin * int right; // will be the opposite of left (0 or 1) 75205475Sedwin * int right_heavy;// will be the opposite of left_heavy (-1 or 1) 76205475Sedwin * 77205475Sedwin * int direction; // 0 for "<" (ie. left child); 1 for ">" (right) 78205475Sedwin * 79205475Sedwin * Though it is a little more confusing to read the code, the approach 80205475Sedwin * allows using half as much code (and hence cache footprint) for tree 81205475Sedwin * manipulations and eliminates many conditional branches. 82205475Sedwin * 83205475Sedwin * - The avl_index_t is an opaque "cookie" used to find nodes at or 84205475Sedwin * adjacent to where a new value would be inserted in the tree. The value 85205475Sedwin * is a modified "avl_node_t *". The bottom bit (normally 0 for a 86205475Sedwin * pointer) is set to indicate if that the new node has a value greater 8720091Swollman * than the value of the indicated "avl_node_t *". 8858782Sru */ 8958782Sru 9058782Sru#include <sys/types.h> 9158782Sru#include <sys/param.h> 9258782Sru#include <sys/stdint.h> 9358782Sru#include <sys/debug.h> 9458782Sru#include <sys/avl.h> 9558782Sru 962744Swollman/* 9719876Swollman * Small arrays to translate between balance (or diff) values and child indices. 9830708Swollman * 9958782Sru * Code that deals with binary tree data structures will randomly use 100153667Swollman * left and right children when examining a tree. C "if()" statements 10158782Sru * which evaluate randomly suffer from very poor hardware branch prediction. 10258782Sru * In this code we avoid some of the branch mispredictions by using the 10358782Sru * following translation arrays. They replace random branches with an 10419876Swollman * additional memory reference. Since the translation arrays are both very 10519876Swollman * small the data should remain efficiently in cache. 10658782Sru */ 10758782Srustatic const int avl_child2balance[2] = {-1, 1}; 10858782Srustatic const int avl_balance2child[] = {0, 0, 1}; 10958782Sru 110199107Sedwin 111199107Sedwin/* 112199107Sedwin * Walk from one node to the previous valued node (ie. an infix walk 113199107Sedwin * towards the left). At any given node we do one of 2 things: 114199107Sedwin * 115199107Sedwin * - If there is a left child, go to it, then to it's rightmost descendant. 116199107Sedwin * 117199107Sedwin * - otherwise we return through parent nodes until we've come from a right 118199107Sedwin * child. 119199107Sedwin * 120199107Sedwin * Return Value: 121199107Sedwin * NULL - if at the end of the nodes 122199107Sedwin * otherwise next node 123199107Sedwin */ 124199107Sedwinvoid * 125199107Sedwinavl_walk(avl_tree_t *tree, void *oldnode, int left) 126199107Sedwin{ 127199107Sedwin size_t off = tree->avl_offset; 128205475Sedwin avl_node_t *node = AVL_DATA2NODE(oldnode, off); 129205475Sedwin int right = 1 - left; 130205475Sedwin int was_child; 131205475Sedwin 132205475Sedwin 133205475Sedwin /* 134205475Sedwin * nowhere to walk to if tree is empty 135205475Sedwin */ 136205475Sedwin if (node == NULL) 137205475Sedwin return (NULL); 138205475Sedwin 139205475Sedwin /* 140205475Sedwin * Visit the previous valued node. There are two possibilities: 141205475Sedwin * 142205475Sedwin * If this node has a left child, go down one left, then all 143205475Sedwin * the way right. 144205475Sedwin */ 145205475Sedwin if (node->avl_child[left] != NULL) { 146205475Sedwin for (node = node->avl_child[left]; 147205475Sedwin node->avl_child[right] != NULL; 148205475Sedwin node = node->avl_child[right]) 149205475Sedwin ; 150205475Sedwin /* 15119876Swollman * Otherwise, return thru left children as far as we can. 15275264Swollman */ 153199107Sedwin } else { 154199107Sedwin for (;;) { 155205475Sedwin was_child = AVL_XCHILD(node); 156205475Sedwin node = AVL_XPARENT(node); 157205475Sedwin if (node == NULL) 15875264Swollman return (NULL); 15943009Swollman if (was_child == right) 16075264Swollman break; 161199336Sedwin } 162205475Sedwin } 163205475Sedwin 16475264Swollman return (AVL_NODE2DATA(node, off)); 165199107Sedwin} 166199107Sedwin 167199107Sedwin/* 168205475Sedwin * Return the lowest valued node in a tree or NULL. 169205475Sedwin * (leftmost child from root of tree) 170205475Sedwin */ 171205475Sedwinvoid * 172205475Sedwinavl_first(avl_tree_t *tree) 173205475Sedwin{ 17419876Swollman avl_node_t *node; 17543009Swollman avl_node_t *prev = NULL; 17643009Swollman size_t off = tree->avl_offset; 17743009Swollman 17843009Swollman for (node = tree->avl_root; node != NULL; node = node->avl_child[0]) 17943009Swollman prev = node; 18043009Swollman 18143009Swollman if (prev != NULL) 18243009Swollman return (AVL_NODE2DATA(prev, off)); 18343009Swollman return (NULL); 18414338Swollman} 18519876Swollman 186149511Swollman/* 18714338Swollman * Return the highest valued node in a tree or NULL. 18886218Swollman * (rightmost child from root of tree) 18958782Sru */ 190149511Swollmanvoid * 191149511Swollmanavl_last(avl_tree_t *tree) 192149511Swollman{ 193149511Swollman avl_node_t *node; 19486218Swollman avl_node_t *prev = NULL; 19514338Swollman size_t off = tree->avl_offset; 19619876Swollman 197149511Swollman for (node = tree->avl_root; node != NULL; node = node->avl_child[1]) 198149511Swollman prev = node; 19919876Swollman 20030708Swollman if (prev != NULL) 20119876Swollman return (AVL_NODE2DATA(prev, off)); 202153667Swollman return (NULL); 20330708Swollman} 20430708Swollman 20530708Swollman/* 20630708Swollman * Access the node immediately before or after an insertion point. 20730708Swollman * 20830708Swollman * "avl_index_t" is a (avl_node_t *) with the bottom bit indicating a child 20919876Swollman * 21019876Swollman * Return value: 21130708Swollman * NULL: no node in the given direction 21230708Swollman * "void *" of the found tree node 21330708Swollman */ 21458782Sruvoid * 21530708Swollmanavl_nearest(avl_tree_t *tree, avl_index_t where, int direction) 21658782Sru{ 21758782Sru int child = AVL_INDEX2CHILD(where); 21830708Swollman avl_node_t *node = AVL_INDEX2NODE(where); 21930708Swollman void *data; 22075264Swollman size_t off = tree->avl_offset; 22130708Swollman 22230708Swollman if (node == NULL) { 22330708Swollman ASSERT(tree->avl_root == NULL); 22458782Sru return (NULL); 22530708Swollman } 22630708Swollman data = AVL_NODE2DATA(node, off); 22730708Swollman if (child != direction) 22830708Swollman return (data); 22930708Swollman 23075264Swollman return (avl_walk(tree, data, direction)); 23130708Swollman} 23275264Swollman 23330708Swollman 23430708Swollman/* 235153667Swollman * Search for the node which contains "value". The algorithm is a 236153667Swollman * simple binary tree search. 23743009Swollman * 23819876Swollman * return value: 23919876Swollman * NULL: the value is not in the AVL tree 240149511Swollman * *where (if not NULL) is set to indicate the insertion point 24119876Swollman * "void *" of the found tree node 24219876Swollman */ 243149511Swollmanvoid * 24419876Swollmanavl_find(avl_tree_t *tree, const void *value, avl_index_t *where) 24519876Swollman{ 246149511Swollman avl_node_t *node; 247149511Swollman avl_node_t *prev = NULL; 24858782Sru int child = 0; 24958782Sru int diff; 250153667Swollman size_t off = tree->avl_offset; 25158782Sru 25258782Sru for (node = tree->avl_root; node != NULL; 25358782Sru node = node->avl_child[child]) { 25458782Sru 25558782Sru prev = node; 25675264Swollman 25758782Sru diff = tree->avl_compar(value, AVL_NODE2DATA(node, off)); 25858782Sru ASSERT(-1 <= diff && diff <= 1); 25958782Sru if (diff == 0) { 26058782Sru#ifdef DEBUG 26158782Sru if (where != NULL) 26219876Swollman *where = 0; 26319876Swollman#endif 264149511Swollman return (AVL_NODE2DATA(node, off)); 26519876Swollman } 26619876Swollman child = avl_balance2child[1 + diff]; 26730708Swollman 26830708Swollman } 26919876Swollman 27019876Swollman if (where != NULL) 27119876Swollman *where = AVL_MKINDEX(prev, child); 27219876Swollman 27319876Swollman return (NULL); 27419876Swollman} 27519876Swollman 27619876Swollman 27719876Swollman/* 278171945Sedwin * Perform a rotation to restore balance at the subtree given by depth. 27919876Swollman * 28019876Swollman * This routine is used by both insertion and deletion. The return value 281171945Sedwin * indicates: 282171945Sedwin * 0 : subtree did not change height 283171945Sedwin * !0 : subtree was reduced in height 28419876Swollman * 28519876Swollman * The code is written as if handling left rotations, right rotations are 28630708Swollman * symmetric and handled by swapping values of variables right/left[_heavy] 28719876Swollman * 28819876Swollman * On input balance is the "new" balance at "node". This value is either 28930708Swollman * -2 or +2. 29019876Swollman */ 29119876Swollmanstatic int 29258782Sruavl_rotation(avl_tree_t *tree, avl_node_t *node, int balance) 29319876Swollman{ 29419876Swollman int left = !(balance < 0); /* when balance = -2, left will be 0 */ 29558782Sru int right = 1 - left; 29658782Sru int left_heavy = balance >> 1; 297149511Swollman int right_heavy = -left_heavy; 298149511Swollman avl_node_t *parent = AVL_XPARENT(node); 29975264Swollman avl_node_t *child = node->avl_child[left]; 30075264Swollman avl_node_t *cright; 30119876Swollman avl_node_t *gchild; 30275264Swollman avl_node_t *gright; 30375264Swollman avl_node_t *gleft; 30475264Swollman int which_child = AVL_XCHILD(node); 30575264Swollman int child_bal = AVL_XBALANCE(child); 30675264Swollman 30775264Swollman /* BEGIN CSTYLED */ 30875264Swollman /* 30975264Swollman * case 1 : node is overly left heavy, the left child is balanced or 31075264Swollman * also left heavy. This requires the following rotation. 31175264Swollman * 31275264Swollman * (node bal:-2) 31375264Swollman * / \ 31475264Swollman * / \ 31575264Swollman * (child bal:0 or -1) 31675264Swollman * / \ 31786218Swollman * / \ 31886218Swollman * cright 31986218Swollman * 32086218Swollman * becomes: 32186218Swollman * 32286218Swollman * (child bal:1 or 0) 32386218Swollman * / \ 32486218Swollman * / \ 32586218Swollman * (node bal:-1 or 0) 32675264Swollman * / \ 32775264Swollman * / \ 32875264Swollman * cright 32919876Swollman * 330149511Swollman * we detect this situation by noting that child's balance is not 331149511Swollman * right_heavy. 33219876Swollman */ 33319876Swollman /* END CSTYLED */ 33419876Swollman if (child_bal != right_heavy) { 33519876Swollman 33619876Swollman /* 33730708Swollman * compute new balance of nodes 33858782Sru * 33919876Swollman * If child used to be left heavy (now balanced) we reduced 34019876Swollman * the height of this sub-tree -- used in "return...;" below 34119876Swollman */ 34258782Sru child_bal += right_heavy; /* adjust towards right */ 34375264Swollman 34475264Swollman /* 34575264Swollman * move "cright" to be node's left child 34675264Swollman */ 34775264Swollman cright = child->avl_child[right]; 34875264Swollman node->avl_child[left] = cright; 34975264Swollman if (cright != NULL) { 35019876Swollman AVL_SETPARENT(cright, node); 351114170Swollman AVL_SETCHILD(cright, left); 352114170Swollman } 353114170Swollman 354114170Swollman /* 355114170Swollman * move node to be child's right child 356114170Swollman */ 357114170Swollman child->avl_child[right] = node; 35819876Swollman AVL_SETBALANCE(node, -child_bal); 35919876Swollman AVL_SETCHILD(node, right); 36058782Sru AVL_SETPARENT(node, child); 36119876Swollman 36219876Swollman /* 36319876Swollman * update the pointer into this subtree 36420091Swollman */ 36519876Swollman AVL_SETBALANCE(child, child_bal); 366149511Swollman AVL_SETCHILD(child, which_child); 36720091Swollman AVL_SETPARENT(child, parent); 36820091Swollman if (parent != NULL) 36920091Swollman parent->avl_child[which_child] = child; 37020091Swollman else 37120091Swollman tree->avl_root = child; 37220091Swollman 37320091Swollman return (child_bal == 0); 37475264Swollman } 37520091Swollman 37620091Swollman /* BEGIN CSTYLED */ 37720091Swollman /* 37820091Swollman * case 2 : When node is left heavy, but child is right heavy we use 37920091Swollman * a different rotation. 38075264Swollman * 38119876Swollman * (node b:-2) 38275264Swollman * / \ 38319876Swollman * / \ 38419876Swollman * / \ 38575264Swollman * (child b:+1) 38675264Swollman * / \ 38719876Swollman * / \ 38819876Swollman * (gchild b: != 0) 38919876Swollman * / \ 39019876Swollman * / \ 391153667Swollman * gleft gright 39219876Swollman * 39319876Swollman * becomes: 39419876Swollman * 39519876Swollman * (gchild b:0) 39619876Swollman * / \ 39719876Swollman * / \ 39819876Swollman * / \ 39943009Swollman * (child b:?) (node b:?) 40043009Swollman * / \ / \ 40143009Swollman * / \ / \ 40243009Swollman * gleft gright 40319876Swollman * 40419876Swollman * computing the new balances is more complicated. As an example: 40519876Swollman * if gchild was right_heavy, then child is now left heavy 40619876Swollman * else it is balanced 40719876Swollman */ 40819876Swollman /* END CSTYLED */ 40919876Swollman gchild = child->avl_child[right]; 41019876Swollman gleft = gchild->avl_child[left]; 41119876Swollman gright = gchild->avl_child[right]; 412 413 /* 414 * move gright to left child of node and 415 * 416 * move gleft to right child of node 417 */ 418 node->avl_child[left] = gright; 419 if (gright != NULL) { 420 AVL_SETPARENT(gright, node); 421 AVL_SETCHILD(gright, left); 422 } 423 424 child->avl_child[right] = gleft; 425 if (gleft != NULL) { 426 AVL_SETPARENT(gleft, child); 427 AVL_SETCHILD(gleft, right); 428 } 429 430 /* 431 * move child to left child of gchild and 432 * 433 * move node to right child of gchild and 434 * 435 * fixup parent of all this to point to gchild 436 */ 437 balance = AVL_XBALANCE(gchild); 438 gchild->avl_child[left] = child; 439 AVL_SETBALANCE(child, (balance == right_heavy ? left_heavy : 0)); 440 AVL_SETPARENT(child, gchild); 441 AVL_SETCHILD(child, left); 442 443 gchild->avl_child[right] = node; 444 AVL_SETBALANCE(node, (balance == left_heavy ? right_heavy : 0)); 445 AVL_SETPARENT(node, gchild); 446 AVL_SETCHILD(node, right); 447 448 AVL_SETBALANCE(gchild, 0); 449 AVL_SETPARENT(gchild, parent); 450 AVL_SETCHILD(gchild, which_child); 451 if (parent != NULL) 452 parent->avl_child[which_child] = gchild; 453 else 454 tree->avl_root = gchild; 455 456 return (1); /* the new tree is always shorter */ 457} 458 459 460/* 461 * Insert a new node into an AVL tree at the specified (from avl_find()) place. 462 * 463 * Newly inserted nodes are always leaf nodes in the tree, since avl_find() 464 * searches out to the leaf positions. The avl_index_t indicates the node 465 * which will be the parent of the new node. 466 * 467 * After the node is inserted, a single rotation further up the tree may 468 * be necessary to maintain an acceptable AVL balance. 469 */ 470void 471avl_insert(avl_tree_t *tree, void *new_data, avl_index_t where) 472{ 473 avl_node_t *node; 474 avl_node_t *parent = AVL_INDEX2NODE(where); 475 int old_balance; 476 int new_balance; 477 int which_child = AVL_INDEX2CHILD(where); 478 size_t off = tree->avl_offset; 479 480 ASSERT(tree); 481#ifdef _LP64 482 ASSERT(((uintptr_t)new_data & 0x7) == 0); 483#endif 484 485 node = AVL_DATA2NODE(new_data, off); 486 487 /* 488 * First, add the node to the tree at the indicated position. 489 */ 490 ++tree->avl_numnodes; 491 492 node->avl_child[0] = NULL; 493 node->avl_child[1] = NULL; 494 495 AVL_SETCHILD(node, which_child); 496 AVL_SETBALANCE(node, 0); 497 AVL_SETPARENT(node, parent); 498 if (parent != NULL) { 499 ASSERT(parent->avl_child[which_child] == NULL); 500 parent->avl_child[which_child] = node; 501 } else { 502 ASSERT(tree->avl_root == NULL); 503 tree->avl_root = node; 504 } 505 /* 506 * Now, back up the tree modifying the balance of all nodes above the 507 * insertion point. If we get to a highly unbalanced ancestor, we 508 * need to do a rotation. If we back out of the tree we are done. 509 * If we brought any subtree into perfect balance (0), we are also done. 510 */ 511 for (;;) { 512 node = parent; 513 if (node == NULL) 514 return; 515 516 /* 517 * Compute the new balance 518 */ 519 old_balance = AVL_XBALANCE(node); 520 new_balance = old_balance + avl_child2balance[which_child]; 521 522 /* 523 * If we introduced equal balance, then we are done immediately 524 */ 525 if (new_balance == 0) { 526 AVL_SETBALANCE(node, 0); 527 return; 528 } 529 530 /* 531 * If both old and new are not zero we went 532 * from -1 to -2 balance, do a rotation. 533 */ 534 if (old_balance != 0) 535 break; 536 537 AVL_SETBALANCE(node, new_balance); 538 parent = AVL_XPARENT(node); 539 which_child = AVL_XCHILD(node); 540 } 541 542 /* 543 * perform a rotation to fix the tree and return 544 */ 545 (void) avl_rotation(tree, node, new_balance); 546} 547 548/* 549 * Insert "new_data" in "tree" in the given "direction" either after or 550 * before (AVL_AFTER, AVL_BEFORE) the data "here". 551 * 552 * Insertions can only be done at empty leaf points in the tree, therefore 553 * if the given child of the node is already present we move to either 554 * the AVL_PREV or AVL_NEXT and reverse the insertion direction. Since 555 * every other node in the tree is a leaf, this always works. 556 * 557 * To help developers using this interface, we assert that the new node 558 * is correctly ordered at every step of the way in DEBUG kernels. 559 */ 560void 561avl_insert_here( 562 avl_tree_t *tree, 563 void *new_data, 564 void *here, 565 int direction) 566{ 567 avl_node_t *node; 568 int child = direction; /* rely on AVL_BEFORE == 0, AVL_AFTER == 1 */ 569#ifdef DEBUG 570 int diff; 571#endif 572 573 ASSERT(tree != NULL); 574 ASSERT(new_data != NULL); 575 ASSERT(here != NULL); 576 ASSERT(direction == AVL_BEFORE || direction == AVL_AFTER); 577 578 /* 579 * If corresponding child of node is not NULL, go to the neighboring 580 * node and reverse the insertion direction. 581 */ 582 node = AVL_DATA2NODE(here, tree->avl_offset); 583 584#ifdef DEBUG 585 diff = tree->avl_compar(new_data, here); 586 ASSERT(-1 <= diff && diff <= 1); 587 ASSERT(diff != 0); 588 ASSERT(diff > 0 ? child == 1 : child == 0); 589#endif 590 591 if (node->avl_child[child] != NULL) { 592 node = node->avl_child[child]; 593 child = 1 - child; 594 while (node->avl_child[child] != NULL) { 595#ifdef DEBUG 596 diff = tree->avl_compar(new_data, 597 AVL_NODE2DATA(node, tree->avl_offset)); 598 ASSERT(-1 <= diff && diff <= 1); 599 ASSERT(diff != 0); 600 ASSERT(diff > 0 ? child == 1 : child == 0); 601#endif 602 node = node->avl_child[child]; 603 } 604#ifdef DEBUG 605 diff = tree->avl_compar(new_data, 606 AVL_NODE2DATA(node, tree->avl_offset)); 607 ASSERT(-1 <= diff && diff <= 1); 608 ASSERT(diff != 0); 609 ASSERT(diff > 0 ? child == 1 : child == 0); 610#endif 611 } 612 ASSERT(node->avl_child[child] == NULL); 613 614 avl_insert(tree, new_data, AVL_MKINDEX(node, child)); 615} 616 617/* 618 * Add a new node to an AVL tree. 619 */ 620void 621avl_add(avl_tree_t *tree, void *new_node) 622{ 623 avl_index_t where; 624 625 /* 626 * This is unfortunate. We want to call panic() here, even for 627 * non-DEBUG kernels. In userland, however, we can't depend on anything 628 * in libc or else the rtld build process gets confused. So, all we can 629 * do in userland is resort to a normal ASSERT(). 630 */ 631 if (avl_find(tree, new_node, &where) != NULL) 632#ifdef _KERNEL 633 panic("avl_find() succeeded inside avl_add()"); 634#else 635 ASSERT(0); 636#endif 637 avl_insert(tree, new_node, where); 638} 639 640/* 641 * Delete a node from the AVL tree. Deletion is similar to insertion, but 642 * with 2 complications. 643 * 644 * First, we may be deleting an interior node. Consider the following subtree: 645 * 646 * d c c 647 * / \ / \ / \ 648 * b e b e b e 649 * / \ / \ / 650 * a c a a 651 * 652 * When we are deleting node (d), we find and bring up an adjacent valued leaf 653 * node, say (c), to take the interior node's place. In the code this is 654 * handled by temporarily swapping (d) and (c) in the tree and then using 655 * common code to delete (d) from the leaf position. 656 * 657 * Secondly, an interior deletion from a deep tree may require more than one 658 * rotation to fix the balance. This is handled by moving up the tree through 659 * parents and applying rotations as needed. The return value from 660 * avl_rotation() is used to detect when a subtree did not change overall 661 * height due to a rotation. 662 */ 663void 664avl_remove(avl_tree_t *tree, void *data) 665{ 666 avl_node_t *delete; 667 avl_node_t *parent; 668 avl_node_t *node; 669 avl_node_t tmp; 670 int old_balance; 671 int new_balance; 672 int left; 673 int right; 674 int which_child; 675 size_t off = tree->avl_offset; 676 677 ASSERT(tree); 678 679 delete = AVL_DATA2NODE(data, off); 680 681 /* 682 * Deletion is easiest with a node that has at most 1 child. 683 * We swap a node with 2 children with a sequentially valued 684 * neighbor node. That node will have at most 1 child. Note this 685 * has no effect on the ordering of the remaining nodes. 686 * 687 * As an optimization, we choose the greater neighbor if the tree 688 * is right heavy, otherwise the left neighbor. This reduces the 689 * number of rotations needed. 690 */ 691 if (delete->avl_child[0] != NULL && delete->avl_child[1] != NULL) { 692 693 /* 694 * choose node to swap from whichever side is taller 695 */ 696 old_balance = AVL_XBALANCE(delete); 697 left = avl_balance2child[old_balance + 1]; 698 right = 1 - left; 699 700 /* 701 * get to the previous value'd node 702 * (down 1 left, as far as possible right) 703 */ 704 for (node = delete->avl_child[left]; 705 node->avl_child[right] != NULL; 706 node = node->avl_child[right]) 707 ; 708 709 /* 710 * create a temp placeholder for 'node' 711 * move 'node' to delete's spot in the tree 712 */ 713 tmp = *node; 714 715 *node = *delete; 716 if (node->avl_child[left] == node) 717 node->avl_child[left] = &tmp; 718 719 parent = AVL_XPARENT(node); 720 if (parent != NULL) 721 parent->avl_child[AVL_XCHILD(node)] = node; 722 else 723 tree->avl_root = node; 724 AVL_SETPARENT(node->avl_child[left], node); 725 AVL_SETPARENT(node->avl_child[right], node); 726 727 /* 728 * Put tmp where node used to be (just temporary). 729 * It always has a parent and at most 1 child. 730 */ 731 delete = &tmp; 732 parent = AVL_XPARENT(delete); 733 parent->avl_child[AVL_XCHILD(delete)] = delete; 734 which_child = (delete->avl_child[1] != 0); 735 if (delete->avl_child[which_child] != NULL) 736 AVL_SETPARENT(delete->avl_child[which_child], delete); 737 } 738 739 740 /* 741 * Here we know "delete" is at least partially a leaf node. It can 742 * be easily removed from the tree. 743 */ 744 ASSERT(tree->avl_numnodes > 0); 745 --tree->avl_numnodes; 746 parent = AVL_XPARENT(delete); 747 which_child = AVL_XCHILD(delete); 748 if (delete->avl_child[0] != NULL) 749 node = delete->avl_child[0]; 750 else 751 node = delete->avl_child[1]; 752 753 /* 754 * Connect parent directly to node (leaving out delete). 755 */ 756 if (node != NULL) { 757 AVL_SETPARENT(node, parent); 758 AVL_SETCHILD(node, which_child); 759 } 760 if (parent == NULL) { 761 tree->avl_root = node; 762 return; 763 } 764 parent->avl_child[which_child] = node; 765 766 767 /* 768 * Since the subtree is now shorter, begin adjusting parent balances 769 * and performing any needed rotations. 770 */ 771 do { 772 773 /* 774 * Move up the tree and adjust the balance 775 * 776 * Capture the parent and which_child values for the next 777 * iteration before any rotations occur. 778 */ 779 node = parent; 780 old_balance = AVL_XBALANCE(node); 781 new_balance = old_balance - avl_child2balance[which_child]; 782 parent = AVL_XPARENT(node); 783 which_child = AVL_XCHILD(node); 784 785 /* 786 * If a node was in perfect balance but isn't anymore then 787 * we can stop, since the height didn't change above this point 788 * due to a deletion. 789 */ 790 if (old_balance == 0) { 791 AVL_SETBALANCE(node, new_balance); 792 break; 793 } 794 795 /* 796 * If the new balance is zero, we don't need to rotate 797 * else 798 * need a rotation to fix the balance. 799 * If the rotation doesn't change the height 800 * of the sub-tree we have finished adjusting. 801 */ 802 if (new_balance == 0) 803 AVL_SETBALANCE(node, new_balance); 804 else if (!avl_rotation(tree, node, new_balance)) 805 break; 806 } while (parent != NULL); 807} 808 809#define AVL_REINSERT(tree, obj) \ 810 avl_remove((tree), (obj)); \ 811 avl_add((tree), (obj)) 812 813boolean_t 814avl_update_lt(avl_tree_t *t, void *obj) 815{ 816 void *neighbor; 817 818 ASSERT(((neighbor = AVL_NEXT(t, obj)) == NULL) || 819 (t->avl_compar(obj, neighbor) <= 0)); 820 821 neighbor = AVL_PREV(t, obj); 822 if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) { 823 AVL_REINSERT(t, obj); 824 return (B_TRUE); 825 } 826 827 return (B_FALSE); 828} 829 830boolean_t 831avl_update_gt(avl_tree_t *t, void *obj) 832{ 833 void *neighbor; 834 835 ASSERT(((neighbor = AVL_PREV(t, obj)) == NULL) || 836 (t->avl_compar(obj, neighbor) >= 0)); 837 838 neighbor = AVL_NEXT(t, obj); 839 if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) { 840 AVL_REINSERT(t, obj); 841 return (B_TRUE); 842 } 843 844 return (B_FALSE); 845} 846 847boolean_t 848avl_update(avl_tree_t *t, void *obj) 849{ 850 void *neighbor; 851 852 neighbor = AVL_PREV(t, obj); 853 if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) < 0)) { 854 AVL_REINSERT(t, obj); 855 return (B_TRUE); 856 } 857 858 neighbor = AVL_NEXT(t, obj); 859 if ((neighbor != NULL) && (t->avl_compar(obj, neighbor) > 0)) { 860 AVL_REINSERT(t, obj); 861 return (B_TRUE); 862 } 863 864 return (B_FALSE); 865} 866 867/* 868 * initialize a new AVL tree 869 */ 870void 871avl_create(avl_tree_t *tree, int (*compar) (const void *, const void *), 872 size_t size, size_t offset) 873{ 874 ASSERT(tree); 875 ASSERT(compar); 876 ASSERT(size > 0); 877 ASSERT(size >= offset + sizeof (avl_node_t)); 878#ifdef _LP64 879 ASSERT((offset & 0x7) == 0); 880#endif 881 882 tree->avl_compar = compar; 883 tree->avl_root = NULL; 884 tree->avl_numnodes = 0; 885 tree->avl_size = size; 886 tree->avl_offset = offset; 887} 888 889/* 890 * Delete a tree. 891 */ 892/* ARGSUSED */ 893void 894avl_destroy(avl_tree_t *tree) 895{ 896 ASSERT(tree); 897 ASSERT(tree->avl_numnodes == 0); 898 ASSERT(tree->avl_root == NULL); 899} 900 901 902/* 903 * Return the number of nodes in an AVL tree. 904 */ 905ulong_t 906avl_numnodes(avl_tree_t *tree) 907{ 908 ASSERT(tree); 909 return (tree->avl_numnodes); 910} 911 912boolean_t 913avl_is_empty(avl_tree_t *tree) 914{ 915 ASSERT(tree); 916 return (tree->avl_numnodes == 0); 917} 918 919#define CHILDBIT (1L) 920 921/* 922 * Post-order tree walk used to visit all tree nodes and destroy the tree 923 * in post order. This is used for destroying a tree without paying any cost 924 * for rebalancing it. 925 * 926 * example: 927 * 928 * void *cookie = NULL; 929 * my_data_t *node; 930 * 931 * while ((node = avl_destroy_nodes(tree, &cookie)) != NULL) 932 * free(node); 933 * avl_destroy(tree); 934 * 935 * The cookie is really an avl_node_t to the current node's parent and 936 * an indication of which child you looked at last. 937 * 938 * On input, a cookie value of CHILDBIT indicates the tree is done. 939 */ 940void * 941avl_destroy_nodes(avl_tree_t *tree, void **cookie) 942{ 943 avl_node_t *node; 944 avl_node_t *parent; 945 int child; 946 void *first; 947 size_t off = tree->avl_offset; 948 949 /* 950 * Initial calls go to the first node or it's right descendant. 951 */ 952 if (*cookie == NULL) { 953 first = avl_first(tree); 954 955 /* 956 * deal with an empty tree 957 */ 958 if (first == NULL) { 959 *cookie = (void *)CHILDBIT; 960 return (NULL); 961 } 962 963 node = AVL_DATA2NODE(first, off); 964 parent = AVL_XPARENT(node); 965 goto check_right_side; 966 } 967 968 /* 969 * If there is no parent to return to we are done. 970 */ 971 parent = (avl_node_t *)((uintptr_t)(*cookie) & ~CHILDBIT); 972 if (parent == NULL) { 973 if (tree->avl_root != NULL) { 974 ASSERT(tree->avl_numnodes == 1); 975 tree->avl_root = NULL; 976 tree->avl_numnodes = 0; 977 } 978 return (NULL); 979 } 980 981 /* 982 * Remove the child pointer we just visited from the parent and tree. 983 */ 984 child = (uintptr_t)(*cookie) & CHILDBIT; 985 parent->avl_child[child] = NULL; 986 ASSERT(tree->avl_numnodes > 1); 987 --tree->avl_numnodes; 988 989 /* 990 * If we just did a right child or there isn't one, go up to parent. 991 */ 992 if (child == 1 || parent->avl_child[1] == NULL) { 993 node = parent; 994 parent = AVL_XPARENT(parent); 995 goto done; 996 } 997 998 /* 999 * Do parent's right child, then leftmost descendent. 1000 */ 1001 node = parent->avl_child[1]; 1002 while (node->avl_child[0] != NULL) { 1003 parent = node; 1004 node = node->avl_child[0]; 1005 } 1006 1007 /* 1008 * If here, we moved to a left child. It may have one 1009 * child on the right (when balance == +1). 1010 */ 1011check_right_side: 1012 if (node->avl_child[1] != NULL) { 1013 ASSERT(AVL_XBALANCE(node) == 1); 1014 parent = node; 1015 node = node->avl_child[1]; 1016 ASSERT(node->avl_child[0] == NULL && 1017 node->avl_child[1] == NULL); 1018 } else { 1019 ASSERT(AVL_XBALANCE(node) <= 0); 1020 } 1021 1022done: 1023 if (parent == NULL) { 1024 *cookie = (void *)CHILDBIT; 1025 ASSERT(node == tree->avl_root); 1026 } else { 1027 *cookie = (void *)((uintptr_t)parent | AVL_XCHILD(node)); 1028 } 1029 1030 return (AVL_NODE2DATA(node, off)); 1031} 1032