3526e4107df078c5fa2f3aa99913f25659bccbf3
1 /*
2 * SysDB - t/unit/utils/avltree_test.c
3 * Copyright (C) 2015 Sebastian 'tokkee' Harl <sh@tokkee.org>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
17 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
18 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
19 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
22 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
23 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
24 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
25 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
28 #include "utils/avltree.h"
29 #include "libsysdb_test.h"
31 #include <check.h>
33 static sdb_avltree_t *tree;
35 static void
36 setup(void)
37 {
38 tree = sdb_avltree_create(NULL);
39 fail_unless(tree != NULL,
40 "sdb_avltree_create() = NULL; expected AVL-tree object");
41 } /* setup */
43 static void
44 teardown(void)
45 {
46 sdb_avltree_destroy(tree);
47 tree = NULL;
48 } /* teardown */
50 /* 'a' thru 'o' */
51 static sdb_object_t test_data[] = {
52 SDB_OBJECT_STATIC("h"),
53 SDB_OBJECT_STATIC("j"),
54 SDB_OBJECT_STATIC("i"),
55 SDB_OBJECT_STATIC("f"),
56 SDB_OBJECT_STATIC("e"),
57 SDB_OBJECT_STATIC("g"),
58 SDB_OBJECT_STATIC("k"),
59 SDB_OBJECT_STATIC("l"),
60 SDB_OBJECT_STATIC("m"),
61 SDB_OBJECT_STATIC("n"),
62 SDB_OBJECT_STATIC("o"),
63 SDB_OBJECT_STATIC("d"),
64 SDB_OBJECT_STATIC("c"),
65 SDB_OBJECT_STATIC("b"),
66 SDB_OBJECT_STATIC("a"),
67 };
69 static char *unused_names[] = { "x", "y", "z" };
71 static void
72 populate(void)
73 {
74 size_t i;
75 for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i)
76 sdb_avltree_insert(tree, &test_data[i]);
77 } /* populate */
79 START_TEST(test_null)
80 {
81 sdb_object_t o1 = SDB_OBJECT_STATIC("obj");
82 sdb_object_t *o2;
83 sdb_avltree_iter_t *iter;
84 int check;
86 /* all functions should work even when passed null values */
87 sdb_avltree_destroy(NULL);
88 sdb_avltree_clear(NULL);
90 check = sdb_avltree_insert(NULL, NULL);
91 fail_unless(check < 0,
92 "sdb_avltree_insert(NULL, NULL) = %d; expected: <0", check);
93 check = sdb_avltree_insert(NULL, &o1);
94 fail_unless(check < 0,
95 "sdb_avltree_insert(NULL, <obj>) = %d; expected: <0", check);
96 fail_unless(o1.ref_cnt == 1,
97 "sdb_avltree_insert(NULL, <obj>) incremented ref-cnt");
98 /* it's acceptable to insert NULL */
100 iter = sdb_avltree_get_iter(NULL);
101 fail_unless(iter == NULL,
102 "sdb_avltree_get_iter(NULL) = %p; expected: NULL", iter);
104 check = sdb_avltree_iter_has_next(NULL) != 0;
105 fail_unless(check == 0,
106 "sdb_avltree_iter_has_next(NULL) = %d; expected: 0", check);
107 o2 = sdb_avltree_iter_get_next(NULL);
108 fail_unless(o2 == NULL,
109 "sdb_avltree_iter_get_next(NULL) = %p; expected: NULL", o2);
111 sdb_avltree_iter_destroy(NULL);
113 check = (int)sdb_avltree_size(NULL);
114 fail_unless(check == 0,
115 "sdb_avltree_size(NULL) = %d; expected: 0", check);
116 }
117 END_TEST
119 START_TEST(test_insert)
120 {
121 size_t i;
123 for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
124 int check;
126 check = sdb_avltree_insert(tree, &test_data[i]);
127 fail_unless(check == 0,
128 "sdb_avltree_insert(<tree>, <%s>) = %d; expected: 0",
129 test_data[i].name, check);
131 check = (int)sdb_avltree_size(tree);
132 fail_unless(check == (int)i + 1,
133 "sdb_avltree_size(<tree>) = %d; expected: %zu",
134 check, i + 1);
136 fail_unless(sdb_avltree_valid(tree),
137 "sdb_avltree_insert(<tree>, <%s>) left behind invalid tree",
138 test_data[i].name);
139 }
141 /* and again ... now reporting errors because of duplicates */
142 for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
143 int check;
145 check = sdb_avltree_insert(tree, &test_data[i]);
146 fail_unless(check < 0,
147 "sdb_avltree_insert(<tree>, <%s>) = %d (redo); expected: <0",
148 test_data[i].name, check);
150 check = (int)sdb_avltree_size(tree);
151 fail_unless(check == SDB_STATIC_ARRAY_LEN(test_data),
152 "sdb_avltree_size(<tree>) = %d; expected: %zu",
153 check, SDB_STATIC_ARRAY_LEN(test_data));
154 }
155 }
156 END_TEST
158 START_TEST(test_lookup)
159 {
160 size_t i;
162 populate();
164 for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
165 sdb_object_t ref = SDB_OBJECT_STATIC(test_data[i].name);
166 sdb_object_t *obj;
168 obj = sdb_avltree_lookup(tree, &ref);
169 fail_unless(obj != NULL,
170 "sdb_avltree_lookup(<tree>, <%s>) = NULL; "
171 "expected: <obj>", ref.name);
172 fail_unless(obj == &test_data[i],
173 "sdb_avltree_lookup(<tree>, <%s>) = %p (%s); "
174 "expected: %p, (%s)", ref.name, obj, obj->name,
175 &test_data[i], test_data[i].name);
176 }
178 for (i = 0; i < SDB_STATIC_ARRAY_LEN(unused_names); ++i) {
179 sdb_object_t ref = SDB_OBJECT_STATIC(unused_names[i]);
180 sdb_object_t *obj;
182 obj = sdb_avltree_lookup(tree, &ref);
183 fail_unless(obj == NULL,
184 "sdb_avltree_lookup(<tree>, <%s> = %p (%s); "
185 "expected: NULL", ref.name, obj, obj ? obj->name : "<nil>");
186 }
187 }
188 END_TEST
190 START_TEST(test_iter)
191 {
192 sdb_avltree_iter_t *iter;
193 sdb_object_t *obj;
195 size_t check, i;
197 populate();
198 check = sdb_avltree_size(tree);
199 fail_unless(check == SDB_STATIC_ARRAY_LEN(test_data),
200 "INTERNAL ERROR: AVL tree size (after populate) = %zu; "
201 "expected: %zu", check, SDB_STATIC_ARRAY_LEN(test_data));
203 iter = sdb_avltree_get_iter(tree);
204 fail_unless(iter != NULL,
205 "sdb_avltree_get_iter(<tree>) = NULL; expected: <iter>");
207 for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
208 char expected_name[] = { (char)('a' + (int)i), '\0' };
210 _Bool c = sdb_avltree_iter_has_next(iter);
211 fail_unless(c, "sdb_avltree_iter_has_next(<iter[%zu]>) = false; "
212 "expected: true", i);
214 obj = sdb_avltree_iter_get_next(iter);
215 fail_unless(obj != NULL,
216 "sdb_avltree_iter_get_next(<iter[%zu]>) = NULL; "
217 "expected: <obj>", i);
218 fail_unless(!strcmp(obj->name, expected_name),
219 "sdb_avltree_iter[%zu] = %s; expected: %s",
220 i, obj->name, expected_name);
221 }
223 check = sdb_avltree_iter_has_next(iter) != 0;
224 fail_unless(check == 0, "sdb_avltree_iter_has_next(<iter>) = true; "
225 "expected: false");
226 obj = sdb_avltree_iter_get_next(iter);
227 fail_unless(obj == NULL,
228 "sdb_avltree_iter_get_next(<iter>) = <obj>; expected: NULL");
230 sdb_avltree_iter_destroy(iter);
232 sdb_avltree_clear(tree);
233 check = sdb_avltree_size(tree);
234 fail_unless(check == 0,
235 "sdb_avltree_clear(<tree>) left %zu nodes in the tree; "
236 "expected: 0", check);
237 }
238 END_TEST
240 Suite *
241 util_avltree_suite(void)
242 {
243 Suite *s = suite_create("utils::avltree");
244 TCase *tc;
246 tc = tcase_create("core");
247 tcase_add_checked_fixture(tc, setup, teardown);
248 tcase_add_test(tc, test_null);
249 tcase_add_test(tc, test_insert);
250 tcase_add_test(tc, test_lookup);
251 tcase_add_test(tc, test_iter);
252 suite_add_tcase(s, tc);
254 return s;
255 } /* util_avltree_suite */
257 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */