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_iter {
50 const struct ec_keyval *keyval;
52 const struct ec_keyval_elt_ref *cur_ref;
55 struct ec_keyval *ec_keyval(void)
57 struct ec_keyval *keyval;
59 keyval = ec_calloc(1, sizeof(*keyval));
66 static struct ec_keyval_elt_ref *
67 ec_keyval_lookup(const struct ec_keyval *keyval, const char *key)
69 struct ec_keyval_elt_ref *ref;
70 uint32_t h, mask = keyval->table_size - 1;
72 if (keyval == NULL || key == NULL) {
76 if (keyval->table_size == 0) {
81 h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
82 LIST_FOREACH(ref, &keyval->table[h & mask], next) {
83 if (strcmp(ref->elt->key, key) == 0)
91 static void ec_keyval_elt_ref_free(struct ec_keyval_elt_ref *ref)
93 struct ec_keyval_elt *elt;
99 if (elt != NULL && --elt->refcount == 0) {
101 if (elt->free != NULL)
108 bool ec_keyval_has_key(const struct ec_keyval *keyval, const char *key)
110 return !!ec_keyval_lookup(keyval, key);
113 void *ec_keyval_get(const struct ec_keyval *keyval, const char *key)
115 struct ec_keyval_elt_ref *ref;
117 ref = ec_keyval_lookup(keyval, key);
121 return ref->elt->val;
124 int ec_keyval_del(struct ec_keyval *keyval, const char *key)
126 struct ec_keyval_elt_ref *ref;
128 ref = ec_keyval_lookup(keyval, key);
132 /* we could resize table here */
134 LIST_REMOVE(ref, next);
135 ec_keyval_elt_ref_free(ref);
141 static int ec_keyval_table_resize(struct ec_keyval *keyval, size_t new_size)
143 struct ec_keyval_elt_ref_list *new_table;
144 struct ec_keyval_elt_ref *ref;
147 if (new_size == 0 || (new_size & (new_size - 1))) {
152 new_table = ec_calloc(new_size, sizeof(*keyval->table));
153 if (new_table == NULL)
156 for (i = 0; i < keyval->table_size; i++) {
157 while (!LIST_EMPTY(&keyval->table[i])) {
158 ref = LIST_FIRST(&keyval->table[i]);
159 LIST_REMOVE(ref, next);
161 &new_table[ref->elt->hash & (new_size - 1)],
166 ec_free(keyval->table);
167 keyval->table = new_table;
168 keyval->table_size = new_size;
174 __ec_keyval_set(struct ec_keyval *keyval, struct ec_keyval_elt_ref *ref)
180 /* remove previous entry if any */
181 ec_keyval_del(keyval, ref->elt->key);
183 if (keyval->len >= keyval->table_size) {
184 if (keyval->table_size != 0)
185 new_size = keyval->table_size << FACTOR;
187 new_size = 1 << FACTOR;
188 ret = ec_keyval_table_resize(keyval, new_size);
193 mask = keyval->table_size - 1;
194 LIST_INSERT_HEAD(&keyval->table[ref->elt->hash & mask], ref, next);
200 int ec_keyval_set(struct ec_keyval *keyval, const char *key, void *val,
201 ec_keyval_elt_free_t free_cb)
203 struct ec_keyval_elt *elt = NULL;
204 struct ec_keyval_elt_ref *ref = NULL;
207 if (keyval == NULL || key == NULL) {
212 ref = ec_calloc(1, sizeof(*ref));
216 elt = ec_calloc(1, sizeof(*elt));
225 elt->key = ec_strdup(key);
226 if (elt->key == NULL)
228 h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
231 if (__ec_keyval_set(keyval, ref) < 0)
237 if (free_cb != NULL && val != NULL)
239 ec_keyval_elt_ref_free(ref);
243 void ec_keyval_free(struct ec_keyval *keyval)
245 struct ec_keyval_elt_ref *ref;
251 for (i = 0; i < keyval->table_size; i++) {
252 while (!LIST_EMPTY(&keyval->table[i])) {
253 ref = LIST_FIRST(&keyval->table[i]);
254 LIST_REMOVE(ref, next);
255 ec_keyval_elt_ref_free(ref);
258 ec_free(keyval->table);
262 size_t ec_keyval_len(const struct ec_keyval *keyval)
268 ec_keyval_iter_free(struct ec_keyval_iter *iter)
273 struct ec_keyval_iter *
274 ec_keyval_iter(const struct ec_keyval *keyval)
276 struct ec_keyval_iter *iter = NULL;
278 iter = ec_calloc(1, sizeof(*iter));
282 iter->keyval = keyval;
284 iter->cur_ref = NULL;
286 ec_keyval_iter_next(iter);
292 ec_keyval_iter_next(struct ec_keyval_iter *iter)
294 const struct ec_keyval_elt_ref *ref;
298 if (i == iter->keyval->table_size)
299 return; /* no more element */
301 if (iter->cur_ref != NULL) {
302 ref = LIST_NEXT(iter->cur_ref, next);
310 for (; i < iter->keyval->table_size; i++) {
311 LIST_FOREACH(ref, &iter->keyval->table[i], next) {
313 iter->cur_ref = LIST_FIRST(&iter->keyval->table[i]);
318 iter->cur_idx = iter->keyval->table_size;
319 iter->cur_ref = NULL;
323 ec_keyval_iter_valid(const struct ec_keyval_iter *iter)
325 if (iter == NULL || iter->cur_ref == NULL)
332 ec_keyval_iter_get_key(const struct ec_keyval_iter *iter)
334 if (iter == NULL || iter->cur_ref == NULL)
337 return iter->cur_ref->elt->key;
341 ec_keyval_iter_get_val(const struct ec_keyval_iter *iter)
343 if (iter == NULL || iter->cur_ref == NULL)
346 return iter->cur_ref->elt->val;
349 void ec_keyval_dump(FILE *out, const struct ec_keyval *keyval)
351 struct ec_keyval_iter *iter;
353 if (keyval == NULL) {
354 fprintf(out, "empty keyval\n");
358 fprintf(out, "keyval:\n");
359 for (iter = ec_keyval_iter(keyval);
360 ec_keyval_iter_valid(iter);
361 ec_keyval_iter_next(iter)) {
362 fprintf(out, " %s: %p\n",
363 ec_keyval_iter_get_key(iter),
364 ec_keyval_iter_get_val(iter));
366 ec_keyval_iter_free(iter);
369 struct ec_keyval *ec_keyval_dup(const struct ec_keyval *keyval)
371 struct ec_keyval *dup = NULL;
372 struct ec_keyval_elt_ref *ref, *dup_ref = NULL;
379 for (i = 0; i < keyval->table_size; i++) {
380 LIST_FOREACH(ref, &keyval->table[i], next) {
381 dup_ref = ec_calloc(1, sizeof(*ref));
384 dup_ref->elt = ref->elt;
385 ref->elt->refcount++;
387 if (__ec_keyval_set(dup, dup_ref) < 0)
395 ec_keyval_elt_ref_free(dup_ref);
400 static int ec_keyval_init_func(void)
405 return 0;//XXX for test reproduceability
407 fd = open("/dev/urandom", 0);
409 fprintf(stderr, "failed to open /dev/urandom\n");
412 ret = read(fd, &ec_keyval_seed, sizeof(ec_keyval_seed));
413 if (ret != sizeof(ec_keyval_seed)) {
414 fprintf(stderr, "failed to read /dev/urandom\n");
421 static struct ec_init ec_keyval_init = {
422 .init = ec_keyval_init_func,
426 EC_INIT_REGISTER(ec_keyval_init);
428 /* LCOV_EXCL_START */
429 static int ec_keyval_testcase(void)
431 struct ec_keyval *keyval, *dup;
432 struct ec_keyval_iter *iter;
435 int ret, testres = 0;
440 keyval = ec_keyval();
441 if (keyval == NULL) {
442 EC_LOG(EC_LOG_ERR, "cannot create keyval\n");
447 for (iter = ec_keyval_iter(keyval);
448 ec_keyval_iter_valid(iter);
449 ec_keyval_iter_next(iter)) {
452 ec_keyval_iter_free(iter);
453 testres |= EC_TEST_CHECK(count == 0, "invalid count in iterator");
455 testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 0, "bad keyval len");
456 ret = ec_keyval_set(keyval, "key1", "val1", NULL);
457 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
458 ret = ec_keyval_set(keyval, "key2", ec_strdup("val2"), ec_free_func);
459 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
460 testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2, "bad keyval len");
462 val = ec_keyval_get(keyval, "key1");
463 testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val1"),
464 "invalid keyval value");
465 val = ec_keyval_get(keyval, "key2");
466 testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val2"),
467 "invalid keyval value");
468 val = ec_keyval_get(keyval, "key3");
469 testres |= EC_TEST_CHECK(val == NULL, "key3 should be NULL");
471 ret = ec_keyval_set(keyval, "key1", "another_val1", NULL);
472 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
473 ret = ec_keyval_set(keyval, "key2", ec_strdup("another_val2"),
475 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
476 testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2,
479 val = ec_keyval_get(keyval, "key1");
480 testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val1"),
481 "invalid keyval value");
482 val = ec_keyval_get(keyval, "key2");
483 testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val2"),
484 "invalid keyval value");
485 testres |= EC_TEST_CHECK(ec_keyval_has_key(keyval, "key1"),
486 "key1 should be in keyval");
488 f = open_memstream(&buf, &buflen);
491 ec_keyval_dump(f, NULL);
497 f = open_memstream(&buf, &buflen);
500 ec_keyval_dump(f, keyval);
506 ret = ec_keyval_del(keyval, "key1");
507 testres |= EC_TEST_CHECK(ret == 0, "cannot del key1");
508 testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 1,
509 "invalid keyval len");
510 ret = ec_keyval_del(keyval, "key2");
511 testres |= EC_TEST_CHECK(ret == 0, "cannot del key2");
512 testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 0,
513 "invalid keyval len");
515 for (i = 0; i < 100; i++) {
517 snprintf(key, sizeof(key), "k%zd", i);
518 ret = ec_keyval_set(keyval, key, "val", NULL);
519 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
521 dup = ec_keyval_dup(keyval);
522 testres |= EC_TEST_CHECK(dup != NULL, "cannot duplicate keyval");
524 for (i = 0; i < 100; i++) {
526 snprintf(key, sizeof(key), "k%zd", i);
527 val = ec_keyval_get(dup, key);
528 testres |= EC_TEST_CHECK(
529 val != NULL && !strcmp(val, "val"),
530 "invalid keyval value");
537 for (iter = ec_keyval_iter(keyval);
538 ec_keyval_iter_valid(iter);
539 ec_keyval_iter_next(iter)) {
542 ec_keyval_iter_free(iter);
543 testres |= EC_TEST_CHECK(count == 100, "invalid count in iterator");
546 ret = ec_keyval_set(keyval, NULL, "val1", NULL);
547 testres |= EC_TEST_CHECK(ret == -1, "should not be able to set key");
548 val = ec_keyval_get(keyval, NULL);
549 testres |= EC_TEST_CHECK(val == NULL, "get(NULL) should no success");
551 ec_keyval_free(keyval);
556 ec_keyval_free(keyval);
564 static struct ec_test ec_keyval_test = {
566 .test = ec_keyval_testcase,
569 EC_TEST_REGISTER(ec_keyval_test);