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