/*
 * Copyright (C) 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/.
 *
 * See the COPYRIGHT file distributed with this work for additional
 * information regarding copyright ownership.
 */

/* ! \file */

#include <config.h>
#include <atf-c.h>
#include <isc/mem.h>
#include <isc/random.h>
#include <isc/string.h>
#include <fcntl.h>
#include <unistd.h>

#include <inttypes.h> /* uintptr_t */
#include <stdbool.h>

#include <dns/rbt.h>
#include <dns/fixedname.h>
#include <dns/name.h>
#include <dns/result.h>
#include <dns/compress.h>
#include "dnstest.h"

#include <isc/app.h>
#include <isc/buffer.h>
#include <isc/entropy.h>
#include <isc/file.h>
#include <isc/hash.h>
#include <isc/mem.h>
#include <isc/os.h>
#include <isc/string.h>
#include <isc/socket.h>
#include <isc/stdio.h>
#include <isc/task.h>
#include <isc/thread.h>
#include <isc/timer.h>
#include <isc/util.h>
#include <isc/print.h>
#include <isc/time.h>

#include <dns/log.h>
#include <dns/name.h>
#include <dns/result.h>

#include <dst/dst.h>

#include <ctype.h>
#include <stdlib.h>
#include <time.h>

typedef struct {
	dns_rbt_t *rbt;
	dns_rbt_t *rbt_distances;
} test_context_t;

/* The initial structure of domain tree will be as follows:
 *
 *	       .
 *	       |
 *	       b
 *	     /	 \
 *	    a	 d.e.f
 *		/  |   \
 *	       c   |	g.h
 *		   |	 |
 *		  w.y	 i
 *		/  |  \	  \
 *	       x   |   z   k
 *		   |   |
 *		   p   j
 *		 /   \
 *		o     q
 */

/* The full absolute names of the nodes in the tree (the tree also
 * contains "." which is not included in this list).
 */
static const char * const domain_names[] = {
    "c", "b", "a", "x.d.e.f", "z.d.e.f", "g.h", "i.g.h", "o.w.y.d.e.f",
    "j.z.d.e.f", "p.w.y.d.e.f", "q.w.y.d.e.f", "k.g.h"
};

static const size_t domain_names_count = (sizeof(domain_names) /
					  sizeof(domain_names[0]));

/* These are set as the node data for the tree used in distances check
 * (for the names in domain_names[] above).
 */
static const int node_distances[] = {
    3, 1, 2, 2, 2, 3, 1, 2, 1, 1, 2, 2
};

/*
 * The domain order should be:
 * ., a, b, c, d.e.f, x.d.e.f, w.y.d.e.f, o.w.y.d.e.f, p.w.y.d.e.f,
 * q.w.y.d.e.f, z.d.e.f, j.z.d.e.f, g.h, i.g.h, k.g.h
 *	       . (no data, can't be found)
 *	       |
 *	       b
 *	     /	 \
 *	    a	 d.e.f
 *		/  |   \
 *	       c   |	g.h
 *		   |	 |
 *		  w.y	 i
 *		/  |  \	  \
 *	       x   |   z   k
 *		   |   |
 *		   p   j
 *		 /   \
 *		o     q
 */

static const char * const ordered_names[] = {
    "a", "b", "c", "d.e.f", "x.d.e.f", "w.y.d.e.f", "o.w.y.d.e.f",
    "p.w.y.d.e.f", "q.w.y.d.e.f", "z.d.e.f", "j.z.d.e.f",
    "g.h", "i.g.h", "k.g.h"};

static const size_t ordered_names_count = (sizeof(ordered_names) /
					   sizeof(*ordered_names));

static void
delete_data(void *data, void *arg) {
	UNUSED(arg);

	isc_mem_put(mctx, data, sizeof(size_t));
}

static test_context_t *
test_context_setup(void) {
	test_context_t *ctx;
	isc_result_t result;
	size_t i;

	ctx = isc_mem_get(mctx, sizeof(*ctx));
	ATF_REQUIRE(ctx != NULL);

	ctx->rbt = NULL;
	result = dns_rbt_create(mctx, delete_data, NULL, &ctx->rbt);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

	ctx->rbt_distances = NULL;
	result = dns_rbt_create(mctx, delete_data, NULL, &ctx->rbt_distances);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

	for (i = 0; i < domain_names_count; i++) {
		size_t *n;
		dns_fixedname_t fname;
		dns_name_t *name;

		dns_test_namefromstring(domain_names[i], &fname);

		name = dns_fixedname_name(&fname);

		n = isc_mem_get(mctx, sizeof(size_t));
		ATF_REQUIRE(n != NULL);
		*n = i + 1;
		result = dns_rbt_addname(ctx->rbt, name, n);
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

		n = isc_mem_get(mctx, sizeof(size_t));
		ATF_REQUIRE(n != NULL);
		*n = node_distances[i];
		result = dns_rbt_addname(ctx->rbt_distances, name, n);
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
	}

	return (ctx);
}

static void
test_context_teardown(test_context_t *ctx) {
	dns_rbt_destroy(&ctx->rbt);
	dns_rbt_destroy(&ctx->rbt_distances);

	isc_mem_put(mctx, ctx, sizeof(*ctx));
}

/*
 * Walk the tree and ensure that all the test nodes are present.
 */
