X-Git-Url: https://git.octo.it/?a=blobdiff_plain;f=src%2Fdaemon%2Futils_avltree_test.c;h=4be49416d7ef0d3f273c6e475c3fe5d8e8b97e10;hb=84502d3824a9a2e5585fc7f000c1b2e23953d212;hp=150dd1b5b8a8476c98a6fefdc01e9c5761ca02b7;hpb=f876292e5ce4be40ab5b031b2bcfb347f00da1f8;p=collectd.git

diff --git a/src/daemon/utils_avltree_test.c b/src/daemon/utils_avltree_test.c
index 150dd1b5..4be49416 100644
--- a/src/daemon/utils_avltree_test.c
+++ b/src/daemon/utils_avltree_test.c
@@ -24,129 +24,157 @@
  *   Florian octo Forster <octo at collectd.org>
  */
 
-#include "common.h" /* STATIC_ARRAY_SIZE */
 #include "collectd.h"
+#include "common.h" /* STATIC_ARRAY_SIZE */
 
 #include "testing.h"
 #include "utils_avltree.h"
 
-static int compare_total_count = 0;
-#define RESET_COUNTS() do { compare_total_count = 0; } while (0)
+static int compare_total_count;
+
+#define RESET_COUNTS()                                                         \
+  do {                                                                         \
+    compare_total_count = 0;                                                   \
+  } while (0)
 
