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 #if HAVE_CONFIG_H
29 # include "config.h"
30 #endif
32 #include "utils/avltree.h"
33 #include "testutils.h"
35 #include <check.h>
37 static sdb_avltree_t *tree;
39 static void
40 setup(void)
41 {
42 tree = sdb_avltree_create();
43 fail_unless(tree != NULL,
44 "sdb_avltree_create() = NULL; expected AVL-tree object");
45 } /* setup */
47 static void
48 teardown(void)
49 {
50 sdb_avltree_destroy(tree);
51 tree = NULL;
52 } /* teardown */
54 /* 'a' thru 'o' */
55 static sdb_object_t test_data[] = {
56 SDB_OBJECT_STATIC("h"),
57 SDB_OBJECT_STATIC("j"),
58 SDB_OBJECT_STATIC("i"),
59 SDB_OBJECT_STATIC("f"),
60 SDB_OBJECT_STATIC("e"),
61 SDB_OBJECT_STATIC("g"),
62 SDB_OBJECT_STATIC("k"),
63 SDB_OBJECT_STATIC("l"),
64 SDB_OBJECT_STATIC("m"),
65 SDB_OBJECT_STATIC("n"),
66 SDB_OBJECT_STATIC("o"),
67 SDB_OBJECT_STATIC("d"),
68 SDB_OBJECT_STATIC("c"),
69 SDB_OBJECT_STATIC("b"),
70 SDB_OBJECT_STATIC("a"),
71 };
73 static char *unused_names[] = { "x", "y", "z" };
75 static void
76 populate(void)
77 {
78 size_t i;
79 for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i)
80 sdb_avltree_insert(tree, &test_data[i]);
81 } /* populate */
83 START_TEST(test_null)
84 {
85 sdb_object_t o1 = SDB_OBJECT_STATIC("obj");
86 sdb_object_t *o2;
87 sdb_avltree_iter_t *iter;
88 int check;
90 /* all functions should work even when passed null values */
91 sdb_avltree_destroy(NULL);
92 sdb_avltree_clear(NULL);
94 check = sdb_avltree_insert(NULL, NULL);
95 fail_unless(check < 0,
96 "sdb_avltree_insert(NULL, NULL) = %d; expected: <0", check);
97 check = sdb_avltree_insert(NULL, &o1);
98 fail_unless(check < 0,
99 "sdb_avltree_insert(NULL, <obj>) = %d; expected: <0", check);
100 fail_unless(o1.ref_cnt == 1,
101 "sdb_avltree_insert(NULL, <obj>) incremented ref-cnt");
102 /* it's acceptable to insert NULL */
104 iter = sdb_avltree_get_iter(NULL);
105 fail_unless(iter == NULL,
106 "sdb_avltree_get_iter(NULL) = %p; expected: NULL", iter);
108 check = sdb_avltree_iter_has_next(NULL) != 0;
109 fail_unless(check == 0,
110 "sdb_avltree_iter_has_next(NULL) = %d; expected: 0", check);
111 o2 = sdb_avltree_iter_get_next(NULL);
112 fail_unless(o2 == NULL,
113 "sdb_avltree_iter_get_next(NULL) = %p; expected: NULL", o2);
115 sdb_avltree_iter_destroy(NULL);
117 check = (int)sdb_avltree_size(NULL);
118 fail_unless(check == 0,
119 "sdb_avltree_size(NULL) = %d; expected: 0", check);
120 }
121 END_TEST
123 START_TEST(test_insert)
124 {
125 size_t i;
127 for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
128 int check;
130 check = sdb_avltree_insert(tree, &test_data[i]);
131 fail_unless(check == 0,
132 "sdb_avltree_insert(<tree>, <%s>) = %d; expected: 0",
133 test_data[i].name, check);
135 check = (int)sdb_avltree_size(tree);
136 fail_unless(check == (int)i + 1,
137 "sdb_avltree_size(<tree>) = %d; expected: %zu",
138 check, i + 1);
140 fail_unless(sdb_avltree_valid(tree),
141 "sdb_avltree_insert(<tree>, <%s>) left behind invalid tree",
142 test_data[i].name);
143 }
145 /* and again ... now reporting errors because of duplicates */
146 for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
147 int check;
149 check = sdb_avltree_insert(tree, &test_data[i]);
150 fail_unless(check < 0,
151 "sdb_avltree_insert(<tree>, <%s>) = %d (redo); expected: <0",
152 test_data[i].name, check);
154 check = (int)sdb_avltree_size(tree);
155 fail_unless(check == SDB_STATIC_ARRAY_LEN(test_data),
156 "sdb_avltree_size(<tree>) = %d; expected: %zu",
157 check, SDB_STATIC_ARRAY_LEN(test_data));
158 }
159 }
160 END_TEST
162 START_TEST(test_lookup)
163 {
164 size_t i;
166 populate();
168 for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
169 sdb_object_t *obj;
171 obj = sdb_avltree_lookup(tree, test_data[i].name);
172 fail_unless(obj != NULL,
173 "sdb_avltree_lookup(<tree>, %s) = NULL; "
174 "expected: <obj>", test_data[i].name);
175 fail_unless(obj == &test_data[i],
176 "sdb_avltree_lookup(<tree>, %s) = %p (%s); "
177 "expected: %p, (%s)", test_data[i].name, obj, obj->name,
178 &test_data[i], test_data[i].name);
179 }
181 for (i = 0; i < SDB_STATIC_ARRAY_LEN(unused_names); ++i) {
182 sdb_object_t *obj;
184 obj = sdb_avltree_lookup(tree, unused_names[i]);
185 fail_unless(obj == NULL,
186 "sdb_avltree_lookup(<tree>, %s) = %p (%s); "
187 "expected: NULL", unused_names[i],
188 obj, obj ? obj->name : "<nil>");
189 }
190 }
191 END_TEST
193 START_TEST(test_iter)
194 {
195 sdb_avltree_iter_t *iter;
196 sdb_object_t *obj;
198 size_t check, i;
200 populate();
201 check = sdb_avltree_size(tree);
202 fail_unless(check == SDB_STATIC_ARRAY_LEN(test_data),
203 "INTERNAL ERROR: AVL tree size (after populate) = %zu; "
204 "expected: %zu", check, SDB_STATIC_ARRAY_LEN(test_data));
206 iter = sdb_avltree_get_iter(tree);
207 fail_unless(iter != NULL,
208 "sdb_avltree_get_iter(<tree>) = NULL; expected: <iter>");
210 for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
211 char expected_name[] = { (char)('a' + (int)i), '\0' };
212 sdb_object_t *expected_obj;
214 _Bool c = sdb_avltree_iter_has_next(iter);
215 fail_unless(c, "sdb_avltree_iter_has_next(<iter[%zu]>) = false; "
216 "expected: true", i);
218 expected_obj = sdb_avltree_iter_peek_next(iter);
219 fail_unless(expected_obj != NULL,
220 "sdb_avltree_iter_peek_next(<iter[%zu]>) = NULL; "
221 "expected: <obj>", i);
223 obj = sdb_avltree_iter_get_next(iter);
224 fail_unless(obj != NULL,
225 "sdb_avltree_iter_get_next(<iter[%zu]>) = NULL; "
226 "expected: <obj>", i);
227 fail_unless(!strcmp(obj->name, expected_name),
228 "sdb_avltree_iter[%zu] = %s; expected: %s",
229 i, obj->name, expected_name);
231 fail_unless(obj == expected_obj,
232 "sdb_avltree_iter_get_next(<iter[%zu]>) = %p; "
233 "expected: %p (from peek())", i, obj, expected_obj);
234 }
236 check = sdb_avltree_iter_has_next(iter) != 0;
237 fail_unless(check == 0, "sdb_avltree_iter_has_next(<iter>) = true; "
238 "expected: false");
239 obj = sdb_avltree_iter_peek_next(iter);
240 fail_unless(obj == NULL,
241 "sdb_avltree_iter_peek_next(<iter>) = <obj>; expected: NULL");
242 obj = sdb_avltree_iter_get_next(iter);
243 fail_unless(obj == NULL,
244 "sdb_avltree_iter_get_next(<iter>) = <obj>; expected: NULL");
246 sdb_avltree_iter_destroy(iter);
248 sdb_avltree_clear(tree);
249 check = sdb_avltree_size(tree);
250 fail_unless(check == 0,
251 "sdb_avltree_clear(<tree>) left %zu nodes in the tree; "
252 "expected: 0", check);
253 }
254 END_TEST
256 TEST_MAIN("utils::avltree")
257 {
258 TCase *tc = tcase_create("core");
259 tcase_add_checked_fixture(tc, setup, teardown);
260 tcase_add_test(tc, test_null);
261 tcase_add_test(tc, test_insert);
262 tcase_add_test(tc, test_lookup);
263 tcase_add_test(tc, test_iter);
264 ADD_TCASE(tc);
265 }
266 TEST_MAIN_END
268 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */