Annotation of embedaddon/ntp/lib/isc/radix.c, revision 1.1
1.1 ! misho 1: /*
! 2: * Copyright (C) 2007-2009 Internet Systems Consortium, Inc. ("ISC")
! 3: *
! 4: * Permission to use, copy, modify, and/or distribute this software for any
! 5: * purpose with or without fee is hereby granted, provided that the above
! 6: * copyright notice and this permission notice appear in all copies.
! 7: *
! 8: * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
! 9: * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
! 10: * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
! 11: * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
! 12: * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
! 13: * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
! 14: * PERFORMANCE OF THIS SOFTWARE.
! 15: */
! 16:
! 17: /* $Id: radix.c,v 1.20.36.3 2009/01/18 23:47:41 tbox Exp $ */
! 18:
! 19: /*
! 20: * This source was adapted from MRT's RCS Ids:
! 21: * Id: radix.c,v 1.10.2.1 1999/11/29 05:16:24 masaki Exp
! 22: * Id: prefix.c,v 1.37.2.9 2000/03/10 02:53:19 labovit Exp
! 23: */
! 24:
! 25: #include <config.h>
! 26:
! 27: #include <isc/mem.h>
! 28: #include <isc/types.h>
! 29: #include <isc/util.h>
! 30: #include <isc/radix.h>
! 31:
! 32: static isc_result_t
! 33: _new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family,
! 34: void *dest, int bitlen);
! 35:
! 36: static void
! 37: _deref_prefix(isc_mem_t *mctx, isc_prefix_t *prefix);
! 38:
! 39: static isc_result_t
! 40: _ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix);
! 41:
! 42: static int
! 43: _comp_with_mask(void *addr, void *dest, u_int mask);
! 44:
! 45: static void
! 46: _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);
! 47:
! 48: static isc_result_t
! 49: _new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest,
! 50: int bitlen)
! 51: {
! 52: isc_prefix_t *prefix;
! 53:
! 54: REQUIRE(target != NULL);
! 55:
! 56: if (family != AF_INET6 && family != AF_INET && family != AF_UNSPEC)
! 57: return (ISC_R_NOTIMPLEMENTED);
! 58:
! 59: prefix = isc_mem_get(mctx, sizeof(isc_prefix_t));
! 60: if (prefix == NULL)
! 61: return (ISC_R_NOMEMORY);
! 62:
! 63: if (family == AF_INET6) {
! 64: prefix->bitlen = (bitlen >= 0) ? bitlen : 128;
! 65: memcpy(&prefix->add.sin6, dest, 16);
! 66: } else {
! 67: /* AF_UNSPEC is "any" or "none"--treat it as AF_INET */
! 68: prefix->bitlen = (bitlen >= 0) ? bitlen : 32;
! 69: memcpy(&prefix->add.sin, dest, 4);
! 70: }
! 71:
! 72: prefix->family = family;
! 73:
! 74: isc_refcount_init(&prefix->refcount, 1);
! 75:
! 76: *target = prefix;
! 77: return (ISC_R_SUCCESS);
! 78: }
! 79:
! 80: static void
! 81: _deref_prefix(isc_mem_t *mctx, isc_prefix_t *prefix) {
! 82: int refs;
! 83:
! 84: if (prefix == NULL)
! 85: return;
! 86:
! 87: isc_refcount_decrement(&prefix->refcount, &refs);
! 88:
! 89: if (refs <= 0) {
! 90: isc_refcount_destroy(&prefix->refcount);
! 91: isc_mem_put(mctx, prefix, sizeof(isc_prefix_t));
! 92: }
! 93: }
! 94:
! 95: static isc_result_t
! 96: _ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix) {
! 97: INSIST(prefix != NULL);
! 98: INSIST((prefix->family == AF_INET && prefix->bitlen <= 32) ||
! 99: (prefix->family == AF_INET6 && prefix->bitlen <= 128) ||
! 100: (prefix->family == AF_UNSPEC && prefix->bitlen == 0));
! 101: REQUIRE(target != NULL && *target == NULL);
! 102:
! 103: /*
! 104: * If this prefix is a static allocation, copy it into new memory.
! 105: * (Note, the refcount still has to be destroyed by the calling
! 106: * routine.)
! 107: */
! 108: if (isc_refcount_current(&prefix->refcount) == 0) {
! 109: isc_result_t ret;
! 110: ret = _new_prefix(mctx, target, prefix->family,
! 111: &prefix->add, prefix->bitlen);
! 112: return ret;
! 113: }
! 114:
! 115: isc_refcount_increment(&prefix->refcount, NULL);
! 116:
! 117: *target = prefix;
! 118: return (ISC_R_SUCCESS);
! 119: }
! 120:
! 121: static int
! 122: _comp_with_mask(void *addr, void *dest, u_int mask) {
! 123:
! 124: /* Mask length of zero matches everything */
! 125: if (mask == 0)
! 126: return (1);
! 127:
! 128: if (memcmp(addr, dest, mask / 8) == 0) {
! 129: int n = mask / 8;
! 130: int m = ((~0) << (8 - (mask % 8)));
! 131:
! 132: if ((mask % 8) == 0 ||
! 133: (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m))
! 134: return (1);
! 135: }
! 136: return (0);
! 137: }
! 138:
! 139: isc_result_t
! 140: isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits) {
! 141: isc_radix_tree_t *radix;
! 142:
! 143: REQUIRE(target != NULL && *target == NULL);
! 144:
! 145: radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t));
! 146: if (radix == NULL)
! 147: return (ISC_R_NOMEMORY);
! 148:
! 149: radix->mctx = mctx;
! 150: radix->maxbits = maxbits;
! 151: radix->head = NULL;
! 152: radix->num_active_node = 0;
! 153: radix->num_added_node = 0;
! 154: RUNTIME_CHECK(maxbits <= RADIX_MAXBITS); /* XXX */
! 155: radix->magic = RADIX_TREE_MAGIC;
! 156: *target = radix;
! 157: return (ISC_R_SUCCESS);
! 158: }
! 159:
! 160: /*
! 161: * if func is supplied, it will be called as func(node->data)
! 162: * before deleting the node
! 163: */
! 164:
! 165: static void
! 166: _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
! 167:
! 168: REQUIRE(radix != NULL);
! 169:
! 170: if (radix->head != NULL) {
! 171:
! 172: isc_radix_node_t *Xstack[RADIX_MAXBITS+1];
! 173: isc_radix_node_t **Xsp = Xstack;
! 174: isc_radix_node_t *Xrn = radix->head;
! 175:
! 176: while (Xrn != NULL) {
! 177: isc_radix_node_t *l = Xrn->l;
! 178: isc_radix_node_t *r = Xrn->r;
! 179:
! 180: if (Xrn->prefix != NULL) {
! 181: _deref_prefix(radix->mctx, Xrn->prefix);
! 182: if (func != NULL && (Xrn->data[0] != NULL ||
! 183: Xrn->data[1] != NULL))
! 184: func(Xrn->data);
! 185: } else {
! 186: INSIST(Xrn->data[0] == NULL &&
! 187: Xrn->data[1] == NULL);
! 188: }
! 189:
! 190: isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn));
! 191: radix->num_active_node--;
! 192:
! 193: if (l != NULL) {
! 194: if (r != NULL) {
! 195: *Xsp++ = r;
! 196: }
! 197: Xrn = l;
! 198: } else if (r != NULL) {
! 199: Xrn = r;
! 200: } else if (Xsp != Xstack) {
! 201: Xrn = *(--Xsp);
! 202: } else {
! 203: Xrn = NULL;
! 204: }
! 205: }
! 206: }
! 207: RUNTIME_CHECK(radix->num_active_node == 0);
! 208: }
! 209:
! 210:
! 211: void
! 212: isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func)
! 213: {
! 214: REQUIRE(radix != NULL);
! 215: _clear_radix(radix, func);
! 216: isc_mem_put(radix->mctx, radix, sizeof(*radix));
! 217: }
! 218:
! 219:
! 220: /*
! 221: * func will be called as func(node->prefix, node->data)
! 222: */
! 223: void
! 224: isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func)
! 225: {
! 226: isc_radix_node_t *node;
! 227:
! 228: REQUIRE(func != NULL);
! 229:
! 230: RADIX_WALK(radix->head, node) {
! 231: func(node->prefix, node->data);
! 232: } RADIX_WALK_END;
! 233: }
! 234:
! 235:
! 236: isc_result_t
! 237: isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
! 238: isc_prefix_t *prefix)
! 239: {
! 240: isc_radix_node_t *node;
! 241: isc_radix_node_t *stack[RADIX_MAXBITS + 1];
! 242: u_char *addr;
! 243: isc_uint32_t bitlen;
! 244: int tfamily = -1;
! 245: int cnt = 0;
! 246:
! 247: REQUIRE(radix != NULL);
! 248: REQUIRE(prefix != NULL);
! 249: REQUIRE(target != NULL && *target == NULL);
! 250: RUNTIME_CHECK(prefix->bitlen <= radix->maxbits);
! 251:
! 252: *target = NULL;
! 253:
! 254: if (radix->head == NULL) {
! 255: return (ISC_R_NOTFOUND);
! 256: }
! 257:
! 258: node = radix->head;
! 259: addr = isc_prefix_touchar(prefix);
! 260: bitlen = prefix->bitlen;
! 261:
! 262: while (node->bit < bitlen) {
! 263: if (node->prefix)
! 264: stack[cnt++] = node;
! 265:
! 266: if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
! 267: node = node->r;
! 268: else
! 269: node = node->l;
! 270:
! 271: if (node == NULL)
! 272: break;
! 273: }
! 274:
! 275: if (node && node->prefix)
! 276: stack[cnt++] = node;
! 277:
! 278: while (--cnt >= 0) {
! 279: node = stack[cnt];
! 280:
! 281: if (_comp_with_mask(isc_prefix_tochar(node->prefix),
! 282: isc_prefix_tochar(prefix),
! 283: node->prefix->bitlen)) {
! 284: if (node->node_num[ISC_IS6(prefix->family)] != -1 &&
! 285: ((*target == NULL) ||
! 286: (*target)->node_num[ISC_IS6(tfamily)] >
! 287: node->node_num[ISC_IS6(prefix->family)])) {
! 288: *target = node;
! 289: tfamily = prefix->family;
! 290: }
! 291: }
! 292: }
! 293:
! 294: if (*target == NULL) {
! 295: return (ISC_R_NOTFOUND);
! 296: } else {
! 297: return (ISC_R_SUCCESS);
! 298: }
! 299: }
! 300:
! 301: isc_result_t
! 302: isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target,
! 303: isc_radix_node_t *source, isc_prefix_t *prefix)
! 304: {
! 305: isc_radix_node_t *node, *new_node, *parent, *glue = NULL;
! 306: u_char *addr, *test_addr;
! 307: isc_uint32_t bitlen, fam, check_bit, differ_bit;
! 308: isc_uint32_t i, j, r;
! 309: isc_result_t result;
! 310:
! 311: REQUIRE(radix != NULL);
! 312: REQUIRE(target != NULL && *target == NULL);
! 313: REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL));
! 314: RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits);
! 315:
! 316: if (prefix == NULL)
! 317: prefix = source->prefix;
! 318:
! 319: INSIST(prefix != NULL);
! 320:
! 321: bitlen = prefix->bitlen;
! 322: fam = prefix->family;
! 323:
! 324: if (radix->head == NULL) {
! 325: node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
! 326: if (node == NULL)
! 327: return (ISC_R_NOMEMORY);
! 328: node->bit = bitlen;
! 329: node->node_num[0] = node->node_num[1] = -1;
! 330: node->prefix = NULL;
! 331: result = _ref_prefix(radix->mctx, &node->prefix, prefix);
! 332: if (result != ISC_R_SUCCESS) {
! 333: isc_mem_put(radix->mctx, node,
! 334: sizeof(isc_radix_node_t));
! 335: return (result);
! 336: }
! 337: node->parent = NULL;
! 338: node->l = node->r = NULL;
! 339: if (source != NULL) {
! 340: /*
! 341: * If source is non-NULL, then we're merging in a
! 342: * node from an existing radix tree. To keep
! 343: * the node_num values consistent, the calling
! 344: * function will add the total number of nodes
! 345: * added to num_added_node at the end of
! 346: * the merge operation--we don't do it here.
! 347: */
! 348: if (source->node_num[0] != -1)
! 349: node->node_num[0] = radix->num_added_node +
! 350: source->node_num[0];
! 351: if (source->node_num[1] != -1)
! 352: node->node_num[1] = radix->num_added_node +
! 353: source->node_num[1];
! 354: node->data[0] = source->data[0];
! 355: node->data[1] = source->data[1];
! 356: } else {
! 357: if (fam == AF_UNSPEC) {
! 358: /* "any" or "none" */
! 359: node->node_num[0] = node->node_num[1] =
! 360: ++radix->num_added_node;
! 361: } else {
! 362: node->node_num[ISC_IS6(fam)] =
! 363: ++radix->num_added_node;
! 364: }
! 365: node->data[0] = NULL;
! 366: node->data[1] = NULL;
! 367: }
! 368: radix->head = node;
! 369: radix->num_active_node++;
! 370: *target = node;
! 371: return (ISC_R_SUCCESS);
! 372: }
! 373:
! 374: addr = isc_prefix_touchar(prefix);
! 375: node = radix->head;
! 376:
! 377: while (node->bit < bitlen || node->prefix == NULL) {
! 378: if (node->bit < radix->maxbits &&
! 379: BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
! 380: {
! 381: if (node->r == NULL)
! 382: break;
! 383: node = node->r;
! 384: } else {
! 385: if (node->l == NULL)
! 386: break;
! 387: node = node->l;
! 388: }
! 389:
! 390: INSIST(node != NULL);
! 391: }
! 392:
! 393: INSIST(node->prefix != NULL);
! 394:
! 395: test_addr = isc_prefix_touchar(node->prefix);
! 396: /* Find the first bit different. */
! 397: check_bit = (node->bit < bitlen) ? node->bit : bitlen;
! 398: differ_bit = 0;
! 399: for (i = 0; i*8 < check_bit; i++) {
! 400: if ((r = (addr[i] ^ test_addr[i])) == 0) {
! 401: differ_bit = (i + 1) * 8;
! 402: continue;
! 403: }
! 404: /* I know the better way, but for now. */
! 405: for (j = 0; j < 8; j++) {
! 406: if (BIT_TEST (r, (0x80 >> j)))
! 407: break;
! 408: }
! 409: /* Must be found. */
! 410: INSIST(j < 8);
! 411: differ_bit = i * 8 + j;
! 412: break;
! 413: }
! 414:
! 415: if (differ_bit > check_bit)
! 416: differ_bit = check_bit;
! 417:
! 418: parent = node->parent;
! 419: while (parent != NULL && parent->bit >= differ_bit) {
! 420: node = parent;
! 421: parent = node->parent;
! 422: }
! 423:
! 424: if (differ_bit == bitlen && node->bit == bitlen) {
! 425: if (node->prefix != NULL) {
! 426: /* Set node_num only if it hasn't been set before */
! 427: if (source != NULL) {
! 428: /* Merging node */
! 429: if (node->node_num[0] == -1 &&
! 430: source->node_num[0] != -1) {
! 431: node->node_num[0] =
! 432: radix->num_added_node +
! 433: source->node_num[0];
! 434: node->data[0] = source->data[0];
! 435: }
! 436: if (node->node_num[1] == -1 &&
! 437: source->node_num[0] != -1) {
! 438: node->node_num[1] =
! 439: radix->num_added_node +
! 440: source->node_num[1];
! 441: node->data[1] = source->data[1];
! 442: }
! 443: } else {
! 444: if (fam == AF_UNSPEC) {
! 445: /* "any" or "none" */
! 446: int next = radix->num_added_node + 1;
! 447: if (node->node_num[0] == -1) {
! 448: node->node_num[0] = next;
! 449: radix->num_added_node = next;
! 450: }
! 451: if (node->node_num[1] == -1) {
! 452: node->node_num[1] = next;
! 453: radix->num_added_node = next;
! 454: }
! 455: } else {
! 456: if (node->node_num[ISC_IS6(fam)] == -1)
! 457: node->node_num[ISC_IS6(fam)]
! 458: = ++radix->num_added_node;
! 459: }
! 460: }
! 461: *target = node;
! 462: return (ISC_R_SUCCESS);
! 463: } else {
! 464: result =
! 465: _ref_prefix(radix->mctx, &node->prefix, prefix);
! 466: if (result != ISC_R_SUCCESS)
! 467: return (result);
! 468: }
! 469: INSIST(node->data[0] == NULL && node->node_num[0] == -1 &&
! 470: node->data[1] == NULL && node->node_num[1] == -1);
! 471: if (source != NULL) {
! 472: /* Merging node */
! 473: if (source->node_num[0] != -1) {
! 474: node->node_num[0] = radix->num_added_node +
! 475: source->node_num[0];
! 476: node->data[0] = source->data[0];
! 477: }
! 478: if (source->node_num[1] != -1) {
! 479: node->node_num[1] = radix->num_added_node +
! 480: source->node_num[1];
! 481: node->data[1] = source->data[1];
! 482: }
! 483: } else {
! 484: if (fam == AF_UNSPEC) {
! 485: /* "any" or "none" */
! 486: node->node_num[0] = node->node_num[1] =
! 487: ++radix->num_added_node;
! 488: } else {
! 489: node->node_num[ISC_IS6(fam)] =
! 490: ++radix->num_added_node;
! 491: }
! 492: }
! 493: *target = node;
! 494: return (ISC_R_SUCCESS);
! 495: }
! 496:
! 497: new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
! 498: if (new_node == NULL)
! 499: return (ISC_R_NOMEMORY);
! 500: if (node->bit != differ_bit && bitlen != differ_bit) {
! 501: glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
! 502: if (glue == NULL) {
! 503: isc_mem_put(radix->mctx, new_node,
! 504: sizeof(isc_radix_node_t));
! 505: return (ISC_R_NOMEMORY);
! 506: }
! 507: }
! 508: new_node->bit = bitlen;
! 509: new_node->prefix = NULL;
! 510: result = _ref_prefix(radix->mctx, &new_node->prefix, prefix);
! 511: if (result != ISC_R_SUCCESS) {
! 512: isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t));
! 513: if (glue != NULL)
! 514: isc_mem_put(radix->mctx, glue,
! 515: sizeof(isc_radix_node_t));
! 516: return (result);
! 517: }
! 518: new_node->parent = NULL;
! 519: new_node->l = new_node->r = NULL;
! 520: new_node->node_num[0] = new_node->node_num[1] = -1;
! 521: radix->num_active_node++;
! 522:
! 523: if (source != NULL) {
! 524: /* Merging node */
! 525: if (source->node_num[0] != -1)
! 526: new_node->node_num[0] = radix->num_added_node +
! 527: source->node_num[0];
! 528: if (source->node_num[1] != -1)
! 529: new_node->node_num[1] = radix->num_added_node +
! 530: source->node_num[1];
! 531: new_node->data[0] = source->data[0];
! 532: new_node->data[1] = source->data[1];
! 533: } else {
! 534: if (fam == AF_UNSPEC) {
! 535: /* "any" or "none" */
! 536: new_node->node_num[0] = new_node->node_num[1] =
! 537: ++radix->num_added_node;
! 538: } else {
! 539: new_node->node_num[ISC_IS6(fam)] =
! 540: ++radix->num_added_node;
! 541: }
! 542: new_node->data[0] = NULL;
! 543: new_node->data[1] = NULL;
! 544: }
! 545:
! 546: if (node->bit == differ_bit) {
! 547: INSIST(glue == NULL);
! 548: new_node->parent = node;
! 549: if (node->bit < radix->maxbits &&
! 550: BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
! 551: {
! 552: INSIST(node->r == NULL);
! 553: node->r = new_node;
! 554: } else {
! 555: INSIST(node->l == NULL);
! 556: node->l = new_node;
! 557: }
! 558: *target = new_node;
! 559: return (ISC_R_SUCCESS);
! 560: }
! 561:
! 562: if (bitlen == differ_bit) {
! 563: INSIST(glue == NULL);
! 564: if (bitlen < radix->maxbits &&
! 565: BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) {
! 566: new_node->r = node;
! 567: } else {
! 568: new_node->l = node;
! 569: }
! 570: new_node->parent = node->parent;
! 571: if (node->parent == NULL) {
! 572: INSIST(radix->head == node);
! 573: radix->head = new_node;
! 574: } else if (node->parent->r == node) {
! 575: node->parent->r = new_node;
! 576: } else {
! 577: node->parent->l = new_node;
! 578: }
! 579: node->parent = new_node;
! 580: } else {
! 581: INSIST(glue != NULL);
! 582: glue->bit = differ_bit;
! 583: glue->prefix = NULL;
! 584: glue->parent = node->parent;
! 585: glue->data[0] = glue->data[1] = NULL;
! 586: glue->node_num[0] = glue->node_num[1] = -1;
! 587: radix->num_active_node++;
! 588: if (differ_bit < radix->maxbits &&
! 589: BIT_TEST(addr[differ_bit>>3], 0x80 >> (differ_bit & 07))) {
! 590: glue->r = new_node;
! 591: glue->l = node;
! 592: } else {
! 593: glue->r = node;
! 594: glue->l = new_node;
! 595: }
! 596: new_node->parent = glue;
! 597:
! 598: if (node->parent == NULL) {
! 599: INSIST(radix->head == node);
! 600: radix->head = glue;
! 601: } else if (node->parent->r == node) {
! 602: node->parent->r = glue;
! 603: } else {
! 604: node->parent->l = glue;
! 605: }
! 606: node->parent = glue;
! 607: }
! 608:
! 609: *target = new_node;
! 610: return (ISC_R_SUCCESS);
! 611: }
! 612:
! 613: void
! 614: isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) {
! 615: isc_radix_node_t *parent, *child;
! 616:
! 617: REQUIRE(radix != NULL);
! 618: REQUIRE(node != NULL);
! 619:
! 620: if (node->r && node->l) {
! 621: /*
! 622: * This might be a placeholder node -- have to check and
! 623: * make sure there is a prefix associated with it!
! 624: */
! 625: if (node->prefix != NULL)
! 626: _deref_prefix(radix->mctx, node->prefix);
! 627:
! 628: node->prefix = NULL;
! 629: node->data[0] = node->data[1] = NULL;
! 630: return;
! 631: }
! 632:
! 633: if (node->r == NULL && node->l == NULL) {
! 634: parent = node->parent;
! 635: _deref_prefix(radix->mctx, node->prefix);
! 636: isc_mem_put(radix->mctx, node, sizeof(*node));
! 637: radix->num_active_node--;
! 638:
! 639: if (parent == NULL) {
! 640: INSIST(radix->head == node);
! 641: radix->head = NULL;
! 642: return;
! 643: }
! 644:
! 645: if (parent->r == node) {
! 646: parent->r = NULL;
! 647: child = parent->l;
! 648: } else {
! 649: INSIST(parent->l == node);
! 650: parent->l = NULL;
! 651: child = parent->r;
! 652: }
! 653:
! 654: if (parent->prefix)
! 655: return;
! 656:
! 657: /* We need to remove parent too. */
! 658:
! 659: if (parent->parent == NULL) {
! 660: INSIST(radix->head == parent);
! 661: radix->head = child;
! 662: } else if (parent->parent->r == parent) {
! 663: parent->parent->r = child;
! 664: } else {
! 665: INSIST(parent->parent->l == parent);
! 666: parent->parent->l = child;
! 667: }
! 668: child->parent = parent->parent;
! 669: isc_mem_put(radix->mctx, parent, sizeof(*parent));
! 670: radix->num_active_node--;
! 671: return;
! 672: }
! 673:
! 674: if (node->r) {
! 675: child = node->r;
! 676: } else {
! 677: INSIST(node->l != NULL);
! 678: child = node->l;
! 679: }
! 680: parent = node->parent;
! 681: child->parent = parent;
! 682:
! 683: _deref_prefix(radix->mctx, node->prefix);
! 684: isc_mem_put(radix->mctx, node, sizeof(*node));
! 685: radix->num_active_node--;
! 686:
! 687: if (parent == NULL) {
! 688: INSIST(radix->head == node);
! 689: radix->head = child;
! 690: return;
! 691: }
! 692:
! 693: if (parent->r == node) {
! 694: parent->r = child;
! 695: } else {
! 696: INSIST(parent->l == node);
! 697: parent->l = child;
! 698: }
! 699: }
! 700:
! 701: /*
! 702: Local Variables:
! 703: c-basic-offset: 4
! 704: indent-tabs-mode: t
! 705: End:
! 706: */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to radix.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / ntp / lib / isc