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