2 * Yanked out of Net::Patricia by Aaron Sethman <androsyn@ratbox.org>
4 * $Id: patricia.c 26 2006-09-20 18:02:06Z spb $
5 * Dave Plonka <plonka@doit.wisc.edu>
7 * This product includes software developed by the University of Michigan,
8 * Merit Network, Inc., and their contributors.
10 * This file had been called "radix.c" in the MRT sources.
12 * I renamed it to "patricia.c" since it's not an implementation of a general
13 * radix trie. Also I pulled in various requirements from "prefix.c" and
14 * "demo.c" so that it could be used as a standalone API.
16 * This product includes software developed by the University of Michigan, Merit
17 * Network, Inc., and their contributors.
24 #include "ircd_defs.h"
28 extern BlockHeap
*prefix_heap
;
29 extern BlockHeap
*node_heap
;
30 extern BlockHeap
*patricia_heap
;
32 /* Enable both of these to debug patricia.c
34 * #define PATRICIA_DEBUG 1
37 #define PREFIX_HEAP_COUNT 1024
38 #define NODE_HEAP_COUNT 1024
39 #define PATRICIA_HEAP_COUNT 128
44 prefix_heap
= BlockHeapCreate(sizeof(prefix_t
), PREFIX_HEAP_COUNT
);
45 node_heap
= BlockHeapCreate(sizeof(patricia_node_t
), NODE_HEAP_COUNT
);
46 patricia_heap
= BlockHeapCreate(sizeof(patricia_tree_t
), PATRICIA_HEAP_COUNT
);
50 * convert prefix information to bytes
53 prefix_tochar(prefix_t
* prefix
)
58 return ((u_char
*) & prefix
->add
.sin
);
63 comp_with_mask(void *addr
, void *dest
, u_int mask
)
66 if( /* mask/8 == 0 || */ memcmp(addr
, dest
, mask
/ 8) == 0)
69 int m
= ((-1) << (8 - (mask
% 8)));
71 if(mask
% 8 == 0 || (((u_char
*) addr
)[n
] & m
) == (((u_char
*) dest
)[n
] & m
))
79 prefix_toa2x(prefix_t
* prefix
, char *buf
, int buf_len
, int with_len
)
84 strcpy(buf
, "(NULL)");
87 inet_ntop(prefix
->family
, &prefix
->add
.sin
, buf
, buf_len
);
90 ircsnprintf(tmp
, sizeof(tmp
), "/%d", prefix
->bitlen
);
97 * convert prefix information to ascii string
101 prefix_toa2(prefix_t
* prefix
, char *buff
, int buf_len
)
103 return (prefix_toa2x(prefix
, buff
, buf_len
, 0));
106 prefix_toa(prefix_t
* prefix
)
109 static char buf
[INET6_ADDRSTRLEN
+ 6];
111 static char buf
[16 + 6];
113 return (prefix_toa2(prefix
, buf
, sizeof(buf
)));
117 New_Prefix2(int family
, void *dest
, int bitlen
, prefix_t
* prefix
)
119 int dynamic_allocated
= 0;
121 int default_bitlen
= 128;
123 int default_bitlen
= 32;
127 if(family
== AF_INET6
)
129 default_bitlen
= 128;
132 prefix
= BlockHeapAlloc(prefix_heap
);
135 memcpy(&prefix
->add
.sin6
, dest
, 16);
139 if(family
== AF_INET
)
143 prefix
= BlockHeapAlloc(prefix_heap
);
146 memcpy(&prefix
->add
.sin
, dest
, 4);
153 prefix
->bitlen
= (bitlen
>= 0) ? bitlen
: default_bitlen
;
154 prefix
->family
= family
;
155 prefix
->ref_count
= 0;
156 if(dynamic_allocated
)
164 New_Prefix(int family
, void *dest
, int bitlen
)
166 return (New_Prefix2(family
, dest
, bitlen
, NULL
));
172 ascii2prefix(int family
, const char *string
)
174 long bitlen
, maxbitlen
= 0;
176 struct in_addr sinaddr
;
178 struct in6_addr sinaddr6
;
186 /* easy way to handle both families */
191 if(strchr(string
, ':'))
195 if(family
== AF_INET
)
200 else if(family
== AF_INET6
)
206 if((cp
= strchr(string
, '/')) != NULL
)
208 bitlen
= atol(cp
+ 1);
210 /* copy the string to save. Avoid destroying the string */
211 assert(cp
- string
< MAXLINE
);
212 memcpy(save
, string
, cp
- string
);
213 save
[cp
- string
] = '\0';
215 if(bitlen
<= 0 || bitlen
> maxbitlen
)
223 if(family
== AF_INET
)
225 if((result
= inetpton(AF_INET
, string
, &sinaddr
)) <= 0)
227 return (New_Prefix(AF_INET
, &sinaddr
, bitlen
));
230 else if(family
== AF_INET6
)
232 if((result
= inetpton(AF_INET6
, string
, &sinaddr6
)) <= 0)
234 return (New_Prefix(AF_INET6
, &sinaddr6
, bitlen
));
242 Ref_Prefix(prefix_t
* prefix
)
246 if(prefix
->ref_count
== 0)
248 /* make a copy in case of a static prefix */
249 return (New_Prefix2(prefix
->family
, &prefix
->add
, prefix
->bitlen
, NULL
));
256 Deref_Prefix(prefix_t
* prefix
)
260 /* for secure programming, raise an assert. no static prefix can call this */
261 assert(prefix
->ref_count
> 0);
264 assert(prefix
->ref_count
>= 0);
265 if(prefix
->ref_count
<= 0)
267 BlockHeapFree(prefix_heap
, prefix
);
274 /* #define PATRICIA_DEBUG 1 */
276 static int num_active_patricia
= 0;
278 /* these routines support continuous mask only */
281 New_Patricia(int maxbits
)
283 patricia_tree_t
*patricia
= BlockHeapAlloc(patricia_heap
);
285 patricia
->maxbits
= maxbits
;
286 patricia
->head
= NULL
;
287 patricia
->num_active_node
= 0;
288 assert(maxbits
<= PATRICIA_MAXBITS
); /* XXX */
289 num_active_patricia
++;
295 * if func is supplied, it will be called as func(node->data)
296 * before deleting the node
300 Clear_Patricia(patricia_tree_t
* patricia
, void_fn_t func
)
306 patricia_node_t
*Xstack
[PATRICIA_MAXBITS
+ 1];
307 patricia_node_t
**Xsp
= Xstack
;
308 patricia_node_t
*Xrn
= patricia
->head
;
312 patricia_node_t
*l
= Xrn
->l
;
313 patricia_node_t
*r
= Xrn
->r
;
317 Deref_Prefix(Xrn
->prefix
);
318 if(Xrn
->data
&& func
)
323 assert(Xrn
->data
== NULL
);
325 BlockHeapFree(node_heap
, Xrn
);
326 patricia
->num_active_node
--;
340 else if(Xsp
!= Xstack
)
346 Xrn
= (patricia_node_t
*) 0;
350 assert(patricia
->num_active_node
== 0);
351 BlockHeapFree(patricia_heap
, patricia
);
356 Destroy_Patricia(patricia_tree_t
* patricia
, void_fn_t func
)
358 Clear_Patricia(patricia
, func
);
359 num_active_patricia
--;
364 * if func is supplied, it will be called as func(node->prefix, node->data)
368 patricia_process(patricia_tree_t
* patricia
, void_fn_t func
)
370 patricia_node_t
*node
;
373 PATRICIA_WALK(patricia
->head
, node
)
375 func(node
->prefix
, node
->data
);
381 patricia_search_exact(patricia_tree_t
* patricia
, prefix_t
* prefix
)
383 patricia_node_t
*node
;
389 assert(prefix
->bitlen
<= patricia
->maxbits
);
391 if(patricia
->head
== NULL
)
394 node
= patricia
->head
;
395 addr
= prefix_touchar(prefix
);
396 bitlen
= prefix
->bitlen
;
398 while (node
->bit
< bitlen
)
401 if(BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
403 #ifdef PATRICIA_DEBUG
406 "patricia_search_exact: take right %s/%d\n",
407 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
410 "patricia_search_exact: take right at %d\n", node
->bit
);
411 #endif /* PATRICIA_DEBUG */
416 #ifdef PATRICIA_DEBUG
419 "patricia_search_exact: take left %s/%d\n",
420 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
423 "patricia_search_exact: take left at %d\n", node
->bit
);
424 #endif /* PATRICIA_DEBUG */
432 #ifdef PATRICIA_DEBUG
434 fprintf(stderr
, "patricia_search_exact: stop at %s/%d %d\n",
435 prefix_toa(node
->prefix
), node
->prefix
->bitlen
, node
->bit
);
437 fprintf(stderr
, "patricia_search_exact: stop at %d\n", node
->bit
);
438 #endif /* PATRICIA_DEBUG */
439 if(node
->bit
> bitlen
|| node
->prefix
== NULL
)
441 assert(node
->bit
== bitlen
);
442 assert(node
->bit
== node
->prefix
->bitlen
);
443 if(comp_with_mask(prefix_tochar(node
->prefix
), prefix_tochar(prefix
), bitlen
))
445 #ifdef PATRICIA_DEBUG
446 fprintf(stderr
, "patricia_search_exact: found %s/%d\n",
447 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
448 #endif /* PATRICIA_DEBUG */
454 /* if inclusive != 0, "best" may be the given prefix itself */
456 patricia_search_best2(patricia_tree_t
* patricia
, prefix_t
* prefix
, int inclusive
)
458 patricia_node_t
*node
;
459 patricia_node_t
*stack
[PATRICIA_MAXBITS
+ 1];
466 assert(prefix
->bitlen
<= patricia
->maxbits
);
468 if(patricia
->head
== NULL
)
471 node
= patricia
->head
;
472 addr
= prefix_touchar(prefix
);
473 bitlen
= prefix
->bitlen
;
475 while (node
->bit
< bitlen
)
480 #ifdef PATRICIA_DEBUG
482 "patricia_search_best: push %s/%d\n",
483 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
484 #endif /* PATRICIA_DEBUG */
488 if(BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
490 #ifdef PATRICIA_DEBUG
493 "patricia_search_best: take right %s/%d\n",
494 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
497 "patricia_search_best: take right at %d\n", node
->bit
);
498 #endif /* PATRICIA_DEBUG */
503 #ifdef PATRICIA_DEBUG
506 "patricia_search_best: take left %s/%d\n",
507 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
510 "patricia_search_best: take left at %d\n", node
->bit
);
511 #endif /* PATRICIA_DEBUG */
519 if(inclusive
&& node
&& node
->prefix
)
522 #ifdef PATRICIA_DEBUG
524 fprintf(stderr
, "patricia_search_best: stop at null\n");
525 else if(node
->prefix
)
526 fprintf(stderr
, "patricia_search_best: stop at %s/%d\n",
527 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
529 fprintf(stderr
, "patricia_search_best: stop at %d\n", node
->bit
);
530 #endif /* PATRICIA_DEBUG */
538 #ifdef PATRICIA_DEBUG
539 fprintf(stderr
, "patricia_search_best: pop %s/%d\n",
540 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
541 #endif /* PATRICIA_DEBUG */
542 if(comp_with_mask(prefix_tochar(node
->prefix
),
543 prefix_tochar(prefix
), node
->prefix
->bitlen
))
545 #ifdef PATRICIA_DEBUG
547 "patricia_search_best: found %s/%d\n",
548 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
549 #endif /* PATRICIA_DEBUG */
558 patricia_search_best(patricia_tree_t
* patricia
, prefix_t
* prefix
)
560 return (patricia_search_best2(patricia
, prefix
, 1));
565 patricia_lookup(patricia_tree_t
* patricia
, prefix_t
* prefix
)
567 patricia_node_t
*node
, *new_node
, *parent
, *glue
;
568 u_char
*addr
, *test_addr
;
569 u_int bitlen
, check_bit
, differ_bit
;
570 unsigned int i
, j
, r
;
574 assert(prefix
->bitlen
<= patricia
->maxbits
);
576 if(patricia
->head
== NULL
)
578 node
= BlockHeapAlloc(node_heap
);
579 node
->bit
= prefix
->bitlen
;
580 node
->prefix
= Ref_Prefix(prefix
);
582 node
->l
= node
->r
= NULL
;
584 patricia
->head
= node
;
585 #ifdef PATRICIA_DEBUG
587 "patricia_lookup: new_node #0 %s/%d (head)\n",
588 prefix_toa(prefix
), prefix
->bitlen
);
589 #endif /* PATRICIA_DEBUG */
590 patricia
->num_active_node
++;
594 addr
= prefix_touchar(prefix
);
595 bitlen
= prefix
->bitlen
;
596 node
= patricia
->head
;
598 while (node
->bit
< bitlen
|| node
->prefix
== NULL
)
601 if(node
->bit
< patricia
->maxbits
&&
602 BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
606 #ifdef PATRICIA_DEBUG
609 "patricia_lookup: take right %s/%d\n",
610 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
612 fprintf(stderr
, "patricia_lookup: take right at %d\n", node
->bit
);
613 #endif /* PATRICIA_DEBUG */
620 #ifdef PATRICIA_DEBUG
623 "patricia_lookup: take left %s/%d\n",
624 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
626 fprintf(stderr
, "patricia_lookup: take left at %d\n", node
->bit
);
627 #endif /* PATRICIA_DEBUG */
634 assert(node
->prefix
);
635 #ifdef PATRICIA_DEBUG
636 fprintf(stderr
, "patricia_lookup: stop at %s/%d\n",
637 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
638 #endif /* PATRICIA_DEBUG */
640 test_addr
= prefix_touchar(node
->prefix
);
641 /* find the first bit different */
642 check_bit
= (node
->bit
< bitlen
) ? node
->bit
: bitlen
;
644 for (i
= 0; i
* 8 < check_bit
; i
++)
646 if((r
= (addr
[i
] ^ test_addr
[i
])) == 0)
648 differ_bit
= (i
+ 1) * 8;
651 /* I know the better way, but for now */
652 for (j
= 0; j
< 8; j
++)
654 if(BIT_TEST(r
, (0x80 >> j
)))
659 differ_bit
= i
* 8 + j
;
662 if(differ_bit
> check_bit
)
663 differ_bit
= check_bit
;
664 #ifdef PATRICIA_DEBUG
665 fprintf(stderr
, "patricia_lookup: differ_bit %d\n", differ_bit
);
666 #endif /* PATRICIA_DEBUG */
668 parent
= node
->parent
;
669 while (parent
&& parent
->bit
>= differ_bit
)
672 parent
= node
->parent
;
673 #ifdef PATRICIA_DEBUG
675 fprintf(stderr
, "patricia_lookup: up to %s/%d\n",
676 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
678 fprintf(stderr
, "patricia_lookup: up to %d\n", node
->bit
);
679 #endif /* PATRICIA_DEBUG */
682 if(differ_bit
== bitlen
&& node
->bit
== bitlen
)
686 #ifdef PATRICIA_DEBUG
687 fprintf(stderr
, "patricia_lookup: found %s/%d\n",
688 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
689 #endif /* PATRICIA_DEBUG */
692 node
->prefix
= Ref_Prefix(prefix
);
693 #ifdef PATRICIA_DEBUG
695 "patricia_lookup: new node #1 %s/%d (glue mod)\n",
696 prefix_toa(prefix
), prefix
->bitlen
);
697 #endif /* PATRICIA_DEBUG */
698 assert(node
->data
== NULL
);
702 new_node
= BlockHeapAlloc(node_heap
);
703 new_node
->bit
= prefix
->bitlen
;
704 new_node
->prefix
= Ref_Prefix(prefix
);
705 new_node
->parent
= NULL
;
706 new_node
->l
= new_node
->r
= NULL
;
707 new_node
->data
= NULL
;
708 patricia
->num_active_node
++;
710 if(node
->bit
== differ_bit
)
712 new_node
->parent
= node
;
713 if(node
->bit
< patricia
->maxbits
&&
714 BIT_TEST(addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
716 assert(node
->r
== NULL
);
721 assert(node
->l
== NULL
);
724 #ifdef PATRICIA_DEBUG
726 "patricia_lookup: new_node #2 %s/%d (child)\n",
727 prefix_toa(prefix
), prefix
->bitlen
);
728 #endif /* PATRICIA_DEBUG */
732 if(bitlen
== differ_bit
)
734 if(bitlen
< patricia
->maxbits
&&
735 BIT_TEST(test_addr
[bitlen
>> 3], 0x80 >> (bitlen
& 0x07)))
743 new_node
->parent
= node
->parent
;
744 if(node
->parent
== NULL
)
746 assert(patricia
->head
== node
);
747 patricia
->head
= new_node
;
749 else if(node
->parent
->r
== node
)
751 node
->parent
->r
= new_node
;
755 node
->parent
->l
= new_node
;
757 node
->parent
= new_node
;
758 #ifdef PATRICIA_DEBUG
760 "patricia_lookup: new_node #3 %s/%d (parent)\n",
761 prefix_toa(prefix
), prefix
->bitlen
);
762 #endif /* PATRICIA_DEBUG */
766 glue
= BlockHeapAlloc(node_heap
);
767 glue
->bit
= differ_bit
;
769 glue
->parent
= node
->parent
;
771 patricia
->num_active_node
++;
772 if(differ_bit
< patricia
->maxbits
&&
773 BIT_TEST(addr
[differ_bit
>> 3], 0x80 >> (differ_bit
& 0x07)))
783 new_node
->parent
= glue
;
785 if(node
->parent
== NULL
)
787 assert(patricia
->head
== node
);
788 patricia
->head
= glue
;
790 else if(node
->parent
->r
== node
)
792 node
->parent
->r
= glue
;
796 node
->parent
->l
= glue
;
799 #ifdef PATRICIA_DEBUG
801 "patricia_lookup: new_node #4 %s/%d (glue+node)\n",
802 prefix_toa(prefix
), prefix
->bitlen
);
803 #endif /* PATRICIA_DEBUG */
810 patricia_remove(patricia_tree_t
* patricia
, patricia_node_t
* node
)
812 patricia_node_t
*parent
, *child
;
817 if(node
->r
&& node
->l
)
819 #ifdef PATRICIA_DEBUG
820 fprintf(stderr
, "patricia_remove: #0 %s/%d (r & l)\n",
821 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
822 #endif /* PATRICIA_DEBUG */
824 /* this might be a placeholder node -- have to check and make sure
825 * there is a prefix aossciated with it ! */
826 if(node
->prefix
!= NULL
)
827 Deref_Prefix(node
->prefix
);
829 /* Also I needed to clear data pointer -- masaki */
834 if(node
->r
== NULL
&& node
->l
== NULL
)
836 #ifdef PATRICIA_DEBUG
837 fprintf(stderr
, "patricia_remove: #1 %s/%d (!r & !l)\n",
838 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
839 #endif /* PATRICIA_DEBUG */
840 parent
= node
->parent
;
841 Deref_Prefix(node
->prefix
);
842 BlockHeapFree(node_heap
, node
);
843 patricia
->num_active_node
--;
847 assert(patricia
->head
== node
);
848 patricia
->head
= NULL
;
852 if(parent
->r
== node
)
859 assert(parent
->l
== node
);
867 /* we need to remove parent too */
869 if(parent
->parent
== NULL
)
871 assert(patricia
->head
== parent
);
872 patricia
->head
= child
;
874 else if(parent
->parent
->r
== parent
)
876 parent
->parent
->r
= child
;
880 assert(parent
->parent
->l
== parent
);
881 parent
->parent
->l
= child
;
883 child
->parent
= parent
->parent
;
884 BlockHeapFree(node_heap
, parent
);
885 patricia
->num_active_node
--;
888 #ifdef PATRICIA_DEBUG
889 fprintf(stderr
, "patricia_remove: #2 %s/%d (r ^ l)\n",
890 prefix_toa(node
->prefix
), node
->prefix
->bitlen
);
891 #endif /* PATRICIA_DEBUG */
901 parent
= node
->parent
;
902 child
->parent
= parent
;
904 Deref_Prefix(node
->prefix
);
905 BlockHeapFree(node_heap
, node
);
906 patricia
->num_active_node
--;
910 assert(patricia
->head
== node
);
911 patricia
->head
= child
;
915 if(parent
->r
== node
)
921 assert(parent
->l
== node
);
927 make_and_lookup_ip(patricia_tree_t
* tree
, struct sockaddr
*in
, int bitlen
)
930 patricia_node_t
*node
;
933 if(in
->sa_family
== AF_INET6
)
934 ipptr
= &((struct sockaddr_in6
*)in
)->sin6_addr
;
937 ipptr
= &((struct sockaddr_in
*)in
)->sin_addr
;
939 prefix
= New_Prefix(in
->sa_family
, ipptr
, bitlen
);
944 node
= patricia_lookup(tree
, prefix
);
948 Deref_Prefix(prefix
);
954 make_and_lookup(patricia_tree_t
* tree
, const char *string
)
957 patricia_node_t
*node
;
959 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
961 node
= patricia_lookup(tree
, prefix
);
965 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
967 node
= patricia_lookup(tree
, prefix
);
972 #ifdef PATRICIA_DEBUG
973 printf("make_and_lookup: %s/%d\n", prefix_toa(prefix
), prefix
->bitlen
);
975 Deref_Prefix(prefix
);
980 static patricia_node_t
*
981 try_search_exact(patricia_tree_t
* tree
, char *string
)
984 patricia_node_t
*node
;
985 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
987 node
= patricia_search_exact(tree
, prefix
);
988 Deref_Prefix(prefix
);
992 else if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
994 node
= patricia_search_exact(tree
, prefix
);
995 Deref_Prefix(prefix
);
1004 lookup_then_remove(patricia_tree_t
* tree
, char *string
)
1006 patricia_node_t
*node
;
1008 if((node
= try_search_exact(tree
, string
)))
1009 patricia_remove(tree
, node
);
1014 match_ip(patricia_tree_t
* tree
, struct sockaddr
*ip
)
1017 patricia_node_t
*node
;
1024 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1026 if(ip
->sa_family
== AF_INET6
)
1030 ipptr
= &((struct sockaddr_in6
*)ip
)->sin6_addr
;
1034 ipptr
= &((struct sockaddr_in
*)ip
)->sin_addr
;
1038 if((prefix
= New_Prefix(family
, ipptr
, len
)) != NULL
)
1040 node
= patricia_search_best(tree
, prefix
);
1041 Deref_Prefix(prefix
);
1048 match_string(patricia_tree_t
* tree
, const char *string
)
1050 patricia_node_t
*node
;
1053 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
1055 node
= patricia_search_best(tree
, prefix
);
1056 Deref_Prefix(prefix
);
1060 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
1062 node
= patricia_search_best(tree
, prefix
);
1063 Deref_Prefix(prefix
);
1072 match_exact_string(patricia_tree_t
* tree
, const char *string
)
1075 patricia_node_t
*node
;
1076 if((prefix
= ascii2prefix(AF_INET
, string
)) != NULL
)
1078 node
= patricia_search_exact(tree
, prefix
);
1079 Deref_Prefix(prefix
);
1083 if((prefix
= ascii2prefix(AF_INET6
, string
)) != NULL
)
1085 node
= patricia_search_exact(tree
, prefix
);
1086 Deref_Prefix(prefix
);