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