-static int compare_callback (void const *v0, void const *v1)
-{
-  assert (v0 != NULL);
-  assert (v1 != NULL);
+static int compare_callback(void const *v0, void const *v1) {
+  assert(v0 != NULL);
+  assert(v1 != NULL);
 
   compare_total_count++;
-  return (strcmp (v0, v1));
+  return strcmp(v0, v1);
 }
 
-DEF_TEST(success)
-{
-  struct {
-    char *key;
-    char *value;
-  } cases[] = {
-    {"Eeph7chu", "vai1reiV"},
-    {"igh3Paiz", "teegh1Ee"},
-    {"caip6Uu8", "ooteQu8n"},
-    {"Aech6vah", "AijeeT0l"},
-    {"Xah0et2L", "gah8Taep"},
-    {"BocaeB8n", "oGaig8io"},
-    {"thai8AhM", "ohjeFo3f"},
-    {"ohth6ieC", "hoo8ieWo"},
-    {"aej7Woow", "phahuC2s"},
-    {"Hai8ier2", "Yie6eimi"},
-    {"phuXi3Li", "JaiF7ieb"},
-    {"Shaig5ef", "aihi5Zai"},
-    {"voh6Aith", "Oozaeto0"},
-    {"zaiP5kie", "seep5veM"},
-    {"pae7ba7D", "chie8Ojo"},
-    {"Gou2ril3", "ouVoo0ha"},
-    {"lo3Thee3", "ahDu4Zuj"},
-    {"Rah8kohv", "ieShoc7E"},
-    {"ieN5engi", "Aevou1ah"},
-    {"ooTe4OhP", "aingai5Y"},
+struct kv_t {
+  char *key;
+  char *value;
+};
+
+static int kv_compare(const void *a_ptr, const void *b_ptr) {
+  return strcmp(((struct kv_t *)a_ptr)->key, ((struct kv_t *)b_ptr)->key);
+}
+
+DEF_TEST(success) {
+  struct kv_t cases[] = {
+      {"Eeph7chu", "vai1reiV"}, {"igh3Paiz", "teegh1Ee"},
+      {"caip6Uu8", "ooteQu8n"}, {"Aech6vah", "AijeeT0l"},
+      {"Xah0et2L", "gah8Taep"}, {"BocaeB8n", "oGaig8io"},
+      {"thai8AhM", "ohjeFo3f"}, {"ohth6ieC", "hoo8ieWo"},
+      {"aej7Woow", "phahuC2s"}, {"Hai8ier2", "Yie6eimi"},
+      {"phuXi3Li", "JaiF7ieb"}, {"Shaig5ef", "aihi5Zai"},
+      {"voh6Aith", "Oozaeto0"}, {"zaiP5kie", "seep5veM"},
+      {"pae7ba7D", "chie8Ojo"}, {"Gou2ril3", "ouVoo0ha"},
+      {"lo3Thee3", "ahDu4Zuj"}, {"Rah8kohv", "ieShoc7E"},
+      {"ieN5engi", "Aevou1ah"}, {"ooTe4OhP", "aingai5Y"},
   };
 
+  struct kv_t sorted_cases[STATIC_ARRAY_SIZE(cases)];
+  memcpy(sorted_cases, cases, sizeof(cases));
+  qsort(sorted_cases, STATIC_ARRAY_SIZE(cases), sizeof(struct kv_t),
+        kv_compare);
+
   c_avl_tree_t *t;
 
-  RESET_COUNTS ();
-  CHECK_NOT_NULL (t = c_avl_create (compare_callback));
+  RESET_COUNTS();
+  CHECK_NOT_NULL(t = c_avl_create(compare_callback));
 
   /* insert */
-  for (size_t i = 0; i < STATIC_ARRAY_SIZE (cases); i++)
-  {
+  for (size_t i = 0; i < STATIC_ARRAY_SIZE(cases); i++) {
     char *key;
     char *value;
 
-    CHECK_NOT_NULL (key = strdup (cases[i].key));
-    CHECK_NOT_NULL (value = strdup (cases[i].value));
+    CHECK_NOT_NULL(key = strdup(cases[i].key));
+    CHECK_NOT_NULL(value = strdup(cases[i].value));
 
-    CHECK_ZERO (c_avl_insert (t, key, value));
-    EXPECT_EQ_INT ((int) (i + 1), c_avl_size (t));
+    CHECK_ZERO(c_avl_insert(t, key, value));
+    EXPECT_EQ_INT((int)(i + 1), c_avl_size(t));
   }
 
   /* Key already exists. */
-  for (size_t i = 0; i < STATIC_ARRAY_SIZE (cases); i++)
-    EXPECT_EQ_INT (1, c_avl_insert (t, cases[i].key, cases[i].value));
+  for (size_t i = 0; i < STATIC_ARRAY_SIZE(cases); i++)
+    EXPECT_EQ_INT(1, c_avl_insert(t, cases[i].key, cases[i].value));
 
   /* get */
-  for (size_t i = 0; i < STATIC_ARRAY_SIZE (cases); i++)
-  {
+  for (size_t i = 0; i < STATIC_ARRAY_SIZE(cases); i++) {
     char *value_ret = NULL;
 
-    CHECK_ZERO (c_avl_get (t, cases[i].key, (void *) &value_ret));
-    EXPECT_EQ_STR (cases[i].value, value_ret);
+    CHECK_ZERO(c_avl_get(t, cases[i].key, (void *)&value_ret));
+    EXPECT_EQ_STR(cases[i].value, value_ret);
   }
 
-  /* remove half */
-  for (size_t i = 0; i < STATIC_ARRAY_SIZE (cases) / 2; i++)
+  /* iterate forward */
   {
+    c_avl_iterator_t *iter = c_avl_get_iterator(t);
+    char *key;
+    char *value;
+    size_t i = 0;
+    while (c_avl_iterator_next(iter, (void **)&key, (void **)&value) == 0) {
+      EXPECT_EQ_STR(sorted_cases[i].key, key);
+      EXPECT_EQ_STR(sorted_cases[i].value, value);
+      i++;
+    }
+    c_avl_iterator_destroy(iter);
+    EXPECT_EQ_INT(i, STATIC_ARRAY_SIZE(cases));
+  }
+
+  /* iterate backward */
+  {
+    c_avl_iterator_t *iter = c_avl_get_iterator(t);
+    char *key;
+    char *value;
+    size_t i = 0;
+    while (c_avl_iterator_prev(iter, (void **)&key, (void **)&value) == 0) {
+      EXPECT_EQ_STR(sorted_cases[STATIC_ARRAY_SIZE(cases) - 1 - i].key, key);
+      EXPECT_EQ_STR(sorted_cases[STATIC_ARRAY_SIZE(cases) - 1 - i].value,
+                    value);
+      i++;
+    }
+    c_avl_iterator_destroy(iter);
+    EXPECT_EQ_INT(i, STATIC_ARRAY_SIZE(cases));
+  }
+
+  /* remove half */
+  for (size_t i = 0; i < STATIC_ARRAY_SIZE(cases) / 2; i++) {
     char *key = NULL;
     char *value = NULL;
 
-    int expected_size = (int) (STATIC_ARRAY_SIZE (cases) - (i + 1));
+    int expected_size = (int)(STATIC_ARRAY_SIZE(cases) - (i + 1));
 
-    CHECK_ZERO (c_avl_remove (t, cases[i].key, (void *) &key, (void *) &value));
+    CHECK_ZERO(c_avl_remove(t, cases[i].key, (void *)&key, (void *)&value));
 
-    EXPECT_EQ_STR (cases[i].key, key);
-    EXPECT_EQ_STR (cases[i].value, value);
+    EXPECT_EQ_STR(cases[i].key, key);
+    EXPECT_EQ_STR(cases[i].value, value);
 
-    free (key);
-    free (value);
+    free(key);
+    free(value);
 
-    EXPECT_EQ_INT (expected_size, c_avl_size (t));
+    EXPECT_EQ_INT(expected_size, c_avl_size(t));
   }
 
   /* pick the other half */
-  for (size_t i = STATIC_ARRAY_SIZE (cases) / 2; i < STATIC_ARRAY_SIZE (cases); i++)
-  {
+  for (size_t i = STATIC_ARRAY_SIZE(cases) / 2; i < STATIC_ARRAY_SIZE(cases);
+       i++) {
     char *key = NULL;
     char *value = NULL;
 
-    int expected_size = (int) (STATIC_ARRAY_SIZE (cases) - (i + 1));
+    int expected_size = (int)(STATIC_ARRAY_SIZE(cases) - (i + 1));
 
-    EXPECT_EQ_INT (expected_size + 1, c_avl_size (t));
-    EXPECT_EQ_INT (0, c_avl_pick (t, (void *) &key, (void *) &value));
+    EXPECT_EQ_INT(expected_size + 1, c_avl_size(t));
+    EXPECT_EQ_INT(0, c_avl_pick(t, (void *)&key, (void *)&value));
 
-    free (key);
-    free (value);
+    free(key);
+    free(value);
 
-    EXPECT_EQ_INT (expected_size, c_avl_size (t));
+    EXPECT_EQ_INT(expected_size, c_avl_size(t));
   }
 
-  c_avl_destroy (t);
+  c_avl_destroy(t);
 
-  return (0);
+  return 0;
 }
 
-int main (void)
-{
+int main(void) {
   RUN_TEST(success);
 
   END_TEST;
 }
-
-/* vim: set sw=2 sts=2 et : */