/[svn]/hopm/trunk/src/patricia.c
ViewVC logotype

Annotation of /hopm/trunk/src/patricia.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 8753 - (hide annotations)
Tue Jan 1 13:56:48 2019 UTC (22 months, 3 weeks ago) by michael
File MIME type: text/x-chdr
File size: 23620 byte(s)
- patricia: update to latest version from ircd-hybrid

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

Properties

Name Value
svn:eol-style native
svn:keywords Id

svnadmin@ircd-hybrid.org
ViewVC Help
Powered by ViewVC 1.1.28