Annotation of libelwix/src/patricia.c, revision 1.1
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: /* } */
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 -] / libelwix / src