summaryrefslogtreecommitdiff
path: root/src/tc-map.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/tc-map.c')
-rw-r--r--src/tc-map.c747
1 files changed, 747 insertions, 0 deletions
diff --git a/src/tc-map.c b/src/tc-map.c
new file mode 100644
index 0000000..4fe0408
--- /dev/null
+++ b/src/tc-map.c
@@ -0,0 +1,747 @@
+/*
+ * Test for libHX's maps
+ * Copyright Jan Engelhardt
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the WTF Public License version 2 or
+ * (at your option) any later version.
+ */
+#include <errno.h>
+#include <math.h>
+#include <stdarg.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#include <libHX/init.h>
+#include <libHX/map.h>
+#include <libHX/misc.h>
+#include <libHX/string.h>
+#ifdef HAVE_SYS_RESOURCE_H
+# include <sys/resource.h>
+#endif
+#include <sys/time.h>
+#include "internal.h"
+#include "map_int.h"
+
+union HXpoly {
+ struct HXmap *map;
+ struct HXhmap *hmap;
+ struct HXrbtree *rbt;
+};
+
+typedef struct HXmap *(*map_create4_fn_t)(unsigned int,
+ const struct HXmap_ops *, size_t, size_t);
+
+static unsigned int tmap_indent = 0;
+
+static __inline__ void tmap_ipush(void)
+{
+ ++tmap_indent;
+}
+
+static __inline__ void tmap_ipop(void)
+{
+ if (tmap_indent > 0)
+ --tmap_indent;
+}
+
+static void tmap_printf(const char *fmt, ...)
+{
+ unsigned int i;
+ va_list args;
+
+ for (i = 0; i < tmap_indent; ++i)
+ printf("\t");
+ va_start(args, fmt);
+ vprintf(fmt, args);
+ va_end(args);
+}
+
+static void tmap_time(struct timeval *tv)
+{
+#ifdef HAVE_SYS_RESOURCE_H
+ struct rusage r;
+ if (getrusage(RUSAGE_SELF, &r) == 0)
+ *tv = r.ru_utime;
+#else
+ memset(tv, 0, sizeof(*tv));
+#endif
+}
+
+static unsigned int tmap_smart_rand(unsigned int *left, unsigned int *right)
+{
+ unsigned int z = HX_irand(*left, *right);
+
+ if (z == *left)
+ ++*left;
+ else if (z == *right - 1)
+ --*right;
+ return z;
+}
+
+/**
+ * tmap_rword - create random word
+ * @dest: char buffer
+ * @length: size of buffer
+ */
+static __inline__ void tmap_rword(char *dest, unsigned int length)
+{
+ while (--length > 0)
+ *dest++ = HX_irand('a', 'z' + 1);
+ *dest = '\0';
+}
+
+static void tmap_add_rand(struct HXmap *map, unsigned int num)
+{
+ char key[8], value[HXSIZEOF_Z32];
+
+ while (num-- > 0) {
+ tmap_rword(key, sizeof(key));
+ snprintf(value, sizeof(value), "%u", num);
+ if (HXmap_add(map, key, value) == -EEXIST)
+ ++num;
+ }
+}
+
+static void tmap_flush(struct HXmap *map, bool verbose)
+{
+ const struct HXmap_node *node;
+ struct HXmap_trav *iter;
+
+ tmap_printf("Flushing %u elements (with traversal)\n", map->items);
+ tmap_ipush();
+ while (map->items != 0) {
+ /* May need to reload traverser due to deletion */
+ if (verbose)
+ tmap_printf("Restarting traverser\n");
+ if ((iter = HXmap_travinit(map, HXMAP_DTRAV)) == NULL)
+ break;
+ tmap_ipush();
+ while ((node = HXmap_traverse(iter)) != NULL) {
+ if (verbose)
+ tmap_printf("Destroying {%s, %s}\n",
+ node->skey, node->sdata);
+ HXmap_del(map, node->key);
+ }
+ tmap_ipop();
+ HXmap_travfree(iter);
+ }
+ tmap_ipop();
+}
+
+static void tmap_add_speed(struct HXmap *map)
+{
+ struct timeval start, stop, delta;
+ unsigned int threshold;
+
+ tmap_printf("MAP test 1: Timing add operation\n");
+ tmap_ipush();
+ tmap_time(&start);
+ do {
+ tmap_add_rand(map, 1);
+ tmap_time(&stop);
+ HX_timeval_sub(&delta, &stop, &start);
+ } while (!(delta.tv_sec >= 1 || map->items >= 1000000));
+ tmap_printf("%u elements in " HX_TIMEVAL_FMT
+ " (plus time measurement overhead)\n",
+ map->items, HX_TIMEVAL_EXP(&delta));
+ threshold = map->items;
+ tmap_flush(map, false);
+
+ tmap_time(&start);
+ tmap_add_rand(map, threshold);
+ tmap_time(&stop);
+ HX_timeval_sub(&delta, &stop, &start);
+ tmap_printf("%u elements in " HX_TIMEVAL_FMT " (w/o overhead)\n",
+ map->items, HX_TIMEVAL_EXP(&delta));
+ tmap_ipop();
+}
+
+static bool tmap_each_fn(const struct HXmap_node *node, void *arg)
+{
+ return true;
+}
+
+static void tmap_trav_speed(struct HXmap *map)
+{
+ struct timeval start, stop, delta, delta2;
+ const struct HXmap_node *node;
+ struct HXmap_trav *iter;
+
+ tmap_printf("MAP test 2: Timing traversal\n");
+ tmap_ipush();
+ iter = HXmap_travinit(map, HXMAP_NOFLAGS);
+ tmap_time(&start);
+ while ((node = HXmap_traverse(iter)) != NULL)
+ ;
+ tmap_time(&stop);
+ HX_timeval_sub(&delta, &stop, &start);
+ HXmap_travfree(iter);
+ tmap_printf("Open traversal of %u nodes: " HX_TIMEVAL_FMT "s\n",
+ map->items, HX_TIMEVAL_EXP(&delta));
+
+ tmap_time(&start);
+ HXmap_qfe(map, tmap_each_fn, NULL);
+ tmap_time(&stop);
+ HX_timeval_sub(&delta, &stop, &start);
+ tmap_printf("QFE traversal of %u nodes: " HX_TIMEVAL_FMT "s\n",
+ map->items, HX_TIMEVAL_EXP(&delta));
+ tmap_ipop();
+
+ tmap_printf("MAP test 2a: Timing lookup\n");
+ tmap_ipush();
+ iter = HXmap_travinit(map, HXMAP_NOFLAGS);
+ tmap_time(&start);
+ while ((node = HXmap_traverse(iter)) != NULL)
+ HXmap_find(map, node->key);
+ tmap_time(&stop);
+ HX_timeval_sub(&delta2, &stop, &start);
+ HXmap_travfree(iter);
+ /* delta2 includes traversal time */
+ start = delta;
+ stop = delta2;
+ HX_timeval_sub(&delta, &stop, &start);
+ tmap_printf("Lookup of %u nodes: " HX_TIMEVAL_FMT "s\n",
+ map->items, HX_TIMEVAL_EXP(&delta));
+ tmap_ipop();
+}
+
+static void tmap_flat(const struct HXmap *map)
+{
+ struct HXmap_node *nodes;
+ unsigned int i;
+
+ tmap_printf("Retrieving flattened list of %u elements:\n", map->items);
+ tmap_ipush();
+ nodes = HXmap_keysvalues(map);
+ if (nodes == NULL) {
+ perror("HXmap_keysvalues");
+ abort();
+ }
+ for (i = 0; i < map->items; ++i)
+ tmap_printf("%u. %s -> %s\n", i, nodes[i].key, nodes[i].data);
+ tmap_ipop();
+ free(nodes);
+}
+
+static void tmap_trav(struct HXmap *map)
+{
+ const struct HXmap_node *node;
+ unsigned int i = ~(~0U >> 1);
+ char key[8], value[HXSIZEOF_Z32];
+ struct HXmap_trav *iter;
+
+ tmap_printf("Simple traversal:\n");
+ tmap_ipush();
+ iter = HXmap_travinit(map, HXMAP_NOFLAGS);
+ while ((node = HXmap_traverse(iter)) != NULL)
+ tmap_printf("%s -> %s\n", node->skey, node->sdata);
+ tmap_ipop();
+ HXmap_travfree(iter);
+
+ tmap_printf("Add modification during traversal:\n");
+ tmap_ipush();
+ iter = HXmap_travinit(map, HXMAP_NOFLAGS);
+ while ((node = HXmap_traverse(iter)) != NULL) {
+ tmap_printf("%s -> %s\n", node->skey, node->sdata);
+ tmap_rword(key, sizeof(key));
+ snprintf(value, sizeof(value), "%u", i++);
+ HXmap_add(map, key, value);
+ }
+ tmap_ipop();
+ HXmap_travfree(iter);
+}
+
+static void tmap_generic_tests(enum HXmap_type type,
+ unsigned long (*hash_fn)(const void *, size_t), const char *hash_name)
+{
+ struct HXmap_ops ops = {.k_hash = hash_fn};
+ struct HXmap *map;
+
+ tmap_printf("Using hash %s\n", hash_name);
+ map = HXmap_init5(type, HXMAP_SCKEY | HXMAP_SCDATA | HXMAP_NOREPLACE,
+ &ops, 0, 0);
+ tmap_add_speed(map);
+ tmap_trav_speed(map);
+ tmap_flush(map, false);
+
+ tmap_add_rand(map, 2);
+ tmap_flat(map);
+ tmap_trav(map);
+ tmap_flush(map, true);
+ HXmap_free(map);
+}
+
+static int tmap_strtolcmp(const void *a, const void *b, size_t z)
+{
+ long p = strtol(static_cast(const char *, a), NULL, 0);
+ long q = strtol(static_cast(const char *, b), NULL, 0);
+
+ if (p < q)
+ return -1;
+ if (p > q)
+ return 1;
+ return 0;
+}
+
+static const struct HXmap_ops tmap_nstr_ops = {
+ .k_compare = tmap_strtolcmp,
+ .k_hash = HXhash_djb2,
+};
+
+static const struct HXmap_ops tmap_nstr_l3_ops = {
+ .k_compare = tmap_strtolcmp,
+ .k_hash = HXhash_jlookup3s,
+};
+
+static const struct HXmap_ops tmap_words_ops = {
+ .k_hash = HXhash_djb2,
+};
+
+static const struct HXmap_ops tmap_words_l3_ops = {
+ .k_hash = HXhash_jlookup3s,
+};
+
+/**
+ * tmap_expect - compare two strings or warn
+ * @result: result from previous operations
+ * @expected: what we think should have happened
+ */
+static int tmap_expect(const char *result, const char *expected)
+{
+ int ret = strcmp(result, expected);
+ tmap_ipush();
+ tmap_printf("Expected: %s\n", expected);
+ tmap_printf(" Result: %s\n", result);
+ if (ret != 0) {
+ tmap_ipush();
+ tmap_printf("...failed\n");
+ tmap_ipop();
+ }
+ tmap_ipop();
+ return ret;
+}
+
+/**
+ * tmap_new_perfect_tree -
+ * Add elements in such a way that it does not cause an rbtree to rebalance and
+ * thus deterministically attain a perfect binary tree. For hash maps, it only
+ * serves to add some elements.
+ */
+static void tmap_new_perfect_tree(struct HXmap *map,
+ unsigned int height, unsigned int mult)
+{
+ unsigned int right = 1 << height;
+ unsigned int incr = right;
+ unsigned int left = incr / 2;
+ unsigned int y, x;
+ char buf[HXSIZEOF_Z32];
+
+ for (y = 0; y < height; ++y) {
+ for (x = left; x < right; x += incr) {
+ snprintf(buf, sizeof(buf), "%u", x * mult);
+ HXmap_add(map, buf, NULL);
+ }
+ incr /= 2;
+ left /= 2;
+ }
+}
+
+/**
+ * Compute an "agglomeration" index that models the lack of distributedness
+ * in hash maps. Range is 0-100%.
+ */
+static double hmap_agg_index(const struct HXhmap *hmap, bool verbose)
+{
+ const struct HXhmap_node *hnode;
+ unsigned int i;
+ int f = 0, j;
+
+ if (hmap->super.items == 1)
+ return 0;
+ if (verbose)
+ printf("{");
+
+ /*
+ * HXhmap is written such that the number of buckets is always equal or
+ * greater than the element count. This is done because, in practice,
+ * buckets will be populated with more than a few (two/three) entries
+ * before elements/buckets >= grow_trigger_ratio.
+ *
+ * Therefore, one could distribute elements such that no bucket
+ * contains more than one. This is the "ideal" situation. We now count
+ * the sum of absolute differences from this ideal, abs(1-j).
+ *
+ */
+ for (i = 0; i < HXhash_primes[hmap->power]; ++i) {
+ j = 0;
+ HXlist_for_each_entry(hnode, &hmap->bk_array[i], anchor)
+ ++j;
+ if (verbose)
+ printf("%u,", j);
+ /*
+ * The --j thing looks a little odd on review, but actually
+ * just does j=abs(1-j), but unlike abs, can handle a range
+ * nearly as large as unsigned int, were it to use something
+ * like j==(unsigned int)-1 instead of j<0.
+ *
+ * j=0 => j=-1 => j=+1
+ * j=1 => j= 0 => j= 0
+ * j=2 => j=+1 => j=+1
+ */
+ --j;
+ if (j < 0)
+ j = -j;
+ f += j;
+ }
+ if (verbose)
+ printf("}\n");
+ /* Ignore buckets that must logically be empty (pigeonhole principle) */
+ f -= HXhash_primes[hmap->power] - hmap->super.items;
+ /*
+ * Since we counted both underpopulation (0 elements in a bucket) as
+ * well as overpopulation (more than 1 element in a bucket), @f needs
+ * to be divided by two, making it f/(2*(e-1)).
+ */
+ /* Now return % */
+ return static_cast(double, 50 * f) / (hmap->super.items - 1);
+}
+
+/**
+ * Test one hash function with different keys and check agglomeration index.
+ */
+static void tmap_hmap_test_1a(const char *map_type,
+ unsigned long (*hash_fn)(const void *, size_t), unsigned int max_power)
+{
+ struct HXmap_ops intstr_ops = {
+ .k_compare = tmap_strtolcmp,
+ .k_hash = hash_fn,
+ };
+ struct HXmap_ops words_ops = {
+ .k_hash = hash_fn,
+ };
+ unsigned int power;
+ union HXpoly u;
+
+ for (power = 1; power <= max_power; ++power) {
+ u.map = HXmap_init5(HXMAPT_HASH, HXMAP_SCKEY,
+ &intstr_ops, 0, 0);
+ tmap_new_perfect_tree(u.map, power, 2);
+ tmap_printf("%s, intstr, %u items/%u buckets, "
+ "agglomeration: %.2f%%\n", map_type,
+ u.map->items, HXhash_primes[u.hmap->power],
+ hmap_agg_index(u.hmap, false));
+ HXmap_free(u.map);
+ }
+
+ u.map = HXmap_init5(HXMAPT_HASH, HXMAP_SCKEY, &words_ops, 0, 0);
+ while (u.map->items < 1 << max_power) {
+ /* Fill up just right up to the maximum load */
+ tmap_add_rand(u.map, u.hmap->max_load - u.map->items);
+ tmap_printf("%s, words, %u items/%u buckets, "
+ "agglomeration: %.2f%%\n", map_type,
+ u.map->items, HXhash_primes[u.hmap->power],
+ hmap_agg_index(u.hmap, false));
+ /* trigger resize */
+ tmap_add_rand(u.map, 1);
+ tmap_printf("%s, words, %u items/%u buckets, "
+ "agglomeration: %.2f%%\n", map_type,
+ u.map->items, HXhash_primes[u.hmap->power],
+ hmap_agg_index(u.hmap, false));
+ }
+ HXmap_free(u.map);
+}
+
+/**
+ * tmap_hmap_test_1 - test distributedness of elements
+ */
+static void tmap_hmap_test_1(void)
+{
+ static const unsigned int max_power = 15;
+
+ tmap_printf("HMAP test 1A: Hashmap distribution\n");
+ tmap_ipush();
+ tmap_hmap_test_1a("DJB2", HXhash_djb2, max_power);
+ tmap_hmap_test_1a("JL3", HXhash_jlookup3s, max_power);
+ tmap_ipop();
+}
+
+static void __rbt_walk_tree(const struct HXrbtree_node *node,
+ char *buf, size_t s)
+{
+ bool has_children = node->sub[0] != NULL || node->sub[1] != NULL;
+ HX_strlcat(buf, node->skey, s);
+
+ if (node->color == RBT_BLACK)
+ HX_strlcat(buf, "%b", s);
+ if (has_children)
+ HX_strlcat(buf, "(" /* ) */, s);
+ if (node->sub[0] != NULL)
+ __rbt_walk_tree(node->sub[0], buf, s);
+ if (node->sub[1] != NULL) {
+ HX_strlcat(buf, ",", s);
+ __rbt_walk_tree(node->sub[1], buf, s);
+ }
+ if (has_children)
+ HX_strlcat(buf, /* ( */ ")", s);
+}
+
+/**
+ * rbt_walk_tree - walk the tree and provide a string suitable for texitree
+ * @node: node of an rbtree to start diving at
+ * @buf: buffer for texitree representation
+ * @size: size for @buf
+ */
+static void rbt_walk_tree(const struct HXrbtree_node *node,
+ char *buf, size_t size)
+{
+ *buf = '\0';
+ __rbt_walk_tree(node, buf, size);
+}
+
+/**
+ * rbt_new_perfect_tree - generate a perfect binary tree
+ * @height: height of the desired tree
+ * @mult: multiplicator for node numbers
+ *
+ * Produces a tree of desired height with exactly 2^height-1 nodes.
+ */
+static struct HXmap *rbt_new_perfect_tree(unsigned int height,
+ unsigned int mult)
+{
+ struct HXmap *tree =
+ HXmap_init5(HXMAPT_RBTREE, HXMAP_SCKEY, &tmap_nstr_ops, 0, 0);
+ tmap_new_perfect_tree(tree, height, mult);
+ return tree;
+}
+
+static unsigned int rbt_tree_height(const struct HXrbtree_node *node)
+{
+ unsigned int a = 1, b = 1;
+ if (node->sub[0] != NULL)
+ a += rbt_tree_height(node->sub[0]);
+ if (node->sub[1] != NULL)
+ b += rbt_tree_height(node->sub[1]);
+ return (a > b) ? a : b;
+}
+
+static void rbt_height_check(const struct HXrbtree *tree)
+{
+ double min, max, avg;
+ min = log(tree->super.items + 1) / log(2);
+ max = 2 * log(tree->super.items + 1) / log(2);
+ avg = log((pow(2, min) + pow(2, max)) / 2) / log(2);
+ tmap_ipush();
+ tmap_printf("%u items; height %u; min/avg/max %.2f/%.2f/%.2f\n",
+ tree->super.items, rbt_tree_height(tree->root),
+ min, avg, max);
+ tmap_ipop();
+}
+
+/**
+ * tmap_rbt_test_1 - basic rbt node layout tests
+ */
+static void tmap_rbt_test_1(void)
+{
+ union HXpoly u;
+ char buf[80];
+
+ tmap_printf("RBT test 1A: Creating tree with 7 nodes (height 3)\n");
+ u.map = rbt_new_perfect_tree(3, 2);
+
+ tmap_printf("RBT test 1B: Manual traverse\n");
+ rbt_walk_tree(u.rbt->root, buf, sizeof(buf));
+
+ tmap_printf("RBT test 1C: Check for correct positions and colors\n");
+ tmap_expect(buf, "8%b(4%b(2,6),12%b(10,14))");
+
+ /* 8
+ * / \
+ * 4 12
+ * / \ / \
+ * 2 6 10 14
+ * /
+ * 9
+ */
+ tmap_printf("RBT test 1D: Node insertion and test for positions/colors\n");
+ HXmap_add(u.map, "9", NULL);
+ rbt_walk_tree(u.rbt->root, buf, sizeof(buf));
+ tmap_expect(buf, "8%b(4%b(2,6),12(10%b(9),14%b))");
+
+ tmap_printf("RBT test 1E: Height check\n");
+ rbt_height_check(u.rbt);
+
+ tmap_printf("RBT test 1G: Node deletion\n");
+ HXmap_del(u.map, "8");
+ rbt_walk_tree(u.rbt->root, buf, sizeof(buf));
+ tmap_expect(buf, "9%b(4%b(2,6),12(10%b,14%b))");
+
+ /* 9 (8 replaced by its in-order successor 9)
+ * / \
+ * 4 12
+ * / \ / \
+ * 2 6 10 14
+ */
+ HXmap_free(u.map);
+}
+
+/**
+ * rbt_no_2red_children - verify rbtree rule
+ * @node: subtree to verify
+ *
+ * Verify that there are no red nodes with red children.
+ */
+static bool rbt_no_2red_children(const struct HXrbtree_node *node)
+{
+ if (node->sub[RBT_LEFT] != NULL) {
+ if (node->color == RBT_RED &&
+ node->sub[RBT_LEFT]->color == RBT_RED)
+ return false;
+ if (!rbt_no_2red_children(node->sub[RBT_LEFT]))
+ return false;
+ }
+ if (node->sub[RBT_RIGHT] != NULL) {
+ if (node->color == RBT_RED &&
+ node->sub[RBT_RIGHT]->color == RBT_RED)
+ return false;
+ if (!rbt_no_2red_children(node->sub[RBT_RIGHT]))
+ return false;
+ }
+ return true;
+}
+
+/**
+ * rbt_black_height - calculate the black height of a tree
+ * @node: subtree to find the black height for
+ *
+ * Returns the black height, or -1 if the black height is not consistent.
+ */
+static int rbt_black_height(const struct HXrbtree_node *node)
+{
+ int lh = 0, rh = 0;
+
+ if (node->sub[RBT_LEFT] != NULL)
+ if ((lh = rbt_black_height(node->sub[RBT_LEFT])) == -1)
+ return -1;
+ if (node->sub[RBT_RIGHT] != NULL)
+ if ((rh = rbt_black_height(node->sub[RBT_RIGHT])) == -1)
+ return -1;
+ if (node->sub[RBT_LEFT] != NULL && node->sub[RBT_RIGHT] != NULL)
+ if (lh != rh)
+ return -1;
+ if (node->sub[RBT_LEFT] != NULL)
+ return lh + (node->color == RBT_BLACK);
+ else
+ return rh + (node->color == RBT_BLACK);
+}
+
+static bool rbt_verify_tree(const struct HXrbtree_node *root)
+{
+ /* Root is black */
+ if (root->color != RBT_BLACK) {
+ tmap_printf("Root is not black\n");
+ return false;
+ }
+ /* A red node may not have any red children */
+ if (!rbt_no_2red_children(root)) {
+ tmap_printf("Red node may not have red children violated\n");
+ return false;
+ }
+ /* Black height must be consistent */
+ if (rbt_black_height(root) < 0) {
+ tmap_printf("Black height violated\n");
+ return false;
+ }
+ return true;
+}
+
+/**
+ * rbt_peel_tree - slowly destroy tree and check characteristics
+ * @tree: the object to disseminate
+ * @range: original number of elements in the tree
+ */
+static void rbt_peel_tree(union HXpoly u, unsigned int range)
+{
+ unsigned int left = 1;
+
+ while (u.map->items != 0) {
+ uintptr_t number = tmap_smart_rand(&left, &range);
+
+ HXmap_del(u.map, reinterpret_cast(const void *, number));
+ if (errno == -ENOENT)
+ continue;
+ if (u.map->items == 0)
+ break;
+ if (!rbt_verify_tree(u.rbt->root))
+ return;
+ }
+}
+
+static void tmap_rbt_test_7(void)
+{
+ unsigned int i, elems, order, left, right;
+ union HXpoly u;
+ int ret;
+
+ tmap_printf("RBT test 7: AMOV/DMOV\n");
+ tmap_ipush();
+ u.map = HXmap_init(HXMAPT_RBTREE, 0);
+ for (order = 2; order <= 10; ++order) {
+ elems = (1 << order) - 1;
+ tmap_printf("Tree of order %u [e=%u]\n", order, elems);
+
+ /* Build a random tree */
+ left = 1;
+ right = elems + 1;
+ for (i = 0; i < elems; ++i) {
+ uintptr_t z = tmap_smart_rand(&left, &right);
+
+ ret = HXmap_add(u.map,
+ reinterpret_cast(const void *, z), NULL);
+ if (ret == -EEXIST)
+ --i;
+ if (!rbt_verify_tree(u.rbt->root))
+ tmap_printf("Verification failed\n");
+ }
+ /* Dismantle. */
+ rbt_height_check(u.rbt);
+ rbt_peel_tree(u, elems + 1);
+ }
+ tmap_ipop();
+ HXmap_free(u.map);
+}
+
+static void tmap_zero(void)
+{
+ struct HXmap *b;
+
+ b = HXmap_init(HXMAPT_DEFAULT, HXMAP_CKEY | HXMAP_CDATA);
+ if (b != NULL)
+ fprintf(stderr, "eek!\n");
+ b = HXmap_init(HXMAPT_DEFAULT, HXMAP_CKEY);
+ if (b != NULL)
+ fprintf(stderr, "eek!\n");
+}
+
+int main(void)
+{
+ if (HX_init() <= 0)
+ abort();
+
+ tmap_zero();
+
+ tmap_printf("* HXhashmap\n");
+ tmap_generic_tests(HXMAPT_HASH, HXhash_djb2, "DJB2");
+ tmap_generic_tests(HXMAPT_HASH, HXhash_jlookup3s, "JL3");
+ tmap_hmap_test_1();
+
+ tmap_printf("\n* RBtree\n");
+ tmap_generic_tests(HXMAPT_RBTREE, NULL, "<NONE>");
+ tmap_rbt_test_1();
+ tmap_rbt_test_7();
+
+ HX_exit();
+ return EXIT_SUCCESS;
+}