src/daemon/utils_avltree_test.c

   1 /**
   2  * collectd - src/tests/test_utils_avltree.c
   3  * Copyright (C) 2013       Florian octo Forster
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a
   6  * copy of this software and associated documentation files (the "Software"),
   7  * to deal in the Software without restriction, including without limitation
   8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9  * and/or sell copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in
  13  * all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21  * DEALINGS IN THE SOFTWARE.
  22  *
  23  * Authors:
  24  *   Florian octo Forster <octo at collectd.org>
  25  */
  26
  27 #include "collectd.h"
  28 #include "common.h" /* STATIC_ARRAY_SIZE */
  29
  30 #include "testing.h"
  31 #include "utils_avltree.h"
  32
  33 static int compare_total_count;
  34
  35 #define RESET_COUNTS()                                                         \
  36   do {                                                                         \
  37     compare_total_count = 0;                                                   \
  38   } while (0)
  39
  40 static int compare_callback(void const *v0, void const *v1) {
  41   assert(v0 != NULL);
  42   assert(v1 != NULL);
  43
  44   compare_total_count++;
  45   return strcmp(v0, v1);
  46 }
  47
  48 struct kv_t {
  49   char *key;
  50   char *value;
  51 };
  52
  53 static int kv_compare(const void *a_ptr, const void *b_ptr) {
  54   return strcmp(((struct kv_t *)a_ptr)->key, ((struct kv_t *)b_ptr)->key);
  55 }
  56
  57 DEF_TEST(success) {
  58   struct kv_t cases[] = {
  59       {"Eeph7chu", "vai1reiV"}, {"igh3Paiz", "teegh1Ee"},
  60       {"caip6Uu8", "ooteQu8n"}, {"Aech6vah", "AijeeT0l"},
  61       {"Xah0et2L", "gah8Taep"}, {"BocaeB8n", "oGaig8io"},
  62       {"thai8AhM", "ohjeFo3f"}, {"ohth6ieC", "hoo8ieWo"},
  63       {"aej7Woow", "phahuC2s"}, {"Hai8ier2", "Yie6eimi"},
  64       {"phuXi3Li", "JaiF7ieb"}, {"Shaig5ef", "aihi5Zai"},
  65       {"voh6Aith", "Oozaeto0"}, {"zaiP5kie", "seep5veM"},
  66       {"pae7ba7D", "chie8Ojo"}, {"Gou2ril3", "ouVoo0ha"},
  67       {"lo3Thee3", "ahDu4Zuj"}, {"Rah8kohv", "ieShoc7E"},
  68       {"ieN5engi", "Aevou1ah"}, {"ooTe4OhP", "aingai5Y"},
  69   };
  70
  71   struct kv_t sorted_cases[STATIC_ARRAY_SIZE(cases)];
  72   memcpy(sorted_cases, cases, sizeof(cases));
  73   qsort(sorted_cases, STATIC_ARRAY_SIZE(cases), sizeof(struct kv_t),
  74         kv_compare);
  75
  76   c_avl_tree_t *t;
  77
  78   RESET_COUNTS();
  79   CHECK_NOT_NULL(t = c_avl_create(compare_callback));
  80
  81   /* insert */
  82   for (size_t i = 0; i < STATIC_ARRAY_SIZE(cases); i++) {
  83     char *key;
  84     char *value;
  85
  86     CHECK_NOT_NULL(key = strdup(cases[i].key));
  87     CHECK_NOT_NULL(value = strdup(cases[i].value));
  88
  89     CHECK_ZERO(c_avl_insert(t, key, value));
  90     EXPECT_EQ_INT((int)(i + 1), c_avl_size(t));
  91   }
  92
  93   /* Key already exists. */
  94   for (size_t i = 0; i < STATIC_ARRAY_SIZE(cases); i++)
  95     EXPECT_EQ_INT(1, c_avl_insert(t, cases[i].key, cases[i].value));
  96
  97   /* get */
  98   for (size_t i = 0; i < STATIC_ARRAY_SIZE(cases); i++) {
  99     char *value_ret = NULL;
 100
 101     CHECK_ZERO(c_avl_get(t, cases[i].key, (void *)&value_ret));
 102     EXPECT_EQ_STR(cases[i].value, value_ret);
 103   }
 104
 105   /* iterate forward */
 106   {
 107     c_avl_iterator_t *iter = c_avl_get_iterator(t);
 108     char *key;
 109     char *value;
 110     size_t i = 0;
 111     while (c_avl_iterator_next(iter, (void **)&key, (void **)&value) == 0) {
 112       EXPECT_EQ_STR(sorted_cases[i].key, key);
 113       EXPECT_EQ_STR(sorted_cases[i].value, value);
 114       i++;
 115     }
 116     c_avl_iterator_destroy(iter);
 117     EXPECT_EQ_INT(i, STATIC_ARRAY_SIZE(cases));
 118   }
 119
 120   /* iterate backward */
 121   {
 122     c_avl_iterator_t *iter = c_avl_get_iterator(t);
 123     char *key;
 124     char *value;
 125     size_t i = 0;
 126     while (c_avl_iterator_prev(iter, (void **)&key, (void **)&value) == 0) {
 127       EXPECT_EQ_STR(sorted_cases[STATIC_ARRAY_SIZE(cases) - 1 - i].key, key);
 128       EXPECT_EQ_STR(sorted_cases[STATIC_ARRAY_SIZE(cases) - 1 - i].value,
 129                     value);
 130       i++;
 131     }
 132     c_avl_iterator_destroy(iter);
 133     EXPECT_EQ_INT(i, STATIC_ARRAY_SIZE(cases));
 134   }
 135
 136   /* remove half */
 137   for (size_t i = 0; i < STATIC_ARRAY_SIZE(cases) / 2; i++) {
 138     char *key = NULL;
 139     char *value = NULL;
 140
 141     int expected_size = (int)(STATIC_ARRAY_SIZE(cases) - (i + 1));
 142
 143     CHECK_ZERO(c_avl_remove(t, cases[i].key, (void *)&key, (void *)&value));
 144
 145     EXPECT_EQ_STR(cases[i].key, key);
 146     EXPECT_EQ_STR(cases[i].value, value);
 147
 148     free(key);
 149     free(value);
 150
 151     EXPECT_EQ_INT(expected_size, c_avl_size(t));
 152   }
 153
 154   /* pick the other half */
 155   for (size_t i = STATIC_ARRAY_SIZE(cases) / 2; i < STATIC_ARRAY_SIZE(cases);
 156        i++) {
 157     char *key = NULL;
 158     char *value = NULL;
 159
 160     int expected_size = (int)(STATIC_ARRAY_SIZE(cases) - (i + 1));
 161
 162     EXPECT_EQ_INT(expected_size + 1, c_avl_size(t));
 163     EXPECT_EQ_INT(0, c_avl_pick(t, (void *)&key, (void *)&value));
 164
 165     free(key);
 166     free(value);
 167
 168     EXPECT_EQ_INT(expected_size, c_avl_size(t));
 169   }
 170
 171   c_avl_destroy(t);
 172
 173   return 0;
 174 }
 175
 176 int main(void) {
 177   RUN_TEST(success);
 178
 179   END_TEST;
 180 }