radix.c revision 290001
1/* 2 * Copyright (C) 2007-2009, 2011, 2012 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$ */ 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 32static isc_result_t 33_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, 34 void *dest, int bitlen); 35 36static void 37_deref_prefix(isc_mem_t *mctx, isc_prefix_t *prefix); 38 39static isc_result_t 40_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix); 41 42static int 43_comp_with_mask(void *addr, void *dest, u_int mask); 44 45static void 46_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func); 47 48static 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 80static 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 95static 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 121static 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 139isc_result_t 140isc_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 165static 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 211void 212isc_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 */ 223void 224isc_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 236isc_result_t 237isc_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 301isc_result_t 302isc_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 613void 614isc_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/* 702Local Variables: 703c-basic-offset: 4 704indent-tabs-mode: t 705End: 706*/ 707