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