From eab37de05c8760ca59ea4fbac20ecb4b7453fdc0 Mon Sep 17 00:00:00 2001 From: Olivier Matz 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.20.1