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