rbt_test.c revision 2a3747006563cfa1c07516ec594cc6d1f0db7ff2
70e5a7403f0e0a3bd292b8287c5fed5772c15270Automatic Updater * Copyright (C) 2012-2015 Internet Systems Consortium, Inc. ("ISC")
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence * Permission to use, copy, modify, and/or distribute this software for any
ec5347e2c775f027573ce5648b910361aa926c01Automatic Updater * purpose with or without fee is hereby granted, provided that the above
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff * copyright notice and this permission notice appear in all copies.
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * PERFORMANCE OF THIS SOFTWARE.
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff/* $Id: rbt_test.c,v 1.1.14.8 2012/02/10 16:24:37 ckb Exp $ */
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/* ! \file */
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrewstypedef struct {
76c8294c81fb48b1da6e1fc5b83322a4cedb8e58Andreas Gustafsson/* The initial structure of domain tree will be as follows:
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence/* The full absolute names of the nodes in the tree (the tree also
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * contains "." which is not included in this list).
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graffstatic const char * const domain_names[] = {
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff "c", "b", "a", "x.d.e.f", "z.d.e.f", "g.h", "i.g.h", "o.w.y.d.e.f",
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff "j.z.d.e.f", "p.w.y.d.e.f", "q.w.y.d.e.f", "k.g.h"
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graffstatic const size_t domain_names_count = (sizeof(domain_names) /
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff/* These are set as the node data for the tree used in distances check
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence * (for the names in domain_names[] above).
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graffstatic const int node_distances[] = {
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * The domain order should be:
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * ., 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,
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * q.w.y.d.e.f, z.d.e.f, j.z.d.e.f, g.h, i.g.h, k.g.h
c803787146cadcb2d7e10cbf4491f3be513dfa1aMichael Graff * . (no data, can't be found)
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graffstatic const char * const ordered_names[] = {
86944a4c8002e80ae9b6eb5a5e29b797879be45fMichael Graff "a", "b", "c", "d.e.f", "x.d.e.f", "w.y.d.e.f", "o.w.y.d.e.f",
e44487bfc23599b6b240e09d83d1c862fecfcc82Michael Graff "p.w.y.d.e.f", "q.w.y.d.e.f", "z.d.e.f", "j.z.d.e.f",
306a93530536f05edfb477cac1c2667d90129a8fMichael Graffstatic const size_t ordered_names_count = (sizeof(ordered_names) /
c803787146cadcb2d7e10cbf4491f3be513dfa1aMichael Graffbuild_name_from_str(const char *namestr, dns_fixedname_t *fname) {
86944a4c8002e80ae9b6eb5a5e29b797879be45fMichael Graff result = isc_buffer_allocate(mctx, &b, length);
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence isc_buffer_putmem(b, (const unsigned char *) namestr, length);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff result = dns_name_fromtext(name, b, dns_rootname, 0, NULL);
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence result = dns_rbt_create(mctx, delete_data, NULL, &ctx->rbt);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff result = dns_rbt_create(mctx, delete_data, NULL, &ctx->rbt_distances);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff for (i = 0; i < domain_names_count; i++) {
fd15c8e32ed0c1cfd3ed737858a81966e7fbaeacAndreas Gustafsson result = dns_rbt_addname(ctx->rbt, name, n);
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff result = dns_rbt_addname(ctx->rbt_distances, name, n);
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff * Walk the tree and ensure that all the test nodes are present.
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff for (i = 0; i < domain_names_count; i++) {
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff result = dns_rbt_findname(rbt, name, 0, foundname,
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence (void *) &n);
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff atf_tc_set_md_var(tc, "descr", "Test the creation of an rbt");
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff atf_tc_set_md_var(tc, "descr", "Test dns_rbt_nodecount() on a tree");
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff ATF_CHECK_EQ(15, dns_rbt_nodecount(ctx->rbt));
58aaab3687aac838542ee4ef65a9c094a5d34ab0Michael Graff "Test dns_rbtnode_get_distance() on a tree");
c90f5e8d1edbd5c277f2ee320167a12a30ba7c7bMichael Graff result = dns_rbt_findnode(ctx->rbt_distances, name, NULL,
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff const size_t *distance = (const size_t *) node->data;
e198cb953c1a5bc189ae21dc3f8d622f5a08bc34Bob Halley result = dns_rbtnodechain_next(&chain, NULL, NULL);
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff dns_rbtnodechain_current(&chain, NULL, NULL, &node);
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff "Test tree balance, inserting names in random order");
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff /* This test checks an important performance-related property of
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff * the red-black tree, which is important for us: the longest
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff * path from a sub-tree's root to a node is no more than
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff * 2log(n). This check verifies that the tree is balanced.
1c3bc66ada38236cc81c41b7174a9f0a872c9ab6Michael Graff result = dns_rbt_create(mctx, delete_data, NULL, &mytree);
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff /* Names are inserted in random order. */
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff /* Make a large 65536 node top-level domain tree, i.e., the
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff * following code inserts names such as:
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff * savoucnsrkrqzpkqypbygwoiliawpbmz.
1a0e33bc2044e1902493111db14cbf793083ac47Michael Graff * wkadamcbbpjtundbxcmuayuycposvngx.
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff * wzbpznemtooxdpjecdxynsfztvnuyfao.
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff * yueojmhyffslpvfmgyfwioxegfhepnqq.
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff for (j = 0; j < 32; j++) {
1c3bc66ada38236cc81c41b7174a9f0a872c9ab6Michael Graff /* 1 (root . node) + (1 << log_num_nodes) */
d4d2a13916a114879763562db6a19b70b1444ec1Michael Graff ATF_CHECK_EQ(1U + (1U << log_num_nodes), dns_rbt_nodecount(mytree));
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff /* The distance from each node to its sub-tree root must be less
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff * than 2 * log(n).
a9ece9973c35d4d780338e89e288fb6a59575324Michael Graff ATF_CHECK((2U * log_num_nodes) >= dns__rbt_getheight(mytree));
3ac63b472022ff92691d1fe69ac715a729671965Michael Graff /* Also check RB tree properties */
86944a4c8002e80ae9b6eb5a5e29b797879be45fMichael Graff "Test tree balance, inserting names in sorted order");
size_t *n;
dns_test_end();
static isc_result_t
static isc_boolean_t
return (is_equal);
/* Fission the node "g.h" */
/* Node count must have incremented ("g.h" fissioned to "g" and
dns_test_end();
size_t j;
for (j = 0; j < ordered_names_count; j++) {
size_t i;
size_t *n;
for (i = 0; i < domain_names_count; i++) {
for (i = 0; i < ordered_names_count; i++) {
start_node = 0;
NULL,
NULL);
NULL,
NULL,
&node);
if (n != NULL) {
ATF_CHECK_EQ(*n, i);
&node);
dns_test_end();
size_t j;
for (j = 0; j < ordered_names_count; j++) {
size_t i;
for (i = 0; i < domain_names_count; i++) {
for (i = 0; i < ordered_names_count; i++) {
start_node = 0;
NULL,
NULL);
NULL,
NULL,
&node);
&node);
dns_test_end();
isc_uint32_t i;
for (i = 0; i < num_names; i++) {
size_t *n;
isc_uint32_t v;
isc_random_get(&v);
namebuf);
isc_uint32_t i;
for (i = 0; i < num_names; i++) {
if (*names_count > 0) {
names_count = 0;
num_names++;
num_names = 0;
if (names_count > 0) {
num_names++;
num_names = 0;
dns_test_end();
static int *values;
unsigned int start = 0;
while (start == 0)
return (NULL);
unsigned int nthreads;
values[i] = r;
for (i = 0; i < maxvalue; i++) {
for (i = 0; i < nthreads; i++) {
ATF_REQUIRE(s == 0);
for (i = 0; i < nthreads; i++) {
ATF_REQUIRE(s == 0);
dns_test_end();
return (atf_no_error());