/*
* Copyright (C) 2012-2017 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/.
*/
/* $Id: rbt_test.c,v 1.1.14.8 2012/02/10 16:24:37 ckb Exp $ */
/* ! \file */
#include <config.h>
#include <atf-c.h>
#include <fcntl.h>
#include <unistd.h>
#ifdef HAVE_INTTYPES_H
#include <inttypes.h> /* uintptr_t */
#endif
#include <dns/fixedname.h>
#include <dns/compress.h>
#include "dnstest.h"
#include <ctype.h>
#include <stdlib.h>
#include <time.h>
typedef struct {
/* 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[] = {
};
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,
* . (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",
sizeof(*ordered_names));
static void
}
static void
isc_buffer_t *b = NULL;
isc_buffer_free(&b);
}
static test_context_t *
test_context_setup(void) {
size_t i;
for (i = 0; i < domain_names_count; i++) {
size_t *n;
*n = i + 1;
*n = node_distances[i];
}
return (ctx);
}
static void
}
/*
* Walk the tree and ensure that all the test nodes are present.
*/
static void
size_t i;
for (i = 0; i < domain_names_count; i++) {
size_t *n;
n = NULL;
(void *) &n);
ATF_CHECK_EQ(*n, i + 1);
}
}
}
ctx = test_context_setup();
dns_test_end();
}
}
ctx = test_context_setup();
dns_test_end();
}
"Test dns_rbtnode_get_distance() on a tree");
}
ctx = test_context_setup();
if (result == ISC_R_NOMORE)
break;
}
dns_test_end();
}
"Test tree balance, inserting names in random order");
}
/* 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.
*/
int i;
/* 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;
*n = i + 1;
while (1) {
int j;
for (j = 0; j < 32; j++) {
isc_uint32_t v;
isc_random_get(&v);
}
namebuf[33] = 0;
if (result == ISC_R_SUCCESS)
break;
}
}
/* 1 (root . node) + (1 << log_num_nodes) */
/* The distance from each node to its sub-tree root must be less
* than 2 * log(n).
*/
/* Also check RB tree properties */
dns_test_end();
}
"Test tree balance, inserting names in sorted order");
}
/* 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.
*/
int i;
/* 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;
*n = i + 1;
}
/* 1 (root . node) + (1 << log_num_nodes) */
/* The distance from each node to its sub-tree root must be less
* than 2 * log(n).
*/
/* Also check RB tree properties */
dns_test_end();
}
static isc_result_t
}
static isc_boolean_t
return (is_equal);
}
}
ctx = test_context_setup();
/* Check node count before beginning. */
/* Try to insert a node that already exists. */
/* Node count must not have changed. */
/* Try to insert a node that doesn't exist. */
/* Node count must have increased. */
/* Another. */
/* Node count must have increased. */
/* Re-adding it should return EXISTS */
/* Node count must not have changed. */
/* Fission the node d.e.f */
/* Node count must have incremented twice ("d.e.f" fissioned to
* "d" and "e.f", and the newly added "k").
*/
/* Fission the node "g.h" */
/* Node count must have incremented ("g.h" fissioned to "g" and
* "h").
*/
/* Add child domains */
/* Add more nodes one by one to cover left and right rotation
* functions.
*/
dns_test_end();
}
}
/*
* 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.
*/
size_t j;
/*
* Delete single nodes and check if the rest of the nodes exist.
*/
for (j = 0; j < ordered_names_count; j++) {
size_t i;
size_t *n;
/* Create a tree. */
/* Insert test data into the tree. */
for (i = 0; i < domain_names_count; i++) {
}
/* Check that all names exist in order. */
for (i = 0; i < ordered_names_count; i++) {
/* Add node data */
*n = i;
}
/* Now, delete the j'th node from the tree. */
{
}
/* Check RB tree properties. */
/* Now, walk through nodes in order. */
if (j == 0) {
/*
* Node for ordered_names[0] was already deleted
* above. We start from node 1.
*/
0,
0,
start_node = 1;
} else {
/* Start from node 0. */
0,
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++) {
/*
* This may be true for the last node if
* we seek ahead in the loop using
* dns_rbtnodechain_next() below.
*/
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.
*/
NULL,
NULL);
if (result == ISC_R_NOMORE) {
} else {
NULL,
NULL,
&node);
}
}
continue;
}
if (n != NULL) {
/* printf("n=%zu, i=%zu\n", *n, i); */
ATF_CHECK_EQ(*n, i);
}
if (result == ISC_R_NOMORE) {
} else {
&node);
}
}
/* We should have reached the end of the tree. */
}
dns_test_end();
}
static void
{
isc_uint32_t i;
for (i = 0; i < num_names; i++) {
size_t *n;
ATF_REQUIRE(n != NULL);
*n = i; /* Unused value */
while (1) {
int j;
for (j = 0; j < 32; j++) {
isc_uint32_t v;
isc_random_get(&v);
}
namebuf[33] = 0;
if (result == ISC_R_SUCCESS) {
namebuf);
*names_count += 1;
break;
}
}
}
}
static void
{
isc_uint32_t i;
for (i = 0; i < num_names; i++) {
node %= *names_count;
if (*names_count > 0) {
*names_count -= 1;
}
}
}
static void
unsigned int line)
{
"line:%u: %lu != %u", line,
(unsigned long)(names_count + 1),
/*
* The distance from each node to its sub-tree root must be less
* than 2 * log_2(1024).
*/
/* Also check RB tree properties */
}
"Test insert and remove in a loop");
}
/*
* 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.
*/
/*
* We use an array for storing names instead of a set
* structure. It's slow, but works and is good enough for tests.
*/
int i;
names_count = 0;
for (i = 0; i < 4096; i++) {
if (names_count < 1024) {
num_names++;
} else {
num_names = 0;
}
if (names_count > 0) {
num_names %= names_count;
num_names++;
} else {
num_names = 0;
}
}
/* Remove the rest of the nodes */
for (i = 0; i < 1024; i++) {
}
}
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.
*/
}
static int *values;
static void *
unsigned int j, i;
unsigned int start = 0;
while (start == 0)
/* Query 32 million random names from it in each thread */
for (j = 0; j < 8; j++) {
}
}
return (NULL);
}
unsigned int r;
unsigned int i;
double t;
unsigned int nthreads;
for (i = 0; i < 4000000; i++) {
values[i] = r;
}
/* Create a tree. */
/* Insert test data into the tree. */
for (i = 0; i < maxvalue; i++) {
}
for (i = 0; i < nthreads; i++) {
}
for (i = 0; i < nthreads; i++) {
}
dns_test_end();
}
#endif /* DNS_BENCHMARK_TESTS */
#endif /* ISC_PLATFORM_USETHREADS */
/*
* Main
*/
#ifdef ISC_PLATFORM_USETHREADS
#ifdef DNS_BENCHMARK_TESTS
#endif /* DNS_BENCHMARK_TESTS */
#endif /* ISC_PLATFORM_USETHREADS */
return (atf_no_error());
}