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