rbt.c revision 40f53fa8d9c6a4fc38c0014495e7a42b08f52481
* 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. * 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. * A little something to help out in GDB. * 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. * 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. * Go as far right and then down as much as possible, * as long as the rightmost node has a down pointer. * Add 'name' to tree, initializing its data pointer with 'data'. * Does this thing have too many variables or what? * Create a copy of the name so the original name structure is * not modified. The name data needs to be modifiable when * a node is split on a bitstring label. * 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 * 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 * Follow the down pointer (possibly NULL). * 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. * 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? * 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 * Reproduce the tree attributes of the * Fix pointers that were to the current node. * Now make 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. * 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. * When bitstring labels are involved, things * are just a tad more complicated (aren't * they always?) because the splitting * has shifted the bits that this name needs, * as well as adjusted the bit count. * So there are convolutions to deal with it. * There are compromises here between * abstraction and efficiency. * Set up the new root of the next level. * By definition it will not be the top * level tree, so clear DNS_NAMEATTR_ABSOLUTE. * The name has been added by pushing * the not-in-common parts down to * 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 but add it to * the ancestor chain, because it will * be the parent node of the new node. /* 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). * 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. * Find the node for "name" in the tree of trees. * 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 * search_name is the name segment being sought in each tree level. * By using a fixedname, the search_name will definitely have offsets * and a buffer for use by any splitting that happens in the middle * of a bitstring label. By using dns_name_clone, no name data is * copied unless a bitstring split occurs. * Standard binary search tree movement. * 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. * Whack off the current node's common parts * for the name to search in the next level. * This might be the closest enclosing name. * 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 * 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 * Treat this node as if it * Finally, head to the next tree level. * 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. * Add this node to the ancestor chain * to simplify things for the chain fixing * logic below then end the loop. * 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. * 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. * 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. * Ensure the chain points nowhere. * Since there was no exact match, the chain argument * needs to be pointed at the DNSSEC predecessor of * First, point current to the node that stopped the * search, and remove that node from the ancestor * 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 * 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 * Ah, the pure and simple * case. The stop node is the * There is no predecessor. * Get the data pointer associated with 'name'. * Delete a name from the tree of trees. * 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 * Remove a node from the tree of trees and rejoin any levels, if possible. * 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. * There is a down pointer to a level with a single * item. That item's name can be joined with the name * 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 * 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. * 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, to the node that points to the level of the deleted node. * Allocate space for the node structure, the name, and the offsets. * 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. * The offsets table could be made smaller by eliminating the * first offset, which is always 0. This requires changes to * 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. * Fix the pointers to the original node. * This is the real workhorse of the insertion code, because it does the * true red/black tree on a single level. * This is the real workhorse of the deletion code, because it does the * true red/black tree on a single level. * Verify that the parent history is (apparently) correct. * This is the only item in the tree. * This node has one child, on the right. * This node has one child, on the left. * 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. * 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. * Original location of successor node has no left. * Remove the node by removing the links from its parent. * This is the root being deleted, and at this point * it is known to have just one child. * Child is parent's right child. * Everything is doen the same as above, * This should only be used on the root of a tree, because no color fixup * NOTE: No root pointer maintenance is done, because the function is only * + 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. for (i = 0; i <
depth; i++)
* ISC_FALSE means absolute names have the final dot added. printf(
" (BAD parent pointer! -> ");
* Names in the top level tree are all absolute. * Always make 'name' relative. * This is cheaper than dns_name_getlabelsequence(). * 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. * 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 /* XXX DCL duplicated from above; clever /* XXX DCL probably needs work on the concept */ * Got to the root of this level without having traversed * any right links. Ascend the tree one level. /* 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. * 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. * 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. * Reached the root without having traversed * any left pointers, so this level is done. * 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. * Free any dynamic storage associated with 'chain', and then * Free any dynamic storage associated with 'chain', and then