blob: 1afeb83c5daa3417da360ecdf91ed5153493bae5 [file] [log] [blame]
Radek Krejciaaf6d402018-09-20 15:14:47 +02001/*
2 * @file hash_table.c
3 * @author: Radek Krejci <rkrejci@cesnet.cz>
4 * @brief unit tests for functions from hash_table.c
5 *
6 * Copyright (c) 2018 CESNET, z.s.p.o.
7 *
8 * This source code is licensed under BSD 3-Clause License (the "License").
9 * You may not use this file except in compliance with the License.
10 * You may obtain a copy of the License at
11 *
12 * https://opensource.org/licenses/BSD-3-Clause
13 */
14
15#define _BSD_SOURCE
16#define _DEFAULT_SOURCE
17
18#include "tests/config.h"
19#include "../../src/hash_table.c"
20
21#include <stdarg.h>
22#include <stddef.h>
23#include <setjmp.h>
24#include <cmocka.h>
25
26#include <string.h>
27#include <stdio.h>
28
29#include "libyang.h"
30
31#define BUFSIZE 1024
32char logbuf[BUFSIZE] = {0};
33
34/* set to 0 to printing error messages to stderr instead of checking them in code */
35#define ENABLE_LOGGER_CHECKING 1
36
37static void
38logger(LY_LOG_LEVEL level, const char *msg, const char *path)
39{
40 (void) level; /* unused */
41 (void) path; /* unused */
42
43 strncpy(logbuf, msg, BUFSIZE - 1);
44}
45
46static int
47logger_setup(void **state)
48{
49 (void) state; /* unused */
50#if ENABLE_LOGGER_CHECKING
51 ly_set_log_clb(logger, 0);
52#endif
53 return 0;
54}
55
56void
57logbuf_clean(void)
58{
59 logbuf[0] = '\0';
60}
61
62#if ENABLE_LOGGER_CHECKING
63# define logbuf_assert(str) assert_string_equal(logbuf, str)
64#else
65# define logbuf_assert(str)
66#endif
67
68static void
69test_invalid_arguments(void **state)
70{
71 (void) state; /* unused */
72 struct ly_ctx *ctx;
73
74 assert_int_equal(LY_SUCCESS, ly_ctx_new(NULL, 0, &ctx));
75
76 assert_null(lydict_insert(NULL, NULL, 0));
77 logbuf_assert("Invalid argument ctx (lydict_insert()).");
78
79 assert_null(lydict_insert_zc(NULL, NULL));
80 logbuf_assert("Invalid argument ctx (lydict_insert_zc()).");
Radek Krejciaaf6d402018-09-20 15:14:47 +020081 assert_null(lydict_insert_zc(ctx, NULL));
Radek Krejci0ae092d2018-09-20 16:43:19 +020082 logbuf_assert("Invalid argument value (lydict_insert_zc()).");
Radek Krejciaaf6d402018-09-20 15:14:47 +020083
84 ly_ctx_destroy(ctx, NULL);
85}
86
87static void
88test_dict_hit(void **state)
89{
90 (void) state; /* unused */
91
92 const char *str1, *str2;
93 struct ly_ctx *ctx;
94
95 assert_int_equal(LY_SUCCESS, ly_ctx_new(NULL, 0, &ctx));
96
97 /* insert 2 strings, one of them repeatedly */
98 str1 = lydict_insert(ctx, "test1", 0);
99 assert_non_null(str1);
100 /* via zerocopy we have to get the same pointer as provided */
101 assert_non_null(str2 = strdup("test2"));
102 assert_true(str2 == lydict_insert_zc(ctx, (char *)str2));
103 /* here we get the same pointer as in case the string was inserted first time */
104 str2 = lydict_insert(ctx, "test1", 0);
105 assert_non_null(str2);
106 assert_ptr_equal(str1, str2);
107
108 /* remove strings, but the repeatedly inserted only once */
109 lydict_remove(ctx, "test1");
110 lydict_remove(ctx, "test2");
111
112 /* destroy dictionary - should raise warning about data presence */
113 ly_ctx_destroy(ctx, NULL);
114 logbuf_assert("String \"test1\" not freed from the dictionary, refcount 1");
115
116#ifndef NDEBUG
117 /* cleanup */
118 free((char*)str1);
119#endif
120}
121
Radek Krejci0ae092d2018-09-20 16:43:19 +0200122static int
123ht_equal_clb(void *val1, void *val2, int mod, void *cb_data)
124{
125 int *v1, *v2;
126 (void)mod;
127 (void)cb_data;
128
129 v1 = (int *)val1;
130 v2 = (int *)val2;
131
132 return *v1 == *v2;
133}
134
135static void
136test_ht_basic(void **state)
137{
138 (void) state; /* unused */
139
140 uint32_t i;
141 struct hash_table *ht;
142
143 assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 0));
144
145 i = 2;
146 assert_int_equal(1, lyht_find(ht, &i, i, NULL));
147 assert_int_equal(LY_SUCCESS, lyht_insert(ht, &i, i, NULL));
148 assert_int_equal(0, lyht_find(ht, &i, i, NULL));
149 assert_int_equal(LY_SUCCESS, lyht_remove(ht, &i, i));
150 assert_int_equal(1, lyht_find(ht, &i, i, NULL));
151 assert_int_equal(LY_EINVAL, lyht_remove(ht, &i, i));
152 logbuf_assert("Invalid argument hash (lyht_remove()).");
153
154 lyht_free(ht);
155}
156
157static void
158test_ht_resize(void **state)
159{
160 (void) state; /* unused */
161
162 uint32_t i;
163 struct ht_rec *rec;
164 struct hash_table *ht;
165
166 assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 1));
167 assert_int_equal(8, ht->size);
168
169 /* insert records into indexes 2-7 */
170 for (i = 2; i < 8; ++i) {
171 assert_int_equal(LY_SUCCESS, lyht_insert(ht, &i, i, NULL));
172 }
173 /* check that table resized */
174 assert_int_equal(16, ht->size);
175
176 /* check expected content of the table */
177 for (i = 0; i < 16; ++i) {
178 if (i >=2 && i < 8) {
179 /* inserted data on indexes 2-7 */
180 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
181 assert_int_equal(1, rec->hits);
182 assert_int_equal(i, rec->hash);
183 } else {
184 /* nothing otherwise */
185 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
186 assert_int_equal(0, rec->hits);
187 }
188 }
189
190 /* removing not present data should fail */
191 for (i = 0; i < 2; ++i) {
192 logbuf_clean();
193 assert_int_equal(LY_EINVAL, lyht_remove(ht, &i, i));
194 logbuf_assert("Invalid argument hash (lyht_remove()).");
195 }
196 /* removing present data, resize should happened
197 * when we are below 25% of the table filled, so with 3 records left */
198 for (; i < 5; ++i) {
199 assert_int_equal(LY_SUCCESS, lyht_remove(ht, &i, i));
200 }
201 assert_int_equal(8, ht->size);
202
203 /* remove the rest */
204 for (; i < 8; ++i) {
205 assert_int_equal(LY_SUCCESS, lyht_remove(ht, &i, i));
206 }
207
208 for (i = 0; i < 8; ++i) {
209 assert_int_equal(1, lyht_find(ht, &i, i, NULL));
210 }
211
212 /* cleanup */
213 lyht_free(ht);
214}
215
216
217static void
218test_ht_collisions(void **state)
219{
220 (void) state; /* unused */
221#define GET_REC_INT(rec) (*((uint32_t *)&(rec)->val))
222
223 uint32_t i;
224 struct ht_rec *rec;
225 struct hash_table *ht;
226
227 assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 1));
228
229 for (i = 2; i < 6; ++i) {
230 assert_int_equal(lyht_insert(ht, &i, 2, NULL), 0);
231 }
232
233 /* check all records */
234 for (i = 0; i < 2; ++i) {
235 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
236 assert_int_equal(rec->hits, 0);
237 }
238 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
239 assert_int_equal(rec->hits, 4);
240 assert_int_equal(GET_REC_INT(rec), i);
241 ++i;
242 for (; i < 6; ++i) {
243 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
244 assert_int_equal(rec->hits, 1);
245 assert_int_equal(GET_REC_INT(rec), i);
246 }
247 for (; i < 8; ++i) {
248 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
249 assert_int_equal(rec->hits, 0);
250 }
251
252 i = 4;
253 assert_int_equal(lyht_remove(ht, &i, 2), 0);
254
255 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
256 assert_int_equal(rec->hits, -1);
257
258 i = 2;
259 assert_int_equal(lyht_remove(ht, &i, 2), 0);
260
261 /* check all records */
262 for (i = 0; i < 2; ++i) {
263 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
264 assert_int_equal(rec->hits, 0);
265 }
266 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
267 assert_int_equal(rec->hits, 2);
268 assert_int_equal(GET_REC_INT(rec), 5);
269 ++i;
270 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
271 assert_int_equal(rec->hits, 1);
272 assert_int_equal(GET_REC_INT(rec), 3);
273 ++i;
274 for (; i < 6; ++i) {
275 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
276 assert_int_equal(rec->hits, -1);
277 }
278 for (; i < 8; ++i) {
279 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
280 assert_int_equal(rec->hits, 0);
281 }
282
283 for (i = 0; i < 3; ++i) {
284 assert_int_equal(lyht_find(ht, &i, 2, NULL), 1);
285 }
286 assert_int_equal(lyht_find(ht, &i, 2, NULL), 0);
287 ++i;
288 assert_int_equal(lyht_find(ht, &i, 2, NULL), 1);
289 ++i;
290 assert_int_equal(lyht_find(ht, &i, 2, NULL), 0);
291 ++i;
292 for (; i < 8; ++i) {
293 assert_int_equal(lyht_find(ht, &i, 2, NULL), 1);
294 }
295
296 i = 3;
297 assert_int_equal(lyht_remove(ht, &i, 2), 0);
298 i = 5;
299 assert_int_equal(lyht_remove(ht, &i, 2), 0);
300
301 /* check all records */
302 for (i = 0; i < 2; ++i) {
303 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
304 assert_int_equal(rec->hits, 0);
305 }
306 for (; i < 6; ++i) {
307 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
308 assert_int_equal(rec->hits, -1);
309 }
310 for (; i < 8; ++i) {
311 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
312 assert_int_equal(rec->hits, 0);
313 }
314
315 lyht_free(ht);
316}
317
Radek Krejciaaf6d402018-09-20 15:14:47 +0200318int main(void)
319{
320 const struct CMUnitTest tests[] = {
321 cmocka_unit_test_setup(test_invalid_arguments, logger_setup),
322 cmocka_unit_test_setup(test_dict_hit, logger_setup),
Radek Krejci0ae092d2018-09-20 16:43:19 +0200323 cmocka_unit_test_setup(test_ht_basic, logger_setup),
324 cmocka_unit_test_setup(test_ht_resize, logger_setup),
325 cmocka_unit_test_setup(test_ht_collisions, logger_setup),
Radek Krejciaaf6d402018-09-20 15:14:47 +0200326 };
327
328 return cmocka_run_group_tests(tests, NULL, NULL);
329}