]>
jfr.im git - irc/quakenet/newserv.git/blob - lib/patricia.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 */
33 * convert prefix information to bytes
36 prefix_tochar (prefix_t
* prefix
)
41 return ((u_char
*) & prefix
->sin
);
45 comp_with_mask (void *addr
, void *dest
, u_int mask
)
48 if ( /* mask/8 == 0 || */ memcmp (addr
, dest
, mask
/ 8) == 0) {
50 int m
= ((-1) << (8 - (mask
% 8)));
52 if (mask
% 8 == 0 || (((u_char
*)addr
)[n
] & m
) == (((u_char
*)dest
)[n
] & m
))
59 patricia_new_prefix (struct irc_in_addr
*dest
, int bitlen
)
61 prefix_t
*prefix
= NULL
;
63 prefix
= malloc(sizeof (prefix_t
));
64 memcpy (&prefix
->sin
, dest
, 16);
66 prefix
->bitlen
= (bitlen
>= 0)? bitlen
: 128;
67 prefix
->ref_count
= 1;
72 patricia_ref_prefix (prefix_t
* prefix
)
76 if (prefix
->ref_count
== 0) {
77 /* make a copy in case of a static prefix */
78 return (patricia_new_prefix (&prefix
->sin
, prefix
->bitlen
));
81 /* fprintf(stderr, "[A %s, %d]\n", prefix_toa (prefix), prefix->ref_count); */
86 patricia_deref_prefix (prefix_t
* prefix
)
90 /* for secure programming, raise an assert. no static prefix can call this */
91 assert (prefix
->ref_count
> 0);
94 assert (prefix
->ref_count
>= 0);
95 if (prefix
->ref_count
<= 0) {
103 /* #define PATRICIA_DEBUG 1 */
105 /* these routines support continuous mask only */
108 patricia_new_tree (int maxbits
)
110 patricia_tree_t
*patricia
= calloc(1, sizeof *patricia
);
112 patricia
->maxbits
= maxbits
;
113 patricia
->head
= NULL
;
114 patricia
->num_active_node
= 0;
115 assert (maxbits
<= PATRICIA_MAXBITS
); /* XXX */
121 patricia_clear_tree (patricia_tree_t
*patricia
, void_fn_t func
)
124 if (patricia
->head
) {
126 patricia_node_t
*Xstack
[PATRICIA_MAXBITS
+1];
127 patricia_node_t
**Xsp
= Xstack
;
128 patricia_node_t
*Xrn
= patricia
->head
;
131 patricia_node_t
*l
= Xrn
->l
;
132 patricia_node_t
*r
= Xrn
->r
;
135 if (Xrn
->exts
&& func
)
137 patricia_deref_prefix (Xrn
->prefix
);
140 patricia
->num_active_node
--;
149 } else if (Xsp
!= Xstack
) {
152 Xrn
= (patricia_node_t
*) 0;
156 assert (patricia
->num_active_node
== 0);
157 /* free(patricia); */
162 patricia_destroy_tree (patricia_tree_t
*patricia
, void_fn_t func
)
164 patricia_clear_tree (patricia
, func
);
170 * if func is supplied, it will be called as func(node->prefix)
174 patricia_process (patricia_tree_t
*patricia
, void_fn_t func
)
176 patricia_node_t
*node
;
179 PATRICIA_WALK (patricia
->head
, node
) {
185 patricia_walk_inorder(patricia_node_t
*node
, void_fn_t func
)
191 n
+= patricia_walk_inorder(node
->l
, func
);
200 n
+= patricia_walk_inorder(node
->r
, func
);
208 patricia_search_exact (patricia_tree_t
*patricia
, struct irc_in_addr
*sin
, unsigned char bitlen
)
210 patricia_node_t
*node
;
215 assert (bitlen
<= patricia
->maxbits
);
217 if (patricia
->head
== NULL
)
220 node
= patricia
->head
;
221 addr
= (u_char
*)sin
;
223 while (node
->bit
< bitlen
) {
224 if (BIT_TEST (addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07)))
233 if (node
->bit
> bitlen
|| node
->prefix
== NULL
)
235 assert (node
->bit
== bitlen
);
236 assert (node
->bit
== node
->prefix
->bitlen
);
237 if (comp_with_mask (prefix_tochar (node
->prefix
), addr
, bitlen
)) {
244 /* if inclusive != 0, "best" may be the given prefix itself */
246 patricia_search_best2 (patricia_tree_t
*patricia
, struct irc_in_addr
*sin
, unsigned char bitlen
, int inclusive
)
248 patricia_node_t
*node
;
249 patricia_node_t
*stack
[PATRICIA_MAXBITS
+ 1];
255 assert (bitlen
<= patricia
->maxbits
);
257 if (patricia
->head
== NULL
)
260 node
= patricia
->head
;
261 addr
= (u_char
*)sin
;
263 while (node
->bit
< bitlen
) {
269 if (BIT_TEST (addr
[node
->bit
>> 3], 0x80 >> (node
->bit
& 0x07))) {
280 if (inclusive
&& node
&& node
->prefix
)
288 if (comp_with_mask (prefix_tochar (node
->prefix
),
290 node
->prefix
->bitlen
)) {
299 patricia_search_best (patricia_tree_t
*patricia
, struct irc_in_addr
*sin
, unsigned char bitlen
)
301 return (patricia_search_best2 (patricia
, sin
, bitlen
, 1));
306 patricia_lookup (patricia_tree_t
*patricia
, prefix_t
*prefix
)
308 patricia_node_t
*node
, *new_node
, *parent
, *glue
;
309 u_char
*addr
, *test_addr
;
310 u_int bitlen
, check_bit
, differ_bit
;
315 assert (prefix
->bitlen
<= patricia
->maxbits
);
317 /* if new trie, create the first node */
318 if (patricia
->head
== NULL
) {
319 node
= malloc(sizeof *node
);
320 memset(node
->exts
, 0, PATRICIA_MAXSLOTS
* sizeof(void *));
321 node
->bit
= prefix
->bitlen
;
322 node
->prefix
= patricia_ref_prefix (prefix
);
324 node
->l
= node
->r
= NULL
;
326 patricia
->head
= node
;
327 patricia
->num_active_node
++;
331 addr
= prefix_touchar (prefix
);
332 bitlen
= prefix
->bitlen
;
333 node
= patricia
->head
;
335 /* while ( bitlength of tree node < bitlength of node we're searching for || the node has no prefix */
336 while (node
->bit
< bitlen
|| node
->prefix
== NULL
) {
337 /* check that we're not at the lowest leaf i.e. node->bit is less than max bits */
338 if (node
->bit
< patricia
->maxbits
&&
339 (addr
[node
->bit
>> 3]) & (0x80 >> (node
->bit
& 0x07))) {
353 assert (node
->prefix
);
355 test_addr
= prefix_touchar (node
->prefix
);
356 /* find the first bit different */
357 check_bit
= (node
->bit
< bitlen
)? node
->bit
: bitlen
;
359 for (i
= 0; i
*8 < check_bit
; i
++) {
360 if ((r
= (addr
[i
] ^ test_addr
[i
])) == 0) {
361 differ_bit
= (i
+ 1) * 8;
364 /* I know the better way, but for now */
365 for (j
= 0; j
< 8; j
++) {
366 if ((r
) & ((0x80 >> j
)))
371 differ_bit
= i
* 8 + j
;
374 if (differ_bit
> check_bit
)
375 differ_bit
= check_bit
;
378 parent
= node
->parent
;
379 while (parent
&& parent
->bit
>= differ_bit
) {
381 parent
= node
->parent
;
384 if (differ_bit
== bitlen
&& node
->bit
== bitlen
) {
388 node
->prefix
= patricia_ref_prefix (prefix
);
392 new_node
= malloc(sizeof *new_node
);
393 memset(new_node
->exts
, 0, PATRICIA_MAXSLOTS
* sizeof(void *));
394 new_node
->bit
= prefix
->bitlen
;
395 new_node
->prefix
= patricia_ref_prefix (prefix
);
396 new_node
->parent
= NULL
;
397 new_node
->l
= new_node
->r
= NULL
;
398 new_node
->usercount
= 0;
399 patricia
->num_active_node
++;
401 if (node
->bit
== differ_bit
) {
402 new_node
->parent
= node
;
403 if (node
->bit
< patricia
->maxbits
&&
404 (addr
[node
->bit
>> 3]) & (0x80 >> (node
->bit
& 0x07))) {
405 assert (node
->r
== NULL
);
409 assert (node
->l
== NULL
);
415 if (bitlen
== differ_bit
) {
416 if (bitlen
< patricia
->maxbits
&&
417 (test_addr
[bitlen
>> 3]) & (0x80 >> (bitlen
& 0x07))) {
423 new_node
->parent
= node
->parent
;
424 if (node
->parent
== NULL
) {
425 assert (patricia
->head
== node
);
426 patricia
->head
= new_node
;
428 else if (node
->parent
->r
== node
) {
429 node
->parent
->r
= new_node
;
432 node
->parent
->l
= new_node
;
434 node
->parent
= new_node
;
437 glue
= malloc(sizeof *glue
);
438 memset(glue
->exts
, 0, PATRICIA_MAXSLOTS
* sizeof(void *));
439 glue
->bit
= differ_bit
;
441 glue
->parent
= node
->parent
;
443 patricia
->num_active_node
++;
444 if (differ_bit
< patricia
->maxbits
&&
445 (addr
[differ_bit
>> 3]) & (0x80 >> (differ_bit
& 0x07))) {
453 new_node
->parent
= glue
;
455 if (node
->parent
== NULL
) {
456 assert (patricia
->head
== node
);
457 patricia
->head
= glue
;
459 else if (node
->parent
->r
== node
) {
460 node
->parent
->r
= glue
;
463 node
->parent
->l
= glue
;
471 patricia_remove (patricia_tree_t
*patricia
, patricia_node_t
*node
)
473 patricia_node_t
*parent
, *child
;
478 if (node
->r
&& node
->l
) {
479 /* this might be a placeholder node -- have to check and make sure
480 * there is a prefix aossciated with it ! */
481 if (node
->prefix
!= NULL
)
482 patricia_deref_prefix (node
->prefix
);
487 if (node
->r
== NULL
&& node
->l
== NULL
) {
488 parent
= node
->parent
;
489 patricia_deref_prefix (node
->prefix
);
491 patricia
->num_active_node
--;
493 if (parent
== NULL
) {
494 assert (patricia
->head
== node
);
495 patricia
->head
= NULL
;
499 if (parent
->r
== node
) {
504 assert (parent
->l
== node
);
512 /* we need to remove parent too */
514 if (parent
->parent
== NULL
) {
515 assert (patricia
->head
== parent
);
516 patricia
->head
= child
;
518 else if (parent
->parent
->r
== parent
) {
519 parent
->parent
->r
= child
;
522 assert (parent
->parent
->l
== parent
);
523 parent
->parent
->l
= child
;
525 child
->parent
= parent
->parent
;
527 patricia
->num_active_node
--;
538 parent
= node
->parent
;
539 child
->parent
= parent
;
541 patricia_deref_prefix (node
->prefix
);
543 patricia
->num_active_node
--;
545 if (parent
== NULL
) {
546 assert (patricia
->head
== node
);
547 patricia
->head
= child
;
551 if (parent
->r
== node
) {
555 assert (parent
->l
== node
);
563 refnode(patricia_tree_t
*tree
, struct irc_in_addr
*sin
, int bitlen
) {
564 patricia_node_t
*node
;
567 node
= patricia_search_exact(tree
, sin
, bitlen
);
570 prefix
= patricia_new_prefix(sin
, bitlen
);
571 node
= patricia_lookup(tree
, prefix
);
572 patricia_deref_prefix(prefix
);
573 } else if (node
->prefix
) {
574 patricia_ref_prefix(node
->prefix
);
581 derefnode(patricia_tree_t
*tree
, patricia_node_t
*node
) {
582 if (!node
|| !node
->prefix
)
585 if (node
->prefix
->ref_count
== 1) {
586 patricia_remove(tree
, node
);
588 patricia_deref_prefix(node
->prefix
);