source: mainline/kernel/generic/src/adt/avl.c@ 9233e9d

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 9233e9d was 63e27ef, checked in by Jiri Svoboda <jiri@…>, 8 years ago

ASSERT → assert
  • Property mode set to 100644
File size: 16.1 KB
Line 
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 <assert.h>
54
55#define LEFT 0
56#define RIGHT 1
57
58/** Search for the first occurence of the given key in an AVL tree.
59 *
60 * @param t AVL tree.
61 * @param key Key to be searched.
62 *
63 * @return Pointer to a node or NULL if there is no such key.
64 */
65avltree_node_t *avltree_search(avltree_t *t, avltree_key_t key)
66{
67 avltree_node_t *p;
68
69 /*
70 * Iteratively descend to the leaf that can contain the searched key.
71 */
72 p = t->root;
73 while (p != NULL) {
74 if (p->key > key)
75 p = p->lft;
76 else if (p->key < key)
77 p = p->rgt;
78 else
79 return p;
80 }
81 return NULL;
82}
83
84
85/** Find the node with the smallest key in an AVL tree.
86 *
87 * @param t AVL tree.
88 *
89 * @return Pointer to a node or NULL if there is no node in the tree.
90 */
91avltree_node_t *avltree_find_min(avltree_t *t)
92{
93 avltree_node_t *p = t->root;
94
95 /*
96 * Check whether the tree is empty.
97 */
98 if (!p)
99 return NULL;
100
101 /*
102 * Iteratively descend to the leftmost leaf in the tree.
103 */
104 while (p->lft != NULL)
105 p = p->lft;
106
107 return p;
108}
109
110#define REBALANCE_INSERT_XX(DIR1, DIR2) \
111 top->DIR1 = par->DIR2; \
112 if (top->DIR1 != NULL) \
113 top->DIR1->par = top; \
114 par->par = top->par; \
115 top->par = par; \
116 par->DIR2 = top; \
117 par->balance = 0; \
118 top->balance = 0; \
119 *dpc = par;
120
121#define REBALANCE_INSERT_LL() REBALANCE_INSERT_XX(lft, rgt)
122#define REBALANCE_INSERT_RR() REBALANCE_INSERT_XX(rgt, lft)
123
124#define REBALANCE_INSERT_XY(DIR1, DIR2, SGN) \
125 gpa = par->DIR2; \
126 par->DIR2 = gpa->DIR1; \
127 if (gpa->DIR1 != NULL) \
128 gpa->DIR1->par = par; \
129 gpa->DIR1 = par; \
130 par->par = gpa; \
131 top->DIR1 = gpa->DIR2; \
132 if (gpa->DIR2 != NULL) \
133 gpa->DIR2->par = top; \
134 gpa->DIR2 = top; \
135 gpa->par = top->par; \
136 top->par = gpa; \
137 \
138 if (gpa->balance == -1 * SGN) { \
139 par->balance = 0; \
140 top->balance = 1 * SGN; \
141 } else if (gpa->balance == 0) { \
142 par->balance = 0; \
143 top->balance = 0; \
144 } else { \
145 par->balance = -1 * SGN; \
146 top->balance = 0; \
147 } \
148 gpa->balance = 0; \
149 *dpc = gpa;
150
151#define REBALANCE_INSERT_LR() REBALANCE_INSERT_XY(lft, rgt, 1)
152#define REBALANCE_INSERT_RL() REBALANCE_INSERT_XY(rgt, lft, -1)
153
154/** Insert new node into AVL tree.
155 *
156 * @param t AVL tree.
157 * @param newnode New node to be inserted.
158 */
159void avltree_insert(avltree_t *t, avltree_node_t *newnode)
160{
161 avltree_node_t *par;
162 avltree_node_t *gpa;
163 avltree_node_t *top;
164 avltree_node_t **dpc;
165 avltree_key_t key;
166
167 assert(t);
168 assert(newnode);
169
170 /*
171 * Creating absolute key.
172 */
173 key = newnode->key + t->base;
174
175 /*
176 * Iteratively descend to the leaf that can contain the new node.
177 * Last node with non-zero balance in the way to leaf is stored as top -
178 * it is a place of possible inbalance.
179 */
180 dpc = &t->root;
181 gpa = NULL;
182 top = t->root;
183 while ((par = (*dpc)) != NULL) {
184 if (par->balance != 0) {
185 top = par;
186 }
187 gpa = par;
188 dpc = par->key > key ? &par->lft: &par->rgt;
189 }
190
191 /*
192 * Initialize the new node.
193 */
194 newnode->key = key;
195 newnode->lft = NULL;
196 newnode->rgt = NULL;
197 newnode->par = gpa;
198 newnode->balance = 0;
199
200 /*
201 * Insert first node into the empty tree.
202 */
203 if (t->root == NULL) {
204 *dpc = newnode;
205 return;
206 }
207
208 /*
209 * Insert the new node into the previously found leaf position.
210 */
211 *dpc = newnode;
212
213 /*
214 * If the tree contains one node - end.
215 */
216 if (top == NULL)
217 return;
218
219 /*
220 * Store pointer of top's father which points to the node with
221 * potentially broken balance (top).
222 */
223 if (top->par == NULL) {
224 dpc = &t->root;
225 } else {
226 if (top->par->lft == top)
227 dpc = &top->par->lft;
228 else
229 dpc = &top->par->rgt;
230 }
231
232 /*
233 * Repair all balances on the way from top node to the newly inserted
234 * node.
235 */
236 par = top;
237 while (par != newnode) {
238 if (par->key > key) {
239 par->balance--;
240 par = par->lft;
241 } else {
242 par->balance++;
243 par = par->rgt;
244 }
245 }
246
247 /*
248 * To balance the tree, we must check and balance top node.
249 */
250 if (top->balance == -2) {
251 par = top->lft;
252 if (par->balance == -1) {
253 /*
254 * LL rotation.
255 */
256 REBALANCE_INSERT_LL();
257 } else {
258 /*
259 * LR rotation.
260 */
261 assert(par->balance == 1);
262
263 REBALANCE_INSERT_LR();
264 }
265 } else if (top->balance == 2) {
266 par = top->rgt;
267 if (par->balance == 1) {
268 /*
269 * RR rotation.
270 */
271 REBALANCE_INSERT_RR();
272 } else {
273 /*
274 * RL rotation.
275 */
276 assert(par->balance == -1);
277
278 REBALANCE_INSERT_RL();
279 }
280 } else {
281 /*
282 * Balance is not broken, insertion is finised.
283 */
284 return;
285 }
286
287}
288
289/** Repair the tree after reparenting node u.
290 *
291 * If node u has no parent, mark it as the root of the whole tree. Otherwise
292 * node v represents stale address of one of the children of node u's parent.
293 * Replace v with w as node u parent's child (for most uses, u and w will be the
294 * same).
295 *
296 * @param t AVL tree.
297 * @param u Node whose new parent has a stale child pointer.
298 * @param v Stale child of node u's new parent.
299 * @param w New child of node u's new parent.
300 * @param dir If not NULL, address of the variable where to store information
301 * about whether w replaced v in the left or the right subtree of
302 * u's new parent.
303 * @param ro Read only operation; do not modify any tree pointers. This is
304 * useful for tracking direction via the dir pointer.
305 *
306 * @return Zero if w became the new root of the tree, otherwise return
307 * non-zero.
308 */
309static int
310repair(avltree_t *t, avltree_node_t *u, avltree_node_t *v, avltree_node_t *w,
311 int *dir, int ro)
312{
313 if (u->par == NULL) {
314 if (!ro)
315 t->root = w;
316 return 0;
317 } else {
318 if (u->par->lft == v) {
319 if (!ro)
320 u->par->lft = w;
321 if (dir)
322 *dir = LEFT;
323 } else {
324 assert(u->par->rgt == v);
325 if (!ro)
326 u->par->rgt = w;
327 if (dir)
328 *dir = RIGHT;
329 }
330 }
331 return 1;
332}
333
334#define REBALANCE_DELETE(DIR1, DIR2, SIGN) \
335 if (cur->balance == -1 * SIGN) { \
336 par->balance = 0; \
337 gpa->balance = 1 * SIGN; \
338 if (gpa->DIR1) \
339 gpa->DIR1->par = gpa; \
340 par->DIR2->par = par; \
341 } else if (cur->balance == 0) { \
342 par->balance = 0; \
343 gpa->balance = 0; \
344 if (gpa->DIR1) \
345 gpa->DIR1->par = gpa; \
346 if (par->DIR2) \
347 par->DIR2->par = par; \
348 } else { \
349 par->balance = -1 * SIGN; \
350 gpa->balance = 0; \
351 if (par->DIR2) \
352 par->DIR2->par = par; \
353 gpa->DIR1->par = gpa; \
354 } \
355 cur->balance = 0;
356
357#define REBALANCE_DELETE_LR() REBALANCE_DELETE(lft, rgt, 1)
358#define REBALANCE_DELETE_RL() REBALANCE_DELETE(rgt, lft, -1)
359
360/** Delete a node from the AVL tree.
361 *
362 * Because multiple identical keys are allowed, the parent pointers are
363 * essential during deletion.
364 *
365 * @param t AVL tree structure.
366 * @param node Address of the node which will be deleted.
367 */
368void avltree_delete(avltree_t *t, avltree_node_t *node)
369{
370 avltree_node_t *cur;
371 avltree_node_t *par;
372 avltree_node_t *gpa;
373 int dir;
374
375 assert(t);
376 assert(node);
377
378 if (node->lft == NULL) {
379 if (node->rgt) {
380 /*
381 * Replace the node with its only right son.
382 *
383 * Balance of the right son will be repaired in the
384 * balancing cycle.
385 */
386 cur = node->rgt;
387 cur->par = node->par;
388 gpa = cur;
389 dir = RIGHT;
390 cur->balance = node->balance;
391 } else {
392 if (node->par == NULL) {
393 /*
394 * The tree has only one node - it will become
395 * an empty tree and the balancing can end.
396 */
397 t->root = NULL;
398 return;
399 }
400 /*
401 * The node has no child, it will be deleted with no
402 * substitution.
403 */
404 gpa = node->par;
405 cur = NULL;
406 dir = (gpa->lft == node) ? LEFT: RIGHT;
407 }
408 } else {
409 /*
410 * The node has the left son. Find a node with the smallest key
411 * in the left subtree and replace the deleted node with that
412 * node.
413 */
414 for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
415 ;
416
417 if (cur != node->lft) {
418 /*
419 * The rightmost node of the deleted node's left subtree
420 * was found. Replace the deleted node with this node.
421 * Cutting off of the found node has two cases that
422 * depend on its left son.
423 */
424 if (cur->lft) {
425 /*
426 * The found node has a left son.
427 */
428 gpa = cur->lft;
429 gpa->par = cur->par;
430 dir = LEFT;
431 gpa->balance = cur->balance;
432 } else {
433 dir = RIGHT;
434 gpa = cur->par;
435 }
436 cur->par->rgt = cur->lft;
437 cur->lft = node->lft;
438 cur->lft->par = cur;
439 } else {
440 /*
441 * The left son of the node hasn't got a right son. The
442 * left son will take the deleted node's place.
443 */
444 dir = LEFT;
445 gpa = cur;
446 }
447 if (node->rgt)
448 node->rgt->par = cur;
449 cur->rgt = node->rgt;
450 cur->balance = node->balance;
451 cur->par = node->par;
452 }
453
454 /*
455 * Repair the parent node's pointer which pointed previously to the
456 * deleted node.
457 */
458 (void) repair(t, node, node, cur, NULL, false);
459
460 /*
461 * Repair cycle which repairs balances of nodes on the way from from the
462 * cut-off node up to the root.
463 */
464 for (;;) {
465 if (dir == LEFT) {
466 /*
467 * Deletion was made in the left subtree.
468 */
469 gpa->balance++;
470 if (gpa->balance == 1) {
471 /*
472 * Stop balancing, the tree is balanced.
473 */
474 break;
475 } else if (gpa->balance == 2) {
476 /*
477 * Bad balance, heights of left and right
478 * subtrees differ more than by one.
479 */
480 par = gpa->rgt;
481
482 if (par->balance == -1) {
483 /*
484 * RL rotation.
485 */
486
487 cur = par->lft;
488 par->lft = cur->rgt;
489 cur->rgt = par;
490 gpa->rgt = cur->lft;
491 cur->lft = gpa;
492
493 /*
494 * Repair balances and paternity of
495 * children, depending on the balance
496 * factor of the grand child (cur).
497 */
498 REBALANCE_DELETE_RL();
499
500 /*
501 * Repair paternity.
502 */
503 cur->par = gpa->par;
504 gpa->par = cur;
505 par->par = cur;
506
507 if (!repair(t, cur, gpa, cur, &dir,
508 false))
509 break;
510 gpa = cur->par;
511 } else {
512 /*
513 * RR rotation.
514 */
515
516 gpa->rgt = par->lft;
517 if (par->lft)
518 par->lft->par = gpa;
519 par->lft = gpa;
520
521 /*
522 * Repair paternity.
523 */
524 par->par = gpa->par;
525 gpa->par = par;
526
527 if (par->balance == 0) {
528 /*
529 * The right child of the
530 * balanced node is balanced,
531 * after RR rotation is done,
532 * the whole tree will be
533 * balanced.
534 */
535 par->balance = -1;
536 gpa->balance = 1;
537
538 (void) repair(t, par, gpa, par,
539 NULL, false);
540 break;
541 } else {
542 par->balance = 0;
543 gpa->balance = 0;
544 if (!repair(t, par, gpa, par,
545 &dir, false))
546 break;
547 }
548 gpa = par->par;
549 }
550 } else {
551 /*
552 * Repair the pointer which pointed to the
553 * balanced node. If it was root then balancing
554 * is finished else continue with the next
555 * iteration (parent node).
556 */
557 if (!repair(t, gpa, gpa, NULL, &dir, true))
558 break;
559 gpa = gpa->par;
560 }
561 } else {
562 /*
563 * Deletion was made in the right subtree.
564 */
565 gpa->balance--;
566 if (gpa->balance == -1) {
567 /*
568 * Stop balancing, the tree is balanced.
569 */
570 break;
571 } else if (gpa->balance == -2) {
572 /*
573 * Bad balance, heights of left and right
574 * subtrees differ more than by one.
575 */
576 par = gpa->lft;
577
578 if (par->balance == 1) {
579 /*
580 * LR rotation.
581 */
582
583 cur = par->rgt;
584 par->rgt = cur->lft;
585 cur->lft = par;
586 gpa->lft = cur->rgt;
587 cur->rgt = gpa;
588
589 /*
590 * Repair balances and paternity of
591 * children, depending on the balance
592 * factor of the grand child (cur).
593 */
594 REBALANCE_DELETE_LR();
595
596 /*
597 * Repair paternity.
598 */
599 cur->par = gpa->par;
600 gpa->par = cur;
601 par->par = cur;
602
603 if (!repair(t, cur, gpa, cur, &dir,
604 false))
605 break;
606 gpa = cur->par;
607 } else {
608 /*
609 * LL rotation.
610 */
611
612 gpa->lft = par->rgt;
613 if (par->rgt)
614 par->rgt->par = gpa;
615 par->rgt = gpa;
616 /*
617 * Repair paternity.
618 */
619 par->par = gpa->par;
620 gpa->par = par;
621
622 if (par->balance == 0) {
623 /*
624 * The left child of the
625 * balanced node is balanced,
626 * after LL rotation is done,
627 * the whole tree will be
628 * balanced.
629 */
630 par->balance = 1;
631 gpa->balance = -1;
632
633 (void) repair(t, par, gpa, par,
634 NULL, false);
635 break;
636 } else {
637 par->balance = 0;
638 gpa->balance = 0;
639
640 if (!repair(t, par, gpa, par,
641 &dir, false))
642 break;
643 }
644 gpa = par->par;
645 }
646 } else {
647 /*
648 * Repair the pointer which pointed to the
649 * balanced node. If it was root then balancing
650 * is finished. Otherwise continue with the next
651 * iteration (parent node).
652 */
653 if (!repair(t, gpa, gpa, NULL, &dir, true))
654 break;
655 gpa = gpa->par;
656 }
657 }
658 }
659}
660
661
662/** Delete a node with the smallest key from the AVL tree.
663 *
664 * @param t AVL tree structure.
665 */
666bool avltree_delete_min(avltree_t *t)
667{
668 avltree_node_t *node;
669
670 /*
671 * Start searching for the smallest key in the tree starting in the root
672 * node and continue in cycle to the leftmost node in the tree (which
673 * must have the smallest key).
674 */
675
676 node = t->root;
677 if (!node)
678 return false;
679
680 while (node->lft != NULL)
681 node = node->lft;
682
683 avltree_delete(t, node);
684
685 return true;
686}
687
688/** Walk a subtree of an AVL tree in-order and apply a supplied walker on each
689 * visited node.
690 *
691 * @param node Node representing the root of an AVL subtree to be
692 * walked.
693 * @param walker Walker function that will be appliad on each visited
694 * node.
695 * @param arg Argument for the walker.
696 *
697 * @return Zero if the walk should stop or non-zero otherwise.
698 */
699static bool _avltree_walk(avltree_node_t *node, avltree_walker_t walker,
700 void *arg)
701{
702 if (node->lft) {
703 if (!_avltree_walk(node->lft, walker, arg))
704 return false;
705 }
706 if (!walker(node, arg))
707 return false;
708 if (node->rgt) {
709 if (!_avltree_walk(node->rgt, walker, arg))
710 return false;
711 }
712 return true;
713}
714
715/** Walk the AVL tree in-order and apply the walker function on each visited
716 * node.
717 *
718 * @param t AVL tree to be walked.
719 * @param walker Walker function that will be called on each visited
720 * node.
721 * @param arg Argument for the walker.
722 */
723void avltree_walk(avltree_t *t, avltree_walker_t walker, void *arg)
724{
725 if (t->root)
726 _avltree_walk(t->root, walker, arg);
727}
728
729/** @}
730 */
731
Note: See TracBrowser for help on using the repository browser.