rbt.c revision ec80744ad68b97f15657b1fdf5591c30b559b57d
/*
* Copyright (C) 1999 Internet Software Consortium.
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS
* ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE
* CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
* DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
* PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
* ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
* SOFTWARE.
*/
/* $Id: rbt.c,v 1.39 1999/04/16 16:12:15 tale Exp $ */
/* Principal Authors: DCL */
#include <config.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <isc/assertions.h>
#include <dns/fixedname.h>
struct dns_rbt {
unsigned int magic;
void (*data_deleter)(void *, void *);
void * deleter_arg;
};
#define RED 0
#define BLACK 1
/*
* Elements of the rbtnode structure.
*/
/*
* Structure elements from the rbtdb.c, not
* used as part of the rbt.c algorithms.
*/
/*
* The variable length stuff stored after the node.
*/
/*
* Color management.
*/
/*
* Chain management.
*/
do { \
return (DNS_R_NOMEMORY); \
} \
} 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.
*/
do { \
} while (0)
#define FAST_ISABSOLUTE(name) \
#define FAST_COUNTLABELS(name) \
#ifdef DEBUG
#define inline
/*
* A little something to help out in GDB.
*/
return (name);
}
#endif
#if defined(ISC_MEM_DEBUG) || defined(RBT_MEM_TEST)
#endif
/*
* Forward declarations.
*/
dns_rbtnode_t **rootp);
dns_rbtnode_t **rootp);
dns_rbtnode_t **rootp);
/*
*/
{
return (DNS_R_NOMEMORY);
return (DNS_R_SUCCESS);
}
/*
*/
void
}
/*
* The next three functions for chains, get_ancestor_mem, put_ancestor_mem
* and chain_name, appear early in this file so they can be effectively
* inlined by the other rbt functions that use them.
*/
static inline dns_result_t
if (oldsize == 0) {
} else {
if (ancestor_mem == NULL)
return (DNS_R_NOMEMORY);
}
return (DNS_R_SUCCESS);
}
/*
* This is used by functions that are popping the chain off their
* own stack, and so do not need to have ancestor_maxitems or the
* ancestors pointer reset. Functions that will be reusing a chain
* structure need to call dns_rbtnodechain_reset() instead.
*/
static inline void
* sizeof(dns_rbtnode_t *));
}
static inline dns_result_t
{
unsigned int i;
/*
* XXX Is this too devilish, initializing name like this?
*/
if (result != DNS_R_SUCCESS)
return result;
for (i = 0; i < chain->level_count; i++) {
if (result != DNS_R_SUCCESS)
break;
}
}
return (result);
}
static inline dns_result_t
while (1) {
/*
* Go as far right and then down as much as possible,
* as long as the rightmost node has a down pointer.
*/
}
break;
}
return (DNS_R_SUCCESS);
}
/*
* Add 'name' to tree, initializing its data pointer with 'data'.
*/
/*
* Does this thing have too many variables or what?
*/
isc_region_t r;
unsigned int common_labels, common_bits;
int order;
/*
* Create a copy of the name so the original name structure is
* not modified.
*/
dns_name_toregion(name, &r);
dns_name_fromregion(&add_name, &r);
if (result == DNS_R_SUCCESS) {
*nodep = new_current;
}
return (result);
}
do {
&order,
&common_labels, &common_bits);
if (compared == dns_namereln_equal) {
return (DNS_R_EXISTS);
}
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.
*/
if (compared == dns_namereln_subdomain) {
/*
* All of the exising labels are in common,
* so the new name is in a subtree.
* First, turn the non-in-common part of
* &add_name into its own dns_name_t to be
* searched for in the downtree.
*/
start_label = 0;
&add_name);
/*
* Follow the down pointer (possibly NULL).
*/
} 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.
*
* XXX DCL need a better error result?
*/
if (chain.level_count ==
return (DNS_R_NOSPACE);
/* XXX DCL handle bitstrings.
* When common_bits is non-zero, the last label
* in common (eg, vix in a.vix.com vs
* b.vix.com) is a bit label and common_bits is
* how many are in common. To split the node,
* the node in question will have to split into
* two bitstrings. A comment in name.h says,
* "Some provision still needs to be made for
* splitting bitstring labels," and Bob has
* pushed this down on the priority list,
* so for now splitting on bitstrings does not
* work.
*/
/*
* Get the common labels of the current name.
*/
&tmp_name);
&tmp_name, &new_current);
if (result != DNS_R_SUCCESS) {
return (result);
}
/*
* Reproduce the tree attributes of the
* current node.
*/
/*
* Fix pointers that were to the current node.
*/
else
*root = new_current;
/*
* Now create the new root of the subtree
* as the not-in-common labels of the current
* node, keeping the same memory location so
* as not to break any external references to
* the node. The down pointer and name data
* are preserved, while left and right
* pointers are nullified when the node is
* established as the start of the next level.
*/
start_label = 0;
&new_name);
/*
* The name stored at the node is effectively
* truncated in place by setting the shorter
* name length, moving the offsets to the
* end of the truncated name, and then
* updating PADBYTES to reflect the truncation.
*/
+ (current_labels - keep_labels);
/*
* Set up the new root of the next level.
* By definition it will not be the top
* level tree, so clear DNS_NAMEATTR_ABSOLUTE.
*/
if (common_labels == add_labels) {
/*
* The name has been added by pushing
* the not-in-common parts down to
* a new level.
*/
*nodep = new_current;
return (DNS_R_SUCCESS);
} else {
/*
* The current node has no data,
* because it is just a placeholder.
* Its data pointer is already NULL
* from create_node()).
*/
/* The not-in-common parts of the new
* name will be inserted into the new
* level following this loop.
*/
start_label = 0;
&add_name);
}
}
}
if (result == DNS_R_SUCCESS) {
*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 == DNS_R_SUCCESS ||
}
return (result);
}
/*
* Find the node for "name" in the tree of trees.
*/
void *callback_arg)
{
isc_region_t r;
unsigned int first_common_label;
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
/*
* search_name is the name segment being sought in each tree level.
* Ensure that it has offsets by making a copy into a structure
* that has offsets.
*/
search_name = &name1;
dns_name_toregion(name, &r);
} else
search_name = name;
current_name = &name2;
&order,
&common_labels, &common_bits);
if (compared == dns_namereln_equal)
break;
if (compared == dns_namereln_none) {
/*
* Standard binary search tree movement.
*/
if (order < 0)
else
} 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 (common_labels == current_labels) {
/*
* Set up new name to search for as
* the not-in-common part, and build foundname.
*/
if (search_name == &name2) {
current_name = &name2;
} else {
current_name = &name1;
}
/*
* Whack off the current node's common labels
* for the name to search in the next level.
*/
tmp_name);
/*
* This might be the closest enclosing name.
*/
/*
* 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.
*/
ISC_TRUE);
if (result != DNS_R_SUCCESS) {
return (result);
}
if (result != DNS_R_CONTINUE) {
/*
* Treat this node as if it
* had no down pointer.
*/
break;
}
}
/*
* Search in the next tree level.
*/
} else {
/*
* Though there is a suffix in common, it
* is shorter than the length of the name at
* this node, which means there is no down
* pointer and the name does not exist.
* Add this node to the ancestor chain
* to simplify things for the chain fixing
* logic below then end the loop.
*/
}
}
}
else
if (result == DNS_R_SUCCESS) {
} else
} else {
/*
* Unwind the chain to the partial match node
* to derive the name.
*/
*node)
chain->level_count--;
} else
if (result == DNS_R_SUCCESS)
} else
if (chain != &localchain) {
/*
* The chain argument needs to be pointed at the
* DNSSEC predecessor of the search name.
*
* First, point current to the node that stopped the
* search, and remove that node from the ancestor
* history.
*/
/*
* 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.
*/
} 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 != DNS_R_SUCCESS)
} else
/*
* Ah, the pure and simple
* case. The stop node is the
* predecessor.
*/
} else {
NULL,
NULL);
if (result2 == DNS_R_SUCCESS ||
; /* Nothing */
else if (result2 == DNS_R_NOMORE)
else
}
}
}
}
if (chain == &localchain)
return (result);
}
/*
* Get the data pointer associated with 'name'.
*/
else
return (result);
}
/*
* Delete a name from the tree of trees.
*/
/*
* Find the node, building the ancestor chain.
*
* 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.
*/
/*
* The guts of this routine are in a separate function (which
* is called only once, by this function) to make freeing the
* ancestor memory easier, since there are several different
* exit points from the level checking logic.
*/
if (result == DNS_R_SUCCESS) {
else
} else if (result == DNS_R_PARTIALMATCH)
return (result);
}
/*
*
*/
static dns_result_t
if (recurse) {
} else {
rbt->deleter_arg);
/*
* This node cannot be removed because it
* points down to a level that has more than
* one node, so it must continue to serve
* as the root for that level. All that
* could be done was to blast its data.
*/
return (DNS_R_SUCCESS);
/*
* There is a down pointer to a level with a single
* item. That item's name can be joined with the name
* on this level.
*/
return (result);
}
}
/*
* This node now has no down pointer (either because it didn't
* have one to start, or because it was recursively removed).
* So now the node needs to be removed from this level.
*/
/*
* Everything is successful, unless the next block fails.
*/
/*
* If there is one node left on this level, and the node one level up
* that points down to here has no data, then those two nodes can be
* merged. The focus for exploring this criteria is shifted up one
* level.
*/
/*
* The search to find the original node went through the
* node that is now being examined. It might have been
*
* current_node -down-to-> deleted_node ... or ...
*
* deleted_node
*
* In the first case, ancestor_count - 1 is NULL and - 2
* is the parent of current_node (possibly also NULL).
* In the second case, ancestor_count - 1 is remaining_node,
* - 2, is NULL and - 3 is the parent of current_node.
*/
}
return (result);
}
void
}
static dns_result_t
unsigned int labels;
/*
* Allocate space for the node structure, the name, and the offsets.
*/
return (DNS_R_NOMEMORY);
/*
* 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
*/
return (DNS_R_SUCCESS);
}
static dns_result_t
isc_region_t r;
return (DNS_R_NOMEMORY);
dns_name_fromregion(&newname, &r);
/*
* Check whether the space needed for the joined names can
* fit within the space already available in the down node,
* so that any external references to the down node are preserved.
*
* Currently this is not very meaningful since preservation
* of the address of the down node cannot be guaranteed.
*/
else {
}
if (result == DNS_R_SUCCESS) {
/*
* Fix the pointers to the original node.
*/
else
} else
}
}
return (result);
}
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
{
unsigned int depth;
return;
}
if (order < 0)
else
node = grandparent;
depth -= 2;
} else {
&root);
}
&root);
}
} else {
node = grandparent;
depth -= 2;
} else {
&root);
}
&root);
}
}
}
return;
}
/*
* This is the real workhorse of the deletion code, because it does the
*
* The ancestor and level history _must_ be set with dns_rbt_findnode for
* this function to work properly.
*/
static void
int depth;
if (chain->level_count > 0)
else
/*
*/
== NULL) {
/*
* 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 would be
* unchanged.
*/
/*
* First, put the successor in the tree location of the
* node to be deleted.
*/
if (parent)
else
else
/*
* Now relink the node to be deleted into the
* successor's previous tree location.
*/
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.
*/
rootp);
}
} else {
rootp);
}
rootp);
}
} else {
rootp);
}
} else {
rootp);
}
rootp);
}
}
}
}
}
/*
* This should only be used on the root of a tree, because no color fixup
* is done at all.
*
* NOTE: No root pointer maintenance is done, because the function is only
* used for two cases:
* + deleting everything DOWN from a node that is itself being deleted, and
* + deleting the entire tree of trees from dns_rbt_destroy.
* In each case, the root pointer is no longer relevant, so there
* is no need for a root parameter to this function.
*
* If the function is ever intended to be used to delete something where
* a pointer needs to be told that this tree no longer exists,
* this function would need to adjusted accordingly.
*/
static void
return;
}
static void
dns_rbt_indent(int depth) {
int i;
for (i = 0; i < depth; i++)
putchar('\t');
}
static void
char *buffer[255];
isc_region_t r;
dns_name_fromregion(&name, &r);
/*
* ISC_FALSE means absolute names have the final dot added.
*/
}
static void
if (parent) {
printf(" from ");
}
printf(")\n");
depth++;
printf("++ BEG down from ");
printf("\n");
printf("-- END down from ");
printf("\n");
}
} else
printf("NULL\n");
}
void
}
/*
* Chain Functions
*/
void
/*
* Initialize 'chain'.
*/
chain->ancestor_count = 0;
chain->level_count = 0;
}
if (chain->level_count == 0) {
/*
* Eliminate the root name, except when name is ".".
*/
/*
* XXX EVIL. But what _should_ I do?
*/
}
}
}
if (chain->level_count > 0)
else
}
return (result);
}
{
predecessor = NULL;
}
} else {
break;
}
}
}
if (predecessor != NULL) {
/*
* 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) {
/*
* Got to the root of this level without having traversed
* any right links. Ascend the tree one level.
*/
chain->ancestor_count--;
/* 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 (origin &&
}
if (predecessor != NULL) {
if (new_origin) {
NULL);
if (result == DNS_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 ||
}
/*
* 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
* ascents until either case is true.
*/
do {
NULL) {
current =
break;
}
}
/*
* Reached the root without having traversed
* any left pointers, so this level is done.
*/
chain->ancestor_count--;
break;
}
}
}
}
if (new_origin) {
if (result == DNS_R_SUCCESS)
} else
} else
return (result);
}
{
if (result == DNS_R_SUCCESS)
return (result);
}
{
if (result != DNS_R_SUCCESS)
return (result);
if (result == DNS_R_SUCCESS)
return (result);
}
void
/*
* Free any dynamic storage associated with 'chain', and then
* reinitialize 'chain'.
*/
chain->ancestor_count = 0;
chain->level_count = 0;
}
void
/*
* Free any dynamic storage associated with 'chain', and then
* invalidate 'chain'.
*/
}