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