summaryrefslogtreecommitdiff
path: root/cesar/lib/test/heap/src/test_heap.c
diff options
context:
space:
mode:
Diffstat (limited to 'cesar/lib/test/heap/src/test_heap.c')
-rw-r--r--cesar/lib/test/heap/src/test_heap.c272
1 files changed, 272 insertions, 0 deletions
diff --git a/cesar/lib/test/heap/src/test_heap.c b/cesar/lib/test/heap/src/test_heap.c
new file mode 100644
index 0000000000..20e0d9ac14
--- /dev/null
+++ b/cesar/lib/test/heap/src/test_heap.c
@@ -0,0 +1,272 @@
+/* Cesar project {{{
+ *
+ * Copyright (C) 2007 Spidcom
+ *
+ * <<<Licence>>>
+ *
+ * }}} */
+/**
+ * \file test_heap.c
+ * \brief Test heap.
+ * \ingroup lib_test
+ */
+#include "common/std.h"
+#include "lib/rnd.h"
+#include "lib/heap.h"
+#include "lib/test.h"
+
+#if DEBUG
+# define NB_NODES 10000
+# define NB_ITER 10000
+#else
+# define NB_NODES 100000
+# define NB_ITER 100000000
+#endif
+
+/**
+ * Check heap structure.
+ * \param t test context
+ * \param heap the heap to check
+ * \return the number of elements
+ */
+static uint
+heap_check (test_t t, heap_t *heap)
+{
+ test_within (t);
+ uint n, depth, maxdepth;
+ heap_node_t *h;
+ h = heap_get_root (heap);
+ n = depth = maxdepth = 0;
+ while (h)
+ {
+ test_fail_unless (h != h->left && h != h->right);
+ test_fail_unless (!h->left || h->left->father == h);
+ test_fail_unless (!h->right || h->right->father == h);
+ if (h->left)
+ {
+ h = h->left;
+ depth++;
+ }
+ else if (h->right)
+ {
+ h = h->right;
+ depth++;
+ }
+ else
+ {
+ /* Go up... */
+ while (h)
+ {
+ test_fail_unless
+ (!h->father ||
+ !less_mod2p32 (PARENT_OF (heap_node_u32_t, node, h)->key,
+ PARENT_OF (heap_node_u32_t, node,
+ h->father)->key)
+ );
+ n++;
+ if (h->father && h->father->left == h && h->father->right)
+ {
+ /* ...and right if coming from left. */
+ h = h->father->right;
+ break;
+ }
+ else
+ {
+ h = h->father;
+ if (depth + 1 > maxdepth)
+ maxdepth = depth + 1;
+ depth--;
+ }
+ }
+ }
+ }
+ return n;
+}
+
+/**
+ * Maintain stats about right path length.
+ * \param heap the heap
+ * \param t test context
+ * \param min minimum path length
+ * \param max maximum path length
+ * \param sum sum of path length (to compute average)
+ */
+static void
+heap_stats (test_t t, heap_t *heap, uint *min, uint *max, unsigned long long *sum)
+{
+ test_within (t);
+ heap_node_t *n;
+ uint path_length;
+#if CONFIG_HEAP_LEFTIST
+ uint null_path_length = heap_get_root (heap)->null_path_length + 1;
+#endif
+ for (n = heap_get_root (heap), path_length = 0;
+ n;
+ n = n->right)
+ {
+#if CONFIG_HEAP_LEFTIST
+ test_fail_unless (null_path_length = n->null_path_length + 1);
+ null_path_length = n->null_path_length;
+#endif
+ path_length++;
+ }
+#if CONFIG_HEAP_LEFTIST
+ test_fail_unless (null_path_length == 1);
+#endif
+ *min = MIN (*min, path_length);
+ *max = MAX (*max, path_length);
+ *sum += path_length;
+}
+
+/**
+ * Return a limited random number.
+ * \param rnd rnd context.
+ * \return the random number.
+ *
+ * As we use a mod2p32 logic, all values should be distant no more than 2^31.
+ */
+static inline u32
+limited_rnd (lib_rnd_t *rnd)
+{
+ return 0xc0000000 + (lib_rnd32 (rnd) & 0x7fffffff);
+}
+
+void
+heap_basic_test_case (test_t t)
+{
+ uint i;
+ uint min = 0, max = 0;
+ unsigned long long sum = 0;
+ lib_rnd_t rnd;
+ heap_t heap, heap2;
+ heap_node_u32_t nodes[NB_NODES];
+ test_case_begin (t, "basic");
+ lib_rnd_init (&rnd, 1234);
+ /* Initialise heap & nodes. */
+ heap_init (&heap, &heap_node_u32_less_mod2p32);
+ heap_init (&heap2, &heap_node_u32_less_mod2p32);
+ for (i = 0; i < COUNT (nodes); i++)
+ heap_node_init (&nodes[i].node);
+ /* Insert them with random key. */
+ test_begin (t, "insert")
+ {
+ for (i = 0; i < COUNT (nodes) / 2; i++)
+ {
+ nodes[i].key = limited_rnd (&rnd);
+ heap_insert (&heap, &nodes[i].node);
+ test_fail_unless (DEBUG && i + 1 == heap_check (t, &heap));
+ }
+ for (i = 0; i < COUNT (nodes) / 2; i++)
+ {
+ uint j = i + COUNT (nodes) / 2;
+ nodes[j].key = limited_rnd (&rnd);
+ heap_insert (&heap2, &nodes[j].node);
+ test_fail_unless (DEBUG && i + 1 == heap_check (t, &heap2));
+ }
+ } test_end;
+ /* Merge. */
+ test_begin (t, "merge")
+ {
+ heap_merge (&heap, &heap2);
+ test_fail_unless (DEBUG && COUNT (nodes) == heap_check (t, &heap));
+ test_fail_unless (DEBUG && heap_empty (&heap2));
+ } test_end;
+ /* Remove a node and insert it back. */
+ test_begin (t, "remove and insert")
+ {
+ for (i = 0; i < NB_ITER; i++)
+ {
+ heap_node_u32_t *r;
+ if (lib_rnd_flip_coin (&rnd, LIB_RND_RATIO (0.8)))
+ {
+ if (lib_rnd_flip_coin (&rnd, LIB_RND_RATIO (0.5)))
+ {
+ r = PARENT_OF (heap_node_u32_t, node,
+ heap_get_root (&heap));
+ heap_remove_root (&heap);
+ }
+ else
+ {
+ r = &nodes[lib_rnd_uniform (&rnd, COUNT (nodes))];
+ heap_remove (&heap, &r->node);
+ }
+ test_fail_unless
+ (DEBUG && COUNT (nodes) - 1 == heap_check (t, &heap));
+ r->key = limited_rnd (&rnd);
+ heap_insert (&heap, &r->node);
+ }
+ else
+ {
+ if (lib_rnd_flip_coin (&rnd, LIB_RND_RATIO (0.5)))
+ {
+ r = PARENT_OF (heap_node_u32_t, node,
+ heap_get_root (&heap));
+ }
+ else
+ {
+ r = &nodes[lib_rnd_uniform (&rnd, COUNT (nodes))];
+ }
+ if (lib_rnd_flip_coin (&rnd, LIB_RND_RATIO (0.5)))
+ {
+ r->key = limited_rnd (&rnd);
+ }
+ else
+ {
+ r->key += (lib_rnd32 (&rnd) & 0xff) - 0x80;
+ if (r->key < 0xc0000000 && r->key >= 0x80000000)
+ r->key = 0xc0000000;
+ else if (r->key > 0x3fffffff && r->key < 0x80000000)
+ r->key = 0x3fffffff;
+ }
+ heap_adjust (&heap, &r->node);
+ }
+ test_fail_unless
+ (DEBUG && COUNT (nodes) == heap_check (t, &heap));
+ if (DEBUG)
+ heap_stats (t, &heap, &min, &max, &sum);
+ }
+ } test_end;
+ /* Remove all nodes and check order. */
+ test_begin (t, "check order")
+ {
+ i = COUNT (nodes);
+ u32 last = PARENT_OF (heap_node_u32_t, node,
+ heap_get_root (&heap))->key;
+ while (!heap_empty (&heap))
+ {
+ heap_node_u32_t *r = PARENT_OF (heap_node_u32_t, node,
+ heap_get_root (&heap));
+ test_fail_unless (!less_mod2p32 (r->key, last));
+ last = r->key;
+ heap_remove_root (&heap);
+ i--;
+ test_fail_unless (DEBUG && i == heap_check (t, &heap));
+ }
+ } test_end;
+ /* Print stats about right path length. */
+ if (DEBUG)
+ {
+ test_begin (t, "check depth")
+ {
+ test_verbose_print ("min=%d, max=%d, avg=%d", min, max,
+ (uint) (sum / NB_ITER));
+ } test_end;
+ }
+}
+
+void
+heap_test_suite (test_t t)
+{
+ test_suite_begin (t, "heap");
+ heap_basic_test_case (t);
+}
+
+int
+main (int argc, char **argv)
+{
+ test_t t;
+ test_init (t, argc, argv);
+ heap_test_suite (t);
+ test_result (t);
+ return test_nb_failed (t) == 0 ? 0 : 1;
+}