rbt.c revision d9f0c713fe1d50f1848ca827c5f31db79d904f04
9d5ed744c46ef241b9d3ba134bf3155e0b62ac9eAutomatic Updater * Copyright (C) 2004, 2005, 2007-2009, 2011-2013 Internet Systems Consortium, Inc. ("ISC")
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * Copyright (C) 1999-2003 Internet Software Consortium.
ec5347e2c775f027573ce5648b910361aa926c01Automatic Updater * Permission to use, copy, modify, and/or distribute this software for any
bf43fdafa3bff9e84cb03f1a19aca74514d2516eBob Halley * purpose with or without fee is hereby granted, provided that the above
bf43fdafa3bff9e84cb03f1a19aca74514d2516eBob Halley * copyright notice and this permission notice appear in all copies.
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * PERFORMANCE OF THIS SOFTWARE.
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence/* Principal Authors: DCL */
09f22ac5b09e70bc526015f37168ba33e21ea91fDavid Lawrence * This define is so dns/name.h (included by dns/fixedname.h) uses more
e419f613d8591885df608cb73065921be07dd12eBob Halley * efficient macro calls instead of functions for a few operations.
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews#define VALID_RBT(rbt) ISC_MAGIC_VALID(rbt, RBT_MAGIC)
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * XXXDCL Since parent pointers were added in again, I could remove all of the
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * chain junk, and replace with dns_rbt_firstnode, _previousnode, _nextnode,
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * _lastnode. This would involve pretty major change to the API.
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews#define CHAIN_MAGIC ISC_MAGIC('0', '-', '0', '-')
d2ef84e07b67e72a4bd9c729c6b8228067d17584Mark Andrews#define VALID_CHAIN(chain) ISC_MAGIC_VALID(chain, CHAIN_MAGIC)
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews#define RBT_HASH_SIZE 2 /*%< To give the reallocation code a workout. */
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews unsigned int magic;
92ef1a9b9dbd48ecb507b42ac62c15afefdaf838David Lawrence void (*data_deleter)(void *, void *);
bf43fdafa3bff9e84cb03f1a19aca74514d2516eBob Halley unsigned int nodecount;
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews unsigned int hashsize;
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * This is the header for map-format RBT images. It is populated,
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews * and then written, as the LAST thing done to the file before returning.
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews * Writing this last (with zeros in the header area initially) will ensure
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews * that the header is only valid when the RBT image is also valid.
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews/* Pad to 32 bytes */
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews/* Header length, always the same size regardless of structure size */
50105afc551903541608b11851d73278b23579a3Mark Andrews isc_uint64_t first_node_offset; /* usually 1024 */
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * information about the system on which the map file was generated
e2c3f8059e77a8e11c4378d22e5d8e78b423a28fMark Andrews * will be used to tell if we can load the map file or not
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews unsigned int bigendian:1; /* big or little endian system */
ed019cabc1cc75d4412010c331876e4ae5080a4dDavid Lawrence unsigned int rdataset_fixed:1; /* compiled with --enable-rrset-fixed */
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington unsigned int nodecount; /* shadow from rbt structure */
ed019cabc1cc75d4412010c331876e4ae5080a4dDavid Lawrence char version2[32]; /* repeated; must match version1 */
ed019cabc1cc75d4412010c331876e4ae5080a4dDavid Lawrence * The following declarations are for the serialization of an RBT:
50105afc551903541608b11851d73278b23579a3Mark Andrews * step one: write out a zeroed header of 1024 bytes
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * step two: walk the tree in a depth-first, left-right-down order, writing
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington * out the nodes, reserving space as we go, correcting addresses to point
93d6dfaf66258337985427c86181f01fc51f0bb4Mark Andrews * at the proper offset in the file, and setting a flag for each pointer to
ed019cabc1cc75d4412010c331876e4ae5080a4dDavid Lawrence * indicate that it is a reference to a location in the file, rather than in
664e11f0b14c78cef7cf6b8c70323a1da494e351Mark Andrews * step three: write out the header, adding the information that will be
664e11f0b14c78cef7cf6b8c70323a1da494e351Mark Andrews * needed to re-create the tree object itself.
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington * The RBTDB object will do this three times, once for each of the three
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington * RBT objects it contains.
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington * Note: 'file' must point an actual open file that can be mmapped
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington * and fseeked, not to a pipe or stream
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewswrite_header(FILE *file, dns_rbt_t *rbt, isc_uint64_t first_node_offset,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews unsigned char *digest);
50105afc551903541608b11851d73278b23579a3Mark Andrewsserialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left,
50105afc551903541608b11851d73278b23579a3Mark Andrews uintptr_t right, uintptr_t down, uintptr_t parent,
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrewsserialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews dns_rbtdatawriter_t datawriter, isc_uint32_t serial,
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * The following functions allow you to get the actual address of a pointer
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * without having to use an if statement to check to see if that address is
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * relative or not
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrewsgetparent(dns_rbtnode_t *node, file_header_t *header) {
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews char *adjusted_address = (char *)(node->parent);
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews adjusted_address += node->parent_is_relative * (uintptr_t)header;
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrewsgetleft(dns_rbtnode_t *node, file_header_t *header) {
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley adjusted_address += node->left_is_relative * (uintptr_t)header;
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halleystatic inline dns_rbtnode_t *
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halleygetright(dns_rbtnode_t *node, file_header_t *header) {
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley adjusted_address += node->right_is_relative * (uintptr_t)header;
b5debbe212097d1c573a2ba3bd9a3d526d86b0aeBrian Wellington return ((dns_rbtnode_t *)adjusted_address);
e44487bfc23599b6b240e09d83d1c862fecfcc82Michael Graffgetdown(dns_rbtnode_t *node, file_header_t *header) {
e44487bfc23599b6b240e09d83d1c862fecfcc82Michael Graff char *adjusted_address = (char *)(node->down);
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley adjusted_address += node->down_is_relative * (uintptr_t)header;
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewsgetdata(dns_rbtnode_t *node, file_header_t *header) {
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews adjusted_address += node->data_is_relative * (uintptr_t)header;
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Elements of the rbtnode structure.
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews#define IS_ROOT(node) ISC_TF((node)->is_root == 1)
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews#define FINDCALLBACK(node) ISC_TF((node)->find_callback == 1)
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews * Structure elements from the rbtdb.c, not
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews * used as part of the rbt.c algorithms.
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews * The variable length stuff stored after the node has the following
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews * structure.
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews * <name_data>{1..255}<oldoffsetlen>{1}<offsets>{1..128}
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews * <name_data> contains the name of the node when it was created.
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews * <oldoffsetlen> contains the length of <offsets> when the node was created.
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews * <offsets> contains the offets into name for each label when the node was
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews#define NAME(node) ((unsigned char *)((node) + 1))
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews#define OFFSETS(node) (NAME(node) + OLDNAMELEN(node) + 1)
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * Color management.
b5debbe212097d1c573a2ba3bd9a3d526d86b0aeBrian Wellington#define IS_RED(node) ((node) != NULL && (node)->color == RED)
b5debbe212097d1c573a2ba3bd9a3d526d86b0aeBrian Wellington#define IS_BLACK(node) ((node) == NULL || (node)->color == BLACK)
b5debbe212097d1c573a2ba3bd9a3d526d86b0aeBrian Wellington#define MAKE_RED(node) ((node)->color = RED)
b5debbe212097d1c573a2ba3bd9a3d526d86b0aeBrian Wellington#define MAKE_BLACK(node) ((node)->color = BLACK)
b5debbe212097d1c573a2ba3bd9a3d526d86b0aeBrian Wellington * Chain management.
b5debbe212097d1c573a2ba3bd9a3d526d86b0aeBrian Wellington * The "ancestors" member of chains were removed, with their job now
b5debbe212097d1c573a2ba3bd9a3d526d86b0aeBrian Wellington * being wholly handled by parent pointers (which didn't exist, because
e44487bfc23599b6b240e09d83d1c862fecfcc82Michael Graff * of memory concerns, when chains were first implemented).
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington (chain)->levels[(chain)->level_count++] = (node)
7d116211ec7b063891130f191e3ed437b45dba70Mark Andrews * The following macros directly access normally private name variables.
7d116211ec7b063891130f191e3ed437b45dba70Mark Andrews * These macros are used to avoid a lot of function calls in the critical
7d116211ec7b063891130f191e3ed437b45dba70Mark Andrews * path of the tree traversal code.
7d116211ec7b063891130f191e3ed437b45dba70Mark Andrewsstatic inline void
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington#define inline
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington * A little something to help out in GDB.
17a3fcecd069130a5f318685493b0db5639a77c9Brian Wellingtonstatic void printnodename(dns_rbtnode_t *node);
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewshexdump(const char *desc, unsigned char *data, size_t size) {
48ed268b3378a8b729a0037bc4ae2ed73647a96aBrian Wellington * Return the node in the level above the argument node that points
48ed268b3378a8b729a0037bc4ae2ed73647a96aBrian Wellington * to the level the argument node is in. If the argument node is in
48ed268b3378a8b729a0037bc4ae2ed73647a96aBrian Wellington * the top level, the return value is NULL.
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington for (root = node; ! IS_ROOT(root); root = PARENT(root))
48ed268b3378a8b729a0037bc4ae2ed73647a96aBrian Wellington ; /* Nothing. */
7d116211ec7b063891130f191e3ed437b45dba70Mark Andrews * Forward declarations.
9cd6710f91bdffef5aed68ab02533e398f6134d7Brian Wellingtoncreate_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep);
9cd6710f91bdffef5aed68ab02533e398f6134d7Brian Wellingtonstatic inline void
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewshash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name);
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellingtonstatic inline void
e2c3f8059e77a8e11c4378d22e5d8e78b423a28fMark Andrewsunhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
50105afc551903541608b11851d73278b23579a3Mark Andrewsstatic inline void
50105afc551903541608b11851d73278b23579a3Mark Andrewsrotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
50105afc551903541608b11851d73278b23579a3Mark Andrewsstatic inline void
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewsrotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
48ed268b3378a8b729a0037bc4ae2ed73647a96aBrian Wellingtonaddonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewsdeletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp);
48ed268b3378a8b729a0037bc4ae2ed73647a96aBrian Wellingtontreefix(dns_rbt_t *rbt, void *base, size_t size,
34aa7909371f13b4bc0ba6d155cfc38bfa1e3c5cAndreas Gustafsson dns_rbtdatafixer_t datafixer, isc_sha1_t *sha1);
8839b6acbf816fedc15b8e9e1c71fd606a9cd8eaBrian Wellingtondeletetree(dns_rbt_t *rbt, dns_rbtnode_t *node);
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewsdeletetreeflat(dns_rbt_t *rbt, unsigned int quantum, dns_rbtnode_t **nodep);
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewsfreenode(dns_rbt_t *rbt, dns_rbtnode_t **nodep);
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * Write out a zeroed header as a placeholder. Doing this ensures
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * that the file will not read while it is partially written, should
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * writing fail or be interrupted.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews result = isc_stdio_write(buffer, 1, HEADER_LENGTH, file, NULL);
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Write out the real header, including NodeDump version information
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * and the offset of the first node.
7d116211ec7b063891130f191e3ed437b45dba70Mark Andrews * Any information stored in the rbt object itself should be stored
7d116211ec7b063891130f191e3ed437b45dba70Mark Andrewswrite_header(FILE *file, dns_rbt_t *rbt, isc_uint64_t first_node_offset,
7d116211ec7b063891130f191e3ed437b45dba70Mark Andrews unsigned char *digest)
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews memcpy(header.version1, FILE_VERSION, sizeof(header.version1));
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews memcpy(header.version2, FILE_VERSION, sizeof(header.version2));
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews header.ptrsize = (isc_uint32_t) sizeof(void *);
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews memcpy(header.digest, digest, sizeof(header.digest));
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews CHECK(isc_stdio_seek(file, location, SEEK_SET));
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews CHECK(isc_stdio_write(&header, 1, sizeof(file_header_t), file, NULL));
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews /* Ensure we are always at the end of the file. */
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewsserialize_node(FILE *file, dns_rbtnode_t *node, uintptr_t left,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews uintptr_t right, uintptr_t down, uintptr_t parent,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews unsigned char *node_data;
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews file_position = dns_rbt_serialize_align(file_position);
3676eeb6ca95c66aae1256f37af8c990d9f25eb4Brian Wellington CHECK(isc_stdio_seek(file, file_position, SEEK_SET));
6f071989da905bb5ab2c6dfd01a71ee5ecea5918Brian Wellington * If the next node is not NULL, calculate the next node's location
6f071989da905bb5ab2c6dfd01a71ee5ecea5918Brian Wellington * in the file. Note that this will have to change when the data
6f071989da905bb5ab2c6dfd01a71ee5ecea5918Brian Wellington * structure changes, and it also assumes that we always write the
6f071989da905bb5ab2c6dfd01a71ee5ecea5918Brian Wellington * nodes out in list order (which we currently do.)
6f071989da905bb5ab2c6dfd01a71ee5ecea5918Brian Wellington temp_node.parent = (dns_rbtnode_t *)(parent);
34aa7909371f13b4bc0ba6d155cfc38bfa1e3c5cAndreas Gustafsson temp_node.right = (dns_rbtnode_t *)(right);
1b1e1fda4638334b484aa38c15f53a131c0b0fdfAndreas Gustafsson node_data = (unsigned char *) node + sizeof(dns_rbtnode_t);
18b7133679efa8f60fd4e396c628576f3f416b3eBrian Wellington datasize = NODE_SIZE(node) - sizeof(dns_rbtnode_t);
17a3fcecd069130a5f318685493b0db5639a77c9Brian Wellington CHECK(isc_stdio_write(&temp_node, 1, sizeof(dns_rbtnode_t),
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews CHECK(isc_stdio_write(node_data, 1, datasize, file, NULL));
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews hexdump("node header", (unsigned char*) &temp_node,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews isc_sha1_update(sha1, (const isc_uint8_t *) &temp_node,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews isc_sha1_update(sha1, (const isc_uint8_t *) node_data, datasize);
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewsserialize_nodes(FILE *file, dns_rbtnode_t *node, uintptr_t parent,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews dns_rbtdatawriter_t datawriter, isc_uint32_t serial,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews uintptr_t left = 0, right = 0, down = 0, data = 0;
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews /* Reserve space for current node. */
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews CHECK(isc_stdio_seek(file, location, SEEK_SET));
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews offset_adjust = dns_rbt_serialize_align(location + NODE_SIZE(node));
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews CHECK(isc_stdio_seek(file, offset_adjust, SEEK_SET));
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Serialize the rest of the tree.
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington * WARNING: A change in the order (from left, right, down)
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington * will break the way the sha1 hash is computed.
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews CHECK(serialize_nodes(file, getleft(node, NULL), location,
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews CHECK(serialize_nodes(file, getright(node, NULL), location,
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews CHECK(serialize_nodes(file, getdown(node, NULL), location,
e407562a75eb93073bb72089cced150d7ffe4d4fTatuya JINMEI 神明達哉 CHECK(isc_stdio_seek(file, ret, SEEK_SET));
c99d9017ba00099bfa89e1ed53e63a5cb07d28d5Mark Andrews /* Seek back to reserved space. */
93d6dfaf66258337985427c86181f01fc51f0bb4Mark Andrews CHECK(isc_stdio_seek(file, location, SEEK_SET));
34aa7909371f13b4bc0ba6d155cfc38bfa1e3c5cAndreas Gustafsson /* Serialize the current node. */
93d6dfaf66258337985427c86181f01fc51f0bb4Mark Andrews CHECK(serialize_node(file, node, left, right, down, parent, data,
93d6dfaf66258337985427c86181f01fc51f0bb4Mark Andrews /* Ensure we are always at the end of the file. */
1ea2595e1b33cc63ea73ee1d54b580b717d7d155Mark Andrewsdns_rbt_serialize_tree(FILE *file, dns_rbt_t *rbt,
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews long header_position, node_position, end_position;
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington /* Write dummy header */
1ea2595e1b33cc63ea73ee1d54b580b717d7d155Mark Andrews /* Serialize nodes */
1ea2595e1b33cc63ea73ee1d54b580b717d7d155Mark Andrews CHECK(serialize_nodes(file, rbt->root, 0, datawriter, serial, NULL,
676619a22fbc760875adb00b58aaef6a22ced18aMark Andrews CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews hexdump("serializing digest", digest, sizeof(digest));
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews /* Serialize header */
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews CHECK(isc_stdio_seek(file, header_position, SEEK_SET));
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews CHECK(write_header(file, rbt, HEADER_LENGTH, digest));
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews /* Ensure we are always at the end of the file. */
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews *offset = dns_rbt_serialize_align(header_position);
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews#define CONFIRM(a) do { \
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews if (! (a)) { \
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrewstreefix(dns_rbt_t *rbt, void *base, size_t filesize, dns_rbtnode_t *n,
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews dns_name_t *name, dns_rbtdatafixer_t datafixer, isc_sha1_t *sha1)
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews unsigned char *node_data;
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews size_t datasize, nodemax = filesize - sizeof(dns_rbtnode_t);
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews CHECK(dns_name_concatenate(&nodename, name, fullname, NULL));
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews /* memorize header contents prior to fixup */
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews CONFIRM(n->right <= (dns_rbtnode_t *) nodemax);
94766449d6125cd5870891b70d46573e5deaceb4Brian Wellington CONFIRM(n->parent <= (dns_rbtnode_t *) nodemax);
9cd6710f91bdffef5aed68ab02533e398f6134d7Brian Wellington /* a change in the order (from left, right, down) will break hashing*/
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington CHECK(treefix(rbt, base, filesize, n->left, name,
e2c3f8059e77a8e11c4378d22e5d8e78b423a28fMark Andrews CHECK(treefix(rbt, base, filesize, n->right, name,
b0d31c78bc24080d4c470a8bd98862375f6e3055Mark Andrews CHECK(treefix(rbt, base, filesize, n->down, fullname,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews node_data = (unsigned char *) n + sizeof(dns_rbtnode_t);
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews datasize = NODE_SIZE(n) - sizeof(dns_rbtnode_t);
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews hexdump("node header", (unsigned char *) &header,
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews isc_sha1_update(sha1, (const isc_uint8_t *) &header,
2f012d936b5ccdf6520c96a4de23721dc58a2221Automatic Updater isc_sha1_update(sha1, (const isc_uint8_t *) node_data,
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrewsdns_rbt_deserialize_tree(void *base_address, size_t filesize,
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews void (*deleter)(void *, void *),
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington REQUIRE(originp == NULL || *originp == NULL);
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews CHECK(dns_rbt_create(mctx, deleter, deleter_arg, &rbt));
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington header = (file_header_t *)((char *)base_address + header_offset);
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews if (header->ptrsize != (isc_uint32_t) sizeof(void *)) {
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews if (header->bigendian != (1 == htonl(1)) ? 1 : 0) {
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews /* Copy other data items from the header into our rbt. */
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews rbt->root = (dns_rbtnode_t *)((char *)base_address +
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews CHECK(treefix(rbt, base_address, filesize, rbt->root,
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews hexdump("deserializing digest", digest, sizeof(digest));
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews /* Check file hash */
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews if (memcmp(header->digest, digest, sizeof(digest)) != 0) {
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews * Initialize a red/black tree of trees.
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrewsdns_rbt_create(isc_mem_t *mctx, void (*deleter)(void *, void *),
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews REQUIRE(deleter == NULL ? deleter_arg == NULL : 1);
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews rbt = (dns_rbt_t *)isc_mem_get(mctx, sizeof(*rbt));
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews * Deallocate a red/black tree of trees.
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews RUNTIME_CHECK(dns_rbt_destroy2(rbtp, 0) == ISC_R_SUCCESS);
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrewsdns_rbt_destroy2(dns_rbt_t **rbtp, unsigned int quantum) {
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews isc_mem_putanddetach(&rbt->mctx, rbt, sizeof(*rbt));
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewschain_name(dns_rbtnodechain_t *chain, dns_name_t *name,
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington for (i = (int)chain->level_count - 1; i >= 0; i--) {
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington result = dns_name_concatenate(name, &nodename, name, NULL);
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewsmove_chain_to_last(dns_rbtnodechain_t *chain, dns_rbtnode_t *node) {
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Go as far right and then down as much as possible,
613efcd8fbd0d1ce0d0afd1ac85d95cf85bffc27Brian Wellington * as long as the rightmost node has a down pointer.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Add 'name' to tree, initializing its data pointer with 'data'.
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrewsdns_rbt_addnode(dns_rbt_t *rbt, dns_name_t *name, dns_rbtnode_t **nodep) {
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Does this thing have too many variables or what?
48ed268b3378a8b729a0037bc4ae2ed73647a96aBrian Wellington dns_rbtnode_t **root, *parent, *child, *current, *new_current;
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews dns_name_t *add_name, *new_name, current_name, *prefix, *suffix;
93c786e0924aeca2c258e32355349e6ae60a0f72Andreas Gustafsson dns_fixedname_t fixedcopy, fixedprefix, fixedsuffix, fnewname;
d6643ef587324e40d8bda63e9f80be8141e101edBrian Wellington * Create a copy of the name so the original name structure is
d6643ef587324e40d8bda63e9f80be8141e101edBrian Wellington * not modified.
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley result = create_node(rbt->mctx, add_name, &new_current);
d6643ef587324e40d8bda63e9f80be8141e101edBrian Wellington dns_name_init(¤t_name, current_offsets);
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley compared = dns_name_fullcompare(add_name, ¤t_name,
93d6dfaf66258337985427c86181f01fc51f0bb4Mark Andrews } else if (order > 0) {
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington * This name has some suffix in common with the
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington * name at the current node. If the name at
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington * the current node is shorter, that means the
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * new name should be in a subtree. If the
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington * name at the current node is longer, that means
e407562a75eb93073bb72089cced150d7ffe4d4fTatuya JINMEI 神明達哉 * the down pointer to this tree should point
a9ba7e65644c50e1549b38150ba8d4787e1fe643Brian Wellington * to a new tree that has the common suffix, and
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington * the non-common parts of these two names should
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * start a new tree.
78951552dccf0d0004d61072bbc71fa4b1aab30fAndreas Gustafsson if (compared == dns_namereln_subdomain) {
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * All of the existing labels are in common,
78951552dccf0d0004d61072bbc71fa4b1aab30fAndreas Gustafsson * so the new name is in a subtree.
93d6dfaf66258337985427c86181f01fc51f0bb4Mark Andrews * Whack off the common labels for the
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * not-in-common part to be searched for
78951552dccf0d0004d61072bbc71fa4b1aab30fAndreas Gustafsson * in the next level.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Follow the down pointer (possibly NULL).
d6643ef587324e40d8bda63e9f80be8141e101edBrian Wellington * The number of labels in common is fewer
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * than the number of labels at the current
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * node, so the current node must be adjusted
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * to have just the common suffix, and a down
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * pointer made to a new tree.
3676eeb6ca95c66aae1256f37af8c990d9f25eb4Brian Wellington * Ensure the number of levels in the tree
3676eeb6ca95c66aae1256f37af8c990d9f25eb4Brian Wellington * does not exceed the number of logical
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington * levels allowed by DNSSEC.
d6643ef587324e40d8bda63e9f80be8141e101edBrian Wellington * XXXDCL need a better error result?
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * XXXDCL Since chain ancestors were removed,
d6643ef587324e40d8bda63e9f80be8141e101edBrian Wellington * no longer used by addonlevel(),
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington * this is the only real use of chains in the
d6643ef587324e40d8bda63e9f80be8141e101edBrian Wellington * function. It could be done instead with
d6643ef587324e40d8bda63e9f80be8141e101edBrian Wellington * a simple integer variable, but I am pressed
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington * Split the name into two parts, a prefix
77c67dfb2607618f5e7940486daebafd42a502abBrian Wellington * which is the not-in-common parts of the
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * two names and a suffix that is the common
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * parts of them.
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * Reproduce the tree attributes of the
93d6dfaf66258337985427c86181f01fc51f0bb4Mark Andrews * current node.
b5debbe212097d1c573a2ba3bd9a3d526d86b0aeBrian Wellington if (current->nsec == DNS_RBT_NSEC_HAS_NSEC)
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * Fix pointers that were to the current node.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Set up the new root of the next level.
25496cebadd170fd5fae2aabf0469eef551259aaBrian Wellington * By definition it will not be the top
25496cebadd170fd5fae2aabf0469eef551259aaBrian Wellington * level tree, so clear DNS_NAMEATTR_ABSOLUTE.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * The name has been added by pushing
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * the not-in-common parts down to
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * a new level.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * The current node has no data,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * because it is just a placeholder.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Its data pointer is already NULL
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * from create_node()), so there's
25496cebadd170fd5fae2aabf0469eef551259aaBrian Wellington * nothing more to do to it.
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * The not-in-common parts of the new
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * name will be inserted into the new
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * level following this loop (unless
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * result != ISC_R_SUCCESS, which
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * is tested after the loop ends).
fabf2ee6b01ee06a0de940b83d53cf57f9f79265Mark Andrews result = create_node(rbt->mctx, add_name, &new_current);
fabf2ee6b01ee06a0de940b83d53cf57f9f79265Mark Andrews * Add a name to the tree of trees, associating it with some data.
fabf2ee6b01ee06a0de940b83d53cf57f9f79265Mark Andrewsdns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data) {
25496cebadd170fd5fae2aabf0469eef551259aaBrian Wellington result = dns_rbt_addnode(rbt, name, &node);
3ce4b8b03ebd017c1d1b320429219ba91e705ea4Andreas Gustafsson * dns_rbt_addnode will report the node exists even when
3ce4b8b03ebd017c1d1b320429219ba91e705ea4Andreas Gustafsson * it does not have data associated with it, but the
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * dns_rbt_*name functions all behave depending on whether
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * there is data associated with a node.
3ce4b8b03ebd017c1d1b320429219ba91e705ea4Andreas Gustafsson (result == ISC_R_EXISTS && DATA(node) == NULL)) {
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * Find the node for "name" in the tree of trees.
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halleydns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname,
93c786e0924aeca2c258e32355349e6ae60a0f72Andreas Gustafsson dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence unsigned int options, dns_rbtfindcallback_t callback,
93c786e0924aeca2c258e32355349e6ae60a0f72Andreas Gustafsson dns_rbtnode_t *current, *last_compared, *current_root;
93c786e0924aeca2c258e32355349e6ae60a0f72Andreas Gustafsson dns_name_t *search_name, current_name, *callback_name;
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley dns_fixedname_t fixedcallbackname, fixedsearchname;
93c786e0924aeca2c258e32355349e6ae60a0f72Andreas Gustafsson unsigned int hlabels = 0;
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington REQUIRE((options & (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR))
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington != (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR));
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington * If there is a chain it needs to appear to be in a sane state,
1f1d36a87b65186d9f89aac7f456ab1fd2a39ef6Andreas Gustafsson * otherwise a chain is still needed to generate foundname and
1f1d36a87b65186d9f89aac7f456ab1fd2a39ef6Andreas Gustafsson * callback_name.
b5debbe212097d1c573a2ba3bd9a3d526d86b0aeBrian Wellington * Appease GCC about variables it incorrectly thinks are
93c786e0924aeca2c258e32355349e6ae60a0f72Andreas Gustafsson * possibly used uninitialized.
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington callback_name = dns_fixedname_name(&fixedcallbackname);
8d414d155953f89a4eff40f16878438a8c9228f3Mark Andrews * search_name is the name segment being sought in each tree level.
8d414d155953f89a4eff40f16878438a8c9228f3Mark Andrews * By using a fixedname, the search_name will definitely have offsets
8d414d155953f89a4eff40f16878438a8c9228f3Mark Andrews * for use by any splitting.
8d414d155953f89a4eff40f16878438a8c9228f3Mark Andrews * By using dns_name_clone, no name data should be copied thanks to
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * the lack of bitstring labels.
d6643ef587324e40d8bda63e9f80be8141e101edBrian Wellington search_name = dns_fixedname_name(&fixedsearchname);
e49c834de8cdf92d4b85ef0fbf1d9dc59620a342Brian Wellington compared = dns_name_fullcompare(search_name, ¤t_name,
ba393f380e4cd93029f6a7291d6c2d14f9022b3cBrian Wellington unsigned int hash;
d6643ef587324e40d8bda63e9f80be8141e101edBrian Wellington * If there is no hash table, hashing can't be done.
75f6c57d9544aa77a3b1a04587b4702c07343c90Brian Wellington * The case of current != current_root, that
75f6c57d9544aa77a3b1a04587b4702c07343c90Brian Wellington * means a left or right pointer was followed,
75f6c57d9544aa77a3b1a04587b4702c07343c90Brian Wellington * only happens when the algorithm fell through to
75f6c57d9544aa77a3b1a04587b4702c07343c90Brian Wellington * the traditional binary search because of a
75f6c57d9544aa77a3b1a04587b4702c07343c90Brian Wellington * bitstring label. Since we dropped the bitstring
75f6c57d9544aa77a3b1a04587b4702c07343c90Brian Wellington * support, this should not happen.
e83cae7fa837e4757c687035d6f6c0900f152749Brian Wellington nlabels = dns_name_countlabels(search_name);
feb40fc5f911d0b2050fb9fd34950a52930b981dBrian Wellington * current_root is the root of the current level, so
feb40fc5f911d0b2050fb9fd34950a52930b981dBrian Wellington * it's parent is the same as it's "up" pointer.
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews * Hash includes tail.
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews hash = dns_name_fullhash(&hash_name, ISC_FALSE);
538fea1c91c68c0a5569c7b8552c8fd0490055efBrian Wellington for (hnode = rbt->hashtable[hash % rbt->hashsize];
34aa7909371f13b4bc0ba6d155cfc38bfa1e3c5cAndreas Gustafsson if (dns_name_equal(&hnode_name, &hash_name))
e1f16346db02486f751c6db683fffe53c866c186Andreas Gustafsson * This is an optimization. If hashing found
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * the right node, the next call to
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * dns_name_fullcompare() would obviously
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * return _equal or _subdomain. Determine
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * which of those would be the case by
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * checking if the full name was hashed. Then
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * make it look like dns_name_fullcompare
50105afc551903541608b11851d73278b23579a3Mark Andrews * was called and jump to the right place.
50105afc551903541608b11851d73278b23579a3Mark Andrews * All of the labels have been tried against the hash
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * table. Since we dropped the support of bitstring
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * labels, the name isn't in the table.
50105afc551903541608b11851d73278b23579a3Mark Andrews#endif /* DNS_RBT_USEHASH */
c5387e694299c41361660e54f23e89c7da3ede1dMark Andrews * Standard binary search tree movement.
fcbc5d2353971f65726a9e86c1f37c813f9c2176Mark Andrews * The names have some common suffix labels.
c5387e694299c41361660e54f23e89c7da3ede1dMark Andrews * If the number in common are equal in length to
f1263d2aa405087e74caf001cd443079f50ee903Mark Andrews * the current node's name length, then follow the
f1263d2aa405087e74caf001cd443079f50ee903Mark Andrews * down pointer and search in the new tree.
394f4aec2189750d7f861d00f97fe28ffcd9f659Mark Andrews * Whack off the current node's common parts
394f4aec2189750d7f861d00f97fe28ffcd9f659Mark Andrews * for the name to search in the next level.
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * This might be the closest enclosing name.
f1263d2aa405087e74caf001cd443079f50ee903Mark Andrews * Point the chain to the next level. This
50105afc551903541608b11851d73278b23579a3Mark Andrews * needs to be done before 'current' is pointed
c941e32d221fbb0cb760e3bc24c7f221c0cf8b97Mark Andrews * there because the callback in the next
c941e32d221fbb0cb760e3bc24c7f221c0cf8b97Mark Andrews * block of code needs the current 'current',
c941e32d221fbb0cb760e3bc24c7f221c0cf8b97Mark Andrews * but in the event the callback requests that
2f012d936b5ccdf6520c96a4de23721dc58a2221Automatic Updater * the search be stopped then the
c5387e694299c41361660e54f23e89c7da3ede1dMark Andrews * DNS_R_PARTIALMATCH code at the end of this
c5387e694299c41361660e54f23e89c7da3ede1dMark Andrews * function needs the chain pointed to the
c5387e694299c41361660e54f23e89c7da3ede1dMark Andrews * next level.
50105afc551903541608b11851d73278b23579a3Mark Andrews * The caller may want to interrupt the
50105afc551903541608b11851d73278b23579a3Mark Andrews * downward search when certain special nodes
50105afc551903541608b11851d73278b23579a3Mark Andrews * are traversed. If this is a special node,
50105afc551903541608b11851d73278b23579a3Mark Andrews * the callback is used to learn what the
50105afc551903541608b11851d73278b23579a3Mark Andrews * caller wants to do.
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * Treat this node as if it
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * had no down pointer.
50105afc551903541608b11851d73278b23579a3Mark Andrews * Finally, head to the next tree level.
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * Though there are labels in common, the
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * entire name at this node is not common
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * with the search name so the search
50105afc551903541608b11851d73278b23579a3Mark Andrews * name does not exist in the tree.
50105afc551903541608b11851d73278b23579a3Mark Andrews * If current is not NULL, NOEXACT is not disallowing exact matches,
50105afc551903541608b11851d73278b23579a3Mark Andrews * and either the node has data or an empty node is ok, return
50105afc551903541608b11851d73278b23579a3Mark Andrews * ISC_R_SUCCESS to indicate an exact match.
50105afc551903541608b11851d73278b23579a3Mark Andrews if (current != NULL && (options & DNS_RBTFIND_NOEXACT) == 0 &&
50105afc551903541608b11851d73278b23579a3Mark Andrews * Found an exact match.
50105afc551903541608b11851d73278b23579a3Mark Andrews result = chain_name(chain, foundname, ISC_TRUE);
50105afc551903541608b11851d73278b23579a3Mark Andrews * Did not find an exact match (or did not want one).
8d414d155953f89a4eff40f16878438a8c9228f3Mark Andrews * ... but found a partially matching superdomain.
8d414d155953f89a4eff40f16878438a8c9228f3Mark Andrews * Unwind the chain to the partial match node
8d414d155953f89a4eff40f16878438a8c9228f3Mark Andrews * to set level_matches to the level above the node,
8d414d155953f89a4eff40f16878438a8c9228f3Mark Andrews * and then to derive the name.
50105afc551903541608b11851d73278b23579a3Mark Andrews * chain->level_count is guaranteed to be at least 1
c941e32d221fbb0cb760e3bc24c7f221c0cf8b97Mark Andrews * here because by definition of finding a superdomain,
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * the chain is pointed to at least the first subtree.
50105afc551903541608b11851d73278b23579a3Mark Andrews while (chain->levels[chain->level_matches] != *node) {
93d6dfaf66258337985427c86181f01fc51f0bb4Mark Andrews * There was an exact match but either
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * DNS_RBTFIND_NOEXACT was set, or
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews * DNS_RBTFIND_EMPTYDATA was set and the node had no
cf224bbf7bab87bc28b12f5b30f5ca3f3e5bf604Mark Andrews * data. A policy decision was made to set the
c5387e694299c41361660e54f23e89c7da3ede1dMark Andrews * chain to the exact match, but this is subject
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * to change if it becomes apparent that something
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * else would be more useful. It is important that
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * this case is handled here, because the predecessor
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * setting code below assumes the match was not exact.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews INSIST(((options & DNS_RBTFIND_NOEXACT) != 0) ||
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews } else if ((options & DNS_RBTFIND_NOPREDECESSOR) != 0) {
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Ensure the chain points nowhere.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Since there was no exact match, the chain argument
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * needs to be pointed at the DNSSEC predecessor of
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * the search name.
f1263d2aa405087e74caf001cd443079f50ee903Mark Andrews * Attempted to follow a down pointer that was
f1263d2aa405087e74caf001cd443079f50ee903Mark Andrews * NULL, which means the searched for name was
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * a subdomain of a terminal name in the tree.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Since there are no existing subdomains to
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * order against, the terminal name is the
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * predecessor.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Point current to the node that stopped
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * the search.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * With the hashing modification that has been
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * added to the algorithm, the stop node of a
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * standard binary search is not known. So it
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * has to be found. There is probably a more
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * clever way of doing this.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * The assignment of current to NULL when
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * the relationship is *not* dns_namereln_none,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * even though it later gets set to the same
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * last_compared anyway, is simply to not push
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * the while loop in one more level of
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * indentation.
cf224bbf7bab87bc28b12f5b30f5ca3f3e5bf604Mark Andrews * Standard binary search movement.
cf224bbf7bab87bc28b12f5b30f5ca3f3e5bf604Mark Andrews * Reached a point within a level tree that
cf224bbf7bab87bc28b12f5b30f5ca3f3e5bf604Mark Andrews * positively indicates the name is not
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * present, but the stop node could be either
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * less than the desired name (order > 0) or
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * greater than the desired name (order < 0).
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * If the stop node is less, it is not
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * necessarily the predecessor. If the stop
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * node has a down pointer, then the real
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * predecessor is at the end of a level below
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * (not necessarily the next level).
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Move down levels until the rightmost node
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * does not have a down pointer.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * When the stop node is greater, it is
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * the successor. All the logic for finding
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * the predecessor is handily encapsulated
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * in dns_rbtnodechain_prev. In the event
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * that the search name is less than anything
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * else in the tree, the chain is reset.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * XXX DCL What is the best way for the caller
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * to know that the search name has
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * no predecessor?
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Ah, the pure and simple
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * case. The stop node is the
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * predecessor.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews ; /* Nothing. */
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * There is no predecessor.
8d414d155953f89a4eff40f16878438a8c9228f3Mark Andrews ENSURE(*node == NULL || DNS_RBTNODE_VALID(*node));
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Get the data pointer associated with 'name'.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewsdns_rbt_findname(dns_rbt_t *rbt, dns_name_t *name, unsigned int options,
c5387e694299c41361660e54f23e89c7da3ede1dMark Andrews result = dns_rbt_findnode(rbt, name, foundname, &node, NULL,
c5387e694299c41361660e54f23e89c7da3ede1dMark Andrews (DATA(node) != NULL || (options & DNS_RBTFIND_EMPTYDATA) != 0))
f1263d2aa405087e74caf001cd443079f50ee903Mark Andrews * Delete a name from the tree of trees.
c5387e694299c41361660e54f23e89c7da3ede1dMark Andrewsdns_rbt_deletename(dns_rbt_t *rbt, dns_name_t *name, isc_boolean_t recurse) {
c5387e694299c41361660e54f23e89c7da3ede1dMark Andrews * First, find the node.
c5387e694299c41361660e54f23e89c7da3ede1dMark Andrews * When searching, the name might not have an exact match:
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * consider a.b.a.com, b.b.a.com and c.b.a.com as the only
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * elements of a tree, which would make layer 1 a single
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * node tree of "b.a.com" and layer 2 a three node tree of
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * a, b, and c. Deleting a.com would find only a partial depth
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * match in the first layer. Should it be a requirement that
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * that the name to be deleted have data? For now, it is.
f1263d2aa405087e74caf001cd443079f50ee903Mark Andrews * ->dirty, ->locknum and ->references are ignored; they are
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * solely the province of rbtdb.c.
c941e32d221fbb0cb760e3bc24c7f221c0cf8b97Mark Andrews result = dns_rbt_findnode(rbt, name, NULL, &node, NULL,
c5387e694299c41361660e54f23e89c7da3ede1dMark Andrews result = dns_rbt_deletenode(rbt, node, recurse);
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * Remove a node from the tree of trees.
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * NOTE WELL: deletion is *not* symmetric with addition; that is, reversing
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * a sequence of additions to be deletions will not generally get the
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * tree back to the state it started in. For example, if the addition
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * of "b.c" caused the node "a.b.c" to be split, pushing "a" to its own level,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * then the subsequent deletion of "b.c" will not cause "a" to be pulled up,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * restoring "a.b.c". The RBT *used* to do this kind of rejoining, but it
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * turned out to be a bad idea because it could corrupt an active nodechain
f1263d2aa405087e74caf001cd443079f50ee903Mark Andrews * that had "b.c" as one of its levels -- and the RBT has no idea what
f1263d2aa405087e74caf001cd443079f50ee903Mark Andrews * nodechains are in use by callers, so it can't even *try* to helpfully
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * fix them up (which would probably be doomed to failure anyway).
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Similarly, it is possible to leave the tree in a state where a supposedly
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * deleted node still exists. The first case of this is obvious; take
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * the tree which has "b.c" on one level, pointing to "a". Now deleted "b.c".
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * It was just established in the previous paragraph why we can't pull "a"
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * back up to its parent level. But what happens when "a" then gets deleted?
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * "b.c" is left hanging around without data or children. This condition
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * is actually pretty easy to detect, but ... should it really be removed?
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Is a chain pointing to it? An iterator? Who knows! (Note that the
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * references structure member cannot be looked at because it is private to
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * rbtdb.) This is ugly and makes me unhappy, but after hours of trying to
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * make it more aesthetically proper and getting nowhere, this is the way it
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * is going to stay until such time as it proves to be a *real* problem.
cc3aafe737334d444781f8a34ffaf459e075bb9aMark Andrews * Finally, for reference, note that the original routine that did node
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * joining was called join_nodes(). It has been excised, living now only
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * in the CVS history, but comments have been left behind that point to it just
2f012d936b5ccdf6520c96a4de23721dc58a2221Automatic Updater * in case someone wants to muck with this some more.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * The one positive aspect of all of this is that joining used to have a
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * case where it might fail. Without trying to join, now this function always
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * succeeds. It still returns isc_result_t, though, so the API wouldn't change.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewsdns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, isc_boolean_t recurse)
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews if (DATA(node) != NULL && rbt->data_deleter != NULL)
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews rbt->data_deleter(DATA(node), rbt->deleter_arg);
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews * Since there is at least one node below this one and
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews * no recursion was requested, the deletion is
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews * complete. The down node from this node might be all
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews * by itself on a single level, so join_nodes() could
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * be used to collapse the tree (with all the caveats
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * of the comment at the start of this function).
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Note the node that points to the level of the node that is being
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * deleted. If the deleted node is the top level, parent will be set
8d414d155953f89a4eff40f16878438a8c9228f3Mark Andrews * This node now has no down pointer (either because it didn't
8d414d155953f89a4eff40f16878438a8c9228f3Mark Andrews * have one to start, or because it was recursively removed).
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews * So now the node needs to be removed from this level.
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews deletefromlevel(node, parent == NULL ? &rbt->root : &DOWN(parent));
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews if (DATA(node) != NULL && rbt->data_deleter != NULL)
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews rbt->data_deleter(DATA(node), rbt->deleter_arg);
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * There are now two special cases that can exist that would
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * not have existed if the tree had been created using only
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * the names that now exist in it. (This is all related to
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * join_nodes() as described in this function's introductory comment.)
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * Both cases exist when the deleted node's parent (the node
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * that pointed to the deleted node's level) is not null but
93d6dfaf66258337985427c86181f01fc51f0bb4Mark Andrews * it has no data: parent != NULL && DATA(parent) == NULL.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * The first case is that the deleted node was the last on its level:
50105afc551903541608b11851d73278b23579a3Mark Andrews * DOWN(parent) == NULL. This case can only exist if the parent was
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * previously deleted -- and so now, apparently, the parent should go
e83cae7fa837e4757c687035d6f6c0900f152749Brian Wellington * away. That can't be done though because there might be external
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * references to it, such as through a nodechain.
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * The other case also involves a parent with no data, but with the
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * deleted node being the next-to-last node instead of the last:
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * LEFT(DOWN(parent)) == NULL && RIGHT(DOWN(parent)) == NULL.
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * Presumably now the remaining node on the level should be joined
2f012d936b5ccdf6520c96a4de23721dc58a2221Automatic Updater * with the parent, but it's already been described why that can't be
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews * This function never fails.
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrewsdns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name) {
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrewsdns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name) {
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews result = dns_name_concatenate(name, ¤t, name, NULL);
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrewsdns_rbt_formatnodename(dns_rbtnode_t *node, char *printname, unsigned int size)
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews snprintf(printname, size, "<error building name: %s>",
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrewscreate_node(isc_mem_t *mctx, dns_name_t *name, dns_rbtnode_t **nodep) {
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews unsigned int labels;
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * Allocate space for the node structure, the name, and the offsets.
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews nodelen = sizeof(dns_rbtnode_t) + region.length + labels + 1;
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington node = (dns_rbtnode_t *)isc_mem_get(mctx, nodelen);
94766449d6125cd5870891b70d46573e5deaceb4Brian Wellington * The following is stored to make reconstructing a name from the
94766449d6125cd5870891b70d46573e5deaceb4Brian Wellington * stored value in the node easy: the length of the name, the number
94766449d6125cd5870891b70d46573e5deaceb4Brian Wellington * of labels, whether the name is absolute or not, the name itself,
94766449d6125cd5870891b70d46573e5deaceb4Brian Wellington * and the name's offsets table.
94766449d6125cd5870891b70d46573e5deaceb4Brian Wellington * The offsets table could be made smaller by eliminating the
94766449d6125cd5870891b70d46573e5deaceb4Brian Wellington * first offset, which is always 0. This requires changes to
d6be55c63f83194d97a565d0fd7b632b31b52a68Brian Wellington * Note: OLDOFFSETLEN *must* be assigned *after* OLDNAMELEN is assigned
d6be55c63f83194d97a565d0fd7b632b31b52a68Brian Wellington * as it uses OLDNAMELEN.
d6be55c63f83194d97a565d0fd7b632b31b52a68Brian Wellington OLDNAMELEN(node) = NAMELEN(node) = region.length;
d6be55c63f83194d97a565d0fd7b632b31b52a68Brian Wellington memcpy(NAME(node), region.base, region.length);
d6be55c63f83194d97a565d0fd7b632b31b52a68Brian Wellington memcpy(OFFSETS(node), name->offsets, labels);
c70908209ee26c51a8e7242a56fdb73847249728Brian Wellingtonstatic inline void
93d6dfaf66258337985427c86181f01fc51f0bb4Mark Andrewshash_add_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) {
93d6dfaf66258337985427c86181f01fc51f0bb4Mark Andrews unsigned int hash;
94766449d6125cd5870891b70d46573e5deaceb4Brian Wellington HASHVAL(node) = dns_name_fullhash(name, ISC_FALSE);
94766449d6125cd5870891b70d46573e5deaceb4Brian Wellington bytes = rbt->hashsize * sizeof(dns_rbtnode_t *);
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews rbt->hashtable = isc_mem_get(rbt->mctx, bytes);
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews unsigned int oldsize;
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews unsigned int hash;
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews unsigned int i;
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews for (i = 0; i < oldsize; i++) {
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews isc_mem_put(rbt->mctx, oldtable, oldsize * sizeof(dns_rbtnode_t *));
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrewsstatic inline void
664e11f0b14c78cef7cf6b8c70323a1da494e351Mark Andrewshash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, dns_name_t *name) {
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrewsstatic inline void
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrewsunhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node) {
35541328a8c18ba1f984300dfe30ec8713c90031Mark Andrews unsigned int bucket;
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews#endif /* DNS_RBT_USEHASH */
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrewsstatic inline void
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrewsrotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrewsstatic inline void
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrewsrotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews * This is the real workhorse of the insertion code, because it does the
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * true red/black tree on a single level.
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrewsaddonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews dns_rbtnode_t *child, *root, *parent, *grandparent;
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews REQUIRE(DNS_RBTNODE_VALID(node) && LEFT(node) == NULL &&
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * First node of a level.
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * XXXDCL could do away with separate parent and grandparent
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * variables. They are vestiges of the days before parent
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * pointers. However, they make the code a little clearer.
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews * This is the real workhorse of the deletion code, because it does the
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews * true red/black tree on a single level.
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrewsdeletefromlevel(dns_rbtnode_t *delete, dns_rbtnode_t **rootp) {
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * Verify that the parent history is (apparently) correct.
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews INSIST((IS_ROOT(delete) && *rootp == delete) ||
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * This is the only item in the tree.
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * This node has one child, on the right.
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * This node has one child, on the left.
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews * This node has two children, so it cannot be directly
6fac7ff1f9ec9c3873d3b55c5079fa79aba1f146Mark Andrews * deleted. Find its immediate in-order successor and
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * move it to this location, then do the deletion at the
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * old site of the successor.
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * The successor cannot possibly have a left child;
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * if there is any child, it is on the right.
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * Swap the two nodes; it would be simpler to just replace
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * the value being deleted with that of the successor,
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * but this rigamarole is done so the caller has complete
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * control over the pointers (and memory allocation) of
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington * all of nodes. If just the key value were removed from
e4d304b70b81ca9956c2eff7c24aacf4dd00266eEvan Hunt * the tree, the pointer to the node would be unchanged.
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * First, put the successor in the tree location of the
613efcd8fbd0d1ce0d0afd1ac85d95cf85bffc27Brian Wellington * node to be deleted. Save its existing tree pointer
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * information, which will be needed when linking up
613efcd8fbd0d1ce0d0afd1ac85d95cf85bffc27Brian Wellington * delete to the successor's old location.
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * Now relink the node to be deleted into the
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * successor's previous tree location. PARENT(tmp)
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * is the successor's original parent.
613efcd8fbd0d1ce0d0afd1ac85d95cf85bffc27Brian Wellington * Node being deleted was successor's parent.
664e11f0b14c78cef7cf6b8c70323a1da494e351Mark Andrews * Original location of successor node has no left.
664e11f0b14c78cef7cf6b8c70323a1da494e351Mark Andrews * Remove the node by removing the links from its parent.
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * This is the root being deleted, and at this point
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * it is known to have just one child.
94766449d6125cd5870891b70d46573e5deaceb4Brian Wellington * Fix color violations.
6036112f4874637240d461c3ccbcb8dbfb1f405bAndreas Gustafsson while (child != *rootp && IS_BLACK(child)) {
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington * Child is parent's right child.
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews * Everything is done the same as above,
8d414d155953f89a4eff40f16878438a8c9228f3Mark Andrews * except mirrored.
613efcd8fbd0d1ce0d0afd1ac85d95cf85bffc27Brian Wellington * This should only be used on the root of a tree, because no color fixup
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * is done at all.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * NOTE: No root pointer maintenance is done, because the function is only
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * used for two cases:
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * + deleting everything DOWN from a node that is itself being deleted, and
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington * + deleting the entire tree of trees from dns_rbt_destroy.
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington * In each case, the root pointer is no longer relevant, so there
613efcd8fbd0d1ce0d0afd1ac85d95cf85bffc27Brian Wellington * is no need for a root parameter to this function.
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrews * If the function is ever intended to be used to delete something where
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * a pointer needs to be told that this tree no longer exists,
ff30cdeb783ca7ffe69b222c56197828e882c229Mark Andrews * this function would need to adjusted accordingly.
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewsdeletetree(dns_rbt_t *rbt, dns_rbtnode_t *node) {
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews if (DATA(node) != NULL && rbt->data_deleter != NULL)
ca9af3aaf798f98624fc1dc69d8c7d51bf01334dBrian Wellington rbt->data_deleter(DATA(node), rbt->deleter_arg);
60ab03125c137c48a6b2ed6df1d2c8657757e09dMark Andrewsfreenode(dns_rbt_t *rbt, dns_rbtnode_t **nodep) {
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrewsdeletetreeflat(dns_rbt_t *rbt, unsigned int quantum, dns_rbtnode_t **nodep) {
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley if (DATA(node) != NULL && rbt->data_deleter != NULL)
b5debbe212097d1c573a2ba3bd9a3d526d86b0aeBrian Wellington rbt->data_deleter(DATA(node), rbt->deleter_arg);
b5debbe212097d1c573a2ba3bd9a3d526d86b0aeBrian Wellington * Note: we don't call unhash_node() here as we are destroying
b5debbe212097d1c573a2ba3bd9a3d526d86b0aeBrian Wellington * the complete rbt tree.
6bc1a645619a14707da68b130dafe41721fd2f25Brian Wellington for (i = 0; i < depth; i++)
34aa7909371f13b4bc0ba6d155cfc38bfa1e3c5cAndreas Gustafsson printf("Relative pointers: %s%s%s%s%s\n",
664e11f0b14c78cef7cf6b8c70323a1da494e351Mark Andrews printf("node lock address = %d\n", n->locknum);
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halleydns_rbt_printtree(dns_rbtnode_t *root, dns_rbtnode_t *parent,
bf43fdafa3bff9e84cb03f1a19aca74514d2516eBob Halley printf(" (%s, %s", direction, IS_RED(root) ? "RED" : "BLACK");
bf43fdafa3bff9e84cb03f1a19aca74514d2516eBob Halley if ((! IS_ROOT(root) && PARENT(root) != parent) ||
e419f613d8591885df608cb73065921be07dd12eBob Halley if (root->data != NULL && data_printer != NULL) {
b5debbe212097d1c573a2ba3bd9a3d526d86b0aeBrian Wellington printf("** Red/Red color violation on left\n");
f3ca27e9fe307b55e35ea8d7b37351650630e5a3Andreas Gustafsson dns_rbt_printtree(LEFT(root), root, depth, "left",
e419f613d8591885df608cb73065921be07dd12eBob Halley dns_rbt_printtree(RIGHT(root), root, depth, "right",
e419f613d8591885df608cb73065921be07dd12eBob Halley dns_rbt_printtree(DOWN(root), NULL, depth, "down",
e419f613d8591885df608cb73065921be07dd12eBob Halleydns_rbt_printall(dns_rbt_t *rbt, void (*data_printer)(FILE *, void *)) {
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley dns_rbt_printtree(rbt->root, NULL, 0, "root", data_printer);
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington * Chain Functions
3676eeb6ca95c66aae1256f37af8c990d9f25eb4Brian Wellingtondns_rbtnodechain_init(dns_rbtnodechain_t *chain, isc_mem_t *mctx) {
feb40fc5f911d0b2050fb9fd34950a52930b981dBrian Wellington * Initialize 'chain'.
8d414d155953f89a4eff40f16878438a8c9228f3Mark Andrews memset(chain->levels, 0, sizeof(chain->levels));
e419f613d8591885df608cb73065921be07dd12eBob Halleydns_rbtnodechain_current(dns_rbtnodechain_t *chain, dns_name_t *name,
bf43fdafa3bff9e84cb03f1a19aca74514d2516eBob Halley * Names in the top level tree are all absolute.
305227476756aecb11cebbc811dba88a2d147b34Mark Andrews * Always make 'name' relative.
305227476756aecb11cebbc811dba88a2d147b34Mark Andrews * This is cheaper than dns_name_getlabelsequence().
e419f613d8591885df608cb73065921be07dd12eBob Halley result = dns_name_copy(dns_rootname, origin, NULL);
264fd373f3f6cc7f271bdff14a020385620015f1Andreas Gustafssondns_rbtnodechain_prev(dns_rbtnodechain_t *chain, dns_name_t *name,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews dns_rbtnode_t *current, *previous, *predecessor;
305227476756aecb11cebbc811dba88a2d147b34Mark Andrews REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
e419f613d8591885df608cb73065921be07dd12eBob Halley * Moving left one then right as far as possible is the
e419f613d8591885df608cb73065921be07dd12eBob Halley * previous node, at least for this level.
c50936eb40263b65ebf6afe4e6556e2dc67c10e4Brian Wellington * No left links, so move toward the root. If at any point on
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington * the way there the link from parent to child is a right
23e4260821eefa5019808e18e14e2b366461aad7Brian Wellington * link, then the parent is the previous node, at least
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * for this level.
bf43fdafa3bff9e84cb03f1a19aca74514d2516eBob Halley * Found a predecessor node in this level. It might not
bf43fdafa3bff9e84cb03f1a19aca74514d2516eBob Halley * really be the predecessor, however.
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * The predecessor is really down at least one level.
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * Go down and as far right as possible, and repeat
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * as long as the rightmost node has a down pointer.
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * XXX DCL Need to do something about origins
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * here. See whether to go down, and if so
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews * whether it is truly what Bob calls a
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley /* XXX DCL duplicated from above; clever
0ec4b862c9abd11c82c88ed62438f0cf06fed25dBob Halley * way to unduplicate? */
1b1e1fda4638334b484aa38c15f53a131c0b0fdfAndreas Gustafsson /* XXX DCL probably needs work on the concept */
1b1e1fda4638334b484aa38c15f53a131c0b0fdfAndreas Gustafsson * Dang, didn't find a predecessor in this level.
1b1e1fda4638334b484aa38c15f53a131c0b0fdfAndreas Gustafsson * Got to the root of this level without having traversed
1b1e1fda4638334b484aa38c15f53a131c0b0fdfAndreas Gustafsson * any right links. Ascend the tree one level; the
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews * node that points to this tree is the predecessor.
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews INSIST(chain->level_count > 0 && IS_ROOT(current));
94766449d6125cd5870891b70d46573e5deaceb4Brian Wellington predecessor = chain->levels[--chain->level_count];
18b7133679efa8f60fd4e396c628576f3f416b3eBrian Wellington /* XXX DCL probably needs work on the concept */
1b1e1fda4638334b484aa38c15f53a131c0b0fdfAndreas Gustafsson * Don't declare an origin change when the new origin is "."
18b7133679efa8f60fd4e396c628576f3f416b3eBrian Wellington * at the top level tree, because "." is declared as the origin
18b7133679efa8f60fd4e396c628576f3f416b3eBrian Wellington * for the second level tree.
5be3685b0e57677c0cc03113099cb8f99f9a070bMark Andrews (chain->level_count > 0 || OFFSETLEN(predecessor) > 1))
1b1e1fda4638334b484aa38c15f53a131c0b0fdfAndreas Gustafsson result = dns_rbtnodechain_current(chain, name, origin,
5b0413f993b1c1ed837d23641e9f696cda1ee293Brian Wellington result = dns_rbtnodechain_current(chain, name, NULL,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrewsdns_rbtnodechain_down(dns_rbtnodechain_t *chain, dns_name_t *name,
0b09763c354ec91fb352b6b4cea383bd0195b2d8Mark Andrews REQUIRE(VALID_CHAIN(chain) && chain->end != NULL);
if (new_origin) {
return (result);
return (result);
if (new_origin) {
return (result);
return (result);
return (result);
return (result);