libubox: tests: add more blobmsg/json test cases
[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 "assert.h"
49 #include "list.h"
50
51 /**
52 * internal type save inline function to calculate the maximum of
53 * to integers without macro implementation.
54 *
55 * @param x first parameter of maximum function
56 * @param y second parameter of maximum function
57 * @return largest integer of both parameters
58 */
59 static inline int avl_max(int x, int y) {
60 return x > y ? x : y;
61 }
62
63 /**
64 * internal type save inline function to calculate the minimum of
65 * to integers without macro implementation.
66 *
67 * @param x first parameter of minimum function
68 * @param y second parameter of minimum function
69 * @return smallest integer of both parameters
70 */
71 static inline int avl_min(int x, int y) {
72 return x < y ? x : y;
73 }
74
75 static struct avl_node *
76 avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *ptr, int *cmp_result);
77 static void avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
78 static void avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node);
79 static void post_insert(struct avl_tree *tree, struct avl_node *node);
80 static void avl_delete_worker(struct avl_tree *tree, struct avl_node *node);
81 static void avl_remove(struct avl_tree *tree, struct avl_node *node);
82
83 /**
84 * Initialize a new avl_tree struct
85 * @param tree pointer to avl-tree
86 * @param comp pointer to comparator for the tree
87 * @param allow_dups true if the tree allows multiple
88 * elements with the same
89 * @param ptr custom parameter for comparator
90 */
91 void
92 avl_init(struct avl_tree *tree, avl_tree_comp comp, bool allow_dups, void *ptr)
93 {
94 INIT_LIST_HEAD(&tree->list_head);
95 tree->root = NULL;
96 tree->count = 0;
97 tree->comp = comp;
98 tree->allow_dups = allow_dups;
99 tree->cmp_ptr = ptr;
100 }
101
102 static inline struct avl_node *avl_next(struct avl_node *node)
103 {
104 return list_entry(node->list.next, struct avl_node, list);
105 }
106
107 /**
108 * Finds a node in an avl-tree with a certain key
109 * @param tree pointer to avl-tree
110 * @param key pointer to key
111 * @return pointer to avl-node with key, NULL if no node with
112 * this key exists.
113 */
114 struct avl_node *
115 avl_find(const struct avl_tree *tree, const void *key)
116 {
117 struct avl_node *node;
118 int diff;
119
120 if (tree->root == NULL)
121 return NULL;
122
123 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
124
125 return diff == 0 ? node : NULL;
126 }
127
128 /**
129 * Finds the last node in an avl-tree with a key less or equal
130 * than the specified key
131 * @param tree pointer to avl-tree
132 * @param key pointer to specified key
133 * @return pointer to avl-node, NULL if no node with
134 * key less or equal specified key exists.
135 */
136 struct avl_node *
137 avl_find_lessequal(const struct avl_tree *tree, const void *key) {
138 struct avl_node *node, *next;
139 int diff;
140
141 if (tree->root == NULL)
142 return NULL;
143
144 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
145
146 /* go left as long as key<node.key */
147 while (diff < 0) {
148 if (list_is_first(&node->list, &tree->list_head)) {
149 return NULL;
150 }
151
152 node = (struct avl_node *)node->list.prev;
153 diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
154 }
155
156 /* go right as long as key>=next_node.key */
157 next = node;
158 while (diff >= 0) {
159 node = next;
160 if (list_is_last(&node->list, &tree->list_head)) {
161 break;
162 }
163
164 next = (struct avl_node *)node->list.next;
165 diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
166 }
167 return node;
168 }
169
170 /**
171 * Finds the first node in an avl-tree with a key greater or equal
172 * than the specified key
173 * @param tree pointer to avl-tree
174 * @param key pointer to specified key
175 * @return pointer to avl-node, NULL if no node with
176 * key greater or equal specified key exists.
177 */
178 struct avl_node *
179 avl_find_greaterequal(const struct avl_tree *tree, const void *key) {
180 struct avl_node *node, *next;
181 int diff;
182
183 if (tree->root == NULL)
184 return NULL;
185
186 node = avl_find_rec(tree->root, key, tree->comp, tree->cmp_ptr, &diff);
187
188 /* go right as long as key>node.key */
189 while (diff > 0) {
190 if (list_is_last(&node->list, &tree->list_head)) {
191 return NULL;
192 }
193
194 node = (struct avl_node *)node->list.next;
195 diff = (*tree->comp) (key, node->key, tree->cmp_ptr);
196 }
197
198 /* go left as long as key<=next_node.key */
199 next = node;
200 while (diff <= 0) {
201 node = next;
202 if (list_is_first(&node->list, &tree->list_head)) {
203 break;
204 }
205
206 next = (struct avl_node *)node->list.prev;
207 diff = (*tree->comp) (key, next->key, tree->cmp_ptr);
208 }
209 return node;
210 }
211
212 /**
213 * Inserts an avl_node into a tree
214 * @param tree pointer to tree
215 * @param new pointer to node
216 * @return 0 if node was inserted successfully, -1 if it was not inserted
217 * because of a key collision
218 */
219 int
220 avl_insert(struct avl_tree *tree, struct avl_node *new)
221 {
222 struct avl_node *node, *next, *last;
223 int diff;
224
225 new->parent = NULL;
226
227 new->left = NULL;
228 new->right = NULL;
229
230 new->balance = 0;
231 new->leader = true;
232
233 if (tree->root == NULL) {
234 list_add(&new->list, &tree->list_head);
235 tree->root = new;
236 tree->count = 1;
237 return 0;
238 }
239
240 node = avl_find_rec(tree->root, new->key, tree->comp, tree->cmp_ptr, &diff);
241
242 last = node;
243
244 while (!list_is_last(&last->list, &tree->list_head)) {
245 next = avl_next(last);
246 if (next->leader) {
247 break;
248 }
249 last = next;
250 }
251
252 diff = (*tree->comp) (new->key, node->key, tree->cmp_ptr);
253
254 if (diff == 0) {
255 if (!tree->allow_dups)
256 return -1;
257
258 new->leader = 0;
259
260 avl_insert_after(tree, last, new);
261 return 0;
262 }
263
264 if (node->balance == 1) {
265 avl_insert_before(tree, node, new);
266
267 node->balance = 0;
268 new->parent = node;
269 node->left = new;
270 return 0;
271 }
272
273 if (node->balance == -1) {
274 avl_insert_after(tree, last, new);
275
276 node->balance = 0;
277 new->parent = node;
278 node->right = new;
279 return 0;
280 }
281
282 if (diff < 0) {
283 avl_insert_before(tree, node, new);
284
285 node->balance = -1;
286 new->parent = node;
287 node->left = new;
288 post_insert(tree, node);
289 return 0;
290 }
291
292 avl_insert_after(tree, last, new);
293
294 node->balance = 1;
295 new->parent = node;
296 node->right = new;
297 post_insert(tree, node);
298 return 0;
299 }
300
301 /**
302 * Remove a node from an avl tree
303 * @param tree pointer to tree
304 * @param node pointer to node
305 */
306 void
307 avl_delete(struct avl_tree *tree, struct avl_node *node)
308 {
309 struct avl_node *next;
310 struct avl_node *parent;
311 struct avl_node *left;
312 struct avl_node *right;
313 if (node->leader) {
314 if (tree->allow_dups
315 && !list_is_last(&node->list, &tree->list_head)
316 && !(next = avl_next(node))->leader) {
317 next->leader = true;
318 next->balance = node->balance;
319
320 parent = node->parent;
321 left = node->left;
322 right = node->right;
323
324 next->parent = parent;
325 next->left = left;
326 next->right = right;
327
328 if (parent == NULL)
329 tree->root = next;
330
331 else {
332 if (node == parent->left)
333 parent->left = next;
334
335 else
336 parent->right = next;
337 }
338
339 if (left != NULL)
340 left->parent = next;
341
342 if (right != NULL)
343 right->parent = next;
344 }
345
346 else
347 avl_delete_worker(tree, node);
348 }
349
350 avl_remove(tree, node);
351 }
352
353 static struct avl_node *
354 avl_find_rec(struct avl_node *node, const void *key, avl_tree_comp comp, void *cmp_ptr, int *cmp_result)
355 {
356 int diff;
357
358 diff = (*comp) (key, node->key, cmp_ptr);
359 *cmp_result = diff;
360
361 if (diff < 0) {
362 if (node->left != NULL)
363 return avl_find_rec(node->left, key, comp, cmp_ptr, cmp_result);
364
365 return node;
366 }
367
368 if (diff > 0) {
369 if (node->right != NULL)
370 return avl_find_rec(node->right, key, comp, cmp_ptr, cmp_result);
371
372 return node;
373 }
374
375 return node;
376 }
377
378 static void
379 avl_rotate_right(struct avl_tree *tree, struct avl_node *node)
380 {
381 struct avl_node *left, *parent;
382
383 left = node->left;
384 parent = node->parent;
385
386 left->parent = parent;
387 node->parent = left;
388
389 if (parent == NULL)
390 tree->root = left;
391
392 else {
393 if (parent->left == node)
394 parent->left = left;
395
396 else
397 parent->right = left;
398 }
399
400 node->left = left->right;
401 left->right = node;
402
403 if (node->left != NULL)
404 node->left->parent = node;
405
406 node->balance += 1 - avl_min(left->balance, 0);
407 left->balance += 1 + avl_max(node->balance, 0);
408 }
409
410 static void
411 avl_rotate_left(struct avl_tree *tree, struct avl_node *node)
412 {
413 struct avl_node *right, *parent;
414
415 right = node->right;
416 parent = node->parent;
417
418 right->parent = parent;
419 node->parent = right;
420
421 if (parent == NULL)
422 tree->root = right;
423
424 else {
425 if (parent->left == node)
426 parent->left = right;
427
428 else
429 parent->right = right;
430 }
431
432 node->right = right->left;
433 right->left = node;
434
435 if (node->right != NULL)
436 node->right->parent = node;
437
438 node->balance -= 1 + avl_max(right->balance, 0);
439 right->balance -= 1 - avl_min(node->balance, 0);
440 }
441
442 static void
443 post_insert(struct avl_tree *tree, struct avl_node *node)
444 {
445 struct avl_node *parent = node->parent;
446
447 if (parent == NULL)
448 return;
449
450 if (node == parent->left) {
451 parent->balance--;
452
453 if (parent->balance == 0)
454 return;
455
456 if (parent->balance == -1) {
457 post_insert(tree, parent);
458 return;
459 }
460
461 if (node->balance == -1) {
462 avl_rotate_right(tree, parent);
463 return;
464 }
465
466 avl_rotate_left(tree, node);
467 avl_rotate_right(tree, node->parent->parent);
468 return;
469 }
470
471 parent->balance++;
472
473 if (parent->balance == 0)
474 return;
475
476 if (parent->balance == 1) {
477 post_insert(tree, parent);
478 return;
479 }
480
481 if (node->balance == 1) {
482 avl_rotate_left(tree, parent);
483 return;
484 }
485
486 avl_rotate_right(tree, node);
487 avl_rotate_left(tree, node->parent->parent);
488 }
489
490 static void
491 avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
492 {
493 list_add_tail(&node->list, &pos_node->list);
494 tree->count++;
495 }
496
497 static void
498 avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node, struct avl_node *node)
499 {
500 list_add(&node->list, &pos_node->list);
501 tree->count++;
502 }
503
504 static void
505 avl_remove(struct avl_tree *tree, struct avl_node *node)
506 {
507 list_del(&node->list);
508 tree->count--;
509 }
510
511 static void
512 avl_post_delete(struct avl_tree *tree, struct avl_node *node)
513 {
514 struct avl_node *parent;
515
516 if ((parent = node->parent) == NULL)
517 return;
518
519 if (node == parent->left) {
520 parent->balance++;
521
522 if (parent->balance == 0) {
523 avl_post_delete(tree, parent);
524 return;
525 }
526
527 if (parent->balance == 1)
528 return;
529
530 if (parent->right->balance == 0) {
531 avl_rotate_left(tree, parent);
532 return;
533 }
534
535 if (parent->right->balance == 1) {
536 avl_rotate_left(tree, parent);
537 avl_post_delete(tree, parent->parent);
538 return;
539 }
540
541 avl_rotate_right(tree, parent->right);
542 avl_rotate_left(tree, parent);
543 avl_post_delete(tree, parent->parent);
544 return;
545 }
546
547 parent->balance--;
548
549 if (parent->balance == 0) {
550 avl_post_delete(tree, parent);
551 return;
552 }
553
554 if (parent->balance == -1)
555 return;
556
557 if (parent->left->balance == 0) {
558 avl_rotate_right(tree, parent);
559 return;
560 }
561
562 if (parent->left->balance == -1) {
563 avl_rotate_right(tree, parent);
564 avl_post_delete(tree, parent->parent);
565 return;
566 }
567
568 avl_rotate_left(tree, parent->left);
569 avl_rotate_right(tree, parent);
570 avl_post_delete(tree, parent->parent);
571 }
572
573 static struct avl_node *
574 avl_local_min(struct avl_node *node)
575 {
576 while (node->left != NULL)
577 node = node->left;
578
579 return node;
580 }
581
582 #if 0
583 static struct avl_node *
584 avl_local_max(struct avl_node *node)
585 {
586 while (node->right != NULL)
587 node = node->right;
588
589 return node;
590 }
591 #endif
592
593 static void
594 avl_delete_worker(struct avl_tree *tree, struct avl_node *node)
595 {
596 struct avl_node *parent, *min;
597
598 parent = node->parent;
599
600 if (node->left == NULL && node->right == NULL) {
601 if (parent == NULL) {
602 tree->root = NULL;
603 return;
604 }
605
606 if (parent->left == node) {
607 parent->left = NULL;
608 parent->balance++;
609
610 if (parent->balance == 1)
611 return;
612
613 if (parent->balance == 0) {
614 avl_post_delete(tree, parent);
615 return;
616 }
617
618 if (parent->right->balance == 0) {
619 avl_rotate_left(tree, parent);
620 return;
621 }
622
623 if (parent->right->balance == 1) {
624 avl_rotate_left(tree, parent);
625 avl_post_delete(tree, parent->parent);
626 return;
627 }
628
629 avl_rotate_right(tree, parent->right);
630 avl_rotate_left(tree, parent);
631 avl_post_delete(tree, parent->parent);
632 return;
633 }
634
635 if (parent->right == node) {
636 parent->right = NULL;
637 parent->balance--;
638
639 if (parent->balance == -1)
640 return;
641
642 if (parent->balance == 0) {
643 avl_post_delete(tree, parent);
644 return;
645 }
646
647 if (parent->left->balance == 0) {
648 avl_rotate_right(tree, parent);
649 return;
650 }
651
652 if (parent->left->balance == -1) {
653 avl_rotate_right(tree, parent);
654 avl_post_delete(tree, parent->parent);
655 return;
656 }
657
658 avl_rotate_left(tree, parent->left);
659 avl_rotate_right(tree, parent);
660 avl_post_delete(tree, parent->parent);
661 return;
662 }
663 }
664
665 if (node->left == NULL) {
666 if (parent == NULL) {
667 tree->root = node->right;
668 node->right->parent = NULL;
669 return;
670 }
671
672 assert(node->right);
673 node->right->parent = parent;
674
675 if (parent->left == node)
676 parent->left = node->right;
677
678 else
679 parent->right = node->right;
680
681 avl_post_delete(tree, node->right);
682 return;
683 }
684
685 if (node->right == NULL) {
686 if (parent == NULL) {
687 tree->root = node->left;
688 node->left->parent = NULL;
689 return;
690 }
691
692 node->left->parent = parent;
693
694 if (parent->left == node)
695 parent->left = node->left;
696
697 else
698 parent->right = node->left;
699
700 avl_post_delete(tree, node->left);
701 return;
702 }
703
704 min = avl_local_min(node->right);
705 avl_delete_worker(tree, min);
706 parent = node->parent;
707
708 min->balance = node->balance;
709 min->parent = parent;
710 min->left = node->left;
711 min->right = node->right;
712
713 if (min->left != NULL)
714 min->left->parent = min;
715
716 if (min->right != NULL)
717 min->right->parent = min;
718
719 if (parent == NULL) {
720 tree->root = min;
721 return;
722 }
723
724 if (parent->left == node) {
725 parent->left = min;
726 return;
727 }
728
729 parent->right = min;
730 }
731
732 /*
733 * Local Variables:
734 * c-basic-offset: 2
735 * indent-tabs-mode: nil
736 * End:
737 */