radix.c revision 1.1.2.2
1 /* $NetBSD: radix.c,v 1.1.2.2 2024/02/24 13:07:21 martin 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 isc_result_t 137 isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits) { 138 isc_radix_tree_t *radix; 139 140 REQUIRE(target != NULL && *target == NULL); 141 142 radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t)); 143 144 radix->mctx = NULL; 145 isc_mem_attach(mctx, &radix->mctx); 146 radix->maxbits = maxbits; 147 radix->head = NULL; 148 radix->num_active_node = 0; 149 radix->num_added_node = 0; 150 RUNTIME_CHECK(maxbits <= RADIX_MAXBITS); /* XXX */ 151 radix->magic = RADIX_TREE_MAGIC; 152 *target = radix; 153 return (ISC_R_SUCCESS); 154 } 155 156 /* 157 * if func is supplied, it will be called as func(node->data) 158 * before deleting the node 159 */ 160 161 static void 162 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) { 163 REQUIRE(radix != NULL); 164 165 if (radix->head != NULL) { 166 isc_radix_node_t *Xstack[RADIX_MAXBITS + 1]; 167 isc_radix_node_t **Xsp = Xstack; 168 isc_radix_node_t *Xrn = radix->head; 169 170 while (Xrn != NULL) { 171 isc_radix_node_t *l = Xrn->l; 172 isc_radix_node_t *r = Xrn->r; 173 174 if (Xrn->prefix != NULL) { 175 _deref_prefix(Xrn->prefix); 176 if (func != NULL) { 177 func(Xrn->data); 178 } 179 } else { 180 INSIST(Xrn->data[RADIX_V4] == NULL && 181 Xrn->data[RADIX_V6] == NULL); 182 } 183 184 isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn)); 185 radix->num_active_node--; 186 187 if (l != NULL) { 188 if (r != NULL) { 189 *Xsp++ = r; 190 } 191 Xrn = l; 192 } else if (r != NULL) { 193 Xrn = r; 194 } else if (Xsp != Xstack) { 195 Xrn = *(--Xsp); 196 } else { 197 Xrn = NULL; 198 } 199 } 200 } 201 RUNTIME_CHECK(radix->num_active_node == 0); 202 } 203 204 void 205 isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) { 206 REQUIRE(radix != NULL); 207 _clear_radix(radix, func); 208 isc_mem_putanddetach(&radix->mctx, radix, sizeof(*radix)); 209 } 210 211 /* 212 * func will be called as func(node->prefix, node->data) 213 */ 214 void 215 isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func) { 216 isc_radix_node_t *node; 217 218 REQUIRE(func != NULL); 219 220 RADIX_WALK(radix->head, node) { func(node->prefix, node->data); } 221 RADIX_WALK_END; 222 } 223 224 isc_result_t 225 isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target, 226 isc_prefix_t *prefix) { 227 isc_radix_node_t *node; 228 isc_radix_node_t *stack[RADIX_MAXBITS + 1]; 229 u_char *addr; 230 uint32_t bitlen; 231 int tfam = -1, cnt = 0; 232 233 REQUIRE(radix != NULL); 234 REQUIRE(prefix != NULL); 235 REQUIRE(target != NULL && *target == NULL); 236 RUNTIME_CHECK(prefix->bitlen <= radix->maxbits); 237 238 *target = NULL; 239 240 node = radix->head; 241 242 if (node == NULL) { 243 return (ISC_R_NOTFOUND); 244 } 245 246 addr = isc_prefix_touchar(prefix); 247 bitlen = prefix->bitlen; 248 249 while (node != NULL && node->bit < bitlen) { 250 if (node->prefix) { 251 stack[cnt++] = node; 252 } 253 254 if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) 255 { 256 node = node->r; 257 } else { 258 node = node->l; 259 } 260 } 261 262 if (node != NULL && node->prefix) { 263 stack[cnt++] = node; 264 } 265 266 while (cnt-- > 0) { 267 node = stack[cnt]; 268 269 if (prefix->bitlen < node->bit) { 270 continue; 271 } 272 273 if (_comp_with_mask(isc_prefix_tochar(node->prefix), 274 isc_prefix_tochar(prefix), 275 node->prefix->bitlen)) 276 { 277 int fam = ISC_RADIX_FAMILY(prefix); 278 if (node->node_num[fam] != -1 && 279 ((*target == NULL) || 280 (*target)->node_num[tfam] > node->node_num[fam])) 281 { 282 *target = node; 283 tfam = fam; 284 } 285 } 286 } 287 288 if (*target == NULL) { 289 return (ISC_R_NOTFOUND); 290 } else { 291 return (ISC_R_SUCCESS); 292 } 293 } 294 295 isc_result_t 296 isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target, 297 isc_radix_node_t *source, isc_prefix_t *prefix) { 298 isc_radix_node_t *node, *new_node, *parent, *glue = NULL; 299 u_char *addr, *test_addr; 300 uint32_t bitlen, fam, check_bit, differ_bit; 301 uint32_t i, j, r; 302 isc_result_t result; 303 304 REQUIRE(radix != NULL); 305 REQUIRE(target != NULL && *target == NULL); 306 REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL)); 307 RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits); 308 309 if (prefix == NULL) { 310 prefix = source->prefix; 311 } 312 313 INSIST(prefix != NULL); 314 315 bitlen = prefix->bitlen; 316 fam = prefix->family; 317 318 if (radix->head == NULL) { 319 node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); 320 node->bit = bitlen; 321 for (i = 0; i < RADIX_FAMILIES; i++) { 322 node->node_num[i] = -1; 323 } 324 node->prefix = NULL; 325 result = _ref_prefix(radix->mctx, &node->prefix, prefix); 326 if (result != ISC_R_SUCCESS) { 327 isc_mem_put(radix->mctx, node, 328 sizeof(isc_radix_node_t)); 329 return (result); 330 } 331 node->parent = NULL; 332 node->l = node->r = NULL; 333 if (source != NULL) { 334 /* 335 * If source is non-NULL, then we're merging in a 336 * node from an existing radix tree. To keep 337 * the node_num values consistent, the calling 338 * function will add the total number of nodes 339 * added to num_added_node at the end of 340 * the merge operation--we don't do it here. 341 */ 342 for (i = 0; i < RADIX_FAMILIES; i++) { 343 if (source->node_num[i] != -1) { 344 node->node_num[i] = 345 radix->num_added_node + 346 source->node_num[i]; 347 } 348 node->data[i] = source->data[i]; 349 } 350 } else { 351 int next = ++radix->num_added_node; 352 if (fam == AF_UNSPEC) { 353 /* "any" or "none" */ 354 for (i = 0; i < RADIX_FAMILIES; i++) { 355 node->node_num[i] = next; 356 } 357 } else { 358 node->node_num[ISC_RADIX_FAMILY(prefix)] = next; 359 } 360 361 memset(node->data, 0, sizeof(node->data)); 362 } 363 radix->head = node; 364 radix->num_active_node++; 365 *target = node; 366 return (ISC_R_SUCCESS); 367 } 368 369 addr = isc_prefix_touchar(prefix); 370 node = radix->head; 371 372 while (node->bit < bitlen || node->prefix == NULL) { 373 if (node->bit < radix->maxbits && 374 BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) 375 { 376 if (node->r == NULL) { 377 break; 378 } 379 node = node->r; 380 } else { 381 if (node->l == NULL) { 382 break; 383 } 384 node = node->l; 385 } 386 387 INSIST(node != NULL); 388 } 389 390 INSIST(node->prefix != NULL); 391 392 test_addr = isc_prefix_touchar(node->prefix); 393 /* Find the first bit different. */ 394 check_bit = (node->bit < bitlen) ? node->bit : bitlen; 395 differ_bit = 0; 396 for (i = 0; i * 8 < check_bit; i++) { 397 if ((r = (addr[i] ^ test_addr[i])) == 0) { 398 differ_bit = (i + 1) * 8; 399 continue; 400 } 401 /* I know the better way, but for now. */ 402 for (j = 0; j < 8; j++) { 403 if (BIT_TEST(r, (0x80 >> j))) { 404 break; 405 } 406 } 407 /* Must be found. */ 408 INSIST(j < 8); 409 differ_bit = i * 8 + j; 410 break; 411 } 412 413 if (differ_bit > check_bit) { 414 differ_bit = check_bit; 415 } 416 417 parent = node->parent; 418 while (parent != NULL && parent->bit >= differ_bit) { 419 node = parent; 420 parent = node->parent; 421 } 422 423 if (differ_bit == bitlen && node->bit == bitlen) { 424 if (node->prefix != NULL) { 425 /* Set node_num only if it hasn't been set before */ 426 if (source != NULL) { 427 /* Merging nodes */ 428 for (i = 0; i < RADIX_FAMILIES; i++) { 429 if (node->node_num[i] == -1 && 430 source->node_num[i] != -1) 431 { 432 node->node_num[i] = 433 radix->num_added_node + 434 source->node_num[i]; 435 node->data[i] = source->data[i]; 436 } 437 } 438 } else { 439 if (fam == AF_UNSPEC) { 440 /* "any" or "none" */ 441 int next = radix->num_added_node + 1; 442 for (i = 0; i < RADIX_FAMILIES; i++) { 443 if (node->node_num[i] == -1) { 444 node->node_num[i] = 445 next; 446 radix->num_added_node = 447 next; 448 } 449 } 450 } else { 451 int foff = ISC_RADIX_FAMILY(prefix); 452 if (node->node_num[foff] == -1) { 453 node->node_num[foff] = 454 ++radix->num_added_node; 455 } 456 } 457 } 458 *target = node; 459 return (ISC_R_SUCCESS); 460 } else { 461 result = _ref_prefix(radix->mctx, &node->prefix, 462 prefix); 463 if (result != ISC_R_SUCCESS) { 464 return (result); 465 } 466 } 467 INSIST(node->data[RADIX_V4] == NULL && 468 node->node_num[RADIX_V4] == -1 && 469 node->data[RADIX_V4] == NULL && 470 node->node_num[RADIX_V4] == -1); 471 if (source != NULL) { 472 /* Merging node */ 473 for (i = 0; i < RADIX_FAMILIES; i++) { 474 int cur = radix->num_added_node; 475 if (source->node_num[i] != -1) { 476 node->node_num[i] = 477 source->node_num[i] + cur; 478 node->data[i] = source->data[i]; 479 } 480 } 481 } else { 482 int next = ++radix->num_added_node; 483 if (fam == AF_UNSPEC) { 484 /* "any" or "none" */ 485 for (i = 0; i < RADIX_FAMILIES; i++) { 486 node->node_num[i] = next; 487 } 488 } else { 489 node->node_num[ISC_RADIX_FAMILY(prefix)] = next; 490 } 491 } 492 *target = node; 493 return (ISC_R_SUCCESS); 494 } 495 496 new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); 497 if (node->bit != differ_bit && bitlen != differ_bit) { 498 glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t)); 499 } 500 new_node->bit = bitlen; 501 new_node->prefix = NULL; 502 result = _ref_prefix(radix->mctx, &new_node->prefix, prefix); 503 if (result != ISC_R_SUCCESS) { 504 isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t)); 505 if (glue != NULL) { 506 isc_mem_put(radix->mctx, glue, 507 sizeof(isc_radix_node_t)); 508 } 509 return (result); 510 } 511 new_node->parent = NULL; 512 new_node->l = new_node->r = NULL; 513 for (i = 0; i < RADIX_FAMILIES; i++) { 514 new_node->node_num[i] = -1; 515 new_node->data[i] = NULL; 516 } 517 radix->num_active_node++; 518 519 if (source != NULL) { 520 /* Merging node */ 521 for (i = 0; i < RADIX_FAMILIES; i++) { 522 int cur = radix->num_added_node; 523 if (source->node_num[i] != -1) { 524 new_node->node_num[i] = source->node_num[i] + 525 cur; 526 new_node->data[i] = source->data[i]; 527 } 528 } 529 } else { 530 int next = ++radix->num_added_node; 531 if (fam == AF_UNSPEC) { 532 /* "any" or "none" */ 533 for (i = 0; i < RADIX_FAMILIES; i++) { 534 new_node->node_num[i] = next; 535 } 536 } else { 537 new_node->node_num[ISC_RADIX_FAMILY(prefix)] = next; 538 } 539 memset(new_node->data, 0, sizeof(new_node->data)); 540 } 541 542 if (node->bit == differ_bit) { 543 INSIST(glue == NULL); 544 new_node->parent = node; 545 if (node->bit < radix->maxbits && 546 BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) 547 { 548 INSIST(node->r == NULL); 549 node->r = new_node; 550 } else { 551 INSIST(node->l == NULL); 552 node->l = new_node; 553 } 554 *target = new_node; 555 return (ISC_R_SUCCESS); 556 } 557 558 if (bitlen == differ_bit) { 559 INSIST(glue == NULL); 560 if (bitlen < radix->maxbits && 561 BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) 562 { 563 new_node->r = node; 564 } else { 565 new_node->l = node; 566 } 567 new_node->parent = node->parent; 568 if (node->parent == NULL) { 569 INSIST(radix->head == node); 570 radix->head = new_node; 571 } else if (node->parent->r == node) { 572 node->parent->r = new_node; 573 } else { 574 node->parent->l = new_node; 575 } 576 node->parent = new_node; 577 } else { 578 INSIST(glue != NULL); 579 glue->bit = differ_bit; 580 glue->prefix = NULL; 581 glue->parent = node->parent; 582 for (i = 0; i < RADIX_FAMILIES; i++) { 583 glue->data[i] = NULL; 584 glue->node_num[i] = -1; 585 } 586 radix->num_active_node++; 587 if (differ_bit < radix->maxbits && 588 BIT_TEST(addr[differ_bit >> 3], 0x80 >> (differ_bit & 07))) 589 { 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 613 void 614 isc_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(node->prefix); 627 } 628 629 node->prefix = NULL; 630 memset(node->data, 0, sizeof(node->data)); 631 return; 632 } 633 634 if (node->r == NULL && node->l == NULL) { 635 parent = node->parent; 636 _deref_prefix(node->prefix); 637 638 if (parent == NULL) { 639 INSIST(radix->head == node); 640 radix->head = NULL; 641 isc_mem_put(radix->mctx, node, sizeof(*node)); 642 radix->num_active_node--; 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 isc_mem_put(radix->mctx, node, sizeof(*node)); 656 radix->num_active_node--; 657 658 if (parent->prefix) { 659 return; 660 } 661 662 /* We need to remove parent too. */ 663 if (parent->parent == NULL) { 664 INSIST(radix->head == parent); 665 radix->head = child; 666 } else if (parent->parent->r == parent) { 667 parent->parent->r = child; 668 } else { 669 INSIST(parent->parent->l == parent); 670 parent->parent->l = child; 671 } 672 673 child->parent = parent->parent; 674 isc_mem_put(radix->mctx, parent, sizeof(*parent)); 675 radix->num_active_node--; 676 return; 677 } 678 679 if (node->r) { 680 child = node->r; 681 } else { 682 INSIST(node->l != NULL); 683 child = node->l; 684 } 685 686 parent = node->parent; 687 child->parent = parent; 688 689 _deref_prefix(node->prefix); 690 691 if (parent == NULL) { 692 INSIST(radix->head == node); 693 radix->head = child; 694 isc_mem_put(radix->mctx, node, sizeof(*node)); 695 radix->num_active_node--; 696 return; 697 } 698 699 isc_mem_put(radix->mctx, node, sizeof(*node)); 700 radix->num_active_node--; 701 702 if (parent->r == node) { 703 parent->r = child; 704 } else { 705 INSIST(parent->l == node); 706 parent->l = child; 707 } 708 } 709
Indexes created Tue Apr 07 00:22:49 UTC 2026