runqueue: fix use-after-free bug
[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  */