]>
jfr.im git - irc/rqf/shadowircd.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 * 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 <libratbox_config.h>
23 #include <ratbox_lib.h>
25 /* Enable both of these to debug patricia.c
27 * #define PATRICIA_DEBUG 1
30 #define PREFIX_HEAP_COUNT 1024
31 #define NODE_HEAP_COUNT 1024
32 #define PATRICIA_HEAP_COUNT 128
35 rb_init_patricia(void)
41 * convert prefix information to bytes
44 prefix_tochar(rb_prefix_t
*prefix
)
49 return ((uint8_t *)&prefix
->add
.sin
);
53 comp_with_mask(void *addr
, void *dest
, unsigned int mask
)
56 if( /* mask/8 == 0 || */ memcmp(addr
, dest
, mask
/ 8) == 0)
59 int m
= ((-1) << (8 - (mask
% 8)));
61 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));
97 prefix_toa(rb_prefix_t
*prefix
)
100 static char buf
[INET6_ADDRSTRLEN
+ 6];
102 static char buf
[16 + 6];
104 return (prefix_toa2(prefix
, buf
, sizeof(buf
)));
108 New_Prefix2(int family
, void *dest
, int bitlen
, rb_prefix_t
*prefix
)
110 int dynamic_allocated
= 0;
112 int default_bitlen
= 128;
114 int default_bitlen
= 32;
118 if(family
== AF_INET6
)
120 default_bitlen
= 128;
123 prefix
= rb_malloc(sizeof(rb_prefix_t
));
126 memcpy(&prefix
->add
.sin6
, dest
, 16);
130 if(family
== AF_INET
)
134 prefix
= rb_malloc(sizeof(rb_prefix_t
));
137 memcpy(&prefix
->add
.sin
, dest
, 4);
144 prefix
->bitlen
= (bitlen
>= 0) ? bitlen
: default_bitlen
;
145 prefix
->family
= family
;
146 prefix
->ref_count
= 0;
147 if(dynamic_allocated
)
155 New_Prefix(int family
, void *dest
, int bitlen
)
157 return (New_Prefix2(family
, dest
, bitlen
, NULL
));
163 ascii2prefix(int family
, const char *string
)
165 long bitlen
, maxbitlen
= 0;
167 struct in_addr sinaddr
;
169 struct in6_addr sinaddr6
;
177 /* easy way to handle both families */
182 if(strchr(string
, ':'))
186 if(family
== AF_INET
)
191 else if(family
== AF_INET6
)
197 if((cp
= strchr(string
, '/')) != NULL
)
199 bitlen
= atol(cp
+ 1);
201 /* copy the string to save. Avoid destroying the string */
202 assert(cp
- string
< MAXLINE
);
203 memcpy(save
, string
, cp
- string
);
204 save
[cp
- string
] = '\0';
206 if(bitlen
<= 0 || bitlen
> maxbitlen
)
214 if(family
== AF_INET
)
216 if((result
= rb_inet_pton(AF_INET
, string
, &sinaddr
)) <= 0)
218 return (New_Prefix(AF_INET
, &sinaddr
, bitlen
));
221 else if(family
== AF_INET6
)
223 if((result
= rb_inet_pton(AF_INET6
, string
, &sinaddr6
)) <= 0)
225 return (New_Prefix(AF_INET6
, &sinaddr6
, bitlen
));
233 Ref_Prefix(rb_prefix_t
*prefix
)
237 if(prefix
->ref_count
== 0)
239 /* make a copy in case of a static prefix */
240 return (New_Prefix2(prefix
->family
, &prefix
->add
, prefix
->bitlen
, NULL
));
247 Deref_Prefix(rb_prefix_t
*prefix
)
251 /* for secure programming, raise an assert. no static prefix can call this */
252 assert(prefix
->ref_count
> 0);
255 assert(prefix
->ref_count
>= 0);
256 if(prefix
->ref_count
<= 0)
265 // #define PATRICIA_DEBUG 1
267 static int num_active_patricia
= 0;
269 /* these routines support continuous mask only */
272 rb_new_patricia(int maxbits
)
274 rb_patricia_tree_t
*patricia
= rb_malloc(sizeof(rb_patricia_tree_t
));
276 patricia
->maxbits
= maxbits
;
277 patricia
->head
= NULL
;
278 patricia
->num_active_node
= 0;
279 assert(maxbits
<= RB_PATRICIA_MAXBITS
); /* XXX */
280 num_active_patricia
++;
286 * if func is supplied, it will be called as func(node->data)
287 * before deleting the node
291 rb_clear_patricia(rb_patricia_tree_t
*patricia
, void (*func
) (void *))
297 rb_patricia_node_t
*Xstack
[RB_PATRICIA_MAXBITS
+ 1];
298 rb_patricia_node_t
**Xsp
= Xstack
;
299 rb_patricia_node_t
*Xrn
= patricia
->head
;
303 rb_patricia_node_t
*l
= Xrn
->l
;
304 rb_patricia_node_t
*r
= Xrn
->r
;
308 Deref_Prefix(Xrn
->prefix
);
309 if(Xrn
->data
&& func
)
314 assert(Xrn
->data
== NULL
);
317 patricia
->num_active_node
--;
331 else if(Xsp
!= Xstack
)
337 Xrn
= (rb_patricia_node_t
*)0;
341 assert(patricia
->num_active_node
== 0);
347 rb_destroy_patricia(rb_patricia_tree_t
*patricia
, void (*func
) (void *))
349 rb_clear_patricia(patricia
, func
);
350 num_active_patricia
--;
355 * if func is supplied, it will be called as func(node->prefix, node->data)
359 rb_patricia_process(rb_patricia_tree_t
*patricia
, void (*func
) (rb_prefix_t
*, void *))
361 rb_patricia_node_t
*node
;
364 RB_PATRICIA_WALK(patricia
->head
, node
)
366 func(node
->prefix
, node
->data
);
368 RB_PATRICIA_WALK_END
;
372 rb_patricia_search_exact(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
)
374 rb_patricia_node_t
*node
;
380 assert(prefix
->bitlen
<= patricia
->maxbits
);
382 if(patricia
->head
== NULL
)
385 node
= patricia
->head
;
386 addr
= rb_prefix_touchar(prefix
);
387 bitlen
= prefix
->bitlen
;
389 while(node
->bit
< bitlen
)
392 if(BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
394 #ifdef PATRICIA_DEBUG
397 "patricia_search_exact: take right %s/%d\n",
398 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
401 "patricia_search_exact: take right at %d\n", node
->bit
);
402 #endif /* PATRICIA_DEBUG */
407 #ifdef PATRICIA_DEBUG
410 "patricia_search_exact: take left %s/%d\n",
411 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
414 "patricia_search_exact: take left at %d\n", node
->bit
);
415 #endif /* PATRICIA_DEBUG */
423 #ifdef PATRICIA_DEBUG
425 fprintf(stderr
, "patricia_search_exact: stop at %s/%d %d\n",
426 prefix_toa(node
->prefix
), node
->prefix
->bitlen
, node
->bit
);
428 fprintf(stderr
, "patricia_search_exact: stop at %d\n", node
->bit
);
429 #endif /* PATRICIA_DEBUG */
430 if(node
->bit
> bitlen
|| node
->prefix
== NULL
)
432 assert(node
->bit
== bitlen
);
433 assert(node
->bit
== node
->prefix
->bitlen
);
434 if(comp_with_mask(prefix_tochar(node
->prefix
), prefix_tochar(prefix
), bitlen
))
436 #ifdef PATRICIA_DEBUG
437 fprintf(stderr
, "patricia_search_exact: found %s/%d\n",
438 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
439 #endif /* PATRICIA_DEBUG */
445 /* if inclusive != 0, "best" may be the given prefix itself */
447 rb_patricia_search_best2(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
, int inclusive
)
449 rb_patricia_node_t
*node
;
450 rb_patricia_node_t
*stack
[RB_PATRICIA_MAXBITS
+ 1];
457 assert(prefix
->bitlen
<= patricia
->maxbits
);
459 if(patricia
->head
== NULL
)
462 node
= patricia
->head
;
463 addr
= rb_prefix_touchar(prefix
);
464 bitlen
= prefix
->bitlen
;
466 while(node
->bit
< bitlen
)
471 #ifdef PATRICIA_DEBUG
473 "patricia_search_best: push %s/%d\n",
474 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
475 #endif /* PATRICIA_DEBUG */
479 if(BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
481 #ifdef PATRICIA_DEBUG
484 "patricia_search_best: take right %s/%d\n",
485 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
488 "patricia_search_best: take right at %d\n", node
->bit
);
489 #endif /* PATRICIA_DEBUG */
494 #ifdef PATRICIA_DEBUG
497 "patricia_search_best: take left %s/%d\n",
498 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
501 "patricia_search_best: take left at %d\n", node
->bit
);
502 #endif /* PATRICIA_DEBUG */
510 if(inclusive
&& node
&& node
->prefix
)
513 #ifdef PATRICIA_DEBUG
515 fprintf(stderr
, "patricia_search_best: stop at null\n");
516 else if(node
->prefix
)
517 fprintf(stderr
, "patricia_search_best: stop at %s/%d\n",
518 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
520 fprintf(stderr
, "patricia_search_best: stop at %d\n", node
->bit
);
521 #endif /* PATRICIA_DEBUG */
529 #ifdef PATRICIA_DEBUG
530 fprintf(stderr
, "patricia_search_best: pop %s/%d\n",
531 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
532 #endif /* PATRICIA_DEBUG */
533 if(comp_with_mask(prefix_tochar(node
->prefix
),
534 prefix_tochar(prefix
), node
->prefix
->bitlen
))
536 #ifdef PATRICIA_DEBUG
538 "patricia_search_best: found %s/%d\n",
539 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
540 #endif /* PATRICIA_DEBUG */
549 rb_patricia_search_best(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
)
551 return (rb_patricia_search_best2(patricia
, prefix
, 1));
556 rb_patricia_lookup(rb_patricia_tree_t
*patricia
, rb_prefix_t
*prefix
)
558 rb_patricia_node_t
*node
, *new_node
, *parent
, *glue
;
559 uint8_t *addr
, *test_addr
;
560 unsigned int bitlen
, check_bit
, differ_bit
;
561 unsigned int i
, j
, r
;
565 assert(prefix
->bitlen
<= patricia
->maxbits
);
567 if(patricia
->head
== NULL
)
569 node
= rb_malloc(sizeof(rb_patricia_node_t
));
570 node
->bit
= prefix
->bitlen
;
571 node
->prefix
= Ref_Prefix(prefix
);
573 node
->l
= node
->r
= NULL
;
575 patricia
->head
= node
;
576 #ifdef PATRICIA_DEBUG
578 "patricia_lookup: new_node #0 %s/%d (head)\n",
579 prefix_toa(prefix
), prefix
->bitlen
);
580 #endif /* PATRICIA_DEBUG */
581 patricia
->num_active_node
++;
585 addr
= rb_prefix_touchar(prefix
);
586 bitlen
= prefix
->bitlen
;
587 node
= patricia
->head
;
589 while(node
->bit
< bitlen
|| node
->prefix
== NULL
)
592 if(node
->bit
< patricia
->maxbits
&&
593 BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
597 #ifdef PATRICIA_DEBUG
600 "patricia_lookup: take right %s/%d\n",
601 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
603 fprintf(stderr
, "patricia_lookup: take right at %d\n", node
->bit
);
604 #endif /* PATRICIA_DEBUG */
611 #ifdef PATRICIA_DEBUG
614 "patricia_lookup: take left %s/%d\n",
615 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
617 fprintf(stderr
, "patricia_lookup: take left at %d\n", node
->bit
);
618 #endif /* PATRICIA_DEBUG */
625 assert(node
->prefix
);
626 #ifdef PATRICIA_DEBUG
627 fprintf(stderr
, "patricia_lookup: stop at %s/%d\n",
628 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
629 #endif /* PATRICIA_DEBUG */
631 test_addr
= rb_prefix_touchar(node
->prefix
);
632 /* find the first bit different */
633 check_bit
= (node
->bit
< bitlen
) ? node
->bit
: bitlen
;
635 for(i
= 0; i
* 8 < check_bit
; i
++)
637 if((r
= (addr
[i
] ^ test_addr
[i
])) == 0)
639 differ_bit
= (i
+ 1) * 8;
642 /* I know the better way, but for now */
643 for(j
= 0; j
< 8; j
++)
645 if(BIT_TEST(r
, (0x80 >> j
)))
650 differ_bit
= i
* 8 + j
;
653 if(differ_bit
> check_bit
)
654 differ_bit
= check_bit
;
655 #ifdef PATRICIA_DEBUG
656 fprintf(stderr
, "patricia_lookup: differ_bit %d\n", differ_bit
);
657 #endif /* PATRICIA_DEBUG */
659 parent
= node
->parent
;
660 while(parent
&& parent
->bit
>= differ_bit
)
663 parent
= node
->parent
;
664 #ifdef PATRICIA_DEBUG
666 fprintf(stderr
, "patricia_lookup: up to %s/%d\n",
667 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
669 fprintf(stderr
, "patricia_lookup: up to %d\n", node
->bit
);
670 #endif /* PATRICIA_DEBUG */
673 if(differ_bit
== bitlen
&& node
->bit
== bitlen
)
677 #ifdef PATRICIA_DEBUG
678 fprintf(stderr
, "patricia_lookup: found %s/%d\n",
679 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
680 #endif /* PATRICIA_DEBUG */
683 node
->prefix
= Ref_Prefix(prefix
);
684 #ifdef PATRICIA_DEBUG
686 "patricia_lookup: new node #1 %s/%d (glue mod)\n",
687 prefix_toa(prefix
), prefix
->bitlen
);
688 #endif /* PATRICIA_DEBUG */
689 assert(node
->data
== NULL
);
693 new_node
= rb_malloc(sizeof(rb_patricia_node_t
));
694 new_node
->bit
= prefix
->bitlen
;
695 new_node
->prefix
= Ref_Prefix(prefix
);
696 new_node
->parent
= NULL
;
697 new_node
->l
= new_node
->r
= NULL
;
698 new_node
->data
= NULL
;
699 patricia
->num_active_node
++;
701 if(node
->bit
== differ_bit
)
703 new_node
->parent
= node
;
704 if(node
->bit
< patricia
->maxbits
&&
705 BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
707 assert(node
->r
== NULL
);
712 assert(node
->l
== NULL
);
715 #ifdef PATRICIA_DEBUG
717 "patricia_lookup: new_node #2 %s/%d (child)\n",
718 prefix_toa(prefix
), prefix
->bitlen
);
719 #endif /* PATRICIA_DEBUG */
723 if(bitlen
== differ_bit
)
725 if(bitlen
< patricia
->maxbits
&&
726 BIT_TEST(test_addr
[bitlen
>> 3], 0x80 >> (bitlen
& 0x07)))
734 new_node
->parent
= node
->parent
;
735 if(node
->parent
== NULL
)
737 assert(patricia
->head
== node
);
738 patricia
->head
= new_node
;
740 else if(node
->parent
->r
== node
)
742 node
->parent
->r
= new_node
;
746 node
->parent
->l
= new_node
;
748 node
->parent
= new_node
;
749 #ifdef PATRICIA_DEBUG
751 "patricia_lookup: new_node #3 %s/%d (parent)\n",
752 prefix_toa(prefix
), prefix
->bitlen
);
753 #endif /* PATRICIA_DEBUG */
757 glue
= rb_malloc(sizeof(rb_patricia_node_t
));
758 glue
->bit
= differ_bit
;
760 glue
->parent
= node
->parent
;
762 patricia
->num_active_node
++;
763 if(differ_bit
< patricia
->maxbits
&&
764 BIT_TEST(addr
[differ_bit
>> 3], 0x80 >> (differ_bit
& 0x07)))
774 new_node
->parent
= glue
;
776 if(node
->parent
== NULL
)
778 assert(patricia
->head
== node
);
779 patricia
->head
= glue
;
781 else if(node
->parent
->r
== node
)
783 node
->parent
->r
= glue
;
787 node
->parent
->l
= glue
;
790 #ifdef PATRICIA_DEBUG
792 "patricia_lookup: new_node #4 %s/%d (glue+node)\n",
793 prefix_toa(prefix
), prefix
->bitlen
);
794 #endif /* PATRICIA_DEBUG */
801 rb_patricia_remove(rb_patricia_tree_t
*patricia
, rb_patricia_node_t
*node
)
803 rb_patricia_node_t
*parent
, *child
;
808 if(node
->r
&& node
->l
)
810 #ifdef PATRICIA_DEBUG
811 fprintf(stderr
, "patricia_remove: #0 %s/%d (r & l)\n",
812 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
813 #endif /* PATRICIA_DEBUG */
815 /* this might be a placeholder node -- have to check and make sure
816 * there is a prefix aossciated with it ! */
817 if(node
->prefix
!= NULL
)
818 Deref_Prefix(node
->prefix
);
820 /* Also I needed to clear data pointer -- masaki */
825 if(node
->r
== NULL
&& node
->l
== NULL
)
827 #ifdef PATRICIA_DEBUG
828 fprintf(stderr
, "patricia_remove: #1 %s/%d (!r & !l)\n",
829 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
830 #endif /* PATRICIA_DEBUG */
831 parent
= node
->parent
;
832 Deref_Prefix(node
->prefix
);
834 patricia
->num_active_node
--;
838 assert(patricia
->head
== node
);
839 patricia
->head
= NULL
;
843 if(parent
->r
== node
)
850 assert(parent
->l
== node
);
858 /* we need to remove parent too */
860 if(parent
->parent
== NULL
)
862 assert(patricia
->head
== parent
);
863 patricia
->head
= child
;
865 else if(parent
->parent
->r
== parent
)
867 parent
->parent
->r
= child
;
871 assert(parent
->parent
->l
== parent
);
872 parent
->parent
->l
= child
;
874 child
->parent
= parent
->parent
;
876 patricia
->num_active_node
--;
879 #ifdef PATRICIA_DEBUG
880 fprintf(stderr
, "patricia_remove: #2 %s/%d (r ^ l)\n",
881 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
882 #endif /* PATRICIA_DEBUG */
892 parent
= node
->parent
;
893 child
->parent
= parent
;
895 Deref_Prefix(node
->prefix
);
897 patricia
->num_active_node
--;
901 assert(patricia
->head
== node
);
902 patricia
->head
= child
;
906 if(parent
->r
== node
)
912 assert(parent
->l
== node
);
918 make_and_lookup_ip(rb_patricia_tree_t
*tree
, struct sockaddr
*in
, int bitlen
)
921 rb_patricia_node_t
*node
;
924 if(in
->sa_family
== AF_INET6
)
925 ipptr
= &((struct sockaddr_in6
*)in
)->sin6_addr
;
928 ipptr
= &((struct sockaddr_in
*)in
)->sin_addr
;
930 prefix
= New_Prefix(in
->sa_family
, ipptr
, bitlen
);
935 node
= rb_patricia_lookup(tree
, prefix
);
939 Deref_Prefix(prefix
);
945 make_and_lookup(rb_patricia_tree_t
*tree
, const char *string
)
948 rb_patricia_node_t
*node
;
950 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
952 node
= rb_patricia_lookup(tree
, prefix
);
956 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
958 node
= rb_patricia_lookup(tree
, prefix
);
963 #ifdef PATRICIA_DEBUG
964 printf("make_and_lookup: %s/%d\n", prefix_toa(prefix
), prefix
->bitlen
);
966 Deref_Prefix(prefix
);
971 static rb_patricia_node_t
*
972 try_search_exact(rb_patricia_tree_t
*tree
, char *string
)
975 rb_patricia_node_t
*node
;
976 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
978 node
= rb_patricia_search_exact(tree
, prefix
);
979 Deref_Prefix(prefix
);
983 else if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
985 node
= rb_patricia_search_exact(tree
, prefix
);
986 Deref_Prefix(prefix
);
995 lookup_then_remove(rb_patricia_tree_t
*tree
, char *string
)
997 rb_patricia_node_t
*node
;
999 if((node
= try_search_exact(tree
, string
)))
1000 patricia_remove(tree
, node
);
1004 rb_patricia_node_t
*
1005 rb_match_ip(rb_patricia_tree_t
*tree
, struct sockaddr
*ip
)
1007 rb_prefix_t
*prefix
;
1008 rb_patricia_node_t
*node
;
1015 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1017 if(ip
->sa_family
== AF_INET6
)
1021 ipptr
= &((struct sockaddr_in6
*)ip
)->sin6_addr
;
1027 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1031 if((prefix
= New_Prefix(family
, ipptr
, len
)) != NULL
)
1033 node
= rb_patricia_search_best(tree
, prefix
);
1034 Deref_Prefix(prefix
);
1040 rb_patricia_node_t
*
1041 rb_match_ip_exact(rb_patricia_tree_t
*tree
, struct sockaddr
*ip
, unsigned int len
)
1043 rb_prefix_t
*prefix
;
1044 rb_patricia_node_t
*node
;
1052 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1054 if(ip
->sa_family
== AF_INET6
)
1059 ipptr
= &((struct sockaddr_in6
*)ip
)->sin6_addr
;
1066 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1070 if((prefix
= New_Prefix(family
, ipptr
, len
)) != NULL
)
1072 node
= rb_patricia_search_exact(tree
, prefix
);
1073 Deref_Prefix(prefix
);
1081 rb_patricia_node_t
*
1082 rb_match_string(rb_patricia_tree_t
*tree
, const char *string
)
1084 rb_patricia_node_t
*node
;
1085 rb_prefix_t
*prefix
;
1087 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
1089 node
= rb_patricia_search_best(tree
, prefix
);
1090 Deref_Prefix(prefix
);
1094 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
1096 node
= rb_patricia_search_best(tree
, prefix
);
1097 Deref_Prefix(prefix
);
1105 rb_patricia_node_t
*
1106 rb_match_exact_string(rb_patricia_tree_t
*tree
, const char *string
)
1108 rb_prefix_t
*prefix
;
1109 rb_patricia_node_t
*node
;
1110 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
1112 node
= rb_patricia_search_exact(tree
, prefix
);
1113 Deref_Prefix(prefix
);
1117 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
1119 node
= rb_patricia_search_exact(tree
, prefix
);
1120 Deref_Prefix(prefix
);