ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/svn/ircd-hybrid/trunk/src/patricia.c
Revision: 8598
Committed: Mon Oct 22 19:29:20 2018 UTC (5 years, 5 months ago) by michael
Content type: text/x-csrc
File size: 23619 byte(s)
Log Message:
- patricia.c: stylistic changes

File Contents

# Content
1 /*
2 * $Id$
3 * Dave Plonka <plonka@doit.wisc.edu>
4 *
5 * This file had been called "radix.c" in the MRT sources.
6 *
7 * I renamed it to "patricia.c" since it's not an implementation of a general
8 * radix trie. Also I pulled in various requirements from "prefix.c" and
9 * "demo.c" so that it could be used as a standalone API.
10 *
11 * Copyright (c) 1999-2013
12 *
13 * The Regents of the University of Michigan ("The Regents") and Merit
14 * Network, Inc.
15 *
16 * Redistributions of source code must retain the above copyright notice,
17 * this list of conditions and the following disclaimer.
18 *
19 * Redistributions in binary form must reproduce the above copyright
20 * notice, this list of conditions and the following disclaimer in the
21 * documentation and/or other materials provided with the distribution.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
29 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
30 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
31 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
33 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 */
35
36 #include <assert.h> /* assert */
37 #include <stddef.h> /* NULL */
38 #include <stdio.h> /* sprintf, fprintf, stderr */
39 #include <stdlib.h> /* free, atol, calloc */
40 #include <string.h> /* memcpy, strchr, strlen */
41 #include <sys/types.h> /* BSD: for inet_addr */
42 #include <sys/socket.h> /* BSD, Linux: for inet_addr */
43 #include <netinet/in.h> /* BSD, Linux: for inet_addr */
44 #include <arpa/inet.h> /* BSD, Linux, Solaris: for inet_addr */
45
46 #include "patricia.h"
47 #include "memory.h"
48
49 /* { from prefix.c */
50
51 /* prefix_tochar
52 * convert prefix information to bytes
53 */
54 static unsigned char *
55 prefix_tochar(prefix_t *prefix)
56 {
57 if (prefix == NULL)
58 return NULL;
59 return (unsigned char *)&prefix->add.sin;
60 }
61
62 static int
63 comp_with_mask(void *addr, void *dest, unsigned int mask)
64 {
65 if ( /* mask/8 == 0 || */ memcmp(addr, dest, mask / 8) == 0)
66 {
67 int n = mask / 8;
68 int m = ~((1 << (8 - (mask % 8))) - 1);
69
70 if (mask % 8 == 0 || (((unsigned char *)addr)[n] & m) == (((unsigned char *)dest)[n] & m))
71 return 1;
72 }
73
74 return 0;
75 }
76
77 /*
78 * convert prefix information to ascii string with length
79 */
80 const char *
81 patricia_prefix_toa(const prefix_t *prefix, int with_len)
82 {
83 static char buf[INET6_ADDRSTRLEN + sizeof("/128")];
84
85 assert(prefix);
86 assert(prefix->ref_count >= 0);
87 assert((prefix->family == AF_INET && prefix->bitlen <= 32) ||
88 (prefix->family == AF_INET6 && prefix->bitlen <= 128));
89
90 inet_ntop(prefix->family, &prefix->add.sin6, buf, INET6_ADDRSTRLEN);
91
92 if (with_len)
93 sprintf(buf + strlen(buf), "/%d", prefix->bitlen);
94 return buf;
95 }
96
97 static prefix_t *
98 New_Prefix2(int family, void *dest, int bitlen, prefix_t *prefix)
99 {
100 int dynamic_allocated = 0;
101 int addr_size = 0;
102
103 switch (family)
104 {
105 case AF_INET:
106 addr_size = sizeof(struct in_addr);
107 break;
108 case AF_INET6:
109 addr_size = sizeof(struct in6_addr);
110 break;
111 default: return NULL;
112 }
113
114 if (prefix == NULL)
115 {
116 prefix = xcalloc(sizeof(*prefix));
117 dynamic_allocated = 1;
118 }
119
120 memcpy(&prefix->add.sin6, dest, addr_size);
121 prefix->bitlen = (bitlen >= 0) ? bitlen : addr_size * 8;
122 prefix->family = family;
123 prefix->ref_count = dynamic_allocated == 1;
124
125 /* fprintf(stderr, "[C %s, %d]\n", patricia_prefix_toa(prefix), prefix->ref_count); */
126 return prefix;
127 }
128
129 static prefix_t *
130 New_Prefix(int family, void *dest, int bitlen)
131 {
132 return New_Prefix2(family, dest, bitlen, NULL);
133 }
134
135 /* ascii2prefix
136 */
137 static prefix_t *
138 ascii2prefix(int family, const char *string)
139 {
140 char save[INET6_ADDRSTRLEN];
141 int bitlen, maxbitlen = 0;
142 union
143 {
144 struct in_addr sin;
145 struct in6_addr sin6;
146 } sin;
147
148 assert(string);
149
150 /* Easy way to handle both families */
151 if (family == 0)
152 {
153 family = AF_INET;
154
155 if (strchr(string, ':'))
156 family = AF_INET6;
157 }
158
159 if (family == AF_INET)
160 maxbitlen = sizeof(struct in_addr) * 8;
161 else if (family == AF_INET6)
162 maxbitlen = sizeof(struct in6_addr) * 8;
163
164 const char *const cp = strchr(string, '/');
165 if (cp)
166 {
167 size_t strlen = cp - string;
168
169 if (strlen >= sizeof(save))
170 return NULL;
171
172 bitlen = atoi(cp + 1);
173
174 /* Copy the string to save. Avoid destroying the string */
175 memcpy(save, string, strlen);
176 save[strlen] = '\0';
177
178 string = save;
179
180 if (bitlen < 0 || bitlen > maxbitlen)
181 bitlen = maxbitlen;
182 }
183 else
184 bitlen = maxbitlen;
185
186 if (inet_pton(family, string, &sin) <= 0)
187 return NULL;
188 return New_Prefix(family, &sin, bitlen);
189 }
190
191 static prefix_t *
192 Ref_Prefix(prefix_t *prefix)
193 {
194 if (prefix == NULL)
195 return NULL;
196
197 if (prefix->ref_count == 0)
198 /* Make a copy in case of a static prefix */
199 return New_Prefix2(prefix->family, &prefix->add, prefix->bitlen, NULL);
200
201 prefix->ref_count++;
202
203 /* fprintf(stderr, "[A %s, %d]\n", patricia_prefix_toa(prefix), prefix->ref_count); */
204 return prefix;
205 }
206
207 static void
208 Deref_Prefix(prefix_t *prefix)
209 {
210 if (prefix == NULL)
211 return;
212
213 /* For secure programming, raise an assert. No static prefix can call this */
214 assert(prefix->ref_count > 0);
215 if (--prefix->ref_count <= 0)
216 xfree(prefix);
217 }
218 /* } */
219
220 /* #define PATRICIA_DEBUG 1 */
221
222 /* these routines support continuous mask only */
223
224 patricia_tree_t *
225 patricia_new(unsigned int maxbits)
226 {
227 patricia_tree_t *patricia = xcalloc(sizeof(*patricia));
228 patricia->maxbits = maxbits;
229
230 assert(maxbits <= PATRICIA_MAXBITS); /* XXX */
231 return patricia;
232 }
233
234 /*
235 * if func is supplied, it will be called as func(node->data)
236 * before deleting the node
237 */
238 void
239 patricia_clear(patricia_tree_t *patricia, void (*func)(void *))
240 {
241 assert(patricia);
242
243 if (patricia->head)
244 {
245 patricia_node_t *Xstack[PATRICIA_MAXBITS + 1];
246 patricia_node_t **Xsp = Xstack;
247 patricia_node_t *Xrn = patricia->head;
248
249 while (Xrn)
250 {
251 patricia_node_t *l = Xrn->l;
252 patricia_node_t *r = Xrn->r;
253
254 if (Xrn->prefix)
255 {
256 Deref_Prefix(Xrn->prefix);
257
258 if (Xrn->data && func)
259 func(Xrn->data);
260 }
261 else
262 {
263 assert(Xrn->data == NULL);
264 }
265
266 xfree(Xrn);
267 patricia->num_active_node--;
268
269 if (l)
270 {
271 if (r)
272 {
273 *Xsp++ = r;
274 }
275
276 Xrn = l;
277 }
278 else if (r)
279 {
280 Xrn = r;
281 }
282 else if (Xsp != Xstack)
283 {
284 Xrn = *(--Xsp);
285 }
286 else
287 {
288 Xrn = NULL;
289 }
290 }
291 }
292
293 assert(patricia->num_active_node == 0);
294 /* xfree(patricia); */
295 }
296
297 void
298 patricia_destroy(patricia_tree_t *patricia, void (*func)(void *))
299 {
300 patricia_clear(patricia, func);
301 xfree(patricia);
302 }
303
304 /*
305 * if func is supplied, it will be called as func(node->prefix, node->data)
306 */
307 void
308 patricia_process(patricia_tree_t *patricia, void (*func)(prefix_t *, void *))
309 {
310 patricia_node_t *node;
311
312 assert(func);
313
314 PATRICIA_WALK(patricia->head, node) {
315 func(node->prefix, node->data);
316 } PATRICIA_WALK_END;
317 }
318
319 patricia_node_t *
320 patricia_search_exact(patricia_tree_t *patricia, prefix_t *prefix)
321 {
322 patricia_node_t *node;
323 unsigned char *addr;
324 unsigned int bitlen;
325
326 assert(patricia);
327 assert(prefix);
328 assert(prefix->bitlen <= patricia->maxbits);
329
330 if (patricia->head == NULL)
331 return NULL;
332
333 node = patricia->head;
334 addr = prefix_touchar(prefix);
335 bitlen = prefix->bitlen;
336
337 while (node->bit < bitlen)
338 {
339 if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
340 {
341 #ifdef PATRICIA_DEBUG
342 if (node->prefix)
343 fprintf(stderr, "patricia_search_exact: take right %s/%d\n",
344 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
345 else
346 fprintf(stderr, "patricia_search_exact: take right at %u\n", node->bit);
347 #endif /* PATRICIA_DEBUG */
348 node = node->r;
349 }
350 else
351 {
352 #ifdef PATRICIA_DEBUG
353 if (node->prefix)
354 fprintf(stderr, "patricia_search_exact: take left %s/%d\n",
355 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
356 else
357 fprintf(stderr, "patricia_search_exact: take left at %u\n", node->bit);
358 #endif /* PATRICIA_DEBUG */
359 node = node->l;
360 }
361
362 if (node == NULL)
363 return NULL;
364 }
365
366 #ifdef PATRICIA_DEBUG
367 if (node->prefix)
368 fprintf(stderr, "patricia_search_exact: stop at %s/%d\n",
369 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
370 else
371 fprintf(stderr, "patricia_search_exact: stop at %u\n", node->bit);
372 #endif /* PATRICIA_DEBUG */
373
374 if (node->bit > bitlen || node->prefix == NULL)
375 return NULL;
376
377 assert(node->bit == bitlen);
378 assert(node->bit == node->prefix->bitlen);
379
380 if (comp_with_mask(prefix_tochar(node->prefix), prefix_tochar(prefix), bitlen))
381 {
382 #ifdef PATRICIA_DEBUG
383 fprintf(stderr, "patricia_search_exact: found %s/%d\n",
384 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
385 #endif /* PATRICIA_DEBUG */
386 return node;
387 }
388
389 return NULL;
390 }
391
392 /* if inclusive != 0, "best" may be the given prefix itself */
393 patricia_node_t *
394 patricia_search_best2(patricia_tree_t *patricia, prefix_t *prefix, int inclusive)
395 {
396 patricia_node_t *node;
397 patricia_node_t *stack[PATRICIA_MAXBITS + 1];
398 unsigned char *addr;
399 unsigned int bitlen;
400 int cnt = 0;
401
402 assert(patricia);
403 assert(prefix);
404 assert(prefix->bitlen <= patricia->maxbits);
405
406 if (patricia->head == NULL)
407 return NULL;
408
409 node = patricia->head;
410 addr = prefix_touchar(prefix);
411 bitlen = prefix->bitlen;
412
413 while (node->bit < bitlen)
414 {
415 if (node->prefix)
416 {
417 #ifdef PATRICIA_DEBUG
418 fprintf(stderr, "patricia_search_best: push %s/%d\n",
419 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
420 #endif /* PATRICIA_DEBUG */
421 stack[cnt++] = node;
422 }
423
424 if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
425 {
426 #ifdef PATRICIA_DEBUG
427 if (node->prefix)
428 fprintf(stderr, "patricia_search_best: take right %s/%d\n",
429 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
430 else
431 fprintf(stderr, "patricia_search_best: take right at %u\n", node->bit);
432 #endif /* PATRICIA_DEBUG */
433 node = node->r;
434 }
435 else
436 {
437 #ifdef PATRICIA_DEBUG
438 if (node->prefix)
439 fprintf(stderr, "patricia_search_best: take left %s/%d\n",
440 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
441 else
442 fprintf(stderr, "patricia_search_best: take left at %u\n", node->bit);
443 #endif /* PATRICIA_DEBUG */
444 node = node->l;
445 }
446
447 if (node == NULL)
448 break;
449 }
450
451 if (inclusive && node && node->prefix)
452 stack[cnt++] = node;
453
454 #ifdef PATRICIA_DEBUG
455 if (node == NULL)
456 fprintf(stderr, "patricia_search_best: stop at null\n");
457 else if (node->prefix)
458 fprintf(stderr, "patricia_search_best: stop at %s/%d\n",
459 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
460 else
461 fprintf(stderr, "patricia_search_best: stop at %u\n", node->bit);
462 #endif /* PATRICIA_DEBUG */
463
464 if (cnt <= 0)
465 return NULL;
466
467 while (--cnt >= 0)
468 {
469 node = stack[cnt];
470 #ifdef PATRICIA_DEBUG
471 fprintf(stderr, "patricia_search_best: pop %s/%d\n",
472 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
473 #endif /* PATRICIA_DEBUG */
474
475 if (comp_with_mask(prefix_tochar(node->prefix),
476 prefix_tochar(prefix), node->prefix->bitlen) && node->prefix->bitlen <= bitlen)
477 {
478 #ifdef PATRICIA_DEBUG
479 fprintf(stderr, "patricia_search_best: found %s/%d\n",
480 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
481 #endif /* PATRICIA_DEBUG */
482 return node;
483 }
484 }
485
486 return NULL;
487 }
488
489 patricia_node_t *
490 patricia_search_best(patricia_tree_t *patricia, prefix_t *prefix)
491 {
492 return patricia_search_best2(patricia, prefix, 1);
493 }
494
495 patricia_node_t *
496 patricia_lookup(patricia_tree_t *patricia, prefix_t *prefix)
497 {
498 patricia_node_t *node, *new_node, *parent, *glue;
499 unsigned char *addr, *test_addr;
500 unsigned int bitlen, check_bit, differ_bit;
501 int j, r;
502
503 assert(patricia);
504 assert(prefix);
505 assert(prefix->bitlen <= patricia->maxbits);
506
507 if (patricia->head == NULL)
508 {
509 node = xcalloc(sizeof(*node));
510 node->bit = prefix->bitlen;
511 node->prefix = Ref_Prefix(prefix);
512 patricia->head = node;
513 #ifdef PATRICIA_DEBUG
514 fprintf(stderr, "patricia_lookup: new_node #0 %s/%d (head)\n",
515 patricia_prefix_toa(prefix), prefix->bitlen);
516 #endif /* PATRICIA_DEBUG */
517 patricia->num_active_node++;
518 return node;
519 }
520
521 addr = prefix_touchar(prefix);
522 bitlen = prefix->bitlen;
523 node = patricia->head;
524
525 while (node->bit < bitlen || node->prefix == NULL)
526 {
527 if (node->bit < patricia->maxbits && BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
528 {
529 if (node->r == NULL)
530 break;
531 #ifdef PATRICIA_DEBUG
532 if (node->prefix)
533 fprintf(stderr, "patricia_lookup: take right %s/%d\n",
534 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
535 else
536 fprintf(stderr, "patricia_lookup: take right at %u\n", node->bit);
537 #endif /* PATRICIA_DEBUG */
538
539 node = node->r;
540 }
541 else
542 {
543 if (node->l == NULL)
544 break;
545 #ifdef PATRICIA_DEBUG
546 if (node->prefix)
547 fprintf(stderr, "patricia_lookup: take left %s/%d\n",
548 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
549 else
550 fprintf(stderr, "patricia_lookup: take left at %u\n", node->bit);
551 #endif /* PATRICIA_DEBUG */
552
553 node = node->l;
554 }
555
556 assert(node);
557 }
558
559 assert(node->prefix);
560 #ifdef PATRICIA_DEBUG
561 fprintf(stderr, "patricia_lookup: stop at %s/%d\n",
562 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
563 #endif /* PATRICIA_DEBUG */
564
565 test_addr = prefix_touchar(node->prefix);
566
567 /* Find the first bit different */
568 check_bit = (node->bit < bitlen) ? node->bit : bitlen;
569 differ_bit = 0;
570
571 for (unsigned int i = 0; i * 8 < check_bit; i++)
572 {
573 if ((r = (addr[i] ^ test_addr[i])) == 0)
574 {
575 differ_bit = (i + 1) * 8;
576 continue;
577 }
578
579 /* I know the better way, but for now */
580 for (j = 0; j < 8; j++)
581 if (BIT_TEST(r, (0x80 >> j)))
582 break;
583
584 /* Must be found */
585 assert(j < 8);
586 differ_bit = i * 8 + j;
587 break;
588 }
589
590 if (differ_bit > check_bit)
591 differ_bit = check_bit;
592 #ifdef PATRICIA_DEBUG
593 fprintf(stderr, "patricia_lookup: differ_bit %d\n", differ_bit);
594 #endif /* PATRICIA_DEBUG */
595
596 parent = node->parent;
597
598 while (parent && parent->bit >= differ_bit)
599 {
600 node = parent;
601 parent = node->parent;
602
603 #ifdef PATRICIA_DEBUG
604 if (node->prefix)
605 fprintf(stderr, "patricia_lookup: up to %s/%d\n",
606 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
607 else
608 fprintf(stderr, "patricia_lookup: up to %u\n", node->bit);
609 #endif /* PATRICIA_DEBUG */
610 }
611
612 if (differ_bit == bitlen && node->bit == bitlen)
613 {
614 if (node->prefix)
615 {
616 #ifdef PATRICIA_DEBUG
617 fprintf(stderr, "patricia_lookup: found %s/%d\n",
618 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
619 #endif /* PATRICIA_DEBUG */
620
621 return node;
622 }
623
624 node->prefix = Ref_Prefix(prefix);
625 #ifdef PATRICIA_DEBUG
626 fprintf(stderr, "patricia_lookup: new node #1 %s/%d (glue mod)\n",
627 patricia_prefix_toa(prefix), prefix->bitlen);
628 #endif /* PATRICIA_DEBUG */
629
630 assert(node->data == NULL);
631 return node;
632 }
633
634 new_node = xcalloc(sizeof(*new_node));
635 new_node->bit = prefix->bitlen;
636 new_node->prefix = Ref_Prefix(prefix);
637 patricia->num_active_node++;
638
639 if (node->bit == differ_bit)
640 {
641 new_node->parent = node;
642
643 if (node->bit < patricia->maxbits && BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
644 {
645 assert(node->r == NULL);
646 node->r = new_node;
647 }
648 else
649 {
650 assert(node->l == NULL);
651 node->l = new_node;
652 }
653 #ifdef PATRICIA_DEBUG
654 fprintf(stderr, "patricia_lookup: new_node #2 %s/%d (child)\n",
655 patricia_prefix_toa(prefix), prefix->bitlen);
656 #endif /* PATRICIA_DEBUG */
657 return new_node;
658 }
659
660 if (bitlen == differ_bit)
661 {
662 if (bitlen < patricia->maxbits && BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07)))
663 {
664 new_node->r = node;
665 }
666 else
667 {
668 new_node->l = node;
669 }
670
671 new_node->parent = node->parent;
672
673 if (node->parent == NULL)
674 {
675 assert(patricia->head == node);
676 patricia->head = new_node;
677 }
678 else if (node->parent->r == node)
679 {
680 node->parent->r = new_node;
681 }
682 else
683 {
684 node->parent->l = new_node;
685 }
686
687 node->parent = new_node;
688 #ifdef PATRICIA_DEBUG
689 fprintf(stderr, "patricia_lookup: new_node #3 %s/%d (parent)\n",
690 patricia_prefix_toa(prefix), prefix->bitlen);
691 #endif /* PATRICIA_DEBUG */
692 }
693 else
694 {
695 glue = xcalloc(sizeof(*glue));
696 glue->bit = differ_bit;
697 glue->parent = node->parent;
698 patricia->num_active_node++;
699
700 if (differ_bit < patricia->maxbits && BIT_TEST(addr[differ_bit >> 3], 0x80 >> (differ_bit & 0x07)))
701 {
702 glue->r = new_node;
703 glue->l = node;
704 }
705 else
706 {
707 glue->r = node;
708 glue->l = new_node;
709 }
710
711 new_node->parent = glue;
712
713 if (node->parent == NULL)
714 {
715 assert(patricia->head == node);
716 patricia->head = glue;
717 }
718 else if (node->parent->r == node)
719 {
720 node->parent->r = glue;
721 }
722 else
723 {
724 node->parent->l = glue;
725 }
726
727 node->parent = glue;
728 #ifdef PATRICIA_DEBUG
729 fprintf(stderr, "patricia_lookup: new_node #4 %s/%d (glue+node)\n",
730 patricia_prefix_toa(prefix), prefix->bitlen);
731 #endif /* PATRICIA_DEBUG */
732 }
733
734 return new_node;
735 }
736
737 void
738 patricia_remove(patricia_tree_t *patricia, patricia_node_t *node)
739 {
740 patricia_node_t *parent, *child;
741
742 assert(patricia);
743 assert(node);
744
745 if (node->r && node->l)
746 {
747 #ifdef PATRICIA_DEBUG
748 fprintf(stderr, "patricia_remove: #0 %s/%d (r & l)\n",
749 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
750 #endif /* PATRICIA_DEBUG */
751
752 /*
753 * This might be a placeholder node -- have to check and make sure
754 * there is a prefix associated with it !
755 */
756 if (node->prefix)
757 Deref_Prefix(node->prefix);
758
759 node->prefix = NULL;
760 /* Also I needed to clear data pointer -- masaki */
761 node->data = NULL;
762 return;
763 }
764
765 if (node->r == NULL && node->l == NULL)
766 {
767 #ifdef PATRICIA_DEBUG
768 fprintf(stderr, "patricia_remove: #1 %s/%d (!r & !l)\n",
769 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
770 #endif /* PATRICIA_DEBUG */
771
772 parent = node->parent;
773 Deref_Prefix(node->prefix);
774 xfree(node);
775 patricia->num_active_node--;
776
777 if (parent == NULL)
778 {
779 assert(patricia->head == node);
780 patricia->head = NULL;
781 return;
782 }
783
784 if (parent->r == node)
785 {
786 parent->r = NULL;
787 child = parent->l;
788 }
789 else
790 {
791 assert(parent->l == node);
792
793 parent->l = NULL;
794 child = parent->r;
795 }
796
797 if (parent->prefix)
798 return;
799
800 /* We need to remove parent too */
801 if (parent->parent == NULL)
802 {
803 assert(patricia->head == parent);
804 patricia->head = child;
805 }
806 else if (parent->parent->r == parent)
807 {
808 parent->parent->r = child;
809 }
810 else
811 {
812 assert(parent->parent->l == parent);
813 parent->parent->l = child;
814 }
815
816 child->parent = parent->parent;
817 xfree(parent);
818 patricia->num_active_node--;
819 return;
820 }
821
822 #ifdef PATRICIA_DEBUG
823 fprintf(stderr, "patricia_remove: #2 %s/%d (r ^ l)\n",
824 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
825 #endif /* PATRICIA_DEBUG */
826
827 if (node->r)
828 {
829 child = node->r;
830 }
831 else
832 {
833 assert(node->l);
834 child = node->l;
835 }
836
837 parent = node->parent;
838 child->parent = parent;
839
840 Deref_Prefix(node->prefix);
841 xfree(node);
842 patricia->num_active_node--;
843
844 if (parent == NULL)
845 {
846 assert(patricia->head == node);
847 patricia->head = child;
848 return;
849 }
850
851 if (parent->r == node)
852 {
853 parent->r = child;
854 }
855 else
856 {
857 assert(parent->l == node);
858 parent->l = child;
859 }
860 }
861
862 /* { from demo.c */
863 patricia_node_t *
864 patricia_make_and_lookup(patricia_tree_t *tree, const char *string)
865 {
866 prefix_t *prefix = ascii2prefix(0, string);
867
868 if (prefix)
869 {
870 patricia_node_t *node = patricia_lookup(tree, prefix);
871 Deref_Prefix(prefix);
872 return node;
873 }
874
875 return NULL;
876 }
877
878 patricia_node_t *
879 patricia_make_and_lookup_addr(patricia_tree_t *tree, struct sockaddr *addr, int bitlen)
880 {
881 int family;
882 void *dest;
883
884 if (addr->sa_family == AF_INET6)
885 {
886 if (bitlen == 0 || bitlen > 128)
887 bitlen = 128;
888 family = AF_INET6;
889 dest = &((struct sockaddr_in6 *)addr)->sin6_addr;
890 }
891 else
892 {
893 if (bitlen == 0 || bitlen > 32)
894 bitlen = 32;
895 family = AF_INET;
896 dest = &((struct sockaddr_in *)addr)->sin_addr;
897 }
898
899 prefix_t *prefix = New_Prefix(family, dest, bitlen);
900 if (prefix)
901 {
902 patricia_node_t *node = patricia_lookup(tree, prefix);
903 Deref_Prefix(prefix);
904 return node;
905 }
906
907 return NULL;
908 }
909
910 void
911 patricia_lookup_then_remove(patricia_tree_t *tree, const char *string)
912 {
913 patricia_node_t *node = patricia_try_search_exact(tree, string);
914 if (node)
915 patricia_remove(tree, node);
916 }
917
918 patricia_node_t *
919 patricia_try_search_exact(patricia_tree_t *tree, const char *string)
920 {
921 prefix_t *prefix = ascii2prefix(0, string);
922
923 if (prefix)
924 {
925 patricia_node_t *node = patricia_search_exact(tree, prefix);
926 Deref_Prefix(prefix);
927 return node;
928 }
929
930 return NULL;
931 }
932
933 patricia_node_t *
934 patricia_try_search_best(patricia_tree_t *tree, const char *string)
935 {
936 prefix_t *prefix = ascii2prefix(0, string);
937
938 if (prefix)
939 {
940 patricia_node_t *node = patricia_search_best(tree, prefix);
941 Deref_Prefix(prefix);
942 return node;
943 }
944
945 return NULL;
946 }
947
948 patricia_node_t *
949 patricia_try_search_exact_addr(patricia_tree_t *tree, struct sockaddr *addr, int bitlen)
950 {
951 int family;
952 void *dest;
953
954 if (addr->sa_family == AF_INET6)
955 {
956 if (bitlen == 0 || bitlen > 128)
957 bitlen = 128;
958 family = AF_INET6;
959 dest = &((struct sockaddr_in6 *)addr)->sin6_addr;
960 }
961 else
962 {
963 if (bitlen == 0 || bitlen > 32)
964 bitlen = 32;
965 family = AF_INET;
966 dest = &((struct sockaddr_in *)addr)->sin_addr;
967 }
968
969 prefix_t *prefix = New_Prefix(family, dest, bitlen);
970 if (prefix)
971 {
972 patricia_node_t *node = patricia_search_exact(tree, prefix);
973 Deref_Prefix(prefix);
974 return node;
975 }
976
977 return NULL;
978 }
979
980 patricia_node_t *
981 patricia_try_search_best_addr(patricia_tree_t *tree, struct sockaddr *addr, int bitlen)
982 {
983 int family;
984 void *dest;
985
986 if (addr->sa_family == AF_INET6)
987 {
988 if (bitlen == 0 || bitlen > 128)
989 bitlen = 128;
990 family = AF_INET6;
991 dest = &((struct sockaddr_in6 *)addr)->sin6_addr;
992 }
993 else
994 {
995 if (bitlen == 0 || bitlen > 32)
996 bitlen = 32;
997 family = AF_INET;
998 dest = &((struct sockaddr_in *)addr)->sin_addr;
999 }
1000
1001 prefix_t *prefix = New_Prefix(family, dest, bitlen);
1002 if (prefix)
1003 {
1004 patricia_node_t *node = patricia_search_best(tree, prefix);
1005 Deref_Prefix(prefix);
1006 return node;
1007 }
1008
1009 return NULL;
1010 }
1011 /* } */

Properties

Name Value
svn:eol-style native
svn:keywords Id