rbt.c

bind-3.2.

				    (sizeof(chain.levels) /
				     sizeof(*chain.levels))) {
					result = ISC_R_NOSPACE;
					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.
				 */
				result = dns_name_split(&current_name,
							common_labels,
							common_bits,
							prefix, suffix);

				if (result == ISC_R_SUCCESS)
					result = create_node(rbt->mctx, suffix,
							     &new_current);

				if (result != ISC_R_SUCCESS)
					break;

				/*
				 * Reproduce the tree attributes of the
				 * current node.
				 */
				new_current->is_root = current->is_root;
				PARENT(new_current)  = PARENT(current);
				LEFT(new_current)    = LEFT(current);
				RIGHT(new_current)   = RIGHT(current);
				COLOR(new_current)   = COLOR(current);

				/*
				 * Fix pointers that were to the current node.
				 */
				if (parent != NULL) {
					if (LEFT(parent) == current)
						LEFT(parent) = new_current;
					else
						RIGHT(parent) = new_current;
				}
				if (LEFT(new_current) != NULL)
					PARENT(LEFT(new_current)) =
						new_current;
				if (RIGHT(new_current) != NULL)
					PARENT(RIGHT(new_current)) =
						new_current;
				if (*root == current)
					*root = new_current;

				/*
				 * 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
				 * from the end of the label they were in
				 * to either the beginning of the label or
				 * even to the previous (lesser significance)
				 * label if the split was done in a maximally
				 * sized bitstring label.  The bit count has
				 * been adjusted too, so there are convolutions
				 * to deal with all the bit movement.  Yay,
				 * I *love* bit labels.  Grumble grumble.
				 */
				if (common_bits > 0) {
					unsigned char *p;
					unsigned int skip_width;
					unsigned int start_label =
					    dns_name_countlabels(&current_name)
						- common_labels;

					/*
					 * If it is not the first label which
					 * was split, also copy the label
					 * before it -- which will essentially
					 * be a NO-OP unless the preceding
					 * label is a bitstring and the split
					 * label was 256 bits.  Testing for
					 * that case is probably roughly
					 * as expensive as just unconditionally
					 * copying the preceding label.
					 */
					if (start_label > 0)
						start_label--;

					skip_width =
						prefix->offsets[start_label];

					memcpy(NAME(current) + skip_width,
					       prefix->ndata + skip_width,
					       prefix->length - skip_width);

					/*
					 * Now add_bits is set to the total
					 * number of bits in the split label of
					 * the name being added, and used later
					 * to determine if the job was
					 * completed by pushing the
					 * not-in-common bits down one level.
					 */
					start_label =
						dns_name_countlabels(add_name)
						- common_labels;

					p = add_name->ndata +
						add_name->offsets[start_label];
					INSIST(*p == DNS_LABELTYPE_BITSTRING);

					add_bits = *(p + 1);

					/*
					 * A bitstring that was split would not
					 * result in a part of maximal length.
					 */
					INSIST(add_bits != 0);
				} else
					add_bits = 0;

				NAMELEN(current) = prefix->length;
				OFFSETLEN(current) = prefix->labels;
				memcpy(OFFSETS(current), prefix->offsets,
				       prefix->labels);
				PADBYTES(current) +=
				       (current_name.length - prefix->length) +
				       (current_name.labels - prefix->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.
				 */
				current->is_root = 1;
				PARENT(current) = new_current;
				DOWN(new_current) = current;
				root = &DOWN(new_current);

				ADD_LEVEL(&chain, new_current);

				LEFT(current) = NULL;
				RIGHT(current) = NULL;

				MAKE_BLACK(current);
				ATTRS(current) &= ~DNS_NAMEATTR_ABSOLUTE;

				rbt->nodecount++;
				result = hash_node(rbt, new_current);
				if (result != ISC_R_SUCCESS)
					break;

				if (common_labels ==
				    dns_name_countlabels(add_name) &&
				    common_bits == add_bits) {
					/*
					 * 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).
					 */
					result = dns_name_split(add_name,
								common_labels,
								common_bits,
								add_name,
								NULL);


					break;
				}

			}

		}

	} while (child != NULL);

	if (result == ISC_R_SUCCESS)
		result = create_node(rbt->mctx, add_name, &new_current);

	if (result == ISC_R_SUCCESS) {
		dns_rbt_addonlevel(new_current, current, order, root);
		rbt->nodecount++;
		*nodep = new_current;
		result = hash_node(rbt, new_current);
		/*
		 * XXXDCL Ugh.  If hash_node failed, it was because
		 * there is not enough memory.  The node is now unfindable,
		 * and ideally should be removed.  This is kind of tricky,
		 * and all hell is probably going to break loose throughout
		 * the rest of the library because of the lack of memory,
		 * so fixing up the tree as though no addition had been
		 * made is skipped.  (Actually, this hash_node failing is
		 * not the only situation in this file where an unexpected
		 * error can leave things in an incorrect state.)
		 */
	}

	return (result);
}

