rbt_test.c revision 2a3747006563cfa1c07516ec594cc6d1f0db7ff2
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff/*
70e5a7403f0e0a3bd292b8287c5fed5772c15270Automatic Updater * Copyright (C) 2012-2015 Internet Systems Consortium, Inc. ("ISC")
499b34cea04a46823d003d4c0520c8b03e8513cbBrian Wellington *
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.
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff *
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.
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews */
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff/* $Id: rbt_test.c,v 1.1.14.8 2012/02/10 16:24:37 ckb Exp $ */
307d2084502eddc7ce921e5ce439aec3531d90e0Tatuya JINMEI 神明達哉
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/* ! \file */
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein
9c3531d72aeaad6c5f01efe6a1c82023e1379e4dDavid Lawrence#include <config.h>
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff#include <atf-c.h>
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff#include <isc/mem.h>
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff#include <isc/random.h>
142784f574e0b63e8bbcccb762eb8727ac7c76feBrian Wellington#include <isc/string.h>
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff#include <fcntl.h>
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff#include <unistd.h>
86944a4c8002e80ae9b6eb5a5e29b797879be45fMichael Graff
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff#ifdef HAVE_INTTYPES_H
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews#include <inttypes.h> /* uintptr_t */
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews#endif
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff#include <dns/rbt.h>
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff#include <dns/fixedname.h>
364a82f7c25b62967678027043425201a5e5171aBob Halley#include <dns/result.h>
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff#include <dns/compress.h>
e45d323a2a0f4ca08d4b139546e60a5fa7bd3f0cMichael Graff#include "dnstest.h"
fd15c8e32ed0c1cfd3ed737858a81966e7fbaeacAndreas Gustafsson
558ab0f6a8046499bfe3e39ea4789036313b72b3Michael Graff#include <isc/app.h>
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff#include <isc/buffer.h>
41ac1e406f1be4ec2eba2d8bae673e762d54ea74Andreas Gustafsson#include <isc/entropy.h>
efa4ebbff3c9f6f38ab8b55540fb696243c1172cAndreas Gustafsson#include <isc/file.h>
c90f5e8d1edbd5c277f2ee320167a12a30ba7c7bMichael Graff#include <isc/hash.h>
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff#include <isc/mem.h>
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff#include <isc/os.h>
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff#include <isc/string.h>
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff#include <isc/socket.h>
49df2ea9870b89427c847864ba18599f4bfa467dAndreas Gustafsson#include <isc/stdio.h>
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff#include <isc/task.h>
c803787146cadcb2d7e10cbf4491f3be513dfa1aMichael Graff#include <isc/timer.h>
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff#include <isc/util.h>
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff#include <isc/print.h>
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews#include <isc/time.h>
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews#include <dns/log.h>
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews#include <dns/name.h>
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews#include <dns/result.h>
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews#include <dst/dst.h>
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews#include <ctype.h>
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews#include <stdlib.h>
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews#include <time.h>
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrewstypedef struct {
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews dns_rbt_t *rbt;
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews dns_rbt_t *rbt_distances;
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews} test_context_t;
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff
76c8294c81fb48b1da6e1fc5b83322a4cedb8e58Andreas Gustafsson/* The initial structure of domain tree will be as follows:
76c8294c81fb48b1da6e1fc5b83322a4cedb8e58Andreas Gustafsson *
76c8294c81fb48b1da6e1fc5b83322a4cedb8e58Andreas Gustafsson * .
76c8294c81fb48b1da6e1fc5b83322a4cedb8e58Andreas Gustafsson * |
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff * b
1b6d529cb5ee0ad44f8518e1b8c2cbca54bbdf18David Lawrence * / \
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff * a d.e.f
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff * / | \
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * c | g.h
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * | |
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * w.y i
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence * / | \ \
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff * x | z k
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff * | |
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff * p j
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff * / \
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff * o q
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff */
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence
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).
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff */
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 Graff};
c803787146cadcb2d7e10cbf4491f3be513dfa1aMichael Graff
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graffstatic const size_t domain_names_count = (sizeof(domain_names) /
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff sizeof(domain_names[0]));
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff
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).
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence */
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graffstatic const int node_distances[] = {
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff 3, 1, 2, 2, 2, 3, 1, 2, 1, 1, 2, 2
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff};
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff/*
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)
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * |
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff * b
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * / \
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * a d.e.f
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * / | \
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence * c | g.h
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * | |
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * w.y i
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * / | \ \
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * x | z k
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence * | |
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * p j
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff * / \
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff * o q
86944a4c8002e80ae9b6eb5a5e29b797879be45fMichael Graff */
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence
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",
e44487bfc23599b6b240e09d83d1c862fecfcc82Michael Graff "g.h", "i.g.h", "k.g.h"};
86944a4c8002e80ae9b6eb5a5e29b797879be45fMichael Graff
306a93530536f05edfb477cac1c2667d90129a8fMichael Graffstatic const size_t ordered_names_count = (sizeof(ordered_names) /
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff sizeof(*ordered_names));
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff
306a93530536f05edfb477cac1c2667d90129a8fMichael Graffstatic void
306a93530536f05edfb477cac1c2667d90129a8fMichael Graffdelete_data(void *data, void *arg) {
897c9ddb4d745b2bfecf98b17e5487bb6656299aMichael Graff UNUSED(arg);
897c9ddb4d745b2bfecf98b17e5487bb6656299aMichael Graff
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff isc_mem_put(mctx, data, sizeof(size_t));
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff}
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graffstatic void
c803787146cadcb2d7e10cbf4491f3be513dfa1aMichael Graffbuild_name_from_str(const char *namestr, dns_fixedname_t *fname) {
c803787146cadcb2d7e10cbf4491f3be513dfa1aMichael Graff size_t length;
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff isc_buffer_t *b = NULL;
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff isc_result_t result;
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff dns_name_t *name;
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff length = strlen(namestr);
86944a4c8002e80ae9b6eb5a5e29b797879be45fMichael Graff
86944a4c8002e80ae9b6eb5a5e29b797879be45fMichael Graff result = isc_buffer_allocate(mctx, &b, length);
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence isc_buffer_putmem(b, (const unsigned char *) namestr, length);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff dns_fixedname_init(fname);
3ac63b472022ff92691d1fe69ac715a729671965Michael Graff name = dns_fixedname_name(fname);
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff ATF_REQUIRE(name != NULL);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff result = dns_name_fromtext(name, b, dns_rootname, 0, NULL);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff isc_buffer_free(&b);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff}
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graffstatic test_context_t *
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Grafftest_context_setup(void) {
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff test_context_t *ctx;
558ab0f6a8046499bfe3e39ea4789036313b72b3Michael Graff isc_result_t result;
558ab0f6a8046499bfe3e39ea4789036313b72b3Michael Graff size_t i;
4e21e54a0394d0f87798620a95c1f675c0b0d09cMichael Graff
558ab0f6a8046499bfe3e39ea4789036313b72b3Michael Graff ctx = isc_mem_get(mctx, sizeof(*ctx));
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff ATF_REQUIRE(ctx != NULL);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence ctx->rbt = NULL;
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence result = dns_rbt_create(mctx, delete_data, NULL, &ctx->rbt);
fd15c8e32ed0c1cfd3ed737858a81966e7fbaeacAndreas Gustafsson ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff ctx->rbt_distances = NULL;
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff result = dns_rbt_create(mctx, delete_data, NULL, &ctx->rbt_distances);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff for (i = 0; i < domain_names_count; i++) {
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff size_t *n;
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff dns_fixedname_t fname;
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff dns_name_t *name;
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff build_name_from_str(domain_names[i], &fname);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff
fd15c8e32ed0c1cfd3ed737858a81966e7fbaeacAndreas Gustafsson name = dns_fixedname_name(&fname);
fd15c8e32ed0c1cfd3ed737858a81966e7fbaeacAndreas Gustafsson
fd15c8e32ed0c1cfd3ed737858a81966e7fbaeacAndreas Gustafsson n = isc_mem_get(mctx, sizeof(size_t));
fd15c8e32ed0c1cfd3ed737858a81966e7fbaeacAndreas Gustafsson *n = i + 1;
fd15c8e32ed0c1cfd3ed737858a81966e7fbaeacAndreas Gustafsson result = dns_rbt_addname(ctx->rbt, name, n);
fd15c8e32ed0c1cfd3ed737858a81966e7fbaeacAndreas Gustafsson ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff n = isc_mem_get(mctx, sizeof(size_t));
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff *n = node_distances[i];
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff result = dns_rbt_addname(ctx->rbt_distances, name, n);
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
40f53fa8d9c6a4fc38c0014495e7a42b08f52481David Lawrence }
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff return (ctx);
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff}
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graffstatic void
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Grafftest_context_teardown(test_context_t *ctx) {
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff dns_rbt_destroy(&ctx->rbt);
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff dns_rbt_destroy(&ctx->rbt_distances);
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff isc_mem_put(mctx, ctx, sizeof(*ctx));
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff}
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff/*
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff * Walk the tree and ensure that all the test nodes are present.
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff */
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graffstatic void
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graffcheck_test_data(dns_rbt_t *rbt) {
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff dns_fixedname_t fixed;
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff isc_result_t result;
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff dns_name_t *foundname;
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff size_t i;
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff dns_fixedname_init(&fixed);
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff foundname = dns_fixedname_name(&fixed);
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff for (i = 0; i < domain_names_count; i++) {
efa4ebbff3c9f6f38ab8b55540fb696243c1172cAndreas Gustafsson dns_fixedname_t fname;
e592dd7c344052ee51eb707cd744b48b34f4c74eBob Halley dns_name_t *name;
efa4ebbff3c9f6f38ab8b55540fb696243c1172cAndreas Gustafsson size_t *n;
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff
36ca83769dbba29a3d8670eef9acd95c7a71a7f6Michael Graff build_name_from_str(domain_names[i], &fname);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff name = dns_fixedname_name(&fname);
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff n = NULL;
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff result = dns_rbt_findname(rbt, name, 0, foundname,
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence (void *) &n);
1b6d529cb5ee0ad44f8518e1b8c2cbca54bbdf18David Lawrence ATF_CHECK_EQ(result, ISC_R_SUCCESS);
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff ATF_CHECK_EQ(*n, i + 1);
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff }
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff}
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael GraffATF_TC(rbt_create);
528829aa8ad69238e674cd81078bc14d4199691bMichael GraffATF_TC_HEAD(rbt_create, tc) {
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff atf_tc_set_md_var(tc, "descr", "Test the creation of an rbt");
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff}
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael GraffATF_TC_BODY(rbt_create, tc) {
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff isc_result_t result;
6e49e91bd08778d7eae45a2229dcf41ed97cc636David Lawrence test_context_t *ctx;
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff isc_boolean_t tree_ok;
6e49e91bd08778d7eae45a2229dcf41ed97cc636David Lawrence
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff UNUSED(tc);
307d2084502eddc7ce921e5ce439aec3531d90e0Tatuya JINMEI 神明達哉
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff isc_mem_debugging = ISC_MEM_DEBUGRECORD;
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff result = dns_test_begin(NULL, ISC_TRUE);
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff ATF_CHECK_EQ(result, ISC_R_SUCCESS);
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff
cebd4498636d3d480f6f2a7aa2eb72bd2ed64010Michael Graff ctx = test_context_setup();
cebd4498636d3d480f6f2a7aa2eb72bd2ed64010Michael Graff
cebd4498636d3d480f6f2a7aa2eb72bd2ed64010Michael Graff check_test_data(ctx->rbt);
cebd4498636d3d480f6f2a7aa2eb72bd2ed64010Michael Graff
1a0e33bc2044e1902493111db14cbf793083ac47Michael Graff tree_ok = dns__rbt_checkproperties(ctx->rbt);
1a0e33bc2044e1902493111db14cbf793083ac47Michael Graff ATF_CHECK_EQ(tree_ok, ISC_TRUE);
897c9ddb4d745b2bfecf98b17e5487bb6656299aMichael Graff
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews test_context_teardown(ctx);
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff dns_test_end();
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff}
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff
c803787146cadcb2d7e10cbf4491f3be513dfa1aMichael GraffATF_TC(rbt_nodecount);
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael GraffATF_TC_HEAD(rbt_nodecount, tc) {
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff atf_tc_set_md_var(tc, "descr", "Test dns_rbt_nodecount() on a tree");
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff}
2bcb48cfcae36398454c98e40c563e2cde748e07Michael GraffATF_TC_BODY(rbt_nodecount, tc) {
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff isc_result_t result;
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff test_context_t *ctx;
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff UNUSED(tc);
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff
c803787146cadcb2d7e10cbf4491f3be513dfa1aMichael Graff isc_mem_debugging = ISC_MEM_DEBUGRECORD;
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff result = dns_test_begin(NULL, ISC_TRUE);
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff ATF_CHECK_EQ(result, ISC_R_SUCCESS);
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff ctx = test_context_setup();
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff ATF_CHECK_EQ(15, dns_rbt_nodecount(ctx->rbt));
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff test_context_teardown(ctx);
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence
1a69a1a78cfaa86f3b68bbc965232b7876d4da2aDavid Lawrence dns_test_end();
da547174e2b7beb6d6119d58197ad0bc85b91179Michael Graff}
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff
86944a4c8002e80ae9b6eb5a5e29b797879be45fMichael GraffATF_TC(rbtnode_get_distance);
86944a4c8002e80ae9b6eb5a5e29b797879be45fMichael GraffATF_TC_HEAD(rbtnode_get_distance, tc) {
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff atf_tc_set_md_var(tc, "descr",
58aaab3687aac838542ee4ef65a9c094a5d34ab0Michael Graff "Test dns_rbtnode_get_distance() on a tree");
f00d96a15cdd11e764437f9359e67328631caaeaMichael Graff}
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael GraffATF_TC_BODY(rbtnode_get_distance, tc) {
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff isc_result_t result;
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff test_context_t *ctx;
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff const char *name_str = "a";
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff dns_fixedname_t fname;
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff dns_name_t *name;
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff dns_rbtnode_t *node = NULL;
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff dns_rbtnodechain_t chain;
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff UNUSED(tc);
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff isc_mem_debugging = ISC_MEM_DEBUGRECORD;
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff result = dns_test_begin(NULL, ISC_TRUE);
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews ATF_CHECK_EQ(result, ISC_R_SUCCESS);
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews ctx = test_context_setup();
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews build_name_from_str(name_str, &fname);
e198cb953c1a5bc189ae21dc3f8d622f5a08bc34Bob Halley name = dns_fixedname_name(&fname);
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff
c90f5e8d1edbd5c277f2ee320167a12a30ba7c7bMichael Graff dns_rbtnodechain_init(&chain, mctx);
e198cb953c1a5bc189ae21dc3f8d622f5a08bc34Bob Halley
c90f5e8d1edbd5c277f2ee320167a12a30ba7c7bMichael Graff result = dns_rbt_findnode(ctx->rbt_distances, name, NULL,
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff &node, &chain, 0, NULL, NULL);
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff ATF_CHECK_EQ(result, ISC_R_SUCCESS);
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff while (node != NULL) {
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff const size_t *distance = (const size_t *) node->data;
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff if (distance != NULL)
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff ATF_CHECK_EQ(*distance,
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff dns__rbtnode_getdistance(node));
e198cb953c1a5bc189ae21dc3f8d622f5a08bc34Bob Halley result = dns_rbtnodechain_next(&chain, NULL, NULL);
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff if (result == ISC_R_NOMORE)
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff break;
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff dns_rbtnodechain_current(&chain, NULL, NULL, &node);
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff }
e198cb953c1a5bc189ae21dc3f8d622f5a08bc34Bob Halley
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff ATF_CHECK_EQ(result, ISC_R_NOMORE);
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff dns_rbtnodechain_invalidate(&chain);
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff test_context_teardown(ctx);
d98c74e2ec5b96bd22aa4ed6d893e8993787493bMichael Graff
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff dns_test_end();
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff}
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff
910df98b0efcbe8380b952887f4071051cc39a25Michael GraffATF_TC(rbt_check_distance_random);
738b9aa3ded1ef724922d6695cb04ec2e721bdd1Bob HalleyATF_TC_HEAD(rbt_check_distance_random, tc) {
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff atf_tc_set_md_var(tc, "descr",
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff "Test tree balance, inserting names in random order");
738b9aa3ded1ef724922d6695cb04ec2e721bdd1Bob Halley}
910df98b0efcbe8380b952887f4071051cc39a25Michael GraffATF_TC_BODY(rbt_check_distance_random, tc) {
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.
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff */
29f28fe573d4b3b318b3b026d567c1eb86738015Michael Graff dns_rbt_t *mytree = NULL;
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff const unsigned int log_num_nodes = 16;
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff
29f28fe573d4b3b318b3b026d567c1eb86738015Michael Graff int i;
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff isc_result_t result;
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff isc_boolean_t tree_ok;
29f28fe573d4b3b318b3b026d567c1eb86738015Michael Graff
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff UNUSED(tc);
cebd4498636d3d480f6f2a7aa2eb72bd2ed64010Michael Graff
cebd4498636d3d480f6f2a7aa2eb72bd2ed64010Michael Graff isc_mem_debugging = ISC_MEM_DEBUGRECORD;
cebd4498636d3d480f6f2a7aa2eb72bd2ed64010Michael Graff
cebd4498636d3d480f6f2a7aa2eb72bd2ed64010Michael Graff result = dns_test_begin(NULL, ISC_TRUE);
1c3bc66ada38236cc81c41b7174a9f0a872c9ab6Michael Graff ATF_CHECK_EQ(result, ISC_R_SUCCESS);
1c3bc66ada38236cc81c41b7174a9f0a872c9ab6Michael Graff
1c3bc66ada38236cc81c41b7174a9f0a872c9ab6Michael Graff result = dns_rbt_create(mctx, delete_data, NULL, &mytree);
528829aa8ad69238e674cd81078bc14d4199691bMichael Graff ATF_REQUIRE_EQ(result, ISC_R_SUCCESS);
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff /* Names are inserted in random order. */
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff /* Make a large 65536 node top-level domain tree, i.e., the
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff * following code inserts names such as:
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff *
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff * savoucnsrkrqzpkqypbygwoiliawpbmz.
1a0e33bc2044e1902493111db14cbf793083ac47Michael Graff * wkadamcbbpjtundbxcmuayuycposvngx.
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff * wzbpznemtooxdpjecdxynsfztvnuyfao.
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff * yueojmhyffslpvfmgyfwioxegfhepnqq.
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff */
1a0e33bc2044e1902493111db14cbf793083ac47Michael Graff for (i = 0; i < (1 << log_num_nodes); i++) {
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff size_t *n;
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff char namebuf[34];
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff n = isc_mem_get(mctx, sizeof(size_t));
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff *n = i + 1;
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff while (1) {
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff int j;
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff dns_fixedname_t fname;
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff dns_name_t *name;
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff
f942258b6380ba1f2c2f057a79ffc37bc3436488Michael Graff for (j = 0; j < 32; j++) {
78854e02c127f31ab90f56da0531542004b45377Michael Graff isc_uint32_t v;
970cccf46e0f949a1a9edbcd8302dd2a112b43c2Michael Graff isc_random_get(&v);
29f28fe573d4b3b318b3b026d567c1eb86738015Michael Graff namebuf[j] = 'a' + (v % 26);
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff }
306a93530536f05edfb477cac1c2667d90129a8fMichael Graff namebuf[32] = '.';
29f28fe573d4b3b318b3b026d567c1eb86738015Michael Graff namebuf[33] = 0;
29f28fe573d4b3b318b3b026d567c1eb86738015Michael Graff
86944a4c8002e80ae9b6eb5a5e29b797879be45fMichael Graff build_name_from_str(namebuf, &fname);
86944a4c8002e80ae9b6eb5a5e29b797879be45fMichael Graff name = dns_fixedname_name(&fname);
86944a4c8002e80ae9b6eb5a5e29b797879be45fMichael Graff
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff result = dns_rbt_addname(mytree, name, n);
30251e07d1705d1a85b0e1d5a969496e1aed612eMichael Graff if (result == ISC_R_SUCCESS)
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff break;
30251e07d1705d1a85b0e1d5a969496e1aed612eMichael Graff }
30251e07d1705d1a85b0e1d5a969496e1aed612eMichael Graff }
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff
1c3bc66ada38236cc81c41b7174a9f0a872c9ab6Michael Graff /* 1 (root . node) + (1 << log_num_nodes) */
d4d2a13916a114879763562db6a19b70b1444ec1Michael Graff ATF_CHECK_EQ(1U + (1U << log_num_nodes), dns_rbt_nodecount(mytree));
ff9bb3fc5453bbf310b67c560fbf04a5c0fb60daMichael Graff
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff /* The distance from each node to its sub-tree root must be less
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff * than 2 * log(n).
efc8a09e19dfcfafa92fd2ad113073a4f5295e9bMichael Graff */
a9ece9973c35d4d780338e89e288fb6a59575324Michael Graff ATF_CHECK((2U * log_num_nodes) >= dns__rbt_getheight(mytree));
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff
3ac63b472022ff92691d1fe69ac715a729671965Michael Graff /* Also check RB tree properties */
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff tree_ok = dns__rbt_checkproperties(mytree);
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff ATF_CHECK_EQ(tree_ok, ISC_TRUE);
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews dns_rbt_destroy(&mytree);
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews
9297259c7abecc78470fdeca173c101137e4b5bbMark Andrews dns_test_end();
2bcb48cfcae36398454c98e40c563e2cde748e07Michael Graff}
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff
910df98b0efcbe8380b952887f4071051cc39a25Michael GraffATF_TC(rbt_check_distance_ordered);
910df98b0efcbe8380b952887f4071051cc39a25Michael GraffATF_TC_HEAD(rbt_check_distance_ordered, tc) {
86944a4c8002e80ae9b6eb5a5e29b797879be45fMichael Graff atf_tc_set_md_var(tc, "descr",
86944a4c8002e80ae9b6eb5a5e29b797879be45fMichael Graff "Test tree balance, inserting names in sorted order");
910df98b0efcbe8380b952887f4071051cc39a25Michael Graff}
910df98b0efcbe8380b952887f4071051cc39a25Michael GraffATF_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;
isc_boolean_t tree_ok;
UNUSED(tc);
isc_mem_debugging = ISC_MEM_DEBUGRECORD;
result = dns_test_begin(NULL, ISC_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));
*n = i + 1;
snprintf(namebuf, sizeof(namebuf), "name%08x.", i);
build_name_from_str(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, ISC_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;
build_name_from_str(namestr, &fname);
name = dns_fixedname_name(&fname);
return (dns_rbt_addnode(rbt, name, node));
}
static isc_boolean_t
compare_labelsequences(dns_rbtnode_t *node, const char *labelstr) {
dns_name_t name;
isc_result_t result;
char *nodestr = NULL;
isc_boolean_t 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 ? ISC_TRUE : ISC_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, ISC_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"), ISC_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"), ISC_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"), ISC_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"), ISC_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"), ISC_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"), ISC_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, ISC_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;
isc_boolean_t 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;
build_name_from_str(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));
*n = i;
node->data = n;
}
/* Now, delete the j'th node from the tree. */
{
dns_fixedname_t fname;
dns_name_t *name;
build_name_from_str(ordered_names[j], &fname);
name = dns_fixedname_name(&fname);
result = dns_rbt_deletename(mytree, name, ISC_FALSE);
ATF_CHECK_EQ(result, ISC_R_SUCCESS);
}
/* Check RB tree properties. */
tree_ok = dns__rbt_checkproperties(mytree);
ATF_CHECK_EQ(tree_ok, ISC_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;
build_name_from_str(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);
build_name_from_str(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;
build_name_from_str(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;
build_name_from_str(ordered_names[j], &fname_j);
name_j = dns_fixedname_name(&fname_j);
build_name_from_str(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();
}
ATF_TC(rbt_remove_empty);
ATF_TC_HEAD(rbt_remove_empty, tc) {
atf_tc_set_md_var(tc, "descr",
"Test removal from a tree when "
"upper nodes are empty");
}
ATF_TC_BODY(rbt_remove_empty, tc) {
/*
* This test is similar to the rbt_remove test, but checks node
* deletion when upper nodes are empty.
*/
isc_result_t result;
size_t j;
UNUSED(tc);
isc_mem_debugging = ISC_MEM_DEBUGRECORD;
result = dns_test_begin(NULL, ISC_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;
isc_boolean_t 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;
build_name_from_str(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);
/* Check that node data is empty */
ATF_REQUIRE(node != NULL);
ATF_REQUIRE_EQ(node->data, NULL);
}
/* Now, delete the j'th node from the tree. */
{
dns_fixedname_t fname;
dns_name_t *name;
build_name_from_str(ordered_names[j], &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);
result = dns_rbt_deletenode(mytree, node, ISC_FALSE);
ATF_CHECK_EQ(result, ISC_R_SUCCESS);
}
/* Check RB tree properties. */
tree_ok = dns__rbt_checkproperties(mytree);
ATF_CHECK_EQ(tree_ok, ISC_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;
build_name_from_str(ordered_names[0], &fname);
name = dns_fixedname_name(&fname);
node = NULL;
result = dns_rbt_findnode(mytree, name, NULL,
&node, NULL,
DNS_RBTFIND_EMPTYDATA,
NULL, NULL);
ATF_CHECK(result != ISC_R_SUCCESS);
build_name_from_str(ordered_names[1], &fname);
name = dns_fixedname_name(&fname);
node = NULL;
result = dns_rbt_findnode(mytree, name, NULL,
&node, &chain,
DNS_RBTFIND_EMPTYDATA,
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;
build_name_from_str(ordered_names[0], &fname);
name = dns_fixedname_name(&fname);
node = NULL;
result = dns_rbt_findnode(mytree, name, NULL,
&node, &chain,
DNS_RBTFIND_EMPTYDATA,
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 fntmp1, fntmp2;
dns_name_t *ntmp1, *ntmp2;
dns_fixedname_t fname_j, fname_i;
dns_name_t *name_j, *name_i;
build_name_from_str("j.z.d.e.f", &fntmp1);
ntmp1 = dns_fixedname_name(&fntmp1);
build_name_from_str("z.d.e.f", &fntmp2);
ntmp2 = dns_fixedname_name(&fntmp2);
build_name_from_str(ordered_names[j], &fname_j);
name_j = dns_fixedname_name(&fname_j);
build_name_from_str(ordered_names[i], &fname_i);
name_i = dns_fixedname_name(&fname_i);
if (dns_name_equal(name_j, ntmp1) &&
dns_name_equal(name_j, ntmp2))
{
/*
* The only special case in the
* tree. Here, "z.d.e.f" will not exist
* as it would have been removed during
* removal of "j.z.d.e.f".
*/
continue;
}
if (dns_name_equal(name_i, name_j)) {
dns_fixedname_t fntmp3, fntmp4, fntmp5, fntmp6;
dns_name_t *ntmp3, *ntmp4, *ntmp5, *ntmp6;
/*
* 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 are empty
* initially. If an empty removed node
* exists because it is a super-domain,
* just skip it.
*/
build_name_from_str("d.e.f", &fntmp3);
ntmp3 = dns_fixedname_name(&fntmp3);
build_name_from_str("w.y.d.e.f", &fntmp4);
ntmp4 = dns_fixedname_name(&fntmp4);
build_name_from_str("z.d.e.f", &fntmp5);
ntmp5 = dns_fixedname_name(&fntmp5);
build_name_from_str("g.h", &fntmp6);
ntmp6 = dns_fixedname_name(&fntmp6);
if (dns_name_equal(name_j, ntmp3) ||
dns_name_equal(name_j, ntmp4) ||
dns_name_equal(name_j, ntmp5) ||
dns_name_equal(name_j, ntmp6))
{
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);
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, isc_uint32_t num_names)
{
isc_uint32_t i;
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++) {
isc_uint32_t v;
isc_random_get(&v);
namebuf[j] = 'a' + (v % 26);
}
namebuf[32] = '.';
namebuf[33] = 0;
build_name_from_str(namebuf, &fname);
name = dns_fixedname_name(&fname);
result = dns_rbt_addname(mytree, name, n);
if (result == ISC_R_SUCCESS) {
names[*names_count] = isc_mem_strdup(mctx,
namebuf);
*names_count += 1;
break;
}
}
}
}
static void
remove_nodes(dns_rbt_t *mytree, char **names,
size_t *names_count, isc_uint32_t num_names)
{
isc_uint32_t i;
UNUSED(mytree);
for (i = 0; i < num_names; i++) {
isc_uint32_t node;
dns_fixedname_t fname;
dns_name_t *name;
isc_result_t result;
isc_random_get(&node);
node %= *names_count;
build_name_from_str(names[node], &fname);
name = dns_fixedname_name(&fname);
result = dns_rbt_deletename(mytree, name, ISC_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) {
isc_boolean_t tree_ok;
UNUSED(names);
ATF_CHECK_EQ(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, ISC_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;
/*
* 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, ISC_TRUE);
ATF_CHECK_EQ(result, ISC_R_SUCCESS);
result = dns_rbt_create(mctx, delete_data, NULL, &mytree);
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++) {
isc_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);
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);
}
/* Remove the rest of the nodes */
remove_nodes(mytree, names, &names_count, names_count);
check_tree(mytree, names, names_count);
for (i = 0; i < 1024; i++) {
if (names[i] != NULL) {
isc_mem_free(mctx, names[i]);
}
}
dns_rbt_destroy(&mytree);
dns_test_end();
}
#if 0
/*
* 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;
pthread_t threads[32];
UNUSED(tc);
srandom(time(NULL));
debug_mem_record = ISC_FALSE;
result = dns_test_begin(NULL, ISC_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);
build_name_from_str(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++) {
int s;
s = pthread_create(&threads[i], NULL, find_thread, mytree);
ATF_REQUIRE(s == 0);
}
for (i = 0; i < nthreads; i++) {
int s;
s = pthread_join(threads[i], NULL);
ATF_REQUIRE(s == 0);
}
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 /* benchmark test */
/*
* 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_remove_empty);
ATF_TP_ADD_TC(tp, rbt_insert_and_remove);
#if 0
ATF_TP_ADD_TC(tp, benchmark);
#endif
return (atf_no_error());
}