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.h>
24 EC_LOG_TYPE_REGISTER(htable);
26 static uint32_t ec_htable_seed;
28 struct ec_htable_elt {
33 ec_htable_elt_free_t free;
34 unsigned int refcount;
37 struct ec_htable_elt_ref {
38 TAILQ_ENTRY(ec_htable_elt_ref) next;
39 TAILQ_ENTRY(ec_htable_elt_ref) hnext;
40 struct ec_htable_elt *elt;
43 TAILQ_HEAD(ec_htable_elt_ref_list, ec_htable_elt_ref);
48 struct ec_htable_elt_ref_list list;
49 struct ec_htable_elt_ref_list *table;
52 struct ec_htable *ec_htable(void)
54 struct ec_htable *htable;
56 htable = ec_calloc(1, sizeof(*htable));
59 TAILQ_INIT(&htable->list);
64 static struct ec_htable_elt_ref *
65 ec_htable_lookup(const struct ec_htable *htable, const void *key,
68 struct ec_htable_elt_ref *ref;
69 uint32_t h, mask = htable->table_size - 1;
71 if (htable == NULL || key == NULL) {
75 if (htable->table_size == 0) {
80 h = ec_murmurhash3(key, key_len, ec_htable_seed);
81 TAILQ_FOREACH(ref, &htable->table[h & mask], hnext) {
82 if (ref->elt->key_len != key_len)
84 if (memcmp(ref->elt->key, key, key_len) == 0)
92 static void ec_htable_elt_ref_free(struct ec_htable_elt_ref *ref)
94 struct ec_htable_elt *elt;
100 if (elt != NULL && --elt->refcount == 0) {
102 if (elt->free != NULL)
109 bool ec_htable_has_key(const struct ec_htable *htable, const void *key,
112 return !!ec_htable_lookup(htable, key, key_len);
115 void *ec_htable_get(const struct ec_htable *htable, const void *key,
118 struct ec_htable_elt_ref *ref;
120 ref = ec_htable_lookup(htable, key, key_len);
124 return ref->elt->val;
127 int ec_htable_del(struct ec_htable *htable, const void *key, size_t key_len)
129 struct ec_htable_elt_ref *ref;
132 ref = ec_htable_lookup(htable, key, key_len);
136 /* we could resize table here */
138 TAILQ_REMOVE(&htable->list, ref, next);
139 idx = ref->elt->hash & (htable->table_size - 1);
140 TAILQ_REMOVE(&htable->table[idx], ref, hnext);
141 ec_htable_elt_ref_free(ref);
147 static int ec_htable_table_resize(struct ec_htable *htable, size_t new_size)
149 struct ec_htable_elt_ref_list *new_table;
150 struct ec_htable_elt_ref *ref;
153 if (new_size == 0 || (new_size & (new_size - 1))) {
158 new_table = ec_calloc(new_size, sizeof(*htable->table));
159 if (new_table == NULL)
161 for (i = 0; i < new_size; i++)
162 TAILQ_INIT(&new_table[i]);
164 TAILQ_FOREACH(ref, &htable->list, next) {
165 i = ref->elt->hash & (htable->table_size - 1);
166 TAILQ_REMOVE(&htable->table[i], ref, hnext);
167 i = ref->elt->hash & (new_size - 1);
168 TAILQ_INSERT_TAIL(&new_table[i], ref, hnext);
171 ec_free(htable->table);
172 htable->table = new_table;
173 htable->table_size = new_size;
179 __ec_htable_set(struct ec_htable *htable, struct ec_htable_elt_ref *ref)
185 /* remove previous entry if any */
186 ec_htable_del(htable, ref->elt->key, ref->elt->key_len);
188 if (htable->len >= htable->table_size) {
189 if (htable->table_size != 0)
190 new_size = htable->table_size << FACTOR;
192 new_size = 1 << FACTOR;
193 ret = ec_htable_table_resize(htable, new_size);
198 mask = htable->table_size - 1;
199 TAILQ_INSERT_TAIL(&htable->table[ref->elt->hash & mask], ref, hnext);
200 TAILQ_INSERT_TAIL(&htable->list, ref, next);
206 int ec_htable_set(struct ec_htable *htable, const void *key, size_t key_len,
207 void *val, ec_htable_elt_free_t free_cb)
209 struct ec_htable_elt *elt = NULL;
210 struct ec_htable_elt_ref *ref = NULL;
213 if (htable == NULL || key == NULL || key_len == 0) {
218 ref = ec_calloc(1, sizeof(*ref));
222 elt = ec_calloc(1, sizeof(*elt));
231 elt->key_len = key_len;
232 elt->key = ec_malloc(key_len);
233 if (elt->key == NULL)
235 memcpy(elt->key, key, key_len);
236 h = ec_murmurhash3(key, key_len, ec_htable_seed);
239 if (__ec_htable_set(htable, ref) < 0)
245 if (free_cb != NULL && val != NULL)
247 ec_htable_elt_ref_free(ref);
251 void ec_htable_free(struct ec_htable *htable)
253 struct ec_htable_elt_ref *ref;
259 while (!TAILQ_EMPTY(&htable->list)) {
260 ref = TAILQ_FIRST(&htable->list);
261 TAILQ_REMOVE(&htable->list, ref, next);
262 idx = ref->elt->hash & (htable->table_size - 1);
263 TAILQ_REMOVE(&htable->table[idx], ref, hnext);
264 ec_htable_elt_ref_free(ref);
266 ec_free(htable->table);
270 size_t ec_htable_len(const struct ec_htable *htable)
275 struct ec_htable_elt_ref *
276 ec_htable_iter(const struct ec_htable *htable)
281 return TAILQ_FIRST(&htable->list);
284 struct ec_htable_elt_ref *
285 ec_htable_iter_next(struct ec_htable_elt_ref *iter)
290 return TAILQ_NEXT(iter, next);
294 ec_htable_iter_get_key(const struct ec_htable_elt_ref *iter)
299 return iter->elt->key;
303 ec_htable_iter_get_val(const struct ec_htable_elt_ref *iter)
308 return iter->elt->val;
311 void ec_htable_dump(FILE *out, const struct ec_htable *htable)
313 if (htable == NULL) {
314 fprintf(out, "empty htable\n");
318 fprintf(out, "htable: %zd elements\n", htable->len);
321 struct ec_htable *ec_htable_dup(const struct ec_htable *htable)
323 struct ec_htable *dup = NULL;
324 struct ec_htable_elt_ref *ref, *dup_ref = NULL;
330 TAILQ_FOREACH(ref, &htable->list, next) {
331 dup_ref = ec_calloc(1, sizeof(*ref));
334 dup_ref->elt = ref->elt;
335 ref->elt->refcount++;
337 if (__ec_htable_set(dup, dup_ref) < 0)
344 ec_htable_elt_ref_free(dup_ref);
349 static int ec_htable_init_func(void)
354 return 0;//XXX for test reproduceability
356 fd = open("/dev/urandom", 0);
358 fprintf(stderr, "failed to open /dev/urandom\n");
361 ret = read(fd, &ec_htable_seed, sizeof(ec_htable_seed));
362 if (ret != sizeof(ec_htable_seed)) {
363 fprintf(stderr, "failed to read /dev/urandom\n");
370 static struct ec_init ec_htable_init = {
371 .init = ec_htable_init_func,
375 EC_INIT_REGISTER(ec_htable_init);
377 /* LCOV_EXCL_START */
378 static int ec_htable_testcase(void)
380 struct ec_htable *htable;
381 struct ec_htable_elt_ref *iter;
383 int ret, testres = 0;
388 /* Minimal test, since ec_dict also uses this code and is better
391 htable = ec_htable();
392 if (htable == NULL) {
393 EC_LOG(EC_LOG_ERR, "cannot create htable\n");
398 for (iter = ec_htable_iter(htable);
400 iter = ec_htable_iter_next(iter)) {
403 testres |= EC_TEST_CHECK(count == 0, "invalid count in iterator");
405 testres |= EC_TEST_CHECK(ec_htable_len(htable) == 0, "bad htable len");
406 ret = ec_htable_set(htable, "key1", 4, "val1", NULL);
407 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
408 ret = ec_htable_set(htable, "key2", 4, ec_strdup("val2"), ec_free_func);
409 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
410 testres |= EC_TEST_CHECK(ec_htable_len(htable) == 2, "bad htable len");
412 f = open_memstream(&buf, &buflen);
415 ec_htable_dump(f, NULL);
421 f = open_memstream(&buf, &buflen);
424 ec_htable_dump(f, htable);
430 ec_htable_free(htable);
435 ec_htable_free(htable);
443 static struct ec_test ec_htable_test = {
445 .test = ec_htable_testcase,
448 EC_TEST_REGISTER(ec_htable_test);