radix.c revision 1.1
1 /* $NetBSD: radix.c,v 1.1 2018/08/12 12:08:24 christos Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * This Source Code Form is subject to the terms of the Mozilla Public 7 * License, v. 2.0. If a copy of the MPL was not distributed with this 8 * file, You can obtain one at http://mozilla.org/MPL/2.0/. 9 * 10 * See the COPYRIGHT file distributed with this work for additional 11 * information regarding copyright ownership. 12 */ 13 14 15 /* 16 * This source was adapted from MRT's RCS Ids: 17 * Id: radix.c,v 1.10.2.1 1999/11/29 05:16:24 masaki Exp 18 * Id: prefix.c,v 1.37.2.9 2000/03/10 02:53:19 labovit Exp 19 */ 20 21 #include <config.h> 22 23 #include <isc/mem.h> 24 #include <isc/types.h> 25 #include <isc/util.h> 26 #include <isc/radix.h> 27 28 static isc_result_t 29 _new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, 30 void *dest, int bitlen); 31 32 static void 33 _deref_prefix(isc_prefix_t *prefix); 34 35 static isc_result_t 36 _ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix); 37 38 static int 39 _comp_with_mask(void *addr, void *dest, u_int mask); 40 41 static void 42 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func); 43 44 static isc_result_t 45 _new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest, 46 int bitlen) 47 { 48 isc_prefix_t *prefix; 49 50 REQUIRE(target != NULL); 51 52 if (family != AF_INET6 && family != AF_INET && family != AF_UNSPEC) 53 return (ISC_R_NOTIMPLEMENTED); 54 55 prefix = isc_mem_get(mctx, sizeof(isc_prefix_t)); 56 if (prefix == NULL) 57 return (ISC_R_NOMEMORY); 58 59 if (family == AF_INET6) { 60 prefix->bitlen = (bitlen >= 0) ? bitlen : 128; 61 memmove(&prefix->add.sin6, dest, 16); 62 } else { 63 /* AF_UNSPEC is "any" or "none"--treat it as AF_INET */ 64 prefix->bitlen = (bitlen >= 0) ? bitlen : 32; 65 memmove(&prefix->add.sin, dest, 4); 66 } 67 68 prefix->family = family; 69 prefix->ecs = ISC_FALSE; 70 prefix->mctx = NULL; 71 isc_mem_attach(mctx, &prefix->mctx); 72 73 isc_refcount_init(&prefix->refcount, 1); 74 75 *target = prefix; 76 return (ISC_R_SUCCESS); 77 } 78 79 static void 80 _deref_prefix(isc_prefix_t *prefix) { 81 int refs; 82 83 if (prefix == NULL) 84 return; 85 86 isc_refcount_decrement(&prefix->refcount, &refs); 87 88 if (refs <= 0) { 89 isc_refcount_destroy(&prefix->refcount); 90 isc_mem_putanddetach(&prefix->mctx, prefix, 91 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 u_int n = mask / 8; 130 u_int m = ((~0U) << (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 = NULL; 150 isc_mem_attach(mctx, &radix->mctx); 151 radix->maxbits = maxbits; 152 radix->head = NULL; 153 radix->num_active_node = 0; 154 radix->num_added_node = 0; 155 RUNTIME_CHECK(maxbits <= RADIX_MAXBITS); /* XXX */ 156 radix->magic = RADIX_TREE_MAGIC; 157 *target = radix; 158 return (ISC_R_SUCCESS); 159 } 160 161 /* 162 * if func is supplied, it will be called as func(node->data) 163 * before deleting the node 164 */ 165 166 static void 167 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) { 168 REQUIRE(radix != NULL); 169 170 if (radix->head != NULL) { 171 isc_radix_node_t *Xstack[RADIX_MAXBITS+1]; 172 isc_radix_node_t **Xsp = Xstack; 173 isc_radix_node_t *Xrn = radix->head; 174 175 while (Xrn != NULL) { 176 isc_radix_node_t *l = Xrn->l; 177 isc_radix_node_t *r = Xrn->r; 178 179 if (Xrn->prefix != NULL) { 180 _deref_prefix(Xrn->prefix); 181 if (func != NULL) 182 func(Xrn->data); 183 } else { 184 INSIST(Xrn->data[RADIX_V4] == NULL && 185 Xrn->data[RADIX_V6] == NULL && 186 Xrn->data[RADIX_V4_ECS] == NULL && 187 Xrn->data[RADIX_V6_ECS] == 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 REQUIRE(radix != NULL); 214 _clear_radix(radix, func); 215 isc_mem_putanddetach(&radix->mctx, radix, sizeof(*radix)); 216 } 217 218 219 /* 220 * func will be called as func(node->prefix, node->data) 221 */ 222 void 223 isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func) { 224 isc_radix_node_t *node; 225 226 REQUIRE(func != NULL); 227 228 RADIX_WALK(radix->head, node) { 229 func(node->prefix, node->data); 230 } RADIX_WALK_END; 231 } 232 233 234 isc_result_t 235 isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target, 236 isc_prefix_t *prefix) 237 { 238 isc_radix_node_t *node; 239 isc_radix_node_t *stack[RADIX_MAXBITS + 1]; 240 u_char *addr; 241 isc_uint32_t bitlen; 242 int tfam = -1, cnt = 0; 243 244 REQUIRE(radix != NULL); 245 REQUIRE(prefix != NULL); 246 REQUIRE(target != NULL && *target == NULL); 247 RUNTIME_CHECK(prefix->bitlen <= radix->maxbits); 248 249 *target = NULL; 250 251 if (radix->head == NULL) { 252 return (ISC_R_NOTFOUND); 253 } 254 255 node = radix->head; 256 addr = isc_prefix_touchar(prefix); 257 bitlen = prefix->bitlen; 258 259 while (node->bit < bitlen) { 260 if (node->prefix) 261 stack[cnt++] = node; 262 263 if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) 264 node = node->r; 265 else 266 node = node->l; 267 268 if (node == NULL) 269 break; 270 } 271 272 if (node && node->prefix) 273 stack[cnt++] = node; 274 275 while (cnt-- > 0) { 276 node = stack[cnt]; 277 278 if (prefix->bitlen < node->bit) 279 continue; 280 281 if (_comp_with_mask(isc_prefix_tochar(node->prefix), 282 isc_prefix_tochar(prefix), 283 node->prefix->bitlen)) 284 { 285 int fam = ISC_RADIX_FAMILY(prefix); 286 if (node->node_num[fam] != -1 && 287 ((*target == NULL) || 288 (*target)->node_num[tfam] > node->node_num[fam])) 289 { 290 *target = node; 291 tfam = fam; 292 } 293 } 294 } 295 296 if (*target == NULL) { 297 return (ISC_R_NOTFOUND); 298 } else { 299 return (ISC_R_SUCCESS); 300 } 301 } 302 303 isc_result_t 304 isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target, 305 isc_radix_node_t *source, isc_prefix_t *prefix) 306 { 307 isc_radix_node_t *node, *new_node, *parent, *glue = NULL; 308 u_char *addr, *test_addr; 309 isc_uint32_t bitlen, fam, check_bit, differ_bit; 310 isc_uint32_t i, j, r; 311 isc_result_t result; 312 313 REQUIRE(radix != NULL); 314 REQUIRE(target != NULL && *target == NULL); 315 REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL)); 316 RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits); 317 318 if (prefix == NULL) 319 prefix = source->prefix; 320 321 INSIST(prefix != NULL); 322 323 bitlen = prefix->bitlen; 324 fam = prefix->family; 325 326 if (radix->head == NULL) { 327 node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); 328 if (node == NULL) 329 return (ISC_R_NOMEMORY); 330 node->bit = bitlen; 331 for (i = 0; i < RADIX_FAMILIES; i++) { 332 node->node_num[i] = -1; 333 } 334 node->prefix = NULL; 335 result = _ref_prefix(radix->mctx, &node->prefix, prefix); 336 if (result != ISC_R_SUCCESS) { 337 isc_mem_put(radix->mctx, node, 338 sizeof(isc_radix_node_t)); 339 return (result); 340 } 341 node->parent = NULL; 342 node->l = node->r = NULL; 343 if (source != NULL) { 344 /* 345 * If source is non-NULL, then we're merging in a 346 * node from an existing radix tree. To keep 347 * the node_num values consistent, the calling 348 * function will add the total number of nodes 349 * added to num_added_node at the end of 350 * the merge operation--we don't do it here. 351 */ 352 for (i = 0; i < RADIX_FAMILIES; i++) { 353 if (source->node_num[i] != -1) { 354 node->node_num[i] = 355 radix->num_added_node + 356 source->node_num[i]; 357 } 358 node->data[i] = source->data[i]; 359 } 360 } else { 361 int next = ++radix->num_added_node; 362 if (fam == AF_UNSPEC) { 363 /* "any" or "none" */ 364 for (i = 0; i < RADIX_FAMILIES; i++) { 365 node->node_num[i] = next; 366 } 367 } else { 368 node->node_num[ISC_RADIX_FAMILY(prefix)] = next; 369 } 370 371 memset(node->data, 0, sizeof(node->data)); 372 } 373 radix->head = node; 374 radix->num_active_node++; 375 *target = node; 376 return (ISC_R_SUCCESS); 377 } 378 379 addr = isc_prefix_touchar(prefix); 380 node = radix->head; 381 382 while (node->bit < bitlen || node->prefix == NULL) { 383 if (node->bit < radix->maxbits && 384 BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) 385 { 386 if (node->r == NULL) 387 break; 388 node = node->r; 389 } else { 390 if (node->l == NULL) 391 break; 392 node = node->l; 393 } 394 395 INSIST(node != NULL); 396 } 397 398 INSIST(node->prefix != NULL); 399 400 test_addr = isc_prefix_touchar(node->prefix); 401 /* Find the first bit different. */ 402 check_bit = (node->bit < bitlen) ? node->bit : bitlen; 403 differ_bit = 0; 404 for (i = 0; i * 8 < check_bit; i++) { 405 if ((r = (addr[i] ^ test_addr[i])) == 0) { 406 differ_bit = (i + 1) * 8; 407 continue; 408 } 409 /* I know the better way, but for now. */ 410 for (j = 0; j < 8; j++) { 411 if (BIT_TEST(r, (0x80 >> j))) 412 break; 413 } 414 /* Must be found. */ 415 INSIST(j < 8); 416 differ_bit = i * 8 + j; 417 break; 418 } 419 420 if (differ_bit > check_bit) 421 differ_bit = check_bit; 422 423 parent = node->parent; 424 while (parent != NULL && parent->bit >= differ_bit) { 425 node = parent; 426 parent = node->parent; 427 } 428 429 if (differ_bit == bitlen && node->bit == bitlen) { 430 if (node->prefix != NULL) { 431 /* Set node_num only if it hasn't been set before */ 432 if (source != NULL) { 433 /* Merging nodes */ 434 for (i = 0; i < RADIX_FAMILIES; i++) { 435 if (node->node_num[i] == -1 && 436 source->node_num[i] != -1) { 437 node->node_num[i] = 438 radix->num_added_node + 439 source->node_num[i]; 440 node->data[i] = source->data[i]; 441 } 442 } 443 } else { 444 if (fam == AF_UNSPEC) { 445 /* "any" or "none" */ 446 int next = radix->num_added_node + 1; 447 for (i = 0; i < RADIX_FAMILIES; i++) { 448 if (node->node_num[i] == -1) { 449 node->node_num[i] = 450 next; 451 radix->num_added_node = 452 next; 453 } 454 } 455 } else { 456 int foff = ISC_RADIX_FAMILY(prefix); 457 if (node->node_num[foff] == -1) { 458 node->node_num[foff] = 459 ++radix->num_added_node; 460 } 461 } 462 } 463 *target = node; 464 return (ISC_R_SUCCESS); 465 } else { 466 result = _ref_prefix(radix->mctx, 467 &node->prefix, prefix); 468 if (result != ISC_R_SUCCESS) 469 return (result); 470 } 471 472 /* Check everything is null and empty before we proceed */ 473 INSIST(node->data[RADIX_V4] == NULL && 474 node->node_num[RADIX_V4] == -1 && 475 node->data[RADIX_V6] == NULL && 476 node->node_num[RADIX_V6] == -1 && 477 node->data[RADIX_V4_ECS] == NULL && 478 node->node_num[RADIX_V4_ECS] == -1 && 479 node->data[RADIX_V6_ECS] == NULL && 480 node->node_num[RADIX_V6_ECS] == -1); 481 482 if (source != NULL) { 483 /* Merging node */ 484 for (i = 0; i < RADIX_FAMILIES; i++) { 485 int cur = radix->num_added_node; 486 if (source->node_num[i] != -1) { 487 node->node_num[i] = 488 source->node_num[i] + cur; 489 node->data[i] = source->data[i]; 490 } 491 } 492 } else { 493 int next = ++radix->num_added_node; 494 if (fam == AF_UNSPEC) { 495 /* "any" or "none" */ 496 for (i = 0; i < RADIX_FAMILIES; i++) { 497 node->node_num[i] = next; 498 } 499 } else { 500 node->node_num[ISC_RADIX_FAMILY(prefix)] = next; 501 } 502 } 503 *target = node; 504 return (ISC_R_SUCCESS); 505 } 506 507 new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); 508 if (new_node == NULL) 509 return (ISC_R_NOMEMORY); 510 if (node->bit != differ_bit && bitlen != differ_bit) { 511 glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); 512 if (glue == NULL) { 513 isc_mem_put(radix->mctx, new_node, 514 sizeof(isc_radix_node_t)); 515 return (ISC_R_NOMEMORY); 516 } 517 } 518 new_node->bit = bitlen; 519 new_node->prefix = NULL; 520 result = _ref_prefix(radix->mctx, &new_node->prefix, prefix); 521 if (result != ISC_R_SUCCESS) { 522 isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t)); 523 if (glue != NULL) 524 isc_mem_put(radix->mctx, glue, 525 sizeof(isc_radix_node_t)); 526 return (result); 527 } 528 new_node->parent = NULL; 529 new_node->l = new_node->r = NULL; 530 for (i = 0; i < RADIX_FAMILIES; i++) { 531 new_node->node_num[i] = -1; 532 new_node->data[i] = NULL; 533 } 534 radix->num_active_node++; 535 536 if (source != NULL) { 537 /* Merging node */ 538 for (i = 0; i < RADIX_FAMILIES; i++) { 539 int cur = radix->num_added_node; 540 if (source->node_num[i] != -1) { 541 new_node->node_num[i] = 542 source->node_num[i] + cur; 543 new_node->data[i] = source->data[i]; 544 } 545 } 546 } else { 547 int next = ++radix->num_added_node; 548 if (fam == AF_UNSPEC) { 549 /* "any" or "none" */ 550 for (i = 0; i < RADIX_FAMILIES; i++) { 551 new_node->node_num[i] = next; 552 } 553 } else { 554 new_node->node_num[ISC_RADIX_FAMILY(prefix)] = next; 555 } 556 memset(new_node->data, 0, sizeof(new_node->data)); 557 } 558 559 if (node->bit == differ_bit) { 560 INSIST(glue == NULL); 561 new_node->parent = node; 562 if (node->bit < radix->maxbits && 563 BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) 564 { 565 INSIST(node->r == NULL); 566 node->r = new_node; 567 } else { 568 INSIST(node->l == NULL); 569 node->l = new_node; 570 } 571 *target = new_node; 572 return (ISC_R_SUCCESS); 573 } 574 575 if (bitlen == differ_bit) { 576 INSIST(glue == NULL); 577 if (bitlen < radix->maxbits && 578 BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) { 579 new_node->r = node; 580 } else { 581 new_node->l = node; 582 } 583 new_node->parent = node->parent; 584 if (node->parent == NULL) { 585 INSIST(radix->head == node); 586 radix->head = new_node; 587 } else if (node->parent->r == node) { 588 node->parent->r = new_node; 589 } else { 590 node->parent->l = new_node; 591 } 592 node->parent = new_node; 593 } else { 594 INSIST(glue != NULL); 595 glue->bit = differ_bit; 596 glue->prefix = NULL; 597 glue->parent = node->parent; 598 for (i = 0; i < RADIX_FAMILIES; i++) { 599 glue->data[i] = NULL; 600 glue->node_num[i] = -1; 601 } 602 radix->num_active_node++; 603 if (differ_bit < radix->maxbits && 604 BIT_TEST(addr[differ_bit>>3], 0x80 >> (differ_bit & 07))) { 605 glue->r = new_node; 606 glue->l = node; 607 } else { 608 glue->r = node; 609 glue->l = new_node; 610 } 611 new_node->parent = glue; 612 613 if (node->parent == NULL) { 614 INSIST(radix->head == node); 615 radix->head = glue; 616 } else if (node->parent->r == node) { 617 node->parent->r = glue; 618 } else { 619 node->parent->l = glue; 620 } 621 node->parent = glue; 622 } 623 624 *target = new_node; 625 return (ISC_R_SUCCESS); 626 } 627 628 void 629 isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) { 630 isc_radix_node_t *parent, *child; 631 632 REQUIRE(radix != NULL); 633 REQUIRE(node != NULL); 634 635 if (node->r && node->l) { 636 /* 637 * This might be a placeholder node -- have to check and 638 * make sure there is a prefix associated with it! 639 */ 640 if (node->prefix != NULL) 641 _deref_prefix(node->prefix); 642 643 node->prefix = NULL; 644 memset(node->data, 0, sizeof(node->data)); 645 return; 646 } 647 648 if (node->r == NULL && node->l == NULL) { 649 parent = node->parent; 650 _deref_prefix(node->prefix); 651 652 if (parent == NULL) { 653 INSIST(radix->head == node); 654 radix->head = NULL; 655 isc_mem_put(radix->mctx, node, sizeof(*node)); 656 radix->num_active_node--; 657 return; 658 } 659 660 if (parent->r == node) { 661 parent->r = NULL; 662 child = parent->l; 663 } else { 664 INSIST(parent->l == node); 665 parent->l = NULL; 666 child = parent->r; 667 } 668 669 isc_mem_put(radix->mctx, node, sizeof(*node)); 670 radix->num_active_node--; 671 672 if (parent->prefix) 673 return; 674 675 /* We need to remove parent too. */ 676 if (parent->parent == NULL) { 677 INSIST(radix->head == parent); 678 radix->head = child; 679 } else if (parent->parent->r == parent) { 680 parent->parent->r = child; 681 } else { 682 INSIST(parent->parent->l == parent); 683 parent->parent->l = child; 684 } 685 686 child->parent = parent->parent; 687 isc_mem_put(radix->mctx, parent, sizeof(*parent)); 688 radix->num_active_node--; 689 return; 690 } 691 692 if (node->r) { 693 child = node->r; 694 } else { 695 INSIST(node->l != NULL); 696 child = node->l; 697 } 698 699 parent = node->parent; 700 child->parent = parent; 701 702 _deref_prefix(node->prefix); 703 704 if (parent == NULL) { 705 INSIST(radix->head == node); 706 radix->head = child; 707 isc_mem_put(radix->mctx, node, sizeof(*node)); 708 radix->num_active_node--; 709 return; 710 } 711 712 isc_mem_put(radix->mctx, node, sizeof(*node)); 713 radix->num_active_node--; 714 715 if (parent->r == node) { 716 parent->r = child; 717 } else { 718 INSIST(parent->l == node); 719 parent->l = child; 720 } 721 } 722 723 /* 724 Local Variables: 725 c-basic-offset: 4 726 indent-tabs-mode: t 727 End: 728 */ 729
Indexes created Mon Mar 02 05:31:46 UTC 2026