]>
jfr.im git - solanum.git/blob - libratbox/src/patricia.c
2 * Yanked out of Net::Patricia by Aaron Sethman <androsyn@ratbox.org>
4 * This was then yanked out of the ratbox/devel/src tree and stuffed into
5 * libratbox and had function names changed, but otherwise not really altered.
7 * $Id: patricia.c 24244 2007-08-22 19:04:55Z androsyn $
8 * Dave Plonka <plonka@doit.wisc.edu>
10 * This product includes software developed by the University of Michigan,
11 * Merit Network, Inc., and their contributors.
13 * This file had been called "radix.c" in the MRT sources.
15 * I renamed it to "patricia.c" since it's not an implementation of a general
16 * radix trie. Also I pulled in various requirements from "prefix.c" and
17 * "demo.c" so that it could be used as a standalone API.
19 * This product includes software developed by the University of Michigan, Merit
20 * Network, Inc., and their contributors.
23 #include <libratbox_config.h>
24 #include <ratbox_lib.h>
26 /* Enable both of these to debug patricia.c
28 * #define PATRICIA_DEBUG 1
31 #define PREFIX_HEAP_COUNT 1024
32 #define NODE_HEAP_COUNT 1024
33 #define PATRICIA_HEAP_COUNT 128
36 rb_init_patricia(void)
42 * convert prefix information to bytes
45 prefix_tochar(rb_prefix_t
*prefix
)
50 return ((uint8_t *)&prefix
->add
.sin
);
54 comp_with_mask(void *addr
, void *dest
, unsigned int mask
)
57 if( /* mask/8 == 0 || */ memcmp(addr
, dest
, mask
/ 8) == 0)
60 int m
= ((-1) << (8 - (mask
% 8)));
62 if(mask
% 8 == 0 || (((uint8_t *)addr
)[n
] & m
) == (((uint8_t *)dest
)[n
] & m
))
70 prefix_toa2x(rb_prefix_t
*prefix
, char *buf
, int buf_len
, int with_len
)
75 strcpy(buf
, "(NULL)");
78 inet_ntop(prefix
->family
, &prefix
->add
.sin
, buf
, buf_len
);
81 rb_snprintf(tmp
, sizeof(tmp
), "/%d", prefix
->bitlen
);
88 * convert prefix information to ascii string
92 prefix_toa2(rb_prefix_t
*prefix
, char *buff
, int buf_len
)
94 return (prefix_toa2x(prefix
, buff
, buf_len
, 0));
98 prefix_toa(rb_prefix_t
*prefix
)
101 static char buf
[INET6_ADDRSTRLEN
+ 6];
103 static char buf
[16 + 6];
105 return (prefix_toa2(prefix
, buf
, sizeof(buf
)));
109 New_Prefix2(int family
, void *dest
, int bitlen
, rb_prefix_t
*prefix
)
111 int dynamic_allocated
= 0;
113 int default_bitlen
= 128;
115 int default_bitlen
= 32;
119 if(family
== AF_INET6
)
121 default_bitlen
= 128;
124 prefix
= rb_malloc(sizeof(rb_prefix_t
));
127 memcpy(&prefix
->add
.sin6
, dest
, 16);
131 if(family
== AF_INET
)
135 prefix
= rb_malloc(sizeof(rb_prefix_t
));
138 memcpy(&prefix
->add
.sin
, dest
, 4);
145 prefix
->bitlen
= (bitlen
>= 0) ? bitlen
: default_bitlen
;
146 prefix
->family
= family
;
147 prefix
->ref_count
= 0;
148 if(dynamic_allocated
)
156 New_Prefix(int family
, void *dest
, int bitlen
)
158 return (New_Prefix2(family
, dest
, bitlen
, NULL
));
164 ascii2prefix(int family
, const char *string
)
166 long bitlen
, maxbitlen
= 0;
168 struct in_addr sinaddr
;
170 struct in6_addr sinaddr6
;
178 /* easy way to handle both families */
183 if(strchr(string
, ':'))
187 if(family
== AF_INET
)
192 else if(family
== AF_INET6
)
198 if((cp
= strchr(string
, '/')) != NULL
)
200 bitlen
= atol(cp
+ 1);
202 /* copy the string to save. Avoid destroying the string */
203 assert(cp
- string
< MAXLINE
);
204 memcpy(save
, string
, cp
- string
);
205 save
[cp
- string
] = '\0';
207 if(bitlen
<= 0 || bitlen
> maxbitlen
)
215 if(family
== AF_INET
)
217 if((result
= rb_inet_pton(AF_INET
, string
, &sinaddr
)) <= 0)
219 return (New_Prefix(AF_INET
, &sinaddr
, bitlen
));
222 else if(family
== AF_INET6
)
224 if((result
= rb_inet_pton(AF_INET6
, string
, &sinaddr6
)) <= 0)
226 return (New_Prefix(AF_INET6
, &sinaddr6
, bitlen
));
234 Ref_Prefix(rb_prefix_t
*prefix
)
238 if(prefix
->ref_count
== 0)
240 /* make a copy in case of a static prefix */
241 return (New_Prefix2(prefix
->family
, &prefix
->add
, prefix
->bitlen
, NULL
));
248 Deref_Prefix(rb_prefix_t
*prefix
)
252 /* for secure programming, raise an assert. no static prefix can call this */
253 assert(prefix
->ref_count
> 0);
256 assert(prefix
->ref_count
>= 0);
257 if(prefix
->ref_count
<= 0)
266 // #define PATRICIA_DEBUG 1
268 static int num_active_patricia
= 0;
270 /* these routines support continuous mask only */
273 rb_new_patricia(int maxbits
)
275 rb_patricia_tree_t
*patricia
= rb_malloc(sizeof(rb_patricia_tree_t
));
277 patricia
->maxbits
= maxbits
;
278 patricia
->head
= NULL
;
279 patricia
->num_active_node
= 0;
280 assert(maxbits
<= RB_PATRICIA_MAXBITS
); /* XXX */
281 num_active_patricia
++;
287 * if func is supplied, it will be called as func(node->data)
288 * before deleting the node
292 rb_clear_patricia(rb_patricia_tree_t
*patricia
, void (*func
) (void *))
298 rb_patricia_node_t
*Xstack
[RB_PATRICIA_MAXBITS
+ 1];
299 rb_patricia_node_t
**Xsp
= Xstack
;
300 rb_patricia_node_t
*Xrn
= patricia
->head
;
304 rb_patricia_node_t
*l
= Xrn
->l
;
305 rb_patricia_node_t
*r
= Xrn
->r
;
309 Deref_Prefix(Xrn
->prefix
);
310 if(Xrn
->data
&& func
)
315 assert(Xrn
->data
== NULL
);
318 patricia
->num_active_node
--;
332 else if(Xsp
!= Xstack
)
338 Xrn
= (rb_patricia_node_t
*)0;
342 assert(patricia
->num_active_node
== 0);
348 rb_destroy_patricia(rb_patricia_tree_t
*patricia
, void (*func
) (void *))
350 rb_clear_patricia(patricia
, func
);
351 num_active_patricia
--;
356 * if func is supplied, it will be called as func(node->prefix, node->data)
360 rb_patricia_process(rb_patricia_tree_t
*patricia
, void (*func
) (rb_prefix_t
*, void *))
362 rb_patricia_node_t
*node
;
365 RB_PATRICIA_WALK(patricia
->head
, node
)
367 func(node
->prefix
, node
->data
);
369 RB_PATRICIA_WALK_END
;
373 rb_patricia_search_exact(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
)
375 rb_patricia_node_t
*node
;
381 assert(prefix
->bitlen
<= patricia
->maxbits
);
383 if(patricia
->head
== NULL
)
386 node
= patricia
->head
;
387 addr
= rb_prefix_touchar(prefix
);
388 bitlen
= prefix
->bitlen
;
390 while(node
->bit
< bitlen
)
393 if(BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
395 #ifdef PATRICIA_DEBUG
398 "patricia_search_exact: take right %s/%d\n",
399 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
402 "patricia_search_exact: take right at %d\n", node
->bit
);
403 #endif /* PATRICIA_DEBUG */
408 #ifdef PATRICIA_DEBUG
411 "patricia_search_exact: take left %s/%d\n",
412 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
415 "patricia_search_exact: take left at %d\n", node
->bit
);
416 #endif /* PATRICIA_DEBUG */
424 #ifdef PATRICIA_DEBUG
426 fprintf(stderr
, "patricia_search_exact: stop at %s/%d %d\n",
427 prefix_toa(node
->prefix
), node
->prefix
->bitlen
, node
->bit
);
429 fprintf(stderr
, "patricia_search_exact: stop at %d\n", node
->bit
);
430 #endif /* PATRICIA_DEBUG */
431 if(node
->bit
> bitlen
|| node
->prefix
== NULL
)
433 assert(node
->bit
== bitlen
);
434 assert(node
->bit
== node
->prefix
->bitlen
);
435 if(comp_with_mask(prefix_tochar(node
->prefix
), prefix_tochar(prefix
), bitlen
))
437 #ifdef PATRICIA_DEBUG
438 fprintf(stderr
, "patricia_search_exact: found %s/%d\n",
439 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
440 #endif /* PATRICIA_DEBUG */
446 /* if inclusive != 0, "best" may be the given prefix itself */
448 rb_patricia_search_best2(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
, int inclusive
)
450 rb_patricia_node_t
*node
;
451 rb_patricia_node_t
*stack
[RB_PATRICIA_MAXBITS
+ 1];
458 assert(prefix
->bitlen
<= patricia
->maxbits
);
460 if(patricia
->head
== NULL
)
463 node
= patricia
->head
;
464 addr
= rb_prefix_touchar(prefix
);
465 bitlen
= prefix
->bitlen
;
467 while(node
->bit
< bitlen
)
472 #ifdef PATRICIA_DEBUG
474 "patricia_search_best: push %s/%d\n",
475 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
476 #endif /* PATRICIA_DEBUG */
480 if(BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
482 #ifdef PATRICIA_DEBUG
485 "patricia_search_best: take right %s/%d\n",
486 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
489 "patricia_search_best: take right at %d\n", node
->bit
);
490 #endif /* PATRICIA_DEBUG */
495 #ifdef PATRICIA_DEBUG
498 "patricia_search_best: take left %s/%d\n",
499 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
502 "patricia_search_best: take left at %d\n", node
->bit
);
503 #endif /* PATRICIA_DEBUG */
511 if(inclusive
&& node
&& node
->prefix
)
514 #ifdef PATRICIA_DEBUG
516 fprintf(stderr
, "patricia_search_best: stop at null\n");
517 else if(node
->prefix
)
518 fprintf(stderr
, "patricia_search_best: stop at %s/%d\n",
519 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
521 fprintf(stderr
, "patricia_search_best: stop at %d\n", node
->bit
);
522 #endif /* PATRICIA_DEBUG */
530 #ifdef PATRICIA_DEBUG
531 fprintf(stderr
, "patricia_search_best: pop %s/%d\n",
532 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
533 #endif /* PATRICIA_DEBUG */
534 if(comp_with_mask(prefix_tochar(node
->prefix
),
535 prefix_tochar(prefix
), node
->prefix
->bitlen
))
537 #ifdef PATRICIA_DEBUG
539 "patricia_search_best: found %s/%d\n",
540 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
541 #endif /* PATRICIA_DEBUG */
550 rb_patricia_search_best(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
)
552 return (rb_patricia_search_best2(patricia
, prefix
, 1));
557 rb_patricia_lookup(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
)
559 rb_patricia_node_t
*node
, *new_node
, *parent
, *glue
;
560 uint8_t *addr
, *test_addr
;
561 unsigned int bitlen
, check_bit
, differ_bit
;
562 unsigned int i
, j
, r
;
566 assert(prefix
->bitlen
<= patricia
->maxbits
);
568 if(patricia
->head
== NULL
)
570 node
= rb_malloc(sizeof(rb_patricia_node_t
));
571 node
->bit
= prefix
->bitlen
;
572 node
->prefix
= Ref_Prefix(prefix
);
574 node
->l
= node
->r
= NULL
;
576 patricia
->head
= node
;
577 #ifdef PATRICIA_DEBUG
579 "patricia_lookup: new_node #0 %s/%d (head)\n",
580 prefix_toa(prefix
), prefix
->bitlen
);
581 #endif /* PATRICIA_DEBUG */
582 patricia
->num_active_node
++;
586 addr
= rb_prefix_touchar(prefix
);
587 bitlen
= prefix
->bitlen
;
588 node
= patricia
->head
;
590 while(node
->bit
< bitlen
|| node
->prefix
== NULL
)
593 if(node
->bit
< patricia
->maxbits
&&
594 BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
598 #ifdef PATRICIA_DEBUG
601 "patricia_lookup: take right %s/%d\n",
602 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
604 fprintf(stderr
, "patricia_lookup: take right at %d\n", node
->bit
);
605 #endif /* PATRICIA_DEBUG */
612 #ifdef PATRICIA_DEBUG
615 "patricia_lookup: take left %s/%d\n",
616 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
618 fprintf(stderr
, "patricia_lookup: take left at %d\n", node
->bit
);
619 #endif /* PATRICIA_DEBUG */
626 assert(node
->prefix
);
627 #ifdef PATRICIA_DEBUG
628 fprintf(stderr
, "patricia_lookup: stop at %s/%d\n",
629 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
630 #endif /* PATRICIA_DEBUG */
632 test_addr
= rb_prefix_touchar(node
->prefix
);
633 /* find the first bit different */
634 check_bit
= (node
->bit
< bitlen
) ? node
->bit
: bitlen
;
636 for(i
= 0; i
* 8 < check_bit
; i
++)
638 if((r
= (addr
[i
] ^ test_addr
[i
])) == 0)
640 differ_bit
= (i
+ 1) * 8;
643 /* I know the better way, but for now */
644 for(j
= 0; j
< 8; j
++)
646 if(BIT_TEST(r
, (0x80 >> j
)))
651 differ_bit
= i
* 8 + j
;
654 if(differ_bit
> check_bit
)
655 differ_bit
= check_bit
;
656 #ifdef PATRICIA_DEBUG
657 fprintf(stderr
, "patricia_lookup: differ_bit %d\n", differ_bit
);
658 #endif /* PATRICIA_DEBUG */
660 parent
= node
->parent
;
661 while(parent
&& parent
->bit
>= differ_bit
)
664 parent
= node
->parent
;
665 #ifdef PATRICIA_DEBUG
667 fprintf(stderr
, "patricia_lookup: up to %s/%d\n",
668 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
670 fprintf(stderr
, "patricia_lookup: up to %d\n", node
->bit
);
671 #endif /* PATRICIA_DEBUG */
674 if(differ_bit
== bitlen
&& node
->bit
== bitlen
)
678 #ifdef PATRICIA_DEBUG
679 fprintf(stderr
, "patricia_lookup: found %s/%d\n",
680 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
681 #endif /* PATRICIA_DEBUG */
684 node
->prefix
= Ref_Prefix(prefix
);
685 #ifdef PATRICIA_DEBUG
687 "patricia_lookup: new node #1 %s/%d (glue mod)\n",
688 prefix_toa(prefix
), prefix
->bitlen
);
689 #endif /* PATRICIA_DEBUG */
690 assert(node
->data
== NULL
);
694 new_node
= rb_malloc(sizeof(rb_patricia_node_t
));
695 new_node
->bit
= prefix
->bitlen
;
696 new_node
->prefix
= Ref_Prefix(prefix
);
697 new_node
->parent
= NULL
;
698 new_node
->l
= new_node
->r
= NULL
;
699 new_node
->data
= NULL
;
700 patricia
->num_active_node
++;
702 if(node
->bit
== differ_bit
)
704 new_node
->parent
= node
;
705 if(node
->bit
< patricia
->maxbits
&&
706 BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
708 assert(node
->r
== NULL
);
713 assert(node
->l
== NULL
);
716 #ifdef PATRICIA_DEBUG
718 "patricia_lookup: new_node #2 %s/%d (child)\n",
719 prefix_toa(prefix
), prefix
->bitlen
);
720 #endif /* PATRICIA_DEBUG */
724 if(bitlen
== differ_bit
)
726 if(bitlen
< patricia
->maxbits
&&
727 BIT_TEST(test_addr
[bitlen
>> 3], 0x80 >> (bitlen
& 0x07)))
735 new_node
->parent
= node
->parent
;
736 if(node
->parent
== NULL
)
738 assert(patricia
->head
== node
);
739 patricia
->head
= new_node
;
741 else if(node
->parent
->r
== node
)
743 node
->parent
->r
= new_node
;
747 node
->parent
->l
= new_node
;
749 node
->parent
= new_node
;
750 #ifdef PATRICIA_DEBUG
752 "patricia_lookup: new_node #3 %s/%d (parent)\n",
753 prefix_toa(prefix
), prefix
->bitlen
);
754 #endif /* PATRICIA_DEBUG */
758 glue
= rb_malloc(sizeof(rb_patricia_node_t
));
759 glue
->bit
= differ_bit
;
761 glue
->parent
= node
->parent
;
763 patricia
->num_active_node
++;
764 if(differ_bit
< patricia
->maxbits
&&
765 BIT_TEST(addr
[differ_bit
>> 3], 0x80 >> (differ_bit
& 0x07)))
775 new_node
->parent
= glue
;
777 if(node
->parent
== NULL
)
779 assert(patricia
->head
== node
);
780 patricia
->head
= glue
;
782 else if(node
->parent
->r
== node
)
784 node
->parent
->r
= glue
;
788 node
->parent
->l
= glue
;
791 #ifdef PATRICIA_DEBUG
793 "patricia_lookup: new_node #4 %s/%d (glue+node)\n",
794 prefix_toa(prefix
), prefix
->bitlen
);
795 #endif /* PATRICIA_DEBUG */
802 rb_patricia_remove(rb_patricia_tree_t
*patricia
, rb_patricia_node_t
*node
)
804 rb_patricia_node_t
*parent
, *child
;
809 if(node
->r
&& node
->l
)
811 #ifdef PATRICIA_DEBUG
812 fprintf(stderr
, "patricia_remove: #0 %s/%d (r & l)\n",
813 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
814 #endif /* PATRICIA_DEBUG */
816 /* this might be a placeholder node -- have to check and make sure
817 * there is a prefix aossciated with it ! */
818 if(node
->prefix
!= NULL
)
819 Deref_Prefix(node
->prefix
);
821 /* Also I needed to clear data pointer -- masaki */
826 if(node
->r
== NULL
&& node
->l
== NULL
)
828 #ifdef PATRICIA_DEBUG
829 fprintf(stderr
, "patricia_remove: #1 %s/%d (!r & !l)\n",
830 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
831 #endif /* PATRICIA_DEBUG */
832 parent
= node
->parent
;
833 Deref_Prefix(node
->prefix
);
835 patricia
->num_active_node
--;
839 assert(patricia
->head
== node
);
840 patricia
->head
= NULL
;
844 if(parent
->r
== node
)
851 assert(parent
->l
== node
);
859 /* we need to remove parent too */
861 if(parent
->parent
== NULL
)
863 assert(patricia
->head
== parent
);
864 patricia
->head
= child
;
866 else if(parent
->parent
->r
== parent
)
868 parent
->parent
->r
= child
;
872 assert(parent
->parent
->l
== parent
);
873 parent
->parent
->l
= child
;
875 child
->parent
= parent
->parent
;
877 patricia
->num_active_node
--;
880 #ifdef PATRICIA_DEBUG
881 fprintf(stderr
, "patricia_remove: #2 %s/%d (r ^ l)\n",
882 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
883 #endif /* PATRICIA_DEBUG */
893 parent
= node
->parent
;
894 child
->parent
= parent
;
896 Deref_Prefix(node
->prefix
);
898 patricia
->num_active_node
--;
902 assert(patricia
->head
== node
);
903 patricia
->head
= child
;
907 if(parent
->r
== node
)
913 assert(parent
->l
== node
);
919 make_and_lookup_ip(rb_patricia_tree_t
*tree
, struct sockaddr
*in
, int bitlen
)
922 rb_patricia_node_t
*node
;
925 if(in
->sa_family
== AF_INET6
)
926 ipptr
= &((struct sockaddr_in6
*)in
)->sin6_addr
;
929 ipptr
= &((struct sockaddr_in
*)in
)->sin_addr
;
931 prefix
= New_Prefix(in
->sa_family
, ipptr
, bitlen
);
936 node
= rb_patricia_lookup(tree
, prefix
);
940 Deref_Prefix(prefix
);
946 make_and_lookup(rb_patricia_tree_t
*tree
, const char *string
)
949 rb_patricia_node_t
*node
;
951 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
953 node
= rb_patricia_lookup(tree
, prefix
);
957 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
959 node
= rb_patricia_lookup(tree
, prefix
);
964 #ifdef PATRICIA_DEBUG
965 printf("make_and_lookup: %s/%d\n", prefix_toa(prefix
), prefix
->bitlen
);
967 Deref_Prefix(prefix
);
972 static rb_patricia_node_t
*
973 try_search_exact(rb_patricia_tree_t
*tree
, char *string
)
976 rb_patricia_node_t
*node
;
977 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
979 node
= rb_patricia_search_exact(tree
, prefix
);
980 Deref_Prefix(prefix
);
984 else if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
986 node
= rb_patricia_search_exact(tree
, prefix
);
987 Deref_Prefix(prefix
);
996 lookup_then_remove(rb_patricia_tree_t
*tree
, char *string
)
998 rb_patricia_node_t
*node
;
1000 if((node
= try_search_exact(tree
, string
)))
1001 patricia_remove(tree
, node
);
1005 rb_patricia_node_t
*
1006 rb_match_ip(rb_patricia_tree_t
*tree
, struct sockaddr
*ip
)
1008 rb_prefix_t
*prefix
;
1009 rb_patricia_node_t
*node
;
1016 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1018 if(ip
->sa_family
== AF_INET6
)
1022 ipptr
= &((struct sockaddr_in6
*)ip
)->sin6_addr
;
1028 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1032 if((prefix
= New_Prefix(family
, ipptr
, len
)) != NULL
)
1034 node
= rb_patricia_search_best(tree
, prefix
);
1035 Deref_Prefix(prefix
);
1041 rb_patricia_node_t
*
1042 rb_match_ip_exact(rb_patricia_tree_t
*tree
, struct sockaddr
*ip
, unsigned int len
)
1044 rb_prefix_t
*prefix
;
1045 rb_patricia_node_t
*node
;
1053 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1055 if(ip
->sa_family
== AF_INET6
)
1060 ipptr
= &((struct sockaddr_in6
*)ip
)->sin6_addr
;
1067 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1071 if((prefix
= New_Prefix(family
, ipptr
, len
)) != NULL
)
1073 node
= rb_patricia_search_exact(tree
, prefix
);
1074 Deref_Prefix(prefix
);
1082 rb_patricia_node_t
*
1083 rb_match_string(rb_patricia_tree_t
*tree
, const char *string
)
1085 rb_patricia_node_t
*node
;
1086 rb_prefix_t
*prefix
;
1088 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
1090 node
= rb_patricia_search_best(tree
, prefix
);
1091 Deref_Prefix(prefix
);
1095 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
1097 node
= rb_patricia_search_best(tree
, prefix
);
1098 Deref_Prefix(prefix
);
1106 rb_patricia_node_t
*
1107 rb_match_exact_string(rb_patricia_tree_t
*tree
, const char *string
)
1109 rb_prefix_t
*prefix
;
1110 rb_patricia_node_t
*node
;
1111 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
1113 node
= rb_patricia_search_exact(tree
, prefix
);
1114 Deref_Prefix(prefix
);
1118 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
1120 node
= rb_patricia_search_exact(tree
, prefix
);
1121 Deref_Prefix(prefix
);