]>
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 uint8_t m
= (0xFF << (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
)
95 static char buf
[INET6_ADDRSTRLEN
+ 6];
96 return (prefix_toa2(prefix
, buf
, sizeof(buf
)));
101 New_Prefix2(int family
, void *dest
, int bitlen
, rb_prefix_t
*prefix
)
103 int dynamic_allocated
= 0;
104 int default_bitlen
= 128;
106 if(family
== AF_INET6
)
108 default_bitlen
= 128;
111 prefix
= rb_malloc(sizeof(rb_prefix_t
));
114 memcpy(&prefix
->add
.sin6
, dest
, 16);
116 else if(family
== AF_INET
)
120 prefix
= rb_malloc(sizeof(rb_prefix_t
));
123 memcpy(&prefix
->add
.sin
, dest
, 4);
130 prefix
->bitlen
= (bitlen
>= 0) ? bitlen
: default_bitlen
;
131 prefix
->family
= family
;
132 prefix
->ref_count
= 0;
133 if(dynamic_allocated
)
141 New_Prefix(int family
, void *dest
, int bitlen
)
143 return (New_Prefix2(family
, dest
, bitlen
, NULL
));
149 ascii2prefix(int family
, const char *string
)
151 long bitlen
, maxbitlen
= 0;
153 struct in_addr sinaddr
;
154 struct in6_addr sinaddr6
;
161 /* easy way to handle both families */
165 if(strchr(string
, ':'))
168 if(family
== AF_INET
)
172 else if(family
== AF_INET6
)
177 if((cp
= strchr(string
, '/')) != NULL
)
179 bitlen
= atol(cp
+ 1);
181 /* copy the string to save. Avoid destroying the string */
182 assert(cp
- string
< MAXLINE
);
183 memcpy(save
, string
, cp
- string
);
184 save
[cp
- string
] = '\0';
186 if(bitlen
<= 0 || bitlen
> maxbitlen
)
194 if(family
== AF_INET
)
196 if((result
= rb_inet_pton(AF_INET
, string
, &sinaddr
)) <= 0)
198 return (New_Prefix(AF_INET
, &sinaddr
, bitlen
));
200 else if(family
== AF_INET6
)
202 if((result
= rb_inet_pton(AF_INET6
, string
, &sinaddr6
)) <= 0)
204 return (New_Prefix(AF_INET6
, &sinaddr6
, bitlen
));
211 Ref_Prefix(rb_prefix_t
*prefix
)
215 if(prefix
->ref_count
== 0)
217 /* make a copy in case of a static prefix */
218 return (New_Prefix2(prefix
->family
, &prefix
->add
, prefix
->bitlen
, NULL
));
225 Deref_Prefix(rb_prefix_t
*prefix
)
229 /* for secure programming, raise an assert. no static prefix can call this */
230 assert(prefix
->ref_count
> 0);
233 assert(prefix
->ref_count
>= 0);
234 if(prefix
->ref_count
<= 0)
243 // #define PATRICIA_DEBUG 1
245 static int num_active_patricia
= 0;
247 /* these routines support continuous mask only */
250 rb_new_patricia(int maxbits
)
252 rb_patricia_tree_t
*patricia
= rb_malloc(sizeof(rb_patricia_tree_t
));
254 patricia
->maxbits
= maxbits
;
255 patricia
->head
= NULL
;
256 patricia
->num_active_node
= 0;
257 assert(maxbits
<= RB_PATRICIA_MAXBITS
); /* XXX */
258 num_active_patricia
++;
264 * if func is supplied, it will be called as func(node->data)
265 * before deleting the node
269 rb_clear_patricia(rb_patricia_tree_t
*patricia
, void (*func
) (void *))
275 rb_patricia_node_t
*Xstack
[RB_PATRICIA_MAXBITS
+ 1];
276 rb_patricia_node_t
**Xsp
= Xstack
;
277 rb_patricia_node_t
*Xrn
= patricia
->head
;
281 rb_patricia_node_t
*l
= Xrn
->l
;
282 rb_patricia_node_t
*r
= Xrn
->r
;
286 Deref_Prefix(Xrn
->prefix
);
287 if(Xrn
->data
&& func
)
292 assert(Xrn
->data
== NULL
);
295 patricia
->num_active_node
--;
309 else if(Xsp
!= Xstack
)
315 Xrn
= (rb_patricia_node_t
*)0;
319 assert(patricia
->num_active_node
== 0);
325 rb_destroy_patricia(rb_patricia_tree_t
*patricia
, void (*func
) (void *))
327 rb_clear_patricia(patricia
, func
);
328 num_active_patricia
--;
333 * if func is supplied, it will be called as func(node->prefix, node->data)
337 rb_patricia_process(rb_patricia_tree_t
*patricia
, void (*func
) (rb_prefix_t
*, void *))
339 rb_patricia_node_t
*node
;
342 RB_PATRICIA_WALK(patricia
->head
, node
)
344 func(node
->prefix
, node
->data
);
346 RB_PATRICIA_WALK_END
;
350 rb_patricia_search_exact(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
)
352 rb_patricia_node_t
*node
;
358 assert(prefix
->bitlen
<= patricia
->maxbits
);
360 if(patricia
->head
== NULL
)
363 node
= patricia
->head
;
364 addr
= rb_prefix_touchar(prefix
);
365 bitlen
= prefix
->bitlen
;
367 while(node
->bit
< bitlen
)
370 if(BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
372 #ifdef PATRICIA_DEBUG
375 "patricia_search_exact: take right %s/%d\n",
376 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
379 "patricia_search_exact: take right at %u\n", node
->bit
);
380 #endif /* PATRICIA_DEBUG */
385 #ifdef PATRICIA_DEBUG
388 "patricia_search_exact: take left %s/%d\n",
389 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
392 "patricia_search_exact: take left at %u\n", node
->bit
);
393 #endif /* PATRICIA_DEBUG */
401 #ifdef PATRICIA_DEBUG
403 fprintf(stderr
, "patricia_search_exact: stop at %s/%d %u\n",
404 prefix_toa(node
->prefix
), node
->prefix
->bitlen
, node
->bit
);
406 fprintf(stderr
, "patricia_search_exact: stop at %u\n", node
->bit
);
407 #endif /* PATRICIA_DEBUG */
408 if(node
->bit
> bitlen
|| node
->prefix
== NULL
)
410 assert(node
->bit
== bitlen
);
411 assert(node
->bit
== node
->prefix
->bitlen
);
412 if(comp_with_mask(prefix_tochar(node
->prefix
), prefix_tochar(prefix
), bitlen
))
414 #ifdef PATRICIA_DEBUG
415 fprintf(stderr
, "patricia_search_exact: found %s/%d\n",
416 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
417 #endif /* PATRICIA_DEBUG */
423 /* if inclusive != 0, "best" may be the given prefix itself */
425 rb_patricia_search_best2(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
, int inclusive
)
427 rb_patricia_node_t
*node
;
428 rb_patricia_node_t
*stack
[RB_PATRICIA_MAXBITS
+ 1];
435 assert(prefix
->bitlen
<= patricia
->maxbits
);
437 if(patricia
->head
== NULL
)
440 node
= patricia
->head
;
441 addr
= rb_prefix_touchar(prefix
);
442 bitlen
= prefix
->bitlen
;
444 while(node
->bit
< bitlen
)
449 #ifdef PATRICIA_DEBUG
451 "patricia_search_best: push %s/%d\n",
452 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
453 #endif /* PATRICIA_DEBUG */
457 if(BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
459 #ifdef PATRICIA_DEBUG
462 "patricia_search_best: take right %s/%d\n",
463 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
466 "patricia_search_best: take right at %u\n", node
->bit
);
467 #endif /* PATRICIA_DEBUG */
472 #ifdef PATRICIA_DEBUG
475 "patricia_search_best: take left %s/%d\n",
476 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
479 "patricia_search_best: take left at %u\n", node
->bit
);
480 #endif /* PATRICIA_DEBUG */
488 if(inclusive
&& node
&& node
->prefix
)
491 #ifdef PATRICIA_DEBUG
493 fprintf(stderr
, "patricia_search_best: stop at null\n");
494 else if(node
->prefix
)
495 fprintf(stderr
, "patricia_search_best: stop at %s/%d\n",
496 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
498 fprintf(stderr
, "patricia_search_best: stop at %u\n", node
->bit
);
499 #endif /* PATRICIA_DEBUG */
507 #ifdef PATRICIA_DEBUG
508 fprintf(stderr
, "patricia_search_best: pop %s/%d\n",
509 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
510 #endif /* PATRICIA_DEBUG */
511 if(comp_with_mask(prefix_tochar(node
->prefix
),
512 prefix_tochar(prefix
), node
->prefix
->bitlen
))
514 #ifdef PATRICIA_DEBUG
516 "patricia_search_best: found %s/%d\n",
517 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
518 #endif /* PATRICIA_DEBUG */
527 rb_patricia_search_best(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
)
529 return (rb_patricia_search_best2(patricia
, prefix
, 1));
534 rb_patricia_lookup(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
)
536 rb_patricia_node_t
*node
, *new_node
, *parent
, *glue
;
537 uint8_t *addr
, *test_addr
;
538 unsigned int bitlen
, check_bit
, differ_bit
;
539 unsigned int i
, j
, r
;
543 assert(prefix
->bitlen
<= patricia
->maxbits
);
545 if(patricia
->head
== NULL
)
547 node
= rb_malloc(sizeof(rb_patricia_node_t
));
548 node
->bit
= prefix
->bitlen
;
549 node
->prefix
= Ref_Prefix(prefix
);
551 node
->l
= node
->r
= NULL
;
553 patricia
->head
= node
;
554 #ifdef PATRICIA_DEBUG
556 "patricia_lookup: new_node #0 %s/%d (head)\n",
557 prefix_toa(prefix
), prefix
->bitlen
);
558 #endif /* PATRICIA_DEBUG */
559 patricia
->num_active_node
++;
563 addr
= rb_prefix_touchar(prefix
);
564 bitlen
= prefix
->bitlen
;
565 node
= patricia
->head
;
567 while(node
->bit
< bitlen
|| node
->prefix
== NULL
)
570 if(node
->bit
< patricia
->maxbits
&&
571 BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
575 #ifdef PATRICIA_DEBUG
578 "patricia_lookup: take right %s/%d\n",
579 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
581 fprintf(stderr
, "patricia_lookup: take right at %u\n", node
->bit
);
582 #endif /* PATRICIA_DEBUG */
589 #ifdef PATRICIA_DEBUG
592 "patricia_lookup: take left %s/%d\n",
593 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
595 fprintf(stderr
, "patricia_lookup: take left at %u\n", node
->bit
);
596 #endif /* PATRICIA_DEBUG */
603 assert(node
->prefix
);
604 #ifdef PATRICIA_DEBUG
605 fprintf(stderr
, "patricia_lookup: stop at %s/%d\n",
606 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
607 #endif /* PATRICIA_DEBUG */
609 test_addr
= rb_prefix_touchar(node
->prefix
);
610 /* find the first bit different */
611 check_bit
= (node
->bit
< bitlen
) ? node
->bit
: bitlen
;
613 for(i
= 0; i
* 8 < check_bit
; i
++)
615 if((r
= (addr
[i
] ^ test_addr
[i
])) == 0)
617 differ_bit
= (i
+ 1) * 8;
620 /* I know the better way, but for now */
621 for(j
= 0; j
< 8; j
++)
623 if(BIT_TEST(r
, (0x80 >> j
)))
628 differ_bit
= i
* 8 + j
;
631 if(differ_bit
> check_bit
)
632 differ_bit
= check_bit
;
633 #ifdef PATRICIA_DEBUG
634 fprintf(stderr
, "patricia_lookup: differ_bit %u\n", differ_bit
);
635 #endif /* PATRICIA_DEBUG */
637 parent
= node
->parent
;
638 while(parent
&& parent
->bit
>= differ_bit
)
641 parent
= node
->parent
;
642 #ifdef PATRICIA_DEBUG
644 fprintf(stderr
, "patricia_lookup: up to %s/%d\n",
645 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
647 fprintf(stderr
, "patricia_lookup: up to %u\n", node
->bit
);
648 #endif /* PATRICIA_DEBUG */
651 if(differ_bit
== bitlen
&& node
->bit
== bitlen
)
655 #ifdef PATRICIA_DEBUG
656 fprintf(stderr
, "patricia_lookup: found %s/%d\n",
657 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
658 #endif /* PATRICIA_DEBUG */
661 node
->prefix
= Ref_Prefix(prefix
);
662 #ifdef PATRICIA_DEBUG
664 "patricia_lookup: new node #1 %s/%d (glue mod)\n",
665 prefix_toa(prefix
), prefix
->bitlen
);
666 #endif /* PATRICIA_DEBUG */
667 assert(node
->data
== NULL
);
671 new_node
= rb_malloc(sizeof(rb_patricia_node_t
));
672 new_node
->bit
= prefix
->bitlen
;
673 new_node
->prefix
= Ref_Prefix(prefix
);
674 new_node
->parent
= NULL
;
675 new_node
->l
= new_node
->r
= NULL
;
676 new_node
->data
= NULL
;
677 patricia
->num_active_node
++;
679 if(node
->bit
== differ_bit
)
681 new_node
->parent
= node
;
682 if(node
->bit
< patricia
->maxbits
&&
683 BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
685 assert(node
->r
== NULL
);
690 assert(node
->l
== NULL
);
693 #ifdef PATRICIA_DEBUG
695 "patricia_lookup: new_node #2 %s/%d (child)\n",
696 prefix_toa(prefix
), prefix
->bitlen
);
697 #endif /* PATRICIA_DEBUG */
701 if(bitlen
== differ_bit
)
703 if(bitlen
< patricia
->maxbits
&&
704 BIT_TEST(test_addr
[bitlen
>> 3], 0x80 >> (bitlen
& 0x07)))
712 new_node
->parent
= node
->parent
;
713 if(node
->parent
== NULL
)
715 assert(patricia
->head
== node
);
716 patricia
->head
= new_node
;
718 else if(node
->parent
->r
== node
)
720 node
->parent
->r
= new_node
;
724 node
->parent
->l
= new_node
;
726 node
->parent
= new_node
;
727 #ifdef PATRICIA_DEBUG
729 "patricia_lookup: new_node #3 %s/%d (parent)\n",
730 prefix_toa(prefix
), prefix
->bitlen
);
731 #endif /* PATRICIA_DEBUG */
735 glue
= rb_malloc(sizeof(rb_patricia_node_t
));
736 glue
->bit
= differ_bit
;
738 glue
->parent
= node
->parent
;
740 patricia
->num_active_node
++;
741 if(differ_bit
< patricia
->maxbits
&&
742 BIT_TEST(addr
[differ_bit
>> 3], 0x80 >> (differ_bit
& 0x07)))
752 new_node
->parent
= glue
;
754 if(node
->parent
== NULL
)
756 assert(patricia
->head
== node
);
757 patricia
->head
= glue
;
759 else if(node
->parent
->r
== node
)
761 node
->parent
->r
= glue
;
765 node
->parent
->l
= glue
;
768 #ifdef PATRICIA_DEBUG
770 "patricia_lookup: new_node #4 %s/%d (glue+node)\n",
771 prefix_toa(prefix
), prefix
->bitlen
);
772 #endif /* PATRICIA_DEBUG */
779 rb_patricia_remove(rb_patricia_tree_t
*patricia
, rb_patricia_node_t
*node
)
781 rb_patricia_node_t
*parent
, *child
;
786 if(node
->r
&& node
->l
)
788 #ifdef PATRICIA_DEBUG
789 fprintf(stderr
, "patricia_remove: #0 %s/%d (r & l)\n",
790 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
791 #endif /* PATRICIA_DEBUG */
793 /* this might be a placeholder node -- have to check and make sure
794 * there is a prefix aossciated with it ! */
795 if(node
->prefix
!= NULL
)
796 Deref_Prefix(node
->prefix
);
798 /* Also I needed to clear data pointer -- masaki */
803 if(node
->r
== NULL
&& node
->l
== NULL
)
805 #ifdef PATRICIA_DEBUG
806 fprintf(stderr
, "patricia_remove: #1 %s/%d (!r & !l)\n",
807 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
808 #endif /* PATRICIA_DEBUG */
809 parent
= node
->parent
;
810 Deref_Prefix(node
->prefix
);
812 patricia
->num_active_node
--;
816 assert(patricia
->head
== node
);
817 patricia
->head
= NULL
;
821 if(parent
->r
== node
)
828 assert(parent
->l
== node
);
836 /* we need to remove parent too */
838 if(parent
->parent
== NULL
)
840 assert(patricia
->head
== parent
);
841 patricia
->head
= child
;
843 else if(parent
->parent
->r
== parent
)
845 parent
->parent
->r
= child
;
849 assert(parent
->parent
->l
== parent
);
850 parent
->parent
->l
= child
;
852 child
->parent
= parent
->parent
;
854 patricia
->num_active_node
--;
857 #ifdef PATRICIA_DEBUG
858 fprintf(stderr
, "patricia_remove: #2 %s/%d (r ^ l)\n",
859 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
860 #endif /* PATRICIA_DEBUG */
870 parent
= node
->parent
;
871 child
->parent
= parent
;
873 Deref_Prefix(node
->prefix
);
875 patricia
->num_active_node
--;
879 assert(patricia
->head
== node
);
880 patricia
->head
= child
;
884 if(parent
->r
== node
)
890 assert(parent
->l
== node
);
896 make_and_lookup_ip(rb_patricia_tree_t
*tree
, struct sockaddr
*in
, int bitlen
)
899 rb_patricia_node_t
*node
;
901 if(in
->sa_family
== AF_INET6
)
902 ipptr
= &((struct sockaddr_in6
*)in
)->sin6_addr
;
904 ipptr
= &((struct sockaddr_in
*)in
)->sin_addr
;
906 prefix
= New_Prefix(in
->sa_family
, ipptr
, bitlen
);
911 node
= rb_patricia_lookup(tree
, prefix
);
915 Deref_Prefix(prefix
);
921 make_and_lookup(rb_patricia_tree_t
*tree
, const char *string
)
924 rb_patricia_node_t
*node
;
926 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
928 node
= rb_patricia_lookup(tree
, prefix
);
931 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
933 node
= rb_patricia_lookup(tree
, prefix
);
937 #ifdef PATRICIA_DEBUG
938 printf("make_and_lookup: %s/%d\n", prefix_toa(prefix
), prefix
->bitlen
);
940 Deref_Prefix(prefix
);
945 static rb_patricia_node_t
*
946 try_search_exact(rb_patricia_tree_t
*tree
, char *string
)
949 rb_patricia_node_t
*node
;
950 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
952 node
= rb_patricia_search_exact(tree
, prefix
);
953 Deref_Prefix(prefix
);
956 else if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
958 node
= rb_patricia_search_exact(tree
, prefix
);
959 Deref_Prefix(prefix
);
967 lookup_then_remove(rb_patricia_tree_t
*tree
, char *string
)
969 rb_patricia_node_t
*node
;
971 if((node
= try_search_exact(tree
, string
)))
972 patricia_remove(tree
, node
);
977 rb_match_ip(rb_patricia_tree_t
*tree
, struct sockaddr
*ip
)
980 rb_patricia_node_t
*node
;
985 if(ip
->sa_family
== AF_INET6
)
989 ipptr
= &((struct sockaddr_in6
*)ip
)->sin6_addr
;
995 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
998 if((prefix
= New_Prefix(family
, ipptr
, len
)) != NULL
)
1000 node
= rb_patricia_search_best(tree
, prefix
);
1001 Deref_Prefix(prefix
);
1007 rb_patricia_node_t
*
1008 rb_match_ip_exact(rb_patricia_tree_t
*tree
, struct sockaddr
*ip
, unsigned int len
)
1010 rb_prefix_t
*prefix
;
1011 rb_patricia_node_t
*node
;
1015 if(ip
->sa_family
== AF_INET6
)
1020 ipptr
= &((struct sockaddr_in6
*)ip
)->sin6_addr
;
1027 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1030 if((prefix
= New_Prefix(family
, ipptr
, len
)) != NULL
)
1032 node
= rb_patricia_search_exact(tree
, prefix
);
1033 Deref_Prefix(prefix
);
1041 rb_patricia_node_t
*
1042 rb_match_string(rb_patricia_tree_t
*tree
, const char *string
)
1044 rb_patricia_node_t
*node
;
1045 rb_prefix_t
*prefix
;
1047 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
1049 node
= rb_patricia_search_best(tree
, prefix
);
1050 Deref_Prefix(prefix
);
1053 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
1055 node
= rb_patricia_search_best(tree
, prefix
);
1056 Deref_Prefix(prefix
);
1063 rb_patricia_node_t
*
1064 rb_match_exact_string(rb_patricia_tree_t
*tree
, const char *string
)
1066 rb_prefix_t
*prefix
;
1067 rb_patricia_node_t
*node
;
1068 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
1070 node
= rb_patricia_search_exact(tree
, prefix
);
1071 Deref_Prefix(prefix
);
1074 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
1076 node
= rb_patricia_search_exact(tree
, prefix
);
1077 Deref_Prefix(prefix
);