rbt.c revision 5d79b60fc5e4dad4f04da39570517d20a2425f8b
7d32c065c7bb56f281651ae3dd2888f32ce4f1d9Bob Halley * Copyright (C) 2004, 2005, 2007-2009, 2011-2015 Internet Systems Consortium, Inc. ("ISC")
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * Copyright (C) 1999-2003 Internet Software Consortium.
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * Permission to use, copy, modify, and/or distribute this software for any
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * purpose with or without fee is hereby granted, provided that the above
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * copyright notice and this permission notice appear in all copies.
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * PERFORMANCE OF THIS SOFTWARE.
0c310d16b05ee94743d33f6920907edee6084fc8Michael Graff/* Principal Authors: DCL */
5fc7ba3e1ac5d72239e9971e0f469dd5796738f9Andreas Gustafsson * This define is so dns/name.h (included by dns/fixedname.h) uses more
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * efficient macro calls instead of functions for a few operations.
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence#define RBT_MAGIC ISC_MAGIC('R', 'B', 'T', '+')
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence#define VALID_RBT(rbt) ISC_MAGIC_VALID(rbt, RBT_MAGIC)
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence * XXXDCL Since parent pointers were added in again, I could remove all of the
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence * chain junk, and replace with dns_rbt_firstnode, _previousnode, _nextnode,
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence * _lastnode. This would involve pretty major change to the API.
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence#define CHAIN_MAGIC ISC_MAGIC('0', '-', '0', '-')
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence#define VALID_CHAIN(chain) ISC_MAGIC_VALID(chain, CHAIN_MAGIC)
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence#define RBT_HASH_SIZE 2 /*%< To give the reallocation code a workout. */
0c8649cea98afc061dd2938fd315df53b8fc35caAndreas Gustafsson void (*data_deleter)(void *, void *);
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * This is the header for map-format RBT images. It is populated,
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * and then written, as the LAST thing done to the file before returning.
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * Writing this last (with zeros in the header area initially) will ensure
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * that the header is only valid when the RBT image is also valid.
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence/* Pad to 32 bytes */
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence/* Header length, always the same size regardless of structure size */
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence isc_uint64_t first_node_offset; /* usually 1024 */
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * information about the system on which the map file was generated
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * will be used to tell if we can load the map file or not
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence unsigned int bigendian:1; /* big or little endian system */
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence unsigned int rdataset_fixed:1; /* compiled with --enable-rrset-fixed */
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence unsigned int nodecount; /* shadow from rbt structure */
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence char version2[32]; /* repeated; must match version1 */
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * The following declarations are for the serialization of an RBT:
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * step one: write out a zeroed header of 1024 bytes
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * step two: walk the tree in a depth-first, left-right-down order, writing
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * out the nodes, reserving space as we go, correcting addresses to point
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * at the proper offset in the file, and setting a flag for each pointer to
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * indicate that it is a reference to a location in the file, rather than in
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * step three: write out the header, adding the information that will be
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * needed to re-create the tree object itself.
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * The RBTDB object will do this three times, once for each of the three
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * RBT objects it contains.
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * Note: 'file' must point an actual open file that can be mmapped
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * and fseeked, not to a pipe or stream
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrencewrite_header(FILE *file, dns_rbt_t *rbt, isc_uint64_t first_node_offset,
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrenceserialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left,
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence uintptr_t right, uintptr_t down, uintptr_t parent,
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrenceserialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence dns_rbtdatawriter_t datawriter, void *writer_arg,
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * The following functions allow you to get the actual address of a pointer
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence * without having to use an if statement to check to see if that address is
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence * relative or not
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrencegetparent(dns_rbtnode_t *node, file_header_t *header) {
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence char *adjusted_address = (char *)(node->parent);
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence adjusted_address += node->parent_is_relative * (uintptr_t)header;
2002be4f65776451676df6ee21a2e28f52bcad6dMark Andrewsgetleft(dns_rbtnode_t *node, file_header_t *header) {
2002be4f65776451676df6ee21a2e28f52bcad6dMark Andrews adjusted_address += node->left_is_relative * (uintptr_t)header;
2002be4f65776451676df6ee21a2e28f52bcad6dMark Andrewsgetright(dns_rbtnode_t *node, file_header_t *header) {
2002be4f65776451676df6ee21a2e28f52bcad6dMark Andrews char *adjusted_address = (char *)(node->right);
2002be4f65776451676df6ee21a2e28f52bcad6dMark Andrews adjusted_address += node->right_is_relative * (uintptr_t)header;
2002be4f65776451676df6ee21a2e28f52bcad6dMark Andrewsgetdown(dns_rbtnode_t *node, file_header_t *header) {
ffe74cc719aa0f10c38fbc1f2f3ea7db0960cb8fMark Andrews adjusted_address += node->down_is_relative * (uintptr_t)header;
bed8e84810a80dad3d37870be927d1dfd015f480Mark Andrewsgetdata(dns_rbtnode_t *node, file_header_t *header) {
8d3e74b1683f714a484bbcf73249e8ee470e36d7Mark Andrews adjusted_address += node->data_is_relative * (uintptr_t)header;
8d3e74b1683f714a484bbcf73249e8ee470e36d7Mark Andrews * Elements of the rbtnode structure.
5d83b561ad7eb84885a8ec63dee4c51b335f067aBrian Wellington#endif /* DNS_RBT_USEHASH */
5d83b561ad7eb84885a8ec63dee4c51b335f067aBrian Wellington#define OLDNAMELEN(node) ((node)->oldnamelen)
5d83b561ad7eb84885a8ec63dee4c51b335f067aBrian Wellington#define IS_ROOT(node) ISC_TF((node)->is_root == 1)
5d83b561ad7eb84885a8ec63dee4c51b335f067aBrian Wellington#define FINDCALLBACK(node) ISC_TF((node)->find_callback == 1)
5d83b561ad7eb84885a8ec63dee4c51b335f067aBrian Wellington * Structure elements from the rbtdb.c, not
54c26ab21c61c6d6b1e484bb88dc3ac263845d17Mark Andrews * used as part of the rbt.c algorithms.
54c26ab21c61c6d6b1e484bb88dc3ac263845d17Mark Andrews * The variable length stuff stored after the node has the following
54c26ab21c61c6d6b1e484bb88dc3ac263845d17Mark Andrews * <name_data>{1..255}<oldoffsetlen>{1}<offsets>{1..128}
bcd7fdf06ca76eb2f6eb157f56b612c503e062a7Mark Andrews * <name_data> contains the name of the node when it was created.
bcd7fdf06ca76eb2f6eb157f56b612c503e062a7Mark Andrews * <oldoffsetlen> contains the length of <offsets> when the node was created.
bcd7fdf06ca76eb2f6eb157f56b612c503e062a7Mark Andrews * <offsets> contains the offets into name for each label when the node was
54c26ab21c61c6d6b1e484bb88dc3ac263845d17Mark Andrews#define NAME(node) ((unsigned char *)((node) + 1))
54c26ab21c61c6d6b1e484bb88dc3ac263845d17Mark Andrews#define OFFSETS(node) (NAME(node) + OLDNAMELEN(node) + 1)
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson#define OLDOFFSETLEN(node) (OFFSETS(node)[-1])
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson#define NODE_SIZE(node) (sizeof(*node) + \
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson OLDNAMELEN(node) + OLDOFFSETLEN(node) + 1)
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson * Color management.
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson#define IS_RED(node) ((node) != NULL && (node)->color == RED)
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson#define IS_BLACK(node) ((node) == NULL || (node)->color == BLACK)
94a537e6ab3069f8d34e12e5ea722250be2b89c8Michael Graff#define MAKE_BLACK(node) ((node)->color = BLACK)
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence * Chain management.
94a537e6ab3069f8d34e12e5ea722250be2b89c8Michael Graff * The "ancestors" member of chains were removed, with their job now
5d83b561ad7eb84885a8ec63dee4c51b335f067aBrian Wellington * being wholly handled by parent pointers (which didn't exist, because
5d83b561ad7eb84885a8ec63dee4c51b335f067aBrian Wellington * of memory concerns, when chains were first implemented).
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson INSIST((chain)->level_count < DNS_RBT_LEVELBLOCK); \
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson (chain)->levels[(chain)->level_count++] = (node); \
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson * The following macros directly access normally private name variables.
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson * These macros are used to avoid a lot of function calls in the critical
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson * path of the tree traversal code.
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafssonstatic inline void
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas GustafssonNODENAME(dns_rbtnode_t *node, dns_name_t *name) {
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson name->attributes |= DNS_NAMEATTR_READONLY;
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafssondns_rbtnode_nodename(dns_rbtnode_t *node, dns_name_t *name) {
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson name->attributes |= DNS_NAMEATTR_READONLY;
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews#define inline
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * A little something to help out in GDB.
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrewshexdump(const char *desc, unsigned char *data, size_t size) {
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews r.length = bytes = (size > BUFSIZ) ? BUFSIZ : size;
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews } while (size > 0);
3d5cad69ec20157912e95cf3b79316dfb0a314f3Mark Andrews#endif /* DEBUG */
44a966dff66061ac3f266c6b451a70733eb78e82Mark Andrews/* Upper node is the parent of the root of the passed node's
44a966dff66061ac3f266c6b451a70733eb78e82Mark Andrews * subtree. The passed node must not be NULL.
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrewsfixup_uppernodes_helper(dns_rbtnode_t *node, dns_rbtnode_t *uppernode) {
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews fixup_uppernodes_helper(LEFT(node), uppernode);
19d365e4448f1782611280b020987988b7ac3210Mark Andrews fixup_uppernodes_helper(RIGHT(node), uppernode);
d981ca645597116d227a48bf37cc5edc061c854dBob Halley * This function is used to fixup uppernode members of all dns_rbtnodes
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * after deserialization.
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews/* The passed node must not be NULL. */
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff/* Upper node is the parent of the root of the passed node's
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * subtree. The passed node must not be NULL.
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * Return the node in the level above the argument node that points
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * to the level the argument node is in. If the argument node is in
0e8cf9a887c70f96ac448b06c069d90b830215ccMark Andrews * the top level, the return value is NULL.
3d5cad69ec20157912e95cf3b79316dfb0a314f3Mark Andrews#endif /* DNS_RBT_USEHASH */
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrencedns__rbtnode_getdistance(dns_rbtnode_t *node) {
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * Forward declarations.
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrewscreate_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep);
0e8cf9a887c70f96ac448b06c069d90b830215ccMark Andrewsstatic inline void
0e8cf9a887c70f96ac448b06c069d90b830215ccMark Andrewshash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name);
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graffstatic inline void
3d5cad69ec20157912e95cf3b79316dfb0a314f3Mark Andrewsunhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrewsstatic inline void
3d5cad69ec20157912e95cf3b79316dfb0a314f3Mark Andrewsrotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
6e49e91bd08778d7eae45a2229dcf41ed97cc636David Lawrencestatic inline void
f0a5bb8f86631ce638cb2b6c65bbb9bcf9b0cdc0Bob Halleyrotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
f0a5bb8f86631ce638cb2b6c65bbb9bcf9b0cdc0Bob Halleyaddonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrewsdeletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp);
52637f592f705ca93fadc218e403fd55e8ce4aeaMark Andrewstreefix(dns_rbt_t *rbt, void *base, size_t size,
0e8cf9a887c70f96ac448b06c069d90b830215ccMark Andrewsdeletetreeflat(dns_rbt_t *rbt, unsigned int quantum, isc_boolean_t unhash,
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graffprintnodename(dns_rbtnode_t *node, isc_boolean_t quoted, FILE *f);
3d5cad69ec20157912e95cf3b79316dfb0a314f3Mark Andrewsfreenode(dns_rbt_t *rbt, dns_rbtnode_t **nodep);
20b20b23948b90cb2f7d7f402da99d09f837efd0David Lawrence * Write out a zeroed header as a placeholder. Doing this ensures
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence * that the file will not read while it is partially written, should
fdd04623a6a36aad8449ef0877d8801a558873b8Mark Andrews * writing fail or be interrupted.
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews result = isc_stdio_write(buffer, 1, HEADER_LENGTH, file, NULL);
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * Write out the real header, including NodeDump version information
3d5cad69ec20157912e95cf3b79316dfb0a314f3Mark Andrews * and the offset of the first node.
3d5cad69ec20157912e95cf3b79316dfb0a314f3Mark Andrews * Any information stored in the rbt object itself should be stored
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrewswrite_header(FILE *file, dns_rbt_t *rbt, isc_uint64_t first_node_offset,
c0d0a59d1b665423b8a0d1829d0f0da121cb3473Andreas Gustafsson memmove(header.version1, FILE_VERSION, sizeof(header.version1));
fdd04623a6a36aad8449ef0877d8801a558873b8Mark Andrews memmove(header.version2, FILE_VERSION, sizeof(header.version2));
fdd04623a6a36aad8449ef0877d8801a558873b8Mark Andrews header.ptrsize = (isc_uint32_t) sizeof(void *);
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews CHECK(isc_stdio_seek(file, location, SEEK_SET));
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff CHECK(isc_stdio_write(&header, 1, sizeof(file_header_t), file, NULL));
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews /* Ensure we are always at the end of the file. */
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrewsserialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left,
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff uintptr_t right, uintptr_t down, uintptr_t parent,
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews unsigned char *node_data;
6e49e91bd08778d7eae45a2229dcf41ed97cc636David Lawrence file_position = dns_rbt_serialize_align(file_position);
19d365e4448f1782611280b020987988b7ac3210Mark Andrews CHECK(isc_stdio_seek(file, file_position, SEEK_SET));
3d5cad69ec20157912e95cf3b79316dfb0a314f3Mark Andrews * If the next node is not NULL, calculate the next node's location
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * in the file. Note that this will have to change when the data
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * structure changes, and it also assumes that we always write the
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * nodes out in list order (which we currently do.)
7ab0e69f61e61e81d489c95c7ebd981e74e7ef16Andreas Gustafsson temp_node.parent = (dns_rbtnode_t *)(parent);
7ab0e69f61e61e81d489c95c7ebd981e74e7ef16Andreas Gustafsson temp_node.left = (dns_rbtnode_t *)(left);
7ab0e69f61e61e81d489c95c7ebd981e74e7ef16Andreas Gustafsson temp_node.right = (dns_rbtnode_t *)(right);
0c8649cea98afc061dd2938fd315df53b8fc35caAndreas Gustafsson temp_node.data = (dns_rbtnode_t *)(data);
0c8649cea98afc061dd2938fd315df53b8fc35caAndreas Gustafsson node_data = (unsigned char *) node + sizeof(dns_rbtnode_t);
0c8649cea98afc061dd2938fd315df53b8fc35caAndreas Gustafsson datasize = NODE_SIZE(node) - sizeof(dns_rbtnode_t);
0c8649cea98afc061dd2938fd315df53b8fc35caAndreas Gustafsson CHECK(isc_stdio_write(&temp_node, 1, sizeof(dns_rbtnode_t),
0c8649cea98afc061dd2938fd315df53b8fc35caAndreas Gustafsson CHECK(isc_stdio_write(node_data, 1, datasize, file, NULL));
3ddd814a97de1d152ba0913c592d6e6dc83d38a6Michael Graff hexdump("node header", (unsigned char*) &temp_node,
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff isc_crc64_update(crc, (const isc_uint8_t *) &temp_node,
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews isc_crc64_update(crc, (const isc_uint8_t *) node_data, datasize);
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrewsserialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews dns_rbtdatawriter_t datawriter, void *writer_arg,
3d5cad69ec20157912e95cf3b79316dfb0a314f3Mark Andrews uintptr_t left = 0, right = 0, down = 0, data = 0;
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews /* Reserve space for current node. */
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff CHECK(isc_stdio_seek(file, location, SEEK_SET));
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews offset_adjust = dns_rbt_serialize_align(location + NODE_SIZE(node));
19d365e4448f1782611280b020987988b7ac3210Mark Andrews CHECK(isc_stdio_seek(file, offset_adjust, SEEK_SET));
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * Serialize the rest of the tree.
3d5cad69ec20157912e95cf3b79316dfb0a314f3Mark Andrews * WARNING: A change in the order (from left, right, down)
3d5cad69ec20157912e95cf3b79316dfb0a314f3Mark Andrews * will break the way the crc hash is computed.
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews CHECK(serialize_nodes(file, getleft(node, NULL), location,
94a3bcd132e515b4baa0884ba9dd0f361d2e17bcMark Andrews CHECK(serialize_nodes(file, getright(node, NULL), location,
94a3bcd132e515b4baa0884ba9dd0f361d2e17bcMark Andrews CHECK(serialize_nodes(file, getdown(node, NULL), location,
d981ca645597116d227a48bf37cc5edc061c854dBob Halley /* Seek back to reserved space. */
d981ca645597116d227a48bf37cc5edc061c854dBob Halley /* Serialize the current node. */
d981ca645597116d227a48bf37cc5edc061c854dBob Halley CHECK(serialize_node(file, node, left, right, down, parent, data, crc));
d981ca645597116d227a48bf37cc5edc061c854dBob Halley /* Ensure we are always at the end of the file. */
0513f89e68f82f9ec54e7af9c979a7c43babbe31Bob Halleydns_rbt_serialize_tree(FILE *file, dns_rbt_t *rbt,
0513f89e68f82f9ec54e7af9c979a7c43babbe31Bob Halley off_t header_position, node_position, end_position;
6324997211a5e2d82528dcde98e8981190a35faeMichael Graff CHECK(isc_stdio_tell(file, &header_position));
6324997211a5e2d82528dcde98e8981190a35faeMichael Graff /* Write dummy header */
3ddd814a97de1d152ba0913c592d6e6dc83d38a6Michael Graff /* Serialize nodes */
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson CHECK(isc_stdio_tell(file, &node_position));
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson CHECK(serialize_nodes(file, rbt->root, 0, datawriter,
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson CHECK(isc_stdio_tell(file, &end_position));
88ba491496daf4463a2c898be8a6c47775a6d048Mark Andrews CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson hexdump("serializing CRC", (unsigned char *)&crc, sizeof(crc));
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson /* Serialize header */
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson CHECK(write_header(file, rbt, HEADER_LENGTH, crc));
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson /* Ensure we are always at the end of the file. */
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson *offset = dns_rbt_serialize_align(header_position);
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson#define CONFIRM(a) do { \
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson if (! (a)) { \
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Grafftreefix(dns_rbt_t *rbt, void *base, size_t filesize, dns_rbtnode_t *n,
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson dns_name_t *name, dns_rbtdatafixer_t datafixer,
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson unsigned char *node_data;
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson size_t datasize, nodemax = filesize - sizeof(dns_rbtnode_t);
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson CONFIRM((char *) n - (char *) base <= (int) nodemax);
3ddd814a97de1d152ba0913c592d6e6dc83d38a6Michael Graff CHECK(dns_name_concatenate(&nodename, name, fullname, NULL));
a98551ef592e9be6008e0141ceeb32efd586c5efMark Andrews /* memorize header contents prior to fixup */
ed019cabc1cc75d4412010c331876e4ae5080a4dDavid Lawrence CONFIRM(n->left <= (dns_rbtnode_t *) nodemax);
16996a04884731d647f43a5eb54f678581f09f68David Lawrence CONFIRM(n->right <= (dns_rbtnode_t *) nodemax);
fa460c223a69449eaac67ddb6abafe74f5e1ff02Michael Graff CONFIRM(n->down <= (dns_rbtnode_t *) nodemax);
fa460c223a69449eaac67ddb6abafe74f5e1ff02Michael Graff CONFIRM(n->parent <= (dns_rbtnode_t *) nodemax);
fa460c223a69449eaac67ddb6abafe74f5e1ff02Michael Graff /* a change in the order (from left, right, down) will break hashing*/
fa460c223a69449eaac67ddb6abafe74f5e1ff02Michael Graff CHECK(treefix(rbt, base, filesize, n->left, name,
fa460c223a69449eaac67ddb6abafe74f5e1ff02Michael Graff CHECK(treefix(rbt, base, filesize, n->right, name,
fa460c223a69449eaac67ddb6abafe74f5e1ff02Michael Graff CHECK(treefix(rbt, base, filesize, n->down, fullname,
fa460c223a69449eaac67ddb6abafe74f5e1ff02Michael Graff CHECK(datafixer(n, base, filesize, fixer_arg, crc));
fa460c223a69449eaac67ddb6abafe74f5e1ff02Michael Graff node_data = (unsigned char *) n + sizeof(dns_rbtnode_t);
fa460c223a69449eaac67ddb6abafe74f5e1ff02Michael Graff datasize = NODE_SIZE(n) - sizeof(dns_rbtnode_t);
94a537e6ab3069f8d34e12e5ea722250be2b89c8Michael Graff hexdump("node header", (unsigned char *) &header,
94a537e6ab3069f8d34e12e5ea722250be2b89c8Michael Graff isc_crc64_update(crc, (const isc_uint8_t *) &header,
94a537e6ab3069f8d34e12e5ea722250be2b89c8Michael Graff isc_crc64_update(crc, (const isc_uint8_t *) node_data,
94a537e6ab3069f8d34e12e5ea722250be2b89c8Michael Graffdns_rbt_deserialize_tree(void *base_address, size_t filesize,
94a537e6ab3069f8d34e12e5ea722250be2b89c8Michael Graff dns_rbtdatafixer_t datafixer, void *fixer_arg,
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence REQUIRE(originp == NULL || *originp == NULL);
6324997211a5e2d82528dcde98e8981190a35faeMichael Graff CHECK(dns_rbt_create(mctx, deleter, deleter_arg, &rbt));
8d3e74b1683f714a484bbcf73249e8ee470e36d7Mark Andrews header = (file_header_t *)((char *)base_address + header_offset);
8d3e74b1683f714a484bbcf73249e8ee470e36d7Mark Andrews if (header->ptrsize != (isc_uint32_t) sizeof(void *)) {
5d83b561ad7eb84885a8ec63dee4c51b335f067aBrian Wellington if (header->bigendian != (1 == htonl(1)) ? 1 : 0) {
5d83b561ad7eb84885a8ec63dee4c51b335f067aBrian Wellington /* Copy other data items from the header into our rbt. */
5d83b561ad7eb84885a8ec63dee4c51b335f067aBrian Wellington rbt->root = (dns_rbtnode_t *)((char *)base_address +
5d83b561ad7eb84885a8ec63dee4c51b335f067aBrian Wellington header_offset + header->first_node_offset);
5d83b561ad7eb84885a8ec63dee4c51b335f067aBrian Wellington if ((header->nodecount * sizeof(dns_rbtnode_t)) > filesize) {
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson CHECK(treefix(rbt, base_address, filesize, rbt->root,
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson hexdump("deserializing CRC", (unsigned char *)&crc, sizeof(crc));
54c26ab21c61c6d6b1e484bb88dc3ac263845d17Mark Andrews /* Check file hash */
54c26ab21c61c6d6b1e484bb88dc3ac263845d17Mark Andrews#endif /* DNS_RBT_USEHASH */
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson if (result != ISC_R_SUCCESS && rbt != NULL) {
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson * Initialize a red/black tree of trees.
88ba491496daf4463a2c898be8a6c47775a6d048Mark Andrewsdns_rbt_create(isc_mem_t *mctx, dns_rbtdeleter_t deleter,
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson REQUIRE(deleter == NULL ? deleter_arg == NULL : 1);
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson rbt = (dns_rbt_t *)isc_mem_get(mctx, sizeof(*rbt));
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson * Deallocate a red/black tree of trees.
3ddd92da6651bc72aa79a04195ad389d86fd1a66Andreas Gustafsson RUNTIME_CHECK(dns_rbt_destroy2(rbtp, 0) == ISC_R_SUCCESS);
54c26ab21c61c6d6b1e484bb88dc3ac263845d17Mark Andrewsdns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum) {
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence deletetreeflat(rbt, quantum, ISC_FALSE, &rbt->root);
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrewschain_name(dns_rbtnodechain_t *chain, dns_name_t *name,
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews for (i = (int)chain->level_count - 1; i >= 0; i--) {
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews result = dns_name_concatenate(name, &nodename, name, NULL);
7d62ddffbb4d1cc97b8d80b7ee4944554a57523eMark Andrewsmove_chain_to_last(dns_rbtnodechain_t *chain, dns_rbtnode_t *node) {
6e49e91bd08778d7eae45a2229dcf41ed97cc636David Lawrence * Go as far right and then down as much as possible,
7d62ddffbb4d1cc97b8d80b7ee4944554a57523eMark Andrews * as long as the rightmost node has a down pointer.
7d62ddffbb4d1cc97b8d80b7ee4944554a57523eMark Andrews } while (1);
7d62ddffbb4d1cc97b8d80b7ee4944554a57523eMark Andrews * Add 'name' to tree, initializing its data pointer with 'data'.
7d62ddffbb4d1cc97b8d80b7ee4944554a57523eMark Andrewsdns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) {
7d62ddffbb4d1cc97b8d80b7ee4944554a57523eMark Andrews * Does this thing have too many variables or what?
7d62ddffbb4d1cc97b8d80b7ee4944554a57523eMark Andrews dns_rbtnode_t **root, *parent, *child, *current, *new_current;
7d62ddffbb4d1cc97b8d80b7ee4944554a57523eMark Andrews dns_name_t *add_name, *new_name, current_name, *prefix, *suffix;
7d62ddffbb4d1cc97b8d80b7ee4944554a57523eMark Andrews dns_fixedname_t fixedcopy, fixedprefix, fixedsuffix, fnewname;
7d62ddffbb4d1cc97b8d80b7ee4944554a57523eMark Andrews * Create a copy of the name so the original name structure is
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff * not modified.
7d62ddffbb4d1cc97b8d80b7ee4944554a57523eMark Andrews result = create_node(rbt->mctx, add_name, &new_current);
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews#endif /* DNS_RBT_USEHASH */
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews compared = dns_name_fullcompare(add_name, ¤t_name,
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews } else if (order > 0) {
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * This name has some suffix in common with the
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * name at the current node. If the name at
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * the current node is shorter, that means the
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff * new name should be in a subtree. If the
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * name at the current node is longer, that means
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * the down pointer to this tree should point
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * to a new tree that has the common suffix, and
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff * the non-common parts of these two names should
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * start a new tree.
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * All of the existing labels are in common,
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * so the new name is in a subtree.
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * Whack off the common labels for the
6e49e91bd08778d7eae45a2229dcf41ed97cc636David Lawrence * not-in-common part to be searched for
6e49e91bd08778d7eae45a2229dcf41ed97cc636David Lawrence * in the next level.
15330e4fa27c82ac04cc2ce234ec930e4b6b42d3Mark Andrews * Follow the down pointer (possibly NULL).
1c3191528684f3dd93ebb122298c2f8ebfc6d397Mark Andrews * The number of labels in common is fewer
34b394b43e2207e8f8f3703f0402422121455638David Lawrence * than the number of labels at the current
6e49e91bd08778d7eae45a2229dcf41ed97cc636David Lawrence * node, so the current node must be adjusted
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * to have just the common suffix, and a down
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff * pointer made to a new tree.
5a219d878f0bd786e86da2c9b92999260dda3f8dAndreas Gustafsson * Ensure the number of levels in the tree
5a219d878f0bd786e86da2c9b92999260dda3f8dAndreas Gustafsson * does not exceed the number of logical
5a219d878f0bd786e86da2c9b92999260dda3f8dAndreas Gustafsson * levels allowed by DNSSEC.
6e49e91bd08778d7eae45a2229dcf41ed97cc636David Lawrence * XXXDCL need a better error result?
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff * XXXDCL Since chain ancestors were removed,
7c0378745269fe49a05904935afc42b85528f53aDavid Lawrence * no longer used by addonlevel(),
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff * this is the only real use of chains in the
5a219d878f0bd786e86da2c9b92999260dda3f8dAndreas Gustafsson * function. It could be done instead with
5a219d878f0bd786e86da2c9b92999260dda3f8dAndreas Gustafsson * a simple integer variable, but I am pressed
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * Split the name into two parts, a prefix
035504dbd8ca5949e8380b860873b3385a4e61e5Mark Andrews * which is the not-in-common parts of the
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * two names and a suffix that is the common
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * parts of them.
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * Reproduce the tree attributes of the
5d51e67c3b4f35c1be742574aacc1d88fe6ed444Mark Andrews * current node.
5a219d878f0bd786e86da2c9b92999260dda3f8dAndreas Gustafsson if (current->nsec == DNS_RBT_NSEC_HAS_NSEC)
0e8cf9a887c70f96ac448b06c069d90b830215ccMark Andrews * Fix pointers that were to the current node.
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff * Set up the new root of the next level.
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * By definition it will not be the top
44a966dff66061ac3f266c6b451a70733eb78e82Mark Andrews * level tree, so clear DNS_NAMEATTR_ABSOLUTE.
44a966dff66061ac3f266c6b451a70733eb78e82Mark Andrews#endif /* DNS_RBT_USEHASH */
44a966dff66061ac3f266c6b451a70733eb78e82Mark Andrews * The name has been added by pushing
44a966dff66061ac3f266c6b451a70733eb78e82Mark Andrews * the not-in-common parts down to
44a966dff66061ac3f266c6b451a70733eb78e82Mark Andrews * a new level.
44a966dff66061ac3f266c6b451a70733eb78e82Mark Andrews * The current node has no data,
44a966dff66061ac3f266c6b451a70733eb78e82Mark Andrews * because it is just a placeholder.
904294c0c952227f7778fd0ba2ccea08c097b872Mark Andrews * Its data pointer is already NULL
904294c0c952227f7778fd0ba2ccea08c097b872Mark Andrews * from create_node()), so there's
44a966dff66061ac3f266c6b451a70733eb78e82Mark Andrews * nothing more to do to it.
ffe74cc719aa0f10c38fbc1f2f3ea7db0960cb8fMark Andrews * The not-in-common parts of the new
47b26abe77184f9bedc68e36bdad03332cf67570David Lawrence * name will be inserted into the new
47b26abe77184f9bedc68e36bdad03332cf67570David Lawrence * level following this loop (unless
47b26abe77184f9bedc68e36bdad03332cf67570David Lawrence * result != ISC_R_SUCCESS, which
47b26abe77184f9bedc68e36bdad03332cf67570David Lawrence * is tested after the loop ends).
47b26abe77184f9bedc68e36bdad03332cf67570David Lawrence result = create_node(rbt->mctx, add_name, &new_current);
8a17d1e7cdba9fdcf71fb2f821a954a251204105Mark Andrews#endif /* DNS_RBT_USEHASH */
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * Add a name to the tree of trees, associating it with some data.
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrewsdns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data) {
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * dns_rbt_addnode will report the node exists even when
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * it does not have data associated with it, but the
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * dns_rbt_*name functions all behave depending on whether
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * there is data associated with a node.
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews (result == ISC_R_EXISTS && DATA(node) == NULL)) {
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * Find the node for "name" in the tree of trees.
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrewsdns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname,
3ddd814a97de1d152ba0913c592d6e6dc83d38a6Michael Graff dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews unsigned int options, dns_rbtfindcallback_t callback,
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews dns_rbtnode_t *current, *last_compared, *current_root;
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews dns_name_t *search_name, current_name, *callback_name;
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews dns_fixedname_t fixedcallbackname, fixedsearchname;
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews unsigned int hlabels = 0;
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews REQUIRE((options & (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR))
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews != (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR));
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * If there is a chain it needs to appear to be in a sane state,
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * otherwise a chain is still needed to generate foundname and
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * callback_name.
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * Appease GCC about variables it incorrectly thinks are
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * possibly used uninitialized.
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews callback_name = dns_fixedname_name(&fixedcallbackname);
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * search_name is the name segment being sought in each tree level.
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * By using a fixedname, the search_name will definitely have offsets
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * for use by any splitting.
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * By using dns_name_clone, no name data should be copied thanks to
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * the lack of bitstring labels.
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff search_name = dns_fixedname_name(&fixedsearchname);
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence compared = dns_name_fullcompare(search_name, ¤t_name,
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * last_compared is used as a shortcut to start (or
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * continue rather) finding the stop-node of the search
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * when hashing was used (see much below in this
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * Here, current is pointing at a subtree root
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * node. We try to find a matching node using
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * the hashtable. We can get one of 3 results
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * here: (a) we locate the matching node, (b) we
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * find a node to which the current node has a
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * subdomain relation, (c) we fail to find (a)
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews unsigned int hash;
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * The case of current != current_root, that
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * means a left or right pointer was followed,
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * only happens when the algorithm fell through to
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * the traditional binary search because of a
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * bitstring label. Since we dropped the bitstring
df8c9ee4819c97089664ccc035eb2aa7569034fdDavid Lawrence * support, this should not happen.
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * current_root is the root of the current level, so
df8c9ee4819c97089664ccc035eb2aa7569034fdDavid Lawrence * its parent is the same as its "up" pointer.
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * Compute the hash over the full absolute
df8c9ee4819c97089664ccc035eb2aa7569034fdDavid Lawrence * name. Look for the smallest suffix match at
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * this tree level (hlevel), and then at every
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * iteration, look for the next smallest suffix
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * match (add another subdomain label to the
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * absolute name being hashed).
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence hash = dns_name_fullhash(&hash_name, ISC_FALSE);
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * Walk all the nodes in the hash bucket pointed
6e49e91bd08778d7eae45a2229dcf41ed97cc636David Lawrence * by the computed hash value.
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews for (hnode = rbt->hashtable[hash % rbt->hashsize];
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * This checks that the hashed label
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * sequence being looked up is at the
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * same tree level, so that we don't
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * match a labelsequence from some other
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * subdomain.
83ac7ce833930a5c6cb92ad9c04a58e775579e73Bob Halley * This is an optimization. If hashing found
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * the right node, the next call to
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * dns_name_fullcompare() would obviously
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * return _equal or _subdomain. Determine
83ac7ce833930a5c6cb92ad9c04a58e775579e73Bob Halley * which of those would be the case by
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * checking if the full name was hashed. Then
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * make it look like dns_name_fullcompare
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff * was called and jump to the right place.
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * All of the labels have been tried against the hash
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * table. Since we dropped the support of bitstring
419590499823ce15b5d2ad4fe71eaf04bd5a86c0Michael Graff * labels, the name isn't in the table.
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews#else /* DNS_RBT_USEHASH */
3ddd814a97de1d152ba0913c592d6e6dc83d38a6Michael Graff * Standard binary search tree movement.
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews#endif /* DNS_RBT_USEHASH */
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * The names have some common suffix labels.
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * If the number in common are equal in length to
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * the current node's name length, then follow the
3a4ec3da9fa14511cbc3660f75817cfacb3f4d1eMark Andrews * down pointer and search in the new tree.
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * Whack off the current node's common parts
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence * for the name to search in the next level.
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * This might be the closest enclosing name.
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence * Point the chain to the next level. This
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence * needs to be done before 'current' is pointed
6d12fdf96621801e80f3f4c2a8a569fe48766a20David Lawrence * there because the callback in the next
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * block of code needs the current 'current',
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * but in the event the callback requests that
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * the search be stopped then the
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * DNS_R_PARTIALMATCH code at the end of this
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * function needs the chain pointed to the
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * next level.
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * The caller may want to interrupt the
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * downward search when certain special nodes
20b20b23948b90cb2f7d7f402da99d09f837efd0David Lawrence * are traversed. If this is a special node,
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * the callback is used to learn what the
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * caller wants to do.
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * Treat this node as if it
82d05588933a3c765aa8518fe455d6477d640b99Mark Andrews * had no down pointer.
0513f89e68f82f9ec54e7af9c979a7c43babbe31Bob Halley * Finally, head to the next tree level.
6324997211a5e2d82528dcde98e8981190a35faeMichael Graff * Though there are labels in common, the
6324997211a5e2d82528dcde98e8981190a35faeMichael Graff * entire name at this node is not common
6324997211a5e2d82528dcde98e8981190a35faeMichael Graff * with the search name so the search
7ec579cd5d07228c0d6cece58b80694ad8d59de9Michael Graff * name does not exist in the tree.
ebd68da027cfa8da0fb536c3db11bb88292f41c7Andreas Gustafsson INSIST(compared == dns_namereln_commonancestor
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * If current is not NULL, NOEXACT is not disallowing exact matches,
7ec579cd5d07228c0d6cece58b80694ad8d59de9Michael Graff * and either the node has data or an empty node is ok, return
7ec579cd5d07228c0d6cece58b80694ad8d59de9Michael Graff * ISC_R_SUCCESS to indicate an exact match.
7ec579cd5d07228c0d6cece58b80694ad8d59de9Michael Graff if (current != NULL && (options & DNS_RBTFIND_NOEXACT) == 0 &&
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * Found an exact match.
3bb3b7ac462a90c2b8b1fb783324d800e2ba748cMichael Graff result = chain_name(chain, foundname, ISC_TRUE);
f8aae502686e2448c48f56697c212a50e2a1cbaeAndreas Gustafsson * Did not find an exact match (or did not want one).
6324997211a5e2d82528dcde98e8981190a35faeMichael Graff * ... but found a partially matching superdomain.
6324997211a5e2d82528dcde98e8981190a35faeMichael Graff * Unwind the chain to the partial match node
6324997211a5e2d82528dcde98e8981190a35faeMichael Graff * to set level_matches to the level above the node,
b469f0321d2bcea3914c57d26fd43319e506c313Andreas Gustafsson * and then to derive the name.
b469f0321d2bcea3914c57d26fd43319e506c313Andreas Gustafsson * chain->level_count is guaranteed to be at least 1
8abddcd3f24476b945419659e7cb73bcb970886bDavid Lawrence * here because by definition of finding a superdomain,
6324997211a5e2d82528dcde98e8981190a35faeMichael Graff * the chain is pointed to at least the first subtree.
6324997211a5e2d82528dcde98e8981190a35faeMichael Graff chain->level_matches = chain->level_count - 1;
6324997211a5e2d82528dcde98e8981190a35faeMichael Graff while (chain->levels[chain->level_matches] != *node) {
014892d86d30b7eceb0003d51788f9b5cadfc1bfAndreas Gustafsson unsigned int saved_count = chain->level_count;
014892d86d30b7eceb0003d51788f9b5cadfc1bfAndreas Gustafsson chain->level_count = chain->level_matches + 1;
&order,
if (order < 0)
if (order > 0) {
result2 =
NULL,
NULL);
return (result);
return (result);
* node tree of "b.a.com" and layer 2 a three node tree of
* a, b, and c. Deleting a.com would find only a partial depth
* solely the province of rbtdb.c.
return (result);
* then the subsequent deletion of "b.c" will not cause "a" to be pulled up,
* restoring "a.b.c". The RBT *used* to do this kind of rejoining, but it
* that had "b.c" as one of its levels -- and the RBT has no idea what
* "b.c" is left hanging around without data or children. This condition
if (recurse) {
return (ISC_R_SUCCESS);
#if DNS_RBT_USEMAGIC
return (ISC_R_SUCCESS);
return (result);
return (printname);
static isc_result_t
unsigned int labels;
return (ISC_R_NOMEMORY);
#ifdef DNS_RBT_USEHASH
#if DNS_RBT_USEMAGIC
return (ISC_R_SUCCESS);
#ifdef DNS_RBT_USEHASH
unsigned int hash;
static isc_result_t
unsigned int bytes;
return (ISC_R_NOMEMORY);
return (ISC_R_SUCCESS);
unsigned int oldsize;
unsigned int hash;
for (i = 0; i < oldsize; i++) {
unsigned int bucket;
if (order < 0) {
if (unhash)
#if DNS_RBT_USEMAGIC
static size_t
static isc_boolean_t
return (ISC_TRUE);
return (ISC_FALSE);
return (ISC_FALSE);
return (ISC_FALSE);
static isc_boolean_t
return (ISC_TRUE);
return (ISC_FALSE);
return (ISC_FALSE);
return (ISC_FALSE);
return (ISC_FALSE);
dl++;
return (ISC_TRUE);
return (ISC_FALSE);
for (i = 0; i < depth; i++)
isc_region_t r;
if (quoted)
depth++;
data_printer, f);
data_printer, f);
data_printer, f);
if (show_pointers)
*nodecount, d);
return (*nodecount);
unsigned int nodecount = 0;
return (ISC_R_NOTFOUND);
return (result);
if (new_origin) {
NULL);
NULL);
return (result);
if (new_origin) {
return (result);
return (result);
if (new_origin) {
return (result);
return (result);
return (result);
return (result);