blob: 57e0de098b1307e3b388feb18b3812c4222380e8 [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
Radek Krejci535ea9f2020-05-29 16:01:05 +020015#define _GNU_SOURCE
16
Radek Krejciaaf6d402018-09-20 15:14:47 +020017#include <stdarg.h>
18#include <stddef.h>
19#include <setjmp.h>
20#include <cmocka.h>
21
22#include <string.h>
Radek Krejcica376bd2020-06-11 16:04:06 +020023#include <stdlib.h>
Radek Krejciaaf6d402018-09-20 15:14:47 +020024#include <stdio.h>
25
Radek Krejci70593c12020-06-13 20:48:09 +020026#include "common.h"
27#include "hash_table.h"
Radek Krejci2d7a47b2019-05-16 13:34:10 +020028
29struct ht_rec *lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx);
Radek Krejciaaf6d402018-09-20 15:14:47 +020030
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
Radek Krejci011e4aa2020-09-04 15:22:31 +020076 assert_int_equal(LY_EINVAL, lydict_insert(NULL, NULL, 0, NULL));
Radek Krejciaaf6d402018-09-20 15:14:47 +020077 logbuf_assert("Invalid argument ctx (lydict_insert()).");
78
Radek Krejci011e4aa2020-09-04 15:22:31 +020079 assert_int_equal(LY_EINVAL, lydict_insert_zc(NULL, NULL, NULL));
Radek Krejciaaf6d402018-09-20 15:14:47 +020080 logbuf_assert("Invalid argument ctx (lydict_insert_zc()).");
Radek Krejci011e4aa2020-09-04 15:22:31 +020081 assert_int_equal(LY_EINVAL, lydict_insert_zc(ctx, NULL, 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
Radek Krejci011e4aa2020-09-04 15:22:31 +020092 const char *str1, *str2, *str3;
Radek Krejciaaf6d402018-09-20 15:14:47 +020093 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 */
Radek Krejci011e4aa2020-09-04 15:22:31 +020098 assert_int_equal(LY_SUCCESS, lydict_insert(ctx, "test1", 0, &str1));
Radek Krejciaaf6d402018-09-20 15:14:47 +020099 assert_non_null(str1);
100 /* via zerocopy we have to get the same pointer as provided */
101 assert_non_null(str2 = strdup("test2"));
Radek Krejci011e4aa2020-09-04 15:22:31 +0200102 assert_int_equal(LY_SUCCESS, lydict_insert_zc(ctx, (char *)str2, &str3));
103 assert_ptr_equal(str2, str3);
Radek Krejciaaf6d402018-09-20 15:14:47 +0200104 /* here we get the same pointer as in case the string was inserted first time */
Radek Krejci011e4aa2020-09-04 15:22:31 +0200105 assert_int_equal(LY_SUCCESS, lydict_insert(ctx, "test1", 0, &str2));
Radek Krejciaaf6d402018-09-20 15:14:47 +0200106 assert_non_null(str2);
107 assert_ptr_equal(str1, str2);
108
109 /* remove strings, but the repeatedly inserted only once */
110 lydict_remove(ctx, "test1");
111 lydict_remove(ctx, "test2");
112
113 /* destroy dictionary - should raise warning about data presence */
114 ly_ctx_destroy(ctx, NULL);
115 logbuf_assert("String \"test1\" not freed from the dictionary, refcount 1");
116
117#ifndef NDEBUG
118 /* cleanup */
119 free((char*)str1);
120#endif
121}
122
Radek Krejci1deb5be2020-08-26 16:43:36 +0200123static uint8_t
124ht_equal_clb(void *val1, void *val2, uint8_t mod, void *cb_data)
Radek Krejci0ae092d2018-09-20 16:43:19 +0200125{
126 int *v1, *v2;
127 (void)mod;
128 (void)cb_data;
129
130 v1 = (int *)val1;
131 v2 = (int *)val2;
132
133 return *v1 == *v2;
134}
135
136static void
137test_ht_basic(void **state)
138{
139 (void) state; /* unused */
140
141 uint32_t i;
142 struct hash_table *ht;
143
144 assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 0));
145
146 i = 2;
Michal Vaskoda859032020-07-14 12:20:14 +0200147 assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
Radek Krejci0ae092d2018-09-20 16:43:19 +0200148 assert_int_equal(LY_SUCCESS, lyht_insert(ht, &i, i, NULL));
Michal Vaskoda859032020-07-14 12:20:14 +0200149 assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, i, NULL));
Radek Krejci0ae092d2018-09-20 16:43:19 +0200150 assert_int_equal(LY_SUCCESS, lyht_remove(ht, &i, i));
Michal Vaskoda859032020-07-14 12:20:14 +0200151 assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200152 assert_int_equal(LY_ENOTFOUND, lyht_remove(ht, &i, i));
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200153 logbuf_assert("Invalid argument hash (lyht_remove_with_resize_cb()).");
Radek Krejci0ae092d2018-09-20 16:43:19 +0200154
155 lyht_free(ht);
156}
157
158static void
159test_ht_resize(void **state)
160{
161 (void) state; /* unused */
162
163 uint32_t i;
164 struct ht_rec *rec;
165 struct hash_table *ht;
166
167 assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 1));
168 assert_int_equal(8, ht->size);
169
170 /* insert records into indexes 2-7 */
171 for (i = 2; i < 8; ++i) {
172 assert_int_equal(LY_SUCCESS, lyht_insert(ht, &i, i, NULL));
173 }
174 /* check that table resized */
175 assert_int_equal(16, ht->size);
176
177 /* check expected content of the table */
178 for (i = 0; i < 16; ++i) {
179 if (i >=2 && i < 8) {
180 /* inserted data on indexes 2-7 */
181 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
182 assert_int_equal(1, rec->hits);
183 assert_int_equal(i, rec->hash);
184 } else {
185 /* nothing otherwise */
186 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
187 assert_int_equal(0, rec->hits);
188 }
189 }
190
191 /* removing not present data should fail */
192 for (i = 0; i < 2; ++i) {
193 logbuf_clean();
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200194 assert_int_equal(LY_ENOTFOUND, lyht_remove(ht, &i, i));
Michal Vasko5bcc33b2020-10-06 15:33:44 +0200195 logbuf_assert("Invalid argument hash (lyht_remove_with_resize_cb()).");
Radek Krejci0ae092d2018-09-20 16:43:19 +0200196 }
197 /* removing present data, resize should happened
198 * when we are below 25% of the table filled, so with 3 records left */
199 for (; i < 5; ++i) {
200 assert_int_equal(LY_SUCCESS, lyht_remove(ht, &i, i));
201 }
202 assert_int_equal(8, ht->size);
203
204 /* remove the rest */
205 for (; i < 8; ++i) {
206 assert_int_equal(LY_SUCCESS, lyht_remove(ht, &i, i));
207 }
208
209 for (i = 0; i < 8; ++i) {
Michal Vaskoda859032020-07-14 12:20:14 +0200210 assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
Radek Krejci0ae092d2018-09-20 16:43:19 +0200211 }
212
213 /* cleanup */
214 lyht_free(ht);
215}
216
217
218static void
219test_ht_collisions(void **state)
220{
221 (void) state; /* unused */
222#define GET_REC_INT(rec) (*((uint32_t *)&(rec)->val))
223
224 uint32_t i;
225 struct ht_rec *rec;
226 struct hash_table *ht;
227
228 assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 1));
229
230 for (i = 2; i < 6; ++i) {
231 assert_int_equal(lyht_insert(ht, &i, 2, NULL), 0);
232 }
233
234 /* check all records */
235 for (i = 0; i < 2; ++i) {
236 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
237 assert_int_equal(rec->hits, 0);
238 }
239 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
240 assert_int_equal(rec->hits, 4);
241 assert_int_equal(GET_REC_INT(rec), i);
242 ++i;
243 for (; i < 6; ++i) {
244 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
245 assert_int_equal(rec->hits, 1);
246 assert_int_equal(GET_REC_INT(rec), i);
247 }
248 for (; i < 8; ++i) {
249 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
250 assert_int_equal(rec->hits, 0);
251 }
252
253 i = 4;
254 assert_int_equal(lyht_remove(ht, &i, 2), 0);
255
256 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
257 assert_int_equal(rec->hits, -1);
258
259 i = 2;
260 assert_int_equal(lyht_remove(ht, &i, 2), 0);
261
262 /* check all records */
263 for (i = 0; i < 2; ++i) {
264 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
265 assert_int_equal(rec->hits, 0);
266 }
267 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
268 assert_int_equal(rec->hits, 2);
269 assert_int_equal(GET_REC_INT(rec), 5);
270 ++i;
271 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
272 assert_int_equal(rec->hits, 1);
273 assert_int_equal(GET_REC_INT(rec), 3);
274 ++i;
275 for (; i < 6; ++i) {
276 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
277 assert_int_equal(rec->hits, -1);
278 }
279 for (; i < 8; ++i) {
280 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
281 assert_int_equal(rec->hits, 0);
282 }
283
284 for (i = 0; i < 3; ++i) {
Michal Vaskoda859032020-07-14 12:20:14 +0200285 assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
Radek Krejci0ae092d2018-09-20 16:43:19 +0200286 }
Michal Vaskoda859032020-07-14 12:20:14 +0200287 assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_SUCCESS);
Radek Krejci0ae092d2018-09-20 16:43:19 +0200288 ++i;
Michal Vaskoda859032020-07-14 12:20:14 +0200289 assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
Radek Krejci0ae092d2018-09-20 16:43:19 +0200290 ++i;
Michal Vaskoda859032020-07-14 12:20:14 +0200291 assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_SUCCESS);
Radek Krejci0ae092d2018-09-20 16:43:19 +0200292 ++i;
293 for (; i < 8; ++i) {
Michal Vaskoda859032020-07-14 12:20:14 +0200294 assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
Radek Krejci0ae092d2018-09-20 16:43:19 +0200295 }
296
297 i = 3;
298 assert_int_equal(lyht_remove(ht, &i, 2), 0);
299 i = 5;
300 assert_int_equal(lyht_remove(ht, &i, 2), 0);
301
302 /* check all records */
303 for (i = 0; i < 2; ++i) {
304 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
305 assert_int_equal(rec->hits, 0);
306 }
307 for (; i < 6; ++i) {
308 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
309 assert_int_equal(rec->hits, -1);
310 }
311 for (; i < 8; ++i) {
312 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
313 assert_int_equal(rec->hits, 0);
314 }
315
316 lyht_free(ht);
317}
318
Radek Krejciaaf6d402018-09-20 15:14:47 +0200319int main(void)
320{
321 const struct CMUnitTest tests[] = {
322 cmocka_unit_test_setup(test_invalid_arguments, logger_setup),
323 cmocka_unit_test_setup(test_dict_hit, logger_setup),
Radek Krejci0ae092d2018-09-20 16:43:19 +0200324 cmocka_unit_test_setup(test_ht_basic, logger_setup),
325 cmocka_unit_test_setup(test_ht_resize, logger_setup),
326 cmocka_unit_test_setup(test_ht_collisions, logger_setup),
Radek Krejciaaf6d402018-09-20 15:14:47 +0200327 };
328
329 return cmocka_run_group_tests(tests, NULL, NULL);
330}