From bfa98f93802bff755a024ee478b85756264f591b Mon Sep 17 00:00:00 2001 From: Olivier Matz Date: Thu, 21 Mar 2019 22:18:12 +0100 Subject: [PATCH] factorize dict and htable --- examples/parse-yaml/meson.build | 2 - examples/readline/meson.build | 2 - include/ecoli_dict.h | 1 - include/ecoli_htable.h | 15 +- meson.build | 3 + src/ecoli_dict.c | 298 +++----------------------------- src/ecoli_htable.c | 36 ++-- src/ecoli_htable_private.h | 34 ++++ src/meson.build | 4 +- test/meson.build | 2 - 10 files changed, 87 insertions(+), 310 deletions(-) create mode 100644 src/ecoli_htable_private.h diff --git a/examples/parse-yaml/meson.build b/examples/parse-yaml/meson.build index d6605c9..519e944 100644 --- a/examples/parse-yaml/meson.build +++ b/examples/parse-yaml/meson.build @@ -1,8 +1,6 @@ # SPDX-License-Identifier: BSD-3-Clause # Copyright 2018, Olivier MATZ -inc = include_directories('../../include') - parse_yaml_sources = [ 'parse-yaml.c', ] diff --git a/examples/readline/meson.build b/examples/readline/meson.build index 513c85c..b20ec24 100644 --- a/examples/readline/meson.build +++ b/examples/readline/meson.build @@ -1,8 +1,6 @@ # SPDX-License-Identifier: BSD-3-Clause # Copyright 2018, Olivier MATZ -inc = include_directories('../../include') - readline_sources = [ 'main.c', ] diff --git a/include/ecoli_dict.h b/include/ecoli_dict.h index 5519c4c..e442466 100644 --- a/include/ecoli_dict.h +++ b/include/ecoli_dict.h @@ -183,5 +183,4 @@ ec_dict_iter_get_key(const struct ec_dict_elt_ref *iter); void * ec_dict_iter_get_val(const struct ec_dict_elt_ref *iter); - #endif diff --git a/include/ecoli_htable.h b/include/ecoli_htable.h index 6729d91..0bed676 100644 --- a/include/ecoli_htable.h +++ b/include/ecoli_htable.h @@ -178,9 +178,21 @@ ec_htable_iter_next(struct ec_htable_elt_ref *iter); * The current element key, or NULL if the iterator points to an * invalid element. */ -const char * +const void * ec_htable_iter_get_key(const struct ec_htable_elt_ref *iter); +/** + * Get the key length of the current element. + * + * @param iter + * The hash table iterator. + * @return + * The current element key length, or 0 if the iterator points to an + * invalid element. + */ +size_t +ec_htable_iter_get_key_len(const struct ec_htable_elt_ref *iter); + /** * Get the value of the current element. * @@ -193,5 +205,4 @@ ec_htable_iter_get_key(const struct ec_htable_elt_ref *iter); void * ec_htable_iter_get_val(const struct ec_htable_elt_ref *iter); - #endif diff --git a/meson.build b/meson.build index 75b1ee0..0e7ebb0 100644 --- a/meson.build +++ b/meson.build @@ -13,6 +13,9 @@ yaml_dep = dependency('yaml-0.1', method: 'pkg-config') # XXX if debug add_global_arguments('-Werror', language : 'c') +inc = include_directories('include') +priv_inc = include_directories('src') + subdir('src') subdir('test') subdir('examples') diff --git a/src/ecoli_dict.c b/src/ecoli_dict.c index 09d7dda..98dc5d1 100644 --- a/src/ecoli_dict.c +++ b/src/ecoli_dict.c @@ -16,288 +16,91 @@ #include #include #include -#include +#include #include -#define FACTOR 3 - EC_LOG_TYPE_REGISTER(dict); -static uint32_t ec_dict_seed; +static size_t +_strlen(const char *s) +{ + if (s == NULL) + return 0; + return strlen(s); +} struct ec_dict_elt { - char *key; - void *val; - uint32_t hash; - ec_dict_elt_free_t free; - unsigned int refcount; + struct ec_htable_elt htable; }; struct ec_dict_elt_ref { - TAILQ_ENTRY(ec_dict_elt_ref) next; - TAILQ_ENTRY(ec_dict_elt_ref) hnext; - struct ec_dict_elt *elt; + struct ec_htable_elt_ref htable; }; -TAILQ_HEAD(ec_dict_elt_ref_list, ec_dict_elt_ref); - struct ec_dict { - size_t len; - size_t table_size; - struct ec_dict_elt_ref_list list; - struct ec_dict_elt_ref_list *table; + struct ec_htable htable; }; struct ec_dict *ec_dict(void) { - struct ec_dict *dict; - - dict = ec_calloc(1, sizeof(*dict)); - if (dict == NULL) - return NULL; - TAILQ_INIT(&dict->list); - - return dict; -} - -static struct ec_dict_elt_ref * -ec_dict_lookup(const struct ec_dict *dict, const char *key) -{ - struct ec_dict_elt_ref *ref; - uint32_t h, mask = dict->table_size - 1; - - if (dict == NULL || key == NULL) { - errno = EINVAL; - return NULL; - } - if (dict->table_size == 0) { - errno = ENOENT; - return NULL; - } - - h = ec_murmurhash3(key, strlen(key), ec_dict_seed); - TAILQ_FOREACH(ref, &dict->table[h & mask], hnext) { - if (strcmp(ref->elt->key, key) == 0) - return ref; - } - - errno = ENOENT; - return NULL; -} - -static void ec_dict_elt_ref_free(struct ec_dict_elt_ref *ref) -{ - struct ec_dict_elt *elt; - - if (ref == NULL) - return; - - 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); + return (struct ec_dict *)ec_htable(); } bool ec_dict_has_key(const struct ec_dict *dict, const char *key) { - return !!ec_dict_lookup(dict, key); + return ec_htable_has_key( + &dict->htable, key, _strlen(key) + 1); } void *ec_dict_get(const struct ec_dict *dict, const char *key) { - struct ec_dict_elt_ref *ref; - - ref = ec_dict_lookup(dict, key); - if (ref == NULL) - return NULL; - - return ref->elt->val; + return ec_htable_get(&dict->htable, key, _strlen(key) + 1); } int ec_dict_del(struct ec_dict *dict, const char *key) { - struct ec_dict_elt_ref *ref; - size_t idx; - - ref = ec_dict_lookup(dict, key); - if (ref == NULL) - return -1; - - /* we could resize table here */ - - TAILQ_REMOVE(&dict->list, ref, next); - idx = ref->elt->hash & (dict->table_size - 1); - TAILQ_REMOVE(&dict->table[idx], ref, hnext); - ec_dict_elt_ref_free(ref); - dict->len--; - - return 0; -} - -static int ec_dict_table_resize(struct ec_dict *dict, size_t new_size) -{ - struct ec_dict_elt_ref_list *new_table; - struct ec_dict_elt_ref *ref; - size_t i; - - if (new_size == 0 || (new_size & (new_size - 1))) { - errno = EINVAL; - return -1; - } - - new_table = ec_calloc(new_size, sizeof(*dict->table)); - if (new_table == NULL) - return -1; - for (i = 0; i < new_size; i++) - TAILQ_INIT(&new_table[i]); - - TAILQ_FOREACH(ref, &dict->list, next) { - i = ref->elt->hash & (dict->table_size - 1); - TAILQ_REMOVE(&dict->table[i], ref, hnext); - i = ref->elt->hash & (new_size - 1); - TAILQ_INSERT_TAIL(&new_table[i], ref, hnext); - } - - ec_free(dict->table); - dict->table = new_table; - dict->table_size = new_size; - - return 0; -} - -static int -__ec_dict_set(struct ec_dict *dict, struct ec_dict_elt_ref *ref) -{ - size_t new_size; - uint32_t mask; - int ret; - - /* remove previous entry if any */ - ec_dict_del(dict, ref->elt->key); - - if (dict->len >= dict->table_size) { - if (dict->table_size != 0) - new_size = dict->table_size << FACTOR; - else - new_size = 1 << FACTOR; - ret = ec_dict_table_resize(dict, new_size); - if (ret < 0) - return ret; - } - - mask = dict->table_size - 1; - TAILQ_INSERT_TAIL(&dict->table[ref->elt->hash & mask], ref, hnext); - TAILQ_INSERT_TAIL(&dict->list, ref, next); - dict->len++; - - return 0; + return ec_htable_del(&dict->htable, key, _strlen(key) + 1); } int ec_dict_set(struct ec_dict *dict, const char *key, void *val, ec_dict_elt_free_t free_cb) { - struct ec_dict_elt *elt = NULL; - struct ec_dict_elt_ref *ref = NULL; - uint32_t h; - - if (dict == 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; - h = ec_murmurhash3(key, strlen(key), ec_dict_seed); - elt->hash = h; - - if (__ec_dict_set(dict, ref) < 0) - goto fail; - - return 0; - -fail: - if (free_cb != NULL && val != NULL) - free_cb(val); - ec_dict_elt_ref_free(ref); - return -1; + return ec_htable_set(&dict->htable, key, _strlen(key) + 1, + val, free_cb); } void ec_dict_free(struct ec_dict *dict) { - struct ec_dict_elt_ref *ref; - size_t idx; - - if (dict == NULL) - return; - - while (!TAILQ_EMPTY(&dict->list)) { - ref = TAILQ_FIRST(&dict->list); - TAILQ_REMOVE(&dict->list, ref, next); - idx = ref->elt->hash & (dict->table_size - 1); - TAILQ_REMOVE(&dict->table[idx], ref, hnext); - ec_dict_elt_ref_free(ref); - } - ec_free(dict->table); - ec_free(dict); + ec_htable_free(&dict->htable); } size_t ec_dict_len(const struct ec_dict *dict) { - return dict->len; + return ec_htable_len(&dict->htable); } struct ec_dict_elt_ref * ec_dict_iter(const struct ec_dict *dict) { - if (dict == NULL) - return NULL; - - return TAILQ_FIRST(&dict->list); + return (struct ec_dict_elt_ref *)ec_htable_iter(&dict->htable); } struct ec_dict_elt_ref * ec_dict_iter_next(struct ec_dict_elt_ref *iter) { - if (iter == NULL) - return NULL; - - return TAILQ_NEXT(iter, next); + return (struct ec_dict_elt_ref *)ec_htable_iter_next(&iter->htable); } const char * ec_dict_iter_get_key(const struct ec_dict_elt_ref *iter) { - if (iter == NULL) - return NULL; - - return iter->elt->key; + return (const char *)ec_htable_iter_get_key(&iter->htable); } void * ec_dict_iter_get_val(const struct ec_dict_elt_ref *iter) { - if (iter == NULL) - return NULL; - - return iter->elt->val; + return (struct ec_dict_elt_ref *)ec_htable_iter_get_val(&iter->htable); } void ec_dict_dump(FILE *out, const struct ec_dict *dict) @@ -321,60 +124,9 @@ void ec_dict_dump(FILE *out, const struct ec_dict *dict) struct ec_dict *ec_dict_dup(const struct ec_dict *dict) { - struct ec_dict *dup = NULL; - struct ec_dict_elt_ref *ref, *dup_ref = NULL; - - dup = ec_dict(); - if (dup == NULL) - return NULL; - - TAILQ_FOREACH(ref, &dict->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_dict_set(dup, dup_ref) < 0) - goto fail; - } - - return dup; - -fail: - ec_dict_elt_ref_free(dup_ref); - ec_dict_free(dup); - return NULL; + return (struct ec_dict *)ec_htable_dup(&dict->htable); } -static int ec_dict_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"); - return -1; - } - ret = read(fd, &ec_dict_seed, sizeof(ec_dict_seed)); - if (ret != sizeof(ec_dict_seed)) { - fprintf(stderr, "failed to read /dev/urandom\n"); - return -1; - } - close(fd); - return 0; -} - -static struct ec_init ec_dict_init = { - .init = ec_dict_init_func, - .priority = 50, -}; - -EC_INIT_REGISTER(ec_dict_init); - /* LCOV_EXCL_START */ static int ec_dict_testcase(void) { diff --git a/src/ecoli_htable.c b/src/ecoli_htable.c index 4b45a76..a8600e2 100644 --- a/src/ecoli_htable.c +++ b/src/ecoli_htable.c @@ -17,6 +17,7 @@ #include #include #include +#include #include #define FACTOR 3 @@ -25,30 +26,6 @@ EC_LOG_TYPE_REGISTER(htable); static uint32_t ec_htable_seed; -struct ec_htable_elt { - void *key; - size_t key_len; - void *val; - uint32_t hash; - ec_htable_elt_free_t free; - unsigned int refcount; -}; - -struct ec_htable_elt_ref { - TAILQ_ENTRY(ec_htable_elt_ref) next; - TAILQ_ENTRY(ec_htable_elt_ref) hnext; - struct ec_htable_elt *elt; -}; - -TAILQ_HEAD(ec_htable_elt_ref_list, ec_htable_elt_ref); - -struct ec_htable { - size_t len; - size_t table_size; - struct ec_htable_elt_ref_list list; - struct ec_htable_elt_ref_list *table; -}; - struct ec_htable *ec_htable(void) { struct ec_htable *htable; @@ -290,7 +267,7 @@ ec_htable_iter_next(struct ec_htable_elt_ref *iter) return TAILQ_NEXT(iter, next); } -const char * +const void * ec_htable_iter_get_key(const struct ec_htable_elt_ref *iter) { if (iter == NULL) @@ -299,6 +276,15 @@ ec_htable_iter_get_key(const struct ec_htable_elt_ref *iter) return iter->elt->key; } +size_t +ec_htable_iter_get_key_len(const struct ec_htable_elt_ref *iter) +{ + if (iter == NULL) + return 0; + + return iter->elt->key_len; +} + void * ec_htable_iter_get_val(const struct ec_htable_elt_ref *iter) { diff --git a/src/ecoli_htable_private.h b/src/ecoli_htable_private.h new file mode 100644 index 0000000..4e80d63 --- /dev/null +++ b/src/ecoli_htable_private.h @@ -0,0 +1,34 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright 2019, Olivier MATZ + */ + +#ifndef ECOLI_HTABLE_PRIVATE_ +#define ECOLI_HTABLE_PRIVATE_ + +#include + +struct ec_htable_elt { + void *key; + size_t key_len; + void *val; + uint32_t hash; + ec_htable_elt_free_t free; + unsigned int refcount; +}; + +struct ec_htable_elt_ref { + TAILQ_ENTRY(ec_htable_elt_ref) next; + TAILQ_ENTRY(ec_htable_elt_ref) hnext; + struct ec_htable_elt *elt; +}; + +TAILQ_HEAD(ec_htable_elt_ref_list, ec_htable_elt_ref); + +struct ec_htable { + size_t len; + size_t table_size; + struct ec_htable_elt_ref_list list; + struct ec_htable_elt_ref_list *table; +}; + +#endif diff --git a/src/meson.build b/src/meson.build index cfd1d04..85bd884 100644 --- a/src/meson.build +++ b/src/meson.build @@ -1,8 +1,6 @@ # SPDX-License-Identifier: BSD-3-Clause # Copyright 2018, Olivier MATZ -inc = include_directories('../include') - libecoli_sources = [ 'ecoli_assert.c', 'ecoli_complete.c', @@ -63,6 +61,6 @@ endif libecoli = shared_library('ecoli', libecoli_sources, - include_directories : inc, + include_directories : [inc, priv_inc], dependencies : deps, install : true) diff --git a/test/meson.build b/test/meson.build index f61dbc6..8d8601e 100644 --- a/test/meson.build +++ b/test/meson.build @@ -1,8 +1,6 @@ # SPDX-License-Identifier: BSD-3-Clause # Copyright 2018, Olivier MATZ -inc = include_directories('../include') - test_sources = [ 'test.c', ] -- 2.20.1