-/*
- * Copyright (c) 2016, Olivier MATZ <zer0@droids-corp.org>
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions are met:
- *
- * * Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- * * Neither the name of the University of California, Berkeley nor the
- * names of its contributors may be used to endorse or promote products
- * derived from this software without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
- * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
- * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
- * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
- * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
- * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
- * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright 2016, Olivier MATZ <zer0@droids-corp.org>
*/
#include <sys/types.h>
static uint32_t ec_keyval_seed;
struct ec_keyval_elt {
- LIST_ENTRY(ec_keyval_elt) next;
char *key;
void *val;
uint32_t hash;
ec_keyval_elt_free_t free;
+ unsigned int refcount;
};
-LIST_HEAD(ec_keyval_elt_list, ec_keyval_elt);
+struct ec_keyval_elt_ref {
+ LIST_ENTRY(ec_keyval_elt_ref) next;
+ struct ec_keyval_elt *elt;
+};
+
+LIST_HEAD(ec_keyval_elt_ref_list, ec_keyval_elt_ref);
struct ec_keyval {
size_t len;
size_t table_size;
- struct ec_keyval_elt_list *table;
+ struct ec_keyval_elt_ref_list *table;
+};
+
+struct ec_keyval_iter {
+ const struct ec_keyval *keyval;
+ size_t cur_idx;
+ const struct ec_keyval_elt_ref *cur_ref;
};
struct ec_keyval *ec_keyval(void)
return keyval;
}
-static struct ec_keyval_elt *ec_keyval_lookup(const struct ec_keyval *keyval,
- const char *key)
+static struct ec_keyval_elt_ref *
+ec_keyval_lookup(const struct ec_keyval *keyval, const char *key)
{
- struct ec_keyval_elt *elt;
+ struct ec_keyval_elt_ref *ref;
uint32_t h, mask = keyval->table_size - 1;
if (keyval == NULL || key == NULL) {
}
h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
- LIST_FOREACH(elt, &keyval->table[h & mask], next) {
- if (strcmp(elt->key, key) == 0) {
- errno = 0;
- return elt;
- }
+ LIST_FOREACH(ref, &keyval->table[h & mask], next) {
+ if (strcmp(ref->elt->key, key) == 0)
+ return ref;
}
errno = ENOENT;
return NULL;
}
-static void ec_keyval_elt_free(struct ec_keyval_elt *elt)
+static void ec_keyval_elt_ref_free(struct ec_keyval_elt_ref *ref)
{
- if (elt == NULL)
+ struct ec_keyval_elt *elt;
+
+ if (ref == NULL)
return;
- ec_free(elt->key);
- if (elt->free != NULL)
- elt->free(elt->val);
- ec_free(elt);
+ elt = ref->elt;
+ if (elt != NULL && --elt->refcount == 0) {
+ ec_free(elt->key);
+ if (elt->free != NULL)
+ elt->free(elt->val);
+ ec_free(elt);
+ }
+ ec_free(ref);
}
bool ec_keyval_has_key(const struct ec_keyval *keyval, const char *key)
void *ec_keyval_get(const struct ec_keyval *keyval, const char *key)
{
- struct ec_keyval_elt *elt;
+ struct ec_keyval_elt_ref *ref;
- elt = ec_keyval_lookup(keyval, key);
- if (elt == NULL)
+ ref = ec_keyval_lookup(keyval, key);
+ if (ref == NULL)
return NULL;
- return elt->val;
+ return ref->elt->val;
}
int ec_keyval_del(struct ec_keyval *keyval, const char *key)
{
- struct ec_keyval_elt *elt;
+ struct ec_keyval_elt_ref *ref;
- elt = ec_keyval_lookup(keyval, key);
- if (elt == NULL)
+ ref = ec_keyval_lookup(keyval, key);
+ if (ref == NULL)
return -1;
/* we could resize table here */
- LIST_REMOVE(elt, next);
- ec_keyval_elt_free(elt);
+ LIST_REMOVE(ref, next);
+ ec_keyval_elt_ref_free(ref);
keyval->len--;
return 0;
static int ec_keyval_table_resize(struct ec_keyval *keyval, size_t new_size)
{
- struct ec_keyval_elt_list *new_table;
- struct ec_keyval_elt *elt;
+ struct ec_keyval_elt_ref_list *new_table;
+ struct ec_keyval_elt_ref *ref;
size_t i;
if (new_size == 0 || (new_size & (new_size - 1))) {
for (i = 0; i < keyval->table_size; i++) {
while (!LIST_EMPTY(&keyval->table[i])) {
- elt = LIST_FIRST(&keyval->table[i]);
- LIST_REMOVE(elt, next);
- LIST_INSERT_HEAD(&new_table[elt->hash & (new_size - 1)],
- elt, next);
+ ref = LIST_FIRST(&keyval->table[i]);
+ LIST_REMOVE(ref, next);
+ LIST_INSERT_HEAD(
+ &new_table[ref->elt->hash & (new_size - 1)],
+ ref, next);
}
}
return 0;
}
-int ec_keyval_set(struct ec_keyval *keyval, const char *key, void *val,
- ec_keyval_elt_free_t free_cb)
+static int
+__ec_keyval_set(struct ec_keyval *keyval, struct ec_keyval_elt_ref *ref)
{
- struct ec_keyval_elt *elt;
- uint32_t h, mask;
size_t new_size;
+ uint32_t mask;
int ret;
- if (keyval == NULL || key == NULL) {
- errno = EINVAL;
- return -1;
- }
-
- elt = ec_keyval_lookup(keyval, key);
- if (elt != NULL) {
- if (elt->free != NULL)
- elt->free(elt->val);
- elt->val = val;
- elt->free = free_cb;
- return 0;
- }
+ /* remove previous entry if any */
+ ec_keyval_del(keyval, ref->elt->key);
if (keyval->len >= keyval->table_size) {
if (keyval->table_size != 0)
new_size = 1 << FACTOR;
ret = ec_keyval_table_resize(keyval, new_size);
if (ret < 0)
- goto fail;
+ return ret;
}
+ mask = keyval->table_size - 1;
+ LIST_INSERT_HEAD(&keyval->table[ref->elt->hash & mask], ref, next);
+ keyval->len++;
+
+ return 0;
+}
+
+int ec_keyval_set(struct ec_keyval *keyval, const char *key, void *val,
+ ec_keyval_elt_free_t free_cb)
+{
+ struct ec_keyval_elt *elt = NULL;
+ struct ec_keyval_elt_ref *ref = NULL;
+ uint32_t h;
+
+ if (keyval == NULL || key == NULL) {
+ errno = EINVAL;
+ return -1;
+ }
+
+ ref = ec_calloc(1, sizeof(*ref));
+ if (ref == NULL)
+ goto fail;
+
elt = ec_calloc(1, sizeof(*elt));
if (elt == NULL)
goto fail;
+
+ ref->elt = elt;
+ elt->refcount = 1;
+ elt->val = val;
+ val = NULL;
+ elt->free = free_cb;
elt->key = ec_strdup(key);
if (elt->key == NULL)
goto fail;
- elt->val = val;
- elt->free = free_cb;
h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
elt->hash = h;
- mask = keyval->table_size - 1;
- LIST_INSERT_HEAD(&keyval->table[h & mask], elt, next);
- keyval->len++;
+ if (__ec_keyval_set(keyval, ref) < 0)
+ goto fail;
return 0;
fail:
- if (free_cb != NULL)
+ if (free_cb != NULL && val != NULL)
free_cb(val);
- if (elt != NULL) {
- ec_free(elt->key);
- ec_free(elt);
- }
-
- return ret;
+ ec_keyval_elt_ref_free(ref);
+ return -1;
}
void ec_keyval_free(struct ec_keyval *keyval)
{
- struct ec_keyval_elt *elt;
+ struct ec_keyval_elt_ref *ref;
size_t i;
if (keyval == NULL)
for (i = 0; i < keyval->table_size; i++) {
while (!LIST_EMPTY(&keyval->table[i])) {
- elt = LIST_FIRST(&keyval->table[i]);
- LIST_REMOVE(elt, next);
- ec_keyval_elt_free(elt);
+ ref = LIST_FIRST(&keyval->table[i]);
+ LIST_REMOVE(ref, next);
+ ec_keyval_elt_ref_free(ref);
}
}
ec_free(keyval->table);
return keyval->len;
}
-void ec_keyval_dump(FILE *out, const struct ec_keyval *keyval)
+void
+ec_keyval_iter_free(struct ec_keyval_iter *iter)
{
- struct ec_keyval_elt *elt;
+ ec_free(iter);
+}
+
+struct ec_keyval_iter *
+ec_keyval_iter(const struct ec_keyval *keyval)
+{
+ struct ec_keyval_iter *iter = NULL;
+
+ iter = ec_calloc(1, sizeof(*iter));
+ if (iter == NULL)
+ return NULL;
+
+ iter->keyval = keyval;
+ iter->cur_idx = 0;
+ iter->cur_ref = NULL;
+
+ ec_keyval_iter_next(iter);
+
+ return iter;
+}
+
+void
+ec_keyval_iter_next(struct ec_keyval_iter *iter)
+{
+ const struct ec_keyval_elt_ref *ref;
size_t i;
+ i = iter->cur_idx;
+ if (i == iter->keyval->table_size)
+ return; /* no more element */
+
+ if (iter->cur_ref != NULL) {
+ ref = LIST_NEXT(iter->cur_ref, next);
+ if (ref != NULL) {
+ iter->cur_ref = ref;
+ return;
+ }
+ i++;
+ }
+
+ for (; i < iter->keyval->table_size; i++) {
+ LIST_FOREACH(ref, &iter->keyval->table[i], next) {
+ iter->cur_idx = i;
+ iter->cur_ref = LIST_FIRST(&iter->keyval->table[i]);
+ return;
+ }
+ }
+
+ iter->cur_idx = iter->keyval->table_size;
+ iter->cur_ref = NULL;
+}
+
+bool
+ec_keyval_iter_valid(const struct ec_keyval_iter *iter)
+{
+ if (iter == NULL || iter->cur_ref == NULL)
+ return false;
+
+ return true;
+}
+
+const char *
+ec_keyval_iter_get_key(const struct ec_keyval_iter *iter)
+{
+ if (iter == NULL || iter->cur_ref == NULL)
+ return NULL;
+
+ return iter->cur_ref->elt->key;
+}
+
+void *
+ec_keyval_iter_get_val(const struct ec_keyval_iter *iter)
+{
+ if (iter == NULL || iter->cur_ref == NULL)
+ return NULL;
+
+ return iter->cur_ref->elt->val;
+}
+
+void ec_keyval_dump(FILE *out, const struct ec_keyval *keyval)
+{
+ struct ec_keyval_iter *iter;
+
if (keyval == NULL) {
fprintf(out, "empty keyval\n");
return;
}
fprintf(out, "keyval:\n");
+ for (iter = ec_keyval_iter(keyval);
+ ec_keyval_iter_valid(iter);
+ ec_keyval_iter_next(iter)) {
+ fprintf(out, " %s: %p\n",
+ ec_keyval_iter_get_key(iter),
+ ec_keyval_iter_get_val(iter));
+ }
+ ec_keyval_iter_free(iter);
+}
+
+struct ec_keyval *ec_keyval_dup(const struct ec_keyval *keyval)
+{
+ struct ec_keyval *dup = NULL;
+ struct ec_keyval_elt_ref *ref, *dup_ref = NULL;
+ size_t i;
+
+ dup = ec_keyval();
+ if (dup == NULL)
+ return NULL;
+
for (i = 0; i < keyval->table_size; i++) {
- LIST_FOREACH(elt, &keyval->table[i], next) {
- fprintf(out, " %s: %p\n",
- elt->key, elt->val);
+ LIST_FOREACH(ref, &keyval->table[i], next) {
+ dup_ref = ec_calloc(1, sizeof(*ref));
+ if (dup_ref == NULL)
+ goto fail;
+ dup_ref->elt = ref->elt;
+ ref->elt->refcount++;
+
+ if (__ec_keyval_set(dup, dup_ref) < 0)
+ goto fail;
}
}
+
+ return dup;
+
+fail:
+ ec_keyval_elt_ref_free(dup_ref);
+ ec_keyval_free(dup);
+ return NULL;
}
static int ec_keyval_init_func(void)
int fd;
ssize_t ret;
+ return 0;//XXX for test reproduceability
+
fd = open("/dev/urandom", 0);
if (fd == -1) {
fprintf(stderr, "failed to open /dev/urandom\n");
/* LCOV_EXCL_START */
static int ec_keyval_testcase(void)
{
- struct ec_keyval *keyval;
+ struct ec_keyval *keyval, *dup;
+ struct ec_keyval_iter *iter;
char *val;
- size_t i;
- int ret;
+ size_t i, count;
+ int ret, testres = 0;
+ FILE *f = NULL;
+ char *buf = NULL;
+ size_t buflen = 0;
keyval = ec_keyval();
if (keyval == NULL) {
return -1;
}
- EC_TEST_ASSERT(ec_keyval_len(keyval) == 0);
+ count = 0;
+ for (iter = ec_keyval_iter(keyval);
+ ec_keyval_iter_valid(iter);
+ ec_keyval_iter_next(iter)) {
+ count++;
+ }
+ ec_keyval_iter_free(iter);
+ testres |= EC_TEST_CHECK(count == 0, "invalid count in iterator");
+
+ testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 0, "bad keyval len");
ret = ec_keyval_set(keyval, "key1", "val1", NULL);
- EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
+ testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
ret = ec_keyval_set(keyval, "key2", ec_strdup("val2"), ec_free_func);
- EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
- EC_TEST_ASSERT(ec_keyval_len(keyval) == 2);
+ testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
+ testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2, "bad keyval len");
val = ec_keyval_get(keyval, "key1");
- EC_TEST_ASSERT(val != NULL && !strcmp(val, "val1"));
+ testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val1"),
+ "invalid keyval value");
val = ec_keyval_get(keyval, "key2");
- EC_TEST_ASSERT(val != NULL && !strcmp(val, "val2"));
+ testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val2"),
+ "invalid keyval value");
val = ec_keyval_get(keyval, "key3");
- EC_TEST_ASSERT(val == NULL);
+ testres |= EC_TEST_CHECK(val == NULL, "key3 should be NULL");
ret = ec_keyval_set(keyval, "key1", "another_val1", NULL);
- EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
+ testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
ret = ec_keyval_set(keyval, "key2", ec_strdup("another_val2"),
ec_free_func);
- EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
- EC_TEST_ASSERT(ec_keyval_len(keyval) == 2);
+ testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
+ testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2,
+ "bad keyval len");
val = ec_keyval_get(keyval, "key1");
- EC_TEST_ASSERT(val != NULL && !strcmp(val, "another_val1"));
+ testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val1"),
+ "invalid keyval value");
val = ec_keyval_get(keyval, "key2");
- EC_TEST_ASSERT(val != NULL && !strcmp(val, "another_val2"));
- EC_TEST_ASSERT(ec_keyval_has_key(keyval, "key1"));
+ testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val2"),
+ "invalid keyval value");
+ testres |= EC_TEST_CHECK(ec_keyval_has_key(keyval, "key1"),
+ "key1 should be in keyval");
- ret = ec_keyval_del(keyval, "key1");
- EC_TEST_ASSERT_STR(ret == 0, "cannot del key");
- EC_TEST_ASSERT(ec_keyval_len(keyval) == 1);
+ f = open_memstream(&buf, &buflen);
+ if (f == NULL)
+ goto fail;
+ ec_keyval_dump(f, NULL);
+ fclose(f);
+ f = NULL;
+ free(buf);
+ buf = NULL;
+
+ f = open_memstream(&buf, &buflen);
+ if (f == NULL)
+ goto fail;
+ ec_keyval_dump(f, keyval);
+ fclose(f);
+ f = NULL;
+ free(buf);
+ buf = NULL;
- ec_keyval_dump(stdout, NULL);
- ec_keyval_dump(stdout, keyval);
+ ret = ec_keyval_del(keyval, "key1");
+ testres |= EC_TEST_CHECK(ret == 0, "cannot del key1");
+ testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 1,
+ "invalid keyval len");
+ ret = ec_keyval_del(keyval, "key2");
+ testres |= EC_TEST_CHECK(ret == 0, "cannot del key2");
+ testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 0,
+ "invalid keyval len");
for (i = 0; i < 100; i++) {
- char buf[8];
- snprintf(buf, sizeof(buf), "k%zd", i);
- ret = ec_keyval_set(keyval, buf, "val", NULL);
- EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
+ char key[8];
+ snprintf(key, sizeof(key), "k%zd", i);
+ ret = ec_keyval_set(keyval, key, "val", NULL);
+ testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
+ }
+ dup = ec_keyval_dup(keyval);
+ testres |= EC_TEST_CHECK(dup != NULL, "cannot duplicate keyval");
+ if (dup != NULL) {
+ for (i = 0; i < 100; i++) {
+ char key[8];
+ snprintf(key, sizeof(key), "k%zd", i);
+ val = ec_keyval_get(dup, key);
+ testres |= EC_TEST_CHECK(
+ val != NULL && !strcmp(val, "val"),
+ "invalid keyval value");
+ }
+ ec_keyval_free(dup);
+ dup = NULL;
+ }
+
+ count = 0;
+ for (iter = ec_keyval_iter(keyval);
+ ec_keyval_iter_valid(iter);
+ ec_keyval_iter_next(iter)) {
+ count++;
}
+ ec_keyval_iter_free(iter);
+ testres |= EC_TEST_CHECK(count == 100, "invalid count in iterator");
/* einval */
ret = ec_keyval_set(keyval, NULL, "val1", NULL);
- EC_TEST_ASSERT(ret == -1);
+ testres |= EC_TEST_CHECK(ret == -1, "should not be able to set key");
val = ec_keyval_get(keyval, NULL);
- EC_TEST_ASSERT(val == NULL);
+ testres |= EC_TEST_CHECK(val == NULL, "get(NULL) should no success");
ec_keyval_free(keyval);
+ return testres;
- return 0;
+fail:
+ ec_keyval_free(keyval);
+ if (f)
+ fclose(f);
+ free(buf);
+ return -1;
}
/* LCOV_EXCL_STOP */
git.droids-corp.org / protos / libecoli.git / blobdiff