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

Last change on this file since bbf38ad was a35b458, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 8 years ago

style: Remove trailing whitespace on _all_ lines, including empty ones, for particular file types.

Command used: tools/srepl '\s\+$' '' -- *.c *.h *.py *.sh *.s *.S *.ag

Currently, whitespace on empty lines is very inconsistent.
There are two basic choices: Either remove the whitespace, or keep empty lines
indented to the level of surrounding code. The former is AFAICT more common,
and also much easier to do automatically.

Alternatively, we could write script for automatic indentation, and use that
instead. However, if such a script exists, it's possible to use the indented
style locally, by having the editor apply relevant conversions on load/save,
without affecting remote repository. IMO, it makes more sense to adopt
the simpler rule.
  • 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 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.