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 */
27 #include "common.h" /* STATIC_ARRAY_SIZE */
28 #include "collectd.h"
30 #include "testing.h"
31 #include "utils_avltree.h"
33 static int compare_total_count = 0;
34 #define RESET_COUNTS() \
35 do { \
36 compare_total_count = 0; \
37 } while (0)
39 static int compare_callback(void const *v0, void const *v1) {
40 assert(v0 != NULL);
41 assert(v1 != NULL);
43 compare_total_count++;
44 return (strcmp(v0, v1));
45 }
47 DEF_TEST(success) {
48 struct {
49 char *key;
50 char *value;
51 } cases[] = {
52 {"Eeph7chu", "vai1reiV"}, {"igh3Paiz", "teegh1Ee"},
53 {"caip6Uu8", "ooteQu8n"}, {"Aech6vah", "AijeeT0l"},
54 {"Xah0et2L", "gah8Taep"}, {"BocaeB8n", "oGaig8io"},
55 {"thai8AhM", "ohjeFo3f"}, {"ohth6ieC", "hoo8ieWo"},
56 {"aej7Woow", "phahuC2s"}, {"Hai8ier2", "Yie6eimi"},
57 {"phuXi3Li", "JaiF7ieb"}, {"Shaig5ef", "aihi5Zai"},
58 {"voh6Aith", "Oozaeto0"}, {"zaiP5kie", "seep5veM"},
59 {"pae7ba7D", "chie8Ojo"}, {"Gou2ril3", "ouVoo0ha"},
60 {"lo3Thee3", "ahDu4Zuj"}, {"Rah8kohv", "ieShoc7E"},
61 {"ieN5engi", "Aevou1ah"}, {"ooTe4OhP", "aingai5Y"},
62 };
64 c_avl_tree_t *t;
66 RESET_COUNTS();
67 CHECK_NOT_NULL(t = c_avl_create(compare_callback));
69 /* insert */
70 for (size_t i = 0; i < STATIC_ARRAY_SIZE(cases); i++) {
71 char *key;
72 char *value;
74 CHECK_NOT_NULL(key = strdup(cases[i].key));
75 CHECK_NOT_NULL(value = strdup(cases[i].value));
77 CHECK_ZERO(c_avl_insert(t, key, value));
78 EXPECT_EQ_INT((int)(i + 1), c_avl_size(t));
79 }
81 /* Key already exists. */
82 for (size_t i = 0; i < STATIC_ARRAY_SIZE(cases); i++)
83 EXPECT_EQ_INT(1, c_avl_insert(t, cases[i].key, cases[i].value));
85 /* get */
86 for (size_t i = 0; i < STATIC_ARRAY_SIZE(cases); i++) {
87 char *value_ret = NULL;
89 CHECK_ZERO(c_avl_get(t, cases[i].key, (void *)&value_ret));
90 EXPECT_EQ_STR(cases[i].value, value_ret);
91 }
93 /* remove half */
94 for (size_t i = 0; i < STATIC_ARRAY_SIZE(cases) / 2; i++) {
95 char *key = NULL;
96 char *value = NULL;
98 int expected_size = (int)(STATIC_ARRAY_SIZE(cases) - (i + 1));
100 CHECK_ZERO(c_avl_remove(t, cases[i].key, (void *)&key, (void *)&value));
102 EXPECT_EQ_STR(cases[i].key, key);
103 EXPECT_EQ_STR(cases[i].value, value);
105 free(key);
106 free(value);
108 EXPECT_EQ_INT(expected_size, c_avl_size(t));
109 }
111 /* pick the other half */
112 for (size_t i = STATIC_ARRAY_SIZE(cases) / 2; i < STATIC_ARRAY_SIZE(cases);
113 i++) {
114 char *key = NULL;
115 char *value = NULL;
117 int expected_size = (int)(STATIC_ARRAY_SIZE(cases) - (i + 1));
119 EXPECT_EQ_INT(expected_size + 1, c_avl_size(t));
120 EXPECT_EQ_INT(0, c_avl_pick(t, (void *)&key, (void *)&value));
122 free(key);
123 free(value);
125 EXPECT_EQ_INT(expected_size, c_avl_size(t));
126 }
128 c_avl_destroy(t);
130 return (0);
131 }
133 int main(void) {
134 RUN_TEST(success);
136 END_TEST;
137 }