fix c_avl_iterator_prev (#2917)

utils_avltree: fix 'c_avl_iterator_prev()' and cover it by tests

diff --git a/src/daemon/utils_avltree.c b/src/daemon/utils_avltree.c
index 87568fb..568d68c 100644 (file)
--- a/src/daemon/utils_avltree.c
+++ b/src/daemon/utils_avltree.c
@@ -621,7 +621,7 @@ int c_avl_iterator_prev(c_avl_iterator_t *iter, void **key, void **value) {
     return -1;
 
   if (iter->node == NULL) {
-    for (n = iter->tree->root; n != NULL; n = n->left)
+    for (n = iter->tree->root; n != NULL; n = n->right)
       if (n->right == NULL)
         break;
     iter->node = n;

diff --git a/src/daemon/utils_avltree_test.c b/src/daemon/utils_avltree_test.c
index 3171246..4be4941 100644 (file)
--- a/src/daemon/utils_avltree_test.c
+++ b/src/daemon/utils_avltree_test.c
@@ -45,11 +45,17 @@ static int compare_callback(void const *v0, void const *v1) {
   return strcmp(v0, v1);
 }
 
+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 {
-    char *key;
-    char *value;
-  } cases[] = {
+  struct kv_t cases[] = {
       {"Eeph7chu", "vai1reiV"}, {"igh3Paiz", "teegh1Ee"},
       {"caip6Uu8", "ooteQu8n"}, {"Aech6vah", "AijeeT0l"},
       {"Xah0et2L", "gah8Taep"}, {"BocaeB8n", "oGaig8io"},
@@ -62,6 +68,11 @@ DEF_TEST(success) {
       {"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();
@@ -91,6 +102,37 @@ DEF_TEST(success) {
     EXPECT_EQ_STR(cases[i].value, value_ret);
   }
 
+  /* 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;