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