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