1 |
/* |
2 |
* $Id$ |
3 |
* Dave Plonka <plonka@doit.wisc.edu> |
4 |
* |
5 |
* This file had been called "radix.c" in the MRT sources. |
6 |
* |
7 |
* I renamed it to "patricia.c" since it's not an implementation of a general |
8 |
* radix trie. Also I pulled in various requirements from "prefix.c" and |
9 |
* "demo.c" so that it could be used as a standalone API. |
10 |
* |
11 |
* Copyright (c) 1999-2013 |
12 |
* |
13 |
* The Regents of the University of Michigan ("The Regents") and Merit |
14 |
* Network, Inc. |
15 |
* |
16 |
* Redistributions of source code must retain the above copyright notice, |
17 |
* this list of conditions and the following disclaimer. |
18 |
* |
19 |
* Redistributions in binary form must reproduce the above copyright |
20 |
* notice, this list of conditions and the following disclaimer in the |
21 |
* documentation and/or other materials provided with the distribution. |
22 |
* |
23 |
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
24 |
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
25 |
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
26 |
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
27 |
* HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
28 |
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
29 |
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
30 |
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
31 |
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
32 |
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
33 |
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
34 |
*/ |
35 |
|
36 |
#include <assert.h> /* assert */ |
37 |
#include <stddef.h> /* NULL */ |
38 |
#include <stdio.h> /* sprintf, fprintf, stderr */ |
39 |
#include <stdlib.h> /* free, atol, calloc */ |
40 |
#include <string.h> /* memcpy, strchr, strlen */ |
41 |
#include <sys/types.h> /* BSD: for inet_addr */ |
42 |
#include <sys/socket.h> /* BSD, Linux: for inet_addr */ |
43 |
#include <netinet/in.h> /* BSD, Linux: for inet_addr */ |
44 |
#include <arpa/inet.h> /* BSD, Linux, Solaris: for inet_addr */ |
45 |
|
46 |
#include "patricia.h" |
47 |
#include "memory.h" |
48 |
|
49 |
/* { from prefix.c */ |
50 |
|
51 |
/* prefix_tochar |
52 |
* convert prefix information to bytes |
53 |
*/ |
54 |
static unsigned char * |
55 |
prefix_tochar(prefix_t *prefix) |
56 |
{ |
57 |
if (prefix == NULL) |
58 |
return NULL; |
59 |
return (unsigned char *)&prefix->add.sin; |
60 |
} |
61 |
|
62 |
static int |
63 |
comp_with_mask(void *addr, void *dest, unsigned int mask) |
64 |
{ |
65 |
if ( /* mask/8 == 0 || */ memcmp(addr, dest, mask / 8) == 0) |
66 |
{ |
67 |
int n = mask / 8; |
68 |
int m = ((-1) << (8 - (mask % 8))); |
69 |
|
70 |
if (mask % 8 == 0 || (((unsigned char *)addr)[n] & m) == (((unsigned char *)dest)[n] & m)) |
71 |
return 1; |
72 |
} |
73 |
|
74 |
return 0; |
75 |
} |
76 |
|
77 |
/* |
78 |
* convert prefix information to ascii string with length |
79 |
*/ |
80 |
const char * |
81 |
patricia_prefix_toa(const prefix_t *prefix, int with_len) |
82 |
{ |
83 |
static char buf[INET6_ADDRSTRLEN + sizeof("/128")]; |
84 |
|
85 |
assert(prefix); |
86 |
assert(prefix->ref_count >= 0); |
87 |
assert((prefix->family == AF_INET && prefix->bitlen <= 32) || |
88 |
(prefix->family == AF_INET6 && prefix->bitlen <= 128)); |
89 |
|
90 |
inet_ntop(prefix->family, &prefix->add.sin6, buf, INET6_ADDRSTRLEN); |
91 |
|
92 |
if (with_len) |
93 |
sprintf(buf + strlen(buf), "/%d", prefix->bitlen); |
94 |
return buf; |
95 |
} |
96 |
|
97 |
static prefix_t * |
98 |
New_Prefix2(int family, void *dest, int bitlen, prefix_t *prefix) |
99 |
{ |
100 |
int dynamic_allocated = 0; |
101 |
int addr_size = 0; |
102 |
|
103 |
switch (family) |
104 |
{ |
105 |
case AF_INET: |
106 |
addr_size = sizeof(struct in_addr); |
107 |
break; |
108 |
case AF_INET6: |
109 |
addr_size = sizeof(struct in6_addr); |
110 |
break; |
111 |
default: return NULL; |
112 |
} |
113 |
|
114 |
if (!prefix) |
115 |
{ |
116 |
prefix = xcalloc(sizeof(prefix_t)); |
117 |
dynamic_allocated = 1; |
118 |
} |
119 |
|
120 |
memcpy(&prefix->add.sin6, dest, addr_size); |
121 |
prefix->bitlen = (bitlen >= 0) ? bitlen : addr_size * 8; |
122 |
prefix->family = family; |
123 |
prefix->ref_count = dynamic_allocated == 1; |
124 |
|
125 |
/* fprintf(stderr, "[C %s, %d]\n", patricia_prefix_toa(prefix), prefix->ref_count); */ |
126 |
return prefix; |
127 |
} |
128 |
|
129 |
static prefix_t * |
130 |
New_Prefix(int family, void *dest, int bitlen) |
131 |
{ |
132 |
return New_Prefix2(family, dest, bitlen, NULL); |
133 |
} |
134 |
|
135 |
/* ascii2prefix |
136 |
*/ |
137 |
static prefix_t * |
138 |
ascii2prefix(int family, const char *string) |
139 |
{ |
140 |
int bitlen, maxbitlen = 0; |
141 |
union |
142 |
{ |
143 |
struct in_addr sin; |
144 |
struct in6_addr sin6; |
145 |
} sin; |
146 |
|
147 |
assert(string); |
148 |
|
149 |
/* Easy way to handle both families */ |
150 |
if (family == 0) |
151 |
{ |
152 |
family = AF_INET; |
153 |
|
154 |
if (strchr (string, ':')) |
155 |
family = AF_INET6; |
156 |
} |
157 |
|
158 |
if (family == AF_INET) |
159 |
maxbitlen = sizeof(struct in_addr) * 8; |
160 |
else if (family == AF_INET6) |
161 |
maxbitlen = sizeof(struct in6_addr) * 8; |
162 |
|
163 |
const char *const cp = strchr(string, '/'); |
164 |
if (cp) |
165 |
{ |
166 |
char save[MAXLINE]; |
167 |
|
168 |
bitlen = atoi(cp + 1); |
169 |
|
170 |
/* *cp = '\0'; */ |
171 |
/* Copy the string to save. Avoid destroying the string */ |
172 |
assert(cp - string < MAXLINE); |
173 |
memcpy(save, string, cp - string); |
174 |
|
175 |
save[cp - string] = '\0'; |
176 |
string = save; |
177 |
|
178 |
if (bitlen < 0 || bitlen > maxbitlen) |
179 |
bitlen = maxbitlen; |
180 |
} |
181 |
else |
182 |
bitlen = maxbitlen; |
183 |
|
184 |
if (inet_pton(family, string, &sin) <= 0) |
185 |
return NULL; |
186 |
return New_Prefix(family, &sin, bitlen); |
187 |
} |
188 |
|
189 |
static prefix_t * |
190 |
Ref_Prefix(prefix_t *prefix) |
191 |
{ |
192 |
if (prefix == NULL) |
193 |
return NULL; |
194 |
|
195 |
if (prefix->ref_count == 0) |
196 |
/* Make a copy in case of a static prefix */ |
197 |
return New_Prefix2(prefix->family, &prefix->add, prefix->bitlen, NULL); |
198 |
|
199 |
prefix->ref_count++; |
200 |
|
201 |
/* fprintf(stderr, "[A %s, %d]\n", patricia_prefix_toa(prefix), prefix->ref_count); */ |
202 |
return prefix; |
203 |
} |
204 |
|
205 |
static void |
206 |
Deref_Prefix(prefix_t *prefix) |
207 |
{ |
208 |
if (prefix == NULL) |
209 |
return; |
210 |
|
211 |
/* For secure programming, raise an assert. No static prefix can call this */ |
212 |
assert(prefix->ref_count > 0); |
213 |
if (--prefix->ref_count <= 0) |
214 |
xfree(prefix); |
215 |
} |
216 |
/* } */ |
217 |
|
218 |
/* #define PATRICIA_DEBUG 1 */ |
219 |
|
220 |
/* these routines support continuous mask only */ |
221 |
|
222 |
patricia_tree_t * |
223 |
patricia_new(unsigned int maxbits) |
224 |
{ |
225 |
patricia_tree_t *patricia = xcalloc(sizeof *patricia); |
226 |
patricia->maxbits = maxbits; |
227 |
|
228 |
assert(maxbits <= PATRICIA_MAXBITS); /* XXX */ |
229 |
return patricia; |
230 |
} |
231 |
|
232 |
/* |
233 |
* if func is supplied, it will be called as func(node->data) |
234 |
* before deleting the node |
235 |
*/ |
236 |
void |
237 |
patricia_clear(patricia_tree_t *patricia, void (*func)(void *)) |
238 |
{ |
239 |
assert(patricia); |
240 |
|
241 |
if (patricia->head) |
242 |
{ |
243 |
patricia_node_t *Xstack[PATRICIA_MAXBITS + 1]; |
244 |
patricia_node_t **Xsp = Xstack; |
245 |
patricia_node_t *Xrn = patricia->head; |
246 |
|
247 |
while (Xrn) |
248 |
{ |
249 |
patricia_node_t *l = Xrn->l; |
250 |
patricia_node_t *r = Xrn->r; |
251 |
|
252 |
if (Xrn->prefix) |
253 |
{ |
254 |
Deref_Prefix(Xrn->prefix); |
255 |
|
256 |
if (Xrn->data && func) |
257 |
func(Xrn->data); |
258 |
} |
259 |
else |
260 |
{ |
261 |
assert(Xrn->data == NULL); |
262 |
} |
263 |
|
264 |
xfree(Xrn); |
265 |
patricia->num_active_node--; |
266 |
|
267 |
if (l) |
268 |
{ |
269 |
if (r) |
270 |
{ |
271 |
*Xsp++ = r; |
272 |
} |
273 |
|
274 |
Xrn = l; |
275 |
} |
276 |
else if (r) |
277 |
{ |
278 |
Xrn = r; |
279 |
} |
280 |
else if (Xsp != Xstack) |
281 |
{ |
282 |
Xrn = *(--Xsp); |
283 |
} |
284 |
else |
285 |
{ |
286 |
Xrn = NULL; |
287 |
} |
288 |
} |
289 |
} |
290 |
|
291 |
assert(patricia->num_active_node == 0); |
292 |
/* xfree (patricia); */ |
293 |
} |
294 |
|
295 |
void |
296 |
patricia_destroy(patricia_tree_t *patricia, void (*func)(void *)) |
297 |
{ |
298 |
patricia_clear(patricia, func); |
299 |
xfree(patricia); |
300 |
} |
301 |
|
302 |
/* |
303 |
* if func is supplied, it will be called as func(node->prefix, node->data) |
304 |
*/ |
305 |
void |
306 |
patricia_process(patricia_tree_t *patricia, void (*func)(prefix_t *, void *)) |
307 |
{ |
308 |
patricia_node_t *node; |
309 |
|
310 |
assert(func); |
311 |
|
312 |
PATRICIA_WALK(patricia->head, node) { |
313 |
func(node->prefix, node->data); |
314 |
} PATRICIA_WALK_END; |
315 |
} |
316 |
|
317 |
patricia_node_t * |
318 |
patricia_search_exact(patricia_tree_t *patricia, prefix_t *prefix) |
319 |
{ |
320 |
patricia_node_t *node; |
321 |
unsigned char *addr; |
322 |
unsigned int bitlen; |
323 |
|
324 |
assert(patricia); |
325 |
assert(prefix); |
326 |
assert(prefix->bitlen <= patricia->maxbits); |
327 |
|
328 |
if (patricia->head == NULL) |
329 |
return NULL; |
330 |
|
331 |
node = patricia->head; |
332 |
addr = prefix_touchar(prefix); |
333 |
bitlen = prefix->bitlen; |
334 |
|
335 |
while (node->bit < bitlen) |
336 |
{ |
337 |
if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) |
338 |
{ |
339 |
#ifdef PATRICIA_DEBUG |
340 |
if (node->prefix) |
341 |
fprintf(stderr, "patricia_search_exact: take right %s/%d\n", |
342 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
343 |
else |
344 |
fprintf(stderr, "patricia_search_exact: take right at %u\n", node->bit); |
345 |
#endif /* PATRICIA_DEBUG */ |
346 |
node = node->r; |
347 |
} |
348 |
else |
349 |
{ |
350 |
#ifdef PATRICIA_DEBUG |
351 |
if (node->prefix) |
352 |
fprintf(stderr, "patricia_search_exact: take left %s/%d\n", |
353 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
354 |
else |
355 |
fprintf(stderr, "patricia_search_exact: take left at %u\n", node->bit); |
356 |
#endif /* PATRICIA_DEBUG */ |
357 |
node = node->l; |
358 |
} |
359 |
|
360 |
if (node == NULL) |
361 |
return NULL; |
362 |
} |
363 |
|
364 |
#ifdef PATRICIA_DEBUG |
365 |
if (node->prefix) |
366 |
fprintf(stderr, "patricia_search_exact: stop at %s/%d\n", |
367 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
368 |
else |
369 |
fprintf(stderr, "patricia_search_exact: stop at %u\n", node->bit); |
370 |
#endif /* PATRICIA_DEBUG */ |
371 |
|
372 |
if (node->bit > bitlen || node->prefix == NULL) |
373 |
return NULL; |
374 |
|
375 |
assert(node->bit == bitlen); |
376 |
assert(node->bit == node->prefix->bitlen); |
377 |
|
378 |
if (comp_with_mask(prefix_tochar(node->prefix), prefix_tochar(prefix), bitlen)) |
379 |
{ |
380 |
#ifdef PATRICIA_DEBUG |
381 |
fprintf(stderr, "patricia_search_exact: found %s/%d\n", |
382 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
383 |
#endif /* PATRICIA_DEBUG */ |
384 |
return node; |
385 |
} |
386 |
|
387 |
return NULL; |
388 |
} |
389 |
|
390 |
/* if inclusive != 0, "best" may be the given prefix itself */ |
391 |
patricia_node_t * |
392 |
patricia_search_best2(patricia_tree_t *patricia, prefix_t *prefix, int inclusive) |
393 |
{ |
394 |
patricia_node_t *node; |
395 |
patricia_node_t *stack[PATRICIA_MAXBITS + 1]; |
396 |
unsigned char *addr; |
397 |
unsigned int bitlen; |
398 |
int cnt = 0; |
399 |
|
400 |
assert(patricia); |
401 |
assert(prefix); |
402 |
assert(prefix->bitlen <= patricia->maxbits); |
403 |
|
404 |
if (patricia->head == NULL) |
405 |
return NULL; |
406 |
|
407 |
node = patricia->head; |
408 |
addr = prefix_touchar(prefix); |
409 |
bitlen = prefix->bitlen; |
410 |
|
411 |
while (node->bit < bitlen) |
412 |
{ |
413 |
if (node->prefix) |
414 |
{ |
415 |
#ifdef PATRICIA_DEBUG |
416 |
fprintf(stderr, "patricia_search_best: push %s/%d\n", |
417 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
418 |
#endif /* PATRICIA_DEBUG */ |
419 |
stack[cnt++] = node; |
420 |
} |
421 |
|
422 |
if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) |
423 |
{ |
424 |
#ifdef PATRICIA_DEBUG |
425 |
if (node->prefix) |
426 |
fprintf(stderr, "patricia_search_best: take right %s/%d\n", |
427 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
428 |
else |
429 |
fprintf(stderr, "patricia_search_best: take right at %u\n", node->bit); |
430 |
#endif /* PATRICIA_DEBUG */ |
431 |
node = node->r; |
432 |
} |
433 |
else |
434 |
{ |
435 |
#ifdef PATRICIA_DEBUG |
436 |
if (node->prefix) |
437 |
fprintf(stderr, "patricia_search_best: take left %s/%d\n", |
438 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
439 |
else |
440 |
fprintf(stderr, "patricia_search_best: take left at %u\n", node->bit); |
441 |
#endif /* PATRICIA_DEBUG */ |
442 |
node = node->l; |
443 |
} |
444 |
|
445 |
if (node == NULL) |
446 |
break; |
447 |
} |
448 |
|
449 |
if (inclusive && node && node->prefix) |
450 |
stack[cnt++] = node; |
451 |
|
452 |
#ifdef PATRICIA_DEBUG |
453 |
if (node == NULL) |
454 |
fprintf(stderr, "patricia_search_best: stop at null\n"); |
455 |
else if (node->prefix) |
456 |
fprintf(stderr, "patricia_search_best: stop at %s/%d\n", |
457 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
458 |
else |
459 |
fprintf(stderr, "patricia_search_best: stop at %u\n", node->bit); |
460 |
#endif /* PATRICIA_DEBUG */ |
461 |
|
462 |
if (cnt <= 0) |
463 |
return NULL; |
464 |
|
465 |
while (--cnt >= 0) |
466 |
{ |
467 |
node = stack[cnt]; |
468 |
#ifdef PATRICIA_DEBUG |
469 |
fprintf(stderr, "patricia_search_best: pop %s/%d\n", |
470 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
471 |
#endif /* PATRICIA_DEBUG */ |
472 |
|
473 |
if (comp_with_mask(prefix_tochar(node->prefix), |
474 |
prefix_tochar(prefix), node->prefix->bitlen) && node->prefix->bitlen <= bitlen) |
475 |
{ |
476 |
#ifdef PATRICIA_DEBUG |
477 |
fprintf(stderr, "patricia_search_best: found %s/%d\n", |
478 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
479 |
#endif /* PATRICIA_DEBUG */ |
480 |
return node; |
481 |
} |
482 |
} |
483 |
|
484 |
return NULL; |
485 |
} |
486 |
|
487 |
patricia_node_t * |
488 |
patricia_search_best(patricia_tree_t *patricia, prefix_t *prefix) |
489 |
{ |
490 |
return patricia_search_best2(patricia, prefix, 1); |
491 |
} |
492 |
|
493 |
patricia_node_t * |
494 |
patricia_lookup(patricia_tree_t *patricia, prefix_t *prefix) |
495 |
{ |
496 |
patricia_node_t *node, *new_node, *parent, *glue; |
497 |
unsigned char *addr, *test_addr; |
498 |
unsigned int bitlen, check_bit, differ_bit; |
499 |
int j, r; |
500 |
|
501 |
assert(patricia); |
502 |
assert(prefix); |
503 |
assert(prefix->bitlen <= patricia->maxbits); |
504 |
|
505 |
if (patricia->head == NULL) |
506 |
{ |
507 |
node = xcalloc(sizeof *node); |
508 |
node->bit = prefix->bitlen; |
509 |
node->prefix = Ref_Prefix (prefix); |
510 |
patricia->head = node; |
511 |
#ifdef PATRICIA_DEBUG |
512 |
fprintf(stderr, "patricia_lookup: new_node #0 %s/%d (head)\n", |
513 |
patricia_prefix_toa(prefix), prefix->bitlen); |
514 |
#endif /* PATRICIA_DEBUG */ |
515 |
patricia->num_active_node++; |
516 |
return node; |
517 |
} |
518 |
|
519 |
addr = prefix_touchar(prefix); |
520 |
bitlen = prefix->bitlen; |
521 |
node = patricia->head; |
522 |
|
523 |
while (node->bit < bitlen || node->prefix == NULL) |
524 |
{ |
525 |
if (node->bit < patricia->maxbits && BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) |
526 |
{ |
527 |
if (node->r == NULL) |
528 |
break; |
529 |
#ifdef PATRICIA_DEBUG |
530 |
if (node->prefix) |
531 |
fprintf(stderr, "patricia_lookup: take right %s/%d\n", |
532 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
533 |
else |
534 |
fprintf(stderr, "patricia_lookup: take right at %u\n", node->bit); |
535 |
#endif /* PATRICIA_DEBUG */ |
536 |
|
537 |
node = node->r; |
538 |
} |
539 |
else |
540 |
{ |
541 |
if (node->l == NULL) |
542 |
break; |
543 |
#ifdef PATRICIA_DEBUG |
544 |
if (node->prefix) |
545 |
fprintf(stderr, "patricia_lookup: take left %s/%d\n", |
546 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
547 |
else |
548 |
fprintf(stderr, "patricia_lookup: take left at %u\n", node->bit); |
549 |
#endif /* PATRICIA_DEBUG */ |
550 |
|
551 |
node = node->l; |
552 |
} |
553 |
|
554 |
assert(node); |
555 |
} |
556 |
|
557 |
assert(node->prefix); |
558 |
#ifdef PATRICIA_DEBUG |
559 |
fprintf(stderr, "patricia_lookup: stop at %s/%d\n", |
560 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
561 |
#endif /* PATRICIA_DEBUG */ |
562 |
|
563 |
test_addr = prefix_touchar(node->prefix); |
564 |
|
565 |
/* Find the first bit different */ |
566 |
check_bit = (node->bit < bitlen) ? node->bit : bitlen; |
567 |
differ_bit = 0; |
568 |
|
569 |
for (unsigned int i = 0; i * 8 < check_bit; i++) |
570 |
{ |
571 |
if ((r = (addr[i] ^ test_addr[i])) == 0) |
572 |
{ |
573 |
differ_bit = (i + 1) * 8; |
574 |
continue; |
575 |
} |
576 |
|
577 |
/* I know the better way, but for now */ |
578 |
for (j = 0; j < 8; j++) |
579 |
if (BIT_TEST(r, (0x80 >> j))) |
580 |
break; |
581 |
|
582 |
/* Must be found */ |
583 |
assert(j < 8); |
584 |
differ_bit = i * 8 + j; |
585 |
break; |
586 |
} |
587 |
|
588 |
if (differ_bit > check_bit) |
589 |
differ_bit = check_bit; |
590 |
#ifdef PATRICIA_DEBUG |
591 |
fprintf(stderr, "patricia_lookup: differ_bit %d\n", differ_bit); |
592 |
#endif /* PATRICIA_DEBUG */ |
593 |
|
594 |
parent = node->parent; |
595 |
|
596 |
while (parent && parent->bit >= differ_bit) |
597 |
{ |
598 |
node = parent; |
599 |
parent = node->parent; |
600 |
|
601 |
#ifdef PATRICIA_DEBUG |
602 |
if (node->prefix) |
603 |
fprintf(stderr, "patricia_lookup: up to %s/%d\n", |
604 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
605 |
else |
606 |
fprintf(stderr, "patricia_lookup: up to %u\n", node->bit); |
607 |
#endif /* PATRICIA_DEBUG */ |
608 |
} |
609 |
|
610 |
if (differ_bit == bitlen && node->bit == bitlen) |
611 |
{ |
612 |
if (node->prefix) |
613 |
{ |
614 |
#ifdef PATRICIA_DEBUG |
615 |
fprintf(stderr, "patricia_lookup: found %s/%d\n", |
616 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
617 |
#endif /* PATRICIA_DEBUG */ |
618 |
|
619 |
return node; |
620 |
} |
621 |
|
622 |
node->prefix = Ref_Prefix(prefix); |
623 |
#ifdef PATRICIA_DEBUG |
624 |
fprintf(stderr, "patricia_lookup: new node #1 %s/%d (glue mod)\n", |
625 |
patricia_prefix_toa(prefix), prefix->bitlen); |
626 |
#endif /* PATRICIA_DEBUG */ |
627 |
|
628 |
assert(node->data == NULL); |
629 |
return node; |
630 |
} |
631 |
|
632 |
new_node = xcalloc(sizeof *new_node); |
633 |
new_node->bit = prefix->bitlen; |
634 |
new_node->prefix = Ref_Prefix(prefix); |
635 |
patricia->num_active_node++; |
636 |
|
637 |
if (node->bit == differ_bit) |
638 |
{ |
639 |
new_node->parent = node; |
640 |
|
641 |
if (node->bit < patricia->maxbits && BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) |
642 |
{ |
643 |
assert(node->r == NULL); |
644 |
node->r = new_node; |
645 |
} |
646 |
else |
647 |
{ |
648 |
assert(node->l == NULL); |
649 |
node->l = new_node; |
650 |
} |
651 |
#ifdef PATRICIA_DEBUG |
652 |
fprintf(stderr, "patricia_lookup: new_node #2 %s/%d (child)\n", |
653 |
patricia_prefix_toa(prefix), prefix->bitlen); |
654 |
#endif /* PATRICIA_DEBUG */ |
655 |
return new_node; |
656 |
} |
657 |
|
658 |
if (bitlen == differ_bit) |
659 |
{ |
660 |
if (bitlen < patricia->maxbits && BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) |
661 |
{ |
662 |
new_node->r = node; |
663 |
} |
664 |
else |
665 |
{ |
666 |
new_node->l = node; |
667 |
} |
668 |
|
669 |
new_node->parent = node->parent; |
670 |
|
671 |
if (node->parent == NULL) |
672 |
{ |
673 |
assert(patricia->head == node); |
674 |
patricia->head = new_node; |
675 |
} |
676 |
else if (node->parent->r == node) |
677 |
{ |
678 |
node->parent->r = new_node; |
679 |
} |
680 |
else |
681 |
{ |
682 |
node->parent->l = new_node; |
683 |
} |
684 |
|
685 |
node->parent = new_node; |
686 |
#ifdef PATRICIA_DEBUG |
687 |
fprintf(stderr, "patricia_lookup: new_node #3 %s/%d (parent)\n", |
688 |
patricia_prefix_toa(prefix), prefix->bitlen); |
689 |
#endif /* PATRICIA_DEBUG */ |
690 |
} |
691 |
else |
692 |
{ |
693 |
glue = xcalloc(sizeof *glue); |
694 |
glue->bit = differ_bit; |
695 |
glue->parent = node->parent; |
696 |
patricia->num_active_node++; |
697 |
|
698 |
if (differ_bit < patricia->maxbits && BIT_TEST(addr[differ_bit >> 3], 0x80 >> (differ_bit & 0x07))) |
699 |
{ |
700 |
glue->r = new_node; |
701 |
glue->l = node; |
702 |
} |
703 |
else |
704 |
{ |
705 |
glue->r = node; |
706 |
glue->l = new_node; |
707 |
} |
708 |
|
709 |
new_node->parent = glue; |
710 |
|
711 |
if (node->parent == NULL) |
712 |
{ |
713 |
assert(patricia->head == node); |
714 |
patricia->head = glue; |
715 |
} |
716 |
else if (node->parent->r == node) |
717 |
{ |
718 |
node->parent->r = glue; |
719 |
} |
720 |
else |
721 |
{ |
722 |
node->parent->l = glue; |
723 |
} |
724 |
|
725 |
node->parent = glue; |
726 |
#ifdef PATRICIA_DEBUG |
727 |
fprintf(stderr, "patricia_lookup: new_node #4 %s/%d (glue+node)\n", |
728 |
patricia_prefix_toa(prefix), prefix->bitlen); |
729 |
#endif /* PATRICIA_DEBUG */ |
730 |
} |
731 |
|
732 |
return new_node; |
733 |
} |
734 |
|
735 |
void |
736 |
patricia_remove(patricia_tree_t *patricia, patricia_node_t *node) |
737 |
{ |
738 |
patricia_node_t *parent, *child; |
739 |
|
740 |
assert(patricia); |
741 |
assert(node); |
742 |
|
743 |
if (node->r && node->l) |
744 |
{ |
745 |
#ifdef PATRICIA_DEBUG |
746 |
fprintf(stderr, "patricia_remove: #0 %s/%d (r & l)\n", |
747 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
748 |
#endif /* PATRICIA_DEBUG */ |
749 |
|
750 |
/* |
751 |
* This might be a placeholder node -- have to check and make sure |
752 |
* there is a prefix associated with it ! |
753 |
*/ |
754 |
if (node->prefix != NULL) |
755 |
Deref_Prefix(node->prefix); |
756 |
|
757 |
node->prefix = NULL; |
758 |
/* Also I needed to clear data pointer -- masaki */ |
759 |
node->data = NULL; |
760 |
return; |
761 |
} |
762 |
|
763 |
if (node->r == NULL && node->l == NULL) |
764 |
{ |
765 |
#ifdef PATRICIA_DEBUG |
766 |
fprintf(stderr, "patricia_remove: #1 %s/%d (!r & !l)\n", |
767 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
768 |
#endif /* PATRICIA_DEBUG */ |
769 |
|
770 |
parent = node->parent; |
771 |
Deref_Prefix(node->prefix); |
772 |
xfree(node); |
773 |
patricia->num_active_node--; |
774 |
|
775 |
if (parent == NULL) |
776 |
{ |
777 |
assert(patricia->head == node); |
778 |
patricia->head = NULL; |
779 |
return; |
780 |
} |
781 |
|
782 |
if (parent->r == node) |
783 |
{ |
784 |
parent->r = NULL; |
785 |
child = parent->l; |
786 |
} |
787 |
else |
788 |
{ |
789 |
assert(parent->l == node); |
790 |
|
791 |
parent->l = NULL; |
792 |
child = parent->r; |
793 |
} |
794 |
|
795 |
if (parent->prefix) |
796 |
return; |
797 |
|
798 |
/* We need to remove parent too */ |
799 |
if (parent->parent == NULL) |
800 |
{ |
801 |
assert(patricia->head == parent); |
802 |
patricia->head = child; |
803 |
} |
804 |
else if (parent->parent->r == parent) |
805 |
{ |
806 |
parent->parent->r = child; |
807 |
} |
808 |
else |
809 |
{ |
810 |
assert(parent->parent->l == parent); |
811 |
parent->parent->l = child; |
812 |
} |
813 |
|
814 |
child->parent = parent->parent; |
815 |
xfree(parent); |
816 |
patricia->num_active_node--; |
817 |
return; |
818 |
} |
819 |
|
820 |
#ifdef PATRICIA_DEBUG |
821 |
fprintf(stderr, "patricia_remove: #2 %s/%d (r ^ l)\n", |
822 |
patricia_prefix_toa(node->prefix), node->prefix->bitlen); |
823 |
#endif /* PATRICIA_DEBUG */ |
824 |
|
825 |
if (node->r) |
826 |
{ |
827 |
child = node->r; |
828 |
} |
829 |
else |
830 |
{ |
831 |
assert(node->l); |
832 |
child = node->l; |
833 |
} |
834 |
|
835 |
parent = node->parent; |
836 |
child->parent = parent; |
837 |
|
838 |
Deref_Prefix(node->prefix); |
839 |
xfree(node); |
840 |
patricia->num_active_node--; |
841 |
|
842 |
if (parent == NULL) |
843 |
{ |
844 |
assert(patricia->head == node); |
845 |
patricia->head = child; |
846 |
return; |
847 |
} |
848 |
|
849 |
if (parent->r == node) |
850 |
{ |
851 |
parent->r = child; |
852 |
} |
853 |
else |
854 |
{ |
855 |
assert(parent->l == node); |
856 |
parent->l = child; |
857 |
} |
858 |
} |
859 |
|
860 |
/* { from demo.c */ |
861 |
patricia_node_t * |
862 |
patricia_make_and_lookup(patricia_tree_t *tree, const char *string) |
863 |
{ |
864 |
prefix_t *prefix = ascii2prefix(0, string); |
865 |
|
866 |
if (prefix) |
867 |
{ |
868 |
patricia_node_t *node = patricia_lookup(tree, prefix); |
869 |
Deref_Prefix(prefix); |
870 |
return node; |
871 |
} |
872 |
|
873 |
return NULL; |
874 |
} |
875 |
|
876 |
void |
877 |
patricia_lookup_then_remove(patricia_tree_t *tree, const char *string) |
878 |
{ |
879 |
patricia_node_t *node = patricia_try_search_exact(tree, string); |
880 |
if (node) |
881 |
patricia_remove(tree, node); |
882 |
} |
883 |
|
884 |
patricia_node_t * |
885 |
patricia_try_search_exact(patricia_tree_t *tree, const char *string) |
886 |
{ |
887 |
prefix_t *prefix = ascii2prefix(0, string); |
888 |
|
889 |
if (prefix) |
890 |
{ |
891 |
patricia_node_t *node = patricia_search_exact(tree, prefix); |
892 |
Deref_Prefix(prefix); |
893 |
return node; |
894 |
} |
895 |
|
896 |
return NULL; |
897 |
} |
898 |
|
899 |
patricia_node_t * |
900 |
patricia_try_search_best(patricia_tree_t *tree, const char *string) |
901 |
{ |
902 |
prefix_t *prefix = ascii2prefix(0, string); |
903 |
|
904 |
if (prefix) |
905 |
{ |
906 |
patricia_node_t *node = patricia_search_best(tree, prefix); |
907 |
Deref_Prefix(prefix); |
908 |
return node; |
909 |
} |
910 |
|
911 |
return NULL; |
912 |
} |
913 |
|
914 |
patricia_node_t * |
915 |
patricia_try_search_exact_addr(patricia_tree_t *tree, struct sockaddr *addr, int bitlen) |
916 |
{ |
917 |
int family; |
918 |
void *dest; |
919 |
|
920 |
if (addr->sa_family == AF_INET6) |
921 |
{ |
922 |
if (bitlen == 0 || bitlen > 128) |
923 |
bitlen = 128; |
924 |
family = AF_INET6; |
925 |
dest = &((struct sockaddr_in6 *)addr)->sin6_addr; |
926 |
} |
927 |
else |
928 |
{ |
929 |
if (bitlen == 0 || bitlen > 32) |
930 |
bitlen = 32; |
931 |
family = AF_INET; |
932 |
dest = &((struct sockaddr_in *)addr)->sin_addr; |
933 |
} |
934 |
|
935 |
prefix_t *prefix = New_Prefix(family, dest, bitlen); |
936 |
if (prefix) |
937 |
{ |
938 |
patricia_node_t *node = patricia_search_exact(tree, prefix); |
939 |
Deref_Prefix(prefix); |
940 |
return node; |
941 |
} |
942 |
|
943 |
return NULL; |
944 |
} |
945 |
|
946 |
patricia_node_t * |
947 |
patricia_try_search_best_addr(patricia_tree_t *tree, struct sockaddr *addr, int bitlen) |
948 |
{ |
949 |
int family; |
950 |
void *dest; |
951 |
|
952 |
if (addr->sa_family == AF_INET6) |
953 |
{ |
954 |
if (bitlen == 0 || bitlen > 128) |
955 |
bitlen = 128; |
956 |
family = AF_INET6; |
957 |
dest = &((struct sockaddr_in6 *)addr)->sin6_addr; |
958 |
} |
959 |
else |
960 |
{ |
961 |
if (bitlen == 0 || bitlen > 32) |
962 |
bitlen = 32; |
963 |
family = AF_INET; |
964 |
dest = &((struct sockaddr_in *)addr)->sin_addr; |
965 |
} |
966 |
|
967 |
prefix_t *prefix = New_Prefix(family, dest, bitlen); |
968 |
if (prefix) |
969 |
{ |
970 |
patricia_node_t *node = patricia_search_best(tree, prefix); |
971 |
Deref_Prefix(prefix); |
972 |
return node; |
973 |
} |
974 |
|
975 |
return NULL; |
976 |
} |
977 |
/* } */ |