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