/*
 * Add a name to the tree of trees, associating it with some data.
 */
isc_result_t
dns_rbt_addname(dns_rbt_t *rbt, dns_name_t *name, void *data) {
	isc_result_t result;
	dns_rbtnode_t *node;

	REQUIRE(VALID_RBT(rbt));
	REQUIRE(dns_name_isabsolute(name));

	node = NULL;

	result = dns_rbt_addnode(rbt, name, &node);

	/*
	 * 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 ||
	    (result == ISC_R_EXISTS && DATA(node) == NULL)) {
		DATA(node) = data;
		result = ISC_R_SUCCESS;
	}

	return (result);
}

/*
 * Find the node for "name" in the tree of trees.
 */
isc_result_t
dns_rbt_findnode(dns_rbt_t *rbt, dns_name_t *name, dns_name_t *foundname,
		 dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
		 unsigned int options, dns_rbtfindcallback_t callback,
		 void *callback_arg)
{
	dns_rbtnode_t *current, *last_compared, *current_root;
	dns_rbtnodechain_t localchain;
	dns_name_t *search_name, current_name, *callback_name;
	dns_fixedname_t fixedcallbackname, fixedsearchname;
	dns_namereln_t compared;
	isc_result_t result, saved_result;
	unsigned int common_labels, common_bits;
	int order;

	REQUIRE(VALID_RBT(rbt));
	REQUIRE(dns_name_isabsolute(name));
	REQUIRE(node != NULL && *node == NULL);
	REQUIRE((options & (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR))
		!=         (DNS_RBTFIND_NOEXACT | DNS_RBTFIND_NOPREDECESSOR));

	/*
	 * 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.
	 */
	if (chain == NULL) {
		options |= DNS_RBTFIND_NOPREDECESSOR;
		chain = &localchain;
		dns_rbtnodechain_init(chain, rbt->mctx);
	} else
		dns_rbtnodechain_reset(chain);

	if (rbt->root == NULL)
		return (ISC_R_NOTFOUND);
	else {
		/*
		 * Appease GCC about variables it incorrectly thinks are
		 * possibly used unitialized.
		 */
		compared = dns_namereln_none;
		last_compared = NULL;
	}

	dns_fixedname_init(&fixedcallbackname);
	callback_name = dns_fixedname_name(&fixedcallbackname);

	/*
	 * 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.
	 */
	dns_fixedname_init(&fixedsearchname);
	search_name = dns_fixedname_name(&fixedsearchname);
	dns_name_clone(name, search_name);

	dns_name_init(&current_name, NULL);

	saved_result = ISC_R_SUCCESS;
	current = rbt->root;
	current_root = rbt->root;

	while (current != NULL) {
		NODENAME(current, &current_name);
		compared = dns_name_fullcompare(search_name, &current_name,
						&order,
						&common_labels, &common_bits);
		last_compared = current;

		if (compared == dns_namereln_equal)
			break;

		if (compared == dns_namereln_none) {
#ifdef DNS_RBT_USEHASH
			dns_name_t hash_name;
			dns_rbtnode_t *hnode;
			dns_rbtnode_t *up_current;
			unsigned int nlabels;
			unsigned int tlabels = 1;
			unsigned int hash;
			isc_boolean_t has_bitstring = ISC_FALSE;

			/*
			 * If there is no hash table, hashing can't be done.
			 * Similarly, when current != current_root, that
			 * means a left or right pointer was followed, which
			 * only happens when the algorithm fell through to
			 * the traditional binary search because of a
			 * bitstring label, so that traditional search
			 * should be continued.
			 */
			if (rbt->hashtable == NULL ||
			    current != current_root)
				goto nohash;

			nlabels = dns_name_countlabels(search_name);

			/*
			 * current_root is the root of the current level, so
			 * it's parent is the same as it's "up" pointer.
			 */
			up_current = PARENT(current_root);
			dns_name_init(&hash_name, NULL);

		hashagain:
			dns_name_getlabelsequence(search_name,
						  nlabels - tlabels,
						  tlabels, &hash_name);
			hash = HASHVAL(up_current) + name_hash(&hash_name);

			for (hnode = rbt->hashtable[hash % rbt->hashsize];
			     hnode != NULL;
			     hnode = hnode->hashnext)
			{
				dns_name_t hnode_name;

				if (hash != HASHVAL(hnode))
					continue;
				if (find_up(hnode) != up_current)
					continue;
				dns_name_init(&hnode_name, NULL);
				NODENAME(hnode, &hnode_name);
				if (dns_name_equal(&hnode_name, &hash_name))
					break;
			}

			if (hnode != NULL) {
				current = hnode;
				/*
				 * 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.
				 */
				if (tlabels == nlabels) {
					compared = dns_namereln_equal;
					break;
				} else {
					common_labels = tlabels;
					common_bits = 0;
					compared = dns_namereln_subdomain;
					goto subdomain;
				}
			}

			/*
			 * XXXDCL Bitstring labels complicate things, as usual.
			 * Checking for the situation could be done up by the
			 * dns_name_getlabelsequence so that they could still
			 * use the hashing code, but it would be messy to
			 * repeatedly try various bitstring lengths.  Instead
			 * just notice when a bitstring label is involved and
			 * then punt to the traditional binary search if no
			 * hash node is found after all of the labels are
			 * tried.
			 */
			if (has_bitstring == ISC_FALSE &&
			    hash_name.ndata[0] ==
			    DNS_LABELTYPE_BITSTRING)
				has_bitstring = ISC_TRUE;

			if (tlabels++ < nlabels)
				goto hashagain;

			/*
			 * All of the labels have been tried against the hash
			 * table.  If there wasn't a bitstring label involved,
			 * the name isn't in the table.  If there was, fall
			 * through to the traditional search algorithm.
			 */
			if (! has_bitstring) {
				/*
				 * Done with the search.
				 */
				current = NULL;
				continue;
			}
			    
			/* FALLTHROUGH */
		nohash:
#endif /* DNS_RBT_USEHASH */
			/*
			 * Standard binary search tree movement.
			 */
			if (order < 0)
				current = LEFT(current);
			else
				current = RIGHT(current);

		} 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) {
		subdomain:
				/*
				 * Whack off the current node's common parts
				 * for the name to search in the next level.
				 */
				result = dns_name_split(search_name,
							common_labels,
							common_bits,
							search_name, NULL);
				if (result != ISC_R_SUCCESS) {
					dns_rbtnodechain_reset(chain);
					return (result);
				}

				/*
				 * This might be the closest enclosing name.
				 */
				if (DATA(current) != NULL ||
				    (options & DNS_RBTFIND_EMPTYDATA) != 0)
					*node = current;

				/*
				 * 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.
				 */
				ADD_LEVEL(chain, current);

				/*
				 * 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.
				 */
				if (callback != NULL &&