From eab37de05c8760ca59ea4fbac20ecb4b7453fdc0 Mon Sep 17 00:00:00 2001
From: Olivier Matz <zer0@droids-corp.org>
Date: Thu, 21 Mar 2019 20:10:20 +0100
Subject: [PATCH] rework keyval
---
include/ecoli_keyval.h | 37 +++------
src/ecoli_config.c | 32 +++-----
src/ecoli_keyval.c | 166 ++++++++++++++---------------------------
3 files changed, 79 insertions(+), 156 deletions(-)
diff --git a/include/ecoli_keyval.h b/include/ecoli_keyval.h
index a3e9400..38b0d40 100644
--- a/include/ecoli_keyval.h
+++ b/include/ecoli_keyval.h
@@ -18,7 +18,7 @@
typedef void (*ec_keyval_elt_free_t)(void *);
struct ec_keyval;
-struct ec_keyval_iter;
+struct ec_keyval_elt_ref;
/**
* Create a hash table.
@@ -133,20 +133,19 @@ void ec_keyval_dump(FILE *out, const struct ec_keyval *keyval);
*
* // dump elements
* for (iter = ec_keyval_iter(keyval);
- * ec_keyval_iter_valid(iter);
- * ec_keyval_iter_next(iter)) {
+ * iter != NULL;
+ * iter = ec_keyval_iter_next(iter)) {
* printf(" %s: %p\n",
* ec_keyval_iter_get_key(iter),
* ec_keyval_iter_get_val(iter));
* }
- * ec_keyval_iter_free(iter);
*
* @param keyval
* The hash table.
* @return
- * An iterator, or NULL on error (errno is set).
+ * An iterator element, or NULL if the dict is empty.
*/
-struct ec_keyval_iter *
+struct ec_keyval_elt_ref *
ec_keyval_iter(const struct ec_keyval *keyval);
/**
@@ -154,27 +153,11 @@ ec_keyval_iter(const struct ec_keyval *keyval);
*
* @param iter
* The hash table iterator.
- */
-void ec_keyval_iter_next(struct ec_keyval_iter *iter);
-
-/**
- * Free the iterator.
- *
- * @param iter
- * The hash table iterator.
- */
-void ec_keyval_iter_free(struct ec_keyval_iter *iter);
-
-/**
- * Check if the iterator points to a valid element.
- *
- * @param iter
- * The hash table iterator.
* @return
- * true if the element is valid, else false.
+ * An iterator element, or NULL there is no more element.
*/
-bool
-ec_keyval_iter_valid(const struct ec_keyval_iter *iter);
+struct ec_keyval_elt_ref *
+ec_keyval_iter_next(struct ec_keyval_elt_ref *iter);
/**
* Get the key of the current element.
@@ -186,7 +169,7 @@ ec_keyval_iter_valid(const struct ec_keyval_iter *iter);
* invalid element.
*/
const char *
-ec_keyval_iter_get_key(const struct ec_keyval_iter *iter);
+ec_keyval_iter_get_key(const struct ec_keyval_elt_ref *iter);
/**
* Get the value of the current element.
@@ -198,7 +181,7 @@ ec_keyval_iter_get_key(const struct ec_keyval_iter *iter);
* invalid element.
*/
void *
-ec_keyval_iter_get_val(const struct ec_keyval_iter *iter);
+ec_keyval_iter_get_val(const struct ec_keyval_elt_ref *iter);
#endif
diff --git a/src/ecoli_config.c b/src/ecoli_config.c
index 66d9232..3a98843 100644
--- a/src/ecoli_config.c
+++ b/src/ecoli_config.c
@@ -461,15 +461,15 @@ ec_config_dict_cmp(const struct ec_keyval *d1,
const struct ec_keyval *d2)
{
const struct ec_config *v1, *v2;
- struct ec_keyval_iter *iter = NULL;
+ struct ec_keyval_elt_ref *iter = NULL;
const char *key;
if (ec_keyval_len(d1) != ec_keyval_len(d2))
return -1;
for (iter = ec_keyval_iter(d1);
- ec_keyval_iter_valid(iter);
- ec_keyval_iter_next(iter)) {
+ iter != NULL;
+ iter = ec_keyval_iter_next(iter)) {
key = ec_keyval_iter_get_key(iter);
v1 = ec_keyval_iter_get_val(iter);
v2 = ec_keyval_get(d2, key);
@@ -478,11 +478,9 @@ ec_config_dict_cmp(const struct ec_keyval *d1,
goto fail;
}
- ec_keyval_iter_free(iter);
return 0;
fail:
- ec_keyval_iter_free(iter);
return -1;
}
@@ -556,13 +554,13 @@ ec_config_dict_validate(const struct ec_keyval *dict,
const struct ec_config_schema *schema)
{
const struct ec_config *value;
- struct ec_keyval_iter *iter = NULL;
+ struct ec_keyval_elt_ref *iter = NULL;
const struct ec_config_schema *sch;
const char *key;
for (iter = ec_keyval_iter(dict);
- ec_keyval_iter_valid(iter);
- ec_keyval_iter_next(iter)) {
+ iter != NULL;
+ iter = ec_keyval_iter_next(iter)) {
key = ec_keyval_iter_get_key(iter);
value = ec_keyval_iter_get_val(iter);
@@ -582,11 +580,9 @@ ec_config_dict_validate(const struct ec_keyval *dict,
}
}
- ec_keyval_iter_free(iter);
return 0;
fail:
- ec_keyval_iter_free(iter);
return -1;
}
@@ -738,7 +734,7 @@ static struct ec_config *
ec_config_dict_dup(const struct ec_keyval *dict)
{
struct ec_config *dup = NULL, *value;
- struct ec_keyval_iter *iter = NULL;
+ struct ec_keyval_elt_ref *iter = NULL;
const char *key;
dup = ec_config_dict();
@@ -746,8 +742,8 @@ ec_config_dict_dup(const struct ec_keyval *dict)
goto fail;
for (iter = ec_keyval_iter(dict);
- ec_keyval_iter_valid(iter);
- ec_keyval_iter_next(iter)) {
+ iter != NULL;
+ iter = ec_keyval_iter_next(iter)) {
key = ec_keyval_iter_get_key(iter);
value = ec_config_dup(ec_keyval_iter_get_val(iter));
if (value == NULL)
@@ -755,13 +751,11 @@ ec_config_dict_dup(const struct ec_keyval *dict)
if (ec_config_dict_set(dup, key, value) < 0)
goto fail;
}
- ec_keyval_iter_free(iter);
return dup;
fail:
ec_config_free(dup);
- ec_keyval_iter_free(iter);
return NULL;
}
@@ -820,7 +814,7 @@ ec_config_dict_dump(FILE *out, const char *key, const struct ec_keyval *dict,
size_t indent)
{
const struct ec_config *value;
- struct ec_keyval_iter *iter;
+ struct ec_keyval_elt_ref *iter;
const char *k;
fprintf(out, "%*s" "%s%s%stype=dict\n", (int)indent * 4, "",
@@ -829,18 +823,16 @@ ec_config_dict_dump(FILE *out, const char *key, const struct ec_keyval *dict,
key ? " ": "");
for (iter = ec_keyval_iter(dict);
- ec_keyval_iter_valid(iter);
- ec_keyval_iter_next(iter)) {
+ iter != NULL;
+ iter = ec_keyval_iter_next(iter)) {
k = ec_keyval_iter_get_key(iter);
value = ec_keyval_iter_get_val(iter);
if (__ec_config_dump(out, k, value, indent + 1) < 0)
goto fail;
}
- ec_keyval_iter_free(iter);
return 0;
fail:
- ec_keyval_iter_free(iter);
return -1;
}
diff --git a/src/ecoli_keyval.c b/src/ecoli_keyval.c
index 12fe66b..a99aaf0 100644
--- a/src/ecoli_keyval.c
+++ b/src/ecoli_keyval.c
@@ -34,24 +34,20 @@ struct ec_keyval_elt {
};
struct ec_keyval_elt_ref {
- LIST_ENTRY(ec_keyval_elt_ref) next;
+ TAILQ_ENTRY(ec_keyval_elt_ref) next;
+ TAILQ_ENTRY(ec_keyval_elt_ref) hnext;
struct ec_keyval_elt *elt;
};
-LIST_HEAD(ec_keyval_elt_ref_list, ec_keyval_elt_ref);
+TAILQ_HEAD(ec_keyval_elt_ref_list, ec_keyval_elt_ref);
struct ec_keyval {
size_t len;
size_t table_size;
+ struct ec_keyval_elt_ref_list list;
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)
{
struct ec_keyval *keyval;
@@ -59,6 +55,7 @@ struct ec_keyval *ec_keyval(void)
keyval = ec_calloc(1, sizeof(*keyval));
if (keyval == NULL)
return NULL;
+ TAILQ_INIT(&keyval->list);
return keyval;
}
@@ -79,7 +76,7 @@ ec_keyval_lookup(const struct ec_keyval *keyval, const char *key)
}
h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
- LIST_FOREACH(ref, &keyval->table[h & mask], next) {
+ TAILQ_FOREACH(ref, &keyval->table[h & mask], hnext) {
if (strcmp(ref->elt->key, key) == 0)
return ref;
}
@@ -124,6 +121,7 @@ void *ec_keyval_get(const struct ec_keyval *keyval, const char *key)
int ec_keyval_del(struct ec_keyval *keyval, const char *key)
{
struct ec_keyval_elt_ref *ref;
+ size_t idx;
ref = ec_keyval_lookup(keyval, key);
if (ref == NULL)
@@ -131,7 +129,9 @@ int ec_keyval_del(struct ec_keyval *keyval, const char *key)
/* we could resize table here */
- LIST_REMOVE(ref, next);
+ TAILQ_REMOVE(&keyval->list, ref, next);
+ idx = ref->elt->hash & (keyval->table_size - 1);
+ TAILQ_REMOVE(&keyval->table[idx], ref, hnext);
ec_keyval_elt_ref_free(ref);
keyval->len--;
@@ -152,15 +152,14 @@ static int ec_keyval_table_resize(struct ec_keyval *keyval, size_t new_size)
new_table = ec_calloc(new_size, sizeof(*keyval->table));
if (new_table == NULL)
return -1;
-
- for (i = 0; i < keyval->table_size; i++) {
- while (!LIST_EMPTY(&keyval->table[i])) {
- ref = LIST_FIRST(&keyval->table[i]);
- LIST_REMOVE(ref, next);
- LIST_INSERT_HEAD(
- &new_table[ref->elt->hash & (new_size - 1)],
- ref, next);
- }
+ for (i = 0; i < new_size; i++)
+ TAILQ_INIT(&new_table[i]);
+
+ TAILQ_FOREACH(ref, &keyval->list, next) {
+ i = ref->elt->hash & (keyval->table_size - 1);
+ TAILQ_REMOVE(&keyval->table[i], ref, hnext);
+ i = ref->elt->hash & (new_size - 1);
+ TAILQ_INSERT_TAIL(&new_table[i], ref, hnext);
}
ec_free(keyval->table);
@@ -191,7 +190,8 @@ __ec_keyval_set(struct ec_keyval *keyval, struct ec_keyval_elt_ref *ref)
}
mask = keyval->table_size - 1;
- LIST_INSERT_HEAD(&keyval->table[ref->elt->hash & mask], ref, next);
+ TAILQ_INSERT_TAIL(&keyval->table[ref->elt->hash & mask], ref, hnext);
+ TAILQ_INSERT_TAIL(&keyval->list, ref, next);
keyval->len++;
return 0;
@@ -243,17 +243,17 @@ fail:
void ec_keyval_free(struct ec_keyval *keyval)
{
struct ec_keyval_elt_ref *ref;
- size_t i;
+ size_t idx;
if (keyval == NULL)
return;
- for (i = 0; i < keyval->table_size; i++) {
- while (!LIST_EMPTY(&keyval->table[i])) {
- ref = LIST_FIRST(&keyval->table[i]);
- LIST_REMOVE(ref, next);
- ec_keyval_elt_ref_free(ref);
- }
+ while (!TAILQ_EMPTY(&keyval->list)) {
+ ref = TAILQ_FIRST(&keyval->list);
+ TAILQ_REMOVE(&keyval->list, ref, next);
+ idx = ref->elt->hash & (keyval->table_size - 1);
+ TAILQ_REMOVE(&keyval->table[idx], ref, hnext);
+ ec_keyval_elt_ref_free(ref);
}
ec_free(keyval->table);
ec_free(keyval);
@@ -264,91 +264,45 @@ size_t ec_keyval_len(const struct ec_keyval *keyval)
return keyval->len;
}
-void
-ec_keyval_iter_free(struct ec_keyval_iter *iter)
-{
- ec_free(iter);
-}
-
-struct ec_keyval_iter *
+struct ec_keyval_elt_ref *
ec_keyval_iter(const struct ec_keyval *keyval)
{
- struct ec_keyval_iter *iter = NULL;
-
- iter = ec_calloc(1, sizeof(*iter));
- if (iter == NULL)
+ if (keyval == 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;
+ return TAILQ_FIRST(&keyval->list);
}
-bool
-ec_keyval_iter_valid(const struct ec_keyval_iter *iter)
+struct ec_keyval_elt_ref *
+ec_keyval_iter_next(struct ec_keyval_elt_ref *iter)
{
- if (iter == NULL || iter->cur_ref == NULL)
- return false;
+ if (iter == NULL)
+ return NULL;
- return true;
+ return TAILQ_NEXT(iter, next);
}
const char *
-ec_keyval_iter_get_key(const struct ec_keyval_iter *iter)
+ec_keyval_iter_get_key(const struct ec_keyval_elt_ref *iter)
{
- if (iter == NULL || iter->cur_ref == NULL)
+ if (iter == NULL)
return NULL;
- return iter->cur_ref->elt->key;
+ return iter->elt->key;
}
void *
-ec_keyval_iter_get_val(const struct ec_keyval_iter *iter)
+ec_keyval_iter_get_val(const struct ec_keyval_elt_ref *iter)
{
- if (iter == NULL || iter->cur_ref == NULL)
+ if (iter == NULL)
return NULL;
- return iter->cur_ref->elt->val;
+ return iter->elt->val;
}
void ec_keyval_dump(FILE *out, const struct ec_keyval *keyval)
{
- struct ec_keyval_iter *iter;
+ struct ec_keyval_elt_ref *iter;
if (keyval == NULL) {
fprintf(out, "empty keyval\n");
@@ -357,36 +311,32 @@ void ec_keyval_dump(FILE *out, const struct ec_keyval *keyval)
fprintf(out, "keyval:\n");
for (iter = ec_keyval_iter(keyval);
- ec_keyval_iter_valid(iter);
- ec_keyval_iter_next(iter)) {
+ iter != NULL;
+ 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(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++;
+ TAILQ_FOREACH(ref, &keyval->list, 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;
- }
+ if (__ec_keyval_set(dup, dup_ref) < 0)
+ goto fail;
}
return dup;
@@ -429,7 +379,7 @@ EC_INIT_REGISTER(ec_keyval_init);
static int ec_keyval_testcase(void)
{
struct ec_keyval *keyval, *dup;
- struct ec_keyval_iter *iter;
+ struct ec_keyval_elt_ref *iter;
char *val;
size_t i, count;
int ret, testres = 0;
@@ -445,11 +395,10 @@ static int ec_keyval_testcase(void)
count = 0;
for (iter = ec_keyval_iter(keyval);
- ec_keyval_iter_valid(iter);
- ec_keyval_iter_next(iter)) {
+ iter != NULL;
+ 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");
@@ -535,11 +484,10 @@ static int ec_keyval_testcase(void)
count = 0;
for (iter = ec_keyval_iter(keyval);
- ec_keyval_iter_valid(iter);
- ec_keyval_iter_next(iter)) {
+ iter != NULL;
+ iter = ec_keyval_iter_next(iter)) {
count++;
}
- ec_keyval_iter_free(iter);
testres |= EC_TEST_CHECK(count == 100, "invalid count in iterator");
/* einval */
--
2.39.5