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