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