?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Allow phone_alloc to not publish the capability
[helenos.git] / kernel / generic / src / adt / avl.c
blob75988d02c02b65c41505cb352ae7427a8ed625b3
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 */
65 avltree_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 */
91 avltree_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 */
159 void 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 */
309 static int
310 repair(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 */
368 void 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 cur = node->lft;
415 while (cur->rgt != NULL)
416 cur = cur->rgt;
417
418 if (cur != node->lft) {
419 /*
420 * The rightmost node of the deleted node's left subtree
421 * was found. Replace the deleted node with this node.
422 * Cutting off of the found node has two cases that
423 * depend on its left son.
424 */
425 if (cur->lft) {
426 /*
427 * The found node has a left son.
428 */
429 gpa = cur->lft;
430 gpa->par = cur->par;
431 dir = LEFT;
432 gpa->balance = cur->balance;
433 } else {
434 dir = RIGHT;
435 gpa = cur->par;
436 }
437 cur->par->rgt = cur->lft;
438 cur->lft = node->lft;
439 cur->lft->par = cur;
440 } else {
441 /*
442 * The left son of the node hasn't got a right son. The
443 * left son will take the deleted node's place.
444 */
445 dir = LEFT;
446 gpa = cur;
447 }
448 if (node->rgt)
449 node->rgt->par = cur;
450 cur->rgt = node->rgt;
451 cur->balance = node->balance;
452 cur->par = node->par;
453 }
454
455 /*
456 * Repair the parent node's pointer which pointed previously to the
457 * deleted node.
458 */
459 (void) repair(t, node, node, cur, NULL, false);
460
461 /*
462 * Repair cycle which repairs balances of nodes on the way from from the
463 * cut-off node up to the root.
464 */
465 while (true) {
466 if (dir == LEFT) {
467 /*
468 * Deletion was made in the left subtree.
469 */
470 gpa->balance++;
471 if (gpa->balance == 1) {
472 /*
473 * Stop balancing, the tree is balanced.
474 */
475 break;
476 } else if (gpa->balance == 2) {
477 /*
478 * Bad balance, heights of left and right
479 * subtrees differ more than by one.
480 */
481 par = gpa->rgt;
482
483 if (par->balance == -1) {
484 /*
485 * RL rotation.
486 */
487
488 cur = par->lft;
489 par->lft = cur->rgt;
490 cur->rgt = par;
491 gpa->rgt = cur->lft;
492 cur->lft = gpa;
493
494 /*
495 * Repair balances and paternity of
496 * children, depending on the balance
497 * factor of the grand child (cur).
498 */
499 REBALANCE_DELETE_RL();
500
501 /*
502 * Repair paternity.
503 */
504 cur->par = gpa->par;
505 gpa->par = cur;
506 par->par = cur;
507
508 if (!repair(t, cur, gpa, cur, &dir,
509 false))
510 break;
511 gpa = cur->par;
512 } else {
513 /*
514 * RR rotation.
515 */
516
517 gpa->rgt = par->lft;
518 if (par->lft)
519 par->lft->par = gpa;
520 par->lft = gpa;
521
522 /*
523 * Repair paternity.
524 */
525 par->par = gpa->par;
526 gpa->par = par;
527
528 if (par->balance == 0) {
529 /*
530 * The right child of the
531 * balanced node is balanced,
532 * after RR rotation is done,
533 * the whole tree will be
534 * balanced.
535 */
536 par->balance = -1;
537 gpa->balance = 1;
538
539 (void) repair(t, par, gpa, par,
540 NULL, false);
541 break;
542 } else {
543 par->balance = 0;
544 gpa->balance = 0;
545 if (!repair(t, par, gpa, par,
546 &dir, false))
547 break;
548 }
549 gpa = par->par;
550 }
551 } else {
552 /*
553 * Repair the pointer which pointed to the
554 * balanced node. If it was root then balancing
555 * is finished else continue with the next
556 * iteration (parent node).
557 */
558 if (!repair(t, gpa, gpa, NULL, &dir, true))
559 break;
560 gpa = gpa->par;
561 }
562 } else {
563 /*
564 * Deletion was made in the right subtree.
565 */
566 gpa->balance--;
567 if (gpa->balance == -1) {
568 /*
569 * Stop balancing, the tree is balanced.
570 */
571 break;
572 } else if (gpa->balance == -2) {
573 /*
574 * Bad balance, heights of left and right
575 * subtrees differ more than by one.
576 */
577 par = gpa->lft;
578
579 if (par->balance == 1) {
580 /*
581 * LR rotation.
582 */
583
584 cur = par->rgt;
585 par->rgt = cur->lft;
586 cur->lft = par;
587 gpa->lft = cur->rgt;
588 cur->rgt = gpa;
589
590 /*
591 * Repair balances and paternity of
592 * children, depending on the balance
593 * factor of the grand child (cur).
594 */
595 REBALANCE_DELETE_LR();
596
597 /*
598 * Repair paternity.
599 */
600 cur->par = gpa->par;
601 gpa->par = cur;
602 par->par = cur;
603
604 if (!repair(t, cur, gpa, cur, &dir,
605 false))
606 break;
607 gpa = cur->par;
608 } else {
609 /*
610 * LL rotation.
611 */
612
613 gpa->lft = par->rgt;
614 if (par->rgt)
615 par->rgt->par = gpa;
616 par->rgt = gpa;
617 /*
618 * Repair paternity.
619 */
620 par->par = gpa->par;
621 gpa->par = par;
622
623 if (par->balance == 0) {
624 /*
625 * The left child of the
626 * balanced node is balanced,
627 * after LL rotation is done,
628 * the whole tree will be
629 * balanced.
630 */
631 par->balance = 1;
632 gpa->balance = -1;
633
634 (void) repair(t, par, gpa, par,
635 NULL, false);
636 break;
637 } else {
638 par->balance = 0;
639 gpa->balance = 0;
640
641 if (!repair(t, par, gpa, par,
642 &dir, false))
643 break;
644 }
645 gpa = par->par;
646 }
647 } else {
648 /*
649 * Repair the pointer which pointed to the
650 * balanced node. If it was root then balancing
651 * is finished. Otherwise continue with the next
652 * iteration (parent node).
653 */
654 if (!repair(t, gpa, gpa, NULL, &dir, true))
655 break;
656 gpa = gpa->par;
657 }
658 }
659 }
660 }
661
662
663 /** Delete a node with the smallest key from the AVL tree.
664 *
665 * @param t AVL tree structure.
666 */
667 bool avltree_delete_min(avltree_t *t)
668 {
669 avltree_node_t *node;
670
671 /*
672 * Start searching for the smallest key in the tree starting in the root
673 * node and continue in cycle to the leftmost node in the tree (which
674 * must have the smallest key).
675 */
676
677 node = t->root;
678 if (!node)
679 return false;
680
681 while (node->lft != NULL)
682 node = node->lft;
683
684 avltree_delete(t, node);
685
686 return true;
687 }
688
689 /** Walk a subtree of an AVL tree in-order and apply a supplied walker on each
690 * visited node.
691 *
692 * @param node Node representing the root of an AVL subtree to be
693 * walked.
694 * @param walker Walker function that will be appliad on each visited
695 * node.
696 * @param arg Argument for the walker.
697 *
698 * @return Zero if the walk should stop or non-zero otherwise.
699 */
700 static bool _avltree_walk(avltree_node_t *node, avltree_walker_t walker,
701 void *arg)
702 {
703 if (node->lft) {
704 if (!_avltree_walk(node->lft, walker, arg))
705 return false;
706 }
707 if (!walker(node, arg))
708 return false;
709 if (node->rgt) {
710 if (!_avltree_walk(node->rgt, walker, arg))
711 return false;
712 }
713 return true;
714 }
715
716 /** Walk the AVL tree in-order and apply the walker function on each visited
717 * node.
718 *
719 * @param t AVL tree to be walked.
720 * @param walker Walker function that will be called on each visited
721 * node.
722 * @param arg Argument for the walker.
723 */
724 void avltree_walk(avltree_t *t, avltree_walker_t walker, void *arg)
725 {
726 if (t->root)
727 _avltree_walk(t->root, walker, arg);
728 }
729
730 /** @}
731 */
732
A portable microkernel-based multiserver operating system written from scratch.