rbt.c revision 0c27b3fe77ac1d5094ba3521e8142d9e7973133f
/*
* Copyright (C) 1999-2005, 2007-2009, 2011-2016 Internet Systems Consortium, Inc. ("ISC")
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
*/
/*! \file */
/* Principal Authors: DCL */
#include <config.h>
#ifdef HAVE_INTTYPES_H
#include <inttypes.h> /* uintptr_t */
#endif
#include <isc/platform.h>
#include <isc/refcount.h>
/*%
* This define is so dns/name.h (included by dns/fixedname.h) uses more
* efficient macro calls instead of functions for a few operations.
*/
#define DNS_NAME_USEINLINE 1
#include <dns/fixedname.h>
#include <unistd.h>
#define CHECK(x) \
do { \
result = (x); \
if (result != ISC_R_SUCCESS) \
goto cleanup; \
} while (0)
/*
* XXXDCL Since parent pointers were added in again, I could remove all of the
* chain junk, and replace with dns_rbt_firstnode, _previousnode, _nextnode,
* _lastnode. This would involve pretty major change to the API.
*/
#define RBT_HASH_SIZE 64
#ifdef RBT_MEM_TEST
#endif
struct dns_rbt {
unsigned int magic;
void (*data_deleter)(void *, void *);
void * deleter_arg;
unsigned int nodecount;
void * mmap_location;
};
#define RED 0
#define BLACK 1
/*
* This is the header for map-format RBT images. It is populated,
* and then written, as the LAST thing done to the file before returning.
* Writing this last (with zeros in the header area initially) will ensure
* that the header is only valid when the RBT image is also valid.
*/
typedef struct file_header file_header_t;
/* Pad to 32 bytes */
/* Header length, always the same size regardless of structure size */
#define HEADER_LENGTH 1024
struct file_header {
char version1[32];
/*
* information about the system on which the map file was generated
* will be used to tell if we can load the map file or not
*/
unsigned int nodecount; /* shadow from rbt structure */
};
/*
* The following declarations are for the serialization of an RBT:
*
* step one: write out a zeroed header of 1024 bytes
* step two: walk the tree in a depth-first, left-right-down order, writing
* out the nodes, reserving space as we go, correcting addresses to point
* at the proper offset in the file, and setting a flag for each pointer to
* indicate that it is a reference to a location in the file, rather than in
* memory.
* step three: write out the header, adding the information that will be
* needed to re-create the tree object itself.
*
* The RBTDB object will do this three times, once for each of the three
* RBT objects it contains.
*
* Note: 'file' must point an actual open file that can be mmapped
* and fseeked, not to a pipe or stream
*/
static isc_result_t
static isc_result_t
static isc_result_t
static isc_result_t
/*
* The following functions allow you to get the actual address of a pointer
* without having to use an if statement to check to see if that address is
* relative or not
*/
static inline dns_rbtnode_t *
return ((dns_rbtnode_t *)adjusted_address);
}
static inline dns_rbtnode_t *
return ((dns_rbtnode_t *)adjusted_address);
}
static inline dns_rbtnode_t *
return ((dns_rbtnode_t *)adjusted_address);
}
static inline dns_rbtnode_t *
return ((dns_rbtnode_t *)adjusted_address);
}
static inline dns_rbtnode_t *
return ((dns_rbtnode_t *)adjusted_address);
}
/*%
* Elements of the rbtnode structure.
*/
#ifdef DNS_RBT_USEHASH
#endif /* DNS_RBT_USEHASH */
/*%
* Structure elements from the rbtdb.c, not
* used as part of the rbt.c algorithms.
*/
/*%
* The variable length stuff stored after the node has the following
* structure.
*
* <name_data>{1..255}<oldoffsetlen>{1}<offsets>{1..128}
*
* <name_data> contains the name of the node when it was created.
* <oldoffsetlen> contains the length of <offsets> when the node was created.
* <offsets> contains the offets into name for each label when the node was
* created.
*/
/*%
* Color management.
*/
/*%
* Chain management.
*
* The "ancestors" member of chains were removed, with their job now
* being wholly handled by parent pointers (which didn't exist, because
* of memory concerns, when chains were first implemented).
*/
do { \
} while (0)
/*%
* The following macros directly access normally private name variables.
* These macros are used to avoid a lot of function calls in the critical
* path of the tree traversal code.
*/
static inline void
}
void
}
}
#ifdef DNS_RBT_USEHASH
static isc_result_t
#endif
#ifdef DEBUG
#define inline
/*
* A little something to help out in GDB.
*/
return (name);
}
static void
isc_buffer_t b;
isc_region_t r;
do {
isc_buffer_putuint8(&b, 0);
} while (size > 0);
}
#endif /* DEBUG */
#ifdef DNS_RBT_USEHASH
/*
* Upper node is the parent of the root of the passed node's
* subtree. The passed node must not be NULL.
*/
static inline dns_rbtnode_t *
}
static void
return;
}
/*
* This function is used to fixup uppernode members of all dns_rbtnodes
* after deserialization.
*/
static void
}
#else
/* The passed node must not be NULL. */
static inline dns_rbtnode_t *
}
return (node);
}
/* Upper node is the parent of the root of the passed node's
* subtree. The passed node must not be NULL.
*/
static inline dns_rbtnode_t *
/*
* Return the node in the level above the argument node that points
* to the level the argument node is in. If the argument node is in
* the top level, the return value is NULL.
*/
}
#endif /* DNS_RBT_USEHASH */
break;
nodes++;
}
return (nodes);
}
/*
* Forward declarations.
*/
static isc_result_t
#ifdef DNS_RBT_USEHASH
static inline void
static inline void
static void
#else
#endif
static inline void
static inline void
static void
dns_rbtnode_t **rootp);
static void
static isc_result_t
isc_uint64_t *crc);
static void
dns_rbtnode_t **nodep);
static void
static void
static isc_result_t
/*
* Write out a zeroed header as a placeholder. Doing this ensures
* that the file will not read while it is partially written, should
* writing fail or be interrupted.
*/
char buffer[HEADER_LENGTH];
if (result != ISC_R_SUCCESS)
return (result);
if (result != ISC_R_SUCCESS)
return (result);
return (ISC_R_SUCCESS);
}
/*
* Write out the real header, including NodeDump version information
* and the offset of the first node.
*
* Any information stored in the rbt object itself should be stored
* here.
*/
static isc_result_t
{
if (FILE_VERSION[0] == '\0') {
}
#ifdef DNS_RDATASET_FIXED
#else
header.rdataset_fixed = 0;
#endif
/* Ensure we are always at the end of the file. */
return (result);
}
static isc_result_t
{
unsigned char *node_data;
#ifdef DEBUG
#endif
/*
* If the next node is not NULL, calculate the next node's location
* in the file. Note that this will have to change when the data
* structure changes, and it also assumes that we always write the
* nodes out in list order (which we currently do.)
*/
}
}
}
}
}
#ifdef DEBUG
sizeof(dns_rbtnode_t));
#endif
sizeof(dns_rbtnode_t));
return (result);
}
static isc_result_t
{
*where = 0;
return (ISC_R_SUCCESS);
}
/* Reserve space for current node. */
/*
* Serialize the rest of the tree.
*
* WARNING: A change in the order (from left, right, down)
* will break the way the crc hash is computed.
*/
}
/* Seek back to reserved space. */
/* Serialize the current node. */
/* Ensure we are always at the end of the file. */
return (result);
}
if (offset == 0)
return (target);
else
}
{
/* Write dummy header */
/* Serialize nodes */
if (node_position == end_position) {
*offset = 0;
return (ISC_R_SUCCESS);
}
#ifdef DEBUG
#endif
/* Serialize header */
/* Ensure we are always at the end of the file. */
return (result);
}
#define CONFIRM(a) do { \
if (! (a)) { \
result = ISC_R_INVALIDFILE; \
goto cleanup; \
} \
} while(0);
static isc_result_t
{
unsigned char *node_data;
if (n == NULL)
return (ISC_R_SUCCESS);
CONFIRM(DNS_RBTNODE_VALID(n));
if (!dns_name_isabsolute(&nodename)) {
}
/* memorize header contents prior to fixup */
if (n->left_is_relative) {
n->left_is_relative = 0;
} else
if (n->right_is_relative) {
n->right_is_relative = 0;
} else
if (n->down_is_relative) {
n->down_is_relative = 0;
} else
if (n->parent_is_relative) {
n->parent_is_relative = 0;
} else
if (n->data_is_relative) {
n->data_is_relative = 0;
} else
/* a change in the order (from left, right, down) will break hashing*/
node_data = (unsigned char *) n + sizeof(dns_rbtnode_t);
#ifdef DEBUG
sizeof(dns_rbtnode_t));
#endif
sizeof(dns_rbtnode_t));
datasize);
return (result);
}
{
#ifdef DNS_RDATASET_FIXED
goto cleanup;
}
#else
if (header->rdataset_fixed != 0) {
goto cleanup;
}
#endif
goto cleanup;
}
goto cleanup;
}
/* Copy other data items from the header into our rbt. */
goto cleanup;
}
#ifdef DEBUG
#endif
/* Check file hash */
goto cleanup;
}
goto cleanup;
}
#ifdef DNS_RBT_USEHASH
#endif /* DNS_RBT_USEHASH */
}
return (result);
}
/*
*/
{
#ifdef DNS_RBT_USEHASH
#endif
return (ISC_R_NOMEMORY);
#ifdef DNS_RBT_USEHASH
if (result != ISC_R_SUCCESS) {
return (result);
}
#endif
return (ISC_R_SUCCESS);
}
/*
*/
void
}
return (ISC_R_QUOTA);
return (ISC_R_SUCCESS);
}
unsigned int
}
}
static inline isc_result_t
{
int i;
if (result != ISC_R_SUCCESS)
return (result);
} else
if (result != ISC_R_SUCCESS)
return (result);
}
return (result);
}
static inline isc_result_t
do {
/*
* Go as far right and then down as much as possible,
* as long as the rightmost node has a down pointer.
*/
break;
} while (1);
return (ISC_R_SUCCESS);
}
/*
* Add 'name' to tree, initializing its data pointer with 'data'.
*/
/*
* Does this thing have too many variables or what?
*/
unsigned int level_count;
unsigned int common_labels;
int order;
/*
* Dear future BIND developer,
*
* After you have tried attempting to optimize this routine by
* using the hashtable and have realized your folly, please
* append another cross ("X") below as a warning to the next
* future BIND developer:
*
* Number of victim developers: X
*
* I wish the past developer had included such a notice.
*
* Long form: Unlike dns_rbt_findnode(), this function does not
* lend itself to be optimized using the hashtable:
*
* 1. In the subtree where the insertion occurs, this function
* needs to have the insertion point and the order where the
* lookup terminated (i.e., at the insertion point where left or
* right child is NULL). This cannot be determined from the
* hashtable, so at least in that subtree, a BST O(log N) lookup
* is necessary.
*
* 2. Our RBT nodes contain not only single labels but label
* sequences to optimize space usage. So at every level, we have
* to look for a match in the hashtable for all superdomains in
* the rest of the name we're searching. This is an O(N)
* operation at least, here N being the label size of name, each
* of which is a hashtable lookup involving dns_name_equal()
* comparisons.
*/
/*
* Create a copy of the name so the original name structure is
* not modified.
*/
if (result == ISC_R_SUCCESS) {
#ifdef DNS_RBT_USEHASH
#endif /* DNS_RBT_USEHASH */
*nodep = new_current;
}
return (result);
}
level_count = 0;
hlabels = 0;
do {
&order, &common_labels);
if (compared == dns_namereln_equal) {
break;
}
if (compared == dns_namereln_none) {
if (order < 0) {
} else if (order > 0) {
}
} else {
/*
* This name has some suffix in common with the
* name at the current node. If the name at
* the current node is shorter, that means the
* new name should be in a subtree. If the
* name at the current node is longer, that means
* the down pointer to this tree should point
* to a new tree that has the common suffix, and
* the non-common parts of these two names should
* start a new tree.
*/
hlabels += common_labels;
if (compared == dns_namereln_subdomain) {
/*
* All of the existing labels are in common,
* so the new name is in a subtree.
* Whack off the common labels for the
* not-in-common part to be searched for
* in the next level.
*/
/*
* Follow the down pointer (possibly NULL).
*/
level_count++;
} else {
/*
* The number of labels in common is fewer
* than the number of labels at the current
* node, so the current node must be adjusted
* to have just the common suffix, and a down
* pointer made to a new tree.
*/
|| compared == dns_namereln_contains);
/*
* Ensure the number of levels in the tree
* does not exceed the number of logical
* levels allowed by DNSSEC.
*
* XXXDCL need a better error result?
*/
if (level_count >= DNS_RBT_LEVELBLOCK) {
break;
}
/*
* Split the name into two parts, a prefix
* which is the not-in-common parts of the
* two names and a suffix that is the common
* parts of them.
*/
&new_current);
if (result != ISC_R_SUCCESS)
break;
/*
* Reproduce the tree attributes of the
* current node.
*/
else
/*
* Fix pointers that were to the current node.
*/
else
}
*root = new_current;
/*
* Set up the new root of the next level.
* By definition it will not be the top
* level tree, so clear DNS_NAMEATTR_ABSOLUTE.
*/
#ifdef DNS_RBT_USEHASH
#endif /* DNS_RBT_USEHASH */
level_count++;
if (common_labels ==
/*
* The name has been added by pushing
* the not-in-common parts down to
* a new level.
*/
*nodep = new_current;
return (ISC_R_SUCCESS);
} else {
/*
* The current node has no data,
* because it is just a placeholder.
* Its data pointer is already NULL
* from create_node()), so there's
* nothing more to do to it.
*/
/*
* The not-in-common parts of the new
* name will be inserted into the new
* level following this loop (unless
* result != ISC_R_SUCCESS, which
* is tested after the loop ends).
*/
break;
}
}
}
#ifdef DNS_RBT_USEHASH
else
#endif /* DNS_RBT_USEHASH */
*nodep = new_current;
}
return (result);
}
/*
* Add a name to the tree of trees, associating it with some data.
*/
/*
* dns_rbt_addnode will report the node exists even when
* it does not have data associated with it, but the
* dns_rbt_*name functions all behave depending on whether
* there is data associated with a node.
*/
if (result == ISC_R_SUCCESS ||
}
return (result);
}
/*
* Find the node for "name" in the tree of trees.
*/
void *callback_arg)
{
unsigned int common_labels;
unsigned int hlabels = 0;
int order;
/*
* If there is a chain it needs to appear to be in a sane state,
* otherwise a chain is still needed to generate foundname and
* callback_name.
*/
chain = &localchain;
} else
return (ISC_R_NOTFOUND);
/*
* Appease GCC about variables it incorrectly thinks are
* possibly used uninitialized.
*/
order = 0;
/*
* search_name is the name segment being sought in each tree level.
* By using a fixedname, the search_name will definitely have offsets
* for use by any splitting.
* By using dns_name_clone, no name data should be copied thanks to
* the lack of bitstring labels.
*/
&order, &common_labels);
/*
* last_compared is used as a shortcut to start (or
* continue rather) finding the stop-node of the search
* when hashing was used (see much below in this
* function).
*/
if (compared == dns_namereln_equal)
break;
if (compared == dns_namereln_none) {
#ifdef DNS_RBT_USEHASH
/*
* Here, current is pointing at a subtree root
* node. We try to find a matching node using
* the hashtable. We can get one of 3 results
* here: (a) we locate the matching node, (b) we
* find a node to which the current node has a
* subdomain relation, (c) we fail to find (a)
* or (b).
*/
unsigned int nlabels;
unsigned int tlabels = 1;
unsigned int hash;
/*
* The case of current not being a subtree root,
* that means a left or right pointer was
* followed, only happens when the algorithm
* fell through to the traditional binary search
* because of a bitstring label. Since we
* dropped the bitstring support, this should
* not happen.
*/
/*
* current is the root of the current level, so
* its parent is the same as its "up" pointer.
*/
/*
* Compute the hash over the full absolute
* name. Look for the smallest suffix match at
* this tree level (hlevel), and then at every
* iteration, look for the next smallest suffix
* match (add another subdomain label to the
* absolute name being hashed).
*/
&hash_name);
/*
* Walk all the nodes in the hash bucket pointed
* by the computed hash value.
*/
{
continue;
/*
* This checks that the hashed label
* sequence being looked up is at the
* same tree level, so that we don't
* match a labelsequence from some other
* subdomain.
*/
continue;
break;
}
/*
* This is an optimization. If hashing found
* the right node, the next call to
* dns_name_fullcompare() would obviously
* return _equal or _subdomain. Determine
* which of those would be the case by
* checking if the full name was hashed. Then
* make it look like dns_name_fullcompare
* was called and jump to the right place.
*/
break;
} else {
goto subdomain;
}
}
goto hashagain;
/*
* All of the labels have been tried against the hash
* table. Since we dropped the support of bitstring
* labels, the name isn't in the table.
*/
continue;
#else /* DNS_RBT_USEHASH */
/*
* Standard binary search tree movement.
*/
if (order < 0)
else
#endif /* DNS_RBT_USEHASH */
} else {
/*
* The names have some common suffix labels.
*
* If the number in common are equal in length to
* the current node's name length, then follow the
* down pointer and search in the new tree.
*/
if (compared == dns_namereln_subdomain) {
#ifdef DNS_RBT_USEHASH
#endif
/*
* Whack off the current node's common parts
* for the name to search in the next level.
*/
search_name, NULL);
hlabels += common_labels;
/*
* This might be the closest enclosing name.
*/
(options & DNS_RBTFIND_EMPTYDATA) != 0)
/*
* Point the chain to the next level. This
* needs to be done before 'current' is pointed
* there because the callback in the next
* block of code needs the current 'current',
* but in the event the callback requests that
* the search be stopped then the
* DNS_R_PARTIALMATCH code at the end of this
* function needs the chain pointed to the
* next level.
*/
/*
* The caller may want to interrupt the
* downward search when certain special nodes
* are traversed. If this is a special node,
* the callback is used to learn what the
* caller wants to do.
*/
FINDCALLBACK(current)) {
if (result != ISC_R_SUCCESS) {
return (result);
}
if (result != DNS_R_CONTINUE) {
/*
* Treat this node as if it
* had no down pointer.
*/
break;
}
}
/*
* Finally, head to the next tree level.
*/
} else {
/*
* Though there are labels in common, the
* entire name at this node is not common
* with the search name so the search
* name does not exist in the tree.
*/
|| compared == dns_namereln_contains);
}
}
}
/*
* If current is not NULL, NOEXACT is not disallowing exact matches,
* and either the node has data or an empty node is ok, return
* ISC_R_SUCCESS to indicate an exact match.
*/
(options & DNS_RBTFIND_EMPTYDATA) != 0)) {
/*
* Found an exact match.
*/
else
if (result == ISC_R_SUCCESS) {
} else
} else {
/*
* Did not find an exact match (or did not want one).
*/
/*
* ... but found a partially matching superdomain.
* Unwind the chain to the partial match node
* to set level_matches to the level above the node,
* and then to derive the name.
*
* chain->level_count is guaranteed to be at least 1
* here because by definition of finding a superdomain,
* the chain is pointed to at least the first subtree.
*/
chain->level_matches--;
}
} else
if (result == ISC_R_SUCCESS)
} else
/*
* There was an exact match but either
* DNS_RBTFIND_NOEXACT was set, or
* DNS_RBTFIND_EMPTYDATA was set and the node had no
* data. A policy decision was made to set the
* chain to the exact match, but this is subject
* to change if it becomes apparent that something
* else would be more useful. It is important that
* this case is handled here, because the predecessor
* setting code below assumes the match was not exact.
*/
((options & DNS_RBTFIND_EMPTYDATA) == 0 &&
} else if ((options & DNS_RBTFIND_NOPREDECESSOR) != 0) {
/*
* Ensure the chain points nowhere.
*/
} else {
/*
* Since there was no exact match, the chain argument
* needs to be pointed at the DNSSEC predecessor of
* the search name.
*/
if (compared == dns_namereln_subdomain) {
/*
* Attempted to follow a down pointer that was
* NULL, which means the searched for name was
* a subdomain of a terminal name in the tree.
* Since there are no existing subdomains to
* order against, the terminal name is the
* predecessor.
*/
chain->level_count);
} else {
/*
* Point current to the node that stopped
* the search.
*
* With the hashing modification that has been
* added to the algorithm, the stop node of a
* standard binary search is not known. So it
* has to be found. There is probably a more
* clever way of doing this.
*
* The assignment of current to NULL when
* the relationship is *not* dns_namereln_none,
* even though it later gets set to the same
* last_compared anyway, is simply to not push
* the while loop in one more level of
* indentation.
*/
if (compared == dns_namereln_none)
else
&order,
/*
* Standard binary search movement.
*/
if (order < 0)
else
}
/*
* Reached a point within a level tree that
* positively indicates the name is not
* present, but the stop node could be either
* less than the desired name (order > 0) or
* greater than the desired name (order < 0).
*
* If the stop node is less, it is not
* necessarily the predecessor. If the stop
* node has a down pointer, then the real
* predecessor is at the end of a level below
* (not necessarily the next level).
* Move down levels until the rightmost node
* does not have a down pointer.
*
* When the stop node is greater, it is
* the successor. All the logic for finding
* the predecessor is handily encapsulated
* in dns_rbtnodechain_prev. In the event
* that the search name is less than anything
* else in the tree, the chain is reset.
* XXX DCL What is the best way for the caller
* to know that the search name has
* no predecessor?
*/
if (order > 0) {
result2 =
if (result2 != ISC_R_SUCCESS)
} else
/*
* Ah, the pure and simple
* case. The stop node is the
* predecessor.
*/
} else {
NULL,
NULL);
if (result2 == ISC_R_SUCCESS ||
; /* Nothing. */
else if (result2 == ISC_R_NOMORE)
/*
* There is no predecessor.
*/
else
}
}
}
}
return (result);
}
/*
* Get the data pointer associated with 'name'.
*/
else
return (result);
}
/*
* Delete a name from the tree of trees.
*/
/*
* First, find the node.
*
* When searching, the name might not have an exact match:
* elements of a tree, which would make layer 1 a single
* 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
* match in the first layer. Should it be a requirement that
* that the name to be deleted have data? For now, it is.
*
* ->dirty, ->locknum and ->references are ignored; they are
* solely the province of rbtdb.c.
*/
if (result == ISC_R_SUCCESS) {
else
} else if (result == DNS_R_PARTIALMATCH)
return (result);
}
/*
* Remove a node from the tree of trees.
*
* NOTE WELL: deletion is *not* symmetric with addition; that is, reversing
* a sequence of additions to be deletions will not generally get the
* tree back to the state it started in. For example, if the addition
* 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
* turned out to be a bad idea because it could corrupt an active nodechain
* that had "b.c" as one of its levels -- and the RBT has no idea what
* nodechains are in use by callers, so it can't even *try* to helpfully
* fix them up (which would probably be doomed to failure anyway).
*
* Similarly, it is possible to leave the tree in a state where a supposedly
* deleted node still exists. The first case of this is obvious; take
* It was just established in the previous paragraph why we can't pull "a"
* back up to its parent level. But what happens when "a" then gets deleted?
* "b.c" is left hanging around without data or children. This condition
* is actually pretty easy to detect, but ... should it really be removed?
* Is a chain pointing to it? An iterator? Who knows! (Note that the
* references structure member cannot be looked at because it is private to
* rbtdb.) This is ugly and makes me unhappy, but after hours of trying to
* make it more aesthetically proper and getting nowhere, this is the way it
* is going to stay until such time as it proves to be a *real* problem.
*
* Finally, for reference, note that the original routine that did node
* joining was called join_nodes(). It has been excised, living now only
* in the CVS history, but comments have been left behind that point to it just
* in case someone wants to muck with this some more.
*
* The one positive aspect of all of this is that joining used to have a
* case where it might fail. Without trying to join, now this function always
* succeeds. It still returns isc_result_t, though, so the API wouldn't change.
*/
{
if (recurse) {
} else {
/*
* Since there is at least one node below this one and
* no recursion was requested, the deletion is
* complete. The down node from this node might be all
* by itself on a single level, so join_nodes() could
* be used to collapse the tree (with all the caveats
* of the comment at the start of this function).
* But join_nodes() function has now been removed.
*/
return (ISC_R_SUCCESS);
}
}
/*
* Note the node that points to the level of the node
* that is being deleted. If the deleted node is the
* top level, parent will be set to NULL.
*/
/*
* This node now has no down pointer, so now it needs
* to be removed from this level.
*/
#if DNS_RBT_USEMAGIC
#endif
/*
* This function never fails.
*/
return (ISC_R_SUCCESS);
}
void
}
do {
if (result != ISC_R_SUCCESS)
break;
} while (! dns_name_isabsolute(name));
return (result);
}
char *
{
if (result == ISC_R_SUCCESS)
else
return (printname);
}
static isc_result_t
unsigned int labels;
/*
* Allocate space for the node structure, the name, and the offsets.
*/
return (ISC_R_NOMEMORY);
node->is_mmapped = 0;
node->down_is_relative = 0;
node->left_is_relative = 0;
node->right_is_relative = 0;
node->parent_is_relative = 0;
node->data_is_relative = 0;
#ifdef DNS_RBT_USEHASH
#endif
dns_rbtnode_refinit(node, 0);
node->find_callback = 0;
/*
* The following is stored to make reconstructing a name from the
* stored value in the node easy: the length of the name, the number
* of labels, whether the name is absolute or not, the name itself,
* and the name's offsets table.
*
* XXX RTH
* The offsets table could be made smaller by eliminating the
* first offset, which is always 0. This requires changes to
*
* Note: OLDOFFSETLEN *must* be assigned *after* OLDNAMELEN is assigned
* as it uses OLDNAMELEN.
*/
#if DNS_RBT_USEMAGIC
#endif
return (ISC_R_SUCCESS);
}
#ifdef DNS_RBT_USEHASH
static inline void
unsigned int hash;
}
static isc_result_t
unsigned int bytes;
return (ISC_R_NOMEMORY);
return (ISC_R_SUCCESS);
}
static void
unsigned int oldsize;
unsigned int hash;
unsigned int i;
do {
return;
}
for (i = 0; i < oldsize; i++) {
}
}
}
static inline void
}
static inline void
unsigned int bucket;
if (bucket_node == node) {
} else {
}
}
}
#endif /* DNS_RBT_USEHASH */
static inline void
} else {
else
}
}
static inline void
} else {
else
}
}
/*
* This is the real workhorse of the insertion code, because it does the
*/
static void
{
/*
* First node of a level.
*/
return;
}
if (order < 0) {
} else {
}
/*
* XXXDCL could do away with separate parent and grandparent
* variables. They are vestiges of the days before parent
* pointers. However, they make the code a little clearer.
*/
node = grandparent;
} else {
}
}
} else {
node = grandparent;
} else {
}
}
}
}
return;
}
/*
* This is the real workhorse of the deletion code, because it does the
*/
static void
/*
* Verify that the parent history is (apparently) correct.
*/
/*
* This is the only item in the tree.
*/
return;
}
} else
/*
* This node has one child, on the right.
*/
/*
* This node has one child, on the left.
*/
else {
/*
* This node has two children, so it cannot be directly
* deleted. Find its immediate in-order successor and
* move it to this location, then do the deletion at the
* old site of the successor.
*/
/*
* The successor cannot possibly have a left child;
* if there is any child, it is on the right.
*/
/*
* Swap the two nodes; it would be simpler to just replace
* the value being deleted with that of the successor,
* but this rigamarole is done so the caller has complete
* control over the pointers (and memory allocation) of
* all of nodes. If just the key value were removed from
* the tree, the pointer to the node would be unchanged.
*/
/*
* First, put the successor in the tree location of the
* node to be deleted. Save its existing tree pointer
* information, which will be needed when linking up
* delete to the successor's old location.
*/
} else
else
/*
* Now relink the node to be deleted into the
* successor's previous tree location. PARENT(tmp)
* is the successor's original parent.
*/
/*
* Node being deleted was successor's parent.
*/
} else {
}
/*
* Original location of successor node has no left.
*/
}
/*
* Remove the node by removing the links from its parent.
*/
else
} else {
/*
* This is the root being deleted, and at this point
* it is known to have just one child.
*/
}
/*
* Fix color violations.
*/
}
} else {
}
}
} else {
/*
* Child is parent's right child.
* Everything is done the same as above,
* except mirrored.
*/
}
} else {
}
}
}
}
}
}
static void
if (node->is_mmapped == 0) {
}
}
static void
{
/*
* If there is a left, right or down node, walk into it
* and iterate.
*/
} else {
/*
* There are no left, right or down nodes, so we
* can free this one and go back to its parent.
*/
rbt->deleter_arg);
if (unhash)
/*
* Note: we don't call unhash_node() here as we
* are destroying the complete RBT tree.
*/
#if DNS_RBT_USEMAGIC
#endif
break;
}
}
}
static size_t
return (0);
}
}
static isc_boolean_t
return (ISC_TRUE);
/* Root nodes must be BLACK. */
return (ISC_FALSE);
/* Both children of RED nodes must be BLACK. */
return (ISC_FALSE);
}
return (ISC_FALSE);
return (ISC_FALSE);
return (ISC_FALSE);
}
/* If node is assigned to the down_ pointer of its parent, it is
* a subtree root and must have the flag set.
*/
{
return (ISC_FALSE);
}
/* Repeat tests with this node's children. */
}
static isc_boolean_t
*distance = 1;
return (ISC_TRUE);
}
return (ISC_FALSE);
return (ISC_FALSE);
return (ISC_FALSE);
/* Left and right side black node counts must match. */
return (ISC_FALSE);
dl++;
return (ISC_TRUE);
}
return (ISC_FALSE);
/* Path from a given node to all its leaves must contain the
* same number of BLACK child nodes. This is done separately
* here instead of inside check_properties_helper() as
* it would take (n log n) complexity otherwise.
*/
}
static void
int i;
for (i = 0; i < depth; i++)
fprintf(f, "- ");
}
void
fprintf(f, "Node info for nodename: ");
printnodename(n, ISC_TRUE, f);
fprintf(f, "\n");
fprintf(f, "n = %p\n", n);
fprintf(f, "Relative pointers: %s%s%s%s%s\n",
}
static void
isc_region_t r;
char buffer[DNS_NAME_FORMATSIZE];
dns_name_fromregion(&name, &r);
if (quoted)
else
}
static void
{
dns_rbt_indent(f, depth);
fprintf(f, " (BAD parent pointer! -> ");
else
fprintf(f, "NULL");
fprintf(f, ")");
}
fprintf(f, ")");
}
fprintf(f, "\n");
depth++;
data_printer, f);
data_printer, f);
data_printer, f);
} else {
}
}
void
{
}
static int
{
unsigned int l, r, d;
return (0);
*nodecount += 1;
fprintf(f, "|<f2>");
if (show_pointers)
fprintf(f, "\"] [");
fprintf(f, "color=red");
else
fprintf(f, "color=black");
/* XXXMUKS: verify that IS_ROOT() indicates subtree root and not
* forest root.
*/
fprintf(f, ",penwidth=3");
fprintf(f, ",style=filled,fillcolor=lightgrey");
fprintf(f, "];\n");
fprintf(f, "\"node%u\":f1 -> \"node%u\":f1 [penwidth=5];\n",
*nodecount, d);
return (*nodecount);
}
void
unsigned int nodecount = 0;
fprintf(f, "digraph g {\n");
fprintf(f, "node [shape = record,height=.1];\n");
fprintf(f, "}\n");
}
/*
* Chain Functions
*/
void
/*
* Initialize 'chain'.
*/
chain->level_count = 0;
chain->level_matches = 0;
}
{
return (ISC_R_NOTFOUND);
if (chain->level_count == 0) {
/*
* Names in the top level tree are all absolute.
* Always make 'name' relative.
*/
/*
* This is cheaper than dns_name_getlabelsequence().
*/
}
}
if (chain->level_count > 0)
else
}
return (result);
}
{
predecessor = NULL;
/*
* Moving left one then right as far as possible is the
* previous node, at least for this level.
*/
} else {
/*
* No left links, so move toward the root. If at any point on
* the way there the link from parent to child is a right
* link, then the parent is the previous node, at least
* for this level.
*/
break;
}
}
}
if (predecessor != NULL) {
/*
* Found a predecessor node in this level. It might not
* really be the predecessor, however.
*/
/*
* The predecessor is really down at least one level.
* Go down and as far right as possible, and repeat
* as long as the rightmost node has a down pointer.
*/
do {
/*
* XXX DCL Need to do something about origins
* here. See whether to go down, and if so
* whether it is truly what Bob calls a
* new origin.
*/
/* XXX DCL duplicated from above; clever
* way to unduplicate? */
/* XXX DCL probably needs work on the concept */
}
} else if (chain->level_count > 0) {
/*
* Dang, didn't find a predecessor in this level.
* Got to the root of this level without having traversed
* any right links. Ascend the tree one level; the
* node that points to this tree is the predecessor.
*/
/* XXX DCL probably needs work on the concept */
/*
* Don't declare an origin change when the new origin is "."
* at the top level tree, because "." is declared as the origin
* for the second level tree.
*/
}
if (predecessor != NULL) {
if (new_origin) {
NULL);
if (result == ISC_R_SUCCESS)
} else
NULL);
} else
return (result);
}
{
/*
* Don't declare an origin change when the new origin is "."
* at the second level tree, because "." is already declared
* as the origin for the top level tree.
*/
if (chain->level_count > 0 ||
}
/*
* It is not necessary to use dns_rbtnodechain_current like
* the other functions because this function will never
* find a node in the topmost level. This is because the
* root level will never be more than one name, and everything
* in the megatree is a successor to that node, down at
* the second level or below.
*/
if (new_origin) {
if (result == ISC_R_SUCCESS)
} else
} else
return (result);
}
break;
}
}
} else {
}
} else
return (result);
}
{
/*
* If there is a level below this node, the next node is the leftmost
* node of the next level.
*/
/*
* Don't declare an origin change when the new origin is "."
* at the second level tree, because "." is already declared
* as the origin for the top level tree.
*/
if (chain->level_count > 0 ||
/*
* The successor is up, either in this level or a previous one.
* Head back toward the root of the tree, looking for any path
* that was via a left link; the successor is the node that has
* that left link. In the event the root of the level is
* reached without having traversed any left links, ascend one
* level and look for either a right link off the point of
* ascent, or search for a left link upward again, repeating
* ascends until either case is true.
*/
do {
break;
}
}
/*
* Reached the root without having traversed
* any left pointers, so this level is done.
*/
if (chain->level_count == 0)
break;
break;
}
}
}
/*
* It is not necessary to use dns_rbtnodechain_current like
* the other functions because this function will never
* find a node in the topmost level. This is because the
* root level will never be more than one name, and everything
* in the megatree is a successor to that node, down at
* the second level or below.
*/
if (new_origin) {
if (result == ISC_R_SUCCESS)
} else
} else
return (result);
}
{
if (result == ISC_R_SUCCESS)
return (result);
}
{
if (result != ISC_R_SUCCESS)
return (result);
if (result == ISC_R_SUCCESS)
return (result);
}
void
/*
* Free any dynamic storage associated with 'chain', and then
* reinitialize 'chain'.
*/
chain->level_count = 0;
chain->level_matches = 0;
}
void
/*
* Free any dynamic storage associated with 'chain', and then
* invalidate 'chain'.
*/
}
/* XXXMUKS:
*
* - worth removing inline as static functions are inlined automatically
* where suitable by modern compilers.
* - bump the size of dns_rbt.nodecount to size_t.
* - the dumpfile header also contains a nodecount that is unsigned
* int. If large files (> 2^32 nodes) are to be supported, the
* allocation for this field should be increased.
*/