static void
check_test_data(dns_rbt_t *rbt) {
	dns_fixedname_t fixed;
	isc_result_t result;
	dns_name_t *foundname;
	size_t i;

	foundname = dns_fixedname_initname(&fixed);

	for (i = 0; i < domain_names_count; i++) {
		dns_fixedname_t fname;
		dns_name_t *name;
		size_t *n;

		dns_test_namefromstring(domain_names[i], &fname);

		name = dns_fixedname_name(&fname);
		n = NULL;
		result = dns_rbt_findname(rbt, name, 0, foundname,
					  (void *) &n);
		ATF_CHECK_EQ(result, ISC_R_SUCCESS);
		ATF_CHECK_EQ(*n, i + 1);
	}
}

ATF_TC(rbt_create);
ATF_TC_HEAD(rbt_create, tc) {
	atf_tc_set_md_var(tc, "descr", "Test the creation of an rbt");
}
ATF_TC_BODY(rbt_create, tc) {
	isc_result_t result;
	test_context_t *ctx;
	bool tree_ok;

	UNUSED(tc);

	isc_mem_debugging = ISC_MEM_DEBUGRECORD;

	result = dns_test_begin(NULL, true);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	ctx = test_context_setup();

	check_test_data(ctx->rbt);

	tree_ok = dns__rbt_checkproperties(ctx->rbt);
	ATF_CHECK_EQ(tree_ok, true);

	test_context_teardown(ctx);

	dns_test_end();
}

ATF_TC(rbt_nodecount);
ATF_TC_HEAD(rbt_nodecount, tc) {
	atf_tc_set_md_var(tc, "descr", "Test dns_rbt_nodecount() on a tree");
}
ATF_TC_BODY(rbt_nodecount, tc) {
	isc_result_t result;
	test_context_t *ctx;

	UNUSED(tc);

	isc_mem_debugging = ISC_MEM_DEBUGRECORD;

	result = dns_test_begin(NULL, true);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	ctx = test_context_setup();

	ATF_CHECK_EQ(15, dns_rbt_nodecount(ctx->rbt));

	test_context_teardown(ctx);

	dns_test_end();
}

ATF_TC(rbtnode_get_distance);
ATF_TC_HEAD(rbtnode_get_distance, tc) {
	atf_tc_set_md_var(tc, "descr",
			  "Test dns_rbtnode_get_distance() on a tree");
}
ATF_TC_BODY(rbtnode_get_distance, tc) {
	isc_result_t result;
	test_context_t *ctx;
	const char *name_str = "a";
	dns_fixedname_t fname;
	dns_name_t *name;
	dns_rbtnode_t *node = NULL;
	dns_rbtnodechain_t chain;

	UNUSED(tc);

	isc_mem_debugging = ISC_MEM_DEBUGRECORD;

	result = dns_test_begin(NULL, true);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	ctx = test_context_setup();

	dns_test_namefromstring(name_str, &fname);
	name = dns_fixedname_name(&fname);

	dns_rbtnodechain_init(&chain, mctx);

	result = dns_rbt_findnode(ctx->rbt_distances, name, NULL,
				  &node, &chain, 0, NULL, NULL);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	while (node != NULL) {
		const size_t *distance = (const size_t *) node->data;
		if (distance != NULL)
			ATF_CHECK_EQ(*distance,
				     dns__rbtnode_getdistance(node));
		result = dns_rbtnodechain_next(&chain, NULL, NULL);
		if (result == ISC_R_NOMORE)
		      break;
		dns_rbtnodechain_current(&chain, NULL, NULL, &node);
	}

	ATF_CHECK_EQ(result, ISC_R_NOMORE);

	dns_rbtnodechain_invalidate(&chain);

	test_context_teardown(ctx);

	dns_test_end();
}

ATF_TC(rbt_check_distance_random);
ATF_TC_HEAD(rbt_check_distance_random, tc) {
	atf_tc_set_md_var(tc, "descr",
			  "Test tree balance, inserting names in random order");
}
ATF_TC_BODY(rbt_check_distance_random, tc) {
	/* This test checks an important performance-related property of
	 * the red-black tree, which is important for us: the longest
	 * path from a sub-tree's root to a node is no more than
	 * 2log(n). This check verifies that the tree is balanced.
	 */
	dns_rbt_t *mytree = NULL;
	const unsigned int log_num_nodes = 16;

	int i;
	isc_result_t result;
	bool tree_ok;

	UNUSED(tc);

	isc_mem_debugging = ISC_MEM_DEBUGRECORD;

	result = dns_test_begin(NULL, true);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	result = dns_rbt_create(mctx, delete_data, NULL, &mytree);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

	/* Names are inserted in random order. */

	/* Make a large 65536 node top-level domain tree, i.e., the
	 * following code inserts names such as:
	 *
	 * savoucnsrkrqzpkqypbygwoiliawpbmz.
	 * wkadamcbbpjtundbxcmuayuycposvngx.
	 * wzbpznemtooxdpjecdxynsfztvnuyfao.
	 * yueojmhyffslpvfmgyfwioxegfhepnqq.
	 */
	for (i = 0; i < (1 << log_num_nodes); i++) {
		size_t *n;
		char namebuf[34];

		n = isc_mem_get(mctx, sizeof(size_t));
		ATF_REQUIRE(n != NULL);
		*n = i + 1;

		while (1) {
			int j;
			dns_fixedname_t fname;
			dns_name_t *name;

			for (j = 0; j < 32; j++) {
				uint32_t v;
				isc_random_get(&v);
				namebuf[j] = 'a' + (v % 26);
			}
			namebuf[32] = '.';
			namebuf[33] = 0;

			dns_test_namefromstring(namebuf, &fname);
			name = dns_fixedname_name(&fname);

			result = dns_rbt_addname(mytree, name, n);
			if (result == ISC_R_SUCCESS)
				break;
		}
	}

	/* 1 (root . node) + (1 << log_num_nodes) */
	ATF_CHECK_EQ(1U + (1U << log_num_nodes), dns_rbt_nodecount(mytree));

	/* The distance from each node to its sub-tree root must be less
	 * than 2 * log(n).
	 */
	ATF_CHECK((2U * log_num_nodes) >= dns__rbt_getheight(mytree));

	/* Also check RB tree properties */
	tree_ok = dns__rbt_checkproperties(mytree);
	ATF_CHECK_EQ(tree_ok, true);

	dns_rbt_destroy(&mytree);

	dns_test_end();
}

