]>
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
))
69 prefix_toa2x(rb_prefix_t
* prefix
, char *buf
, int buf_len
, int with_len
)
74 strcpy(buf
, "(NULL)");
77 inet_ntop(prefix
->family
, &prefix
->add
.sin
, buf
, buf_len
);
80 rb_snprintf(tmp
, sizeof(tmp
), "/%d", prefix
->bitlen
);
87 * convert prefix information to ascii string
91 prefix_toa2(rb_prefix_t
* prefix
, char *buff
, int buf_len
)
93 return (prefix_toa2x(prefix
, buff
, buf_len
, 0));
96 prefix_toa(rb_prefix_t
* prefix
)
99 static char buf
[INET6_ADDRSTRLEN
+ 6];
101 static char buf
[16 + 6];
103 return (prefix_toa2(prefix
, buf
, sizeof(buf
)));
107 New_Prefix2(int family
, void *dest
, int bitlen
, rb_prefix_t
* prefix
)
109 int dynamic_allocated
= 0;
111 int default_bitlen
= 128;
113 int default_bitlen
= 32;
117 if(family
== AF_INET6
)
119 default_bitlen
= 128;
122 prefix
= rb_malloc(sizeof(rb_prefix_t
));
125 memcpy(&prefix
->add
.sin6
, dest
, 16);
129 if(family
== AF_INET
)
133 prefix
= rb_malloc(sizeof(rb_prefix_t
));
136 memcpy(&prefix
->add
.sin
, dest
, 4);
143 prefix
->bitlen
= (bitlen
>= 0) ? bitlen
: default_bitlen
;
144 prefix
->family
= family
;
145 prefix
->ref_count
= 0;
146 if(dynamic_allocated
)
154 New_Prefix(int family
, void *dest
, int bitlen
)
156 return (New_Prefix2(family
, dest
, bitlen
, NULL
));
162 ascii2prefix(int family
, const char *string
)
164 long bitlen
, maxbitlen
= 0;
166 struct in_addr sinaddr
;
168 struct in6_addr sinaddr6
;
176 /* easy way to handle both families */
181 if(strchr(string
, ':'))
185 if(family
== AF_INET
)
190 else if(family
== AF_INET6
)
196 if((cp
= strchr(string
, '/')) != NULL
)
198 bitlen
= atol(cp
+ 1);
200 /* copy the string to save. Avoid destroying the string */
201 assert(cp
- string
< MAXLINE
);
202 memcpy(save
, string
, cp
- string
);
203 save
[cp
- string
] = '\0';
205 if(bitlen
<= 0 || bitlen
> maxbitlen
)
213 if(family
== AF_INET
)
215 if((result
= rb_inet_pton(AF_INET
, string
, &sinaddr
)) <= 0)
217 return (New_Prefix(AF_INET
, &sinaddr
, bitlen
));
220 else if(family
== AF_INET6
)
222 if((result
= rb_inet_pton(AF_INET6
, string
, &sinaddr6
)) <= 0)
224 return (New_Prefix(AF_INET6
, &sinaddr6
, bitlen
));
232 Ref_Prefix(rb_prefix_t
* prefix
)
236 if(prefix
->ref_count
== 0)
238 /* make a copy in case of a static prefix */
239 return (New_Prefix2(prefix
->family
, &prefix
->add
, prefix
->bitlen
, NULL
));
246 Deref_Prefix(rb_prefix_t
* prefix
)
250 /* for secure programming, raise an assert. no static prefix can call this */
251 assert(prefix
->ref_count
> 0);
254 assert(prefix
->ref_count
>= 0);
255 if(prefix
->ref_count
<= 0)
264 // #define PATRICIA_DEBUG 1
266 static int num_active_patricia
= 0;
268 /* these routines support continuous mask only */
271 rb_new_patricia(int maxbits
)
273 rb_patricia_tree_t
*patricia
= rb_malloc(sizeof(rb_patricia_tree_t
));
275 patricia
->maxbits
= maxbits
;
276 patricia
->head
= NULL
;
277 patricia
->num_active_node
= 0;
278 assert(maxbits
<= RB_PATRICIA_MAXBITS
); /* XXX */
279 num_active_patricia
++;
285 * if func is supplied, it will be called as func(node->data)
286 * before deleting the node
290 rb_clear_patricia(rb_patricia_tree_t
* patricia
, void (*func
)(void *))
296 rb_patricia_node_t
*Xstack
[RB_PATRICIA_MAXBITS
+ 1];
297 rb_patricia_node_t
**Xsp
= Xstack
;
298 rb_patricia_node_t
*Xrn
= patricia
->head
;
302 rb_patricia_node_t
*l
= Xrn
->l
;
303 rb_patricia_node_t
*r
= Xrn
->r
;
307 Deref_Prefix(Xrn
->prefix
);
308 if(Xrn
->data
&& func
)
313 assert(Xrn
->data
== NULL
);
316 patricia
->num_active_node
--;
330 else if(Xsp
!= Xstack
)
336 Xrn
= (rb_patricia_node_t
*) 0;
340 assert(patricia
->num_active_node
== 0);
346 rb_destroy_patricia(rb_patricia_tree_t
* patricia
, void (*func
)(void *))
348 rb_clear_patricia(patricia
, func
);
349 num_active_patricia
--;
354 * if func is supplied, it will be called as func(node->prefix, node->data)
358 rb_patricia_process(rb_patricia_tree_t
* patricia
, void (*func
)(rb_prefix_t
*, void *))
360 rb_patricia_node_t
*node
;
363 RB_PATRICIA_WALK(patricia
->head
, node
)
365 func(node
->prefix
, node
->data
);
367 RB_PATRICIA_WALK_END
;
371 rb_patricia_search_exact(rb_patricia_tree_t
* patricia
, rb_prefix_t
* prefix
)
373 rb_patricia_node_t
*node
;
379 assert(prefix
->bitlen
<= patricia
->maxbits
);
381 if(patricia
->head
== NULL
)
384 node
= patricia
->head
;
385 addr
= rb_prefix_touchar(prefix
);
386 bitlen
= prefix
->bitlen
;
388 while (node
->bit
< bitlen
)
391 if(BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
393 #ifdef PATRICIA_DEBUG
396 "patricia_search_exact: take right %s/%d\n",
397 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
400 "patricia_search_exact: take right at %d\n", node
->bit
);
401 #endif /* PATRICIA_DEBUG */
406 #ifdef PATRICIA_DEBUG
409 "patricia_search_exact: take left %s/%d\n",
410 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
413 "patricia_search_exact: take left at %d\n", node
->bit
);
414 #endif /* PATRICIA_DEBUG */
422 #ifdef PATRICIA_DEBUG
424 fprintf(stderr
, "patricia_search_exact: stop at %s/%d %d\n",
425 prefix_toa(node
->prefix
), node
->prefix
->bitlen
, node
->bit
);
427 fprintf(stderr
, "patricia_search_exact: stop at %d\n", node
->bit
);
428 #endif /* PATRICIA_DEBUG */
429 if(node
->bit
> bitlen
|| node
->prefix
== NULL
)
431 assert(node
->bit
== bitlen
);
432 assert(node
->bit
== node
->prefix
->bitlen
);
433 if(comp_with_mask(prefix_tochar(node
->prefix
), prefix_tochar(prefix
), bitlen
))
435 #ifdef PATRICIA_DEBUG
436 fprintf(stderr
, "patricia_search_exact: found %s/%d\n",
437 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
438 #endif /* PATRICIA_DEBUG */
444 /* if inclusive != 0, "best" may be the given prefix itself */
446 rb_patricia_search_best2(rb_patricia_tree_t
* patricia
, rb_prefix_t
* prefix
, int inclusive
)
448 rb_patricia_node_t
*node
;
449 rb_patricia_node_t
*stack
[RB_PATRICIA_MAXBITS
+ 1];
456 assert(prefix
->bitlen
<= patricia
->maxbits
);
458 if(patricia
->head
== NULL
)
461 node
= patricia
->head
;
462 addr
= rb_prefix_touchar(prefix
);
463 bitlen
= prefix
->bitlen
;
465 while (node
->bit
< bitlen
)
470 #ifdef PATRICIA_DEBUG
472 "patricia_search_best: push %s/%d\n",
473 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
474 #endif /* PATRICIA_DEBUG */
478 if(BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
480 #ifdef PATRICIA_DEBUG
483 "patricia_search_best: take right %s/%d\n",
484 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
487 "patricia_search_best: take right at %d\n", node
->bit
);
488 #endif /* PATRICIA_DEBUG */
493 #ifdef PATRICIA_DEBUG
496 "patricia_search_best: take left %s/%d\n",
497 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
500 "patricia_search_best: take left at %d\n", node
->bit
);
501 #endif /* PATRICIA_DEBUG */
509 if(inclusive
&& node
&& node
->prefix
)
512 #ifdef PATRICIA_DEBUG
514 fprintf(stderr
, "patricia_search_best: stop at null\n");
515 else if(node
->prefix
)
516 fprintf(stderr
, "patricia_search_best: stop at %s/%d\n",
517 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
519 fprintf(stderr
, "patricia_search_best: stop at %d\n", node
->bit
);
520 #endif /* PATRICIA_DEBUG */
528 #ifdef PATRICIA_DEBUG
529 fprintf(stderr
, "patricia_search_best: pop %s/%d\n",
530 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
531 #endif /* PATRICIA_DEBUG */
532 if(comp_with_mask(prefix_tochar(node
->prefix
),
533 prefix_tochar(prefix
), node
->prefix
->bitlen
))
535 #ifdef PATRICIA_DEBUG
537 "patricia_search_best: found %s/%d\n",
538 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
539 #endif /* PATRICIA_DEBUG */
548 rb_patricia_search_best(rb_patricia_tree_t
* patricia
, rb_prefix_t
* prefix
)
550 return (rb_patricia_search_best2(patricia
, prefix
, 1));
555 rb_patricia_lookup(rb_patricia_tree_t
* patricia
, rb_prefix_t
* prefix
)
557 rb_patricia_node_t
*node
, *new_node
, *parent
, *glue
;
558 uint8_t *addr
, *test_addr
;
559 unsigned int bitlen
, check_bit
, differ_bit
;
560 unsigned int i
, j
, r
;
564 assert(prefix
->bitlen
<= patricia
->maxbits
);
566 if(patricia
->head
== NULL
)
568 node
= rb_malloc(sizeof(rb_patricia_node_t
));
569 node
->bit
= prefix
->bitlen
;
570 node
->prefix
= Ref_Prefix(prefix
);
572 node
->l
= node
->r
= NULL
;
574 patricia
->head
= node
;
575 #ifdef PATRICIA_DEBUG
577 "patricia_lookup: new_node #0 %s/%d (head)\n",
578 prefix_toa(prefix
), prefix
->bitlen
);
579 #endif /* PATRICIA_DEBUG */
580 patricia
->num_active_node
++;
584 addr
= rb_prefix_touchar(prefix
);
585 bitlen
= prefix
->bitlen
;
586 node
= patricia
->head
;
588 while (node
->bit
< bitlen
|| node
->prefix
== NULL
)
591 if(node
->bit
< patricia
->maxbits
&&
592 BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
596 #ifdef PATRICIA_DEBUG
599 "patricia_lookup: take right %s/%d\n",
600 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
602 fprintf(stderr
, "patricia_lookup: take right at %d\n", node
->bit
);
603 #endif /* PATRICIA_DEBUG */
610 #ifdef PATRICIA_DEBUG
613 "patricia_lookup: take left %s/%d\n",
614 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
616 fprintf(stderr
, "patricia_lookup: take left at %d\n", node
->bit
);
617 #endif /* PATRICIA_DEBUG */
624 assert(node
->prefix
);
625 #ifdef PATRICIA_DEBUG
626 fprintf(stderr
, "patricia_lookup: stop at %s/%d\n",
627 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
628 #endif /* PATRICIA_DEBUG */
630 test_addr
= rb_prefix_touchar(node
->prefix
);
631 /* find the first bit different */
632 check_bit
= (node
->bit
< bitlen
) ? node
->bit
: bitlen
;
634 for (i
= 0; i
* 8 < check_bit
; i
++)
636 if((r
= (addr
[i
] ^ test_addr
[i
])) == 0)
638 differ_bit
= (i
+ 1) * 8;
641 /* I know the better way, but for now */
642 for (j
= 0; j
< 8; j
++)
644 if(BIT_TEST(r
, (0x80 >> j
)))
649 differ_bit
= i
* 8 + j
;
652 if(differ_bit
> check_bit
)
653 differ_bit
= check_bit
;
654 #ifdef PATRICIA_DEBUG
655 fprintf(stderr
, "patricia_lookup: differ_bit %d\n", differ_bit
);
656 #endif /* PATRICIA_DEBUG */
658 parent
= node
->parent
;
659 while (parent
&& parent
->bit
>= differ_bit
)
662 parent
= node
->parent
;
663 #ifdef PATRICIA_DEBUG
665 fprintf(stderr
, "patricia_lookup: up to %s/%d\n",
666 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
668 fprintf(stderr
, "patricia_lookup: up to %d\n", node
->bit
);
669 #endif /* PATRICIA_DEBUG */
672 if(differ_bit
== bitlen
&& node
->bit
== bitlen
)
676 #ifdef PATRICIA_DEBUG
677 fprintf(stderr
, "patricia_lookup: found %s/%d\n",
678 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
679 #endif /* PATRICIA_DEBUG */
682 node
->prefix
= Ref_Prefix(prefix
);
683 #ifdef PATRICIA_DEBUG
685 "patricia_lookup: new node #1 %s/%d (glue mod)\n",
686 prefix_toa(prefix
), prefix
->bitlen
);
687 #endif /* PATRICIA_DEBUG */
688 assert(node
->data
== NULL
);
692 new_node
= rb_malloc(sizeof(rb_patricia_node_t
));
693 new_node
->bit
= prefix
->bitlen
;
694 new_node
->prefix
= Ref_Prefix(prefix
);
695 new_node
->parent
= NULL
;
696 new_node
->l
= new_node
->r
= NULL
;
697 new_node
->data
= NULL
;
698 patricia
->num_active_node
++;
700 if(node
->bit
== differ_bit
)
702 new_node
->parent
= node
;
703 if(node
->bit
< patricia
->maxbits
&&
704 BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
706 assert(node
->r
== NULL
);
711 assert(node
->l
== NULL
);
714 #ifdef PATRICIA_DEBUG
716 "patricia_lookup: new_node #2 %s/%d (child)\n",
717 prefix_toa(prefix
), prefix
->bitlen
);
718 #endif /* PATRICIA_DEBUG */
722 if(bitlen
== differ_bit
)
724 if(bitlen
< patricia
->maxbits
&&
725 BIT_TEST(test_addr
[bitlen
>> 3], 0x80 >> (bitlen
& 0x07)))
733 new_node
->parent
= node
->parent
;
734 if(node
->parent
== NULL
)
736 assert(patricia
->head
== node
);
737 patricia
->head
= new_node
;
739 else if(node
->parent
->r
== node
)
741 node
->parent
->r
= new_node
;
745 node
->parent
->l
= new_node
;
747 node
->parent
= new_node
;
748 #ifdef PATRICIA_DEBUG
750 "patricia_lookup: new_node #3 %s/%d (parent)\n",
751 prefix_toa(prefix
), prefix
->bitlen
);
752 #endif /* PATRICIA_DEBUG */
756 glue
= rb_malloc(sizeof(rb_patricia_node_t
));
757 glue
->bit
= differ_bit
;
759 glue
->parent
= node
->parent
;
761 patricia
->num_active_node
++;
762 if(differ_bit
< patricia
->maxbits
&&
763 BIT_TEST(addr
[differ_bit
>> 3], 0x80 >> (differ_bit
& 0x07)))
773 new_node
->parent
= glue
;
775 if(node
->parent
== NULL
)
777 assert(patricia
->head
== node
);
778 patricia
->head
= glue
;
780 else if(node
->parent
->r
== node
)
782 node
->parent
->r
= glue
;
786 node
->parent
->l
= glue
;
789 #ifdef PATRICIA_DEBUG
791 "patricia_lookup: new_node #4 %s/%d (glue+node)\n",
792 prefix_toa(prefix
), prefix
->bitlen
);
793 #endif /* PATRICIA_DEBUG */
800 rb_patricia_remove(rb_patricia_tree_t
* patricia
, rb_patricia_node_t
* node
)
802 rb_patricia_node_t
*parent
, *child
;
807 if(node
->r
&& node
->l
)
809 #ifdef PATRICIA_DEBUG
810 fprintf(stderr
, "patricia_remove: #0 %s/%d (r & l)\n",
811 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
812 #endif /* PATRICIA_DEBUG */
814 /* this might be a placeholder node -- have to check and make sure
815 * there is a prefix aossciated with it ! */
816 if(node
->prefix
!= NULL
)
817 Deref_Prefix(node
->prefix
);
819 /* Also I needed to clear data pointer -- masaki */
824 if(node
->r
== NULL
&& node
->l
== NULL
)
826 #ifdef PATRICIA_DEBUG
827 fprintf(stderr
, "patricia_remove: #1 %s/%d (!r & !l)\n",
828 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
829 #endif /* PATRICIA_DEBUG */
830 parent
= node
->parent
;
831 Deref_Prefix(node
->prefix
);
833 patricia
->num_active_node
--;
837 assert(patricia
->head
== node
);
838 patricia
->head
= NULL
;
842 if(parent
->r
== node
)
849 assert(parent
->l
== node
);
857 /* we need to remove parent too */
859 if(parent
->parent
== NULL
)
861 assert(patricia
->head
== parent
);
862 patricia
->head
= child
;
864 else if(parent
->parent
->r
== parent
)
866 parent
->parent
->r
= child
;
870 assert(parent
->parent
->l
== parent
);
871 parent
->parent
->l
= child
;
873 child
->parent
= parent
->parent
;
875 patricia
->num_active_node
--;
878 #ifdef PATRICIA_DEBUG
879 fprintf(stderr
, "patricia_remove: #2 %s/%d (r ^ l)\n",
880 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
881 #endif /* PATRICIA_DEBUG */
891 parent
= node
->parent
;
892 child
->parent
= parent
;
894 Deref_Prefix(node
->prefix
);
896 patricia
->num_active_node
--;
900 assert(patricia
->head
== node
);
901 patricia
->head
= child
;
905 if(parent
->r
== node
)
911 assert(parent
->l
== node
);
917 make_and_lookup_ip(rb_patricia_tree_t
* tree
, struct sockaddr
*in
, int bitlen
)
920 rb_patricia_node_t
*node
;
923 if(in
->sa_family
== AF_INET6
)
924 ipptr
= &((struct sockaddr_in6
*)in
)->sin6_addr
;
927 ipptr
= &((struct sockaddr_in
*)in
)->sin_addr
;
929 prefix
= New_Prefix(in
->sa_family
, ipptr
, bitlen
);
934 node
= rb_patricia_lookup(tree
, prefix
);
938 Deref_Prefix(prefix
);
944 make_and_lookup(rb_patricia_tree_t
* tree
, const char *string
)
947 rb_patricia_node_t
*node
;
949 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
951 node
= rb_patricia_lookup(tree
, prefix
);
955 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
957 node
= rb_patricia_lookup(tree
, prefix
);
962 #ifdef PATRICIA_DEBUG
963 printf("make_and_lookup: %s/%d\n", prefix_toa(prefix
), prefix
->bitlen
);
965 Deref_Prefix(prefix
);
970 static rb_patricia_node_t
*
971 try_search_exact(rb_patricia_tree_t
* tree
, char *string
)
974 rb_patricia_node_t
*node
;
975 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
977 node
= rb_patricia_search_exact(tree
, prefix
);
978 Deref_Prefix(prefix
);
982 else if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
984 node
= rb_patricia_search_exact(tree
, prefix
);
985 Deref_Prefix(prefix
);
994 lookup_then_remove(rb_patricia_tree_t
* tree
, char *string
)
996 rb_patricia_node_t
*node
;
998 if((node
= try_search_exact(tree
, string
)))
999 patricia_remove(tree
, node
);
1003 rb_patricia_node_t
*
1004 rb_match_ip(rb_patricia_tree_t
* tree
, struct sockaddr
*ip
)
1006 rb_prefix_t
*prefix
;
1007 rb_patricia_node_t
*node
;
1014 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1016 if(ip
->sa_family
== AF_INET6
)
1020 ipptr
= &((struct sockaddr_in6
*)ip
)->sin6_addr
;
1024 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1028 if((prefix
= New_Prefix(family
, ipptr
, len
)) != NULL
)
1030 node
= rb_patricia_search_best(tree
, prefix
);
1031 Deref_Prefix(prefix
);
1037 rb_patricia_node_t
*
1038 rb_match_ip_exact(rb_patricia_tree_t
* tree
, struct sockaddr
*ip
, unsigned int len
)
1040 rb_prefix_t
*prefix
;
1041 rb_patricia_node_t
*node
;
1049 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1051 if(ip
->sa_family
== AF_INET6
)
1056 ipptr
= &((struct sockaddr_in6
*)ip
)->sin6_addr
;
1061 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1065 if((prefix
= New_Prefix(family
, ipptr
, len
)) != NULL
)
1067 node
= rb_patricia_search_exact(tree
, prefix
);
1068 Deref_Prefix(prefix
);
1076 rb_patricia_node_t
*
1077 rb_match_string(rb_patricia_tree_t
* tree
, const char *string
)
1079 rb_patricia_node_t
*node
;
1080 rb_prefix_t
*prefix
;
1082 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
1084 node
= rb_patricia_search_best(tree
, prefix
);
1085 Deref_Prefix(prefix
);
1089 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
1091 node
= rb_patricia_search_best(tree
, prefix
);
1092 Deref_Prefix(prefix
);
1100 rb_patricia_node_t
*
1101 rb_match_exact_string(rb_patricia_tree_t
* tree
, const char *string
)
1103 rb_prefix_t
*prefix
;
1104 rb_patricia_node_t
*node
;
1105 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
1107 node
= rb_patricia_search_exact(tree
, prefix
);
1108 Deref_Prefix(prefix
);
1112 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
1114 node
= rb_patricia_search_exact(tree
, prefix
);
1115 Deref_Prefix(prefix
);