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