blob: 6643c94429ffea2b92a5d93f9d9679c13e87be43 [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 */
Radek Iša56ca9e42020-09-08 18:42:00 +020014#define _UTEST_MAIN_
15#include "utests.h"
Radek Krejci535ea9f2020-05-29 16:01:05 +020016
Radek Krejcica376bd2020-06-11 16:04:06 +020017#include <stdlib.h>
Radek Krejciaaf6d402018-09-20 15:14:47 +020018
Radek Krejci70593c12020-06-13 20:48:09 +020019#include "common.h"
20#include "hash_table.h"
Radek Krejci2d7a47b2019-05-16 13:34:10 +020021
22struct ht_rec *lyht_get_rec(unsigned char *recs, uint16_t rec_size, uint32_t idx);
Radek Krejciaaf6d402018-09-20 15:14:47 +020023
Radek Krejciaaf6d402018-09-20 15:14:47 +020024static void
25test_invalid_arguments(void **state)
26{
Radek Krejci011e4aa2020-09-04 15:22:31 +020027 assert_int_equal(LY_EINVAL, lydict_insert(NULL, NULL, 0, NULL));
Radek Iša56ca9e42020-09-08 18:42:00 +020028 CHECK_LOG("Invalid argument ctx (lydict_insert()).", NULL);
Radek Krejciaaf6d402018-09-20 15:14:47 +020029
Radek Krejci011e4aa2020-09-04 15:22:31 +020030 assert_int_equal(LY_EINVAL, lydict_insert_zc(NULL, NULL, NULL));
Radek Iša56ca9e42020-09-08 18:42:00 +020031 CHECK_LOG("Invalid argument ctx (lydict_insert_zc()).", NULL);
32 assert_int_equal(LY_EINVAL, lydict_insert_zc(UTEST_LYCTX, NULL, NULL));
Michal Vaskobe27c912021-02-24 17:07:37 +010033 CHECK_LOG_CTX("Invalid argument str_p (lydict_insert_zc()).", NULL);
Radek Krejciaaf6d402018-09-20 15:14:47 +020034}
35
36static void
37test_dict_hit(void **state)
38{
Radek Krejci011e4aa2020-09-04 15:22:31 +020039 const char *str1, *str2, *str3;
Radek Krejciaaf6d402018-09-20 15:14:47 +020040
41 /* insert 2 strings, one of them repeatedly */
Radek Iša56ca9e42020-09-08 18:42:00 +020042 assert_int_equal(LY_SUCCESS, lydict_insert(UTEST_LYCTX, "test1", 0, &str1));
Radek Krejciaaf6d402018-09-20 15:14:47 +020043 assert_non_null(str1);
44 /* via zerocopy we have to get the same pointer as provided */
45 assert_non_null(str2 = strdup("test2"));
Radek Iša56ca9e42020-09-08 18:42:00 +020046 assert_int_equal(LY_SUCCESS, lydict_insert_zc(UTEST_LYCTX, (char *)str2, &str3));
Radek Krejci011e4aa2020-09-04 15:22:31 +020047 assert_ptr_equal(str2, str3);
Radek Krejciaaf6d402018-09-20 15:14:47 +020048 /* here we get the same pointer as in case the string was inserted first time */
Radek Iša56ca9e42020-09-08 18:42:00 +020049 assert_int_equal(LY_SUCCESS, lydict_insert(UTEST_LYCTX, "test1", 0, &str2));
Radek Krejciaaf6d402018-09-20 15:14:47 +020050 assert_non_null(str2);
51 assert_ptr_equal(str1, str2);
52
53 /* remove strings, but the repeatedly inserted only once */
Radek Iša56ca9e42020-09-08 18:42:00 +020054 lydict_remove(UTEST_LYCTX, "test1");
55 lydict_remove(UTEST_LYCTX, "test2");
Radek Krejciaaf6d402018-09-20 15:14:47 +020056
57 /* destroy dictionary - should raise warning about data presence */
Radek Krejci90ed21e2021-04-12 14:47:46 +020058 ly_ctx_destroy(UTEST_LYCTX);
Radek Iša56ca9e42020-09-08 18:42:00 +020059 UTEST_LYCTX = NULL;
60 CHECK_LOG("String \"test1\" not freed from the dictionary, refcount 1", NULL);
Radek Krejciaaf6d402018-09-20 15:14:47 +020061
62#ifndef NDEBUG
63 /* cleanup */
Radek Krejcib4ac5a92020-11-23 17:54:33 +010064 free((char *)str1);
Radek Krejciaaf6d402018-09-20 15:14:47 +020065#endif
66}
67
Radek Krejci1deb5be2020-08-26 16:43:36 +020068static uint8_t
69ht_equal_clb(void *val1, void *val2, uint8_t mod, void *cb_data)
Radek Krejci0ae092d2018-09-20 16:43:19 +020070{
71 int *v1, *v2;
Radek Krejcib4ac5a92020-11-23 17:54:33 +010072
Radek Krejci0ae092d2018-09-20 16:43:19 +020073 (void)mod;
74 (void)cb_data;
75
76 v1 = (int *)val1;
77 v2 = (int *)val2;
78
79 return *v1 == *v2;
80}
81
82static void
83test_ht_basic(void **state)
84{
Radek Krejci0ae092d2018-09-20 16:43:19 +020085 uint32_t i;
86 struct hash_table *ht;
87
88 assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 0));
89
90 i = 2;
Michal Vaskoda859032020-07-14 12:20:14 +020091 assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
Radek Krejci0ae092d2018-09-20 16:43:19 +020092 assert_int_equal(LY_SUCCESS, lyht_insert(ht, &i, i, NULL));
Michal Vaskoda859032020-07-14 12:20:14 +020093 assert_int_equal(LY_SUCCESS, lyht_find(ht, &i, i, NULL));
Radek Krejci0ae092d2018-09-20 16:43:19 +020094 assert_int_equal(LY_SUCCESS, lyht_remove(ht, &i, i));
Michal Vaskoda859032020-07-14 12:20:14 +020095 assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
Michal Vasko4a4c7ed2020-07-17 09:30:12 +020096 assert_int_equal(LY_ENOTFOUND, lyht_remove(ht, &i, i));
Radek Iša56ca9e42020-09-08 18:42:00 +020097 CHECK_LOG("Invalid argument hash (lyht_remove_with_resize_cb()).", NULL);
Radek Krejci0ae092d2018-09-20 16:43:19 +020098
99 lyht_free(ht);
100}
101
102static void
103test_ht_resize(void **state)
104{
Radek Krejci0ae092d2018-09-20 16:43:19 +0200105 uint32_t i;
106 struct ht_rec *rec;
107 struct hash_table *ht;
108
109 assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 1));
110 assert_int_equal(8, ht->size);
111
112 /* insert records into indexes 2-7 */
113 for (i = 2; i < 8; ++i) {
114 assert_int_equal(LY_SUCCESS, lyht_insert(ht, &i, i, NULL));
115 }
116 /* check that table resized */
117 assert_int_equal(16, ht->size);
118
119 /* check expected content of the table */
120 for (i = 0; i < 16; ++i) {
Radek Krejcib4ac5a92020-11-23 17:54:33 +0100121 if ((i >= 2) && (i < 8)) {
Radek Krejci0ae092d2018-09-20 16:43:19 +0200122 /* inserted data on indexes 2-7 */
123 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
124 assert_int_equal(1, rec->hits);
125 assert_int_equal(i, rec->hash);
126 } else {
127 /* nothing otherwise */
128 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
129 assert_int_equal(0, rec->hits);
130 }
131 }
132
133 /* removing not present data should fail */
134 for (i = 0; i < 2; ++i) {
Radek Iša56ca9e42020-09-08 18:42:00 +0200135 UTEST_LOG_CLEAN;
Michal Vasko4a4c7ed2020-07-17 09:30:12 +0200136 assert_int_equal(LY_ENOTFOUND, lyht_remove(ht, &i, i));
Radek Iša56ca9e42020-09-08 18:42:00 +0200137 CHECK_LOG("Invalid argument hash (lyht_remove_with_resize_cb()).", NULL);
Radek Krejci0ae092d2018-09-20 16:43:19 +0200138 }
139 /* removing present data, resize should happened
140 * when we are below 25% of the table filled, so with 3 records left */
Radek Krejcib4ac5a92020-11-23 17:54:33 +0100141 for ( ; i < 5; ++i) {
Radek Krejci0ae092d2018-09-20 16:43:19 +0200142 assert_int_equal(LY_SUCCESS, lyht_remove(ht, &i, i));
143 }
144 assert_int_equal(8, ht->size);
145
146 /* remove the rest */
Radek Krejcib4ac5a92020-11-23 17:54:33 +0100147 for ( ; i < 8; ++i) {
Radek Krejci0ae092d2018-09-20 16:43:19 +0200148 assert_int_equal(LY_SUCCESS, lyht_remove(ht, &i, i));
149 }
150
151 for (i = 0; i < 8; ++i) {
Michal Vaskoda859032020-07-14 12:20:14 +0200152 assert_int_equal(LY_ENOTFOUND, lyht_find(ht, &i, i, NULL));
Radek Krejci0ae092d2018-09-20 16:43:19 +0200153 }
154
155 /* cleanup */
156 lyht_free(ht);
157}
158
Radek Krejci0ae092d2018-09-20 16:43:19 +0200159static void
Radek Iša56ca9e42020-09-08 18:42:00 +0200160test_ht_collisions(void **UNUSED(state))
Radek Krejci0ae092d2018-09-20 16:43:19 +0200161{
Radek Krejci0ae092d2018-09-20 16:43:19 +0200162#define GET_REC_INT(rec) (*((uint32_t *)&(rec)->val))
163
164 uint32_t i;
165 struct ht_rec *rec;
166 struct hash_table *ht;
167
168 assert_non_null(ht = lyht_new(8, sizeof(int), ht_equal_clb, NULL, 1));
169
170 for (i = 2; i < 6; ++i) {
171 assert_int_equal(lyht_insert(ht, &i, 2, NULL), 0);
172 }
173
174 /* check all records */
175 for (i = 0; i < 2; ++i) {
176 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
177 assert_int_equal(rec->hits, 0);
178 }
179 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
180 assert_int_equal(rec->hits, 4);
181 assert_int_equal(GET_REC_INT(rec), i);
182 ++i;
Radek Krejcib4ac5a92020-11-23 17:54:33 +0100183 for ( ; i < 6; ++i) {
Radek Krejci0ae092d2018-09-20 16:43:19 +0200184 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
185 assert_int_equal(rec->hits, 1);
186 assert_int_equal(GET_REC_INT(rec), i);
187 }
Radek Krejcib4ac5a92020-11-23 17:54:33 +0100188 for ( ; i < 8; ++i) {
Radek Krejci0ae092d2018-09-20 16:43:19 +0200189 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
190 assert_int_equal(rec->hits, 0);
191 }
192
193 i = 4;
194 assert_int_equal(lyht_remove(ht, &i, 2), 0);
195
196 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
197 assert_int_equal(rec->hits, -1);
198
199 i = 2;
200 assert_int_equal(lyht_remove(ht, &i, 2), 0);
201
202 /* check all records */
203 for (i = 0; i < 2; ++i) {
204 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
205 assert_int_equal(rec->hits, 0);
206 }
207 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
208 assert_int_equal(rec->hits, 2);
209 assert_int_equal(GET_REC_INT(rec), 5);
210 ++i;
211 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
212 assert_int_equal(rec->hits, 1);
213 assert_int_equal(GET_REC_INT(rec), 3);
214 ++i;
Radek Krejcib4ac5a92020-11-23 17:54:33 +0100215 for ( ; i < 6; ++i) {
Radek Krejci0ae092d2018-09-20 16:43:19 +0200216 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
217 assert_int_equal(rec->hits, -1);
218 }
Radek Krejcib4ac5a92020-11-23 17:54:33 +0100219 for ( ; i < 8; ++i) {
Radek Krejci0ae092d2018-09-20 16:43:19 +0200220 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
221 assert_int_equal(rec->hits, 0);
222 }
223
224 for (i = 0; i < 3; ++i) {
Michal Vaskoda859032020-07-14 12:20:14 +0200225 assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
Radek Krejci0ae092d2018-09-20 16:43:19 +0200226 }
Michal Vaskoda859032020-07-14 12:20:14 +0200227 assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_SUCCESS);
Radek Krejci0ae092d2018-09-20 16:43:19 +0200228 ++i;
Michal Vaskoda859032020-07-14 12:20:14 +0200229 assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
Radek Krejci0ae092d2018-09-20 16:43:19 +0200230 ++i;
Michal Vaskoda859032020-07-14 12:20:14 +0200231 assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_SUCCESS);
Radek Krejci0ae092d2018-09-20 16:43:19 +0200232 ++i;
Radek Krejcib4ac5a92020-11-23 17:54:33 +0100233 for ( ; i < 8; ++i) {
Michal Vaskoda859032020-07-14 12:20:14 +0200234 assert_int_equal(lyht_find(ht, &i, 2, NULL), LY_ENOTFOUND);
Radek Krejci0ae092d2018-09-20 16:43:19 +0200235 }
236
237 i = 3;
238 assert_int_equal(lyht_remove(ht, &i, 2), 0);
239 i = 5;
240 assert_int_equal(lyht_remove(ht, &i, 2), 0);
241
242 /* check all records */
243 for (i = 0; i < 2; ++i) {
244 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
245 assert_int_equal(rec->hits, 0);
246 }
Radek Krejcib4ac5a92020-11-23 17:54:33 +0100247 for ( ; i < 6; ++i) {
Radek Krejci0ae092d2018-09-20 16:43:19 +0200248 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
249 assert_int_equal(rec->hits, -1);
250 }
Radek Krejcib4ac5a92020-11-23 17:54:33 +0100251 for ( ; i < 8; ++i) {
Radek Krejci0ae092d2018-09-20 16:43:19 +0200252 rec = lyht_get_rec(ht->recs, ht->rec_size, i);
253 assert_int_equal(rec->hits, 0);
254 }
255
256 lyht_free(ht);
257}
258
Radek Krejcib4ac5a92020-11-23 17:54:33 +0100259int
260main(void)
Radek Krejciaaf6d402018-09-20 15:14:47 +0200261{
262 const struct CMUnitTest tests[] = {
Radek Iša56ca9e42020-09-08 18:42:00 +0200263 UTEST(test_invalid_arguments),
264 UTEST(test_dict_hit),
265 UTEST(test_ht_basic),
266 UTEST(test_ht_resize),
267 UTEST(test_ht_collisions),
Radek Krejciaaf6d402018-09-20 15:14:47 +0200268 };
269
270 return cmocka_run_group_tests(tests, NULL, NULL);
271}