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