Annotation of libaitio/src/patricia.c, revision 1.2
1.2 ! 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.1.2.1 2011/06/07 11:37:13 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