blobmsg_example: fix output
[project/libubox.git] / avl.c
1 /*
2 * PacketBB handler library (see RFC 5444)
3 * Copyright (c) 2010 Henning Rogge <hrogge@googlemail.com>
4 * Original OLSRd implementation by Hannes Gredler <hannes@gredler.at>
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
16 * distribution.
17 * * Neither the name of olsr.org, olsrd nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
33 *
34 * Visit http://www.olsr.org/git for more information.
35 *
36 * If you find this software useful feel free to make a donation
37 * to the project. For more information see the website or contact
38 * the copyright holders.
39 */
40
41 #include <stdbool.h>
42 #include <stddef.h>
43 #include <stdint.h>
44 #include <time.h>
45 #include <string.h>
46
47 #include "avl.h"
48 #include "list.h"
49
50 /**
51 * internal type save inline function to calculate the maximum of
52 * to integers without macro implementation.
53 *
54 * @param x first parameter of maximum function
55 * @param y second parameter of maximum function
56 * @return largest integer of both parameters
57 */
58 static inline int avl_max(int x, int y) {
59 return x > y ? x : y;
60 }
61
62 /**
63 * internal type save inline function to calculate the minimum of
64 * to integers without macro implementation.
65 *
66 * @param x first parameter of minimum function
67 * @param y second parameter of minimum function
68 * @return smallest integer of both parameters
69 */
70 static inline int avl_min(int x, int y) {
71 return x < y ? x : y;
72 }
73
74 static struct avl_node *
75 avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *ptr, int *cmp_result);
76 static void avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
77 static void avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
78 static void post_insert(struct avl_tree *tree, struct avl_node *node);
79 static void avl_delete_worker(struct avl_tree *tree, struct avl_node *node);
80 static void avl_remove(struct avl_tree *tree, struct avl_node *node);
81
82 /**
83 * Initialize a new avl_tree struct
84 * @param tree pointer to avl-tree
85 * @param comp pointer to comparator for the tree
86 * @param allow_dups true if the tree allows multiple
87 * elements with the same
88 * @param ptr custom parameter for comparator
89 */
90 void
91 avl_init(struct avl_tree *tree, avl_tree_comp comp, bool allow_dups, void *ptr)
92 {
93 INIT_LIST_HEAD(&tree->list_head);
94 tree->root = NULL;
95 tree->count = 0;
96 tree->comp = comp;
97 tree->allow_dups = allow_dups;
98 tree->cmp_ptr = ptr;
99 }
100
101 static inline struct avl_node *avl_next(struct avl_node *node)
102 {
103 return list_entry(node->list.next, struct avl_node, list);
104 }
105
106 /**
107 * Finds a node in an avl-tree with a certain key
108 * @param tree pointer to avl-tree
109 * @param key pointer to key
110 * @return pointer to avl-node with key, NULL if no node with
111 * this key exists.
112 */
113 struct avl_node *
114 avl_find(const struct avl_tree *tree, const void *key)
115 {
116 struct avl_node *node;
117 int diff;
118
119 if (tree->root == NULL)
120 return NULL;
121
122 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
123
124 return diff == 0 ? node : NULL;
125 }
126
127 /**
128 * Finds the last node in an avl-tree with a key less or equal
129 * than the specified key
130 * @param tree pointer to avl-tree
131 * @param key pointer to specified key
132 * @return pointer to avl-node, NULL if no node with
133 * key less or equal specified key exists.
134 */
135 struct avl_node *
136 avl_find_lessequal(const struct avl_tree *tree, const void *key) {
137 struct avl_node *node, *next;
138 int diff;
139
140 if (tree->root == NULL)
141 return NULL;
142
143 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
144
145 /* go left as long as key<node.key */
146 while (diff < 0) {
147 if (list_is_first(&node->list, &tree->list_head)) {
148 return NULL;
149 }
150
151 node = (struct avl_node *)node->list.prev;
152 diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
153 }
154
155 /* go right as long as key>=next_node.key */
156 next = node;
157 while (diff >= 0) {
158 node = next;
159 if (list_is_last(&node->list, &tree->list_head)) {
160 break;
161 }
162
163 next = (struct avl_node *)node->list.next;
164 diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
165 }
166 return node;
167 }
168
169 /**
170 * Finds the first node in an avl-tree with a key greater or equal
171 * than the specified key
172 * @param tree pointer to avl-tree
173 * @param key pointer to specified key
174 * @return pointer to avl-node, NULL if no node with
175 * key greater or equal specified key exists.
176 */
177 struct avl_node *
178 avl_find_greaterequal(const struct avl_tree *tree, const void *key) {
179 struct avl_node *node, *next;
180 int diff;
181
182 if (tree->root == NULL)
183 return NULL;
184
185 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
186
187 /* go right as long as key>node.key */
188 while (diff > 0) {
189 if (list_is_last(&node->list, &tree->list_head)) {
190 return NULL;
191 }
192
193 node = (struct avl_node *)node->list.next;
194 diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
195 }
196
197 /* go left as long as key<=next_node.key */
198 next = node;
199 while (diff <= 0) {
200 node = next;
201 if (list_is_first(&node->list, &tree->list_head)) {
202 break;
203 }
204
205 next = (struct avl_node *)node->list.prev;
206 diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
207 }
208 return node;
209 }
210
211 /**
212 * Inserts an avl_node into a tree
213 * @param tree pointer to tree
214 * @param new pointer to node
215 * @return 0 if node was inserted successfully, -1 if it was not inserted
216 * because of a key collision
217 */
218 int
219 avl_insert(struct avl_tree *tree, struct avl_node *new)
220 {
221 struct avl_node *node, *next, *last;
222 int diff;
223
224 new->parent = NULL;
225
226 new->left = NULL;
227 new->right = NULL;
228
229 new->balance = 0;
230 new->leader = true;
231
232 if (tree->root == NULL) {
233 list_add(&new->list, &tree->list_head);
234 tree->root = new;
235 tree->count = 1;
236 return 0;
237 }
238
239 node = avl_find_rec(tree->root, new->key, tree->comp, tree->cmp_ptr, &diff);
240
241 last = node;
242
243 while (!list_is_last(&last->list, &tree->list_head)) {
244 next = avl_next(last);
245 if (next->leader) {
246 break;
247 }
248 last = next;
249 }
250
251 diff = (*tree->comp) (new->key, node->key, tree->cmp_ptr);
252
253 if (diff == 0) {
254 if (!tree->allow_dups)
255 return -1;
256
257 new->leader = 0;
258
259 avl_insert_after(tree, last, new);
260 return 0;
261 }
262
263 if (node->balance == 1) {
264 avl_insert_before(tree, node, new);
265
266 node->balance = 0;
267 new->parent = node;
268 node->left = new;
269 return 0;
270 }
271
272 if (node->balance == -1) {
273 avl_insert_after(tree, last, new);
274
275 node->balance = 0;
276 new->parent = node;
277 node->right = new;
278 return 0;
279 }
280
281 if (diff < 0) {
282 avl_insert_before(tree, node, new);
283
284 node->balance = -1;
285 new->parent = node;
286 node->left = new;
287 post_insert(tree, node);
288 return 0;
289 }
290
291 avl_insert_after(tree, last, new);
292
293 node->balance = 1;
294 new->parent = node;
295 node->right = new;
296 post_insert(tree, node);
297 return 0;
298 }
299
300 /**
301 * Remove a node from an avl tree
302 * @param tree pointer to tree
303 * @param node pointer to node
304 */
305 void
306 avl_delete(struct avl_tree *tree, struct avl_node *node)
307 {
308 struct avl_node *next;
309 struct avl_node *parent;
310 struct avl_node *left;
311 struct avl_node *right;
312 if (node->leader) {
313 if (tree->allow_dups
314 && !list_is_last(&node->list, &tree->list_head)
315 && !(next = avl_next(node))->leader) {
316 next->leader = true;
317 next->balance = node->balance;
318
319 parent = node->parent;
320 left = node->left;
321 right = node->right;
322
323 next->parent = parent;
324 next->left = left;
325 next->right = right;
326
327 if (parent == NULL)
328 tree->root = next;
329
330 else {
331 if (node == parent->left)
332 parent->left = next;
333
334 else
335 parent->right = next;
336 }
337
338 if (left != NULL)
339 left->parent = next;
340
341 if (right != NULL)
342 right->parent = next;
343 }
344
345 else
346 avl_delete_worker(tree, node);
347 }
348
349 avl_remove(tree, node);
350 }
351
352 static struct avl_node *
353 avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *cmp_ptr, int *cmp_result)
354 {
355 int diff;
356
357 diff = (*comp) (key, node->key, cmp_ptr);
358 *cmp_result = diff;
359
360 if (diff < 0) {
361 if (node->left != NULL)
362 return avl_find_rec(node->left, key, comp, cmp_ptr, cmp_result);
363
364 return node;
365 }
366
367 if (diff > 0) {
368 if (node->right != NULL)
369 return avl_find_rec(node->right, key, comp, cmp_ptr, cmp_result);
370
371 return node;
372 }
373
374 return node;
375 }
376
377 static void
378 avl_rotate_right(struct avl_tree *tree, struct avl_node *node)
379 {
380 struct avl_node *left, *parent;
381
382 left = node->left;
383 parent = node->parent;
384
385 left->parent = parent;
386 node->parent = left;
387
388 if (parent == NULL)
389 tree->root = left;
390
391 else {
392 if (parent->left == node)
393 parent->left = left;
394
395 else
396 parent->right = left;
397 }
398
399 node->left = left->right;
400 left->right = node;
401
402 if (node->left != NULL)
403 node->left->parent = node;
404
405 node->balance += 1 - avl_min(left->balance, 0);
406 left->balance += 1 + avl_max(node->balance, 0);
407 }
408
409 static void
410 avl_rotate_left(struct avl_tree *tree, struct avl_node *node)
411 {
412 struct avl_node *right, *parent;
413
414 right = node->right;
415 parent = node->parent;
416
417 right->parent = parent;
418 node->parent = right;
419
420 if (parent == NULL)
421 tree->root = right;
422
423 else {
424 if (parent->left == node)
425 parent->left = right;
426
427 else
428 parent->right = right;
429 }
430
431 node->right = right->left;
432 right->left = node;
433
434 if (node->right != NULL)
435 node->right->parent = node;
436
437 node->balance -= 1 + avl_max(right->balance, 0);
438 right->balance -= 1 - avl_min(node->balance, 0);
439 }
440
441 static void
442 post_insert(struct avl_tree *tree, struct avl_node *node)
443 {
444 struct avl_node *parent = node->parent;
445
446 if (parent == NULL)
447 return;
448
449 if (node == parent->left) {
450 parent->balance--;
451
452 if (parent->balance == 0)
453 return;
454
455 if (parent->balance == -1) {
456 post_insert(tree, parent);
457 return;
458 }
459
460 if (node->balance == -1) {
461 avl_rotate_right(tree, parent);
462 return;
463 }
464
465 avl_rotate_left(tree, node);
466 avl_rotate_right(tree, node->parent->parent);
467 return;
468 }
469
470 parent->balance++;
471
472 if (parent->balance == 0)
473 return;
474
475 if (parent->balance == 1) {
476 post_insert(tree, parent);
477 return;
478 }
479
480 if (node->balance == 1) {
481 avl_rotate_left(tree, parent);
482 return;
483 }
484
485 avl_rotate_right(tree, node);
486 avl_rotate_left(tree, node->parent->parent);
487 }
488
489 static void
490 avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
491 {
492 list_add_tail(&node->list, &pos_node->list);
493 tree->count++;
494 }
495
496 static void
497 avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
498 {
499 list_add(&node->list, &pos_node->list);
500 tree->count++;
501 }
502
503 static void
504 avl_remove(struct avl_tree *tree, struct avl_node *node)
505 {
506 list_del(&node->list);
507 tree->count--;
508 }
509
510 static void
511 avl_post_delete(struct avl_tree *tree, struct avl_node *node)
512 {
513 struct avl_node *parent;
514
515 if ((parent = node->parent) == NULL)
516 return;
517
518 if (node == parent->left) {
519 parent->balance++;
520
521 if (parent->balance == 0) {
522 avl_post_delete(tree, parent);
523 return;
524 }
525
526 if (parent->balance == 1)
527 return;
528
529 if (parent->right->balance == 0) {
530 avl_rotate_left(tree, parent);
531 return;
532 }
533
534 if (parent->right->balance == 1) {
535 avl_rotate_left(tree, parent);
536 avl_post_delete(tree, parent->parent);
537 return;
538 }
539
540 avl_rotate_right(tree, parent->right);
541 avl_rotate_left(tree, parent);
542 avl_post_delete(tree, parent->parent);
543 return;
544 }
545
546 parent->balance--;
547
548 if (parent->balance == 0) {
549 avl_post_delete(tree, parent);
550 return;
551 }
552
553 if (parent->balance == -1)
554 return;
555
556 if (parent->left->balance == 0) {
557 avl_rotate_right(tree, parent);
558 return;
559 }
560
561 if (parent->left->balance == -1) {
562 avl_rotate_right(tree, parent);
563 avl_post_delete(tree, parent->parent);
564 return;
565 }
566
567 avl_rotate_left(tree, parent->left);
568 avl_rotate_right(tree, parent);
569 avl_post_delete(tree, parent->parent);
570 }
571
572 static struct avl_node *
573 avl_local_min(struct avl_node *node)
574 {
575 while (node->left != NULL)
576 node = node->left;
577
578 return node;
579 }
580
581 #if 0
582 static struct avl_node *
583 avl_local_max(struct avl_node *node)
584 {
585 while (node->right != NULL)
586 node = node->right;
587
588 return node;
589 }
590 #endif
591
592 static void
593 avl_delete_worker(struct avl_tree *tree, struct avl_node *node)
594 {
595 struct avl_node *parent, *min;
596
597 parent = node->parent;
598
599 if (node->left == NULL && node->right == NULL) {
600 if (parent == NULL) {
601 tree->root = NULL;
602 return;
603 }
604
605 if (parent->left == node) {
606 parent->left = NULL;
607 parent->balance++;
608
609 if (parent->balance == 1)
610 return;
611
612 if (parent->balance == 0) {
613 avl_post_delete(tree, parent);
614 return;
615 }
616
617 if (parent->right->balance == 0) {
618 avl_rotate_left(tree, parent);
619 return;
620 }
621
622 if (parent->right->balance == 1) {
623 avl_rotate_left(tree, parent);
624 avl_post_delete(tree, parent->parent);
625 return;
626 }
627
628 avl_rotate_right(tree, parent->right);
629 avl_rotate_left(tree, parent);
630 avl_post_delete(tree, parent->parent);
631 return;
632 }
633
634 if (parent->right == node) {
635 parent->right = NULL;
636 parent->balance--;
637
638 if (parent->balance == -1)
639 return;
640
641 if (parent->balance == 0) {
642 avl_post_delete(tree, parent);
643 return;
644 }
645
646 if (parent->left->balance == 0) {
647 avl_rotate_right(tree, parent);
648 return;
649 }
650
651 if (parent->left->balance == -1) {
652 avl_rotate_right(tree, parent);
653 avl_post_delete(tree, parent->parent);
654 return;
655 }
656
657 avl_rotate_left(tree, parent->left);
658 avl_rotate_right(tree, parent);
659 avl_post_delete(tree, parent->parent);
660 return;
661 }
662 }
663
664 if (node->left == NULL) {
665 if (parent == NULL) {
666 tree->root = node->right;
667 node->right->parent = NULL;
668 return;
669 }
670
671 node->right->parent = parent;
672
673 if (parent->left == node)
674 parent->left = node->right;
675
676 else
677 parent->right = node->right;
678
679 avl_post_delete(tree, node->right);
680 return;
681 }
682
683 if (node->right == NULL) {
684 if (parent == NULL) {
685 tree->root = node->left;
686 node->left->parent = NULL;
687 return;
688 }
689
690 node->left->parent = parent;
691
692 if (parent->left == node)
693 parent->left = node->left;
694
695 else
696 parent->right = node->left;
697
698 avl_post_delete(tree, node->left);
699 return;
700 }
701
702 min = avl_local_min(node->right);
703 avl_delete_worker(tree, min);
704 parent = node->parent;
705
706 min->balance = node->balance;
707 min->parent = parent;
708 min->left = node->left;
709 min->right = node->right;
710
711 if (min->left != NULL)
712 min->left->parent = min;
713
714 if (min->right != NULL)
715 min->right->parent = min;
716
717 if (parent == NULL) {
718 tree->root = min;
719 return;
720 }
721
722 if (parent->left == node) {
723 parent->left = min;
724 return;
725 }
726
727 parent->right = min;
728 }
729
730 /*
731 * Local Variables:
732 * c-basic-offset: 2
733 * indent-tabs-mode: nil
734 * End:
735 */