ATF_TC(rbt_check_distance_ordered);
ATF_TC_HEAD(rbt_check_distance_ordered, tc) {
	atf_tc_set_md_var(tc, "descr",
			  "Test tree balance, inserting names in sorted order");
}
ATF_TC_BODY(rbt_check_distance_ordered, tc) {
	/* This test checks an important performance-related property of
	 * the red-black tree, which is important for us: the longest
	 * path from a sub-tree's root to a node is no more than
	 * 2log(n). This check verifies that the tree is balanced.
	 */
	dns_rbt_t *mytree = NULL;
	const unsigned int log_num_nodes = 16;

	int i;
	isc_result_t result;
	bool tree_ok;

	UNUSED(tc);

	isc_mem_debugging = ISC_MEM_DEBUGRECORD;

	result = dns_test_begin(NULL, true);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	result = dns_rbt_create(mctx, delete_data, NULL, &mytree);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

	/* Names are inserted in sorted order. */

	/* Make a large 65536 node top-level domain tree, i.e., the
	 * following code inserts names such as:
	 *
	 *   name00000000.
	 *   name00000001.
	 *   name00000002.
	 *   name00000003.
	 */
	for (i = 0; i < (1 << log_num_nodes); i++) {
		size_t *n;
		char namebuf[14];
		dns_fixedname_t fname;
		dns_name_t *name;

		n = isc_mem_get(mctx, sizeof(size_t));
		ATF_REQUIRE(n != NULL);
		*n = i + 1;

		snprintf(namebuf, sizeof(namebuf), "name%08x.", i);
		dns_test_namefromstring(namebuf, &fname);
		name = dns_fixedname_name(&fname);

		result = dns_rbt_addname(mytree, name, n);
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
	}

	/* 1 (root . node) + (1 << log_num_nodes) */
	ATF_CHECK_EQ(1U + (1U << log_num_nodes), dns_rbt_nodecount(mytree));

	/* The distance from each node to its sub-tree root must be less
	 * than 2 * log(n).
	 */
	ATF_CHECK((2U * log_num_nodes) >= dns__rbt_getheight(mytree));

	/* Also check RB tree properties */
	tree_ok = dns__rbt_checkproperties(mytree);
	ATF_CHECK_EQ(tree_ok, true);

	dns_rbt_destroy(&mytree);

	dns_test_end();
}

static isc_result_t
insert_helper(dns_rbt_t *rbt, const char *namestr, dns_rbtnode_t **node) {
	dns_fixedname_t fname;
	dns_name_t *name;

	dns_test_namefromstring(namestr, &fname);
	name = dns_fixedname_name(&fname);

	return (dns_rbt_addnode(rbt, name, node));
}

static bool
compare_labelsequences(dns_rbtnode_t *node, const char *labelstr) {
	dns_name_t name;
	isc_result_t result;
	char *nodestr = NULL;
	bool is_equal;

	dns_name_init(&name, NULL);
	dns_rbt_namefromnode(node, &name);

	result = dns_name_tostring(&name, &nodestr, mctx);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

	is_equal = strcmp(labelstr, nodestr) == 0 ? true : false;

	isc_mem_free(mctx, nodestr);

	return (is_equal);
}

