1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright 2016, Olivier MATZ <zer0@droids-corp.org>
15 #include <ecoli_init.h>
16 #include <ecoli_malloc.h>
17 #include <ecoli_log.h>
18 #include <ecoli_test.h>
19 #include <ecoli_murmurhash.h>
20 #include <ecoli_htable_private.h>
21 #include <ecoli_htable.h>
25 EC_LOG_TYPE_REGISTER(htable);
27 static uint32_t ec_htable_seed;
29 struct ec_htable *ec_htable(void)
31 struct ec_htable *htable;
33 htable = ec_calloc(1, sizeof(*htable));
36 TAILQ_INIT(&htable->list);
41 static struct ec_htable_elt_ref *
42 ec_htable_lookup(const struct ec_htable *htable, const void *key,
45 struct ec_htable_elt_ref *ref;
46 uint32_t h, mask = htable->table_size - 1;
48 if (htable == NULL || key == NULL) {
52 if (htable->table_size == 0) {
57 h = ec_murmurhash3(key, key_len, ec_htable_seed);
58 TAILQ_FOREACH(ref, &htable->table[h & mask], hnext) {
59 if (ref->elt->key_len != key_len)
61 if (memcmp(ref->elt->key, key, key_len) == 0)
69 static void ec_htable_elt_ref_free(struct ec_htable_elt_ref *ref)
71 struct ec_htable_elt *elt;
77 if (elt != NULL && --elt->refcount == 0) {
79 if (elt->free != NULL)
86 bool ec_htable_has_key(const struct ec_htable *htable, const void *key,
89 return !!ec_htable_lookup(htable, key, key_len);
92 void *ec_htable_get(const struct ec_htable *htable, const void *key,
95 struct ec_htable_elt_ref *ref;
97 ref = ec_htable_lookup(htable, key, key_len);
101 return ref->elt->val;
104 int ec_htable_del(struct ec_htable *htable, const void *key, size_t key_len)
106 struct ec_htable_elt_ref *ref;
109 ref = ec_htable_lookup(htable, key, key_len);
113 /* we could resize table here */
115 TAILQ_REMOVE(&htable->list, ref, next);
116 idx = ref->elt->hash & (htable->table_size - 1);
117 TAILQ_REMOVE(&htable->table[idx], ref, hnext);
118 ec_htable_elt_ref_free(ref);
124 static int ec_htable_table_resize(struct ec_htable *htable, size_t new_size)
126 struct ec_htable_elt_ref_list *new_table;
127 struct ec_htable_elt_ref *ref;
130 if (new_size == 0 || (new_size & (new_size - 1))) {
135 new_table = ec_calloc(new_size, sizeof(*htable->table));
136 if (new_table == NULL)
138 for (i = 0; i < new_size; i++)
139 TAILQ_INIT(&new_table[i]);
141 TAILQ_FOREACH(ref, &htable->list, next) {
142 i = ref->elt->hash & (htable->table_size - 1);
143 TAILQ_REMOVE(&htable->table[i], ref, hnext);
144 i = ref->elt->hash & (new_size - 1);
145 TAILQ_INSERT_TAIL(&new_table[i], ref, hnext);
148 ec_free(htable->table);
149 htable->table = new_table;
150 htable->table_size = new_size;
156 __ec_htable_set(struct ec_htable *htable, struct ec_htable_elt_ref *ref)
162 /* remove previous entry if any */
163 ec_htable_del(htable, ref->elt->key, ref->elt->key_len);
165 if (htable->len >= htable->table_size) {
166 if (htable->table_size != 0)
167 new_size = htable->table_size << FACTOR;
169 new_size = 1 << FACTOR;
170 ret = ec_htable_table_resize(htable, new_size);
175 mask = htable->table_size - 1;
176 TAILQ_INSERT_TAIL(&htable->table[ref->elt->hash & mask], ref, hnext);
177 TAILQ_INSERT_TAIL(&htable->list, ref, next);
183 int ec_htable_set(struct ec_htable *htable, const void *key, size_t key_len,
184 void *val, ec_htable_elt_free_t free_cb)
186 struct ec_htable_elt *elt = NULL;
187 struct ec_htable_elt_ref *ref = NULL;
190 if (htable == NULL || key == NULL || key_len == 0) {
195 ref = ec_calloc(1, sizeof(*ref));
199 elt = ec_calloc(1, sizeof(*elt));
208 elt->key_len = key_len;
209 elt->key = ec_malloc(key_len);
210 if (elt->key == NULL)
212 memcpy(elt->key, key, key_len);
213 h = ec_murmurhash3(key, key_len, ec_htable_seed);
216 if (__ec_htable_set(htable, ref) < 0)
222 if (free_cb != NULL && val != NULL)
224 ec_htable_elt_ref_free(ref);
228 void ec_htable_free(struct ec_htable *htable)
230 struct ec_htable_elt_ref *ref;
236 while (!TAILQ_EMPTY(&htable->list)) {
237 ref = TAILQ_FIRST(&htable->list);
238 TAILQ_REMOVE(&htable->list, ref, next);
239 idx = ref->elt->hash & (htable->table_size - 1);
240 TAILQ_REMOVE(&htable->table[idx], ref, hnext);
241 ec_htable_elt_ref_free(ref);
243 ec_free(htable->table);
247 size_t ec_htable_len(const struct ec_htable *htable)
252 struct ec_htable_elt_ref *
253 ec_htable_iter(const struct ec_htable *htable)
258 return TAILQ_FIRST(&htable->list);
261 struct ec_htable_elt_ref *
262 ec_htable_iter_next(struct ec_htable_elt_ref *iter)
267 return TAILQ_NEXT(iter, next);
271 ec_htable_iter_get_key(const struct ec_htable_elt_ref *iter)
276 return iter->elt->key;
280 ec_htable_iter_get_key_len(const struct ec_htable_elt_ref *iter)
285 return iter->elt->key_len;
289 ec_htable_iter_get_val(const struct ec_htable_elt_ref *iter)
294 return iter->elt->val;
297 void ec_htable_dump(FILE *out, const struct ec_htable *htable)
299 if (htable == NULL) {
300 fprintf(out, "empty htable\n");
304 fprintf(out, "htable: %zd elements\n", htable->len);
307 struct ec_htable *ec_htable_dup(const struct ec_htable *htable)
309 struct ec_htable *dup = NULL;
310 struct ec_htable_elt_ref *ref, *dup_ref = NULL;
316 TAILQ_FOREACH(ref, &htable->list, next) {
317 dup_ref = ec_calloc(1, sizeof(*ref));
320 dup_ref->elt = ref->elt;
321 ref->elt->refcount++;
323 if (__ec_htable_set(dup, dup_ref) < 0)
330 ec_htable_elt_ref_free(dup_ref);
335 static int ec_htable_init_func(void)
340 return 0;//XXX for test reproduceability
342 fd = open("/dev/urandom", 0);
344 fprintf(stderr, "failed to open /dev/urandom\n");
347 ret = read(fd, &ec_htable_seed, sizeof(ec_htable_seed));
348 if (ret != sizeof(ec_htable_seed)) {
349 fprintf(stderr, "failed to read /dev/urandom\n");
356 static struct ec_init ec_htable_init = {
357 .init = ec_htable_init_func,
361 EC_INIT_REGISTER(ec_htable_init);
363 /* LCOV_EXCL_START */
364 static int ec_htable_testcase(void)
366 struct ec_htable *htable;
367 struct ec_htable_elt_ref *iter;
369 int ret, testres = 0;
374 /* Minimal test, since ec_dict also uses this code and is better
377 htable = ec_htable();
378 if (htable == NULL) {
379 EC_LOG(EC_LOG_ERR, "cannot create htable\n");
384 for (iter = ec_htable_iter(htable);
386 iter = ec_htable_iter_next(iter)) {
389 testres |= EC_TEST_CHECK(count == 0, "invalid count in iterator");
391 testres |= EC_TEST_CHECK(ec_htable_len(htable) == 0, "bad htable len");
392 ret = ec_htable_set(htable, "key1", 4, "val1", NULL);
393 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
394 ret = ec_htable_set(htable, "key2", 4, ec_strdup("val2"), ec_free_func);
395 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
396 testres |= EC_TEST_CHECK(ec_htable_len(htable) == 2, "bad htable len");
398 f = open_memstream(&buf, &buflen);
401 ec_htable_dump(f, NULL);
407 f = open_memstream(&buf, &buflen);
410 ec_htable_dump(f, htable);
416 ec_htable_free(htable);
421 ec_htable_free(htable);
429 static struct ec_test ec_htable_test = {
431 .test = ec_htable_testcase,
434 EC_TEST_REGISTER(ec_htable_test);