summaryrefslogtreecommitdiff
path: root/cesar/lib/test/set/src/test_set.c
diff options
context:
space:
mode:
Diffstat (limited to 'cesar/lib/test/set/src/test_set.c')
-rw-r--r--cesar/lib/test/set/src/test_set.c362
1 files changed, 362 insertions, 0 deletions
diff --git a/cesar/lib/test/set/src/test_set.c b/cesar/lib/test/set/src/test_set.c
new file mode 100644
index 0000000000..971c699cec
--- /dev/null
+++ b/cesar/lib/test/set/src/test_set.c
@@ -0,0 +1,362 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file src/test_set.c
+ * \brief Set test.
+ * \ingroup test
+ */
+#include "common/std.h"
+
+#include "lib/test.h"
+#include "lib/rnd.h"
+#include "lib/set.h"
+
+#define DEBUG_PRINT 0
+
+#if DEBUG_PRINT
+# include <stdio.h>
+# define NB_NODES 8
+# define NB_ITER 100
+# define NOT_TOO_BIG(x) ((x) & (NB_NODES * 2 - 1))
+#elif DEBUG
+# define NB_NODES 16384
+# define NB_ITER 10000
+# define NOT_TOO_BIG(x) (x)
+#else
+# define NB_NODES 131072
+# define NB_ITER 1000000
+# define NOT_TOO_BIG(x) (x)
+#endif
+
+/** Set node with an u32 data. */
+struct set_node_u32_t
+{
+ set_node_t node;
+ u32 data;
+};
+typedef struct set_node_u32_t set_node_u32_t;
+
+/**
+ * Comparison function for an u32 node.
+ * \param l left hand node
+ * \param r right hand node
+ * \return true iff left is lesser than right
+ */
+static bool
+set_u32_less (set_node_t *l, set_node_t *r)
+{
+ u32 ld, rd;
+ dbg_assert (l);
+ dbg_assert (r);
+ ld = PARENT_OF (set_node_u32_t, node, l)->data;
+ rd = PARENT_OF (set_node_u32_t, node, r)->data;
+ return ld < rd;
+}
+
+/**
+ * Check a node and recurse.
+ * \param t test context
+ * \param node node to check
+ * \param depth tree depth
+ * \param less comparison function
+ * \return tree size
+ */
+static uint
+set_check_node (test_t t, set_node_t *node, uint *depth, set_node_less_t less)
+{
+ test_within (t);
+ uint size, ldepth, rdepth;
+ dbg_assert (node && node != node->left);
+ dbg_assert (depth);
+ /* AA-tree structure checks. */
+ test_fail_unless (node->level > node->right->right->level);
+ test_fail_unless (node->level == node->left->level + 1);
+ test_fail_unless (node->level == node->right->level
+ || node->level == node->right->level + 1);
+ test_fail_unless (node->left == node->left->left
+ || node->left->father == node);
+ test_fail_unless (node->right == node->right->left
+ || node->right->father == node);
+ /* Binary search tree checks & stats. */
+ dbg_assert (node->left);
+ dbg_assert (node->right);
+ size = 1;
+ ldepth = rdepth = 0;
+ if (node->left != node->left->left)
+ {
+ test_fail_unless (less (node->left, node));
+ size += set_check_node (t, node->left, &ldepth, less);
+ }
+ if (node->right != node->right->left)
+ {
+ test_fail_unless (less (node, node->right));
+ size += set_check_node (t, node->right, &rdepth, less);
+ }
+ *depth = MAX (ldepth, rdepth) + 1;
+ return size;
+}
+
+/**
+ * Recursively check a tree.
+ * \param t test context
+ * \param set the tree to check
+ * \param depth tree depth
+ * \return tree size
+ */
+uint
+set_check (test_t t, set_t *set, uint *depth)
+{
+ test_within (t);
+ dbg_assert (set);
+ dbg_assert (depth);
+ if (set->root == set->root->left)
+ {
+ *depth = 0;
+ test_fail_unless (set_empty (set));
+ return 0;
+ }
+ else
+ {
+ test_fail_unless (!set_empty (set));
+ return set_check_node (t, set->root, depth, set->less);
+ }
+}
+
+#if DEBUG_PRINT
+
+/**
+ * Travel the tree at the \a p depth and print.
+ * \param node current node
+ * \param size number of characters available
+ * \param p depth to print
+ * \param c current recursion depth
+ */
+static void
+set_print_nodes (set_node_t *node, uint size, uint p, uint c)
+{
+ dbg_assert (node);
+ dbg_assert (p >= c);
+ if (p == c)
+ {
+ if (node->left == node)
+ {
+ printf ("%*s", size, " ");
+ }
+ else
+ {
+ uint before = (size + 1) / 2;
+ uint after = size - before;
+ uint data = PARENT_OF (set_node_u32_t, node, node)->data;
+ uint level = node->level;
+ /* ASCII codes... */
+#define GREY "\e[30;1m"
+#define BLACK "\e[0m"
+ printf ("%*u" GREY "%-*u" BLACK, before, data, after, level);
+ }
+ }
+ else
+ {
+ set_print_nodes (node->left, size, p, c + 1);
+ set_print_nodes (node->right, size, p, c + 1);
+ }
+}
+
+/**
+ * Print a tree.
+ * \param set tree to print
+ * \param depth tree depth
+ */
+static void
+set_print (set_t *set, uint depth)
+{
+ uint i, size;
+ dbg_assert (set);
+ printf ("depth: %d\n", depth);
+ /* Screen size is limited... */
+ size = 4 << (MIN (depth, 5u) - 1);
+ for (i = 0; i < MIN (depth, 6u); i++)
+ {
+ set_print_nodes (set->root, size / (1 << i), i, 0);
+ printf ("\n");
+ }
+ if (depth > 6u)
+ printf ("...\n");
+}
+
+#else /* !DEBUG_PRINT */
+# define set_print(set, depth)
+#endif /* !DEBUG_PRINT */
+
+void
+set_basic_test_case (test_t t)
+{
+ uint i, maxdepth, depth;
+ u64 sumdepth;
+ lib_rnd_t rnd[1];
+ set_t set;
+ set_node_u32_t nodes[NB_NODES];
+ test_case_begin (t, "basic");
+ lib_rnd_init (rnd, 1234);
+ /* Initialise. */
+ set_init (&set, set_u32_less);
+ for (i = 0; i < COUNT (nodes) / 2; i++)
+ {
+ set_node_init (&nodes[i].node);
+ nodes[i].data = i;
+ }
+ for (; i < COUNT (nodes); i++)
+ {
+ set_node_init (&nodes[i].node);
+ /* Ensure there is no duplicates. */
+ nodes[i].data = NOT_TOO_BIG ((lib_rnd32 (rnd) & ~(NB_NODES - 1)) | i);
+ }
+ /* Empty set tests. */
+ test_begin (t, "empty")
+ {
+ test_fail_unless (set_empty (&set));
+ test_fail_unless (set_begin (&set) == set_end (&set));
+ } test_end;
+ /* Insert. */
+ test_begin (t, "insert")
+ {
+ maxdepth = 0;
+ test_fail_unless (0 == set_check (t, &set, &depth));
+ for (i = 0; i < COUNT (nodes); i++)
+ {
+ test_fail_unless (set_insert (&set, &nodes[i].node));
+ if (DEBUG)
+ {
+ test_fail_unless (i + 1 == set_check (t, &set, &depth));
+ if (maxdepth < depth)
+ maxdepth = depth;
+ }
+ set_print (&set, depth);
+ }
+ if (DEBUG)
+ test_verbose_print ("count = %d, max depth = %d", COUNT (nodes),
+ maxdepth);
+ } test_end;
+ /* Insert duplicates, should be denied. */
+ test_begin (t, "insert dup")
+ {
+ set_node_u32_t dup;
+ set_node_init (&dup.node);
+ for (i = 0; i < COUNT (nodes); i++)
+ {
+ dup.data = nodes[i].data;
+ test_fail_if (set_insert (&set, &dup.node), "dup accepted");
+ }
+ } test_end;
+ /* Find nodes. */
+ test_begin (t, "find nodes")
+ {
+ for (i = 0; i < NB_ITER; i++)
+ {
+ set_node_u32_t k;
+ set_node_init (&k.node);
+ if (lib_rnd_flip_coin (rnd, LIB_RND_RATIO (0.5)))
+ {
+ /* Node in the set. */
+ set_node_u32_t *n;
+ n = &nodes[lib_rnd_uniform (rnd, NB_NODES)];
+ k.data = n->data;
+ test_fail_unless (set_find (&set, &k.node) == &n->node);
+ }
+ else
+ {
+ /* Node not in the set. */
+ u32 r;
+ do {
+ r = lib_rnd32 (rnd);
+ } while (nodes[r & (NB_NODES - 1)].data == r);
+ k.data = r;
+ test_fail_unless (set_find (&set, &k.node) == NULL);
+ }
+ }
+ } test_end;
+ /* Now, remove a node and insert it back. */
+ test_begin (t, "remove and insert")
+ {
+ sumdepth = 0;
+ maxdepth = 0;
+ for (i = 0; i < NB_ITER; i++)
+ {
+ set_node_u32_t *n, k;
+ u32 r;
+ set_node_init (&k.node);
+ n = &nodes[lib_rnd_uniform (rnd, NB_NODES)];
+ do {
+ r = NOT_TOO_BIG (lib_rnd32 (rnd));
+ k.data = r;
+ } while (set_find (&set, &k.node));
+ /* Remove. */
+ set_remove (&set, &n->node);
+ if (DEBUG)
+ {
+ test_fail_unless (COUNT (nodes) - 1
+ == set_check (t, &set, &depth));
+ if (maxdepth < depth)
+ maxdepth = depth;
+ }
+ set_print (&set, depth);
+ /* Insert. */
+ n->data = r;
+ test_fail_unless (set_insert (&set, &n->node));
+ if (DEBUG)
+ {
+ test_fail_unless (COUNT (nodes)
+ == set_check (t, &set, &depth));
+ if (maxdepth < depth)
+ maxdepth = depth;
+ sumdepth += depth;
+ }
+ set_print (&set, depth);
+ }
+ if (DEBUG)
+ test_verbose_print ("count = %d, avg depth = %d, max depth = %d",
+ COUNT (nodes), (uint) (sumdepth / NB_ITER),
+ maxdepth);
+ } test_end;
+ /* Check order. */
+ test_begin (t, "order")
+ {
+ uint size, last, data;
+ set_node_t *n;
+ n = set_begin (&set);
+ test_fail_if (!n || n == set_end (&set));
+ last = PARENT_OF (set_node_u32_t, node, n)->data;
+ size = 1;
+ for (n = set_next (&set, n); n != set_end (&set);
+ n = set_next (&set, n))
+ {
+ test_fail_unless (n);
+ data = PARENT_OF (set_node_u32_t, node, n)->data;
+ test_fail_unless (last < data, "broken order");
+ last = data;
+ size++;
+ }
+ test_fail_unless (size == COUNT (nodes));
+ } test_end;
+}
+
+void
+set_test_suite (test_t t)
+{
+ test_suite_begin (t, "set");
+ set_basic_test_case (t);
+}
+
+int
+main (int argc, char **argv)
+{
+ test_t t;
+ test_init (t, argc, argv);
+ set_test_suite (t);
+ test_result (t);
+ return test_nb_failed (t) == 0 ? 0 : 1;
+}