ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/svn/hopm/trunk/src/patricia.c
Revision: 7848
Committed: Sun Nov 6 18:05:24 2016 UTC (7 years, 4 months ago) by michael
Content type: text/x-csrc
Original Path: ircd-hybrid/trunk/src/patricia.c
File size: 22934 byte(s)
Log Message:
- patricia.c: style corrections; remove unused header includes

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)));
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)
115 {
116 prefix = xcalloc(sizeof(prefix_t));
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 int bitlen, maxbitlen = 0;
141 union
142 {
143 struct in_addr sin;
144 struct in6_addr sin6;
145 } sin;
146
147 assert(string);
148
149 /* Easy way to handle both families */
150 if (family == 0)
151 {
152 family = AF_INET;
153
154 if (strchr (string, ':'))
155 family = AF_INET6;
156 }
157
158 if (family == AF_INET)
159 maxbitlen = sizeof(struct in_addr) * 8;
160 else if (family == AF_INET6)
161 maxbitlen = sizeof(struct in6_addr) * 8;
162
163 const char *const cp = strchr(string, '/');
164 if (cp)
165 {
166 char save[MAXLINE];
167
168 bitlen = atoi(cp + 1);
169
170 /* *cp = '\0'; */
171 /* Copy the string to save. Avoid destroying the string */
172 assert(cp - string < MAXLINE);
173 memcpy(save, string, cp - string);
174
175 save[cp - string] = '\0';
176 string = save;
177
178 if (bitlen < 0 || bitlen > maxbitlen)
179 bitlen = maxbitlen;
180 }
181 else
182 bitlen = maxbitlen;
183
184 if (inet_pton(family, string, &sin) <= 0)
185 return NULL;
186 return New_Prefix(family, &sin, bitlen);
187 }
188
189 static prefix_t *
190 Ref_Prefix(prefix_t *prefix)
191 {
192 if (prefix == NULL)
193 return NULL;
194
195 if (prefix->ref_count == 0)
196 /* Make a copy in case of a static prefix */
197 return New_Prefix2(prefix->family, &prefix->add, prefix->bitlen, NULL);
198
199 prefix->ref_count++;
200
201 /* fprintf(stderr, "[A %s, %d]\n", patricia_prefix_toa(prefix), prefix->ref_count); */
202 return prefix;
203 }
204
205 static void
206 Deref_Prefix(prefix_t *prefix)
207 {
208 if (prefix == NULL)
209 return;
210
211 /* For secure programming, raise an assert. No static prefix can call this */
212 assert(prefix->ref_count > 0);
213 if (--prefix->ref_count <= 0)
214 xfree(prefix);
215 }
216 /* } */
217
218 /* #define PATRICIA_DEBUG 1 */
219
220 /* these routines support continuous mask only */
221
222 patricia_tree_t *
223 patricia_new(unsigned int maxbits)
224 {
225 patricia_tree_t *patricia = xcalloc(sizeof *patricia);
226 patricia->maxbits = maxbits;
227
228 assert(maxbits <= PATRICIA_MAXBITS); /* XXX */
229 return patricia;
230 }
231
232 /*
233 * if func is supplied, it will be called as func(node->data)
234 * before deleting the node
235 */
236 void
237 patricia_clear(patricia_tree_t *patricia, void (*func)(void *))
238 {
239 assert(patricia);
240
241 if (patricia->head)
242 {
243 patricia_node_t *Xstack[PATRICIA_MAXBITS + 1];
244 patricia_node_t **Xsp = Xstack;
245 patricia_node_t *Xrn = patricia->head;
246
247 while (Xrn)
248 {
249 patricia_node_t *l = Xrn->l;
250 patricia_node_t *r = Xrn->r;
251
252 if (Xrn->prefix)
253 {
254 Deref_Prefix(Xrn->prefix);
255
256 if (Xrn->data && func)
257 func(Xrn->data);
258 }
259 else
260 {
261 assert(Xrn->data == NULL);
262 }
263
264 xfree(Xrn);
265 patricia->num_active_node--;
266
267 if (l)
268 {
269 if (r)
270 {
271 *Xsp++ = r;
272 }
273
274 Xrn = l;
275 }
276 else if (r)
277 {
278 Xrn = r;
279 }
280 else if (Xsp != Xstack)
281 {
282 Xrn = *(--Xsp);
283 }
284 else
285 {
286 Xrn = NULL;
287 }
288 }
289 }
290
291 assert(patricia->num_active_node == 0);
292 /* xfree (patricia); */
293 }
294
295 void
296 patricia_destroy(patricia_tree_t *patricia, void (*func)(void *))
297 {
298 patricia_clear(patricia, func);
299 xfree(patricia);
300 }
301
302 /*
303 * if func is supplied, it will be called as func(node->prefix, node->data)
304 */
305 void
306 patricia_process(patricia_tree_t *patricia, void (*func)(prefix_t *, void *))
307 {
308 patricia_node_t *node;
309
310 assert(func);
311
312 PATRICIA_WALK(patricia->head, node) {
313 func(node->prefix, node->data);
314 } PATRICIA_WALK_END;
315 }
316
317 patricia_node_t *
318 patricia_search_exact(patricia_tree_t *patricia, prefix_t *prefix)
319 {
320 patricia_node_t *node;
321 unsigned char *addr;
322 unsigned int bitlen;
323
324 assert(patricia);
325 assert(prefix);
326 assert(prefix->bitlen <= patricia->maxbits);
327
328 if (patricia->head == NULL)
329 return NULL;
330
331 node = patricia->head;
332 addr = prefix_touchar(prefix);
333 bitlen = prefix->bitlen;
334
335 while (node->bit < bitlen)
336 {
337 if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
338 {
339 #ifdef PATRICIA_DEBUG
340 if (node->prefix)
341 fprintf(stderr, "patricia_search_exact: take right %s/%d\n",
342 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
343 else
344 fprintf(stderr, "patricia_search_exact: take right at %u\n", node->bit);
345 #endif /* PATRICIA_DEBUG */
346 node = node->r;
347 }
348 else
349 {
350 #ifdef PATRICIA_DEBUG
351 if (node->prefix)
352 fprintf(stderr, "patricia_search_exact: take left %s/%d\n",
353 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
354 else
355 fprintf(stderr, "patricia_search_exact: take left at %u\n", node->bit);
356 #endif /* PATRICIA_DEBUG */
357 node = node->l;
358 }
359
360 if (node == NULL)
361 return NULL;
362 }
363
364 #ifdef PATRICIA_DEBUG
365 if (node->prefix)
366 fprintf(stderr, "patricia_search_exact: stop at %s/%d\n",
367 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
368 else
369 fprintf(stderr, "patricia_search_exact: stop at %u\n", node->bit);
370 #endif /* PATRICIA_DEBUG */
371
372 if (node->bit > bitlen || node->prefix == NULL)
373 return NULL;
374
375 assert(node->bit == bitlen);
376 assert(node->bit == node->prefix->bitlen);
377
378 if (comp_with_mask(prefix_tochar(node->prefix), prefix_tochar(prefix), bitlen))
379 {
380 #ifdef PATRICIA_DEBUG
381 fprintf(stderr, "patricia_search_exact: found %s/%d\n",
382 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
383 #endif /* PATRICIA_DEBUG */
384 return node;
385 }
386
387 return NULL;
388 }
389
390 /* if inclusive != 0, "best" may be the given prefix itself */
391 patricia_node_t *
392 patricia_search_best2(patricia_tree_t *patricia, prefix_t *prefix, int inclusive)
393 {
394 patricia_node_t *node;
395 patricia_node_t *stack[PATRICIA_MAXBITS + 1];
396 unsigned char *addr;
397 unsigned int bitlen;
398 int cnt = 0;
399
400 assert(patricia);
401 assert(prefix);
402 assert(prefix->bitlen <= patricia->maxbits);
403
404 if (patricia->head == NULL)
405 return NULL;
406
407 node = patricia->head;
408 addr = prefix_touchar(prefix);
409 bitlen = prefix->bitlen;
410
411 while (node->bit < bitlen)
412 {
413 if (node->prefix)
414 {
415 #ifdef PATRICIA_DEBUG
416 fprintf(stderr, "patricia_search_best: push %s/%d\n",
417 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
418 #endif /* PATRICIA_DEBUG */
419 stack[cnt++] = node;
420 }
421
422 if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
423 {
424 #ifdef PATRICIA_DEBUG
425 if (node->prefix)
426 fprintf(stderr, "patricia_search_best: take right %s/%d\n",
427 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
428 else
429 fprintf(stderr, "patricia_search_best: take right at %u\n", node->bit);
430 #endif /* PATRICIA_DEBUG */
431 node = node->r;
432 }
433 else
434 {
435 #ifdef PATRICIA_DEBUG
436 if (node->prefix)
437 fprintf(stderr, "patricia_search_best: take left %s/%d\n",
438 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
439 else
440 fprintf(stderr, "patricia_search_best: take left at %u\n", node->bit);
441 #endif /* PATRICIA_DEBUG */
442 node = node->l;
443 }
444
445 if (node == NULL)
446 break;
447 }
448
449 if (inclusive && node && node->prefix)
450 stack[cnt++] = node;
451
452 #ifdef PATRICIA_DEBUG
453 if (node == NULL)
454 fprintf(stderr, "patricia_search_best: stop at null\n");
455 else if (node->prefix)
456 fprintf(stderr, "patricia_search_best: stop at %s/%d\n",
457 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
458 else
459 fprintf(stderr, "patricia_search_best: stop at %u\n", node->bit);
460 #endif /* PATRICIA_DEBUG */
461
462 if (cnt <= 0)
463 return NULL;
464
465 while (--cnt >= 0)
466 {
467 node = stack[cnt];
468 #ifdef PATRICIA_DEBUG
469 fprintf(stderr, "patricia_search_best: pop %s/%d\n",
470 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
471 #endif /* PATRICIA_DEBUG */
472
473 if (comp_with_mask(prefix_tochar(node->prefix),
474 prefix_tochar(prefix), node->prefix->bitlen) && node->prefix->bitlen <= bitlen)
475 {
476 #ifdef PATRICIA_DEBUG
477 fprintf(stderr, "patricia_search_best: found %s/%d\n",
478 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
479 #endif /* PATRICIA_DEBUG */
480 return node;
481 }
482 }
483
484 return NULL;
485 }
486
487 patricia_node_t *
488 patricia_search_best(patricia_tree_t *patricia, prefix_t *prefix)
489 {
490 return patricia_search_best2(patricia, prefix, 1);
491 }
492
493 patricia_node_t *
494 patricia_lookup(patricia_tree_t *patricia, prefix_t *prefix)
495 {
496 patricia_node_t *node, *new_node, *parent, *glue;
497 unsigned char *addr, *test_addr;
498 unsigned int bitlen, check_bit, differ_bit;
499 int j, r;
500
501 assert(patricia);
502 assert(prefix);
503 assert(prefix->bitlen <= patricia->maxbits);
504
505 if (patricia->head == NULL)
506 {
507 node = xcalloc(sizeof *node);
508 node->bit = prefix->bitlen;
509 node->prefix = Ref_Prefix (prefix);
510 patricia->head = node;
511 #ifdef PATRICIA_DEBUG
512 fprintf(stderr, "patricia_lookup: new_node #0 %s/%d (head)\n",
513 patricia_prefix_toa(prefix), prefix->bitlen);
514 #endif /* PATRICIA_DEBUG */
515 patricia->num_active_node++;
516 return node;
517 }
518
519 addr = prefix_touchar(prefix);
520 bitlen = prefix->bitlen;
521 node = patricia->head;
522
523 while (node->bit < bitlen || node->prefix == NULL)
524 {
525 if (node->bit < patricia->maxbits && BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
526 {
527 if (node->r == NULL)
528 break;
529 #ifdef PATRICIA_DEBUG
530 if (node->prefix)
531 fprintf(stderr, "patricia_lookup: take right %s/%d\n",
532 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
533 else
534 fprintf(stderr, "patricia_lookup: take right at %u\n", node->bit);
535 #endif /* PATRICIA_DEBUG */
536
537 node = node->r;
538 }
539 else
540 {
541 if (node->l == NULL)
542 break;
543 #ifdef PATRICIA_DEBUG
544 if (node->prefix)
545 fprintf(stderr, "patricia_lookup: take left %s/%d\n",
546 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
547 else
548 fprintf(stderr, "patricia_lookup: take left at %u\n", node->bit);
549 #endif /* PATRICIA_DEBUG */
550
551 node = node->l;
552 }
553
554 assert(node);
555 }
556
557 assert(node->prefix);
558 #ifdef PATRICIA_DEBUG
559 fprintf(stderr, "patricia_lookup: stop at %s/%d\n",
560 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
561 #endif /* PATRICIA_DEBUG */
562
563 test_addr = prefix_touchar(node->prefix);
564
565 /* Find the first bit different */
566 check_bit = (node->bit < bitlen) ? node->bit : bitlen;
567 differ_bit = 0;
568
569 for (unsigned int i = 0; i * 8 < check_bit; i++)
570 {
571 if ((r = (addr[i] ^ test_addr[i])) == 0)
572 {
573 differ_bit = (i + 1) * 8;
574 continue;
575 }
576
577 /* I know the better way, but for now */
578 for (j = 0; j < 8; j++)
579 if (BIT_TEST(r, (0x80 >> j)))
580 break;
581
582 /* Must be found */
583 assert(j < 8);
584 differ_bit = i * 8 + j;
585 break;
586 }
587
588 if (differ_bit > check_bit)
589 differ_bit = check_bit;
590 #ifdef PATRICIA_DEBUG
591 fprintf(stderr, "patricia_lookup: differ_bit %d\n", differ_bit);
592 #endif /* PATRICIA_DEBUG */
593
594 parent = node->parent;
595
596 while (parent && parent->bit >= differ_bit)
597 {
598 node = parent;
599 parent = node->parent;
600
601 #ifdef PATRICIA_DEBUG
602 if (node->prefix)
603 fprintf(stderr, "patricia_lookup: up to %s/%d\n",
604 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
605 else
606 fprintf(stderr, "patricia_lookup: up to %u\n", node->bit);
607 #endif /* PATRICIA_DEBUG */
608 }
609
610 if (differ_bit == bitlen && node->bit == bitlen)
611 {
612 if (node->prefix)
613 {
614 #ifdef PATRICIA_DEBUG
615 fprintf(stderr, "patricia_lookup: found %s/%d\n",
616 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
617 #endif /* PATRICIA_DEBUG */
618
619 return node;
620 }
621
622 node->prefix = Ref_Prefix(prefix);
623 #ifdef PATRICIA_DEBUG
624 fprintf(stderr, "patricia_lookup: new node #1 %s/%d (glue mod)\n",
625 patricia_prefix_toa(prefix), prefix->bitlen);
626 #endif /* PATRICIA_DEBUG */
627
628 assert(node->data == NULL);
629 return node;
630 }
631
632 new_node = xcalloc(sizeof *new_node);
633 new_node->bit = prefix->bitlen;
634 new_node->prefix = Ref_Prefix(prefix);
635 patricia->num_active_node++;
636
637 if (node->bit == differ_bit)
638 {
639 new_node->parent = node;
640
641 if (node->bit < patricia->maxbits && BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
642 {
643 assert(node->r == NULL);
644 node->r = new_node;
645 }
646 else
647 {
648 assert(node->l == NULL);
649 node->l = new_node;
650 }
651 #ifdef PATRICIA_DEBUG
652 fprintf(stderr, "patricia_lookup: new_node #2 %s/%d (child)\n",
653 patricia_prefix_toa(prefix), prefix->bitlen);
654 #endif /* PATRICIA_DEBUG */
655 return new_node;
656 }
657
658 if (bitlen == differ_bit)
659 {
660 if (bitlen < patricia->maxbits && BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07)))
661 {
662 new_node->r = node;
663 }
664 else
665 {
666 new_node->l = node;
667 }
668
669 new_node->parent = node->parent;
670
671 if (node->parent == NULL)
672 {
673 assert(patricia->head == node);
674 patricia->head = new_node;
675 }
676 else if (node->parent->r == node)
677 {
678 node->parent->r = new_node;
679 }
680 else
681 {
682 node->parent->l = new_node;
683 }
684
685 node->parent = new_node;
686 #ifdef PATRICIA_DEBUG
687 fprintf(stderr, "patricia_lookup: new_node #3 %s/%d (parent)\n",
688 patricia_prefix_toa(prefix), prefix->bitlen);
689 #endif /* PATRICIA_DEBUG */
690 }
691 else
692 {
693 glue = xcalloc(sizeof *glue);
694 glue->bit = differ_bit;
695 glue->parent = node->parent;
696 patricia->num_active_node++;
697
698 if (differ_bit < patricia->maxbits && BIT_TEST(addr[differ_bit >> 3], 0x80 >> (differ_bit & 0x07)))
699 {
700 glue->r = new_node;
701 glue->l = node;
702 }
703 else
704 {
705 glue->r = node;
706 glue->l = new_node;
707 }
708
709 new_node->parent = glue;
710
711 if (node->parent == NULL)
712 {
713 assert(patricia->head == node);
714 patricia->head = glue;
715 }
716 else if (node->parent->r == node)
717 {
718 node->parent->r = glue;
719 }
720 else
721 {
722 node->parent->l = glue;
723 }
724
725 node->parent = glue;
726 #ifdef PATRICIA_DEBUG
727 fprintf(stderr, "patricia_lookup: new_node #4 %s/%d (glue+node)\n",
728 patricia_prefix_toa(prefix), prefix->bitlen);
729 #endif /* PATRICIA_DEBUG */
730 }
731
732 return new_node;
733 }
734
735 void
736 patricia_remove(patricia_tree_t *patricia, patricia_node_t *node)
737 {
738 patricia_node_t *parent, *child;
739
740 assert(patricia);
741 assert(node);
742
743 if (node->r && node->l)
744 {
745 #ifdef PATRICIA_DEBUG
746 fprintf(stderr, "patricia_remove: #0 %s/%d (r & l)\n",
747 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
748 #endif /* PATRICIA_DEBUG */
749
750 /*
751 * This might be a placeholder node -- have to check and make sure
752 * there is a prefix associated with it !
753 */
754 if (node->prefix != NULL)
755 Deref_Prefix(node->prefix);
756
757 node->prefix = NULL;
758 /* Also I needed to clear data pointer -- masaki */
759 node->data = NULL;
760 return;
761 }
762
763 if (node->r == NULL && node->l == NULL)
764 {
765 #ifdef PATRICIA_DEBUG
766 fprintf(stderr, "patricia_remove: #1 %s/%d (!r & !l)\n",
767 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
768 #endif /* PATRICIA_DEBUG */
769
770 parent = node->parent;
771 Deref_Prefix(node->prefix);
772 xfree(node);
773 patricia->num_active_node--;
774
775 if (parent == NULL)
776 {
777 assert(patricia->head == node);
778 patricia->head = NULL;
779 return;
780 }
781
782 if (parent->r == node)
783 {
784 parent->r = NULL;
785 child = parent->l;
786 }
787 else
788 {
789 assert(parent->l == node);
790
791 parent->l = NULL;
792 child = parent->r;
793 }
794
795 if (parent->prefix)
796 return;
797
798 /* We need to remove parent too */
799 if (parent->parent == NULL)
800 {
801 assert(patricia->head == parent);
802 patricia->head = child;
803 }
804 else if (parent->parent->r == parent)
805 {
806 parent->parent->r = child;
807 }
808 else
809 {
810 assert(parent->parent->l == parent);
811 parent->parent->l = child;
812 }
813
814 child->parent = parent->parent;
815 xfree(parent);
816 patricia->num_active_node--;
817 return;
818 }
819
820 #ifdef PATRICIA_DEBUG
821 fprintf(stderr, "patricia_remove: #2 %s/%d (r ^ l)\n",
822 patricia_prefix_toa(node->prefix), node->prefix->bitlen);
823 #endif /* PATRICIA_DEBUG */
824
825 if (node->r)
826 {
827 child = node->r;
828 }
829 else
830 {
831 assert(node->l);
832 child = node->l;
833 }
834
835 parent = node->parent;
836 child->parent = parent;
837
838 Deref_Prefix(node->prefix);
839 xfree(node);
840 patricia->num_active_node--;
841
842 if (parent == NULL)
843 {
844 assert(patricia->head == node);
845 patricia->head = child;
846 return;
847 }
848
849 if (parent->r == node)
850 {
851 parent->r = child;
852 }
853 else
854 {
855 assert(parent->l == node);
856 parent->l = child;
857 }
858 }
859
860 /* { from demo.c */
861 patricia_node_t *
862 patricia_make_and_lookup(patricia_tree_t *tree, const char *string)
863 {
864 prefix_t *prefix = ascii2prefix(0, string);
865
866 if (prefix)
867 {
868 patricia_node_t *node = patricia_lookup(tree, prefix);
869 Deref_Prefix(prefix);
870 return node;
871 }
872
873 return NULL;
874 }
875
876 void
877 patricia_lookup_then_remove(patricia_tree_t *tree, const char *string)
878 {
879 patricia_node_t *node = patricia_try_search_exact(tree, string);
880 if (node)
881 patricia_remove(tree, node);
882 }
883
884 patricia_node_t *
885 patricia_try_search_exact(patricia_tree_t *tree, const char *string)
886 {
887 prefix_t *prefix = ascii2prefix(0, string);
888
889 if (prefix)
890 {
891 patricia_node_t *node = patricia_search_exact(tree, prefix);
892 Deref_Prefix(prefix);
893 return node;
894 }
895
896 return NULL;
897 }
898
899 patricia_node_t *
900 patricia_try_search_best(patricia_tree_t *tree, const char *string)
901 {
902 prefix_t *prefix = ascii2prefix(0, string);
903
904 if (prefix)
905 {
906 patricia_node_t *node = patricia_search_best(tree, prefix);
907 Deref_Prefix(prefix);
908 return node;
909 }
910
911 return NULL;
912 }
913
914 patricia_node_t *
915 patricia_try_search_exact_addr(patricia_tree_t *tree, struct sockaddr *addr, int bitlen)
916 {
917 int family;
918 void *dest;
919
920 if (addr->sa_family == AF_INET6)
921 {
922 if (bitlen == 0 || bitlen > 128)
923 bitlen = 128;
924 family = AF_INET6;
925 dest = &((struct sockaddr_in6 *)addr)->sin6_addr;
926 }
927 else
928 {
929 if (bitlen == 0 || bitlen > 32)
930 bitlen = 32;
931 family = AF_INET;
932 dest = &((struct sockaddr_in *)addr)->sin_addr;
933 }
934
935 prefix_t *prefix = New_Prefix(family, dest, bitlen);
936 if (prefix)
937 {
938 patricia_node_t *node = patricia_search_exact(tree, prefix);
939 Deref_Prefix(prefix);
940 return node;
941 }
942
943 return NULL;
944 }
945
946 patricia_node_t *
947 patricia_try_search_best_addr(patricia_tree_t *tree, struct sockaddr *addr, int bitlen)
948 {
949 int family;
950 void *dest;
951
952 if (addr->sa_family == AF_INET6)
953 {
954 if (bitlen == 0 || bitlen > 128)
955 bitlen = 128;
956 family = AF_INET6;
957 dest = &((struct sockaddr_in6 *)addr)->sin6_addr;
958 }
959 else
960 {
961 if (bitlen == 0 || bitlen > 32)
962 bitlen = 32;
963 family = AF_INET;
964 dest = &((struct sockaddr_in *)addr)->sin_addr;
965 }
966
967 prefix_t *prefix = New_Prefix(family, dest, bitlen);
968 if (prefix)
969 {
970 patricia_node_t *node = patricia_search_best(tree, prefix);
971 Deref_Prefix(prefix);
972 return node;
973 }
974
975 return NULL;
976 }
977 /* } */

Properties

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