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