source: mainline/kernel/generic/src/adt/avl.c@ 30785f1

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

Disambiguate doxygroup generic*
  • Property mode set to 100644
File size: 16.0 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 kernel_generic_adt
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/** Find the node with the smallest key in an AVL tree.
85 *
86 * @param t AVL tree.
87 *
88 * @return Pointer to a node or NULL if there is no node in the tree.
89 */
90avltree_node_t *avltree_find_min(avltree_t *t)
91{
92 avltree_node_t *p = t->root;
93
94 /*
95 * Check whether the tree is empty.
96 */
97 if (!p)
98 return NULL;
99
100 /*
101 * Iteratively descend to the leftmost leaf in the tree.
102 */
103 while (p->lft != NULL)
104 p = p->lft;
105
106 return p;
107}
108
109#define REBALANCE_INSERT_XX(DIR1, DIR2) \
110 top->DIR1 = par->DIR2; \
111 if (top->DIR1 != NULL) \
112 top->DIR1->par = top; \
113 par->par = top->par; \
114 top->par = par; \
115 par->DIR2 = top; \
116 par->balance = 0; \
117 top->balance = 0; \
118 *dpc = par;
119
120#define REBALANCE_INSERT_LL() REBALANCE_INSERT_XX(lft, rgt)
121#define REBALANCE_INSERT_RR() REBALANCE_INSERT_XX(rgt, lft)
122
123#define REBALANCE_INSERT_XY(DIR1, DIR2, SGN) \
124 gpa = par->DIR2; \
125 par->DIR2 = gpa->DIR1; \
126 if (gpa->DIR1 != NULL) \
127 gpa->DIR1->par = par; \
128 gpa->DIR1 = par; \
129 par->par = gpa; \
130 top->DIR1 = gpa->DIR2; \
131 if (gpa->DIR2 != NULL) \
132 gpa->DIR2->par = top; \
133 gpa->DIR2 = top; \
134 gpa->par = top->par; \
135 top->par = gpa; \
136 \
137 if (gpa->balance == -1 * SGN) { \
138 par->balance = 0; \
139 top->balance = 1 * SGN; \
140 } else if (gpa->balance == 0) { \
141 par->balance = 0; \
142 top->balance = 0; \
143 } else { \
144 par->balance = -1 * SGN; \
145 top->balance = 0; \
146 } \
147 gpa->balance = 0; \
148 *dpc = gpa;
149
150#define REBALANCE_INSERT_LR() REBALANCE_INSERT_XY(lft, rgt, 1)
151#define REBALANCE_INSERT_RL() REBALANCE_INSERT_XY(rgt, lft, -1)
152
153/** Insert new node into AVL tree.
154 *
155 * @param t AVL tree.
156 * @param newnode New node to be inserted.
157 */
158void avltree_insert(avltree_t *t, avltree_node_t *newnode)
159{
160 avltree_node_t *par;
161 avltree_node_t *gpa;
162 avltree_node_t *top;
163 avltree_node_t **dpc;
164 avltree_key_t key;
165
166 assert(t);
167 assert(newnode);
168
169 /*
170 * Creating absolute key.
171 */
172 key = newnode->key + t->base;
173
174 /*
175 * Iteratively descend to the leaf that can contain the new node.
176 * Last node with non-zero balance in the way to leaf is stored as top -
177 * it is a place of possible inbalance.
178 */
179 dpc = &t->root;
180 gpa = NULL;
181 top = t->root;
182 while ((par = (*dpc)) != NULL) {
183 if (par->balance != 0) {
184 top = par;
185 }
186 gpa = par;
187 dpc = par->key > key ? &par->lft : &par->rgt;
188 }
189
190 /*
191 * Initialize the new node.
192 */
193 newnode->key = key;
194 newnode->lft = NULL;
195 newnode->rgt = NULL;
196 newnode->par = gpa;
197 newnode->balance = 0;
198
199 /*
200 * Insert first node into the empty tree.
201 */
202 if (t->root == NULL) {
203 *dpc = newnode;
204 return;
205 }
206
207 /*
208 * Insert the new node into the previously found leaf position.
209 */
210 *dpc = newnode;
211
212 /*
213 * If the tree contains one node - end.
214 */
215 if (top == NULL)
216 return;
217
218 /*
219 * Store pointer of top's father which points to the node with
220 * potentially broken balance (top).
221 */
222 if (top->par == NULL) {
223 dpc = &t->root;
224 } else {
225 if (top->par->lft == top)
226 dpc = &top->par->lft;
227 else
228 dpc = &top->par->rgt;
229 }
230
231 /*
232 * Repair all balances on the way from top node to the newly inserted
233 * node.
234 */
235 par = top;
236 while (par != newnode) {
237 if (par->key > key) {
238 par->balance--;
239 par = par->lft;
240 } else {
241 par->balance++;
242 par = par->rgt;
243 }
244 }
245
246 /*
247 * To balance the tree, we must check and balance top node.
248 */
249 if (top->balance == -2) {
250 par = top->lft;
251 if (par->balance == -1) {
252 /*
253 * LL rotation.
254 */
255 REBALANCE_INSERT_LL();
256 } else {
257 /*
258 * LR rotation.
259 */
260 assert(par->balance == 1);
261
262 REBALANCE_INSERT_LR();
263 }
264 } else if (top->balance == 2) {
265 par = top->rgt;
266 if (par->balance == 1) {
267 /*
268 * RR rotation.
269 */
270 REBALANCE_INSERT_RR();
271 } else {
272 /*
273 * RL rotation.
274 */
275 assert(par->balance == -1);
276
277 REBALANCE_INSERT_RL();
278 }
279 } else {
280 /*
281 * Balance is not broken, insertion is finised.
282 */
283 return;
284 }
285
286}
287
288/** Repair the tree after reparenting node u.
289 *
290 * If node u has no parent, mark it as the root of the whole tree. Otherwise
291 * node v represents stale address of one of the children of node u's parent.
292 * Replace v with w as node u parent's child (for most uses, u and w will be the
293 * same).
294 *
295 * @param t AVL tree.
296 * @param u Node whose new parent has a stale child pointer.
297 * @param v Stale child of node u's new parent.
298 * @param w New child of node u's new parent.
299 * @param dir If not NULL, address of the variable where to store information
300 * about whether w replaced v in the left or the right subtree of
301 * u's new parent.
302 * @param ro Read only operation; do not modify any tree pointers. This is
303 * useful for tracking direction via the dir pointer.
304 *
305 * @return Zero if w became the new root of the tree, otherwise return
306 * non-zero.
307 */
308static int
309repair(avltree_t *t, avltree_node_t *u, avltree_node_t *v, avltree_node_t *w,
310 int *dir, int ro)
311{
312 if (u->par == NULL) {
313 if (!ro)
314 t->root = w;
315 return 0;
316 } else {
317 if (u->par->lft == v) {
318 if (!ro)
319 u->par->lft = w;
320 if (dir)
321 *dir = LEFT;
322 } else {
323 assert(u->par->rgt == v);
324 if (!ro)
325 u->par->rgt = w;
326 if (dir)
327 *dir = RIGHT;
328 }
329 }
330 return 1;
331}
332
333#define REBALANCE_DELETE(DIR1, DIR2, SIGN) \
334 if (cur->balance == -1 * SIGN) { \
335 par->balance = 0; \
336 gpa->balance = 1 * SIGN; \
337 if (gpa->DIR1) \
338 gpa->DIR1->par = gpa; \
339 par->DIR2->par = par; \
340 } else if (cur->balance == 0) { \
341 par->balance = 0; \
342 gpa->balance = 0; \
343 if (gpa->DIR1) \
344 gpa->DIR1->par = gpa; \
345 if (par->DIR2) \
346 par->DIR2->par = par; \
347 } else { \
348 par->balance = -1 * SIGN; \
349 gpa->balance = 0; \
350 if (par->DIR2) \
351 par->DIR2->par = par; \
352 gpa->DIR1->par = gpa; \
353 } \
354 cur->balance = 0;
355
356#define REBALANCE_DELETE_LR() REBALANCE_DELETE(lft, rgt, 1)
357#define REBALANCE_DELETE_RL() REBALANCE_DELETE(rgt, lft, -1)
358
359/** Delete a node from the AVL tree.
360 *
361 * Because multiple identical keys are allowed, the parent pointers are
362 * essential during deletion.
363 *
364 * @param t AVL tree structure.
365 * @param node Address of the node which will be deleted.
366 */
367void avltree_delete(avltree_t *t, avltree_node_t *node)
368{
369 avltree_node_t *cur;
370 avltree_node_t *par;
371 avltree_node_t *gpa;
372 int dir;
373
374 assert(t);
375 assert(node);
376
377 if (node->lft == NULL) {
378 if (node->rgt) {
379 /*
380 * Replace the node with its only right son.
381 *
382 * Balance of the right son will be repaired in the
383 * balancing cycle.
384 */
385 cur = node->rgt;
386 cur->par = node->par;
387 gpa = cur;
388 dir = RIGHT;
389 cur->balance = node->balance;
390 } else {
391 if (node->par == NULL) {
392 /*
393 * The tree has only one node - it will become
394 * an empty tree and the balancing can end.
395 */
396 t->root = NULL;
397 return;
398 }
399 /*
400 * The node has no child, it will be deleted with no
401 * substitution.
402 */
403 gpa = node->par;
404 cur = NULL;
405 dir = (gpa->lft == node) ? LEFT : RIGHT;
406 }
407 } else {
408 /*
409 * The node has the left son. Find a node with the smallest key
410 * in the left subtree and replace the deleted node with that
411 * node.
412 */
413 cur = node->lft;
414 while (cur->rgt != NULL)
415 cur = cur->rgt;
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 while (true) {
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/** Delete a node with the smallest key from the AVL tree.
662 *
663 * @param t AVL tree structure.
664 */
665bool avltree_delete_min(avltree_t *t)
666{
667 avltree_node_t *node;
668
669 /*
670 * Start searching for the smallest key in the tree starting in the root
671 * node and continue in cycle to the leftmost node in the tree (which
672 * must have the smallest key).
673 */
674
675 node = t->root;
676 if (!node)
677 return false;
678
679 while (node->lft != NULL)
680 node = node->lft;
681
682 avltree_delete(t, node);
683
684 return true;
685}
686
687/** Walk a subtree of an AVL tree in-order and apply a supplied walker on each
688 * visited node.
689 *
690 * @param node Node representing the root of an AVL subtree to be
691 * walked.
692 * @param walker Walker function that will be appliad on each visited
693 * node.
694 * @param arg Argument for the walker.
695 *
696 * @return Zero if the walk should stop or non-zero otherwise.
697 */
698static bool _avltree_walk(avltree_node_t *node, avltree_walker_t walker,
699 void *arg)
700{
701 if (node->lft) {
702 if (!_avltree_walk(node->lft, walker, arg))
703 return false;
704 }
705 if (!walker(node, arg))
706 return false;
707 if (node->rgt) {
708 if (!_avltree_walk(node->rgt, walker, arg))
709 return false;
710 }
711 return true;
712}
713
714/** Walk the AVL tree in-order and apply the walker function on each visited
715 * node.
716 *
717 * @param t AVL tree to be walked.
718 * @param walker Walker function that will be called on each visited
719 * node.
720 * @param arg Argument for the walker.
721 */
722void avltree_walk(avltree_t *t, avltree_walker_t walker, void *arg)
723{
724 if (t->root)
725 _avltree_walk(t->root, walker, arg);
726}
727
728/** @}
729 */
Note: See TracBrowser for help on using the repository browser.