source: mainline/kernel/generic/src/adt/avl.c@ 358ec13

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 358ec13 was 358ec13, checked in by Jakub Jermar <jakub@…>, 18 years ago

Import the AVL tree implementation from the RCU branch.
  • Property mode set to 100644
File size: 15.2 KB
RevLine 
[358ec13]1/*
2 * Copyright (c) 2007 Vojtech Mencl
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup genericadt
30 * @{
31 */
32
33/**
34 * @file
35 * @brief AVL tree implementation.
36 *
37 * This file implements AVL tree type and operations.
38 *
39 * Implemented AVL tree has the following properties:
40 * @li It is a binary search tree with non-unique keys.
41 * @li Difference of heights of the left and the right subtree of every node is
42 * one at maximum.
43 *
44 * Every node has a pointer to its parent which allows insertion of multiple
45 * identical keys into the tree.
46 *
47 * Be careful when using this tree because of the base atribute which is added
48 * to every inserted node key. There is no rule in which order nodes with the
49 * same key are visited.
50 */
51
52#include <adt/avl.h>
53#include <debug.h>
54
55
56#define LEFT 0
57#define RIGHT 1
58
59
60/** Search for the first occurence of the given key in an AVL tree.
61 *
62 * @param t AVL tree.
63 * @param key Key to be searched.
64 *
65 * @return Pointer to a node or NULL if there is no such key.
66 */
67avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
68{
69 avltree_node_t *p;
70
71 /*
72 * Iteratively descend to the leaf that can contain the searched key.
73 */
74 p = t->root;
75 while (p != NULL) {
76 if (p->key > key)
77 p = p->lft;
78 else if (p->key < key)
79 p = p->rgt;
80 else
81 return p;
82 }
83 return NULL;
84}
85
86
87/** Find the node with the smallest key in an AVL tree.
88 *
89 * @param t AVL tree.
90 *
91 * @return Pointer to a node or NULL if there is no node in the tree.
92 */
93avltree_node_t *avltree_find_min(avltree_t *t)
94{
95 avltree_node_t *p = t->root;
96
97 /*
98 * Check whether the tree is empty.
99 */
100 if (!p)
101 return NULL;
102
103 /*
104 * Iteratively descend to the leftmost leaf in the tree.
105 */
106 while (p->lft != NULL)
107 p = p->lft;
108
109 return p;
110}
111
112/** Insert new node into AVL tree.
113 *
114 * @param t AVL tree.
115 * @param newnode New node to be inserted.
116 */
117void avltree_insert(avltree_t *t, avltree_node_t *newnode)
118{
119 avltree_node_t *par;
120 avltree_node_t *gpa;
121 avltree_node_t *top;
122 avltree_node_t **dpc;
123 uint64_t key;
124
125 ASSERT(t);
126 ASSERT(newnode);
127
128 /*
129 * Creating absolute key.
130 */
131 key = newnode->key + t->base;
132
133 /*
134 * Iteratively descend to the leaf that can contain the new node.
135 * Last node with non-zero balance in the way to leaf is stored as top -
136 * it is a place of possible inbalance.
137 */
138 dpc = &t->root;
139 gpa = NULL;
140 top = t->root;
141 while ((par = (*dpc)) != NULL) {
142 if (par->balance != 0) {
143 top = par;
144 }
145 gpa = par;
146 dpc = par->key > key ? &par->lft: &par->rgt;
147 }
148
149 /*
150 * Initialize new node.
151 */
152 newnode->key = key;
153 newnode->lft = NULL;
154 newnode->rgt = NULL;
155 newnode->par = gpa;
156 newnode->balance = 0;
157
158 /*
159 * Insert first node into the empty tree.
160 */
161 if (t->root == NULL) {
162 *dpc = newnode;
163 return;
164 }
165
166 /*
167 * Insert new node into previously found leaf place.
168 */
169 *dpc = newnode;
170
171 /*
172 * If the tree contains one node - end.
173 */
174 if (top == NULL)
175 return;
176
177 /*
178 * Store pointer of top's father which points to the node with
179 * potentially broken balance (top).
180 */
181 if (top->par == NULL) {
182 dpc = &t->root;
183 } else {
184 if (top->par->lft == top)
185 dpc = &top->par->lft;
186 else
187 dpc = &top->par->rgt;
188 }
189
190 /*
191 * Repair all balances on the way from top node to the newly inserted
192 * node.
193 */
194 par = top;
195 while (par != newnode) {
196 if (par->key > key) {
197 par->balance--;
198 par = par->lft;
199 } else {
200 par->balance++;
201 par = par->rgt;
202 }
203 }
204
205 /*
206 * To balance the tree, we must check and balance top node.
207 */
208 if (top->balance == -2) {
209 par = top->lft;
210 if (par->balance == -1) {
211 /*
212 * LL rotation.
213 */
214 top->lft = par->rgt;
215 if (top->lft != NULL)
216 top->lft->par = top;
217 par->par = top->par;
218 top->par = par;
219 par->rgt = top;
220 par->balance = 0;
221 top->balance = 0;
222 *dpc = par;
223 } else {
224 /*
225 * LR rotation.
226 */
227 ASSERT(par->balance == 1);
228
229 gpa = par->rgt;
230 par->rgt = gpa->lft;
231 if (gpa->lft != NULL)
232 gpa->lft->par = par;
233 gpa->lft = par;
234 par->par = gpa;
235 top->lft = gpa->rgt;
236 if (gpa->rgt != NULL)
237 gpa->rgt->par = top;
238 gpa->rgt = top;
239 gpa->par = top->par;
240 top->par = gpa;
241
242 if (gpa->balance == -1) {
243 par->balance = 0;
244 top->balance = 1;
245 } else if (gpa->balance == 0) {
246 par->balance = 0;
247 top->balance = 0;
248 } else {
249 par->balance = -1;
250 top->balance = 0;
251 }
252 gpa->balance = 0;
253 *dpc = gpa;
254 }
255 } else if (top->balance == 2) {
256 par = top->rgt;
257 if (par->balance == 1) {
258 /*
259 * RR rotation.
260 */
261 top->rgt = par->lft;
262 if (top->rgt != NULL)
263 top->rgt->par = top;
264 par->par = top->par;
265 top->par = par;
266 par->lft = top;
267 par->balance = 0;
268 top->balance = 0;
269 *dpc = par;
270 } else {
271 /*
272 * RL rotation.
273 */
274 ASSERT(par->balance == -1);
275
276 gpa = par->lft;
277 par->lft = gpa->rgt;
278 if (gpa->rgt != NULL)
279 gpa->rgt->par = par;
280 gpa->rgt = par;
281 par->par = gpa;
282 top->rgt = gpa->lft;
283 if (gpa->lft != NULL)
284 gpa->lft->par = top;
285 gpa->lft = top;
286 gpa->par = top->par;
287 top->par = gpa;
288
289 if (gpa->balance == 1) {
290 par->balance = 0;
291 top->balance = -1;
292 } else if (gpa->balance == 0) {
293 par->balance = 0;
294 top->balance = 0;
295 } else {
296 par->balance = 1;
297 top->balance = 0;
298 }
299 gpa->balance = 0;
300 *dpc = gpa;
301 }
302 } else {
303 /*
304 * Balance is not broken, insertion is finised.
305 */
306 return;
307 }
308
309}
310
311/** Repair the tree after reparenting node u.
312 *
313 * If node u has no parent, mark it as the root of the whole tree. Otherwise
314 * node v represents stale address of one of the children of node u's parent.
315 * Replace v with w as node u parent's child (for most uses, u and w will be the
316 * same).
317 *
318 * @param t AVL tree.
319 * @param u Node whose new parent has a stale child pointer.
320 * @param v Stale child of node u's new parent.
321 * @param w New child of node u's new parent.
322 * @param dir If not NULL, address of the variable where to store information
323 * about whether w replaced v in the left or the right subtree of
324 * u's new parent.
325 * @param ro Read only operation; do not modify any tree pointers. This is
326 * useful for tracking direction via the dir pointer.
327 *
328 * @return Zero if w became the new root of the tree, otherwise return
329 * non-zero.
330 */
331static int
332repair(avltree_t *t, avltree_node_t *u, avltree_node_t *v, avltree_node_t *w,
333 int *dir, int ro)
334{
335 if (u->par == NULL) {
336 if (!ro)
337 t->root = w;
338 return 0;
339 } else {
340 if (u->par->lft == v) {
341 if (!ro)
342 u->par->lft = w;
343 if (dir)
344 *dir = LEFT;
345 } else {
346 ASSERT(u->par->rgt == v);
347 if (!ro)
348 u->par->rgt = w;
349 if (dir)
350 *dir = RIGHT;
351 }
352 }
353 return 1;
354}
355
356#define REBALANCE(DIR1, DIR2, SIGN) \
357 if (cur->balance == -1 * SIGN) { \
358 par->balance = 0; \
359 gpa->balance = 1 * SIGN; \
360 if (gpa->DIR1) \
361 gpa->DIR1->par = gpa; \
362 par->DIR2->par = par; \
363 } else if (cur->balance == 0) { \
364 par->balance = 0; \
365 gpa->balance = 0; \
366 if (gpa->DIR1) \
367 gpa->DIR1->par = gpa; \
368 if (par->DIR2) \
369 par->DIR2->par = par; \
370 } else { \
371 par->balance = -1 * SIGN; \
372 gpa->balance = 0; \
373 if (par->DIR2) \
374 par->DIR2->par = par; \
375 gpa->DIR1->par = gpa; \
376 } \
377 cur->balance = 0;
378
379#define REBALANCE_LR() REBALANCE(lft, rgt, 1)
380#define REBALANCE_RL() REBALANCE(rgt, lft, -1)
381
382/** Delete a node from the AVL tree.
383 *
384 * Because multiple identical keys are allowed, the parent pointers are
385 * essential during deletion.
386 *
387 * @param t AVL tree structure.
388 * @param node Address of the node which will be deleted.
389 */
390void avltree_delete(avltree_t *t, avltree_node_t *node)
391{
392 avltree_node_t *cur;
393 avltree_node_t *par;
394 avltree_node_t *gpa;
395 int dir;
396
397 ASSERT(t);
398 ASSERT(node);
399
400 if (node->lft == NULL) {
401 if (node->rgt) {
402 /*
403 * Replace the node with its only right son.
404 *
405 * Balance of the right son will be repaired in the
406 * balancing cycle.
407 */
408 cur = node->rgt;
409 cur->par = node->par;
410 gpa = cur;
411 dir = RIGHT;
412 cur->balance = node->balance;
413 } else {
414 if (node->par == NULL) {
415 /*
416 * The tree has only one node - it will become
417 * an empty tree and the balancing can end.
418 */
419 t->root = NULL;
420 return;
421 }
422 /*
423 * The node has no child, it will be deleted with no
424 * substitution.
425 */
426 gpa = node->par;
427 cur = NULL;
428 dir = (gpa->lft == node) ? LEFT: RIGHT;
429 }
430 } else {
431 /*
432 * The node has the left son. Find a node with the smallest key
433 * in the left subtree and replace the deleted node with that
434 * node.
435 */
436 for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
437 ;
438
439 if (cur != node->lft) {
440 /*
441 * The rightmost node of the deleted node's left subtree
442 * was found. Replace the deleted node with this node.
443 * Cutting off of the found node has two cases that
444 * depend on its left son.
445 */
446 if (cur->lft) {
447 /*
448 * The found node has a left son.
449 */
450 gpa = cur->lft;
451 gpa->par = cur->par;
452 dir = LEFT;
453 gpa->balance = cur->balance;
454 } else {
455 dir = RIGHT;
456 gpa = cur->par;
457 }
458 cur->par->rgt = cur->lft;
459 cur->lft = node->lft;
460 cur->lft->par = cur;
461 } else {
462 /*
463 * The left son of the node hasn't got a right son. The
464 * left son will take the deleted node's place.
465 */
466 dir = LEFT;
467 gpa = cur;
468 }
469 if (node->rgt)
470 node->rgt->par = cur;
471 cur->rgt = node->rgt;
472 cur->balance = node->balance;
473 cur->par = node->par;
474 }
475
476 /*
477 * Repair the parent node's pointer which pointed previously to the
478 * deleted node.
479 */
480 (void) repair(t, node, node, cur, NULL, false);
481
482 /*
483 * Repair cycle which repairs balances of nodes on the way from from the
484 * cut-off node up to the root.
485 */
486 for (;;) {
487 if (dir == LEFT) {
488 /*
489 * Deletion was made in the left subtree.
490 */
491 gpa->balance++;
492 if (gpa->balance == 1) {
493 /*
494 * Stop balancing, the tree is balanced.
495 */
496 break;
497 } else if (gpa->balance == 2) {
498 /*
499 * Bad balance, heights of left and right
500 * subtrees differ more than by one.
501 */
502 par = gpa->rgt;
503
504 if (par->balance == -1) {
505 /*
506 * RL rotation.
507 */
508
509 cur = par->lft;
510 par->lft = cur->rgt;
511 cur->rgt = par;
512 gpa->rgt = cur->lft;
513 cur->lft = gpa;
514
515 /*
516 * Repair balances and paternity of
517 * children, depending on the balance
518 * factor of the grand child (cur).
519 */
520 REBALANCE_RL();
521
522 /*
523 * Repair paternity.
524 */
525 cur->par = gpa->par;
526 gpa->par = cur;
527 par->par = cur;
528
529 if (!repair(t, cur, gpa, cur, &dir,
530 false))
531 break;
532 gpa = cur->par;
533 } else {
534 /*
535 * RR rotation.
536 */
537
538 gpa->rgt = par->lft;
539 if (par->lft)
540 par->lft->par = gpa;
541 par->lft = gpa;
542
543 /*
544 * Repair paternity.
545 */
546 par->par = gpa->par;
547 gpa->par = par;
548
549 if (par->balance == 0) {
550 /*
551 * The right child of the
552 * balanced node is balanced,
553 * after RR rotation is done,
554 * the whole tree will be
555 * balanced.
556 */
557 par->balance = -1;
558 gpa->balance = 1;
559
560 (void) repair(t, par, gpa, par,
561 NULL, false);
562 break;
563 } else {
564 par->balance = 0;
565 gpa->balance = 0;
566 if (!repair(t, par, gpa, par,
567 &dir, false))
568 break;
569 }
570 gpa = par->par;
571 }
572 } else {
573 /*
574 * Repair the pointer which pointed to the
575 * balanced node. If it was root then balancing
576 * is finished else continue with the next
577 * iteration (parent node).
578 */
579 if (!repair(t, gpa, gpa, NULL, &dir, true))
580 break;
581 gpa = gpa->par;
582 }
583 } else {
584 /*
585 * Deletion was made in the right subtree.
586 */
587 gpa->balance--;
588 if (gpa->balance == -1) {
589 /*
590 * Stop balancing, the tree is balanced.
591 */
592 break;
593 } else if (gpa->balance == -2) {
594 /*
595 * Bad balance, heights of left and right
596 * subtrees differ more than by one.
597 */
598 par = gpa->lft;
599
600 if (par->balance == 1) {
601 /*
602 * LR rotation.
603 */
604
605 cur = par->rgt;
606 par->rgt = cur->lft;
607 cur->lft = par;
608 gpa->lft = cur->rgt;
609 cur->rgt = gpa;
610
611 /*
612 * Repair balances and paternity of
613 * children, depending on the balance
614 * factor of the grand child (cur).
615 */
616 REBALANCE_LR();
617
618 /*
619 * Repair paternity.
620 */
621 cur->par = gpa->par;
622 gpa->par = cur;
623 par->par = cur;
624
625 if (!repair(t, cur, gpa, cur, &dir,
626 false))
627 break;
628 gpa = cur->par;
629 } else {
630 /*
631 * LL rotation.
632 */
633
634 gpa->lft = par->rgt;
635 if (par->rgt)
636 par->rgt->par = gpa;
637 par->rgt = gpa;
638 /*
639 * Repair paternity.
640 */
641 par->par = gpa->par;
642 gpa->par = par;
643
644 if (par->balance == 0) {
645 /*
646 * The left child of the
647 * balanced node is balanced,
648 * after LL rotation is done,
649 * the whole tree will be
650 * balanced.
651 */
652 par->balance = 1;
653 gpa->balance = -1;
654
655 (void) repair(t, par, gpa, par,
656 NULL, false);
657 break;
658 } else {
659 par->balance = 0;
660 gpa->balance = 0;
661
662 if (!repair(t, par, gpa, par,
663 &dir, false))
664 break;
665 }
666 gpa = par->par;
667 }
668 } else {
669 /*
670 * Repair the pointer which pointed to the
671 * balanced node. If it was root then balancing
672 * is finished. Otherwise continue with the next
673 * iteration (parent node).
674 */
675 if (!repair(t, gpa, gpa, NULL, &dir, true))
676 break;
677 gpa = gpa->par;
678 }
679 }
680 }
681}
682
683
684/** Delete a node with the smallest key from the AVL tree.
685 *
686 * @param t AVL tree structure.
687 */
688bool avltree_delete_min(avltree_t *t)
689{
690 avltree_node_t *node;
691
692 /*
693 * Start searching for the smallest key in the tree starting in the root
694 * node and continue in cycle to the leftmost node in the tree (which
695 * must have the smallest key).
696 */
697
698 node = t->root;
699 if (!node)
700 return false;
701
702 while (node->lft != NULL)
703 node = node->lft;
704
705 avltree_delete(t, node);
706
707 return true;
708}
709
710/** @}
711 */
712
Note: See TracBrowser for help on using the repository browser.