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;
370 keyval = ec_keyval();
371 if (keyval == NULL) {
372 EC_LOG(EC_LOG_ERR, "cannot create keyval\n");
376 EC_TEST_ASSERT(ec_keyval_len(keyval) == 0);
377 ret = ec_keyval_set(keyval, "key1", "val1", NULL);
378 EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
379 ret = ec_keyval_set(keyval, "key2", ec_strdup("val2"), ec_free_func);
380 EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
381 EC_TEST_ASSERT(ec_keyval_len(keyval) == 2);
383 val = ec_keyval_get(keyval, "key1");
384 EC_TEST_ASSERT(val != NULL && !strcmp(val, "val1"));
385 val = ec_keyval_get(keyval, "key2");
386 EC_TEST_ASSERT(val != NULL && !strcmp(val, "val2"));
387 val = ec_keyval_get(keyval, "key3");
388 EC_TEST_ASSERT(val == NULL);
390 ret = ec_keyval_set(keyval, "key1", "another_val1", NULL);
391 EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
392 ret = ec_keyval_set(keyval, "key2", ec_strdup("another_val2"),
394 EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
395 EC_TEST_ASSERT(ec_keyval_len(keyval) == 2);
397 val = ec_keyval_get(keyval, "key1");
398 EC_TEST_ASSERT(val != NULL && !strcmp(val, "another_val1"));
399 val = ec_keyval_get(keyval, "key2");
400 EC_TEST_ASSERT(val != NULL && !strcmp(val, "another_val2"));
401 EC_TEST_ASSERT(ec_keyval_has_key(keyval, "key1"));
403 ret = ec_keyval_del(keyval, "key1");
404 EC_TEST_ASSERT_STR(ret == 0, "cannot del key");
405 EC_TEST_ASSERT(ec_keyval_len(keyval) == 1);
407 ec_keyval_dump(stdout, NULL);
408 ec_keyval_dump(stdout, keyval);
410 for (i = 0; i < 100; i++) {
412 snprintf(key, sizeof(key), "k%zd", i);
413 ret = ec_keyval_set(keyval, key, "val", NULL);
414 EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
416 dup = ec_keyval_dup(keyval);
417 EC_TEST_ASSERT_STR(dup != NULL, "cannot duplicate keyval");
419 for (i = 0; i < 100; i++) {
421 snprintf(key, sizeof(key), "k%zd", i);
422 val = ec_keyval_get(dup, key);
423 EC_TEST_ASSERT(val != NULL && !strcmp(val, "val"));
430 ret = ec_keyval_set(keyval, NULL, "val1", NULL);
431 EC_TEST_ASSERT(ret == -1);
432 val = ec_keyval_get(keyval, NULL);
433 EC_TEST_ASSERT(val == NULL);
435 ec_keyval_free(keyval);
441 static struct ec_test ec_keyval_test = {
443 .test = ec_keyval_testcase,
446 EC_TEST_REGISTER(ec_keyval_test);