ATF_TC(rbt_insert);
ATF_TC_HEAD(rbt_insert, tc) {
	atf_tc_set_md_var(tc, "descr", "Test insertion into a tree");
}
ATF_TC_BODY(rbt_insert, tc) {
	isc_result_t result;
	test_context_t *ctx;
	dns_rbtnode_t *node;

	UNUSED(tc);

	isc_mem_debugging = ISC_MEM_DEBUGRECORD;

	result = dns_test_begin(NULL, true);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	ctx = test_context_setup();

	/* Check node count before beginning. */
	ATF_CHECK_EQ(15, dns_rbt_nodecount(ctx->rbt));

	/* Try to insert a node that already exists. */
	node = NULL;
	result = insert_helper(ctx->rbt, "d.e.f", &node);
	ATF_CHECK_EQ(result, ISC_R_EXISTS);

	/* Node count must not have changed. */
	ATF_CHECK_EQ(15, dns_rbt_nodecount(ctx->rbt));

	/* Try to insert a node that doesn't exist. */
	node = NULL;
	result = insert_helper(ctx->rbt, "0", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);
	ATF_CHECK_EQ(compare_labelsequences(node, "0"), true);

	/* Node count must have increased. */
	ATF_CHECK_EQ(16, dns_rbt_nodecount(ctx->rbt));

	/* Another. */
	node = NULL;
	result = insert_helper(ctx->rbt, "example.com", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);
	ATF_REQUIRE(node != NULL);
	ATF_CHECK_EQ(node->data, NULL);

	/* Node count must have increased. */
	ATF_CHECK_EQ(17, dns_rbt_nodecount(ctx->rbt));

	/* Re-adding it should return EXISTS */
	node = NULL;
	result = insert_helper(ctx->rbt, "example.com", &node);
	ATF_CHECK_EQ(result, ISC_R_EXISTS);

	/* Node count must not have changed. */
	ATF_CHECK_EQ(17, dns_rbt_nodecount(ctx->rbt));

	/* Fission the node d.e.f */
	node = NULL;
	result = insert_helper(ctx->rbt, "k.e.f", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);
	ATF_CHECK_EQ(compare_labelsequences(node, "k"), true);

	/* Node count must have incremented twice ("d.e.f" fissioned to
	 * "d" and "e.f", and the newly added "k").
	 */
	ATF_CHECK_EQ(19, dns_rbt_nodecount(ctx->rbt));

	/* Fission the node "g.h" */
	node = NULL;
	result = insert_helper(ctx->rbt, "h", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);
	ATF_CHECK_EQ(compare_labelsequences(node, "h"), true);

	/* Node count must have incremented ("g.h" fissioned to "g" and
	 * "h").
	 */
	ATF_CHECK_EQ(20, dns_rbt_nodecount(ctx->rbt));

	/* Add child domains */

	node = NULL;
	result = insert_helper(ctx->rbt, "m.p.w.y.d.e.f", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);
	ATF_CHECK_EQ(compare_labelsequences(node, "m"), true);
	ATF_CHECK_EQ(21, dns_rbt_nodecount(ctx->rbt));

	node = NULL;
	result = insert_helper(ctx->rbt, "n.p.w.y.d.e.f", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);
	ATF_CHECK_EQ(compare_labelsequences(node, "n"), true);
	ATF_CHECK_EQ(22, dns_rbt_nodecount(ctx->rbt));

	node = NULL;
	result = insert_helper(ctx->rbt, "l.a", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);
	ATF_CHECK_EQ(compare_labelsequences(node, "l"), true);
	ATF_CHECK_EQ(23, dns_rbt_nodecount(ctx->rbt));

	node = NULL;
	result = insert_helper(ctx->rbt, "r.d.e.f", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);
	node = NULL;
	result = insert_helper(ctx->rbt, "s.d.e.f", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);
	ATF_CHECK_EQ(25, dns_rbt_nodecount(ctx->rbt));

	node = NULL;
	result = insert_helper(ctx->rbt, "h.w.y.d.e.f", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	/* Add more nodes one by one to cover left and right rotation
	 * functions.
	 */
	node = NULL;
	result = insert_helper(ctx->rbt, "f", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	node = NULL;
	result = insert_helper(ctx->rbt, "m", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	node = NULL;
	result = insert_helper(ctx->rbt, "nm", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	node = NULL;
	result = insert_helper(ctx->rbt, "om", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	node = NULL;
	result = insert_helper(ctx->rbt, "k", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	node = NULL;
	result = insert_helper(ctx->rbt, "l", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	node = NULL;
	result = insert_helper(ctx->rbt, "fe", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	node = NULL;
	result = insert_helper(ctx->rbt, "ge", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	node = NULL;
	result = insert_helper(ctx->rbt, "i", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	node = NULL;
	result = insert_helper(ctx->rbt, "ae", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	node = NULL;
	result = insert_helper(ctx->rbt, "n", &node);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	test_context_teardown(ctx);

	dns_test_end();
}

ATF_TC(rbt_remove);
ATF_TC_HEAD(rbt_remove, tc) {
	atf_tc_set_md_var(tc, "descr", "Test removal from a tree");
}
ATF_TC_BODY(rbt_remove, tc) {
	/*
	 * This testcase checks that after node removal, the
	 * binary-search tree is valid and all nodes that are supposed
	 * to exist are present in the correct order. It mainly tests
	 * DomainTree as a BST, and not particularly as a red-black
	 * tree. This test checks node deletion when upper nodes have
	 * data.
	 */
	isc_result_t result;
	size_t j;

	UNUSED(tc);

	isc_mem_debugging = ISC_MEM_DEBUGRECORD;

	result = dns_test_begin(NULL, true);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

	/*
	 * Delete single nodes and check if the rest of the nodes exist.
	 */
	for (j = 0; j < ordered_names_count; j++) {
		dns_rbt_t *mytree = NULL;
		dns_rbtnode_t *node;
		size_t i;
		size_t *n;
		bool tree_ok;
		dns_rbtnodechain_t chain;
		size_t start_node;

		/* Create a tree. */
		result = dns_rbt_create(mctx, delete_data, NULL, &mytree);
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

		/* Insert test data into the tree. */
		for (i = 0; i < domain_names_count; i++) {
			node = NULL;
			result = insert_helper(mytree, domain_names[i], &node);
			ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
		}

		/* Check that all names exist in order. */
		for (i = 0; i < ordered_names_count; i++) {
			dns_fixedname_t fname;
			dns_name_t *name;

			dns_test_namefromstring(ordered_names[i], &fname);

			name = dns_fixedname_name(&fname);
			node = NULL;
			result = dns_rbt_findnode(mytree, name, NULL,
						  &node, NULL,
						  DNS_RBTFIND_EMPTYDATA,
						  NULL, NULL);
			ATF_CHECK_EQ(result, ISC_R_SUCCESS);

			/* Add node data */
			ATF_REQUIRE(node != NULL);
			ATF_REQUIRE_EQ(node->data, NULL);

			n = isc_mem_get(mctx, sizeof(size_t));
			ATF_REQUIRE(n != NULL);
			*n = i;

			node->data = n;
		}

		/* Now, delete the j'th node from the tree. */
		{
			dns_fixedname_t fname;
			dns_name_t *name;

			dns_test_namefromstring(ordered_names[j], &fname);

			name = dns_fixedname_name(&fname);

			result = dns_rbt_deletename(mytree, name, false);
			ATF_CHECK_EQ(result, ISC_R_SUCCESS);
		}

		/* Check RB tree properties. */
		tree_ok = dns__rbt_checkproperties(mytree);
		ATF_CHECK_EQ(tree_ok, true);

		dns_rbtnodechain_init(&chain, mctx);

		/* Now, walk through nodes in order. */
		if (j == 0) {
			/*
			 * Node for ordered_names[0] was already deleted
			 * above. We start from node 1.
			 */
			dns_fixedname_t fname;
			dns_name_t *name;

			dns_test_namefromstring(ordered_names[0], &fname);
			name = dns_fixedname_name(&fname);
			node = NULL;
			result = dns_rbt_findnode(mytree, name, NULL,
						  &node, NULL,
						  0,
						  NULL, NULL);
			ATF_CHECK_EQ(result, ISC_R_NOTFOUND);

			dns_test_namefromstring(ordered_names[1], &fname);
			name = dns_fixedname_name(&fname);
			node = NULL;
			result = dns_rbt_findnode(mytree, name, NULL,
						  &node, &chain,
						  0,
						  NULL, NULL);
			ATF_CHECK_EQ(result, ISC_R_SUCCESS);
			start_node = 1;
		} else {
			/* Start from node 0. */
			dns_fixedname_t fname;
			dns_name_t *name;

			dns_test_namefromstring(ordered_names[0], &fname);
			name = dns_fixedname_name(&fname);
			node = NULL;
			result = dns_rbt_findnode(mytree, name, NULL,
						  &node, &chain,
						  0,
						  NULL, NULL);
			ATF_CHECK_EQ(result, ISC_R_SUCCESS);
			start_node = 0;
		}

		/*
		 * node and chain have been set by the code above at
		 * this point.
		 */
		for (i = start_node; i < ordered_names_count; i++) {
			dns_fixedname_t fname_j, fname_i;
			dns_name_t *name_j, *name_i;

			dns_test_namefromstring(ordered_names[j], &fname_j);
			name_j = dns_fixedname_name(&fname_j);
			dns_test_namefromstring(ordered_names[i], &fname_i);
			name_i = dns_fixedname_name(&fname_i);

			if (dns_name_equal(name_i, name_j)) {
				/*
				 * This may be true for the last node if
				 * we seek ahead in the loop using
				 * dns_rbtnodechain_next() below.
				 */
				if (node == NULL) {
					break;
				}

				/* All ordered nodes have data
				 * initially. If any node is empty, it
				 * means it was removed, but an empty
				 * node exists because it is a
				 * super-domain. Just skip it.
				 */
				if (node->data == NULL) {
					result = dns_rbtnodechain_next(&chain,
								       NULL,
								       NULL);
					if (result == ISC_R_NOMORE) {
						node = NULL;
					} else {
						dns_rbtnodechain_current(&chain,
									 NULL,
									 NULL,
									 &node);
					}
				}
				continue;
			}

			ATF_REQUIRE(node != NULL);

			n = (size_t *) node->data;
			if (n != NULL) {
				/* printf("n=%zu, i=%zu\n", *n, i); */
				ATF_CHECK_EQ(*n, i);
			}

			result = dns_rbtnodechain_next(&chain, NULL, NULL);
			if (result == ISC_R_NOMORE) {
				node = NULL;
			} else {
				dns_rbtnodechain_current(&chain, NULL, NULL,
							 &node);
			}
		}

		/* We should have reached the end of the tree. */
		ATF_REQUIRE_EQ(node, NULL);

		dns_rbt_destroy(&mytree);
	}

	dns_test_end();
}

static void
insert_nodes(dns_rbt_t *mytree, char **names,
	     size_t *names_count, uint32_t num_names)
{
	uint32_t i;
	dns_rbtnode_t *node;

	for (i = 0; i < num_names; i++) {
		size_t *n;
		char namebuf[34];

		n = isc_mem_get(mctx, sizeof(size_t));
		ATF_REQUIRE(n != NULL);

		*n = i; /* Unused value */

		while (1) {
			int j;
			dns_fixedname_t fname;
			dns_name_t *name;
			isc_result_t result;

			for (j = 0; j < 32; j++) {
				uint32_t v;
				isc_random_get(&v);
				namebuf[j] = 'a' + (v % 26);
			}
			namebuf[32] = '.';
			namebuf[33] = 0;

			dns_test_namefromstring(namebuf, &fname);
			name = dns_fixedname_name(&fname);

			node = NULL;
			result = dns_rbt_addnode(mytree, name, &node);
			if (result == ISC_R_SUCCESS) {
				node->data = n;
				names[*names_count] = isc_mem_strdup(mctx,
								     namebuf);
				ATF_REQUIRE(names[*names_count] != NULL);
				*names_count += 1;
				break;
			}
		}
	}
}

static void
remove_nodes(dns_rbt_t *mytree, char **names,
	     size_t *names_count, uint32_t num_names)
{
	uint32_t i;

	UNUSED(mytree);

	for (i = 0; i < num_names; i++) {
		uint32_t node;
		dns_fixedname_t fname;
		dns_name_t *name;
		isc_result_t result;

		isc_random_get(&node);

		node %= *names_count;

		dns_test_namefromstring(names[node], &fname);
		name = dns_fixedname_name(&fname);

		result = dns_rbt_deletename(mytree, name, false);
		ATF_CHECK_EQ(result, ISC_R_SUCCESS);

		isc_mem_free(mctx, names[node]);
		if (*names_count > 0) {
			names[node] = names[*names_count - 1];
			names[*names_count - 1] = NULL;
			*names_count -= 1;
		}
	}
}

static void
check_tree(dns_rbt_t *mytree, char **names, size_t names_count,
	   unsigned int line)
{
	bool tree_ok;

	UNUSED(names);

	ATF_CHECK_EQ_MSG(names_count + 1, dns_rbt_nodecount(mytree),
			 "line:%u: %lu != %u", line,
			 (unsigned long)(names_count + 1),
			 dns_rbt_nodecount(mytree));

	/*
	 * The distance from each node to its sub-tree root must be less
	 * than 2 * log_2(1024).
	 */
	ATF_CHECK((2 * 10) >= dns__rbt_getheight(mytree));

	/* Also check RB tree properties */
	tree_ok = dns__rbt_checkproperties(mytree);
	ATF_CHECK_EQ(tree_ok, true);
}

ATF_TC(rbt_insert_and_remove);
ATF_TC_HEAD(rbt_insert_and_remove, tc) {
	atf_tc_set_md_var(tc, "descr",
			  "Test insert and remove in a loop");
}
ATF_TC_BODY(rbt_insert_and_remove, tc) {
	/*
	 * What is the best way to test our red-black tree code? It is
	 * not a good method to test every case handled in the actual
	 * code itself. This is because our approach itself may be
	 * incorrect.
	 *
	 * We test our code at the interface level here by exercising the
	 * tree randomly multiple times, checking that red-black tree
	 * properties are valid, and all the nodes that are supposed to be
	 * in the tree exist and are in order.
	 *
	 * NOTE: These tests are run within a single tree level in the
	 * forest. The number of nodes in the tree level doesn't grow
	 * over 1024.
	 */
	isc_result_t result;
	dns_rbt_t *mytree = NULL;
	size_t *n;
	/*
	 * We use an array for storing names instead of a set
	 * structure. It's slow, but works and is good enough for tests.
	 */
	char *names[1024];
	size_t names_count;
	int i;

	UNUSED(tc);

	isc_mem_debugging = ISC_MEM_DEBUGRECORD;

	result = dns_test_begin(NULL, true);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	result = dns_rbt_create(mctx, delete_data, NULL, &mytree);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

	n = isc_mem_get(mctx, sizeof(size_t));
	ATF_REQUIRE(n != NULL);
	result = dns_rbt_addname(mytree, dns_rootname, n);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

	memset(names, 0, sizeof(names));
	names_count = 0;

	/* Repeat the insert/remove test some 4096 times */
	for (i = 0; i < 4096; i++) {
		uint32_t num_names;
		isc_random_get(&num_names);

		if (names_count < 1024) {
			num_names %= 1024 - names_count;
			num_names++;
		} else {
			num_names = 0;
		}

		insert_nodes(mytree, names, &names_count, num_names);
		check_tree(mytree, names, names_count, __LINE__);

		isc_random_get(&num_names);
		if (names_count > 0) {
			num_names %= names_count;
			num_names++;
		} else {
			num_names = 0;
		}

		remove_nodes(mytree, names, &names_count, num_names);
		check_tree(mytree, names, names_count, __LINE__);
	}

	/* Remove the rest of the nodes */
	remove_nodes(mytree, names, &names_count, names_count);
	check_tree(mytree, names, names_count, __LINE__);

	for (i = 0; i < 1024; i++) {
		if (names[i] != NULL) {
			isc_mem_free(mctx, names[i]);
		}
	}

	result = dns_rbt_deletename(mytree, dns_rootname, false);
	ATF_CHECK_EQ_MSG(result, ISC_R_SUCCESS,
			 "result: %s", isc_result_totext(result));
	ATF_CHECK_EQ_MSG(dns_rbt_nodecount(mytree), 0,
			 "%u != 0", dns_rbt_nodecount(mytree));

	dns_rbt_destroy(&mytree);

	dns_test_end();
}

ATF_TC(rbt_findname);
ATF_TC_HEAD(rbt_findname, tc) {
	atf_tc_set_md_var(tc, "descr", "findname return values");
}
ATF_TC_BODY(rbt_findname, tc) {
	isc_result_t result;
	test_context_t *ctx = NULL;
	dns_fixedname_t fname, found;
	dns_name_t *name = NULL, *foundname = NULL;
	size_t *n = NULL;

	UNUSED(tc);

	isc_mem_debugging = ISC_MEM_DEBUGRECORD;

	result = dns_test_begin(NULL, true);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	ctx = test_context_setup();

	/* Try to find a name that exists. */
	dns_test_namefromstring("d.e.f", &fname);
	name = dns_fixedname_name(&fname);

	foundname = dns_fixedname_initname(&found);

	result = dns_rbt_findname(ctx->rbt, name,
				  DNS_RBTFIND_EMPTYDATA,
				  foundname, (void *) &n);
	ATF_CHECK(dns_name_equal(foundname, name));
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	/* Now without EMPTYDATA */
	result = dns_rbt_findname(ctx->rbt, name, 0,
				  foundname, (void *) &n);
	ATF_CHECK_EQ(result, ISC_R_NOTFOUND);

	/* Now one that partially matches */
	dns_test_namefromstring("d.e.f.g.h.i.j", &fname);
	name = dns_fixedname_name(&fname);
	result = dns_rbt_findname(ctx->rbt, name,
				  DNS_RBTFIND_EMPTYDATA,
				  foundname, (void *) &n);
	ATF_CHECK_EQ(result, DNS_R_PARTIALMATCH);

	/* Now one that doesn't match */
	dns_test_namefromstring("1.2", &fname);
	name = dns_fixedname_name(&fname);
	result = dns_rbt_findname(ctx->rbt, name,
				  DNS_RBTFIND_EMPTYDATA,
				  foundname, (void *) &n);
	ATF_CHECK_EQ(result, DNS_R_PARTIALMATCH);
	ATF_CHECK(dns_name_equal(foundname, dns_rootname));

	test_context_teardown(ctx);

	dns_test_end();
}

ATF_TC(rbt_addname);
ATF_TC_HEAD(rbt_addname, tc) {
	atf_tc_set_md_var(tc, "descr", "addname return values");
}
ATF_TC_BODY(rbt_addname, tc) {
	isc_result_t result;
	test_context_t *ctx = NULL;
	dns_fixedname_t fname;
	dns_name_t *name = NULL;
	size_t *n;

	UNUSED(tc);

	isc_mem_debugging = ISC_MEM_DEBUGRECORD;

	result = dns_test_begin(NULL, true);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	ctx = test_context_setup();

	n = isc_mem_get(mctx, sizeof(size_t));
	ATF_REQUIRE(n != NULL);
	*n = 1;

	dns_test_namefromstring("d.e.f.g.h.i.j.k", &fname);
	name = dns_fixedname_name(&fname);

	/* Add a name that doesn't exist */
	result = dns_rbt_addname(ctx->rbt, name, n);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

	/* Now add again, should get ISC_R_EXISTS */
	n = isc_mem_get(mctx, sizeof(size_t));
	ATF_REQUIRE(n != NULL);
	*n = 2;
	result = dns_rbt_addname(ctx->rbt, name, n);
	ATF_REQUIRE_EQ(result, ISC_R_EXISTS);
	isc_mem_put(mctx, n, sizeof(size_t));

	test_context_teardown(ctx);

	dns_test_end();
}

ATF_TC(rbt_deletename);
ATF_TC_HEAD(rbt_deletename, tc) {
	atf_tc_set_md_var(tc, "descr", "deletename return values");
}
ATF_TC_BODY(rbt_deletename, tc) {
	isc_result_t result;
	test_context_t *ctx = NULL;
	dns_fixedname_t fname;
	dns_name_t *name = NULL;

	UNUSED(tc);

	isc_mem_debugging = ISC_MEM_DEBUGRECORD;

	result = dns_test_begin(NULL, true);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	ctx = test_context_setup();

	/* Delete a name that doesn't exist */
	dns_test_namefromstring("z.x.y.w", &fname);
	name = dns_fixedname_name(&fname);
	result = dns_rbt_deletename(ctx->rbt, name, false);
	ATF_REQUIRE_EQ(result, ISC_R_NOTFOUND);

	/* Now one that does */
	dns_test_namefromstring("d.e.f", &fname);
	name = dns_fixedname_name(&fname);
	result = dns_rbt_deletename(ctx->rbt, name, false);
	ATF_REQUIRE_EQ(result, ISC_R_NOTFOUND);

	test_context_teardown(ctx);

	dns_test_end();
}

ATF_TC(rbt_nodechain);
ATF_TC_HEAD(rbt_nodechain, tc) {
	atf_tc_set_md_var(tc, "descr", "nodechain");
}
ATF_TC_BODY(rbt_nodechain, tc) {
	isc_result_t result;
	test_context_t *ctx;
	dns_fixedname_t fname, found, expect;
	dns_name_t *name, *foundname, *expected;
	dns_rbtnode_t *node = NULL;
	dns_rbtnodechain_t chain;

	UNUSED(tc);

	isc_mem_debugging = ISC_MEM_DEBUGRECORD;

	result = dns_test_begin(NULL, true);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	ctx = test_context_setup();

	dns_rbtnodechain_init(&chain, mctx);

	dns_test_namefromstring("a", &fname);
	name = dns_fixedname_name(&fname);

	result = dns_rbt_findnode(ctx->rbt, name, NULL,
				  &node, &chain, 0, NULL, NULL);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	foundname = dns_fixedname_initname(&found);

	dns_test_namefromstring("a", &expect);
	expected = dns_fixedname_name(&expect);
	UNUSED(expected);

	result = dns_rbtnodechain_first(&chain, ctx->rbt, foundname, NULL);
	ATF_CHECK_EQ(result, DNS_R_NEWORIGIN);
	ATF_CHECK_EQ(dns_name_countlabels(foundname), 0);

	result = dns_rbtnodechain_prev(&chain, NULL, NULL);
	ATF_CHECK_EQ(result, ISC_R_NOMORE);

	result = dns_rbtnodechain_next(&chain, NULL, NULL);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	result = dns_rbtnodechain_next(&chain, NULL, NULL);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	result = dns_rbtnodechain_last(&chain, ctx->rbt, NULL, NULL);
	ATF_CHECK_EQ(result, DNS_R_NEWORIGIN);

	result = dns_rbtnodechain_next(&chain, NULL, NULL);
	ATF_CHECK_EQ(result, ISC_R_NOMORE);

	result = dns_rbtnodechain_last(&chain, ctx->rbt, NULL, NULL);
	ATF_CHECK_EQ(result, DNS_R_NEWORIGIN);

	result = dns_rbtnodechain_prev(&chain, NULL, NULL);
	ATF_CHECK_EQ(result, ISC_R_SUCCESS);

	dns_rbtnodechain_invalidate(&chain);

	test_context_teardown(ctx);

	dns_test_end();
}

#ifdef ISC_PLATFORM_USETHREADS
#ifdef DNS_BENCHMARK_TESTS

/*
 * XXXMUKS: Don't delete this code. It is useful in benchmarking the
 * RBT, but we don't require it as part of the unit test runs.
 */

ATF_TC(benchmark);
ATF_TC_HEAD(benchmark, tc) {
	atf_tc_set_md_var(tc, "descr", "Benchmark RBT implementation");
}

static dns_fixedname_t *fnames;
static dns_name_t **names;
static int *values;

static void *
find_thread(void *arg) {
	dns_rbt_t *mytree;
	isc_result_t result;
	dns_rbtnode_t *node;
	unsigned int j, i;
	unsigned int start = 0;

	mytree = (dns_rbt_t *) arg;
	while (start == 0)
		start = random() % 4000000;

	/* Query 32 million random names from it in each thread */
	for (j = 0; j < 8; j++) {
		for (i = start; i != start - 1; i = (i + 1) % 4000000) {
			node = NULL;
			result = dns_rbt_findnode(mytree, names[i], NULL,
						  &node, NULL,
						  DNS_RBTFIND_EMPTYDATA,
						  NULL, NULL);
			ATF_CHECK_EQ(result, ISC_R_SUCCESS);
			ATF_REQUIRE(node != NULL);
			ATF_CHECK_EQ(values[i], (intptr_t) node->data);
		}
	}

	return (NULL);
}

ATF_TC_BODY(benchmark, tc) {
	isc_result_t result;
	char namestr[sizeof("name18446744073709551616.example.org.")];
	unsigned int r;
	dns_rbt_t *mytree;
	dns_rbtnode_t *node;
	unsigned int i;
	unsigned int maxvalue = 1000000;
	isc_time_t ts1, ts2;
	double t;
	unsigned int nthreads;
	isc_thread_t threads[32];

	UNUSED(tc);

	srandom(time(NULL));

	debug_mem_record = false;

	result = dns_test_begin(NULL, true);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

	fnames = (dns_fixedname_t *) malloc(4000000 * sizeof(dns_fixedname_t));
	names = (dns_name_t **) malloc(4000000 * sizeof(dns_name_t *));
	values = (int *) malloc(4000000 * sizeof(int));

	for (i = 0; i < 4000000; i++) {
		  r = ((unsigned long) random()) % maxvalue;
		  snprintf(namestr, sizeof(namestr), "name%u.example.org.", r);
		  dns_test_namefromstring(namestr, &fnames[i]);
		  names[i] = dns_fixedname_name(&fnames[i]);
		  values[i] = r;
	}

	/* Create a tree. */
	mytree = NULL;
	result = dns_rbt_create(mctx, NULL, NULL, &mytree);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

	/* Insert test data into the tree. */
	for (i = 0; i < maxvalue; i++) {
		snprintf(namestr, sizeof(namestr), "name%u.example.org.", i);
		node = NULL;
		result = insert_helper(mytree, namestr, &node);
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
		node->data = (void *) (intptr_t) i;
	}

	result = isc_time_now(&ts1);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

	nthreads = ISC_MIN(isc_os_ncpus(), 32);
	nthreads = ISC_MAX(nthreads, 1);
	for (i = 0; i < nthreads; i++) {
		result = isc_thread_create(find_thread, mytree, &threads[i]);
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
	}

	for (i = 0; i < nthreads; i++) {
		result = isc_thread_join(threads[i], NULL);
		ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
	}

	result = isc_time_now(&ts2);
	ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);

	t = isc_time_microdiff(&ts2, &ts1);

	printf("%u findnode calls, %f seconds, %f calls/second\n",
	       nthreads * 8 * 4000000, t / 1000000.0,
	       (nthreads * 8 * 4000000) / (t / 1000000.0));

	free(values);
	free(names);
	free(fnames);

	dns_rbt_destroy(&mytree);

	dns_test_end();
}

#endif /* DNS_BENCHMARK_TESTS */
#endif /* ISC_PLATFORM_USETHREADS */

/*
 * Main
 */
ATF_TP_ADD_TCS(tp) {
	ATF_TP_ADD_TC(tp, rbt_create);
	ATF_TP_ADD_TC(tp, rbt_nodecount);
	ATF_TP_ADD_TC(tp, rbtnode_get_distance);
	ATF_TP_ADD_TC(tp, rbt_check_distance_random);
	ATF_TP_ADD_TC(tp, rbt_check_distance_ordered);
	ATF_TP_ADD_TC(tp, rbt_insert);
	ATF_TP_ADD_TC(tp, rbt_remove);
	ATF_TP_ADD_TC(tp, rbt_insert_and_remove);
	ATF_TP_ADD_TC(tp, rbt_findname);
	ATF_TP_ADD_TC(tp, rbt_addname);
	ATF_TP_ADD_TC(tp, rbt_deletename);
	ATF_TP_ADD_TC(tp, rbt_nodechain);
#ifdef ISC_PLATFORM_USETHREADS
#ifdef DNS_BENCHMARK_TESTS
	ATF_TP_ADD_TC(tp, benchmark);
#endif /* DNS_BENCHMARK_TESTS */
#endif /* ISC_PLATFORM_USETHREADS */

	return (atf_no_error());
}