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