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