]>
jfr.im git - solanum.git/blob - librb/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 * librb and had function names changed, but otherwise not really altered.
7 * Dave Plonka <plonka@doit.wisc.edu>
9 * This product includes software developed by the University of Michigan,
10 * Merit Network, Inc., and their contributors.
12 * This file had been called "radix.c" in the MRT sources.
14 * I renamed it to "patricia.c" since it's not an implementation of a general
15 * radix trie. Also I pulled in various requirements from "prefix.c" and
16 * "demo.c" so that it could be used as a standalone API.
18 * This product includes software developed by the University of Michigan, Merit
19 * Network, Inc., and their contributors.
22 #include <librb_config.h>
25 /* Enable both of these to debug patricia.c
27 * #define PATRICIA_DEBUG 1
31 rb_init_patricia(void)
37 * convert prefix information to bytes
40 prefix_tochar(rb_prefix_t
*prefix
)
45 return ((uint8_t *)&prefix
->add
.sin
);
49 comp_with_mask(void *addr
, void *dest
, unsigned int mask
)
52 if( /* mask/8 == 0 || */ memcmp(addr
, dest
, mask
/ 8) == 0)
55 int m
= ((-1) << (8 - (mask
% 8)));
57 if(mask
% 8 == 0 || (((uint8_t *)addr
)[n
] & m
) == (((uint8_t *)dest
)[n
] & m
))
65 prefix_toa2x(rb_prefix_t
*prefix
, char *buf
, int buf_len
, int with_len
)
70 rb_strlcpy(buf
, "(NULL)", buf_len
);
73 inet_ntop(prefix
->family
, &prefix
->add
.sin
, buf
, buf_len
);
76 snprintf(tmp
, sizeof(tmp
), "/%d", prefix
->bitlen
);
83 * convert prefix information to ascii string
87 prefix_toa2(rb_prefix_t
*prefix
, char *buff
, int buf_len
)
89 return (prefix_toa2x(prefix
, buff
, buf_len
, 0));
93 prefix_toa(rb_prefix_t
*prefix
)
96 static char buf
[INET6_ADDRSTRLEN
+ 6];
98 static char buf
[16 + 6];
100 return (prefix_toa2(prefix
, buf
, sizeof(buf
)));
104 New_Prefix2(int family
, void *dest
, int bitlen
, rb_prefix_t
*prefix
)
106 int dynamic_allocated
= 0;
108 int default_bitlen
= 128;
110 int default_bitlen
= 32;
114 if(family
== AF_INET6
)
116 default_bitlen
= 128;
119 prefix
= rb_malloc(sizeof(rb_prefix_t
));
122 memcpy(&prefix
->add
.sin6
, dest
, 16);
126 if(family
== AF_INET
)
130 prefix
= rb_malloc(sizeof(rb_prefix_t
));
133 memcpy(&prefix
->add
.sin
, dest
, 4);
140 prefix
->bitlen
= (bitlen
>= 0) ? bitlen
: default_bitlen
;
141 prefix
->family
= family
;
142 prefix
->ref_count
= 0;
143 if(dynamic_allocated
)
151 New_Prefix(int family
, void *dest
, int bitlen
)
153 return (New_Prefix2(family
, dest
, bitlen
, NULL
));
159 ascii2prefix(int family
, const char *string
)
161 long bitlen
, maxbitlen
= 0;
163 struct in_addr sinaddr
;
165 struct in6_addr sinaddr6
;
173 /* easy way to handle both families */
178 if(strchr(string
, ':'))
182 if(family
== AF_INET
)
187 else if(family
== AF_INET6
)
193 if((cp
= strchr(string
, '/')) != NULL
)
195 bitlen
= atol(cp
+ 1);
197 /* copy the string to save. Avoid destroying the string */
198 assert(cp
- string
< MAXLINE
);
199 memcpy(save
, string
, cp
- string
);
200 save
[cp
- string
] = '\0';
202 if(bitlen
<= 0 || bitlen
> maxbitlen
)
210 if(family
== AF_INET
)
212 if((result
= rb_inet_pton(AF_INET
, string
, &sinaddr
)) <= 0)
214 return (New_Prefix(AF_INET
, &sinaddr
, bitlen
));
217 else if(family
== AF_INET6
)
219 if((result
= rb_inet_pton(AF_INET6
, string
, &sinaddr6
)) <= 0)
221 return (New_Prefix(AF_INET6
, &sinaddr6
, bitlen
));
229 Ref_Prefix(rb_prefix_t
*prefix
)
233 if(prefix
->ref_count
== 0)
235 /* make a copy in case of a static prefix */
236 return (New_Prefix2(prefix
->family
, &prefix
->add
, prefix
->bitlen
, NULL
));
243 Deref_Prefix(rb_prefix_t
*prefix
)
247 /* for secure programming, raise an assert. no static prefix can call this */
248 assert(prefix
->ref_count
> 0);
251 assert(prefix
->ref_count
>= 0);
252 if(prefix
->ref_count
<= 0)
261 // #define PATRICIA_DEBUG 1
263 static int num_active_patricia
= 0;
265 /* these routines support continuous mask only */
268 rb_new_patricia(int maxbits
)
270 rb_patricia_tree_t
*patricia
= rb_malloc(sizeof(rb_patricia_tree_t
));
272 patricia
->maxbits
= maxbits
;
273 patricia
->head
= NULL
;
274 patricia
->num_active_node
= 0;
275 assert(maxbits
<= RB_PATRICIA_MAXBITS
); /* XXX */
276 num_active_patricia
++;
282 * if func is supplied, it will be called as func(node->data)
283 * before deleting the node
287 rb_clear_patricia(rb_patricia_tree_t
*patricia
, void (*func
) (void *))
293 rb_patricia_node_t
*Xstack
[RB_PATRICIA_MAXBITS
+ 1];
294 rb_patricia_node_t
**Xsp
= Xstack
;
295 rb_patricia_node_t
*Xrn
= patricia
->head
;
299 rb_patricia_node_t
*l
= Xrn
->l
;
300 rb_patricia_node_t
*r
= Xrn
->r
;
304 Deref_Prefix(Xrn
->prefix
);
305 if(Xrn
->data
&& func
)
310 assert(Xrn
->data
== NULL
);
313 patricia
->num_active_node
--;
327 else if(Xsp
!= Xstack
)
333 Xrn
= (rb_patricia_node_t
*)0;
337 assert(patricia
->num_active_node
== 0);
343 rb_destroy_patricia(rb_patricia_tree_t
*patricia
, void (*func
) (void *))
345 rb_clear_patricia(patricia
, func
);
346 num_active_patricia
--;
351 * if func is supplied, it will be called as func(node->prefix, node->data)
355 rb_patricia_process(rb_patricia_tree_t
*patricia
, void (*func
) (rb_prefix_t
*, void *))
357 rb_patricia_node_t
*node
;
360 RB_PATRICIA_WALK(patricia
->head
, node
)
362 func(node
->prefix
, node
->data
);
364 RB_PATRICIA_WALK_END
;
368 rb_patricia_search_exact(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
)
370 rb_patricia_node_t
*node
;
376 assert(prefix
->bitlen
<= patricia
->maxbits
);
378 if(patricia
->head
== NULL
)
381 node
= patricia
->head
;
382 addr
= rb_prefix_touchar(prefix
);
383 bitlen
= prefix
->bitlen
;
385 while(node
->bit
< bitlen
)
388 if(BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
390 #ifdef PATRICIA_DEBUG
393 "patricia_search_exact: take right %s/%d\n",
394 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
397 "patricia_search_exact: take right at %u\n", node
->bit
);
398 #endif /* PATRICIA_DEBUG */
403 #ifdef PATRICIA_DEBUG
406 "patricia_search_exact: take left %s/%d\n",
407 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
410 "patricia_search_exact: take left at %u\n", node
->bit
);
411 #endif /* PATRICIA_DEBUG */
419 #ifdef PATRICIA_DEBUG
421 fprintf(stderr
, "patricia_search_exact: stop at %s/%d %u\n",
422 prefix_toa(node
->prefix
), node
->prefix
->bitlen
, node
->bit
);
424 fprintf(stderr
, "patricia_search_exact: stop at %u\n", node
->bit
);
425 #endif /* PATRICIA_DEBUG */
426 if(node
->bit
> bitlen
|| node
->prefix
== NULL
)
428 assert(node
->bit
== bitlen
);
429 assert(node
->bit
== node
->prefix
->bitlen
);
430 if(comp_with_mask(prefix_tochar(node
->prefix
), prefix_tochar(prefix
), bitlen
))
432 #ifdef PATRICIA_DEBUG
433 fprintf(stderr
, "patricia_search_exact: found %s/%d\n",
434 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
435 #endif /* PATRICIA_DEBUG */
441 /* if inclusive != 0, "best" may be the given prefix itself */
443 rb_patricia_search_best2(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
, int inclusive
)
445 rb_patricia_node_t
*node
;
446 rb_patricia_node_t
*stack
[RB_PATRICIA_MAXBITS
+ 1];
453 assert(prefix
->bitlen
<= patricia
->maxbits
);
455 if(patricia
->head
== NULL
)
458 node
= patricia
->head
;
459 addr
= rb_prefix_touchar(prefix
);
460 bitlen
= prefix
->bitlen
;
462 while(node
->bit
< bitlen
)
467 #ifdef PATRICIA_DEBUG
469 "patricia_search_best: push %s/%d\n",
470 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
471 #endif /* PATRICIA_DEBUG */
475 if(BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
477 #ifdef PATRICIA_DEBUG
480 "patricia_search_best: take right %s/%d\n",
481 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
484 "patricia_search_best: take right at %u\n", node
->bit
);
485 #endif /* PATRICIA_DEBUG */
490 #ifdef PATRICIA_DEBUG
493 "patricia_search_best: take left %s/%d\n",
494 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
497 "patricia_search_best: take left at %u\n", node
->bit
);
498 #endif /* PATRICIA_DEBUG */
506 if(inclusive
&& node
&& node
->prefix
)
509 #ifdef PATRICIA_DEBUG
511 fprintf(stderr
, "patricia_search_best: stop at null\n");
512 else if(node
->prefix
)
513 fprintf(stderr
, "patricia_search_best: stop at %s/%d\n",
514 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
516 fprintf(stderr
, "patricia_search_best: stop at %u\n", node
->bit
);
517 #endif /* PATRICIA_DEBUG */
525 #ifdef PATRICIA_DEBUG
526 fprintf(stderr
, "patricia_search_best: pop %s/%d\n",
527 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
528 #endif /* PATRICIA_DEBUG */
529 if(comp_with_mask(prefix_tochar(node
->prefix
),
530 prefix_tochar(prefix
), node
->prefix
->bitlen
))
532 #ifdef PATRICIA_DEBUG
534 "patricia_search_best: found %s/%d\n",
535 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
536 #endif /* PATRICIA_DEBUG */
545 rb_patricia_search_best(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
)
547 return (rb_patricia_search_best2(patricia
, prefix
, 1));
552 rb_patricia_lookup(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
)
554 rb_patricia_node_t
*node
, *new_node
, *parent
, *glue
;
555 uint8_t *addr
, *test_addr
;
556 unsigned int bitlen
, check_bit
, differ_bit
;
557 unsigned int i
, j
, r
;
561 assert(prefix
->bitlen
<= patricia
->maxbits
);
563 if(patricia
->head
== NULL
)
565 node
= rb_malloc(sizeof(rb_patricia_node_t
));
566 node
->bit
= prefix
->bitlen
;
567 node
->prefix
= Ref_Prefix(prefix
);
569 node
->l
= node
->r
= NULL
;
571 patricia
->head
= node
;
572 #ifdef PATRICIA_DEBUG
574 "patricia_lookup: new_node #0 %s/%d (head)\n",
575 prefix_toa(prefix
), prefix
->bitlen
);
576 #endif /* PATRICIA_DEBUG */
577 patricia
->num_active_node
++;
581 addr
= rb_prefix_touchar(prefix
);
582 bitlen
= prefix
->bitlen
;
583 node
= patricia
->head
;
585 while(node
->bit
< bitlen
|| node
->prefix
== NULL
)
588 if(node
->bit
< patricia
->maxbits
&&
589 BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
593 #ifdef PATRICIA_DEBUG
596 "patricia_lookup: take right %s/%d\n",
597 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
599 fprintf(stderr
, "patricia_lookup: take right at %u\n", node
->bit
);
600 #endif /* PATRICIA_DEBUG */
607 #ifdef PATRICIA_DEBUG
610 "patricia_lookup: take left %s/%d\n",
611 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
613 fprintf(stderr
, "patricia_lookup: take left at %u\n", node
->bit
);
614 #endif /* PATRICIA_DEBUG */
621 assert(node
->prefix
);
622 #ifdef PATRICIA_DEBUG
623 fprintf(stderr
, "patricia_lookup: stop at %s/%d\n",
624 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
625 #endif /* PATRICIA_DEBUG */
627 test_addr
= rb_prefix_touchar(node
->prefix
);
628 /* find the first bit different */
629 check_bit
= (node
->bit
< bitlen
) ? node
->bit
: bitlen
;
631 for(i
= 0; i
* 8 < check_bit
; i
++)
633 if((r
= (addr
[i
] ^ test_addr
[i
])) == 0)
635 differ_bit
= (i
+ 1) * 8;
638 /* I know the better way, but for now */
639 for(j
= 0; j
< 8; j
++)
641 if(BIT_TEST(r
, (0x80 >> j
)))
646 differ_bit
= i
* 8 + j
;
649 if(differ_bit
> check_bit
)
650 differ_bit
= check_bit
;
651 #ifdef PATRICIA_DEBUG
652 fprintf(stderr
, "patricia_lookup: differ_bit %u\n", differ_bit
);
653 #endif /* PATRICIA_DEBUG */
655 parent
= node
->parent
;
656 while(parent
&& parent
->bit
>= differ_bit
)
659 parent
= node
->parent
;
660 #ifdef PATRICIA_DEBUG
662 fprintf(stderr
, "patricia_lookup: up to %s/%d\n",
663 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
665 fprintf(stderr
, "patricia_lookup: up to %u\n", node
->bit
);
666 #endif /* PATRICIA_DEBUG */
669 if(differ_bit
== bitlen
&& node
->bit
== bitlen
)
673 #ifdef PATRICIA_DEBUG
674 fprintf(stderr
, "patricia_lookup: found %s/%d\n",
675 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
676 #endif /* PATRICIA_DEBUG */
679 node
->prefix
= Ref_Prefix(prefix
);
680 #ifdef PATRICIA_DEBUG
682 "patricia_lookup: new node #1 %s/%d (glue mod)\n",
683 prefix_toa(prefix
), prefix
->bitlen
);
684 #endif /* PATRICIA_DEBUG */
685 assert(node
->data
== NULL
);
689 new_node
= rb_malloc(sizeof(rb_patricia_node_t
));
690 new_node
->bit
= prefix
->bitlen
;
691 new_node
->prefix
= Ref_Prefix(prefix
);
692 new_node
->parent
= NULL
;
693 new_node
->l
= new_node
->r
= NULL
;
694 new_node
->data
= NULL
;
695 patricia
->num_active_node
++;
697 if(node
->bit
== differ_bit
)
699 new_node
->parent
= node
;
700 if(node
->bit
< patricia
->maxbits
&&
701 BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
703 assert(node
->r
== NULL
);
708 assert(node
->l
== NULL
);
711 #ifdef PATRICIA_DEBUG
713 "patricia_lookup: new_node #2 %s/%d (child)\n",
714 prefix_toa(prefix
), prefix
->bitlen
);
715 #endif /* PATRICIA_DEBUG */
719 if(bitlen
== differ_bit
)
721 if(bitlen
< patricia
->maxbits
&&
722 BIT_TEST(test_addr
[bitlen
>> 3], 0x80 >> (bitlen
& 0x07)))
730 new_node
->parent
= node
->parent
;
731 if(node
->parent
== NULL
)
733 assert(patricia
->head
== node
);
734 patricia
->head
= new_node
;
736 else if(node
->parent
->r
== node
)
738 node
->parent
->r
= new_node
;
742 node
->parent
->l
= new_node
;
744 node
->parent
= new_node
;
745 #ifdef PATRICIA_DEBUG
747 "patricia_lookup: new_node #3 %s/%d (parent)\n",
748 prefix_toa(prefix
), prefix
->bitlen
);
749 #endif /* PATRICIA_DEBUG */
753 glue
= rb_malloc(sizeof(rb_patricia_node_t
));
754 glue
->bit
= differ_bit
;
756 glue
->parent
= node
->parent
;
758 patricia
->num_active_node
++;
759 if(differ_bit
< patricia
->maxbits
&&
760 BIT_TEST(addr
[differ_bit
>> 3], 0x80 >> (differ_bit
& 0x07)))
770 new_node
->parent
= glue
;
772 if(node
->parent
== NULL
)
774 assert(patricia
->head
== node
);
775 patricia
->head
= glue
;
777 else if(node
->parent
->r
== node
)
779 node
->parent
->r
= glue
;
783 node
->parent
->l
= glue
;
786 #ifdef PATRICIA_DEBUG
788 "patricia_lookup: new_node #4 %s/%d (glue+node)\n",
789 prefix_toa(prefix
), prefix
->bitlen
);
790 #endif /* PATRICIA_DEBUG */
797 rb_patricia_remove(rb_patricia_tree_t
*patricia
, rb_patricia_node_t
*node
)
799 rb_patricia_node_t
*parent
, *child
;
804 if(node
->r
&& node
->l
)
806 #ifdef PATRICIA_DEBUG
807 fprintf(stderr
, "patricia_remove: #0 %s/%d (r & l)\n",
808 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
809 #endif /* PATRICIA_DEBUG */
811 /* this might be a placeholder node -- have to check and make sure
812 * there is a prefix aossciated with it ! */
813 if(node
->prefix
!= NULL
)
814 Deref_Prefix(node
->prefix
);
816 /* Also I needed to clear data pointer -- masaki */
821 if(node
->r
== NULL
&& node
->l
== NULL
)
823 #ifdef PATRICIA_DEBUG
824 fprintf(stderr
, "patricia_remove: #1 %s/%d (!r & !l)\n",
825 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
826 #endif /* PATRICIA_DEBUG */
827 parent
= node
->parent
;
828 Deref_Prefix(node
->prefix
);
830 patricia
->num_active_node
--;
834 assert(patricia
->head
== node
);
835 patricia
->head
= NULL
;
839 if(parent
->r
== node
)
846 assert(parent
->l
== node
);
854 /* we need to remove parent too */
856 if(parent
->parent
== NULL
)
858 assert(patricia
->head
== parent
);
859 patricia
->head
= child
;
861 else if(parent
->parent
->r
== parent
)
863 parent
->parent
->r
= child
;
867 assert(parent
->parent
->l
== parent
);
868 parent
->parent
->l
= child
;
870 child
->parent
= parent
->parent
;
872 patricia
->num_active_node
--;
875 #ifdef PATRICIA_DEBUG
876 fprintf(stderr
, "patricia_remove: #2 %s/%d (r ^ l)\n",
877 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
878 #endif /* PATRICIA_DEBUG */
888 parent
= node
->parent
;
889 child
->parent
= parent
;
891 Deref_Prefix(node
->prefix
);
893 patricia
->num_active_node
--;
897 assert(patricia
->head
== node
);
898 patricia
->head
= child
;
902 if(parent
->r
== node
)
908 assert(parent
->l
== node
);
914 make_and_lookup_ip(rb_patricia_tree_t
*tree
, struct sockaddr
*in
, int bitlen
)
917 rb_patricia_node_t
*node
;
920 if(in
->sa_family
== AF_INET6
)
921 ipptr
= &((struct sockaddr_in6
*)in
)->sin6_addr
;
924 ipptr
= &((struct sockaddr_in
*)in
)->sin_addr
;
926 prefix
= New_Prefix(in
->sa_family
, ipptr
, bitlen
);
931 node
= rb_patricia_lookup(tree
, prefix
);
935 Deref_Prefix(prefix
);
941 make_and_lookup(rb_patricia_tree_t
*tree
, const char *string
)
944 rb_patricia_node_t
*node
;
946 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
948 node
= rb_patricia_lookup(tree
, prefix
);
952 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
954 node
= rb_patricia_lookup(tree
, prefix
);
959 #ifdef PATRICIA_DEBUG
960 printf("make_and_lookup: %s/%d\n", prefix_toa(prefix
), prefix
->bitlen
);
962 Deref_Prefix(prefix
);
967 static rb_patricia_node_t
*
968 try_search_exact(rb_patricia_tree_t
*tree
, char *string
)
971 rb_patricia_node_t
*node
;
972 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
974 node
= rb_patricia_search_exact(tree
, prefix
);
975 Deref_Prefix(prefix
);
979 else if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
981 node
= rb_patricia_search_exact(tree
, prefix
);
982 Deref_Prefix(prefix
);
991 lookup_then_remove(rb_patricia_tree_t
*tree
, char *string
)
993 rb_patricia_node_t
*node
;
995 if((node
= try_search_exact(tree
, string
)))
996 patricia_remove(tree
, node
);
1000 rb_patricia_node_t
*
1001 rb_match_ip(rb_patricia_tree_t
*tree
, struct sockaddr
*ip
)
1003 rb_prefix_t
*prefix
;
1004 rb_patricia_node_t
*node
;
1011 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1013 if(ip
->sa_family
== AF_INET6
)
1017 ipptr
= &((struct sockaddr_in6
*)ip
)->sin6_addr
;
1023 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1027 if((prefix
= New_Prefix(family
, ipptr
, len
)) != NULL
)
1029 node
= rb_patricia_search_best(tree
, prefix
);
1030 Deref_Prefix(prefix
);
1036 rb_patricia_node_t
*
1037 rb_match_ip_exact(rb_patricia_tree_t
*tree
, struct sockaddr
*ip
, unsigned int len
)
1039 rb_prefix_t
*prefix
;
1040 rb_patricia_node_t
*node
;
1048 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1050 if(ip
->sa_family
== AF_INET6
)
1055 ipptr
= &((struct sockaddr_in6
*)ip
)->sin6_addr
;
1062 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1066 if((prefix
= New_Prefix(family
, ipptr
, len
)) != NULL
)
1068 node
= rb_patricia_search_exact(tree
, prefix
);
1069 Deref_Prefix(prefix
);
1077 rb_patricia_node_t
*
1078 rb_match_string(rb_patricia_tree_t
*tree
, const char *string
)
1080 rb_patricia_node_t
*node
;
1081 rb_prefix_t
*prefix
;
1083 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
1085 node
= rb_patricia_search_best(tree
, prefix
);
1086 Deref_Prefix(prefix
);
1090 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
1092 node
= rb_patricia_search_best(tree
, prefix
);
1093 Deref_Prefix(prefix
);
1101 rb_patricia_node_t
*
1102 rb_match_exact_string(rb_patricia_tree_t
*tree
, const char *string
)
1104 rb_prefix_t
*prefix
;
1105 rb_patricia_node_t
*node
;
1106 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
1108 node
= rb_patricia_search_exact(tree
, prefix
);
1109 Deref_Prefix(prefix
);
1113 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
1115 node
= rb_patricia_search_exact(tree
, prefix
);
1116 Deref_Prefix(prefix
);