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