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