Annotation of src/external/mpl/bind/dist/lib/dns/rbt.c, Revision 1.1
1.1 ! christos 1: /* $NetBSD$ */
! 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: /*! \file */
! 15:
! 16: #include <config.h>
! 17:
! 18: #include <sys/stat.h>
! 19: #ifdef HAVE_INTTYPES_H
! 20: #include <inttypes.h> /* uintptr_t */
! 21: #endif
! 22:
! 23: #include <isc/crc64.h>
! 24: #include <isc/file.h>
! 25: #include <isc/hex.h>
! 26: #include <isc/mem.h>
! 27: #include <isc/once.h>
! 28: #include <isc/platform.h>
! 29: #include <isc/print.h>
! 30: #include <isc/refcount.h>
! 31: #include <isc/socket.h>
! 32: #include <isc/stdio.h>
! 33: #include <isc/string.h>
! 34: #include <isc/util.h>
! 35:
! 36: /*%
! 37: * This define is so dns/name.h (included by dns/fixedname.h) uses more
! 38: * efficient macro calls instead of functions for a few operations.
! 39: */
! 40: #define DNS_NAME_USEINLINE 1
! 41:
! 42: #include <dns/fixedname.h>
! 43: #include <dns/log.h>
! 44: #include <dns/rbt.h>
! 45: #include <dns/result.h>
! 46: #include <dns/version.h>
! 47:
! 48: #include <unistd.h>
! 49:
! 50: #define CHECK(x) \
! 51: do { \
! 52: result = (x); \
! 53: if (result != ISC_R_SUCCESS) \
! 54: goto cleanup; \
! 55: } while (0)
! 56:
! 57: #define RBT_MAGIC ISC_MAGIC('R', 'B', 'T', '+')
! 58: #define VALID_RBT(rbt) ISC_MAGIC_VALID(rbt, RBT_MAGIC)
! 59:
! 60: /*
! 61: * XXXDCL Since parent pointers were added in again, I could remove all of the
! 62: * chain junk, and replace with dns_rbt_firstnode, _previousnode, _nextnode,
! 63: * _lastnode. This would involve pretty major change to the API.
! 64: */
! 65: #define CHAIN_MAGIC ISC_MAGIC('0', '-', '0', '-')
! 66: #define VALID_CHAIN(chain) ISC_MAGIC_VALID(chain, CHAIN_MAGIC)
! 67:
! 68: #define RBT_HASH_SIZE 64
! 69:
! 70: #ifdef RBT_MEM_TEST
! 71: #undef RBT_HASH_SIZE
! 72: #define RBT_HASH_SIZE 2 /*%< To give the reallocation code a workout. */
! 73: #endif
! 74:
! 75: struct dns_rbt {
! 76: unsigned int magic;
! 77: isc_mem_t * mctx;
! 78: dns_rbtnode_t * root;
! 79: void (*data_deleter)(void *, void *);
! 80: void * deleter_arg;
! 81: unsigned int nodecount;
! 82: size_t hashsize;
! 83: dns_rbtnode_t ** hashtable;
! 84: void * mmap_location;
! 85: };
! 86:
! 87: #define RED 0
! 88: #define BLACK 1
! 89:
! 90: /*
! 91: * This is the header for map-format RBT images. It is populated,
! 92: * and then written, as the LAST thing done to the file before returning.
! 93: * Writing this last (with zeros in the header area initially) will ensure
! 94: * that the header is only valid when the RBT image is also valid.
! 95: */
! 96: typedef struct file_header file_header_t;
! 97:
! 98: /* Pad to 32 bytes */
! 99: static char FILE_VERSION[32] = "\0";
! 100:
! 101: /* Header length, always the same size regardless of structure size */
! 102: #define HEADER_LENGTH 1024
! 103:
! 104: struct file_header {
! 105: char version1[32];
! 106: isc_uint64_t first_node_offset; /* usually 1024 */
! 107: /*
! 108: * information about the system on which the map file was generated
! 109: * will be used to tell if we can load the map file or not
! 110: */
! 111: isc_uint32_t ptrsize;
! 112: unsigned int bigendian:1; /* big or little endian system */
! 113: unsigned int rdataset_fixed:1; /* compiled with --enable-rrset-fixed */
! 114: unsigned int nodecount; /* shadow from rbt structure */
! 115: isc_uint64_t crc;
! 116: char version2[32]; /* repeated; must match version1 */
! 117: };
! 118:
! 119: /*
! 120: * The following declarations are for the serialization of an RBT:
! 121: *
! 122: * step one: write out a zeroed header of 1024 bytes
! 123: * step two: walk the tree in a depth-first, left-right-down order, writing
! 124: * out the nodes, reserving space as we go, correcting addresses to point
! 125: * at the proper offset in the file, and setting a flag for each pointer to
! 126: * indicate that it is a reference to a location in the file, rather than in
! 127: * memory.
! 128: * step three: write out the header, adding the information that will be
! 129: * needed to re-create the tree object itself.
! 130: *
! 131: * The RBTDB object will do this three times, once for each of the three
! 132: * RBT objects it contains.
! 133: *
! 134: * Note: 'file' must point an actual open file that can be mmapped
! 135: * and fseeked, not to a pipe or stream
! 136: */
! 137:
! 138: static isc_result_t
! 139: dns_rbt_zero_header(FILE *file);
! 140:
! 141: static isc_result_t
! 142: write_header(FILE *file, dns_rbt_t *rbt, isc_uint64_t first_node_offset,
! 143: isc_uint64_t crc);
! 144:
! 145: static isc_boolean_t
! 146: match_header_version(file_header_t *header);
! 147:
! 148: static isc_result_t
! 149: serialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left,
! 150: uintptr_t right, uintptr_t down, uintptr_t parent,
! 151: uintptr_t data, isc_uint64_t *crc);
! 152:
! 153: static isc_result_t
! 154: serialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
! 155: dns_rbtdatawriter_t datawriter, void *writer_arg,
! 156: uintptr_t *where, isc_uint64_t *crc);
! 157: /*
! 158: * The following functions allow you to get the actual address of a pointer
! 159: * without having to use an if statement to check to see if that address is
! 160: * relative or not
! 161: */
! 162: static inline dns_rbtnode_t *
! 163: getparent(dns_rbtnode_t *node, file_header_t *header) {
! 164: char *adjusted_address = (char *)(node->parent);
! 165: adjusted_address += node->parent_is_relative * (uintptr_t)header;
! 166:
! 167: return ((dns_rbtnode_t *)adjusted_address);
! 168: }
! 169:
! 170: static inline dns_rbtnode_t *
! 171: getleft(dns_rbtnode_t *node, file_header_t *header) {
! 172: char *adjusted_address = (char *)(node->left);
! 173: adjusted_address += node->left_is_relative * (uintptr_t)header;
! 174:
! 175: return ((dns_rbtnode_t *)adjusted_address);
! 176: }
! 177:
! 178: static inline dns_rbtnode_t *
! 179: getright(dns_rbtnode_t *node, file_header_t *header) {
! 180: char *adjusted_address = (char *)(node->right);
! 181: adjusted_address += node->right_is_relative * (uintptr_t)header;
! 182:
! 183: return ((dns_rbtnode_t *)adjusted_address);
! 184: }
! 185:
! 186: static inline dns_rbtnode_t *
! 187: getdown(dns_rbtnode_t *node, file_header_t *header) {
! 188: char *adjusted_address = (char *)(node->down);
! 189: adjusted_address += node->down_is_relative * (uintptr_t)header;
! 190:
! 191: return ((dns_rbtnode_t *)adjusted_address);
! 192: }
! 193:
! 194: static inline dns_rbtnode_t *
! 195: getdata(dns_rbtnode_t *node, file_header_t *header) {
! 196: char *adjusted_address = (char *)(node->data);
! 197: adjusted_address += node->data_is_relative * (uintptr_t)header;
! 198:
! 199: return ((dns_rbtnode_t *)adjusted_address);
! 200: }
! 201:
! 202: /*%
! 203: * Elements of the rbtnode structure.
! 204: */
! 205: #define PARENT(node) ((node)->parent)
! 206: #define LEFT(node) ((node)->left)
! 207: #define RIGHT(node) ((node)->right)
! 208: #define DOWN(node) ((node)->down)
! 209: #ifdef DNS_RBT_USEHASH
! 210: #define UPPERNODE(node) ((node)->uppernode)
! 211: #endif /* DNS_RBT_USEHASH */
! 212: #define DATA(node) ((node)->data)
! 213: #define IS_EMPTY(node) ((node)->data == NULL)
! 214: #define HASHNEXT(node) ((node)->hashnext)
! 215: #define HASHVAL(node) ((node)->hashval)
! 216: #define COLOR(node) ((node)->color)
! 217: #define NAMELEN(node) ((node)->namelen)
! 218: #define OLDNAMELEN(node) ((node)->oldnamelen)
! 219: #define OFFSETLEN(node) ((node)->offsetlen)
! 220: #define ATTRS(node) ((node)->attributes)
! 221: #define IS_ROOT(node) ISC_TF((node)->is_root == 1)
! 222: #define FINDCALLBACK(node) ISC_TF((node)->find_callback == 1)
! 223:
! 224: /*%
! 225: * Structure elements from the rbtdb.c, not
! 226: * used as part of the rbt.c algorithms.
! 227: */
! 228: #define DIRTY(node) ((node)->dirty)
! 229: #define WILD(node) ((node)->wild)
! 230: #define LOCKNUM(node) ((node)->locknum)
! 231:
! 232: /*%
! 233: * The variable length stuff stored after the node has the following
! 234: * structure.
! 235: *
! 236: * <name_data>{1..255}<oldoffsetlen>{1}<offsets>{1..128}
! 237: *
! 238: * <name_data> contains the name of the node when it was created.
! 239: * <oldoffsetlen> contains the length of <offsets> when the node was created.
! 240: * <offsets> contains the offets into name for each label when the node was
! 241: * created.
! 242: */
! 243:
! 244: #define NAME(node) ((unsigned char *)((node) + 1))
! 245: #define OFFSETS(node) (NAME(node) + OLDNAMELEN(node) + 1)
! 246: #define OLDOFFSETLEN(node) (OFFSETS(node)[-1])
! 247:
! 248: #define NODE_SIZE(node) (sizeof(*node) + \
! 249: OLDNAMELEN(node) + OLDOFFSETLEN(node) + 1)
! 250:
! 251: /*%
! 252: * Color management.
! 253: */
! 254: #define IS_RED(node) ((node) != NULL && (node)->color == RED)
! 255: #define IS_BLACK(node) ((node) == NULL || (node)->color == BLACK)
! 256: #define MAKE_RED(node) ((node)->color = RED)
! 257: #define MAKE_BLACK(node) ((node)->color = BLACK)
! 258:
! 259: /*%
! 260: * Chain management.
! 261: *
! 262: * The "ancestors" member of chains were removed, with their job now
! 263: * being wholly handled by parent pointers (which didn't exist, because
! 264: * of memory concerns, when chains were first implemented).
! 265: */
! 266: #define ADD_LEVEL(chain, node) \
! 267: do { \
! 268: INSIST((chain)->level_count < DNS_RBT_LEVELBLOCK); \
! 269: (chain)->levels[(chain)->level_count++] = (node); \
! 270: } while (0)
! 271:
! 272: /*%
! 273: * The following macros directly access normally private name variables.
! 274: * These macros are used to avoid a lot of function calls in the critical
! 275: * path of the tree traversal code.
! 276: */
! 277:
! 278: static inline void
! 279: NODENAME(dns_rbtnode_t *node, dns_name_t *name) {
! 280: name->length = NAMELEN(node);
! 281: name->labels = OFFSETLEN(node);
! 282: name->ndata = NAME(node);
! 283: name->offsets = OFFSETS(node);
! 284: name->attributes = ATTRS(node);
! 285: name->attributes |= DNS_NAMEATTR_READONLY;
! 286: }
! 287:
! 288: void
! 289: dns_rbtnode_nodename(dns_rbtnode_t *node, dns_name_t *name) {
! 290: name->length = NAMELEN(node);
! 291: name->labels = OFFSETLEN(node);
! 292: name->ndata = NAME(node);
! 293: name->offsets = OFFSETS(node);
! 294: name->attributes = ATTRS(node);
! 295: name->attributes |= DNS_NAMEATTR_READONLY;
! 296: }
! 297:
! 298: dns_rbtnode_t *
! 299: dns_rbt_root(dns_rbt_t *rbt) {
! 300: return rbt->root;
! 301: }
! 302:
! 303: #ifdef DNS_RBT_USEHASH
! 304: static isc_result_t
! 305: inithash(dns_rbt_t *rbt);
! 306: #endif
! 307:
! 308: #ifdef DEBUG
! 309: #define inline
! 310: /*
! 311: * A little something to help out in GDB.
! 312: */
! 313: dns_name_t Name(dns_rbtnode_t *node);
! 314: dns_name_t
! 315: Name(dns_rbtnode_t *node) {
! 316: dns_name_t name;
! 317:
! 318: dns_name_init(&name, NULL);
! 319: if (node != NULL)
! 320: NODENAME(node, &name);
! 321:
! 322: return (name);
! 323: }
! 324:
! 325: static void
! 326: hexdump(const char *desc, unsigned char *data, size_t size) {
! 327: char hexdump[BUFSIZ * 2 + 1];
! 328: isc_buffer_t b;
! 329: isc_region_t r;
! 330: isc_result_t result;
! 331: size_t bytes;
! 332:
! 333: fprintf(stderr, "%s: ", desc);
! 334: do {
! 335: isc_buffer_init(&b, hexdump, sizeof(hexdump));
! 336: r.base = data;
! 337: r.length = bytes = (size > BUFSIZ) ? BUFSIZ : size;
! 338: result = isc_hex_totext(&r, 0, "", &b);
! 339: RUNTIME_CHECK(result == ISC_R_SUCCESS);
! 340: isc_buffer_putuint8(&b, 0);
! 341: fprintf(stderr, "%s", hexdump);
! 342: data += bytes;
! 343: size -= bytes;
! 344: } while (size > 0);
! 345: fprintf(stderr, "\n");
! 346: }
! 347: #endif /* DEBUG */
! 348:
! 349: #ifdef DNS_RBT_USEHASH
! 350:
! 351: /*
! 352: * Upper node is the parent of the root of the passed node's
! 353: * subtree. The passed node must not be NULL.
! 354: */
! 355: static inline dns_rbtnode_t *
! 356: get_upper_node(dns_rbtnode_t *node) {
! 357: return (UPPERNODE(node));
! 358: }
! 359:
! 360: static void
! 361: fixup_uppernodes_helper(dns_rbtnode_t *node, dns_rbtnode_t *uppernode) {
! 362: if (node == NULL)
! 363: return;
! 364:
! 365: UPPERNODE(node) = uppernode;
! 366:
! 367: fixup_uppernodes_helper(LEFT(node), uppernode);
! 368: fixup_uppernodes_helper(RIGHT(node), uppernode);
! 369: fixup_uppernodes_helper(DOWN(node), node);
! 370: }
! 371:
! 372: /*
! 373: * This function is used to fixup uppernode members of all dns_rbtnodes
! 374: * after deserialization.
! 375: */
! 376: static void
! 377: fixup_uppernodes(dns_rbt_t *rbt) {
! 378: fixup_uppernodes_helper(rbt->root, NULL);
! 379: }
! 380:
! 381: #else
! 382:
! 383: /* The passed node must not be NULL. */
! 384: static inline dns_rbtnode_t *
! 385: get_subtree_root(dns_rbtnode_t *node) {
! 386: while (!IS_ROOT(node)) {
! 387: node = PARENT(node);
! 388: }
! 389:
! 390: return (node);
! 391: }
! 392:
! 393: /* Upper node is the parent of the root of the passed node's
! 394: * subtree. The passed node must not be NULL.
! 395: */
! 396: static inline dns_rbtnode_t *
! 397: get_upper_node(dns_rbtnode_t *node) {
! 398: dns_rbtnode_t *root = get_subtree_root(node);
! 399:
! 400: /*
! 401: * Return the node in the level above the argument node that points
! 402: * to the level the argument node is in. If the argument node is in
! 403: * the top level, the return value is NULL.
! 404: */
! 405: return (PARENT(root));
! 406: }
! 407:
! 408: #endif /* DNS_RBT_USEHASH */
! 409:
! 410: size_t
! 411: dns__rbtnode_getdistance(dns_rbtnode_t *node) {
! 412: size_t nodes = 1;
! 413:
! 414: while (node != NULL) {
! 415: if (IS_ROOT(node))
! 416: break;
! 417: nodes++;
! 418: node = PARENT(node);
! 419: }
! 420:
! 421: return (nodes);
! 422: }
! 423:
! 424: /*
! 425: * Forward declarations.
! 426: */
! 427: static isc_result_t
! 428: create_node(isc_mem_t *mctx, const dns_name_t *name, dns_rbtnode_t **nodep);
! 429:
! 430: #ifdef DNS_RBT_USEHASH
! 431: static inline void
! 432: hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, const dns_name_t *name);
! 433: static inline void
! 434: unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
! 435: static void
! 436: rehash(dns_rbt_t *rbt, unsigned int newcount);
! 437: #else
! 438: #define hash_node(rbt, node, name)
! 439: #define unhash_node(rbt, node)
! 440: #define rehash(rbt, newcount)
! 441: #endif
! 442:
! 443: static inline void
! 444: rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
! 445: static inline void
! 446: rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
! 447:
! 448: static void
! 449: addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
! 450: dns_rbtnode_t **rootp);
! 451:
! 452: static void
! 453: deletefromlevel(dns_rbtnode_t *item, dns_rbtnode_t **rootp);
! 454:
! 455: static isc_result_t
! 456: treefix(dns_rbt_t *rbt, void *base, size_t size,
! 457: dns_rbtnode_t *n, const dns_name_t *name,
! 458: dns_rbtdatafixer_t datafixer, void *fixer_arg,
! 459: isc_uint64_t *crc);
! 460:
! 461: static void
! 462: deletetreeflat(dns_rbt_t *rbt, unsigned int quantum, isc_boolean_t unhash,
! 463: dns_rbtnode_t **nodep);
! 464:
! 465: static void
! 466: printnodename(dns_rbtnode_t *node, isc_boolean_t quoted, FILE *f);
! 467:
! 468: static void
! 469: freenode(dns_rbt_t *rbt, dns_rbtnode_t **nodep);
! 470:
! 471: static isc_result_t
! 472: dns_rbt_zero_header(FILE *file) {
! 473: /*
! 474: * Write out a zeroed header as a placeholder. Doing this ensures
! 475: * that the file will not read while it is partially written, should
! 476: * writing fail or be interrupted.
! 477: */
! 478: char buffer[HEADER_LENGTH];
! 479: isc_result_t result;
! 480:
! 481: memset(buffer, 0, HEADER_LENGTH);
! 482: result = isc_stdio_write(buffer, 1, HEADER_LENGTH, file, NULL);
! 483: if (result != ISC_R_SUCCESS)
! 484: return (result);
! 485:
! 486: result = fflush(file);
! 487: if (result != ISC_R_SUCCESS)
! 488: return (result);
! 489:
! 490: return (ISC_R_SUCCESS);
! 491: }
! 492:
! 493: static isc_once_t once = ISC_ONCE_INIT;
! 494:
! 495: static void
! 496: init_file_version(void) {
! 497: int n;
! 498:
! 499: memset(FILE_VERSION, 0, sizeof(FILE_VERSION));
! 500: n = snprintf(FILE_VERSION, sizeof(FILE_VERSION),
! 501: "RBT Image %s %s", dns_major, dns_mapapi);
! 502: INSIST(n > 0 && (unsigned int)n < sizeof(FILE_VERSION));
! 503: }
! 504:
! 505: /*
! 506: * Write out the real header, including NodeDump version information
! 507: * and the offset of the first node.
! 508: *
! 509: * Any information stored in the rbt object itself should be stored
! 510: * here.
! 511: */
! 512: static isc_result_t
! 513: write_header(FILE *file, dns_rbt_t *rbt, isc_uint64_t first_node_offset,
! 514: isc_uint64_t crc)
! 515: {
! 516: file_header_t header;
! 517: isc_result_t result;
! 518: off_t location;
! 519:
! 520: RUNTIME_CHECK(isc_once_do(&once, init_file_version) == ISC_R_SUCCESS);
! 521:
! 522: memset(&header, 0, sizeof(file_header_t));
! 523: memmove(header.version1, FILE_VERSION, sizeof(header.version1));
! 524: memmove(header.version2, FILE_VERSION, sizeof(header.version2));
! 525: header.first_node_offset = first_node_offset;
! 526: header.ptrsize = (isc_uint32_t) sizeof(void *);
! 527: header.bigendian = (1 == htonl(1)) ? 1 : 0;
! 528:
! 529: #ifdef DNS_RDATASET_FIXED
! 530: header.rdataset_fixed = 1;
! 531: #else
! 532: header.rdataset_fixed = 0;
! 533: #endif
! 534:
! 535: header.nodecount = rbt->nodecount;
! 536:
! 537: header.crc = crc;
! 538:
! 539: CHECK(isc_stdio_tell(file, &location));
! 540: location = dns_rbt_serialize_align(location);
! 541: CHECK(isc_stdio_seek(file, location, SEEK_SET));
! 542: CHECK(isc_stdio_write(&header, 1, sizeof(file_header_t), file, NULL));
! 543: CHECK(fflush(file));
! 544:
! 545: /* Ensure we are always at the end of the file. */
! 546: CHECK(isc_stdio_seek(file, 0, SEEK_END));
! 547:
! 548: cleanup:
! 549: return (result);
! 550: }
! 551:
! 552: static isc_boolean_t
! 553: match_header_version(file_header_t *header) {
! 554: RUNTIME_CHECK(isc_once_do(&once, init_file_version) == ISC_R_SUCCESS);
! 555:
! 556: if (memcmp(header->version1, FILE_VERSION,
! 557: sizeof(header->version1)) != 0 ||
! 558: memcmp(header->version2, FILE_VERSION,
! 559: sizeof(header->version1)) != 0)
! 560: {
! 561: return (ISC_FALSE);
! 562: }
! 563:
! 564: return (ISC_TRUE);
! 565: }
! 566:
! 567: static isc_result_t
! 568: serialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left,
! 569: uintptr_t right, uintptr_t down, uintptr_t parent,
! 570: uintptr_t data, isc_uint64_t *crc)
! 571: {
! 572: dns_rbtnode_t temp_node;
! 573: off_t file_position;
! 574: unsigned char *node_data;
! 575: size_t datasize;
! 576: isc_result_t result;
! 577: #ifdef DEBUG
! 578: dns_name_t nodename;
! 579: #endif
! 580:
! 581: INSIST(node != NULL);
! 582:
! 583: CHECK(isc_stdio_tell(file, &file_position));
! 584: file_position = dns_rbt_serialize_align(file_position);
! 585: CHECK(isc_stdio_seek(file, file_position, SEEK_SET));
! 586:
! 587: temp_node = *node;
! 588: temp_node.down_is_relative = 0;
! 589: temp_node.left_is_relative = 0;
! 590: temp_node.right_is_relative = 0;
! 591: temp_node.parent_is_relative = 0;
! 592: temp_node.data_is_relative = 0;
! 593: temp_node.is_mmapped = 1;
! 594:
! 595: /*
! 596: * If the next node is not NULL, calculate the next node's location
! 597: * in the file. Note that this will have to change when the data
! 598: * structure changes, and it also assumes that we always write the
! 599: * nodes out in list order (which we currently do.)
! 600: */
! 601: if (temp_node.parent != NULL) {
! 602: temp_node.parent = (dns_rbtnode_t *)(parent);
! 603: temp_node.parent_is_relative = 1;
! 604: }
! 605: if (temp_node.left != NULL) {
! 606: temp_node.left = (dns_rbtnode_t *)(left);
! 607: temp_node.left_is_relative = 1;
! 608: }
! 609: if (temp_node.right != NULL) {
! 610: temp_node.right = (dns_rbtnode_t *)(right);
! 611: temp_node.right_is_relative = 1;
! 612: }
! 613: if (temp_node.down != NULL) {
! 614: temp_node.down = (dns_rbtnode_t *)(down);
! 615: temp_node.down_is_relative = 1;
! 616: }
! 617: if (temp_node.data != NULL) {
! 618: temp_node.data = (dns_rbtnode_t *)(data);
! 619: temp_node.data_is_relative = 1;
! 620: }
! 621:
! 622: node_data = (unsigned char *) node + sizeof(dns_rbtnode_t);
! 623: datasize = NODE_SIZE(node) - sizeof(dns_rbtnode_t);
! 624:
! 625: CHECK(isc_stdio_write(&temp_node, 1, sizeof(dns_rbtnode_t),
! 626: file, NULL));
! 627: CHECK(isc_stdio_write(node_data, 1, datasize, file, NULL));
! 628:
! 629: #ifdef DEBUG
! 630: dns_name_init(&nodename, NULL);
! 631: NODENAME(node, &nodename);
! 632: fprintf(stderr, "serialize ");
! 633: dns_name_print(&nodename, stderr);
! 634: fprintf(stderr, "\n");
! 635: hexdump("node header", (unsigned char*) &temp_node,
! 636: sizeof(dns_rbtnode_t));
! 637: hexdump("node data", node_data, datasize);
! 638: #endif
! 639:
! 640: isc_crc64_update(crc, (const isc_uint8_t *) &temp_node,
! 641: sizeof(dns_rbtnode_t));
! 642: isc_crc64_update(crc, (const isc_uint8_t *) node_data, datasize);
! 643:
! 644: cleanup:
! 645: return (result);
! 646: }
! 647:
! 648: static isc_result_t
! 649: serialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
! 650: dns_rbtdatawriter_t datawriter, void *writer_arg,
! 651: uintptr_t *where, isc_uint64_t *crc)
! 652: {
! 653: uintptr_t left = 0, right = 0, down = 0, data = 0;
! 654: off_t location = 0, offset_adjust;
! 655: isc_result_t result;
! 656:
! 657: if (node == NULL) {
! 658: if (where != NULL)
! 659: *where = 0;
! 660: return (ISC_R_SUCCESS);
! 661: }
! 662:
! 663: /* Reserve space for current node. */
! 664: CHECK(isc_stdio_tell(file, &location));
! 665: location = dns_rbt_serialize_align(location);
! 666: CHECK(isc_stdio_seek(file, location, SEEK_SET));
! 667:
! 668: offset_adjust = dns_rbt_serialize_align(location + NODE_SIZE(node));
! 669: CHECK(isc_stdio_seek(file, offset_adjust, SEEK_SET));
! 670:
! 671: /*
! 672: * Serialize the rest of the tree.
! 673: *
! 674: * WARNING: A change in the order (from left, right, down)
! 675: * will break the way the crc hash is computed.
! 676: */
! 677: CHECK(serialize_nodes(file, getleft(node, NULL), location,
! 678: datawriter, writer_arg, &left, crc));
! 679: CHECK(serialize_nodes(file, getright(node, NULL), location,
! 680: datawriter, writer_arg, &right, crc));
! 681: CHECK(serialize_nodes(file, getdown(node, NULL), location,
! 682: datawriter, writer_arg, &down, crc));
! 683:
! 684: if (node->data != NULL) {
! 685: off_t ret;
! 686:
! 687: CHECK(isc_stdio_tell(file, &ret));
! 688: ret = dns_rbt_serialize_align(ret);
! 689: CHECK(isc_stdio_seek(file, ret, SEEK_SET));
! 690: data = ret;
! 691:
! 692: datawriter(file, node->data, writer_arg, crc);
! 693: }
! 694:
! 695: /* Seek back to reserved space. */
! 696: CHECK(isc_stdio_seek(file, location, SEEK_SET));
! 697:
! 698: /* Serialize the current node. */
! 699: CHECK(serialize_node(file, node, left, right, down, parent, data, crc));
! 700:
! 701: /* Ensure we are always at the end of the file. */
! 702: CHECK(isc_stdio_seek(file, 0, SEEK_END));
! 703:
! 704: if (where != NULL)
! 705: *where = (uintptr_t) location;
! 706:
! 707: cleanup:
! 708: return (result);
! 709: }
! 710:
! 711: off_t
! 712: dns_rbt_serialize_align(off_t target) {
! 713: off_t offset = target % 8;
! 714:
! 715: if (offset == 0)
! 716: return (target);
! 717: else
! 718: return (target + 8 - offset);
! 719: }
! 720:
! 721: isc_result_t
! 722: dns_rbt_serialize_tree(FILE *file, dns_rbt_t *rbt,
! 723: dns_rbtdatawriter_t datawriter,
! 724: void *writer_arg, off_t *offset)
! 725: {
! 726: isc_result_t result;
! 727: off_t header_position, node_position, end_position;
! 728: isc_uint64_t crc;
! 729:
! 730: REQUIRE(file != NULL);
! 731:
! 732: CHECK(isc_file_isplainfilefd(fileno(file)));
! 733:
! 734: isc_crc64_init(&crc);
! 735:
! 736: CHECK(isc_stdio_tell(file, &header_position));
! 737:
! 738: /* Write dummy header */
! 739: CHECK(dns_rbt_zero_header(file));
! 740:
! 741: /* Serialize nodes */
! 742: CHECK(isc_stdio_tell(file, &node_position));
! 743: CHECK(serialize_nodes(file, rbt->root, 0, datawriter,
! 744: writer_arg, NULL, &crc));
! 745:
! 746: CHECK(isc_stdio_tell(file, &end_position));
! 747: if (node_position == end_position) {
! 748: CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
! 749: *offset = 0;
! 750: return (ISC_R_SUCCESS);
! 751: }
! 752:
! 753: isc_crc64_final(&crc);
! 754: #ifdef DEBUG
! 755: hexdump("serializing CRC", (unsigned char *)&crc, sizeof(crc));
! 756: #endif
! 757:
! 758: /* Serialize header */
! 759: CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
! 760: CHECK(write_header(file, rbt, HEADER_LENGTH, crc));
! 761:
! 762: /* Ensure we are always at the end of the file. */
! 763: CHECK(isc_stdio_seek(file, 0, SEEK_END));
! 764: *offset = dns_rbt_serialize_align(header_position);
! 765:
! 766: cleanup:
! 767: return (result);
! 768: }
! 769:
! 770: #define CONFIRM(a) do { \
! 771: if (! (a)) { \
! 772: result = ISC_R_INVALIDFILE; \
! 773: goto cleanup; \
! 774: } \
! 775: } while(0);
! 776:
! 777: static isc_result_t
! 778: treefix(dns_rbt_t *rbt, void *base, size_t filesize, dns_rbtnode_t *n,
! 779: const dns_name_t *name, dns_rbtdatafixer_t datafixer,
! 780: void *fixer_arg, isc_uint64_t *crc)
! 781: {
! 782: isc_result_t result = ISC_R_SUCCESS;
! 783: dns_fixedname_t fixed;
! 784: dns_name_t nodename, *fullname;
! 785: unsigned char *node_data;
! 786: dns_rbtnode_t header;
! 787: size_t datasize, nodemax = filesize - sizeof(dns_rbtnode_t);
! 788:
! 789: if (n == NULL)
! 790: return (ISC_R_SUCCESS);
! 791:
! 792: CONFIRM((void *) n >= base);
! 793: CONFIRM((char *) n - (char *) base <= (int) nodemax);
! 794: CONFIRM(DNS_RBTNODE_VALID(n));
! 795:
! 796: dns_name_init(&nodename, NULL);
! 797: NODENAME(n, &nodename);
! 798:
! 799: fullname = &nodename;
! 800: CONFIRM(dns_name_isvalid(fullname));
! 801:
! 802: if (!dns_name_isabsolute(&nodename)) {
! 803: fullname = dns_fixedname_initname(&fixed);
! 804: CHECK(dns_name_concatenate(&nodename, name, fullname, NULL));
! 805: }
! 806:
! 807: /* memorize header contents prior to fixup */
! 808: memmove(&header, n, sizeof(header));
! 809:
! 810: if (n->left_is_relative) {
! 811: CONFIRM(n->left <= (dns_rbtnode_t *) nodemax);
! 812: n->left = getleft(n, rbt->mmap_location);
! 813: n->left_is_relative = 0;
! 814: CONFIRM(DNS_RBTNODE_VALID(n->left));
! 815: } else
! 816: CONFIRM(n->left == NULL);
! 817:
! 818: if (n->right_is_relative) {
! 819: CONFIRM(n->right <= (dns_rbtnode_t *) nodemax);
! 820: n->right = getright(n, rbt->mmap_location);
! 821: n->right_is_relative = 0;
! 822: CONFIRM(DNS_RBTNODE_VALID(n->right));
! 823: } else
! 824: CONFIRM(n->right == NULL);
! 825:
! 826: if (n->down_is_relative) {
! 827: CONFIRM(n->down <= (dns_rbtnode_t *) nodemax);
! 828: n->down = getdown(n, rbt->mmap_location);
! 829: n->down_is_relative = 0;
! 830: CONFIRM(n->down > (dns_rbtnode_t *) n);
! 831: CONFIRM(DNS_RBTNODE_VALID(n->down));
! 832: } else
! 833: CONFIRM(n->down == NULL);
! 834:
! 835: if (n->parent_is_relative) {
! 836: CONFIRM(n->parent <= (dns_rbtnode_t *) nodemax);
! 837: n->parent = getparent(n, rbt->mmap_location);
! 838: n->parent_is_relative = 0;
! 839: CONFIRM(n->parent < (dns_rbtnode_t *) n);
! 840: CONFIRM(DNS_RBTNODE_VALID(n->parent));
! 841: } else
! 842: CONFIRM(n->parent == NULL);
! 843:
! 844: if (n->data_is_relative) {
! 845: CONFIRM(n->data <= (void *) filesize);
! 846: n->data = getdata(n, rbt->mmap_location);
! 847: n->data_is_relative = 0;
! 848: CONFIRM(n->data > (void *) n);
! 849: } else
! 850: CONFIRM(n->data == NULL);
! 851:
! 852: hash_node(rbt, n, fullname);
! 853:
! 854: /* a change in the order (from left, right, down) will break hashing*/
! 855: if (n->left != NULL)
! 856: CHECK(treefix(rbt, base, filesize, n->left, name,
! 857: datafixer, fixer_arg, crc));
! 858: if (n->right != NULL)
! 859: CHECK(treefix(rbt, base, filesize, n->right, name,
! 860: datafixer, fixer_arg, crc));
! 861: if (n->down != NULL)
! 862: CHECK(treefix(rbt, base, filesize, n->down, fullname,
! 863: datafixer, fixer_arg, crc));
! 864:
! 865: if (datafixer != NULL && n->data != NULL)
! 866: CHECK(datafixer(n, base, filesize, fixer_arg, crc));
! 867:
! 868: rbt->nodecount++;
! 869: node_data = (unsigned char *) n + sizeof(dns_rbtnode_t);
! 870: datasize = NODE_SIZE(n) - sizeof(dns_rbtnode_t);
! 871:
! 872: #ifdef DEBUG
! 873: fprintf(stderr, "deserialize ");
! 874: dns_name_print(&nodename, stderr);
! 875: fprintf(stderr, "\n");
! 876: hexdump("node header", (unsigned char *) &header,
! 877: sizeof(dns_rbtnode_t));
! 878: hexdump("node data", node_data, datasize);
! 879: #endif
! 880: isc_crc64_update(crc, (const isc_uint8_t *) &header,
! 881: sizeof(dns_rbtnode_t));
! 882: isc_crc64_update(crc, (const isc_uint8_t *) node_data,
! 883: datasize);
! 884:
! 885: cleanup:
! 886: return (result);
! 887: }
! 888:
! 889: isc_result_t
! 890: dns_rbt_deserialize_tree(void *base_address, size_t filesize,
! 891: off_t header_offset, isc_mem_t *mctx,
! 892: dns_rbtdeleter_t deleter, void *deleter_arg,
! 893: dns_rbtdatafixer_t datafixer, void *fixer_arg,
! 894: dns_rbtnode_t **originp, dns_rbt_t **rbtp)
! 895: {
! 896: isc_result_t result = ISC_R_SUCCESS;
! 897: file_header_t *header;
! 898: dns_rbt_t *rbt = NULL;
! 899: isc_uint64_t crc;
! 900: unsigned int host_big_endian;
! 901:
! 902: REQUIRE(originp == NULL || *originp == NULL);
! 903: REQUIRE(rbtp != NULL && *rbtp == NULL);
! 904:
! 905: isc_crc64_init(&crc);
! 906:
! 907: CHECK(dns_rbt_create(mctx, deleter, deleter_arg, &rbt));
! 908:
! 909: rbt->mmap_location = base_address;
! 910:
! 911: header = (file_header_t *)((char *)base_address + header_offset);
! 912: if (!match_header_version(header)) {
! 913: result = ISC_R_INVALIDFILE;
! 914: goto cleanup;
! 915: }
! 916:
! 917: #ifdef DNS_RDATASET_FIXED
! 918: if (header->rdataset_fixed != 1) {
! 919: result = ISC_R_INVALIDFILE;
! 920: goto cleanup;
! 921: }
! 922:
! 923: #else
! 924: if (header->rdataset_fixed != 0) {
! 925: result = ISC_R_INVALIDFILE;
! 926: goto cleanup;
! 927: }
! 928: #endif
! 929:
! 930: if (header->ptrsize != (isc_uint32_t) sizeof(void *)) {
! 931: result = ISC_R_INVALIDFILE;
! 932: goto cleanup;
! 933: }
! 934:
! 935: host_big_endian = (1 == htonl(1));
! 936: if (header->bigendian != host_big_endian) {
! 937: result = ISC_R_INVALIDFILE;
! 938: goto cleanup;
! 939: }
! 940:
! 941: /* Copy other data items from the header into our rbt. */
! 942: rbt->root = (dns_rbtnode_t *)((char *)base_address +
! 943: header_offset + header->first_node_offset);
! 944:
! 945: if ((header->nodecount * sizeof(dns_rbtnode_t)) > filesize) {
! 946: result = ISC_R_INVALIDFILE;
! 947: goto cleanup;
! 948: }
! 949: rehash(rbt, header->nodecount);
! 950:
! 951: CHECK(treefix(rbt, base_address, filesize, rbt->root,
! 952: dns_rootname, datafixer, fixer_arg, &crc));
! 953:
! 954: isc_crc64_final(&crc);
! 955: #ifdef DEBUG
! 956: hexdump("deserializing CRC", (unsigned char *)&crc, sizeof(crc));
! 957: #endif
! 958:
! 959: /* Check file hash */
! 960: if (header->crc != crc) {
! 961: result = ISC_R_INVALIDFILE;
! 962: goto cleanup;
! 963: }
! 964:
! 965: if (header->nodecount != rbt->nodecount) {
! 966: result = ISC_R_INVALIDFILE;
! 967: goto cleanup;
! 968: }
! 969:
! 970: #ifdef DNS_RBT_USEHASH
! 971: fixup_uppernodes(rbt);
! 972: #endif /* DNS_RBT_USEHASH */
! 973:
! 974: *rbtp = rbt;
! 975: if (originp != NULL)
! 976: *originp = rbt->root;
! 977:
! 978: cleanup:
! 979: if (result != ISC_R_SUCCESS && rbt != NULL) {
! 980: rbt->root = NULL;
! 981: rbt->nodecount = 0;
! 982: dns_rbt_destroy(&rbt);
! 983: }
! 984:
! 985: return (result);
! 986: }
! 987:
! 988: /*
! 989: * Initialize a red/black tree of trees.
! 990: */
! 991: isc_result_t
! 992: dns_rbt_create(isc_mem_t *mctx, dns_rbtdeleter_t deleter,
! 993: void *deleter_arg, dns_rbt_t **rbtp)
! 994: {
! 995: #ifdef DNS_RBT_USEHASH
! 996: isc_result_t result;
! 997: #endif
! 998: dns_rbt_t *rbt;
! 999:
! 1000: REQUIRE(mctx != NULL);
! 1001: REQUIRE(rbtp != NULL && *rbtp == NULL);
! 1002: REQUIRE(deleter == NULL ? deleter_arg == NULL : 1);
! 1003:
! 1004: rbt = (dns_rbt_t *)isc_mem_get(mctx, sizeof(*rbt));
! 1005: if (rbt == NULL)
! 1006: return (ISC_R_NOMEMORY);
! 1007:
! 1008: rbt->mctx = NULL;
! 1009: isc_mem_attach(mctx, &rbt->mctx);
! 1010: rbt->data_deleter = deleter;
! 1011: rbt->deleter_arg = deleter_arg;
! 1012: rbt->root = NULL;
! 1013: rbt->nodecount = 0;
! 1014: rbt->hashtable = NULL;
! 1015: rbt->hashsize = 0;
! 1016: rbt->mmap_location = NULL;
! 1017:
! 1018: #ifdef DNS_RBT_USEHASH
! 1019: result = inithash(rbt);
! 1020: if (result != ISC_R_SUCCESS) {
! 1021: isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
! 1022: return (result);
! 1023: }
! 1024: #endif
! 1025:
! 1026: rbt->magic = RBT_MAGIC;
! 1027:
! 1028: *rbtp = rbt;
! 1029:
! 1030: return (ISC_R_SUCCESS);
! 1031: }
! 1032:
! 1033: /*
! 1034: * Deallocate a red/black tree of trees.
! 1035: */
! 1036: void
! 1037: dns_rbt_destroy(dns_rbt_t **rbtp) {
! 1038: RUNTIME_CHECK(dns_rbt_destroy2(rbtp, 0) == ISC_R_SUCCESS);
! 1039: }
! 1040:
! 1041: isc_result_t
! 1042: dns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum) {
! 1043: dns_rbt_t *rbt;
! 1044:
! 1045: REQUIRE(rbtp != NULL && VALID_RBT(*rbtp));
! 1046:
! 1047: rbt = *rbtp;
! 1048:
! 1049: deletetreeflat(rbt, quantum, ISC_FALSE, &rbt->root);
! 1050: if (rbt->root != NULL)
! 1051: return (ISC_R_QUOTA);
! 1052:
! 1053: INSIST(rbt->nodecount == 0);
! 1054:
! 1055: rbt->mmap_location = NULL;
! 1056:
! 1057: if (rbt->hashtable != NULL)
! 1058: isc_mem_put(rbt->mctx, rbt->hashtable,
! 1059: rbt->hashsize * sizeof(dns_rbtnode_t *));
! 1060:
! 1061: rbt->magic = 0;
! 1062:
! 1063: isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
! 1064: *rbtp = NULL;
! 1065: return (ISC_R_SUCCESS);
! 1066: }
! 1067:
! 1068: unsigned int
! 1069: dns_rbt_nodecount(dns_rbt_t *rbt) {
! 1070:
! 1071: REQUIRE(VALID_RBT(rbt));
! 1072:
! 1073: return (rbt->nodecount);
! 1074: }
! 1075:
! 1076: size_t
! 1077: dns_rbt_hashsize(dns_rbt_t *rbt) {
! 1078:
! 1079: REQUIRE(VALID_RBT(rbt));
! 1080:
! 1081: return (rbt->hashsize);
! 1082: }
! 1083:
! 1084: static inline isc_result_t
! 1085: chain_name(dns_rbtnodechain_t *chain, dns_name_t *name,
! 1086: isc_boolean_t include_chain_end)
! 1087: {
! 1088: dns_name_t nodename;
! 1089: isc_result_t result = ISC_R_SUCCESS;
! 1090: int i;
! 1091:
! 1092: dns_name_init(&nodename, NULL);
! 1093:
! 1094: if (include_chain_end && chain->end != NULL) {
! 1095: NODENAME(chain->end, &nodename);
! 1096: result = dns_name_copy(&nodename, name, NULL);
! 1097: if (result != ISC_R_SUCCESS)
! 1098: return (result);
! 1099: } else
! 1100: dns_name_reset(name);
! 1101:
! 1102: for (i = (int)chain->level_count - 1; i >= 0; i--) {
! 1103: NODENAME(chain->levels[i], &nodename);
! 1104: result = dns_name_concatenate(name, &nodename, name, NULL);
! 1105:
! 1106: if (result != ISC_R_SUCCESS)
! 1107: return (result);
! 1108: }
! 1109: return (result);
! 1110: }
! 1111:
! 1112: static inline isc_result_t
! 1113: move_chain_to_last(dns_rbtnodechain_t *chain, dns_rbtnode_t *node) {
! 1114: do {
! 1115: /*
! 1116: * Go as far right and then down as much as possible,
! 1117: * as long as the rightmost node has a down pointer.
! 1118: */
! 1119: while (RIGHT(node) != NULL)
! 1120: node = RIGHT(node);
! 1121:
! 1122: if (DOWN(node) == NULL)
! 1123: break;
! 1124:
! 1125: ADD_LEVEL(chain, node);
! 1126: node = DOWN(node);
! 1127: } while (1);
! 1128:
! 1129: chain->end = node;
! 1130:
! 1131: return (ISC_R_SUCCESS);
! 1132: }
! 1133:
! 1134: /*
! 1135: * Add 'name' to tree, initializing its data pointer with 'data'.
! 1136: */
! 1137:
! 1138: isc_result_t
! 1139: dns_rbt_addnode(dns_rbt_t *rbt, const dns_name_t *name, dns_rbtnode_t **nodep) {
! 1140: /*
! 1141: * Does this thing have too many variables or what?
! 1142: */
! 1143: dns_rbtnode_t **root, *parent, *child, *current, *new_current;
! 1144: dns_name_t *add_name, *new_name, current_name, *prefix, *suffix;
! 1145: dns_fixedname_t fixedcopy, fixedprefix, fixedsuffix, fnewname;
! 1146: dns_offsets_t current_offsets;
! 1147: dns_namereln_t compared;
! 1148: isc_result_t result = ISC_R_SUCCESS;
! 1149: unsigned int level_count;
! 1150: unsigned int common_labels;
! 1151: unsigned int nlabels, hlabels;
! 1152: int order;
! 1153:
! 1154: REQUIRE(VALID_RBT(rbt));
! 1155: REQUIRE(dns_name_isabsolute(name));
! 1156: REQUIRE(nodep != NULL && *nodep == NULL);
! 1157:
! 1158: /*
! 1159: * Dear future BIND developer,
! 1160: *
! 1161: * After you have tried attempting to optimize this routine by
! 1162: * using the hashtable and have realized your folly, please
! 1163: * append another cross ("X") below as a warning to the next
! 1164: * future BIND developer:
! 1165: *
! 1166: * Number of victim developers: X
! 1167: *
! 1168: * I wish the past developer had included such a notice.
! 1169: *
! 1170: * Long form: Unlike dns_rbt_findnode(), this function does not
! 1171: * lend itself to be optimized using the hashtable:
! 1172: *
! 1173: * 1. In the subtree where the insertion occurs, this function
! 1174: * needs to have the insertion point and the order where the
! 1175: * lookup terminated (i.e., at the insertion point where left or
! 1176: * right child is NULL). This cannot be determined from the
! 1177: * hashtable, so at least in that subtree, a BST O(log N) lookup
! 1178: * is necessary.
! 1179: *
! 1180: * 2. Our RBT nodes contain not only single labels but label
! 1181: * sequences to optimize space usage. So at every level, we have
! 1182: * to look for a match in the hashtable for all superdomains in
! 1183: * the rest of the name we're searching. This is an O(N)
! 1184: * operation at least, here N being the label size of name, each
! 1185: * of which is a hashtable lookup involving dns_name_equal()
! 1186: * comparisons.
! 1187: */
! 1188:
! 1189: /*
! 1190: * Create a copy of the name so the original name structure is
! 1191: * not modified.
! 1192: */
! 1193: add_name = dns_fixedname_initname(&fixedcopy);
! 1194: dns_name_clone(name, add_name);
! 1195:
! 1196: if (ISC_UNLIKELY(rbt->root == NULL)) {
! 1197: result = create_node(rbt->mctx, add_name, &new_current);
! 1198: if (result == ISC_R_SUCCESS) {
! 1199: rbt->nodecount++;
! 1200: new_current->is_root = 1;
! 1201: #ifdef DNS_RBT_USEHASH
! 1202: UPPERNODE(new_current) = NULL;
! 1203: #endif /* DNS_RBT_USEHASH */
! 1204: rbt->root = new_current;
! 1205: *nodep = new_current;
! 1206: hash_node(rbt, new_current, name);
! 1207: }
! 1208: return (result);
! 1209: }
! 1210:
! 1211: level_count = 0;
! 1212:
! 1213: prefix = dns_fixedname_initname(&fixedprefix);
! 1214: suffix = dns_fixedname_initname(&fixedsuffix);
! 1215:
! 1216: root = &rbt->root;
! 1217: INSIST(IS_ROOT(*root));
! 1218: parent = NULL;
! 1219: current = NULL;
! 1220: child = *root;
! 1221: dns_name_init(¤t_name, current_offsets);
! 1222: new_name = dns_fixedname_initname(&fnewname);
! 1223: nlabels = dns_name_countlabels(name);
! 1224: hlabels = 0;
! 1225:
! 1226: do {
! 1227: current = child;
! 1228:
! 1229: NODENAME(current, ¤t_name);
! 1230: compared = dns_name_fullcompare(add_name, ¤t_name,
! 1231: &order, &common_labels);
! 1232:
! 1233: if (compared == dns_namereln_equal) {
! 1234: *nodep = current;
! 1235: result = ISC_R_EXISTS;
! 1236: break;
! 1237:
! 1238: }
! 1239:
! 1240: if (compared == dns_namereln_none) {
! 1241:
! 1242: if (order < 0) {
! 1243: parent = current;
! 1244: child = LEFT(current);
! 1245:
! 1246: } else if (order > 0) {
! 1247: parent = current;
! 1248: child = RIGHT(current);
! 1249:
! 1250: }
! 1251:
! 1252: } else {
! 1253: /*
! 1254: * This name has some suffix in common with the
! 1255: * name at the current node. If the name at
! 1256: * the current node is shorter, that means the
! 1257: * new name should be in a subtree. If the
! 1258: * name at the current node is longer, that means
! 1259: * the down pointer to this tree should point
! 1260: * to a new tree that has the common suffix, and
! 1261: * the non-common parts of these two names should
! 1262: * start a new tree.
! 1263: */
! 1264: hlabels += common_labels;
! 1265: if (compared == dns_namereln_subdomain) {
! 1266: /*
! 1267: * All of the existing labels are in common,
! 1268: * so the new name is in a subtree.
! 1269: * Whack off the common labels for the
! 1270: * not-in-common part to be searched for
! 1271: * in the next level.
! 1272: */
! 1273: dns_name_split(add_name, common_labels,
! 1274: add_name, NULL);
! 1275:
! 1276: /*
! 1277: * Follow the down pointer (possibly NULL).
! 1278: */
! 1279: root = &DOWN(current);
! 1280:
! 1281: INSIST(*root == NULL ||
! 1282: (IS_ROOT(*root) &&
! 1283: PARENT(*root) == current));
! 1284:
! 1285: parent = NULL;
! 1286: child = DOWN(current);
! 1287:
! 1288: INSIST(level_count < DNS_RBT_LEVELBLOCK);
! 1289: level_count++;
! 1290: } else {
! 1291: /*
! 1292: * The number of labels in common is fewer
! 1293: * than the number of labels at the current
! 1294: * node, so the current node must be adjusted
! 1295: * to have just the common suffix, and a down
! 1296: * pointer made to a new tree.
! 1297: */
! 1298:
! 1299: INSIST(compared == dns_namereln_commonancestor
! 1300: || compared == dns_namereln_contains);
! 1301:
! 1302: /*
! 1303: * Ensure the number of levels in the tree
! 1304: * does not exceed the number of logical
! 1305: * levels allowed by DNSSEC.
! 1306: *
! 1307: * XXXDCL need a better error result?
! 1308: */
! 1309: if (level_count >= DNS_RBT_LEVELBLOCK) {
! 1310: result = ISC_R_NOSPACE;
! 1311: break;
! 1312: }
! 1313:
! 1314: /*
! 1315: * Split the name into two parts, a prefix
! 1316: * which is the not-in-common parts of the
! 1317: * two names and a suffix that is the common
! 1318: * parts of them.
! 1319: */
! 1320: dns_name_split(¤t_name, common_labels,
! 1321: prefix, suffix);
! 1322: result = create_node(rbt->mctx, suffix,
! 1323: &new_current);
! 1324:
! 1325: if (result != ISC_R_SUCCESS)
! 1326: break;
! 1327:
! 1328: /*
! 1329: * Reproduce the tree attributes of the
! 1330: * current node.
! 1331: */
! 1332: new_current->is_root = current->is_root;
! 1333: if (current->nsec == DNS_RBT_NSEC_HAS_NSEC)
! 1334: new_current->nsec = DNS_RBT_NSEC_NORMAL;
! 1335: else
! 1336: new_current->nsec = current->nsec;
! 1337: PARENT(new_current) = PARENT(current);
! 1338: LEFT(new_current) = LEFT(current);
! 1339: RIGHT(new_current) = RIGHT(current);
! 1340: COLOR(new_current) = COLOR(current);
! 1341:
! 1342: /*
! 1343: * Fix pointers that were to the current node.
! 1344: */
! 1345: if (parent != NULL) {
! 1346: if (LEFT(parent) == current)
! 1347: LEFT(parent) = new_current;
! 1348: else
! 1349: RIGHT(parent) = new_current;
! 1350: }
! 1351: if (LEFT(new_current) != NULL)
! 1352: PARENT(LEFT(new_current)) =
! 1353: new_current;
! 1354: if (RIGHT(new_current) != NULL)
! 1355: PARENT(RIGHT(new_current)) =
! 1356: new_current;
! 1357: if (*root == current)
! 1358: *root = new_current;
! 1359:
! 1360: NAMELEN(current) = prefix->length;
! 1361: OFFSETLEN(current) = prefix->labels;
! 1362:
! 1363: /*
! 1364: * Set up the new root of the next level.
! 1365: * By definition it will not be the top
! 1366: * level tree, so clear DNS_NAMEATTR_ABSOLUTE.
! 1367: */
! 1368: current->is_root = 1;
! 1369: PARENT(current) = new_current;
! 1370: DOWN(new_current) = current;
! 1371: root = &DOWN(new_current);
! 1372: #ifdef DNS_RBT_USEHASH
! 1373: UPPERNODE(new_current) = UPPERNODE(current);
! 1374: UPPERNODE(current) = new_current;
! 1375: #endif /* DNS_RBT_USEHASH */
! 1376:
! 1377: INSIST(level_count < DNS_RBT_LEVELBLOCK);
! 1378: level_count++;
! 1379:
! 1380: LEFT(current) = NULL;
! 1381: RIGHT(current) = NULL;
! 1382:
! 1383: MAKE_BLACK(current);
! 1384: ATTRS(current) &= ~DNS_NAMEATTR_ABSOLUTE;
! 1385:
! 1386: rbt->nodecount++;
! 1387: dns_name_getlabelsequence(name,
! 1388: nlabels - hlabels,
! 1389: hlabels, new_name);
! 1390: hash_node(rbt, new_current, new_name);
! 1391:
! 1392: if (common_labels ==
! 1393: dns_name_countlabels(add_name)) {
! 1394: /*
! 1395: * The name has been added by pushing
! 1396: * the not-in-common parts down to
! 1397: * a new level.
! 1398: */
! 1399: *nodep = new_current;
! 1400: return (ISC_R_SUCCESS);
! 1401:
! 1402: } else {
! 1403: /*
! 1404: * The current node has no data,
! 1405: * because it is just a placeholder.
! 1406: * Its data pointer is already NULL
! 1407: * from create_node()), so there's
! 1408: * nothing more to do to it.
! 1409: */
! 1410:
! 1411: /*
! 1412: * The not-in-common parts of the new
! 1413: * name will be inserted into the new
! 1414: * level following this loop (unless
! 1415: * result != ISC_R_SUCCESS, which
! 1416: * is tested after the loop ends).
! 1417: */
! 1418: dns_name_split(add_name, common_labels,
! 1419: add_name, NULL);
! 1420:
! 1421: break;
! 1422: }
! 1423:
! 1424: }
! 1425:
! 1426: }
! 1427:
! 1428: } while (ISC_LIKELY(child != NULL));
! 1429:
! 1430: if (ISC_LIKELY(result == ISC_R_SUCCESS))
! 1431: result = create_node(rbt->mctx, add_name, &new_current);
! 1432:
! 1433: if (ISC_LIKELY(result == ISC_R_SUCCESS)) {
! 1434: #ifdef DNS_RBT_USEHASH
! 1435: if (*root == NULL)
! 1436: UPPERNODE(new_current) = current;
! 1437: else
! 1438: UPPERNODE(new_current) = PARENT(*root);
! 1439: #endif /* DNS_RBT_USEHASH */
! 1440: addonlevel(new_current, current, order, root);
! 1441: rbt->nodecount++;
! 1442: *nodep = new_current;
! 1443: hash_node(rbt, new_current, name);
! 1444: }
! 1445:
! 1446: return (result);
! 1447: }
! 1448:
! 1449: /*
! 1450: * Add a name to the tree of trees, associating it with some data.
! 1451: */
! 1452: isc_result_t
! 1453: dns_rbt_addname(dns_rbt_t *rbt, const dns_name_t *name, void *data) {
! 1454: isc_result_t result;
! 1455: dns_rbtnode_t *node;
! 1456:
! 1457: REQUIRE(VALID_RBT(rbt));
! 1458: REQUIRE(dns_name_isabsolute(name));
! 1459:
! 1460: node = NULL;
! 1461:
! 1462: result = dns_rbt_addnode(rbt, name, &node);
! 1463:
! 1464: /*
! 1465: * dns_rbt_addnode will report the node exists even when
! 1466: * it does not have data associated with it, but the
! 1467: * dns_rbt_*name functions all behave depending on whether
! 1468: * there is data associated with a node.
! 1469: */
! 1470: if (result == ISC_R_SUCCESS ||
! 1471: (result == ISC_R_EXISTS && DATA(node) == NULL)) {
! 1472: DATA(node) = data;
! 1473: result = ISC_R_SUCCESS;
! 1474: }
! 1475:
! 1476: return (result);
! 1477: }
! 1478:
! 1479: /*
! 1480: * Find the node for "name" in the tree of trees.
! 1481: */
! 1482: isc_result_t
! 1483: dns_rbt_findnode(dns_rbt_t *rbt, const dns_name_t *name, dns_name_t *foundname,
! 1484: dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
! 1485: unsigned int options, dns_rbtfindcallback_t callback,
! 1486: void *callback_arg)
! 1487: {
! 1488: dns_rbtnode_t *current, *last_compared;
! 1489: dns_rbtnodechain_t localchain;
! 1490: dns_name_t *search_name, current_name, *callback_name;
! 1491: dns_fixedname_t fixedcallbackname, fixedsearchname;
! 1492: dns_namereln_t compared;
! 1493: isc_result_t result, saved_result;
! 1494: unsigned int common_labels;
! 1495: unsigned int hlabels = 0;
! 1496: int order;
! 1497:
! 1498: REQUIRE(VALID_RBT(rbt));
! 1499: REQUIRE(dns_name_isabsolute(name));
! 1500: REQUIRE(node != NULL && *node == NULL);
! 1501: REQUIRE((options & (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR))
! 1502: != (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR));
! 1503:
! 1504: /*
! 1505: * If there is a chain it needs to appear to be in a sane state,
! 1506: * otherwise a chain is still needed to generate foundname and
! 1507: * callback_name.
! 1508: */
! 1509: if (chain == NULL) {
! 1510: options |= DNS_RBTFIND_NOPREDECESSOR;
! 1511: chain = &localchain;
! 1512: dns_rbtnodechain_init(chain, rbt->mctx);
! 1513: } else
! 1514: dns_rbtnodechain_reset(chain);
! 1515:
! 1516: if (ISC_UNLIKELY(rbt->root == NULL))
! 1517: return (ISC_R_NOTFOUND);
! 1518:
! 1519: /*
! 1520: * Appease GCC about variables it incorrectly thinks are
! 1521: * possibly used uninitialized.
! 1522: */
! 1523: compared = dns_namereln_none;
! 1524: last_compared = NULL;
! 1525: order = 0;
! 1526:
! 1527: callback_name = dns_fixedname_initname(&fixedcallbackname);
! 1528:
! 1529: /*
! 1530: * search_name is the name segment being sought in each tree level.
! 1531: * By using a fixedname, the search_name will definitely have offsets
! 1532: * for use by any splitting.
! 1533: * By using dns_name_clone, no name data should be copied thanks to
! 1534: * the lack of bitstring labels.
! 1535: */
! 1536: search_name = dns_fixedname_initname(&fixedsearchname);
! 1537: dns_name_clone(name, search_name);
! 1538:
! 1539: dns_name_init(¤t_name, NULL);
! 1540:
! 1541: saved_result = ISC_R_SUCCESS;
! 1542: current = rbt->root;
! 1543:
! 1544: while (ISC_LIKELY(current != NULL)) {
! 1545: NODENAME(current, ¤t_name);
! 1546: compared = dns_name_fullcompare(search_name, ¤t_name,
! 1547: &order, &common_labels);
! 1548: /*
! 1549: * last_compared is used as a shortcut to start (or
! 1550: * continue rather) finding the stop-node of the search
! 1551: * when hashing was used (see much below in this
! 1552: * function).
! 1553: */
! 1554: last_compared = current;
! 1555:
! 1556: if (compared == dns_namereln_equal)
! 1557: break;
! 1558:
! 1559: if (compared == dns_namereln_none) {
! 1560: #ifdef DNS_RBT_USEHASH
! 1561: /*
! 1562: * Here, current is pointing at a subtree root
! 1563: * node. We try to find a matching node using
! 1564: * the hashtable. We can get one of 3 results
! 1565: * here: (a) we locate the matching node, (b) we
! 1566: * find a node to which the current node has a
! 1567: * subdomain relation, (c) we fail to find (a)
! 1568: * or (b).
! 1569: */
! 1570:
! 1571: dns_name_t hash_name;
! 1572: dns_rbtnode_t *hnode;
! 1573: dns_rbtnode_t *up_current;
! 1574: unsigned int nlabels;
! 1575: unsigned int tlabels = 1;
! 1576: unsigned int hash;
! 1577:
! 1578: /*
! 1579: * The case of current not being a subtree root,
! 1580: * that means a left or right pointer was
! 1581: * followed, only happens when the algorithm
! 1582: * fell through to the traditional binary search
! 1583: * because of a bitstring label. Since we
! 1584: * dropped the bitstring support, this should
! 1585: * not happen.
! 1586: */
! 1587: INSIST(IS_ROOT(current));
! 1588:
! 1589: nlabels = dns_name_countlabels(search_name);
! 1590:
! 1591: /*
! 1592: * current is the root of the current level, so
! 1593: * its parent is the same as its "up" pointer.
! 1594: */
! 1595: up_current = PARENT(current);
! 1596: dns_name_init(&hash_name, NULL);
! 1597:
! 1598: hashagain:
! 1599: /*
! 1600: * Compute the hash over the full absolute
! 1601: * name. Look for the smallest suffix match at
! 1602: * this tree level (hlevel), and then at every
! 1603: * iteration, look for the next smallest suffix
! 1604: * match (add another subdomain label to the
! 1605: * absolute name being hashed).
! 1606: */
! 1607: dns_name_getlabelsequence(name,
! 1608: nlabels - tlabels,
! 1609: hlabels + tlabels,
! 1610: &hash_name);
! 1611: hash = dns_name_fullhash(&hash_name, ISC_FALSE);
! 1612: dns_name_getlabelsequence(search_name,
! 1613: nlabels - tlabels,
! 1614: tlabels, &hash_name);
! 1615:
! 1616: /*
! 1617: * Walk all the nodes in the hash bucket pointed
! 1618: * by the computed hash value.
! 1619: */
! 1620: for (hnode = rbt->hashtable[hash % rbt->hashsize];
! 1621: hnode != NULL;
! 1622: hnode = hnode->hashnext)
! 1623: {
! 1624: dns_name_t hnode_name;
! 1625:
! 1626: if (ISC_LIKELY(hash != HASHVAL(hnode)))
! 1627: continue;
! 1628: /*
! 1629: * This checks that the hashed label
! 1630: * sequence being looked up is at the
! 1631: * same tree level, so that we don't
! 1632: * match a labelsequence from some other
! 1633: * subdomain.
! 1634: */
! 1635: if (ISC_LIKELY(get_upper_node(hnode) != up_current))
! 1636: continue;
! 1637:
! 1638: dns_name_init(&hnode_name, NULL);
! 1639: NODENAME(hnode, &hnode_name);
! 1640: if (ISC_LIKELY(dns_name_equal(&hnode_name, &hash_name)))
! 1641: break;
! 1642: }
! 1643:
! 1644: if (hnode != NULL) {
! 1645: current = hnode;
! 1646: /*
! 1647: * This is an optimization. If hashing found
! 1648: * the right node, the next call to
! 1649: * dns_name_fullcompare() would obviously
! 1650: * return _equal or _subdomain. Determine
! 1651: * which of those would be the case by
! 1652: * checking if the full name was hashed. Then
! 1653: * make it look like dns_name_fullcompare
! 1654: * was called and jump to the right place.
! 1655: */
! 1656: if (tlabels == nlabels) {
! 1657: compared = dns_namereln_equal;
! 1658: break;
! 1659: } else {
! 1660: common_labels = tlabels;
! 1661: compared = dns_namereln_subdomain;
! 1662: goto subdomain;
! 1663: }
! 1664: }
! 1665:
! 1666: if (tlabels++ < nlabels)
! 1667: goto hashagain;
! 1668:
! 1669: /*
! 1670: * All of the labels have been tried against the hash
! 1671: * table. Since we dropped the support of bitstring
! 1672: * labels, the name isn't in the table.
! 1673: */
! 1674: current = NULL;
! 1675: continue;
! 1676:
! 1677: #else /* DNS_RBT_USEHASH */
! 1678:
! 1679: /*
! 1680: * Standard binary search tree movement.
! 1681: */
! 1682: if (order < 0)
! 1683: current = LEFT(current);
! 1684: else
! 1685: current = RIGHT(current);
! 1686:
! 1687: #endif /* DNS_RBT_USEHASH */
! 1688:
! 1689: } else {
! 1690: /*
! 1691: * The names have some common suffix labels.
! 1692: *
! 1693: * If the number in common are equal in length to
! 1694: * the current node's name length, then follow the
! 1695: * down pointer and search in the new tree.
! 1696: */
! 1697: if (compared == dns_namereln_subdomain) {
! 1698: #ifdef DNS_RBT_USEHASH
! 1699: subdomain:
! 1700: #endif
! 1701: /*
! 1702: * Whack off the current node's common parts
! 1703: * for the name to search in the next level.
! 1704: */
! 1705: dns_name_split(search_name, common_labels,
! 1706: search_name, NULL);
! 1707: hlabels += common_labels;
! 1708: /*
! 1709: * This might be the closest enclosing name.
! 1710: */
! 1711: if (DATA(current) != NULL ||
! 1712: (options & DNS_RBTFIND_EMPTYDATA) != 0)
! 1713: *node = current;
! 1714:
! 1715: /*
! 1716: * Point the chain to the next level. This
! 1717: * needs to be done before 'current' is pointed
! 1718: * there because the callback in the next
! 1719: * block of code needs the current 'current',
! 1720: * but in the event the callback requests that
! 1721: * the search be stopped then the
! 1722: * DNS_R_PARTIALMATCH code at the end of this
! 1723: * function needs the chain pointed to the
! 1724: * next level.
! 1725: */
! 1726: ADD_LEVEL(chain, current);
! 1727:
! 1728: /*
! 1729: * The caller may want to interrupt the
! 1730: * downward search when certain special nodes
! 1731: * are traversed. If this is a special node,
! 1732: * the callback is used to learn what the
! 1733: * caller wants to do.
! 1734: */
! 1735: if (callback != NULL &&
! 1736: FINDCALLBACK(current)) {
! 1737: result = chain_name(chain,
! 1738: callback_name,
! 1739: ISC_FALSE);
! 1740: if (result != ISC_R_SUCCESS) {
! 1741: dns_rbtnodechain_reset(chain);
! 1742: return (result);
! 1743: }
! 1744:
! 1745: result = (callback)(current,
! 1746: callback_name,
! 1747: callback_arg);
! 1748: if (result != DNS_R_CONTINUE) {
! 1749: saved_result = result;
! 1750: /*
! 1751: * Treat this node as if it
! 1752: * had no down pointer.
! 1753: */
! 1754: current = NULL;
! 1755: break;
! 1756: }
! 1757: }
! 1758:
! 1759: /*
! 1760: * Finally, head to the next tree level.
! 1761: */
! 1762: current = DOWN(current);
! 1763: } else {
! 1764: /*
! 1765: * Though there are labels in common, the
! 1766: * entire name at this node is not common
! 1767: * with the search name so the search
! 1768: * name does not exist in the tree.
! 1769: */
! 1770: INSIST(compared == dns_namereln_commonancestor
! 1771: || compared == dns_namereln_contains);
! 1772:
! 1773: current = NULL;
! 1774: }
! 1775: }
! 1776: }
! 1777:
! 1778: /*
! 1779: * If current is not NULL, NOEXACT is not disallowing exact matches,
! 1780: * and either the node has data or an empty node is ok, return
! 1781: * ISC_R_SUCCESS to indicate an exact match.
! 1782: */
! 1783: if (current != NULL && (options & DNS_RBTFIND_NOEXACT) == 0 &&
! 1784: (DATA(current) != NULL ||
! 1785: (options & DNS_RBTFIND_EMPTYDATA) != 0)) {
! 1786: /*
! 1787: * Found an exact match.
! 1788: */
! 1789: chain->end = current;
! 1790: chain->level_matches = chain->level_count;
! 1791:
! 1792: if (foundname != NULL)
! 1793: result = chain_name(chain, foundname, ISC_TRUE);
! 1794: else
! 1795: result = ISC_R_SUCCESS;
! 1796:
! 1797: if (result == ISC_R_SUCCESS) {
! 1798: *node = current;
! 1799: result = saved_result;
! 1800: } else
! 1801: *node = NULL;
! 1802: } else {
! 1803: /*
! 1804: * Did not find an exact match (or did not want one).
! 1805: */
! 1806: if (*node != NULL) {
! 1807: /*
! 1808: * ... but found a partially matching superdomain.
! 1809: * Unwind the chain to the partial match node
! 1810: * to set level_matches to the level above the node,
! 1811: * and then to derive the name.
! 1812: *
! 1813: * chain->level_count is guaranteed to be at least 1
! 1814: * here because by definition of finding a superdomain,
! 1815: * the chain is pointed to at least the first subtree.
! 1816: */
! 1817: chain->level_matches = chain->level_count - 1;
! 1818:
! 1819: while (chain->levels[chain->level_matches] != *node) {
! 1820: INSIST(chain->level_matches > 0);
! 1821: chain->level_matches--;
! 1822: }
! 1823:
! 1824: if (foundname != NULL) {
! 1825: unsigned int saved_count = chain->level_count;
! 1826:
! 1827: chain->level_count = chain->level_matches + 1;
! 1828:
! 1829: result = chain_name(chain, foundname,
! 1830: ISC_FALSE);
! 1831:
! 1832: chain->level_count = saved_count;
! 1833: } else
! 1834: result = ISC_R_SUCCESS;
! 1835:
! 1836: if (result == ISC_R_SUCCESS)
! 1837: result = DNS_R_PARTIALMATCH;
! 1838:
! 1839: } else
! 1840: result = ISC_R_NOTFOUND;
! 1841:
! 1842: if (current != NULL) {
! 1843: /*
! 1844: * There was an exact match but either
! 1845: * DNS_RBTFIND_NOEXACT was set, or
! 1846: * DNS_RBTFIND_EMPTYDATA was set and the node had no
! 1847: * data. A policy decision was made to set the
! 1848: * chain to the exact match, but this is subject
! 1849: * to change if it becomes apparent that something
! 1850: * else would be more useful. It is important that
! 1851: * this case is handled here, because the predecessor
! 1852: * setting code below assumes the match was not exact.
! 1853: */
! 1854: INSIST(((options & DNS_RBTFIND_NOEXACT) != 0) ||
! 1855: ((options & DNS_RBTFIND_EMPTYDATA) == 0 &&
! 1856: DATA(current) == NULL));
! 1857: chain->end = current;
! 1858:
! 1859: } else if ((options & DNS_RBTFIND_NOPREDECESSOR) != 0) {
! 1860: /*
! 1861: * Ensure the chain points nowhere.
! 1862: */
! 1863: chain->end = NULL;
! 1864:
! 1865: } else {
! 1866: /*
! 1867: * Since there was no exact match, the chain argument
! 1868: * needs to be pointed at the DNSSEC predecessor of
! 1869: * the search name.
! 1870: */
! 1871: if (compared == dns_namereln_subdomain) {
! 1872: /*
! 1873: * Attempted to follow a down pointer that was
! 1874: * NULL, which means the searched for name was
! 1875: * a subdomain of a terminal name in the tree.
! 1876: * Since there are no existing subdomains to
! 1877: * order against, the terminal name is the
! 1878: * predecessor.
! 1879: */
! 1880: INSIST(chain->level_count > 0);
! 1881: INSIST(chain->level_matches <
! 1882: chain->level_count);
! 1883: chain->end =
! 1884: chain->levels[--chain->level_count];
! 1885:
! 1886: } else {
! 1887: isc_result_t result2;
! 1888:
! 1889: /*
! 1890: * Point current to the node that stopped
! 1891: * the search.
! 1892: *
! 1893: * With the hashing modification that has been
! 1894: * added to the algorithm, the stop node of a
! 1895: * standard binary search is not known. So it
! 1896: * has to be found. There is probably a more
! 1897: * clever way of doing this.
! 1898: *
! 1899: * The assignment of current to NULL when
! 1900: * the relationship is *not* dns_namereln_none,
! 1901: * even though it later gets set to the same
! 1902: * last_compared anyway, is simply to not push
! 1903: * the while loop in one more level of
! 1904: * indentation.
! 1905: */
! 1906: if (compared == dns_namereln_none)
! 1907: current = last_compared;
! 1908: else
! 1909: current = NULL;
! 1910:
! 1911: while (current != NULL) {
! 1912: NODENAME(current, ¤t_name);
! 1913: compared = dns_name_fullcompare(
! 1914: search_name,
! 1915: ¤t_name,
! 1916: &order,
! 1917: &common_labels);
! 1918: POST(compared);
! 1919:
! 1920: last_compared = current;
! 1921:
! 1922: /*
! 1923: * Standard binary search movement.
! 1924: */
! 1925: if (order < 0)
! 1926: current = LEFT(current);
! 1927: else
! 1928: current = RIGHT(current);
! 1929:
! 1930: }
! 1931:
! 1932: current = last_compared;
! 1933:
! 1934: /*
! 1935: * Reached a point within a level tree that
! 1936: * positively indicates the name is not
! 1937: * present, but the stop node could be either
! 1938: * less than the desired name (order > 0) or
! 1939: * greater than the desired name (order < 0).
! 1940: *
! 1941: * If the stop node is less, it is not
! 1942: * necessarily the predecessor. If the stop
! 1943: * node has a down pointer, then the real
! 1944: * predecessor is at the end of a level below
! 1945: * (not necessarily the next level).
! 1946: * Move down levels until the rightmost node
! 1947: * does not have a down pointer.
! 1948: *
! 1949: * When the stop node is greater, it is
! 1950: * the successor. All the logic for finding
! 1951: * the predecessor is handily encapsulated
! 1952: * in dns_rbtnodechain_prev. In the event
! 1953: * that the search name is less than anything
! 1954: * else in the tree, the chain is reset.
! 1955: * XXX DCL What is the best way for the caller
! 1956: * to know that the search name has
! 1957: * no predecessor?
! 1958: */
! 1959:
! 1960:
! 1961: if (order > 0) {
! 1962: if (DOWN(current) != NULL) {
! 1963: ADD_LEVEL(chain, current);
! 1964:
! 1965: result2 =
! 1966: move_chain_to_last(chain,
! 1967: DOWN(current));
! 1968:
! 1969: if (result2 != ISC_R_SUCCESS)
! 1970: result = result2;
! 1971: } else
! 1972: /*
! 1973: * Ah, the pure and simple
! 1974: * case. The stop node is the
! 1975: * predecessor.
! 1976: */
! 1977: chain->end = current;
! 1978:
! 1979: } else {
! 1980: INSIST(order < 0);
! 1981:
! 1982: chain->end = current;
! 1983:
! 1984: result2 = dns_rbtnodechain_prev(chain,
! 1985: NULL,
! 1986: NULL);
! 1987: if (result2 == ISC_R_SUCCESS ||
! 1988: result2 == DNS_R_NEWORIGIN)
! 1989: ; /* Nothing. */
! 1990: else if (result2 == ISC_R_NOMORE)
! 1991: /*
! 1992: * There is no predecessor.
! 1993: */
! 1994: dns_rbtnodechain_reset(chain);
! 1995: else
! 1996: result = result2;
! 1997: }
! 1998:
! 1999: }
! 2000: }
! 2001: }
! 2002:
! 2003: ENSURE(*node == NULL || DNS_RBTNODE_VALID(*node));
! 2004:
! 2005: return (result);
! 2006: }
! 2007:
! 2008: /*
! 2009: * Get the data pointer associated with 'name'.
! 2010: */
! 2011: isc_result_t
! 2012: dns_rbt_findname(dns_rbt_t *rbt, const dns_name_t *name, unsigned int options,
! 2013: dns_name_t *foundname, void **data) {
! 2014: dns_rbtnode_t *node = NULL;
! 2015: isc_result_t result;
! 2016:
! 2017: REQUIRE(data != NULL && *data == NULL);
! 2018:
! 2019: result = dns_rbt_findnode(rbt, name, foundname, &node, NULL,
! 2020: options, NULL, NULL);
! 2021:
! 2022: if (node != NULL &&
! 2023: (DATA(node) != NULL || (options & DNS_RBTFIND_EMPTYDATA) != 0))
! 2024: *data = DATA(node);
! 2025: else
! 2026: result = ISC_R_NOTFOUND;
! 2027:
! 2028: return (result);
! 2029: }
! 2030:
! 2031: /*
! 2032: * Delete a name from the tree of trees.
! 2033: */
! 2034: isc_result_t
! 2035: dns_rbt_deletename(dns_rbt_t *rbt, const dns_name_t *name,
! 2036: isc_boolean_t recurse)
! 2037: {
! 2038: dns_rbtnode_t *node = NULL;
! 2039: isc_result_t result;
! 2040:
! 2041: REQUIRE(VALID_RBT(rbt));
! 2042: REQUIRE(dns_name_isabsolute(name));
! 2043:
! 2044: /*
! 2045: * First, find the node.
! 2046: *
! 2047: * When searching, the name might not have an exact match:
! 2048: * consider a.b.a.com, b.b.a.com and c.b.a.com as the only
! 2049: * elements of a tree, which would make layer 1 a single
! 2050: * node tree of "b.a.com" and layer 2 a three node tree of
! 2051: * a, b, and c. Deleting a.com would find only a partial depth
! 2052: * match in the first layer. Should it be a requirement that
! 2053: * that the name to be deleted have data? For now, it is.
! 2054: *
! 2055: * ->dirty, ->locknum and ->references are ignored; they are
! 2056: * solely the province of rbtdb.c.
! 2057: */
! 2058: result = dns_rbt_findnode(rbt, name, NULL, &node, NULL,
! 2059: DNS_RBTFIND_NOOPTIONS, NULL, NULL);
! 2060:
! 2061: if (result == ISC_R_SUCCESS) {
! 2062: if (DATA(node) != NULL)
! 2063: result = dns_rbt_deletenode(rbt, node, recurse);
! 2064: else
! 2065: result = ISC_R_NOTFOUND;
! 2066:
! 2067: } else if (result == DNS_R_PARTIALMATCH)
! 2068: result = ISC_R_NOTFOUND;
! 2069:
! 2070: return (result);
! 2071: }
! 2072:
! 2073: /*
! 2074: * Remove a node from the tree of trees.
! 2075: *
! 2076: * NOTE WELL: deletion is *not* symmetric with addition; that is, reversing
! 2077: * a sequence of additions to be deletions will not generally get the
! 2078: * tree back to the state it started in. For example, if the addition
! 2079: * of "b.c" caused the node "a.b.c" to be split, pushing "a" to its own level,
! 2080: * then the subsequent deletion of "b.c" will not cause "a" to be pulled up,
! 2081: * restoring "a.b.c". The RBT *used* to do this kind of rejoining, but it
! 2082: * turned out to be a bad idea because it could corrupt an active nodechain
! 2083: * that had "b.c" as one of its levels -- and the RBT has no idea what
! 2084: * nodechains are in use by callers, so it can't even *try* to helpfully
! 2085: * fix them up (which would probably be doomed to failure anyway).
! 2086: *
! 2087: * Similarly, it is possible to leave the tree in a state where a supposedly
! 2088: * deleted node still exists. The first case of this is obvious; take
! 2089: * the tree which has "b.c" on one level, pointing to "a". Now deleted "b.c".
! 2090: * It was just established in the previous paragraph why we can't pull "a"
! 2091: * back up to its parent level. But what happens when "a" then gets deleted?
! 2092: * "b.c" is left hanging around without data or children. This condition
! 2093: * is actually pretty easy to detect, but ... should it really be removed?
! 2094: * Is a chain pointing to it? An iterator? Who knows! (Note that the
! 2095: * references structure member cannot be looked at because it is private to
! 2096: * rbtdb.) This is ugly and makes me unhappy, but after hours of trying to
! 2097: * make it more aesthetically proper and getting nowhere, this is the way it
! 2098: * is going to stay until such time as it proves to be a *real* problem.
! 2099: *
! 2100: * Finally, for reference, note that the original routine that did node
! 2101: * joining was called join_nodes(). It has been excised, living now only
! 2102: * in the CVS history, but comments have been left behind that point to it just
! 2103: * in case someone wants to muck with this some more.
! 2104: *
! 2105: * The one positive aspect of all of this is that joining used to have a
! 2106: * case where it might fail. Without trying to join, now this function always
! 2107: * succeeds. It still returns isc_result_t, though, so the API wouldn't change.
! 2108: */
! 2109: isc_result_t
! 2110: dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse)
! 2111: {
! 2112: dns_rbtnode_t *parent;
! 2113:
! 2114: REQUIRE(VALID_RBT(rbt));
! 2115: REQUIRE(DNS_RBTNODE_VALID(node));
! 2116: INSIST(rbt->nodecount != 0);
! 2117:
! 2118: if (DOWN(node) != NULL) {
! 2119: if (recurse) {
! 2120: PARENT(DOWN(node)) = NULL;
! 2121: deletetreeflat(rbt, 0, ISC_TRUE, &DOWN(node));
! 2122: } else {
! 2123: if (DATA(node) != NULL && rbt->data_deleter != NULL)
! 2124: rbt->data_deleter(DATA(node), rbt->deleter_arg);
! 2125: DATA(node) = NULL;
! 2126:
! 2127: /*
! 2128: * Since there is at least one node below this one and
! 2129: * no recursion was requested, the deletion is
! 2130: * complete. The down node from this node might be all
! 2131: * by itself on a single level, so join_nodes() could
! 2132: * be used to collapse the tree (with all the caveats
! 2133: * of the comment at the start of this function).
! 2134: * But join_nodes() function has now been removed.
! 2135: */
! 2136: return (ISC_R_SUCCESS);
! 2137: }
! 2138: }
! 2139:
! 2140: /*
! 2141: * Note the node that points to the level of the node
! 2142: * that is being deleted. If the deleted node is the
! 2143: * top level, parent will be set to NULL.
! 2144: */
! 2145: parent = get_upper_node(node);
! 2146:
! 2147: /*
! 2148: * This node now has no down pointer, so now it needs
! 2149: * to be removed from this level.
! 2150: */
! 2151: deletefromlevel(node, parent == NULL ? &rbt->root : &DOWN(parent));
! 2152:
! 2153: if (DATA(node) != NULL && rbt->data_deleter != NULL)
! 2154: rbt->data_deleter(DATA(node), rbt->deleter_arg);
! 2155:
! 2156: unhash_node(rbt, node);
! 2157: #if DNS_RBT_USEMAGIC
! 2158: node->magic = 0;
! 2159: #endif
! 2160: dns_rbtnode_refdestroy(node);
! 2161:
! 2162: freenode(rbt, &node);
! 2163:
! 2164: /*
! 2165: * This function never fails.
! 2166: */
! 2167: return (ISC_R_SUCCESS);
! 2168: }
! 2169:
! 2170: void
! 2171: dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name) {
! 2172:
! 2173: REQUIRE(DNS_RBTNODE_VALID(node));
! 2174: REQUIRE(name != NULL);
! 2175: REQUIRE(name->offsets == NULL);
! 2176:
! 2177: NODENAME(node, name);
! 2178: }
! 2179:
! 2180: isc_result_t
! 2181: dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name) {
! 2182: dns_name_t current;
! 2183: isc_result_t result;
! 2184:
! 2185: REQUIRE(DNS_RBTNODE_VALID(node));
! 2186: REQUIRE(name != NULL);
! 2187: REQUIRE(name->buffer != NULL);
! 2188:
! 2189: dns_name_init(¤t, NULL);
! 2190: dns_name_reset(name);
! 2191:
! 2192: do {
! 2193: INSIST(node != NULL);
! 2194:
! 2195: NODENAME(node, ¤t);
! 2196:
! 2197: result = dns_name_concatenate(name, ¤t, name, NULL);
! 2198: if (result != ISC_R_SUCCESS)
! 2199: break;
! 2200:
! 2201: node = get_upper_node(node);
! 2202: } while (! dns_name_isabsolute(name));
! 2203:
! 2204: return (result);
! 2205: }
! 2206:
! 2207: char *
! 2208: dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname, unsigned int size)
! 2209: {
! 2210: dns_fixedname_t fixedname;
! 2211: dns_name_t *name;
! 2212: isc_result_t result;
! 2213:
! 2214: REQUIRE(DNS_RBTNODE_VALID(node));
! 2215: REQUIRE(printname != NULL);
! 2216:
! 2217: name = dns_fixedname_initname(&fixedname);
! 2218: result = dns_rbt_fullnamefromnode(node, name);
! 2219: if (result == ISC_R_SUCCESS)
! 2220: dns_name_format(name, printname, size);
! 2221: else
! 2222: snprintf(printname, size, "<error building name: %s>",
! 2223: dns_result_totext(result));
! 2224:
! 2225: return (printname);
! 2226: }
! 2227:
! 2228: static isc_result_t
! 2229: create_node(isc_mem_t *mctx, const dns_name_t *name, dns_rbtnode_t **nodep) {
! 2230: dns_rbtnode_t *node;
! 2231: isc_region_t region;
! 2232: unsigned int labels;
! 2233: size_t nodelen;
! 2234:
! 2235: REQUIRE(name->offsets != NULL);
! 2236:
! 2237: dns_name_toregion(name, ®ion);
! 2238: labels = dns_name_countlabels(name);
! 2239: ENSURE(labels > 0);
! 2240:
! 2241: /*
! 2242: * Allocate space for the node structure, the name, and the offsets.
! 2243: */
! 2244: nodelen = sizeof(dns_rbtnode_t) + region.length + labels + 1;
! 2245: node = (dns_rbtnode_t *)isc_mem_get(mctx, nodelen);
! 2246: if (node == NULL)
! 2247: return (ISC_R_NOMEMORY);
! 2248: memset(node, 0, nodelen);
! 2249:
! 2250: node->is_root = 0;
! 2251: PARENT(node) = NULL;
! 2252: RIGHT(node) = NULL;
! 2253: LEFT(node) = NULL;
! 2254: DOWN(node) = NULL;
! 2255: DATA(node) = NULL;
! 2256: node->is_mmapped = 0;
! 2257: node->down_is_relative = 0;
! 2258: node->left_is_relative = 0;
! 2259: node->right_is_relative = 0;
! 2260: node->parent_is_relative = 0;
! 2261: node->data_is_relative = 0;
! 2262: node->rpz = 0;
! 2263:
! 2264: #ifdef DNS_RBT_USEHASH
! 2265: HASHNEXT(node) = NULL;
! 2266: HASHVAL(node) = 0;
! 2267: #endif
! 2268:
! 2269: ISC_LINK_INIT(node, deadlink);
! 2270:
! 2271: LOCKNUM(node) = 0;
! 2272: WILD(node) = 0;
! 2273: DIRTY(node) = 0;
! 2274: dns_rbtnode_refinit(node, 0);
! 2275: node->find_callback = 0;
! 2276: node->nsec = DNS_RBT_NSEC_NORMAL;
! 2277:
! 2278: MAKE_BLACK(node);
! 2279:
! 2280: /*
! 2281: * The following is stored to make reconstructing a name from the
! 2282: * stored value in the node easy: the length of the name, the number
! 2283: * of labels, whether the name is absolute or not, the name itself,
! 2284: * and the name's offsets table.
! 2285: *
! 2286: * XXX RTH
! 2287: * The offsets table could be made smaller by eliminating the
! 2288: * first offset, which is always 0. This requires changes to
! 2289: * lib/dns/name.c.
! 2290: *
! 2291: * Note: OLDOFFSETLEN *must* be assigned *after* OLDNAMELEN is assigned
! 2292: * as it uses OLDNAMELEN.
! 2293: */
! 2294: OLDNAMELEN(node) = NAMELEN(node) = region.length;
! 2295: OLDOFFSETLEN(node) = OFFSETLEN(node) = labels;
! 2296: ATTRS(node) = name->attributes;
! 2297:
! 2298: memmove(NAME(node), region.base, region.length);
! 2299: memmove(OFFSETS(node), name->offsets, labels);
! 2300:
! 2301: #if DNS_RBT_USEMAGIC
! 2302: node->magic = DNS_RBTNODE_MAGIC;
! 2303: #endif
! 2304: *nodep = node;
! 2305:
! 2306: return (ISC_R_SUCCESS);
! 2307: }
! 2308:
! 2309: #ifdef DNS_RBT_USEHASH
! 2310: static inline void
! 2311: hash_add_node(dns_rbt_t *rbt, dns_rbtnode_t *node, const dns_name_t *name) {
! 2312: unsigned int hash;
! 2313:
! 2314: REQUIRE(name != NULL);
! 2315:
! 2316: HASHVAL(node) = dns_name_fullhash(name, ISC_FALSE);
! 2317:
! 2318: hash = HASHVAL(node) % rbt->hashsize;
! 2319: HASHNEXT(node) = rbt->hashtable[hash];
! 2320:
! 2321: rbt->hashtable[hash] = node;
! 2322: }
! 2323:
! 2324: static isc_result_t
! 2325: inithash(dns_rbt_t *rbt) {
! 2326: unsigned int bytes;
! 2327:
! 2328: rbt->hashsize = RBT_HASH_SIZE;
! 2329: bytes = (unsigned int)rbt->hashsize * sizeof(dns_rbtnode_t *);
! 2330: rbt->hashtable = isc_mem_get(rbt->mctx, bytes);
! 2331:
! 2332: if (rbt->hashtable == NULL)
! 2333: return (ISC_R_NOMEMORY);
! 2334:
! 2335: memset(rbt->hashtable, 0, bytes);
! 2336:
! 2337: return (ISC_R_SUCCESS);
! 2338: }
! 2339:
! 2340: static void
! 2341: rehash(dns_rbt_t *rbt, unsigned int newcount) {
! 2342: unsigned int oldsize;
! 2343: dns_rbtnode_t **oldtable;
! 2344: dns_rbtnode_t *node;
! 2345: dns_rbtnode_t *nextnode;
! 2346: unsigned int hash;
! 2347: unsigned int i;
! 2348:
! 2349: oldsize = (unsigned int)rbt->hashsize;
! 2350: oldtable = rbt->hashtable;
! 2351: do {
! 2352: INSIST((rbt->hashsize * 2 + 1) > rbt->hashsize);
! 2353: rbt->hashsize = rbt->hashsize * 2 + 1;
! 2354: } while (newcount >= (rbt->hashsize * 3));
! 2355: rbt->hashtable = isc_mem_get(rbt->mctx,
! 2356: rbt->hashsize * sizeof(dns_rbtnode_t *));
! 2357: if (rbt->hashtable == NULL) {
! 2358: rbt->hashtable = oldtable;
! 2359: rbt->hashsize = oldsize;
! 2360: return;
! 2361: }
! 2362:
! 2363: for (i = 0; i < rbt->hashsize; i++)
! 2364: rbt->hashtable[i] = NULL;
! 2365:
! 2366: for (i = 0; i < oldsize; i++) {
! 2367: for (node = oldtable[i]; node != NULL; node = nextnode) {
! 2368: hash = HASHVAL(node) % rbt->hashsize;
! 2369: nextnode = HASHNEXT(node);
! 2370: HASHNEXT(node) = rbt->hashtable[hash];
! 2371: rbt->hashtable[hash] = node;
! 2372: }
! 2373: }
! 2374:
! 2375: isc_mem_put(rbt->mctx, oldtable, oldsize * sizeof(dns_rbtnode_t *));
! 2376: }
! 2377:
! 2378: static inline void
! 2379: hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, const dns_name_t *name) {
! 2380: REQUIRE(DNS_RBTNODE_VALID(node));
! 2381:
! 2382: if (rbt->nodecount >= (rbt->hashsize * 3))
! 2383: rehash(rbt, rbt->nodecount);
! 2384:
! 2385: hash_add_node(rbt, node, name);
! 2386: }
! 2387:
! 2388: static inline void
! 2389: unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node) {
! 2390: unsigned int bucket;
! 2391: dns_rbtnode_t *bucket_node;
! 2392:
! 2393: REQUIRE(DNS_RBTNODE_VALID(node));
! 2394:
! 2395: bucket = HASHVAL(node) % rbt->hashsize;
! 2396: bucket_node = rbt->hashtable[bucket];
! 2397:
! 2398: if (bucket_node == node) {
! 2399: rbt->hashtable[bucket] = HASHNEXT(node);
! 2400: } else {
! 2401: while (HASHNEXT(bucket_node) != node) {
! 2402: INSIST(HASHNEXT(bucket_node) != NULL);
! 2403: bucket_node = HASHNEXT(bucket_node);
! 2404: }
! 2405: HASHNEXT(bucket_node) = HASHNEXT(node);
! 2406: }
! 2407: }
! 2408: #endif /* DNS_RBT_USEHASH */
! 2409:
! 2410: static inline void
! 2411: rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
! 2412: dns_rbtnode_t *child;
! 2413:
! 2414: REQUIRE(DNS_RBTNODE_VALID(node));
! 2415: REQUIRE(rootp != NULL);
! 2416:
! 2417: child = RIGHT(node);
! 2418: INSIST(child != NULL);
! 2419:
! 2420: RIGHT(node) = LEFT(child);
! 2421: if (LEFT(child) != NULL)
! 2422: PARENT(LEFT(child)) = node;
! 2423: LEFT(child) = node;
! 2424:
! 2425: PARENT(child) = PARENT(node);
! 2426:
! 2427: if (IS_ROOT(node)) {
! 2428: *rootp = child;
! 2429: child->is_root = 1;
! 2430: node->is_root = 0;
! 2431:
! 2432: } else {
! 2433: if (LEFT(PARENT(node)) == node)
! 2434: LEFT(PARENT(node)) = child;
! 2435: else
! 2436: RIGHT(PARENT(node)) = child;
! 2437: }
! 2438:
! 2439: PARENT(node) = child;
! 2440: }
! 2441:
! 2442: static inline void
! 2443: rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
! 2444: dns_rbtnode_t *child;
! 2445:
! 2446: REQUIRE(DNS_RBTNODE_VALID(node));
! 2447: REQUIRE(rootp != NULL);
! 2448:
! 2449: child = LEFT(node);
! 2450: INSIST(child != NULL);
! 2451:
! 2452: LEFT(node) = RIGHT(child);
! 2453: if (RIGHT(child) != NULL)
! 2454: PARENT(RIGHT(child)) = node;
! 2455: RIGHT(child) = node;
! 2456:
! 2457: PARENT(child) = PARENT(node);
! 2458:
! 2459: if (IS_ROOT(node)) {
! 2460: *rootp = child;
! 2461: child->is_root = 1;
! 2462: node->is_root = 0;
! 2463:
! 2464: } else {
! 2465: if (LEFT(PARENT(node)) == node)
! 2466: LEFT(PARENT(node)) = child;
! 2467: else
! 2468: RIGHT(PARENT(node)) = child;
! 2469: }
! 2470:
! 2471: PARENT(node) = child;
! 2472: }
! 2473:
! 2474: /*
! 2475: * This is the real workhorse of the insertion code, because it does the
! 2476: * true red/black tree on a single level.
! 2477: */
! 2478: static void
! 2479: addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
! 2480: dns_rbtnode_t **rootp)
! 2481: {
! 2482: dns_rbtnode_t *child, *root, *parent, *grandparent;
! 2483: dns_name_t add_name, current_name;
! 2484: dns_offsets_t add_offsets, current_offsets;
! 2485:
! 2486: REQUIRE(rootp != NULL);
! 2487: REQUIRE(DNS_RBTNODE_VALID(node) && LEFT(node) == NULL &&
! 2488: RIGHT(node) == NULL);
! 2489: REQUIRE(current != NULL);
! 2490:
! 2491: root = *rootp;
! 2492: if (root == NULL) {
! 2493: /*
! 2494: * First node of a level.
! 2495: */
! 2496: MAKE_BLACK(node);
! 2497: node->is_root = 1;
! 2498: PARENT(node) = current;
! 2499: *rootp = node;
! 2500: return;
! 2501: }
! 2502:
! 2503: child = root;
! 2504: POST(child);
! 2505:
! 2506: dns_name_init(&add_name, add_offsets);
! 2507: NODENAME(node, &add_name);
! 2508:
! 2509: dns_name_init(¤t_name, current_offsets);
! 2510: NODENAME(current, ¤t_name);
! 2511:
! 2512: if (order < 0) {
! 2513: INSIST(LEFT(current) == NULL);
! 2514: LEFT(current) = node;
! 2515: } else {
! 2516: INSIST(RIGHT(current) == NULL);
! 2517: RIGHT(current) = node;
! 2518: }
! 2519:
! 2520: INSIST(PARENT(node) == NULL);
! 2521: PARENT(node) = current;
! 2522:
! 2523: MAKE_RED(node);
! 2524:
! 2525: while (node != root && IS_RED(PARENT(node))) {
! 2526: /*
! 2527: * XXXDCL could do away with separate parent and grandparent
! 2528: * variables. They are vestiges of the days before parent
! 2529: * pointers. However, they make the code a little clearer.
! 2530: */
! 2531:
! 2532: parent = PARENT(node);
! 2533: grandparent = PARENT(parent);
! 2534:
! 2535: if (parent == LEFT(grandparent)) {
! 2536: child = RIGHT(grandparent);
! 2537: if (child != NULL && IS_RED(child)) {
! 2538: MAKE_BLACK(parent);
! 2539: MAKE_BLACK(child);
! 2540: MAKE_RED(grandparent);
! 2541: node = grandparent;
! 2542: } else {
! 2543: if (node == RIGHT(parent)) {
! 2544: rotate_left(parent, &root);
! 2545: node = parent;
! 2546: parent = PARENT(node);
! 2547: grandparent = PARENT(parent);
! 2548: }
! 2549: MAKE_BLACK(parent);
! 2550: MAKE_RED(grandparent);
! 2551: rotate_right(grandparent, &root);
! 2552: }
! 2553: } else {
! 2554: child = LEFT(grandparent);
! 2555: if (child != NULL && IS_RED(child)) {
! 2556: MAKE_BLACK(parent);
! 2557: MAKE_BLACK(child);
! 2558: MAKE_RED(grandparent);
! 2559: node = grandparent;
! 2560: } else {
! 2561: if (node == LEFT(parent)) {
! 2562: rotate_right(parent, &root);
! 2563: node = parent;
! 2564: parent = PARENT(node);
! 2565: grandparent = PARENT(parent);
! 2566: }
! 2567: MAKE_BLACK(parent);
! 2568: MAKE_RED(grandparent);
! 2569: rotate_left(grandparent, &root);
! 2570: }
! 2571: }
! 2572: }
! 2573:
! 2574: MAKE_BLACK(root);
! 2575: ENSURE(IS_ROOT(root));
! 2576: *rootp = root;
! 2577:
! 2578: return;
! 2579: }
! 2580:
! 2581: /*
! 2582: * This is the real workhorse of the deletion code, because it does the
! 2583: * true red/black tree on a single level.
! 2584: */
! 2585: static void
! 2586: deletefromlevel(dns_rbtnode_t *item, dns_rbtnode_t **rootp) {
! 2587: dns_rbtnode_t *child, *sibling, *parent;
! 2588: dns_rbtnode_t *successor;
! 2589:
! 2590: REQUIRE(item != NULL);
! 2591:
! 2592: /*
! 2593: * Verify that the parent history is (apparently) correct.
! 2594: */
! 2595: INSIST((IS_ROOT(item) && *rootp == item) ||
! 2596: (! IS_ROOT(item) &&
! 2597: (LEFT(PARENT(item)) == item ||
! 2598: RIGHT(PARENT(item)) == item)));
! 2599:
! 2600: child = NULL;
! 2601:
! 2602: if (LEFT(item) == NULL) {
! 2603: if (RIGHT(item) == NULL) {
! 2604: if (IS_ROOT(item)) {
! 2605: /*
! 2606: * This is the only item in the tree.
! 2607: */
! 2608: *rootp = NULL;
! 2609: return;
! 2610: }
! 2611: } else
! 2612: /*
! 2613: * This node has one child, on the right.
! 2614: */
! 2615: child = RIGHT(item);
! 2616:
! 2617: } else if (RIGHT(item) == NULL)
! 2618: /*
! 2619: * This node has one child, on the left.
! 2620: */
! 2621: child = LEFT(item);
! 2622: else {
! 2623: dns_rbtnode_t holder, *tmp = &holder;
! 2624:
! 2625: /*
! 2626: * This node has two children, so it cannot be directly
! 2627: * deleted. Find its immediate in-order successor and
! 2628: * move it to this location, then do the deletion at the
! 2629: * old site of the successor.
! 2630: */
! 2631: successor = RIGHT(item);
! 2632: while (LEFT(successor) != NULL)
! 2633: successor = LEFT(successor);
! 2634:
! 2635: /*
! 2636: * The successor cannot possibly have a left child;
! 2637: * if there is any child, it is on the right.
! 2638: */
! 2639: if (RIGHT(successor) != NULL)
! 2640: child = RIGHT(successor);
! 2641:
! 2642: /*
! 2643: * Swap the two nodes; it would be simpler to just replace
! 2644: * the value being deleted with that of the successor,
! 2645: * but this rigamarole is done so the caller has complete
! 2646: * control over the pointers (and memory allocation) of
! 2647: * all of nodes. If just the key value were removed from
! 2648: * the tree, the pointer to the node would be unchanged.
! 2649: */
! 2650:
! 2651: /*
! 2652: * First, put the successor in the tree location of the
! 2653: * node to be deleted. Save its existing tree pointer
! 2654: * information, which will be needed when linking up
! 2655: * delete to the successor's old location.
! 2656: */
! 2657: memmove(tmp, successor, sizeof(dns_rbtnode_t));
! 2658:
! 2659: if (IS_ROOT(item)) {
! 2660: *rootp = successor;
! 2661: successor->is_root = ISC_TRUE;
! 2662: item->is_root = ISC_FALSE;
! 2663:
! 2664: } else
! 2665: if (LEFT(PARENT(item)) == item)
! 2666: LEFT(PARENT(item)) = successor;
! 2667: else
! 2668: RIGHT(PARENT(item)) = successor;
! 2669:
! 2670: PARENT(successor) = PARENT(item);
! 2671: LEFT(successor) = LEFT(item);
! 2672: RIGHT(successor) = RIGHT(item);
! 2673: COLOR(successor) = COLOR(item);
! 2674:
! 2675: if (LEFT(successor) != NULL)
! 2676: PARENT(LEFT(successor)) = successor;
! 2677: if (RIGHT(successor) != successor)
! 2678: PARENT(RIGHT(successor)) = successor;
! 2679:
! 2680: /*
! 2681: * Now relink the node to be deleted into the
! 2682: * successor's previous tree location. PARENT(tmp)
! 2683: * is the successor's original parent.
! 2684: */
! 2685: INSIST(! IS_ROOT(item));
! 2686:
! 2687: if (PARENT(tmp) == item) {
! 2688: /*
! 2689: * Node being deleted was successor's parent.
! 2690: */
! 2691: RIGHT(successor) = item;
! 2692: PARENT(item) = successor;
! 2693:
! 2694: } else {
! 2695: LEFT(PARENT(tmp)) = item;
! 2696: PARENT(item) = PARENT(tmp);
! 2697: }
! 2698:
! 2699: /*
! 2700: * Original location of successor node has no left.
! 2701: */
! 2702: LEFT(item) = NULL;
! 2703: RIGHT(item) = RIGHT(tmp);
! 2704: COLOR(item) = COLOR(tmp);
! 2705: }
! 2706:
! 2707: /*
! 2708: * Remove the node by removing the links from its parent.
! 2709: */
! 2710: if (! IS_ROOT(item)) {
! 2711: if (LEFT(PARENT(item)) == item)
! 2712: LEFT(PARENT(item)) = child;
! 2713: else
! 2714: RIGHT(PARENT(item)) = child;
! 2715:
! 2716: if (child != NULL)
! 2717: PARENT(child) = PARENT(item);
! 2718:
! 2719: } else {
! 2720: /*
! 2721: * This is the root being deleted, and at this point
! 2722: * it is known to have just one child.
! 2723: */
! 2724: *rootp = child;
! 2725: child->is_root = 1;
! 2726: PARENT(child) = PARENT(item);
! 2727: }
! 2728:
! 2729: /*
! 2730: * Fix color violations.
! 2731: */
! 2732: if (IS_BLACK(item)) {
! 2733: parent = PARENT(item);
! 2734:
! 2735: while (child != *rootp && IS_BLACK(child)) {
! 2736: INSIST(child == NULL || ! IS_ROOT(child));
! 2737:
! 2738: if (LEFT(parent) == child) {
! 2739: sibling = RIGHT(parent);
! 2740:
! 2741: if (IS_RED(sibling)) {
! 2742: MAKE_BLACK(sibling);
! 2743: MAKE_RED(parent);
! 2744: rotate_left(parent, rootp);
! 2745: sibling = RIGHT(parent);
! 2746: }
! 2747:
! 2748: INSIST(sibling != NULL);
! 2749:
! 2750: if (IS_BLACK(LEFT(sibling)) &&
! 2751: IS_BLACK(RIGHT(sibling))) {
! 2752: MAKE_RED(sibling);
! 2753: child = parent;
! 2754:
! 2755: } else {
! 2756:
! 2757: if (IS_BLACK(RIGHT(sibling))) {
! 2758: MAKE_BLACK(LEFT(sibling));
! 2759: MAKE_RED(sibling);
! 2760: rotate_right(sibling, rootp);
! 2761: sibling = RIGHT(parent);
! 2762: }
! 2763:
! 2764: COLOR(sibling) = COLOR(parent);
! 2765: MAKE_BLACK(parent);
! 2766: INSIST(RIGHT(sibling) != NULL);
! 2767: MAKE_BLACK(RIGHT(sibling));
! 2768: rotate_left(parent, rootp);
! 2769: child = *rootp;
! 2770: }
! 2771:
! 2772: } else {
! 2773: /*
! 2774: * Child is parent's right child.
! 2775: * Everything is done the same as above,
! 2776: * except mirrored.
! 2777: */
! 2778: sibling = LEFT(parent);
! 2779:
! 2780: if (IS_RED(sibling)) {
! 2781: MAKE_BLACK(sibling);
! 2782: MAKE_RED(parent);
! 2783: rotate_right(parent, rootp);
! 2784: sibling = LEFT(parent);
! 2785: }
! 2786:
! 2787: INSIST(sibling != NULL);
! 2788:
! 2789: if (IS_BLACK(LEFT(sibling)) &&
! 2790: IS_BLACK(RIGHT(sibling))) {
! 2791: MAKE_RED(sibling);
! 2792: child = parent;
! 2793:
! 2794: } else {
! 2795: if (IS_BLACK(LEFT(sibling))) {
! 2796: MAKE_BLACK(RIGHT(sibling));
! 2797: MAKE_RED(sibling);
! 2798: rotate_left(sibling, rootp);
! 2799: sibling = LEFT(parent);
! 2800: }
! 2801:
! 2802: COLOR(sibling) = COLOR(parent);
! 2803: MAKE_BLACK(parent);
! 2804: INSIST(LEFT(sibling) != NULL);
! 2805: MAKE_BLACK(LEFT(sibling));
! 2806: rotate_right(parent, rootp);
! 2807: child = *rootp;
! 2808: }
! 2809: }
! 2810:
! 2811: parent = PARENT(child);
! 2812: }
! 2813:
! 2814: if (IS_RED(child))
! 2815: MAKE_BLACK(child);
! 2816: }
! 2817: }
! 2818:
! 2819: static void
! 2820: freenode(dns_rbt_t *rbt, dns_rbtnode_t **nodep) {
! 2821: dns_rbtnode_t *node = *nodep;
! 2822:
! 2823: if (node->is_mmapped == 0) {
! 2824: isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
! 2825: }
! 2826: *nodep = NULL;
! 2827:
! 2828: rbt->nodecount--;
! 2829: }
! 2830:
! 2831: static void
! 2832: deletetreeflat(dns_rbt_t *rbt, unsigned int quantum, isc_boolean_t unhash,
! 2833: dns_rbtnode_t **nodep)
! 2834: {
! 2835: dns_rbtnode_t *root = *nodep;
! 2836:
! 2837: while (root != NULL) {
! 2838: /*
! 2839: * If there is a left, right or down node, walk into it
! 2840: * and iterate.
! 2841: */
! 2842: if (LEFT(root) != NULL) {
! 2843: dns_rbtnode_t *node = root;
! 2844: root = LEFT(root);
! 2845: LEFT(node) = NULL;
! 2846: } else if (RIGHT(root) != NULL) {
! 2847: dns_rbtnode_t *node = root;
! 2848: root = RIGHT(root);
! 2849: RIGHT(node) = NULL;
! 2850: } else if (DOWN(root) != NULL) {
! 2851: dns_rbtnode_t *node = root;
! 2852: root = DOWN(root);
! 2853: DOWN(node) = NULL;
! 2854: } else {
! 2855: /*
! 2856: * There are no left, right or down nodes, so we
! 2857: * can free this one and go back to its parent.
! 2858: */
! 2859: dns_rbtnode_t *node = root;
! 2860: root = PARENT(root);
! 2861:
! 2862: if (DATA(node) != NULL && rbt->data_deleter != NULL)
! 2863: rbt->data_deleter(DATA(node),
! 2864: rbt->deleter_arg);
! 2865: if (unhash)
! 2866: unhash_node(rbt, node);
! 2867: /*
! 2868: * Note: we don't call unhash_node() here as we
! 2869: * are destroying the complete RBT tree.
! 2870: */
! 2871: #if DNS_RBT_USEMAGIC
! 2872: node->magic = 0;
! 2873: #endif
! 2874: freenode(rbt, &node);
! 2875: if (quantum != 0 && --quantum == 0)
! 2876: break;
! 2877: }
! 2878: }
! 2879:
! 2880: *nodep = root;
! 2881: }
! 2882:
! 2883: static size_t
! 2884: getheight_helper(dns_rbtnode_t *node) {
! 2885: size_t dl, dr;
! 2886: size_t this_height, down_height;
! 2887:
! 2888: if (node == NULL)
! 2889: return (0);
! 2890:
! 2891: dl = getheight_helper(LEFT(node));
! 2892: dr = getheight_helper(RIGHT(node));
! 2893:
! 2894: this_height = ISC_MAX(dl + 1, dr + 1);
! 2895: down_height = getheight_helper(DOWN(node));
! 2896:
! 2897: return (ISC_MAX(this_height, down_height));
! 2898: }
! 2899:
! 2900: size_t
! 2901: dns__rbt_getheight(dns_rbt_t *rbt) {
! 2902: return (getheight_helper(rbt->root));
! 2903: }
! 2904:
! 2905: static isc_boolean_t
! 2906: check_properties_helper(dns_rbtnode_t *node) {
! 2907: if (node == NULL)
! 2908: return (ISC_TRUE);
! 2909:
! 2910: if (IS_RED(node)) {
! 2911: /* Root nodes must be BLACK. */
! 2912: if (IS_ROOT(node))
! 2913: return (ISC_FALSE);
! 2914:
! 2915: /* Both children of RED nodes must be BLACK. */
! 2916: if (IS_RED(LEFT(node)) || IS_RED(RIGHT(node)))
! 2917: return (ISC_FALSE);
! 2918: }
! 2919:
! 2920: if ((DOWN(node) != NULL) && (!IS_ROOT(DOWN(node))))
! 2921: return (ISC_FALSE);
! 2922:
! 2923: if (IS_ROOT(node)) {
! 2924: if ((PARENT(node) != NULL) &&
! 2925: (DOWN(PARENT(node)) != node))
! 2926: return (ISC_FALSE);
! 2927:
! 2928: if (get_upper_node(node) != PARENT(node))
! 2929: return (ISC_FALSE);
! 2930: }
! 2931:
! 2932: /* If node is assigned to the down_ pointer of its parent, it is
! 2933: * a subtree root and must have the flag set.
! 2934: */
! 2935: if (((!PARENT(node)) ||
! 2936: (DOWN(PARENT(node)) == node)) &&
! 2937: (!IS_ROOT(node)))
! 2938: {
! 2939: return (ISC_FALSE);
! 2940: }
! 2941:
! 2942: /* Repeat tests with this node's children. */
! 2943: return (check_properties_helper(LEFT(node)) &&
! 2944: check_properties_helper(RIGHT(node)) &&
! 2945: check_properties_helper(DOWN(node)));
! 2946: }
! 2947:
! 2948: static isc_boolean_t
! 2949: check_black_distance_helper(dns_rbtnode_t *node, size_t *distance) {
! 2950: size_t dl, dr, dd;
! 2951:
! 2952: if (node == NULL) {
! 2953: *distance = 1;
! 2954: return (ISC_TRUE);
! 2955: }
! 2956:
! 2957: if (!check_black_distance_helper(LEFT(node), &dl))
! 2958: return (ISC_FALSE);
! 2959:
! 2960: if (!check_black_distance_helper(RIGHT(node), &dr))
! 2961: return (ISC_FALSE);
! 2962:
! 2963: if (!check_black_distance_helper(DOWN(node), &dd))
! 2964: return (ISC_FALSE);
! 2965:
! 2966: /* Left and right side black node counts must match. */
! 2967: if (dl != dr)
! 2968: return (ISC_FALSE);
! 2969:
! 2970: if (IS_BLACK(node))
! 2971: dl++;
! 2972:
! 2973: *distance = dl;
! 2974:
! 2975: return (ISC_TRUE);
! 2976: }
! 2977:
! 2978: isc_boolean_t
! 2979: dns__rbt_checkproperties(dns_rbt_t *rbt) {
! 2980: size_t dd;
! 2981:
! 2982: if (!check_properties_helper(rbt->root))
! 2983: return (ISC_FALSE);
! 2984:
! 2985: /* Path from a given node to all its leaves must contain the
! 2986: * same number of BLACK child nodes. This is done separately
! 2987: * here instead of inside check_properties_helper() as
! 2988: * it would take (n log n) complexity otherwise.
! 2989: */
! 2990: return (check_black_distance_helper(rbt->root, &dd));
! 2991: }
! 2992:
! 2993: static void
! 2994: dns_rbt_indent(FILE *f, int depth) {
! 2995: int i;
! 2996:
! 2997: fprintf(f, "%4d ", depth);
! 2998:
! 2999: for (i = 0; i < depth; i++)
! 3000: fprintf(f, "- ");
! 3001: }
! 3002:
! 3003: void
! 3004: dns_rbt_printnodeinfo(dns_rbtnode_t *n, FILE *f) {
! 3005: fprintf(f, "Node info for nodename: ");
! 3006: printnodename(n, ISC_TRUE, f);
! 3007: fprintf(f, "\n");
! 3008:
! 3009: fprintf(f, "n = %p\n", n);
! 3010:
! 3011: fprintf(f, "Relative pointers: %s%s%s%s%s\n",
! 3012: (n->parent_is_relative == 1 ? " P" : ""),
! 3013: (n->right_is_relative == 1 ? " R" : ""),
! 3014: (n->left_is_relative == 1 ? " L" : ""),
! 3015: (n->down_is_relative == 1 ? " D" : ""),
! 3016: (n->data_is_relative == 1 ? " T" : ""));
! 3017:
! 3018: fprintf(f, "node lock address = %u\n", n->locknum);
! 3019:
! 3020: fprintf(f, "Parent: %p\n", n->parent);
! 3021: fprintf(f, "Right: %p\n", n->right);
! 3022: fprintf(f, "Left: %p\n", n->left);
! 3023: fprintf(f, "Down: %p\n", n->down);
! 3024: fprintf(f, "daTa: %p\n", n->data);
! 3025: }
! 3026:
! 3027: static void
! 3028: printnodename(dns_rbtnode_t *node, isc_boolean_t quoted, FILE *f) {
! 3029: isc_region_t r;
! 3030: dns_name_t name;
! 3031: char buffer[DNS_NAME_FORMATSIZE];
! 3032: dns_offsets_t offsets;
! 3033:
! 3034: r.length = NAMELEN(node);
! 3035: r.base = NAME(node);
! 3036:
! 3037: dns_name_init(&name, offsets);
! 3038: dns_name_fromregion(&name, &r);
! 3039:
! 3040: dns_name_format(&name, buffer, sizeof(buffer));
! 3041:
! 3042: if (quoted)
! 3043: fprintf(f, "\"%s\"", buffer);
! 3044: else
! 3045: fprintf(f, "%s", buffer);
! 3046: }
! 3047:
! 3048: static void
! 3049: print_text_helper(dns_rbtnode_t *root, dns_rbtnode_t *parent,
! 3050: int depth, const char *direction,
! 3051: void (*data_printer)(FILE *, void *), FILE *f)
! 3052: {
! 3053: dns_rbt_indent(f, depth);
! 3054:
! 3055: if (root != NULL) {
! 3056: printnodename(root, ISC_TRUE, f);
! 3057: fprintf(f, " (%s, %s", direction,
! 3058: IS_RED(root) ? "RED" : "BLACK");
! 3059:
! 3060: if ((! IS_ROOT(root) && PARENT(root) != parent) ||
! 3061: ( IS_ROOT(root) && depth > 0 &&
! 3062: DOWN(PARENT(root)) != root)) {
! 3063:
! 3064: fprintf(f, " (BAD parent pointer! -> ");
! 3065: if (PARENT(root) != NULL)
! 3066: printnodename(PARENT(root), ISC_TRUE, f);
! 3067: else
! 3068: fprintf(f, "NULL");
! 3069: fprintf(f, ")");
! 3070: }
! 3071:
! 3072: fprintf(f, ")");
! 3073:
! 3074: if (root->data != NULL && data_printer != NULL) {
! 3075: fprintf(f, " data@%p: ", root->data);
! 3076: data_printer(f, root->data);
! 3077: }
! 3078: fprintf(f, "\n");
! 3079:
! 3080: depth++;
! 3081:
! 3082: if (IS_RED(root) && IS_RED(LEFT(root)))
! 3083: fprintf(f, "** Red/Red color violation on left\n");
! 3084: print_text_helper(LEFT(root), root, depth, "left",
! 3085: data_printer, f);
! 3086:
! 3087: if (IS_RED(root) && IS_RED(RIGHT(root)))
! 3088: fprintf(f, "** Red/Red color violation on right\n");
! 3089: print_text_helper(RIGHT(root), root, depth, "right",
! 3090: data_printer, f);
! 3091:
! 3092: print_text_helper(DOWN(root), NULL, depth, "down",
! 3093: data_printer, f);
! 3094: } else {
! 3095: fprintf(f, "NULL (%s)\n", direction);
! 3096: }
! 3097: }
! 3098:
! 3099: void
! 3100: dns_rbt_printtext(dns_rbt_t *rbt,
! 3101: void (*data_printer)(FILE *, void *), FILE *f)
! 3102: {
! 3103: REQUIRE(VALID_RBT(rbt));
! 3104:
! 3105: print_text_helper(rbt->root, NULL, 0, "root", data_printer, f);
! 3106: }
! 3107:
! 3108: static int
! 3109: print_dot_helper(dns_rbtnode_t *node, unsigned int *nodecount,
! 3110: isc_boolean_t show_pointers, FILE *f)
! 3111: {
! 3112: unsigned int l, r, d;
! 3113:
! 3114: if (node == NULL)
! 3115: return (0);
! 3116:
! 3117: l = print_dot_helper(LEFT(node), nodecount, show_pointers, f);
! 3118: r = print_dot_helper(RIGHT(node), nodecount, show_pointers, f);
! 3119: d = print_dot_helper(DOWN(node), nodecount, show_pointers, f);
! 3120:
! 3121: *nodecount += 1;
! 3122:
! 3123: fprintf(f, "node%u[label = \"<f0> |<f1> ", *nodecount);
! 3124: printnodename(node, ISC_FALSE, f);
! 3125: fprintf(f, "|<f2>");
! 3126:
! 3127: if (show_pointers)
! 3128: fprintf(f, "|<f3> n=%p|<f4> p=%p", node, PARENT(node));
! 3129:
! 3130: fprintf(f, "\"] [");
! 3131:
! 3132: if (IS_RED(node))
! 3133: fprintf(f, "color=red");
! 3134: else
! 3135: fprintf(f, "color=black");
! 3136:
! 3137: /* XXXMUKS: verify that IS_ROOT() indicates subtree root and not
! 3138: * forest root.
! 3139: */
! 3140: if (IS_ROOT(node))
! 3141: fprintf(f, ",penwidth=3");
! 3142:
! 3143: if (IS_EMPTY(node))
! 3144: fprintf(f, ",style=filled,fillcolor=lightgrey");
! 3145:
! 3146: fprintf(f, "];\n");
! 3147:
! 3148: if (LEFT(node) != NULL)
! 3149: fprintf(f, "\"node%u\":f0 -> \"node%u\":f1;\n", *nodecount, l);
! 3150:
! 3151: if (DOWN(node) != NULL)
! 3152: fprintf(f, "\"node%u\":f1 -> \"node%u\":f1 [penwidth=5];\n",
! 3153: *nodecount, d);
! 3154:
! 3155: if (RIGHT(node) != NULL)
! 3156: fprintf(f, "\"node%u\":f2 -> \"node%u\":f1;\n", *nodecount, r);
! 3157:
! 3158: return (*nodecount);
! 3159: }
! 3160:
! 3161: void
! 3162: dns_rbt_printdot(dns_rbt_t *rbt, isc_boolean_t show_pointers, FILE *f) {
! 3163: unsigned int nodecount = 0;
! 3164:
! 3165: REQUIRE(VALID_RBT(rbt));
! 3166:
! 3167: fprintf(f, "digraph g {\n");
! 3168: fprintf(f, "node [shape = record,height=.1];\n");
! 3169: print_dot_helper(rbt->root, &nodecount, show_pointers, f);
! 3170: fprintf(f, "}\n");
! 3171: }
! 3172:
! 3173: /*
! 3174: * Chain Functions
! 3175: */
! 3176:
! 3177: void
! 3178: dns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx) {
! 3179:
! 3180: REQUIRE(chain != NULL);
! 3181:
! 3182: /*
! 3183: * Initialize 'chain'.
! 3184: */
! 3185: chain->mctx = mctx;
! 3186: chain->end = NULL;
! 3187: chain->level_count = 0;
! 3188: chain->level_matches = 0;
! 3189: memset(chain->levels, 0, sizeof(chain->levels));
! 3190:
! 3191: chain->magic = CHAIN_MAGIC;
! 3192: }
! 3193:
! 3194: isc_result_t
! 3195: dns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name,
! 3196: dns_name_t *origin, dns_rbtnode_t **node)
! 3197: {
! 3198: isc_result_t result = ISC_R_SUCCESS;
! 3199:
! 3200: REQUIRE(VALID_CHAIN(chain));
! 3201:
! 3202: if (node != NULL)
! 3203: *node = chain->end;
! 3204:
! 3205: if (chain->end == NULL)
! 3206: return (ISC_R_NOTFOUND);
! 3207:
! 3208: if (name != NULL) {
! 3209: NODENAME(chain->end, name);
! 3210:
! 3211: if (chain->level_count == 0) {
! 3212: /*
! 3213: * Names in the top level tree are all absolute.
! 3214: * Always make 'name' relative.
! 3215: */
! 3216: INSIST(dns_name_isabsolute(name));
! 3217:
! 3218: /*
! 3219: * This is cheaper than dns_name_getlabelsequence().
! 3220: */
! 3221: name->labels--;
! 3222: name->length--;
! 3223: name->attributes &= ~DNS_NAMEATTR_ABSOLUTE;
! 3224: }
! 3225: }
! 3226:
! 3227: if (origin != NULL) {
! 3228: if (chain->level_count > 0)
! 3229: result = chain_name(chain, origin, ISC_FALSE);
! 3230: else
! 3231: result = dns_name_copy(dns_rootname, origin, NULL);
! 3232: }
! 3233:
! 3234: return (result);
! 3235: }
! 3236:
! 3237: isc_result_t
! 3238: dns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name,
! 3239: dns_name_t *origin)
! 3240: {
! 3241: dns_rbtnode_t *current, *previous, *predecessor;
! 3242: isc_result_t result = ISC_R_SUCCESS;
! 3243: isc_boolean_t new_origin = ISC_FALSE;
! 3244:
! 3245: REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
! 3246:
! 3247: predecessor = NULL;
! 3248:
! 3249: current = chain->end;
! 3250:
! 3251: if (LEFT(current) != NULL) {
! 3252: /*
! 3253: * Moving left one then right as far as possible is the
! 3254: * previous node, at least for this level.
! 3255: */
! 3256: current = LEFT(current);
! 3257:
! 3258: while (RIGHT(current) != NULL)
! 3259: current = RIGHT(current);
! 3260:
! 3261: predecessor = current;
! 3262:
! 3263: } else {
! 3264: /*
! 3265: * No left links, so move toward the root. If at any point on
! 3266: * the way there the link from parent to child is a right
! 3267: * link, then the parent is the previous node, at least
! 3268: * for this level.
! 3269: */
! 3270: while (! IS_ROOT(current)) {
! 3271: previous = current;
! 3272: current = PARENT(current);
! 3273:
! 3274: if (RIGHT(current) == previous) {
! 3275: predecessor = current;
! 3276: break;
! 3277: }
! 3278: }
! 3279: }
! 3280:
! 3281: if (predecessor != NULL) {
! 3282: /*
! 3283: * Found a predecessor node in this level. It might not
! 3284: * really be the predecessor, however.
! 3285: */
! 3286: if (DOWN(predecessor) != NULL) {
! 3287: /*
! 3288: * The predecessor is really down at least one level.
! 3289: * Go down and as far right as possible, and repeat
! 3290: * as long as the rightmost node has a down pointer.
! 3291: */
! 3292: do {
! 3293: /*
! 3294: * XXX DCL Need to do something about origins
! 3295: * here. See whether to go down, and if so
! 3296: * whether it is truly what Bob calls a
! 3297: * new origin.
! 3298: */
! 3299: ADD_LEVEL(chain, predecessor);
! 3300: predecessor = DOWN(predecessor);
! 3301:
! 3302: /* XXX DCL duplicated from above; clever
! 3303: * way to unduplicate? */
! 3304:
! 3305: while (RIGHT(predecessor) != NULL)
! 3306: predecessor = RIGHT(predecessor);
! 3307: } while (DOWN(predecessor) != NULL);
! 3308:
! 3309: /* XXX DCL probably needs work on the concept */
! 3310: if (origin != NULL)
! 3311: new_origin = ISC_TRUE;
! 3312: }
! 3313:
! 3314: } else if (chain->level_count > 0) {
! 3315: /*
! 3316: * Dang, didn't find a predecessor in this level.
! 3317: * Got to the root of this level without having traversed
! 3318: * any right links. Ascend the tree one level; the
! 3319: * node that points to this tree is the predecessor.
! 3320: */
! 3321: INSIST(chain->level_count > 0 && IS_ROOT(current));
! 3322: predecessor = chain->levels[--chain->level_count];
! 3323:
! 3324: /* XXX DCL probably needs work on the concept */
! 3325: /*
! 3326: * Don't declare an origin change when the new origin is "."
! 3327: * at the top level tree, because "." is declared as the origin
! 3328: * for the second level tree.
! 3329: */
! 3330: if (origin != NULL &&
! 3331: (chain->level_count > 0 || OFFSETLEN(predecessor) > 1))
! 3332: new_origin = ISC_TRUE;
! 3333: }
! 3334:
! 3335: if (predecessor != NULL) {
! 3336: chain->end = predecessor;
! 3337:
! 3338: if (new_origin) {
! 3339: result = dns_rbtnodechain_current(chain, name, origin,
! 3340: NULL);
! 3341: if (result == ISC_R_SUCCESS)
! 3342: result = DNS_R_NEWORIGIN;
! 3343:
! 3344: } else
! 3345: result = dns_rbtnodechain_current(chain, name, NULL,
! 3346: NULL);
! 3347:
! 3348: } else
! 3349: result = ISC_R_NOMORE;
! 3350:
! 3351: return (result);
! 3352: }
! 3353:
! 3354: isc_result_t
! 3355: dns_rbtnodechain_down(dns_rbtnodechain_t *chain, dns_name_t *name,
! 3356: dns_name_t *origin)
! 3357: {
! 3358: dns_rbtnode_t *current, *successor;
! 3359: isc_result_t result = ISC_R_SUCCESS;
! 3360: isc_boolean_t new_origin = ISC_FALSE;
! 3361:
! 3362: REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
! 3363:
! 3364: successor = NULL;
! 3365:
! 3366: current = chain->end;
! 3367:
! 3368: if (DOWN(current) != NULL) {
! 3369: /*
! 3370: * Don't declare an origin change when the new origin is "."
! 3371: * at the second level tree, because "." is already declared
! 3372: * as the origin for the top level tree.
! 3373: */
! 3374: if (chain->level_count > 0 ||
! 3375: OFFSETLEN(current) > 1)
! 3376: new_origin = ISC_TRUE;
! 3377:
! 3378: ADD_LEVEL(chain, current);
! 3379: current = DOWN(current);
! 3380:
! 3381: while (LEFT(current) != NULL)
! 3382: current = LEFT(current);
! 3383:
! 3384: successor = current;
! 3385: }
! 3386:
! 3387: if (successor != NULL) {
! 3388: chain->end = successor;
! 3389:
! 3390: /*
! 3391: * It is not necessary to use dns_rbtnodechain_current like
! 3392: * the other functions because this function will never
! 3393: * find a node in the topmost level. This is because the
! 3394: * root level will never be more than one name, and everything
! 3395: * in the megatree is a successor to that node, down at
! 3396: * the second level or below.
! 3397: */
! 3398:
! 3399: if (name != NULL)
! 3400: NODENAME(chain->end, name);
! 3401:
! 3402: if (new_origin) {
! 3403: if (origin != NULL)
! 3404: result = chain_name(chain, origin, ISC_FALSE);
! 3405:
! 3406: if (result == ISC_R_SUCCESS)
! 3407: result = DNS_R_NEWORIGIN;
! 3408:
! 3409: } else
! 3410: result = ISC_R_SUCCESS;
! 3411:
! 3412: } else
! 3413: result = ISC_R_NOMORE;
! 3414:
! 3415: return (result);
! 3416: }
! 3417:
! 3418: isc_result_t
! 3419: dns_rbtnodechain_nextflat(dns_rbtnodechain_t *chain, dns_name_t *name) {
! 3420: dns_rbtnode_t *current, *previous, *successor;
! 3421: isc_result_t result = ISC_R_SUCCESS;
! 3422:
! 3423: REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
! 3424:
! 3425: successor = NULL;
! 3426:
! 3427: current = chain->end;
! 3428:
! 3429: if (RIGHT(current) == NULL) {
! 3430: while (! IS_ROOT(current)) {
! 3431: previous = current;
! 3432: current = PARENT(current);
! 3433:
! 3434: if (LEFT(current) == previous) {
! 3435: successor = current;
! 3436: break;
! 3437: }
! 3438: }
! 3439: } else {
! 3440: current = RIGHT(current);
! 3441:
! 3442: while (LEFT(current) != NULL)
! 3443: current = LEFT(current);
! 3444:
! 3445: successor = current;
! 3446: }
! 3447:
! 3448: if (successor != NULL) {
! 3449: chain->end = successor;
! 3450:
! 3451: if (name != NULL)
! 3452: NODENAME(chain->end, name);
! 3453:
! 3454: result = ISC_R_SUCCESS;
! 3455: } else
! 3456: result = ISC_R_NOMORE;
! 3457:
! 3458: return (result);
! 3459: }
! 3460:
! 3461: isc_result_t
! 3462: dns_rbtnodechain_next(dns_rbtnodechain_t *chain, dns_name_t *name,
! 3463: dns_name_t *origin)
! 3464: {
! 3465: dns_rbtnode_t *current, *previous, *successor;
! 3466: isc_result_t result = ISC_R_SUCCESS;
! 3467: isc_boolean_t new_origin = ISC_FALSE;
! 3468:
! 3469: REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
! 3470:
! 3471: successor = NULL;
! 3472:
! 3473: current = chain->end;
! 3474:
! 3475: /*
! 3476: * If there is a level below this node, the next node is the leftmost
! 3477: * node of the next level.
! 3478: */
! 3479: if (DOWN(current) != NULL) {
! 3480: /*
! 3481: * Don't declare an origin change when the new origin is "."
! 3482: * at the second level tree, because "." is already declared
! 3483: * as the origin for the top level tree.
! 3484: */
! 3485: if (chain->level_count > 0 ||
! 3486: OFFSETLEN(current) > 1)
! 3487: new_origin = ISC_TRUE;
! 3488:
! 3489: ADD_LEVEL(chain, current);
! 3490: current = DOWN(current);
! 3491:
! 3492: while (LEFT(current) != NULL)
! 3493: current = LEFT(current);
! 3494:
! 3495: successor = current;
! 3496:
! 3497: } else if (RIGHT(current) == NULL) {
! 3498: /*
! 3499: * The successor is up, either in this level or a previous one.
! 3500: * Head back toward the root of the tree, looking for any path
! 3501: * that was via a left link; the successor is the node that has
! 3502: * that left link. In the event the root of the level is
! 3503: * reached without having traversed any left links, ascend one
! 3504: * level and look for either a right link off the point of
! 3505: * ascent, or search for a left link upward again, repeating
! 3506: * ascends until either case is true.
! 3507: */
! 3508: do {
! 3509: while (! IS_ROOT(current)) {
! 3510: previous = current;
! 3511: current = PARENT(current);
! 3512:
! 3513: if (LEFT(current) == previous) {
! 3514: successor = current;
! 3515: break;
! 3516: }
! 3517: }
! 3518:
! 3519: if (successor == NULL) {
! 3520: /*
! 3521: * Reached the root without having traversed
! 3522: * any left pointers, so this level is done.
! 3523: */
! 3524: if (chain->level_count == 0) {
! 3525: /*
! 3526: * If the tree we are iterating over
! 3527: * was modified since this chain was
! 3528: * initialized in a way that caused
! 3529: * node splits to occur, "current" may
! 3530: * now be pointing to a root node which
! 3531: * appears to be at level 0, but still
! 3532: * has a parent. If that happens,
! 3533: * abort. Otherwise, we are done
! 3534: * looking for a successor as we really
! 3535: * reached the root node on level 0.
! 3536: */
! 3537: INSIST(PARENT(current) == NULL);
! 3538: break;
! 3539: }
! 3540:
! 3541: current = chain->levels[--chain->level_count];
! 3542: new_origin = ISC_TRUE;
! 3543:
! 3544: if (RIGHT(current) != NULL)
! 3545: break;
! 3546: }
! 3547: } while (successor == NULL);
! 3548: }
! 3549:
! 3550: if (successor == NULL && RIGHT(current) != NULL) {
! 3551: current = RIGHT(current);
! 3552:
! 3553: while (LEFT(current) != NULL)
! 3554: current = LEFT(current);
! 3555:
! 3556: successor = current;
! 3557: }
! 3558:
! 3559: if (successor != NULL) {
! 3560: /*
! 3561: * If we determine that the current node is the successor to
! 3562: * itself, we will run into an infinite loop, so abort instead.
! 3563: */
! 3564: INSIST(chain->end != successor);
! 3565:
! 3566: chain->end = successor;
! 3567:
! 3568: /*
! 3569: * It is not necessary to use dns_rbtnodechain_current like
! 3570: * the other functions because this function will never
! 3571: * find a node in the topmost level. This is because the
! 3572: * root level will never be more than one name, and everything
! 3573: * in the megatree is a successor to that node, down at
! 3574: * the second level or below.
! 3575: */
! 3576:
! 3577: if (name != NULL)
! 3578: NODENAME(chain->end, name);
! 3579:
! 3580: if (new_origin) {
! 3581: if (origin != NULL)
! 3582: result = chain_name(chain, origin, ISC_FALSE);
! 3583:
! 3584: if (result == ISC_R_SUCCESS)
! 3585: result = DNS_R_NEWORIGIN;
! 3586:
! 3587: } else
! 3588: result = ISC_R_SUCCESS;
! 3589:
! 3590: } else
! 3591: result = ISC_R_NOMORE;
! 3592:
! 3593: return (result);
! 3594: }
! 3595:
! 3596: isc_result_t
! 3597: dns_rbtnodechain_first(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
! 3598: dns_name_t *name, dns_name_t *origin)
! 3599:
! 3600: {
! 3601: isc_result_t result;
! 3602:
! 3603: REQUIRE(VALID_RBT(rbt));
! 3604: REQUIRE(VALID_CHAIN(chain));
! 3605:
! 3606: dns_rbtnodechain_reset(chain);
! 3607:
! 3608: chain->end = rbt->root;
! 3609:
! 3610: result = dns_rbtnodechain_current(chain, name, origin, NULL);
! 3611:
! 3612: if (result == ISC_R_SUCCESS)
! 3613: result = DNS_R_NEWORIGIN;
! 3614:
! 3615: return (result);
! 3616: }
! 3617:
! 3618: isc_result_t
! 3619: dns_rbtnodechain_last(dns_rbtnodechain_t *chain, dns_rbt_t *rbt,
! 3620: dns_name_t *name, dns_name_t *origin)
! 3621:
! 3622: {
! 3623: isc_result_t result;
! 3624:
! 3625: REQUIRE(VALID_RBT(rbt));
! 3626: REQUIRE(VALID_CHAIN(chain));
! 3627:
! 3628: dns_rbtnodechain_reset(chain);
! 3629:
! 3630: result = move_chain_to_last(chain, rbt->root);
! 3631: if (result != ISC_R_SUCCESS)
! 3632: return (result);
! 3633:
! 3634: result = dns_rbtnodechain_current(chain, name, origin, NULL);
! 3635:
! 3636: if (result == ISC_R_SUCCESS)
! 3637: result = DNS_R_NEWORIGIN;
! 3638:
! 3639: return (result);
! 3640: }
! 3641:
! 3642:
! 3643: void
! 3644: dns_rbtnodechain_reset(dns_rbtnodechain_t *chain) {
! 3645:
! 3646: REQUIRE(VALID_CHAIN(chain));
! 3647:
! 3648: /*
! 3649: * Free any dynamic storage associated with 'chain', and then
! 3650: * reinitialize 'chain'.
! 3651: */
! 3652: chain->end = NULL;
! 3653: chain->level_count = 0;
! 3654: chain->level_matches = 0;
! 3655: }
! 3656:
! 3657: void
! 3658: dns_rbtnodechain_invalidate(dns_rbtnodechain_t *chain) {
! 3659: /*
! 3660: * Free any dynamic storage associated with 'chain', and then
! 3661: * invalidate 'chain'.
! 3662: */
! 3663:
! 3664: dns_rbtnodechain_reset(chain);
! 3665:
! 3666: chain->magic = 0;
! 3667: }
! 3668:
! 3669: /* XXXMUKS:
! 3670: *
! 3671: * - worth removing inline as static functions are inlined automatically
! 3672: * where suitable by modern compilers.
! 3673: * - bump the size of dns_rbt.nodecount to size_t.
! 3674: * - the dumpfile header also contains a nodecount that is unsigned
! 3675: * int. If large files (> 2^32 nodes) are to be supported, the
! 3676: * allocation for this field should be increased.
! 3677: */
CVSweb <webmaster@jp.NetBSD.org>