2 * Copyright (c) 2016, Olivier MATZ <zer0@droids-corp.org>
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
7 * * Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of the University of California, Berkeley nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
16 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
17 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
20 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 #include <sys/types.h>
30 #include <sys/queue.h>
38 #include <ecoli_init.h>
39 #include <ecoli_malloc.h>
40 #include <ecoli_log.h>
41 #include <ecoli_test.h>
42 #include <ecoli_murmurhash.h>
43 #include <ecoli_keyval.h>
47 EC_LOG_TYPE_REGISTER(keyval);
49 static uint32_t ec_keyval_seed;
51 struct ec_keyval_elt {
55 ec_keyval_elt_free_t free;
56 unsigned int refcount;
59 struct ec_keyval_elt_ref {
60 LIST_ENTRY(ec_keyval_elt_ref) next;
61 struct ec_keyval_elt *elt;
64 LIST_HEAD(ec_keyval_elt_ref_list, ec_keyval_elt_ref);
69 struct ec_keyval_elt_ref_list *table;
72 struct ec_keyval *ec_keyval(void)
74 struct ec_keyval *keyval;
76 keyval = ec_calloc(1, sizeof(*keyval));
83 static struct ec_keyval_elt_ref *
84 ec_keyval_lookup(const struct ec_keyval *keyval, const char *key)
86 struct ec_keyval_elt_ref *ref;
87 uint32_t h, mask = keyval->table_size - 1;
89 if (keyval == NULL || key == NULL) {
93 if (keyval->table_size == 0) {
98 h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
99 LIST_FOREACH(ref, &keyval->table[h & mask], next) {
100 if (strcmp(ref->elt->key, key) == 0) {
110 static void ec_keyval_elt_ref_free(struct ec_keyval_elt_ref *ref)
112 struct ec_keyval_elt *elt;
118 if (elt != NULL && --elt->refcount == 0) {
120 if (elt->free != NULL)
127 bool ec_keyval_has_key(const struct ec_keyval *keyval, const char *key)
129 return !!ec_keyval_lookup(keyval, key);
132 void *ec_keyval_get(const struct ec_keyval *keyval, const char *key)
134 struct ec_keyval_elt_ref *ref;
136 ref = ec_keyval_lookup(keyval, key);
140 return ref->elt->val;
143 int ec_keyval_del(struct ec_keyval *keyval, const char *key)
145 struct ec_keyval_elt_ref *ref;
147 ref = ec_keyval_lookup(keyval, key);
151 /* we could resize table here */
153 LIST_REMOVE(ref, next);
154 ec_keyval_elt_ref_free(ref);
160 static int ec_keyval_table_resize(struct ec_keyval *keyval, size_t new_size)
162 struct ec_keyval_elt_ref_list *new_table;
163 struct ec_keyval_elt_ref *ref;
166 if (new_size == 0 || (new_size & (new_size - 1))) {
171 new_table = ec_calloc(new_size, sizeof(*keyval->table));
172 if (new_table == NULL)
175 for (i = 0; i < keyval->table_size; i++) {
176 while (!LIST_EMPTY(&keyval->table[i])) {
177 ref = LIST_FIRST(&keyval->table[i]);
178 LIST_REMOVE(ref, next);
180 &new_table[ref->elt->hash & (new_size - 1)],
185 ec_free(keyval->table);
186 keyval->table = new_table;
187 keyval->table_size = new_size;
193 __ec_keyval_set(struct ec_keyval *keyval, struct ec_keyval_elt_ref *ref)
199 /* remove previous entry if any */
200 ec_keyval_del(keyval, ref->elt->key);
202 if (keyval->len >= keyval->table_size) {
203 if (keyval->table_size != 0)
204 new_size = keyval->table_size << FACTOR;
206 new_size = 1 << FACTOR;
207 ret = ec_keyval_table_resize(keyval, new_size);
212 mask = keyval->table_size - 1;
213 LIST_INSERT_HEAD(&keyval->table[ref->elt->hash & mask], ref, next);
219 int ec_keyval_set(struct ec_keyval *keyval, const char *key, void *val,
220 ec_keyval_elt_free_t free_cb)
222 struct ec_keyval_elt *elt = NULL;
223 struct ec_keyval_elt_ref *ref = NULL;
226 if (keyval == NULL || key == NULL) {
231 ref = ec_calloc(1, sizeof(*ref));
235 elt = ec_calloc(1, sizeof(*elt));
244 elt->key = ec_strdup(key);
245 if (elt->key == NULL)
247 h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
250 if (__ec_keyval_set(keyval, ref) < 0)
256 if (free_cb != NULL && val != NULL)
258 ec_keyval_elt_ref_free(ref);
262 void ec_keyval_free(struct ec_keyval *keyval)
264 struct ec_keyval_elt_ref *ref;
270 for (i = 0; i < keyval->table_size; i++) {
271 while (!LIST_EMPTY(&keyval->table[i])) {
272 ref = LIST_FIRST(&keyval->table[i]);
273 LIST_REMOVE(ref, next);
274 ec_keyval_elt_ref_free(ref);
277 ec_free(keyval->table);
281 size_t ec_keyval_len(const struct ec_keyval *keyval)
286 void ec_keyval_dump(FILE *out, const struct ec_keyval *keyval)
288 struct ec_keyval_elt_ref *ref;
291 if (keyval == NULL) {
292 fprintf(out, "empty keyval\n");
296 fprintf(out, "keyval:\n");
297 for (i = 0; i < keyval->table_size; i++) {
298 LIST_FOREACH(ref, &keyval->table[i], next) {
299 fprintf(out, " %s: %p\n",
300 ref->elt->key, ref->elt->val);
305 struct ec_keyval *ec_keyval_dup(const struct ec_keyval *keyval)
307 struct ec_keyval *dup = NULL;
308 struct ec_keyval_elt_ref *ref, *dup_ref = NULL;
315 for (i = 0; i < keyval->table_size; i++) {
316 LIST_FOREACH(ref, &keyval->table[i], next) {
317 dup_ref = ec_calloc(1, sizeof(*ref));
320 dup_ref->elt = ref->elt;
321 ref->elt->refcount++;
323 if (__ec_keyval_set(dup, dup_ref) < 0)
331 ec_keyval_elt_ref_free(dup_ref);
336 static int ec_keyval_init_func(void)
341 fd = open("/dev/urandom", 0);
343 fprintf(stderr, "failed to open /dev/urandom\n");
346 ret = read(fd, &ec_keyval_seed, sizeof(ec_keyval_seed));
347 if (ret != sizeof(ec_keyval_seed)) {
348 fprintf(stderr, "failed to read /dev/urandom\n");
355 static struct ec_init ec_keyval_init = {
356 .init = ec_keyval_init_func,
360 EC_INIT_REGISTER(ec_keyval_init);
362 /* LCOV_EXCL_START */
363 static int ec_keyval_testcase(void)
365 struct ec_keyval *keyval, *dup;
368 int ret, testres = 0;
370 keyval = ec_keyval();
371 if (keyval == NULL) {
372 EC_LOG(EC_LOG_ERR, "cannot create keyval\n");
376 testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 0, "bad keyval len");
377 ret = ec_keyval_set(keyval, "key1", "val1", NULL);
378 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
379 ret = ec_keyval_set(keyval, "key2", ec_strdup("val2"), ec_free_func);
380 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
381 testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2, "bad keyval len");
383 val = ec_keyval_get(keyval, "key1");
384 testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val1"),
385 "invalid keyval value");
386 val = ec_keyval_get(keyval, "key2");
387 testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val2"),
388 "invalid keyval value");
389 val = ec_keyval_get(keyval, "key3");
390 testres |= EC_TEST_CHECK(val == NULL, "key3 should be NULL");
392 ret = ec_keyval_set(keyval, "key1", "another_val1", NULL);
393 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
394 ret = ec_keyval_set(keyval, "key2", ec_strdup("another_val2"),
396 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
397 testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2,
400 val = ec_keyval_get(keyval, "key1");
401 testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val1"),
402 "invalid keyval value");
403 val = ec_keyval_get(keyval, "key2");
404 testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val2"),
405 "invalid keyval value");
406 testres |= EC_TEST_CHECK(ec_keyval_has_key(keyval, "key1"),
407 "key1 should be in keyval");
409 ret = ec_keyval_del(keyval, "key1");
410 testres |= EC_TEST_CHECK(ret == 0, "cannot del key");
411 testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 1,
412 "invalid keyval len");
414 ec_keyval_dump(stdout, NULL);
415 ec_keyval_dump(stdout, keyval);
417 for (i = 0; i < 100; i++) {
419 snprintf(key, sizeof(key), "k%zd", i);
420 ret = ec_keyval_set(keyval, key, "val", NULL);
421 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
423 dup = ec_keyval_dup(keyval);
424 testres |= EC_TEST_CHECK(dup != NULL, "cannot duplicate keyval");
426 for (i = 0; i < 100; i++) {
428 snprintf(key, sizeof(key), "k%zd", i);
429 val = ec_keyval_get(dup, key);
430 testres |= EC_TEST_CHECK(
431 val != NULL && !strcmp(val, "val"),
432 "invalid keyval value");
439 ret = ec_keyval_set(keyval, NULL, "val1", NULL);
440 testres |= EC_TEST_CHECK(ret == -1, "should not be able to set key");
441 val = ec_keyval_get(keyval, NULL);
442 testres |= EC_TEST_CHECK(val == NULL, "get(NULL) should no success");
444 ec_keyval_free(keyval);
450 static struct ec_test ec_keyval_test = {
452 .test = ec_keyval_testcase,
455 EC_TEST_REGISTER(ec_keyval_test);