]>
jfr.im git - irc/quakenet/newserv.git/blob - patricia/patricialib.c
2 * $Id: patricia.c,v 1.7 2005/12/07 20:46:41 dplonka Exp $
3 * Dave Plonka <plonka@doit.wisc.edu>
5 * This product includes software developed by the University of Michigan,
6 * Merit Network, Inc., and their contributors.
8 * This file had been called "radix.c" in the MRT sources.
10 * I renamed it to "patricia.c" since it's not an implementation of a general
11 * radix trie. Also I pulled in various requirements from "prefix.c" and
12 * "demo.c" so that it could be used as a standalone API.
15 char patricia_copyright
[] =
16 "This product includes software developed by the University of Michigan, Merit"
17 "Network, Inc., and their contributors.";
19 #include <assert.h> /* assert */
20 #include <ctype.h> /* isdigit */
21 #include <errno.h> /* errno */
22 #include <math.h> /* sin */
23 #include <stddef.h> /* NULL */
24 #include <stdio.h> /* sprintf, fprintf, stderr */
25 #include <stdlib.h> /* free, atol, calloc */
26 #include <string.h> /* memcpy, strchr, strlen */
30 //#define LEAK_DETECTION
33 #define MAGIC 0x6a3b4ef3
38 patricia_node_t
*real_node
;
43 * convert prefix information to bytes
46 prefix_tochar (prefix_t
* prefix
)
51 return ((u_char
*) & prefix
->sin
);
55 comp_with_mask (void *addr
, void *dest
, u_int mask
)
58 if ( /* mask/8 == 0 || */ memcmp (addr
, dest
, mask
/ 8) == 0) {
60 int m
= ((-1) << (8 - (mask
% 8)));
62 if (mask
% 8 == 0 || (((u_char
*)addr
)[n
] & m
) == (((u_char
*)dest
)[n
] & m
))
70 patricia_new_prefix (struct irc_in_addr
*dest
, int bitlen
)
72 prefix_t
*prefix
= newprefix();
75 memcpy (&prefix
->sin
, dest
, 16);
76 prefix
->bitlen
= (bitlen
>= 0)? bitlen
: 128;
77 prefix
->ref_count
= 1;
83 patricia_ref_prefix (prefix_t
* prefix
)
87 if (prefix
->ref_count
== 0) {
88 /* make a copy in case of a static prefix */
89 return (patricia_new_prefix (&prefix
->sin
, prefix
->bitlen
));
96 patricia_deref_prefix (prefix_t
* prefix
)
100 /* for secure programming, raise an assert. no static prefix can call this */
101 assert (prefix
->ref_count
> 0);
104 if (prefix
->ref_count
<= 0) {
110 /* these routines support continuous mask only */
113 patricia_new_tree (int maxbits
)
115 patricia_tree_t
*patricia
= calloc(1, sizeof *patricia
);
117 patricia
->maxbits
= maxbits
;
118 patricia
->head
= NULL
;
119 patricia
->num_active_node
= 0;
120 assert (maxbits
<= PATRICIA_MAXBITS
); /* XXX */
126 patricia_clear_tree (patricia_tree_t
*patricia
, void_fn_t func
)
129 if (patricia
->head
) {
131 patricia_node_t
*Xstack
[PATRICIA_MAXBITS
+1];
132 patricia_node_t
**Xsp
= Xstack
;
133 patricia_node_t
*Xrn
= patricia
->head
;
136 patricia_node_t
*l
= Xrn
->l
;
137 patricia_node_t
*r
= Xrn
->r
;
140 if (Xrn
->exts
&& func
)
142 patricia_deref_prefix (Xrn
->prefix
);
145 patricia
->num_active_node
--;
154 } else if (Xsp
!= Xstack
) {
157 Xrn
= (patricia_node_t
*) 0;
161 assert (patricia
->num_active_node
== 0);
165 patricia_destroy_tree (patricia_tree_t
*patricia
, void_fn_t func
)
167 patricia_clear_tree (patricia
, func
);
169 /*TODO: EXTENSIONS!*/
174 * if func is supplied, it will be called as func(node->prefix)
178 patricia_process (patricia_tree_t
*patricia
, void_fn_t func
)
180 patricia_node_t
*node
;
183 PATRICIA_WALK (patricia
->head
, node
) {
189 patricia_walk_inorder(patricia_node_t
*node
, void_fn_t func
)
195 n
+= patricia_walk_inorder(node
->l
, func
);
204 n
+= patricia_walk_inorder(node
->r
, func
);
212 patricia_search_exact (patricia_tree_t
*patricia
, struct irc_in_addr
*sin
, unsigned char bitlen
)
214 patricia_node_t
*node
;
219 assert (bitlen
<= patricia
->maxbits
);
221 if (patricia
->head
== NULL
)
224 node
= patricia
->head
;
225 addr
= (u_char
*)sin
;
227 while (node
->bit
< bitlen
) {
228 if (is_bit_set(addr
,node
->bit
))
237 if (node
->bit
> bitlen
|| node
->prefix
== NULL
)
239 assert (node
->bit
== bitlen
);
240 assert (node
->bit
== node
->prefix
->bitlen
);
241 if (comp_with_mask (prefix_tochar (node
->prefix
), addr
, bitlen
)) {
248 /* if inclusive != 0, "best" may be the given prefix itself */
250 patricia_search_best2 (patricia_tree_t
*patricia
, struct irc_in_addr
*sin
, unsigned char bitlen
, int inclusive
)
252 patricia_node_t
*node
;
253 patricia_node_t
*stack
[PATRICIA_MAXBITS
+ 1];
259 assert (bitlen
<= patricia
->maxbits
);
261 if (patricia
->head
== NULL
)
264 node
= patricia
->head
;
265 addr
= (u_char
*)sin
;
267 while (node
->bit
< bitlen
) {
273 if (is_bit_set(addr
,node
->bit
)) {
284 if (inclusive
&& node
&& node
->prefix
)
292 if (comp_with_mask (prefix_tochar (node
->prefix
),
294 node
->prefix
->bitlen
)) {
303 patricia_search_best (patricia_tree_t
*patricia
, struct irc_in_addr
*sin
, unsigned char bitlen
)
305 return (patricia_search_best2 (patricia
, sin
, bitlen
, 1));
310 patricia_lookup (patricia_tree_t
*patricia
, prefix_t
*prefix
)
312 patricia_node_t
*node
, *new_node
, *parent
, *glue
;
313 u_char
*addr
, *test_addr
;
314 u_int bitlen
, check_bit
, differ_bit
;
319 assert (prefix
->bitlen
<= patricia
->maxbits
);
321 /* if new trie, create the first node */
322 if (patricia
->head
== NULL
) {
323 node
= patricia_new_node(patricia
, prefix
->bitlen
, patricia_ref_prefix (prefix
));
324 patricia
->head
= node
;
328 addr
= prefix_touchar (prefix
);
329 bitlen
= prefix
->bitlen
;
330 node
= patricia
->head
;
332 /* while ( bitlength of tree node < bitlength of node we're searching for || the node has no prefix */
333 while (node
->bit
< bitlen
|| node
->prefix
== NULL
) {
334 /* check that we're not at the lowest leaf i.e. node->bit is less than max bits */
335 if (node
->bit
< patricia
->maxbits
&&
336 (is_bit_set(addr
,node
->bit
))) {
350 assert (node
->prefix
);
352 test_addr
= prefix_touchar (node
->prefix
);
353 /* find the first bit different */
354 check_bit
= (node
->bit
< bitlen
)? node
->bit
: bitlen
;
356 for (i
= 0; i
*8 < check_bit
; i
++) {
357 if ((r
= (addr
[i
] ^ test_addr
[i
])) == 0) {
358 differ_bit
= (i
+ 1) * 8;
361 /* I know the better way, but for now */
362 for (j
= 0; j
< 8; j
++) {
363 if ((r
) & ((0x80 >> j
)))
368 differ_bit
= i
* 8 + j
;
371 if (differ_bit
> check_bit
)
372 differ_bit
= check_bit
;
375 parent
= node
->parent
;
376 while (parent
&& parent
->bit
>= differ_bit
) {
378 parent
= node
->parent
;
381 if (differ_bit
== bitlen
&& node
->bit
== bitlen
) {
383 node
->prefix
= patricia_ref_prefix (prefix
);
388 new_node
= patricia_new_node(patricia
, prefix
->bitlen
, patricia_ref_prefix (prefix
));
389 if (node
->bit
== differ_bit
) {
390 new_node
->parent
= node
;
391 if (node
->bit
< patricia
->maxbits
&&
392 (is_bit_set(addr
, node
->bit
))) {
393 assert (node
->r
== NULL
);
397 assert (node
->l
== NULL
);
403 if (bitlen
== differ_bit
) {
404 if (bitlen
< patricia
->maxbits
&&
405 (is_bit_set(test_addr
,bitlen
))) {
411 new_node
->parent
= node
->parent
;
412 if (node
->parent
== NULL
) {
413 assert (patricia
->head
== node
);
414 patricia
->head
= new_node
;
416 else if (node
->parent
->r
== node
) {
417 node
->parent
->r
= new_node
;
420 node
->parent
->l
= new_node
;
422 node
->parent
= new_node
;
423 new_node
->usercount
= node
->usercount
;
426 glue
= patricia_new_node(patricia
, differ_bit
, NULL
);
427 glue
->parent
= node
->parent
;
428 if (differ_bit
< patricia
->maxbits
&&
429 (is_bit_set(addr
, differ_bit
))) {
437 new_node
->parent
= glue
;
439 if (node
->parent
== NULL
) {
440 assert (patricia
->head
== node
);
441 patricia
->head
= glue
;
443 else if (node
->parent
->r
== node
) {
444 node
->parent
->r
= glue
;
447 node
->parent
->l
= glue
;
450 glue
->usercount
= node
->usercount
;
457 patricia_remove (patricia_tree_t
*patricia
, patricia_node_t
*node
)
459 patricia_node_t
*parent
, *child
;
464 if (node
->r
&& node
->l
) {
465 /* this might be a placeholder node -- have to check and make sure
466 * there is a prefix aossciated with it ! */
467 if (node
->prefix
!= NULL
)
468 patricia_deref_prefix (node
->prefix
);
473 if (node
->r
== NULL
&& node
->l
== NULL
) {
474 parent
= node
->parent
;
475 patricia_deref_prefix (node
->prefix
);
477 patricia
->num_active_node
--;
479 if (parent
== NULL
) {
480 assert (patricia
->head
== node
);
481 patricia
->head
= NULL
;
485 if (parent
->r
== node
) {
490 assert (parent
->l
== node
);
498 /* we need to remove parent too */
500 if (parent
->parent
== NULL
) {
501 assert (patricia
->head
== parent
);
502 patricia
->head
= child
;
504 else if (parent
->parent
->r
== parent
) {
505 parent
->parent
->r
= child
;
508 assert (parent
->parent
->l
== parent
);
509 parent
->parent
->l
= child
;
511 child
->parent
= parent
->parent
;
513 patricia
->num_active_node
--;
524 parent
= node
->parent
;
525 child
->parent
= parent
;
527 patricia_deref_prefix (node
->prefix
);
529 patricia
->num_active_node
--;
531 if (parent
== NULL
) {
532 assert (patricia
->head
== node
);
533 patricia
->head
= child
;
537 if (parent
->r
== node
) {
541 assert (parent
->l
== node
);
546 #ifdef LEAK_DETECTION
547 static patricia_node_t
*getrealnode(patricia_node_t
*node
) {
548 struct fake_node
*f
= (struct fake_node
*)node
;
549 if(f
->magic
!= MAGIC
) {
550 printf("magic failure\n");
558 refnode(patricia_tree_t
*tree
, struct irc_in_addr
*sin
, int bitlen
) {
559 patricia_node_t
*node
;
562 node
= patricia_search_exact(tree
, sin
, bitlen
);
565 prefix
= patricia_new_prefix(sin
, bitlen
);
566 node
= patricia_lookup(tree
, prefix
);
567 patricia_deref_prefix(prefix
);
568 } else if (node
->prefix
) {
569 patricia_ref_prefix(node
->prefix
);
572 #ifdef LEAK_DETECTION
573 struct fake_node
*f
= malloc(sizeof(struct fake_node
));
577 node
= (patricia_node_t
*)f
;
584 derefnode(patricia_tree_t
*tree
, patricia_node_t
*node
) {
585 if (!node
|| !node
->prefix
)
588 #ifdef LEAK_DETECTION
589 patricia_node_t
*real_node
= getrealnode(node
);
593 if (!node
|| !node
->prefix
)
597 if (node
->prefix
->ref_count
== 1) {
598 patricia_remove(tree
, node
);
600 patricia_deref_prefix(node
->prefix
);
603 patricia_node_t
*patricia_new_node(patricia_tree_t
*patricia
, unsigned char bit
,prefix_t
*prefix
) {
604 patricia_node_t
*new_node
= newnode();
605 memset(new_node
->exts
, 0, PATRICIA_MAXSLOTS
* sizeof(void *));
607 new_node
->prefix
= prefix
;
608 new_node
->usercount
= 0;
609 new_node
->parent
= NULL
;
610 new_node
->l
= new_node
->r
= NULL
;
611 patricia
->num_active_node
++;
615 void node_increment_usercount( patricia_node_t
*node
) {
616 #ifdef LEAK_DETECTION
617 node
= getrealnode(node
);
626 void node_decrement_usercount( patricia_node_t
*node
) {
627 #ifdef LEAK_DETECTION
628 node
= getrealnode(node
);
637 int is_normalized_ipmask( struct irc_in_addr
*sin
, unsigned char bitlen
) {
638 u_char
*addr
= (u_char
*)sin
;
640 while (bitlen
< PATRICIA_MAXBITS
) {
641 if (is_bit_set(addr
,bitlen
))