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 {
52 LIST_ENTRY(ec_keyval_elt) next;
56 ec_keyval_elt_free_t free;
59 LIST_HEAD(ec_keyval_elt_list, ec_keyval_elt);
64 struct ec_keyval_elt_list *table;
67 struct ec_keyval *ec_keyval(void)
69 struct ec_keyval *keyval;
71 keyval = ec_calloc(1, sizeof(*keyval));
78 static struct ec_keyval_elt *ec_keyval_lookup(const struct ec_keyval *keyval,
81 struct ec_keyval_elt *elt;
82 uint32_t h, mask = keyval->table_size - 1;
84 if (keyval == NULL || key == NULL) {
88 if (keyval->table_size == 0) {
93 h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
94 LIST_FOREACH(elt, &keyval->table[h & mask], next) {
95 if (strcmp(elt->key, key) == 0) {
105 static void ec_keyval_elt_free(struct ec_keyval_elt *elt)
111 if (elt->free != NULL)
116 bool ec_keyval_has_key(const struct ec_keyval *keyval, const char *key)
118 return !!ec_keyval_lookup(keyval, key);
121 void *ec_keyval_get(const struct ec_keyval *keyval, const char *key)
123 struct ec_keyval_elt *elt;
125 elt = ec_keyval_lookup(keyval, key);
132 int ec_keyval_del(struct ec_keyval *keyval, const char *key)
134 struct ec_keyval_elt *elt;
136 elt = ec_keyval_lookup(keyval, key);
140 /* we could resize table here */
142 LIST_REMOVE(elt, next);
143 ec_keyval_elt_free(elt);
149 static int ec_keyval_table_resize(struct ec_keyval *keyval, size_t new_size)
151 struct ec_keyval_elt_list *new_table;
152 struct ec_keyval_elt *elt;
155 if (new_size == 0 || (new_size & (new_size - 1))) {
160 new_table = ec_calloc(new_size, sizeof(*keyval->table));
161 if (new_table == NULL)
164 for (i = 0; i < keyval->table_size; i++) {
165 while (!LIST_EMPTY(&keyval->table[i])) {
166 elt = LIST_FIRST(&keyval->table[i]);
167 LIST_REMOVE(elt, next);
168 LIST_INSERT_HEAD(&new_table[elt->hash & (new_size - 1)],
173 ec_free(keyval->table);
174 keyval->table = new_table;
175 keyval->table_size = new_size;
180 int ec_keyval_set(struct ec_keyval *keyval, const char *key, void *val,
181 ec_keyval_elt_free_t free_cb)
183 struct ec_keyval_elt *elt;
188 if (keyval == NULL || key == NULL) {
193 elt = ec_keyval_lookup(keyval, key);
195 if (elt->free != NULL)
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 elt = ec_calloc(1, sizeof(*elt));
215 elt->key = ec_strdup(key);
216 if (elt->key == NULL)
220 h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
223 mask = keyval->table_size - 1;
224 LIST_INSERT_HEAD(&keyval->table[h & mask], elt, next);
240 void ec_keyval_free(struct ec_keyval *keyval)
242 struct ec_keyval_elt *elt;
248 for (i = 0; i < keyval->table_size; i++) {
249 while (!LIST_EMPTY(&keyval->table[i])) {
250 elt = LIST_FIRST(&keyval->table[i]);
251 LIST_REMOVE(elt, next);
252 ec_keyval_elt_free(elt);
255 ec_free(keyval->table);
259 size_t ec_keyval_len(const struct ec_keyval *keyval)
264 void ec_keyval_dump(FILE *out, const struct ec_keyval *keyval)
266 struct ec_keyval_elt *elt;
269 if (keyval == NULL) {
270 fprintf(out, "empty keyval\n");
274 fprintf(out, "keyval:\n");
275 for (i = 0; i < keyval->table_size; i++) {
276 LIST_FOREACH(elt, &keyval->table[i], next) {
277 fprintf(out, " %s: %p\n",
283 static int ec_keyval_init_func(void)
288 fd = open("/dev/urandom", 0);
290 fprintf(stderr, "failed to open /dev/urandom\n");
293 ret = read(fd, &ec_keyval_seed, sizeof(ec_keyval_seed));
294 if (ret != sizeof(ec_keyval_seed)) {
295 fprintf(stderr, "failed to read /dev/urandom\n");
302 static struct ec_init ec_keyval_init = {
303 .init = ec_keyval_init_func,
307 EC_INIT_REGISTER(ec_keyval_init);
309 /* LCOV_EXCL_START */
310 static int ec_keyval_testcase(void)
312 struct ec_keyval *keyval;
317 keyval = ec_keyval();
318 if (keyval == NULL) {
319 EC_LOG(EC_LOG_ERR, "cannot create keyval\n");
323 EC_TEST_ASSERT(ec_keyval_len(keyval) == 0);
324 ret = ec_keyval_set(keyval, "key1", "val1", NULL);
325 EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
326 ret = ec_keyval_set(keyval, "key2", ec_strdup("val2"), ec_free_func);
327 EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
328 EC_TEST_ASSERT(ec_keyval_len(keyval) == 2);
330 val = ec_keyval_get(keyval, "key1");
331 EC_TEST_ASSERT(val != NULL && !strcmp(val, "val1"));
332 val = ec_keyval_get(keyval, "key2");
333 EC_TEST_ASSERT(val != NULL && !strcmp(val, "val2"));
334 val = ec_keyval_get(keyval, "key3");
335 EC_TEST_ASSERT(val == NULL);
337 ret = ec_keyval_set(keyval, "key1", "another_val1", NULL);
338 EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
339 ret = ec_keyval_set(keyval, "key2", ec_strdup("another_val2"),
341 EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
342 EC_TEST_ASSERT(ec_keyval_len(keyval) == 2);
344 val = ec_keyval_get(keyval, "key1");
345 EC_TEST_ASSERT(val != NULL && !strcmp(val, "another_val1"));
346 val = ec_keyval_get(keyval, "key2");
347 EC_TEST_ASSERT(val != NULL && !strcmp(val, "another_val2"));
348 EC_TEST_ASSERT(ec_keyval_has_key(keyval, "key1"));
350 ret = ec_keyval_del(keyval, "key1");
351 EC_TEST_ASSERT_STR(ret == 0, "cannot del key");
352 EC_TEST_ASSERT(ec_keyval_len(keyval) == 1);
354 ec_keyval_dump(stdout, NULL);
355 ec_keyval_dump(stdout, keyval);
357 for (i = 0; i < 100; i++) {
359 snprintf(buf, sizeof(buf), "k%zd", i);
360 ret = ec_keyval_set(keyval, buf, "val", NULL);
361 EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
365 ret = ec_keyval_set(keyval, NULL, "val1", NULL);
366 EC_TEST_ASSERT(ret == -1);
367 val = ec_keyval_get(keyval, NULL);
368 EC_TEST_ASSERT(val == NULL);
370 ec_keyval_free(keyval);
377 static struct ec_test ec_keyval_test = {
379 .test = ec_keyval_testcase,
382 EC_TEST_REGISTER(ec_keyval_test);