1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright 2016, Olivier MATZ <zer0@droids-corp.org>
15 #include <ecoli_init.h>
16 #include <ecoli_malloc.h>
17 #include <ecoli_log.h>
18 #include <ecoli_test.h>
19 #include <ecoli_murmurhash.h>
20 #include <ecoli_keyval.h>
24 EC_LOG_TYPE_REGISTER(keyval);
26 static uint32_t ec_keyval_seed;
28 struct ec_keyval_elt {
32 ec_keyval_elt_free_t free;
33 unsigned int refcount;
36 struct ec_keyval_elt_ref {
37 LIST_ENTRY(ec_keyval_elt_ref) next;
38 struct ec_keyval_elt *elt;
41 LIST_HEAD(ec_keyval_elt_ref_list, ec_keyval_elt_ref);
46 struct ec_keyval_elt_ref_list *table;
49 struct ec_keyval *ec_keyval(void)
51 struct ec_keyval *keyval;
53 keyval = ec_calloc(1, sizeof(*keyval));
60 static struct ec_keyval_elt_ref *
61 ec_keyval_lookup(const struct ec_keyval *keyval, const char *key)
63 struct ec_keyval_elt_ref *ref;
64 uint32_t h, mask = keyval->table_size - 1;
66 if (keyval == NULL || key == NULL) {
70 if (keyval->table_size == 0) {
75 h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
76 LIST_FOREACH(ref, &keyval->table[h & mask], next) {
77 if (strcmp(ref->elt->key, key) == 0) {
87 static void ec_keyval_elt_ref_free(struct ec_keyval_elt_ref *ref)
89 struct ec_keyval_elt *elt;
95 if (elt != NULL && --elt->refcount == 0) {
97 if (elt->free != NULL)
104 bool ec_keyval_has_key(const struct ec_keyval *keyval, const char *key)
106 return !!ec_keyval_lookup(keyval, key);
109 void *ec_keyval_get(const struct ec_keyval *keyval, const char *key)
111 struct ec_keyval_elt_ref *ref;
113 ref = ec_keyval_lookup(keyval, key);
117 return ref->elt->val;
120 int ec_keyval_del(struct ec_keyval *keyval, const char *key)
122 struct ec_keyval_elt_ref *ref;
124 ref = ec_keyval_lookup(keyval, key);
128 /* we could resize table here */
130 LIST_REMOVE(ref, next);
131 ec_keyval_elt_ref_free(ref);
137 static int ec_keyval_table_resize(struct ec_keyval *keyval, size_t new_size)
139 struct ec_keyval_elt_ref_list *new_table;
140 struct ec_keyval_elt_ref *ref;
143 if (new_size == 0 || (new_size & (new_size - 1))) {
148 new_table = ec_calloc(new_size, sizeof(*keyval->table));
149 if (new_table == NULL)
152 for (i = 0; i < keyval->table_size; i++) {
153 while (!LIST_EMPTY(&keyval->table[i])) {
154 ref = LIST_FIRST(&keyval->table[i]);
155 LIST_REMOVE(ref, next);
157 &new_table[ref->elt->hash & (new_size - 1)],
162 ec_free(keyval->table);
163 keyval->table = new_table;
164 keyval->table_size = new_size;
170 __ec_keyval_set(struct ec_keyval *keyval, struct ec_keyval_elt_ref *ref)
176 /* remove previous entry if any */
177 ec_keyval_del(keyval, ref->elt->key);
179 if (keyval->len >= keyval->table_size) {
180 if (keyval->table_size != 0)
181 new_size = keyval->table_size << FACTOR;
183 new_size = 1 << FACTOR;
184 ret = ec_keyval_table_resize(keyval, new_size);
189 mask = keyval->table_size - 1;
190 LIST_INSERT_HEAD(&keyval->table[ref->elt->hash & mask], ref, next);
196 int ec_keyval_set(struct ec_keyval *keyval, const char *key, void *val,
197 ec_keyval_elt_free_t free_cb)
199 struct ec_keyval_elt *elt = NULL;
200 struct ec_keyval_elt_ref *ref = NULL;
203 if (keyval == NULL || key == NULL) {
208 ref = ec_calloc(1, sizeof(*ref));
212 elt = ec_calloc(1, sizeof(*elt));
221 elt->key = ec_strdup(key);
222 if (elt->key == NULL)
224 h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
227 if (__ec_keyval_set(keyval, ref) < 0)
233 if (free_cb != NULL && val != NULL)
235 ec_keyval_elt_ref_free(ref);
239 void ec_keyval_free(struct ec_keyval *keyval)
241 struct ec_keyval_elt_ref *ref;
247 for (i = 0; i < keyval->table_size; i++) {
248 while (!LIST_EMPTY(&keyval->table[i])) {
249 ref = LIST_FIRST(&keyval->table[i]);
250 LIST_REMOVE(ref, next);
251 ec_keyval_elt_ref_free(ref);
254 ec_free(keyval->table);
258 size_t ec_keyval_len(const struct ec_keyval *keyval)
263 void ec_keyval_dump(FILE *out, const struct ec_keyval *keyval)
265 struct ec_keyval_elt_ref *ref;
268 if (keyval == NULL) {
269 fprintf(out, "empty keyval\n");
273 fprintf(out, "keyval:\n");
274 for (i = 0; i < keyval->table_size; i++) {
275 LIST_FOREACH(ref, &keyval->table[i], next) {
276 fprintf(out, " %s: %p\n",
277 ref->elt->key, ref->elt->val);
282 struct ec_keyval *ec_keyval_dup(const struct ec_keyval *keyval)
284 struct ec_keyval *dup = NULL;
285 struct ec_keyval_elt_ref *ref, *dup_ref = NULL;
292 for (i = 0; i < keyval->table_size; i++) {
293 LIST_FOREACH(ref, &keyval->table[i], next) {
294 dup_ref = ec_calloc(1, sizeof(*ref));
297 dup_ref->elt = ref->elt;
298 ref->elt->refcount++;
300 if (__ec_keyval_set(dup, dup_ref) < 0)
308 ec_keyval_elt_ref_free(dup_ref);
313 static int ec_keyval_init_func(void)
318 fd = open("/dev/urandom", 0);
320 fprintf(stderr, "failed to open /dev/urandom\n");
323 ret = read(fd, &ec_keyval_seed, sizeof(ec_keyval_seed));
324 if (ret != sizeof(ec_keyval_seed)) {
325 fprintf(stderr, "failed to read /dev/urandom\n");
332 static struct ec_init ec_keyval_init = {
333 .init = ec_keyval_init_func,
337 EC_INIT_REGISTER(ec_keyval_init);
339 /* LCOV_EXCL_START */
340 static int ec_keyval_testcase(void)
342 struct ec_keyval *keyval, *dup;
345 int ret, testres = 0;
347 keyval = ec_keyval();
348 if (keyval == NULL) {
349 EC_LOG(EC_LOG_ERR, "cannot create keyval\n");
353 testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 0, "bad keyval len");
354 ret = ec_keyval_set(keyval, "key1", "val1", NULL);
355 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
356 ret = ec_keyval_set(keyval, "key2", ec_strdup("val2"), ec_free_func);
357 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
358 testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2, "bad keyval len");
360 val = ec_keyval_get(keyval, "key1");
361 testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val1"),
362 "invalid keyval value");
363 val = ec_keyval_get(keyval, "key2");
364 testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val2"),
365 "invalid keyval value");
366 val = ec_keyval_get(keyval, "key3");
367 testres |= EC_TEST_CHECK(val == NULL, "key3 should be NULL");
369 ret = ec_keyval_set(keyval, "key1", "another_val1", NULL);
370 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
371 ret = ec_keyval_set(keyval, "key2", ec_strdup("another_val2"),
373 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
374 testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2,
377 val = ec_keyval_get(keyval, "key1");
378 testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val1"),
379 "invalid keyval value");
380 val = ec_keyval_get(keyval, "key2");
381 testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val2"),
382 "invalid keyval value");
383 testres |= EC_TEST_CHECK(ec_keyval_has_key(keyval, "key1"),
384 "key1 should be in keyval");
386 ret = ec_keyval_del(keyval, "key1");
387 testres |= EC_TEST_CHECK(ret == 0, "cannot del key");
388 testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 1,
389 "invalid keyval len");
391 ec_keyval_dump(stdout, NULL);
392 ec_keyval_dump(stdout, keyval);
394 for (i = 0; i < 100; i++) {
396 snprintf(key, sizeof(key), "k%zd", i);
397 ret = ec_keyval_set(keyval, key, "val", NULL);
398 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
400 dup = ec_keyval_dup(keyval);
401 testres |= EC_TEST_CHECK(dup != NULL, "cannot duplicate keyval");
403 for (i = 0; i < 100; i++) {
405 snprintf(key, sizeof(key), "k%zd", i);
406 val = ec_keyval_get(dup, key);
407 testres |= EC_TEST_CHECK(
408 val != NULL && !strcmp(val, "val"),
409 "invalid keyval value");
416 ret = ec_keyval_set(keyval, NULL, "val1", NULL);
417 testres |= EC_TEST_CHECK(ret == -1, "should not be able to set key");
418 val = ec_keyval_get(keyval, NULL);
419 testres |= EC_TEST_CHECK(val == NULL, "get(NULL) should no success");
421 ec_keyval_free(keyval);
427 static struct ec_test ec_keyval_test = {
429 .test = ec_keyval_testcase,
432 EC_TEST_REGISTER(ec_keyval_test);