]>
Commit | Line | Data |
---|---|---|
db137867 AC |
1 | /* |
2 | * Yanked out of Net::Patricia by Aaron Sethman <androsyn@ratbox.org> | |
3 | * | |
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. | |
6 | * | |
7 | * $Id: patricia.c 24244 2007-08-22 19:04:55Z androsyn $ | |
8 | * Dave Plonka <plonka@doit.wisc.edu> | |
9 | * | |
10 | * This product includes software developed by the University of Michigan, | |
11 | * Merit Network, Inc., and their contributors. | |
12 | * | |
13 | * This file had been called "radix.c" in the MRT sources. | |
14 | * | |
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. | |
18 | * | |
19 | * This product includes software developed by the University of Michigan, Merit | |
20 | * Network, Inc., and their contributors. | |
21 | * | |
22 | */ | |
23 | #include <libratbox_config.h> | |
24 | #include <ratbox_lib.h> | |
25 | ||
26 | /* Enable both of these to debug patricia.c | |
27 | * #define NOTYET 1 | |
28 | * #define PATRICIA_DEBUG 1 | |
29 | */ | |
30 | ||
31 | #define PREFIX_HEAP_COUNT 1024 | |
32 | #define NODE_HEAP_COUNT 1024 | |
33 | #define PATRICIA_HEAP_COUNT 128 | |
34 | ||
35 | void | |
36 | rb_init_patricia(void) | |
37 | { | |
38 | return; | |
39 | } | |
40 | ||
41 | /* prefix_tochar | |
42 | * convert prefix information to bytes | |
43 | */ | |
44 | static uint8_t * | |
45 | prefix_tochar(rb_prefix_t * prefix) | |
46 | { | |
47 | if(prefix == NULL) | |
48 | return (NULL); | |
49 | ||
50 | return ((uint8_t *) & prefix->add.sin); | |
51 | } | |
52 | ||
53 | static int | |
54 | comp_with_mask(void *addr, void *dest, unsigned int mask) | |
55 | { | |
56 | ||
57 | if( /* mask/8 == 0 || */ memcmp(addr, dest, mask / 8) == 0) | |
58 | { | |
59 | int n = mask / 8; | |
60 | int m = ((-1) << (8 - (mask % 8))); | |
61 | ||
62 | if(mask % 8 == 0 || (((uint8_t *) addr)[n] & m) == (((uint8_t *) dest)[n] & m)) | |
63 | return (1); | |
64 | } | |
65 | return (0); | |
66 | } | |
67 | #ifdef NOTYET | |
68 | static char * | |
69 | prefix_toa2x(rb_prefix_t * prefix, char *buf, int buf_len, int with_len) | |
70 | { | |
71 | static char tmp[6]; | |
72 | if(prefix == NULL) | |
73 | { | |
74 | strcpy(buf, "(NULL)"); | |
75 | return (buf); | |
76 | } | |
77 | inet_ntop(prefix->family, &prefix->add.sin, buf, buf_len); | |
78 | if(with_len) | |
79 | { | |
80 | rb_snprintf(tmp, sizeof(tmp), "/%d", prefix->bitlen); | |
81 | strcat(buf, tmp); | |
82 | } | |
83 | return (buf); | |
84 | } | |
85 | ||
86 | /* prefix_toa2 | |
87 | * convert prefix information to ascii string | |
88 | */ | |
89 | ||
90 | static char * | |
91 | prefix_toa2(rb_prefix_t * prefix, char *buff, int buf_len) | |
92 | { | |
93 | return (prefix_toa2x(prefix, buff, buf_len, 0)); | |
94 | } | |
95 | static char * | |
96 | prefix_toa(rb_prefix_t * prefix) | |
97 | { | |
98 | #ifdef RB_IPV6 | |
99 | static char buf[INET6_ADDRSTRLEN + 6]; | |
100 | #else | |
101 | static char buf[16 + 6]; | |
102 | #endif | |
103 | return (prefix_toa2(prefix, buf, sizeof(buf))); | |
104 | } | |
105 | #endif | |
106 | static rb_prefix_t * | |
107 | New_Prefix2(int family, void *dest, int bitlen, rb_prefix_t * prefix) | |
108 | { | |
109 | int dynamic_allocated = 0; | |
110 | #ifdef RB_IPV6 | |
111 | int default_bitlen = 128; | |
112 | #else | |
113 | int default_bitlen = 32; | |
114 | #endif | |
115 | ||
116 | #ifdef RB_IPV6 | |
117 | if(family == AF_INET6) | |
118 | { | |
119 | default_bitlen = 128; | |
120 | if(prefix == NULL) | |
121 | { | |
122 | prefix = rb_malloc(sizeof(rb_prefix_t)); | |
123 | dynamic_allocated++; | |
124 | } | |
125 | memcpy(&prefix->add.sin6, dest, 16); | |
126 | } | |
127 | else | |
128 | #endif /* RB_IPV6 */ | |
129 | if(family == AF_INET) | |
130 | { | |
131 | if(prefix == NULL) | |
132 | { | |
133 | prefix = rb_malloc(sizeof(rb_prefix_t)); | |
134 | dynamic_allocated++; | |
135 | } | |
136 | memcpy(&prefix->add.sin, dest, 4); | |
137 | } | |
138 | else | |
139 | { | |
140 | return (NULL); | |
141 | } | |
142 | ||
143 | prefix->bitlen = (bitlen >= 0) ? bitlen : default_bitlen; | |
144 | prefix->family = family; | |
145 | prefix->ref_count = 0; | |
146 | if(dynamic_allocated) | |
147 | { | |
148 | prefix->ref_count++; | |
149 | } | |
150 | return (prefix); | |
151 | } | |
152 | ||
153 | static rb_prefix_t * | |
154 | New_Prefix(int family, void *dest, int bitlen) | |
155 | { | |
156 | return (New_Prefix2(family, dest, bitlen, NULL)); | |
157 | } | |
158 | ||
159 | /* ascii2prefix | |
160 | */ | |
161 | static rb_prefix_t * | |
162 | ascii2prefix(int family, const char *string) | |
163 | { | |
164 | long bitlen, maxbitlen = 0; | |
165 | char *cp; | |
166 | struct in_addr sinaddr; | |
167 | #ifdef RB_IPV6 | |
168 | struct in6_addr sinaddr6; | |
169 | #endif /* RB_IPV6 */ | |
170 | int result; | |
171 | char save[MAXLINE]; | |
172 | ||
173 | if(string == NULL) | |
174 | return (NULL); | |
175 | ||
176 | /* easy way to handle both families */ | |
177 | if(family == 0) | |
178 | { | |
179 | family = AF_INET; | |
180 | #ifdef RB_IPV6 | |
181 | if(strchr(string, ':')) | |
182 | family = AF_INET6; | |
183 | #endif /* RB_IPV6 */ | |
184 | } | |
185 | if(family == AF_INET) | |
186 | { | |
187 | maxbitlen = 32; | |
188 | } | |
189 | #ifdef RB_IPV6 | |
190 | else if(family == AF_INET6) | |
191 | { | |
192 | maxbitlen = 128; | |
193 | } | |
194 | #endif /* RB_IPV6 */ | |
195 | ||
196 | if((cp = strchr(string, '/')) != NULL) | |
197 | { | |
198 | bitlen = atol(cp + 1); | |
199 | /* *cp = '\0'; */ | |
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'; | |
204 | string = save; | |
205 | if(bitlen <= 0 || bitlen > maxbitlen) | |
206 | bitlen = maxbitlen; | |
207 | } | |
208 | else | |
209 | { | |
210 | bitlen = maxbitlen; | |
211 | } | |
212 | ||
213 | if(family == AF_INET) | |
214 | { | |
215 | if((result = rb_inet_pton(AF_INET, string, &sinaddr)) <= 0) | |
216 | return (NULL); | |
217 | return (New_Prefix(AF_INET, &sinaddr, bitlen)); | |
218 | } | |
219 | #ifdef RB_IPV6 | |
220 | else if(family == AF_INET6) | |
221 | { | |
222 | if((result = rb_inet_pton(AF_INET6, string, &sinaddr6)) <= 0) | |
223 | return (NULL); | |
224 | return (New_Prefix(AF_INET6, &sinaddr6, bitlen)); | |
225 | } | |
226 | #endif /* RB_IPV6 */ | |
227 | else | |
228 | return (NULL); | |
229 | } | |
230 | ||
231 | static rb_prefix_t * | |
232 | Ref_Prefix(rb_prefix_t * prefix) | |
233 | { | |
234 | if(prefix == NULL) | |
235 | return (NULL); | |
236 | if(prefix->ref_count == 0) | |
237 | { | |
238 | /* make a copy in case of a static prefix */ | |
239 | return (New_Prefix2(prefix->family, &prefix->add, prefix->bitlen, NULL)); | |
240 | } | |
241 | prefix->ref_count++; | |
242 | return (prefix); | |
243 | } | |
244 | ||
245 | static void | |
246 | Deref_Prefix(rb_prefix_t * prefix) | |
247 | { | |
248 | if(prefix == NULL) | |
249 | return; | |
250 | /* for secure programming, raise an assert. no static prefix can call this */ | |
251 | assert(prefix->ref_count > 0); | |
252 | ||
253 | prefix->ref_count--; | |
254 | assert(prefix->ref_count >= 0); | |
255 | if(prefix->ref_count <= 0) | |
256 | { | |
257 | rb_free(prefix); | |
258 | return; | |
259 | } | |
260 | } | |
261 | ||
262 | /* } */ | |
263 | ||
264 | // #define PATRICIA_DEBUG 1 | |
265 | ||
266 | static int num_active_patricia = 0; | |
267 | ||
268 | /* these routines support continuous mask only */ | |
269 | ||
270 | rb_patricia_tree_t * | |
271 | rb_new_patricia(int maxbits) | |
272 | { | |
273 | rb_patricia_tree_t *patricia = rb_malloc(sizeof(rb_patricia_tree_t)); | |
274 | ||
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++; | |
280 | return (patricia); | |
281 | } | |
282 | ||
283 | ||
284 | /* | |
285 | * if func is supplied, it will be called as func(node->data) | |
286 | * before deleting the node | |
287 | */ | |
288 | ||
289 | void | |
365d91a8 | 290 | rb_clear_patricia(rb_patricia_tree_t * patricia, void (*func)(void *)) |
db137867 AC |
291 | { |
292 | assert(patricia); | |
293 | if(patricia->head) | |
294 | { | |
295 | ||
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; | |
299 | ||
300 | while (Xrn) | |
301 | { | |
302 | rb_patricia_node_t *l = Xrn->l; | |
303 | rb_patricia_node_t *r = Xrn->r; | |
304 | ||
305 | if(Xrn->prefix) | |
306 | { | |
307 | Deref_Prefix(Xrn->prefix); | |
308 | if(Xrn->data && func) | |
309 | func(Xrn->data); | |
310 | } | |
311 | else | |
312 | { | |
313 | assert(Xrn->data == NULL); | |
314 | } | |
315 | rb_free(Xrn); | |
316 | patricia->num_active_node--; | |
317 | ||
318 | if(l) | |
319 | { | |
320 | if(r) | |
321 | { | |
322 | *Xsp++ = r; | |
323 | } | |
324 | Xrn = l; | |
325 | } | |
326 | else if(r) | |
327 | { | |
328 | Xrn = r; | |
329 | } | |
330 | else if(Xsp != Xstack) | |
331 | { | |
332 | Xrn = *(--Xsp); | |
333 | } | |
334 | else | |
335 | { | |
336 | Xrn = (rb_patricia_node_t *) 0; | |
337 | } | |
338 | } | |
339 | } | |
340 | assert(patricia->num_active_node == 0); | |
341 | rb_free(patricia); | |
342 | } | |
343 | ||
344 | ||
345 | void | |
365d91a8 | 346 | rb_destroy_patricia(rb_patricia_tree_t * patricia, void (*func)(void *)) |
db137867 AC |
347 | { |
348 | rb_clear_patricia(patricia, func); | |
349 | num_active_patricia--; | |
350 | } | |
351 | ||
352 | ||
353 | /* | |
354 | * if func is supplied, it will be called as func(node->prefix, node->data) | |
355 | */ | |
356 | ||
357 | void | |
365d91a8 | 358 | rb_patricia_process(rb_patricia_tree_t * patricia, void (*func)(rb_prefix_t *, void *)) |
db137867 AC |
359 | { |
360 | rb_patricia_node_t *node; | |
361 | assert(func); | |
362 | ||
363 | RB_PATRICIA_WALK(patricia->head, node) | |
364 | { | |
365 | func(node->prefix, node->data); | |
366 | } | |
367 | RB_PATRICIA_WALK_END; | |
368 | } | |
369 | ||
370 | rb_patricia_node_t * | |
371 | rb_patricia_search_exact(rb_patricia_tree_t * patricia, rb_prefix_t * prefix) | |
372 | { | |
373 | rb_patricia_node_t *node; | |
374 | uint8_t *addr; | |
375 | unsigned int bitlen; | |
376 | ||
377 | assert(patricia); | |
378 | assert(prefix); | |
379 | assert(prefix->bitlen <= patricia->maxbits); | |
380 | ||
381 | if(patricia->head == NULL) | |
382 | return (NULL); | |
383 | ||
384 | node = patricia->head; | |
385 | addr = rb_prefix_touchar(prefix); | |
386 | bitlen = prefix->bitlen; | |
387 | ||
388 | while (node->bit < bitlen) | |
389 | { | |
390 | ||
391 | if(BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) | |
392 | { | |
393 | #ifdef PATRICIA_DEBUG | |
394 | if(node->prefix) | |
395 | fprintf(stderr, | |
396 | "patricia_search_exact: take right %s/%d\n", | |
397 | prefix_toa(node->prefix), node->prefix->bitlen); | |
398 | else | |
399 | fprintf(stderr, | |
400 | "patricia_search_exact: take right at %d\n", node->bit); | |
401 | #endif /* PATRICIA_DEBUG */ | |
402 | node = node->r; | |
403 | } | |
404 | else | |
405 | { | |
406 | #ifdef PATRICIA_DEBUG | |
407 | if(node->prefix) | |
408 | fprintf(stderr, | |
409 | "patricia_search_exact: take left %s/%d\n", | |
410 | prefix_toa(node->prefix), node->prefix->bitlen); | |
411 | else | |
412 | fprintf(stderr, | |
413 | "patricia_search_exact: take left at %d\n", node->bit); | |
414 | #endif /* PATRICIA_DEBUG */ | |
415 | node = node->l; | |
416 | } | |
417 | ||
418 | if(node == NULL) | |
419 | return (NULL); | |
420 | } | |
421 | ||
422 | #ifdef PATRICIA_DEBUG | |
423 | if(node->prefix) | |
424 | fprintf(stderr, "patricia_search_exact: stop at %s/%d %d\n", | |
425 | prefix_toa(node->prefix), node->prefix->bitlen, node->bit); | |
426 | else | |
427 | fprintf(stderr, "patricia_search_exact: stop at %d\n", node->bit); | |
428 | #endif /* PATRICIA_DEBUG */ | |
429 | if(node->bit > bitlen || node->prefix == NULL) | |
430 | return (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)) | |
434 | { | |
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 */ | |
439 | return (node); | |
440 | } | |
441 | return (NULL); | |
442 | } | |
443 | ||
444 | /* if inclusive != 0, "best" may be the given prefix itself */ | |
445 | rb_patricia_node_t * | |
446 | rb_patricia_search_best2(rb_patricia_tree_t * patricia, rb_prefix_t * prefix, int inclusive) | |
447 | { | |
448 | rb_patricia_node_t *node; | |
449 | rb_patricia_node_t *stack[RB_PATRICIA_MAXBITS + 1]; | |
450 | uint8_t *addr; | |
451 | unsigned int bitlen; | |
452 | int cnt = 0; | |
453 | ||
454 | assert(patricia); | |
455 | assert(prefix); | |
456 | assert(prefix->bitlen <= patricia->maxbits); | |
457 | ||
458 | if(patricia->head == NULL) | |
459 | return (NULL); | |
460 | ||
461 | node = patricia->head; | |
462 | addr = rb_prefix_touchar(prefix); | |
463 | bitlen = prefix->bitlen; | |
464 | ||
465 | while (node->bit < bitlen) | |
466 | { | |
467 | ||
468 | if(node->prefix) | |
469 | { | |
470 | #ifdef PATRICIA_DEBUG | |
471 | fprintf(stderr, | |
472 | "patricia_search_best: push %s/%d\n", | |
473 | prefix_toa(node->prefix), node->prefix->bitlen); | |
474 | #endif /* PATRICIA_DEBUG */ | |
475 | stack[cnt++] = node; | |
476 | } | |
477 | ||
478 | if(BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) | |
479 | { | |
480 | #ifdef PATRICIA_DEBUG | |
481 | if(node->prefix) | |
482 | fprintf(stderr, | |
483 | "patricia_search_best: take right %s/%d\n", | |
484 | prefix_toa(node->prefix), node->prefix->bitlen); | |
485 | else | |
486 | fprintf(stderr, | |
487 | "patricia_search_best: take right at %d\n", node->bit); | |
488 | #endif /* PATRICIA_DEBUG */ | |
489 | node = node->r; | |
490 | } | |
491 | else | |
492 | { | |
493 | #ifdef PATRICIA_DEBUG | |
494 | if(node->prefix) | |
495 | fprintf(stderr, | |
496 | "patricia_search_best: take left %s/%d\n", | |
497 | prefix_toa(node->prefix), node->prefix->bitlen); | |
498 | else | |
499 | fprintf(stderr, | |
500 | "patricia_search_best: take left at %d\n", node->bit); | |
501 | #endif /* PATRICIA_DEBUG */ | |
502 | node = node->l; | |
503 | } | |
504 | ||
505 | if(node == NULL) | |
506 | break; | |
507 | } | |
508 | ||
509 | if(inclusive && node && node->prefix) | |
510 | stack[cnt++] = node; | |
511 | ||
512 | #ifdef PATRICIA_DEBUG | |
513 | if(node == NULL) | |
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); | |
518 | else | |
519 | fprintf(stderr, "patricia_search_best: stop at %d\n", node->bit); | |
520 | #endif /* PATRICIA_DEBUG */ | |
521 | ||
522 | if(cnt <= 0) | |
523 | return (NULL); | |
524 | ||
525 | while (--cnt >= 0) | |
526 | { | |
527 | node = stack[cnt]; | |
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)) | |
534 | { | |
535 | #ifdef PATRICIA_DEBUG | |
536 | fprintf(stderr, | |
537 | "patricia_search_best: found %s/%d\n", | |
538 | prefix_toa(node->prefix), node->prefix->bitlen); | |
539 | #endif /* PATRICIA_DEBUG */ | |
540 | return (node); | |
541 | } | |
542 | } | |
543 | return (NULL); | |
544 | } | |
545 | ||
546 | ||
547 | rb_patricia_node_t * | |
548 | rb_patricia_search_best(rb_patricia_tree_t * patricia, rb_prefix_t * prefix) | |
549 | { | |
550 | return (rb_patricia_search_best2(patricia, prefix, 1)); | |
551 | } | |
552 | ||
553 | ||
554 | rb_patricia_node_t * | |
555 | rb_patricia_lookup(rb_patricia_tree_t * patricia, rb_prefix_t * prefix) | |
556 | { | |
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; | |
561 | ||
562 | assert(patricia); | |
563 | assert(prefix); | |
564 | assert(prefix->bitlen <= patricia->maxbits); | |
565 | ||
566 | if(patricia->head == NULL) | |
567 | { | |
568 | node = rb_malloc(sizeof(rb_patricia_node_t)); | |
569 | node->bit = prefix->bitlen; | |
570 | node->prefix = Ref_Prefix(prefix); | |
571 | node->parent = NULL; | |
572 | node->l = node->r = NULL; | |
573 | node->data = NULL; | |
574 | patricia->head = node; | |
575 | #ifdef PATRICIA_DEBUG | |
576 | fprintf(stderr, | |
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++; | |
581 | return (node); | |
582 | } | |
583 | ||
584 | addr = rb_prefix_touchar(prefix); | |
585 | bitlen = prefix->bitlen; | |
586 | node = patricia->head; | |
587 | ||
588 | while (node->bit < bitlen || node->prefix == NULL) | |
589 | { | |
590 | ||
591 | if(node->bit < patricia->maxbits && | |
592 | BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) | |
593 | { | |
594 | if(node->r == NULL) | |
595 | break; | |
596 | #ifdef PATRICIA_DEBUG | |
597 | if(node->prefix) | |
598 | fprintf(stderr, | |
599 | "patricia_lookup: take right %s/%d\n", | |
600 | prefix_toa(node->prefix), node->prefix->bitlen); | |
601 | else | |
602 | fprintf(stderr, "patricia_lookup: take right at %d\n", node->bit); | |
603 | #endif /* PATRICIA_DEBUG */ | |
604 | node = node->r; | |
605 | } | |
606 | else | |
607 | { | |
608 | if(node->l == NULL) | |
609 | break; | |
610 | #ifdef PATRICIA_DEBUG | |
611 | if(node->prefix) | |
612 | fprintf(stderr, | |
613 | "patricia_lookup: take left %s/%d\n", | |
614 | prefix_toa(node->prefix), node->prefix->bitlen); | |
615 | else | |
616 | fprintf(stderr, "patricia_lookup: take left at %d\n", node->bit); | |
617 | #endif /* PATRICIA_DEBUG */ | |
618 | node = node->l; | |
619 | } | |
620 | ||
621 | assert(node); | |
622 | } | |
623 | ||
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 */ | |
629 | ||
630 | test_addr = rb_prefix_touchar(node->prefix); | |
631 | /* find the first bit different */ | |
632 | check_bit = (node->bit < bitlen) ? node->bit : bitlen; | |
633 | differ_bit = 0; | |
634 | for (i = 0; i * 8 < check_bit; i++) | |
635 | { | |
636 | if((r = (addr[i] ^ test_addr[i])) == 0) | |
637 | { | |
638 | differ_bit = (i + 1) * 8; | |
639 | continue; | |
640 | } | |
641 | /* I know the better way, but for now */ | |
642 | for (j = 0; j < 8; j++) | |
643 | { | |
644 | if(BIT_TEST(r, (0x80 >> j))) | |
645 | break; | |
646 | } | |
647 | /* must be found */ | |
648 | assert(j < 8); | |
649 | differ_bit = i * 8 + j; | |
650 | break; | |
651 | } | |
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 */ | |
657 | ||
658 | parent = node->parent; | |
659 | while (parent && parent->bit >= differ_bit) | |
660 | { | |
661 | node = parent; | |
662 | parent = node->parent; | |
663 | #ifdef PATRICIA_DEBUG | |
664 | if(node->prefix) | |
665 | fprintf(stderr, "patricia_lookup: up to %s/%d\n", | |
666 | prefix_toa(node->prefix), node->prefix->bitlen); | |
667 | else | |
668 | fprintf(stderr, "patricia_lookup: up to %d\n", node->bit); | |
669 | #endif /* PATRICIA_DEBUG */ | |
670 | } | |
671 | ||
672 | if(differ_bit == bitlen && node->bit == bitlen) | |
673 | { | |
674 | if(node->prefix) | |
675 | { | |
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 */ | |
680 | return (node); | |
681 | } | |
682 | node->prefix = Ref_Prefix(prefix); | |
683 | #ifdef PATRICIA_DEBUG | |
684 | fprintf(stderr, | |
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); | |
689 | return (node); | |
690 | } | |
691 | ||
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++; | |
699 | ||
700 | if(node->bit == differ_bit) | |
701 | { | |
702 | new_node->parent = node; | |
703 | if(node->bit < patricia->maxbits && | |
704 | BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) | |
705 | { | |
706 | assert(node->r == NULL); | |
707 | node->r = new_node; | |
708 | } | |
709 | else | |
710 | { | |
711 | assert(node->l == NULL); | |
712 | node->l = new_node; | |
713 | } | |
714 | #ifdef PATRICIA_DEBUG | |
715 | fprintf(stderr, | |
716 | "patricia_lookup: new_node #2 %s/%d (child)\n", | |
717 | prefix_toa(prefix), prefix->bitlen); | |
718 | #endif /* PATRICIA_DEBUG */ | |
719 | return (new_node); | |
720 | } | |
721 | ||
722 | if(bitlen == differ_bit) | |
723 | { | |
724 | if(bitlen < patricia->maxbits && | |
725 | BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) | |
726 | { | |
727 | new_node->r = node; | |
728 | } | |
729 | else | |
730 | { | |
731 | new_node->l = node; | |
732 | } | |
733 | new_node->parent = node->parent; | |
734 | if(node->parent == NULL) | |
735 | { | |
736 | assert(patricia->head == node); | |
737 | patricia->head = new_node; | |
738 | } | |
739 | else if(node->parent->r == node) | |
740 | { | |
741 | node->parent->r = new_node; | |
742 | } | |
743 | else | |
744 | { | |
745 | node->parent->l = new_node; | |
746 | } | |
747 | node->parent = new_node; | |
748 | #ifdef PATRICIA_DEBUG | |
749 | fprintf(stderr, | |
750 | "patricia_lookup: new_node #3 %s/%d (parent)\n", | |
751 | prefix_toa(prefix), prefix->bitlen); | |
752 | #endif /* PATRICIA_DEBUG */ | |
753 | } | |
754 | else | |
755 | { | |
756 | glue = rb_malloc(sizeof(rb_patricia_node_t)); | |
757 | glue->bit = differ_bit; | |
758 | glue->prefix = NULL; | |
759 | glue->parent = node->parent; | |
760 | glue->data = NULL; | |
761 | patricia->num_active_node++; | |
762 | if(differ_bit < patricia->maxbits && | |
763 | BIT_TEST(addr[differ_bit >> 3], 0x80 >> (differ_bit & 0x07))) | |
764 | { | |
765 | glue->r = new_node; | |
766 | glue->l = node; | |
767 | } | |
768 | else | |
769 | { | |
770 | glue->r = node; | |
771 | glue->l = new_node; | |
772 | } | |
773 | new_node->parent = glue; | |
774 | ||
775 | if(node->parent == NULL) | |
776 | { | |
777 | assert(patricia->head == node); | |
778 | patricia->head = glue; | |
779 | } | |
780 | else if(node->parent->r == node) | |
781 | { | |
782 | node->parent->r = glue; | |
783 | } | |
784 | else | |
785 | { | |
786 | node->parent->l = glue; | |
787 | } | |
788 | node->parent = glue; | |
789 | #ifdef PATRICIA_DEBUG | |
790 | fprintf(stderr, | |
791 | "patricia_lookup: new_node #4 %s/%d (glue+node)\n", | |
792 | prefix_toa(prefix), prefix->bitlen); | |
793 | #endif /* PATRICIA_DEBUG */ | |
794 | } | |
795 | return (new_node); | |
796 | } | |
797 | ||
798 | ||
799 | void | |
800 | rb_patricia_remove(rb_patricia_tree_t * patricia, rb_patricia_node_t * node) | |
801 | { | |
802 | rb_patricia_node_t *parent, *child; | |
803 | ||
804 | assert(patricia); | |
805 | assert(node); | |
806 | ||
807 | if(node->r && node->l) | |
808 | { | |
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 */ | |
813 | ||
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); | |
818 | node->prefix = NULL; | |
819 | /* Also I needed to clear data pointer -- masaki */ | |
820 | node->data = NULL; | |
821 | return; | |
822 | } | |
823 | ||
824 | if(node->r == NULL && node->l == NULL) | |
825 | { | |
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); | |
832 | rb_free(node); | |
833 | patricia->num_active_node--; | |
834 | ||
835 | if(parent == NULL) | |
836 | { | |
837 | assert(patricia->head == node); | |
838 | patricia->head = NULL; | |
839 | return; | |
840 | } | |
841 | ||
842 | if(parent->r == node) | |
843 | { | |
844 | parent->r = NULL; | |
845 | child = parent->l; | |
846 | } | |
847 | else | |
848 | { | |
849 | assert(parent->l == node); | |
850 | parent->l = NULL; | |
851 | child = parent->r; | |
852 | } | |
853 | ||
854 | if(parent->prefix) | |
855 | return; | |
856 | ||
857 | /* we need to remove parent too */ | |
858 | ||
859 | if(parent->parent == NULL) | |
860 | { | |
861 | assert(patricia->head == parent); | |
862 | patricia->head = child; | |
863 | } | |
864 | else if(parent->parent->r == parent) | |
865 | { | |
866 | parent->parent->r = child; | |
867 | } | |
868 | else | |
869 | { | |
870 | assert(parent->parent->l == parent); | |
871 | parent->parent->l = child; | |
872 | } | |
873 | child->parent = parent->parent; | |
874 | rb_free(parent); | |
875 | patricia->num_active_node--; | |
876 | return; | |
877 | } | |
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 */ | |
882 | if(node->r) | |
883 | { | |
884 | child = node->r; | |
885 | } | |
886 | else | |
887 | { | |
888 | assert(node->l); | |
889 | child = node->l; | |
890 | } | |
891 | parent = node->parent; | |
892 | child->parent = parent; | |
893 | ||
894 | Deref_Prefix(node->prefix); | |
895 | rb_free(node); | |
896 | patricia->num_active_node--; | |
897 | ||
898 | if(parent == NULL) | |
899 | { | |
900 | assert(patricia->head == node); | |
901 | patricia->head = child; | |
902 | return; | |
903 | } | |
904 | ||
905 | if(parent->r == node) | |
906 | { | |
907 | parent->r = child; | |
908 | } | |
909 | else | |
910 | { | |
911 | assert(parent->l == node); | |
912 | parent->l = child; | |
913 | } | |
914 | } | |
915 | ||
916 | rb_patricia_node_t * | |
917 | make_and_lookup_ip(rb_patricia_tree_t * tree, struct sockaddr *in, int bitlen) | |
918 | { | |
919 | rb_prefix_t *prefix; | |
920 | rb_patricia_node_t *node; | |
921 | void *ipptr = NULL; | |
922 | #ifdef RB_IPV6 | |
923 | if(in->sa_family == AF_INET6) | |
924 | ipptr = &((struct sockaddr_in6 *)in)->sin6_addr; | |
925 | else | |
926 | #endif | |
927 | ipptr = &((struct sockaddr_in *)in)->sin_addr; | |
928 | ||
929 | prefix = New_Prefix(in->sa_family, ipptr, bitlen); | |
930 | ||
931 | if(prefix == NULL) | |
932 | return NULL; | |
933 | ||
934 | node = rb_patricia_lookup(tree, prefix); | |
935 | ||
936 | ||
937 | ||
938 | Deref_Prefix(prefix); | |
939 | return (node); | |
940 | } | |
941 | ||
942 | ||
943 | rb_patricia_node_t * | |
944 | make_and_lookup(rb_patricia_tree_t * tree, const char *string) | |
945 | { | |
946 | rb_prefix_t *prefix; | |
947 | rb_patricia_node_t *node; | |
948 | ||
949 | if((prefix = ascii2prefix(AF_INET, string)) != NULL) | |
950 | { | |
951 | node = rb_patricia_lookup(tree, prefix); | |
952 | } | |
953 | else | |
954 | #ifdef RB_IPV6 | |
955 | if((prefix = ascii2prefix(AF_INET6, string)) != NULL) | |
956 | { | |
957 | node = rb_patricia_lookup(tree, prefix); | |
958 | } | |
959 | else | |
960 | #endif | |
961 | return NULL; | |
962 | #ifdef PATRICIA_DEBUG | |
963 | printf("make_and_lookup: %s/%d\n", prefix_toa(prefix), prefix->bitlen); | |
964 | #endif | |
965 | Deref_Prefix(prefix); | |
966 | return (node); | |
967 | } | |
968 | ||
969 | #ifdef NOTYET | |
970 | static rb_patricia_node_t * | |
971 | try_search_exact(rb_patricia_tree_t * tree, char *string) | |
972 | { | |
973 | rb_prefix_t *prefix; | |
974 | rb_patricia_node_t *node; | |
975 | if((prefix = ascii2prefix(AF_INET, string)) != NULL) | |
976 | { | |
977 | node = rb_patricia_search_exact(tree, prefix); | |
978 | Deref_Prefix(prefix); | |
979 | return (node); | |
980 | } | |
981 | #ifdef RB_IPV6 | |
982 | else if((prefix = ascii2prefix(AF_INET6, string)) != NULL) | |
983 | { | |
984 | node = rb_patricia_search_exact(tree, prefix); | |
985 | Deref_Prefix(prefix); | |
986 | return (node); | |
987 | } | |
988 | #endif | |
989 | else | |
990 | return NULL; | |
991 | } | |
992 | ||
993 | void | |
994 | lookup_then_remove(rb_patricia_tree_t * tree, char *string) | |
995 | { | |
996 | rb_patricia_node_t *node; | |
997 | ||
998 | if((node = try_search_exact(tree, string))) | |
999 | patricia_remove(tree, node); | |
1000 | } | |
1001 | #endif | |
1002 | ||
1003 | rb_patricia_node_t * | |
1004 | rb_match_ip(rb_patricia_tree_t * tree, struct sockaddr *ip) | |
1005 | { | |
1006 | rb_prefix_t *prefix; | |
1007 | rb_patricia_node_t *node; | |
1008 | void *ipptr; | |
1009 | unsigned int len; | |
1010 | int family; | |
1011 | #ifndef RB_IPV6 | |
1012 | len = 32; | |
1013 | family = AF_INET; | |
1014 | ipptr = &((struct sockaddr_in *)ip)->sin_addr; | |
1015 | #else | |
1016 | if(ip->sa_family == AF_INET6) | |
1017 | { | |
1018 | len = 128; | |
1019 | family = AF_INET6; | |
1020 | ipptr = &((struct sockaddr_in6 *)ip)->sin6_addr; | |
1021 | } else { | |
1022 | len = 32; | |
1023 | family = AF_INET; | |
1024 | ipptr = &((struct sockaddr_in *)ip)->sin_addr; | |
1025 | } | |
1026 | #endif | |
1027 | ||
1028 | if((prefix = New_Prefix(family, ipptr, len)) != NULL) | |
1029 | { | |
1030 | node = rb_patricia_search_best(tree, prefix); | |
1031 | Deref_Prefix(prefix); | |
1032 | return (node); | |
1033 | } | |
1034 | return NULL; | |
1035 | } | |
1036 | ||
1037 | rb_patricia_node_t * | |
1038 | rb_match_ip_exact(rb_patricia_tree_t * tree, struct sockaddr *ip, unsigned int len) | |
1039 | { | |
1040 | rb_prefix_t *prefix; | |
1041 | rb_patricia_node_t *node; | |
1042 | void *ipptr; | |
1043 | int family; | |
1044 | #ifndef RB_IPV6 | |
1045 | if(len > 128) | |
1046 | len = 128; | |
1047 | ||
1048 | family = AF_INET; | |
1049 | ipptr = &((struct sockaddr_in *)ip)->sin_addr; | |
1050 | #else | |
1051 | if(ip->sa_family == AF_INET6) | |
1052 | { | |
1053 | if(len > 128) | |
1054 | len = 128; | |
1055 | family = AF_INET6; | |
1056 | ipptr = &((struct sockaddr_in6 *)ip)->sin6_addr; | |
1057 | } else { | |
1058 | if(len > 32) | |
1059 | len = 32; | |
1060 | family = AF_INET; | |
1061 | ipptr = &((struct sockaddr_in *)ip)->sin_addr; | |
1062 | } | |
1063 | #endif | |
1064 | ||
1065 | if((prefix = New_Prefix(family, ipptr, len)) != NULL) | |
1066 | { | |
1067 | node = rb_patricia_search_exact(tree, prefix); | |
1068 | Deref_Prefix(prefix); | |
1069 | return (node); | |
1070 | } | |
1071 | return NULL; | |
1072 | } | |
1073 | ||
1074 | ||
1075 | ||
1076 | rb_patricia_node_t * | |
1077 | rb_match_string(rb_patricia_tree_t * tree, const char *string) | |
1078 | { | |
1079 | rb_patricia_node_t *node; | |
1080 | rb_prefix_t *prefix; | |
1081 | ||
1082 | if((prefix = ascii2prefix(AF_INET, string)) != NULL) | |
1083 | { | |
1084 | node = rb_patricia_search_best(tree, prefix); | |
1085 | Deref_Prefix(prefix); | |
1086 | } | |
1087 | else | |
1088 | #ifdef RB_IPV6 | |
1089 | if((prefix = ascii2prefix(AF_INET6, string)) != NULL) | |
1090 | { | |
1091 | node = rb_patricia_search_best(tree, prefix); | |
1092 | Deref_Prefix(prefix); | |
1093 | } | |
1094 | else | |
1095 | #endif | |
1096 | return NULL; | |
1097 | return node; | |
1098 | } | |
1099 | ||
1100 | rb_patricia_node_t * | |
1101 | rb_match_exact_string(rb_patricia_tree_t * tree, const char *string) | |
1102 | { | |
1103 | rb_prefix_t *prefix; | |
1104 | rb_patricia_node_t *node; | |
1105 | if((prefix = ascii2prefix(AF_INET, string)) != NULL) | |
1106 | { | |
1107 | node = rb_patricia_search_exact(tree, prefix); | |
1108 | Deref_Prefix(prefix); | |
1109 | } | |
1110 | else | |
1111 | #ifdef RB_IPV6 | |
1112 | if((prefix = ascii2prefix(AF_INET6, string)) != NULL) | |
1113 | { | |
1114 | node = rb_patricia_search_exact(tree, prefix); | |
1115 | Deref_Prefix(prefix); | |
1116 | } | |
1117 | else | |
1118 | #endif | |
1119 | return NULL; | |
1120 | return node; | |
1121 | } |