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