src/ecoli_htable.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright 2016, Olivier MATZ <zer0@droids-corp.org>
   3  */
   4
   5 #include <sys/types.h>
   6 #include <sys/stat.h>
   7 #include <sys/queue.h>
   8 #include <stdlib.h>
   9 #include <stdint.h>
  10 #include <unistd.h>
  11 #include <assert.h>
  12 #include <errno.h>
  13 #include <fcntl.h>
  14
  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>
  22
  23 #define FACTOR 3
  24
  25 EC_LOG_TYPE_REGISTER(htable);
  26
  27 static uint32_t ec_htable_seed;
  28
  29 struct ec_htable *ec_htable(void)
  30 {
  31         struct ec_htable *htable;
  32
  33         htable = ec_calloc(1, sizeof(*htable));
  34         if (htable == NULL)
  35                 return NULL;
  36         TAILQ_INIT(&htable->list);
  37
  38         return htable;
  39 }
  40
  41 static struct ec_htable_elt_ref *
  42 ec_htable_lookup(const struct ec_htable *htable, const void *key,
  43                 size_t key_len)
  44 {
  45         struct ec_htable_elt_ref *ref;
  46         uint32_t h, mask = htable->table_size - 1;
  47
  48         if (htable == NULL || key == NULL) {
  49                 errno = EINVAL;
  50                 return NULL;
  51         }
  52         if (htable->table_size == 0) {
  53                 errno = ENOENT;
  54                 return NULL;
  55         }
  56
  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)
  60                         continue;
  61                 if (memcmp(ref->elt->key, key, key_len) == 0)
  62                         return ref;
  63         }
  64
  65         errno = ENOENT;
  66         return NULL;
  67 }
  68
  69 static void ec_htable_elt_ref_free(struct ec_htable_elt_ref *ref)
  70 {
  71         struct ec_htable_elt *elt;
  72
  73         if (ref == NULL)
  74                 return;
  75
  76         elt = ref->elt;
  77         if (elt != NULL && --elt->refcount == 0) {
  78                 ec_free(elt->key);
  79                 if (elt->free != NULL)
  80                         elt->free(elt->val);
  81                 ec_free(elt);
  82         }
  83         ec_free(ref);
  84 }
  85
  86 bool ec_htable_has_key(const struct ec_htable *htable, const void *key,
  87                 size_t key_len)
  88 {
  89         return !!ec_htable_lookup(htable, key, key_len);
  90 }
  91
  92 void *ec_htable_get(const struct ec_htable *htable, const void *key,
  93                 size_t key_len)
  94 {
  95         struct ec_htable_elt_ref *ref;
  96
  97         ref = ec_htable_lookup(htable, key, key_len);
  98         if (ref == NULL)
  99                 return NULL;
 100
 101         return ref->elt->val;
 102 }
 103
 104 int ec_htable_del(struct ec_htable *htable, const void *key, size_t key_len)
 105 {
 106         struct ec_htable_elt_ref *ref;
 107         size_t idx;
 108
 109         ref = ec_htable_lookup(htable, key, key_len);
 110         if (ref == NULL)
 111                 return -1;
 112
 113         /* we could resize table here */
 114
 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);
 119         htable->len--;
 120
 121         return 0;
 122 }
 123
 124 static int ec_htable_table_resize(struct ec_htable *htable, size_t new_size)
 125 {
 126         struct ec_htable_elt_ref_list *new_table;
 127         struct ec_htable_elt_ref *ref;
 128         size_t i;
 129
 130         if (new_size == 0 || (new_size & (new_size - 1))) {
 131                 errno = EINVAL;
 132                 return -1;
 133         }
 134
 135         new_table = ec_calloc(new_size, sizeof(*htable->table));
 136         if (new_table == NULL)
 137                 return -1;
 138         for (i = 0; i < new_size; i++)
 139                 TAILQ_INIT(&new_table[i]);
 140
 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);
 146         }
 147
 148         ec_free(htable->table);
 149         htable->table = new_table;
 150         htable->table_size = new_size;
 151
 152         return 0;
 153 }
 154
 155 static int
 156 __ec_htable_set(struct ec_htable *htable, struct ec_htable_elt_ref *ref)
 157 {
 158         size_t new_size;
 159         uint32_t mask;
 160         int ret;
 161
 162         /* remove previous entry if any */
 163         ec_htable_del(htable, ref->elt->key, ref->elt->key_len);
 164
 165         if (htable->len >= htable->table_size) {
 166                 if (htable->table_size != 0)
 167                         new_size =  htable->table_size << FACTOR;
 168                 else
 169                         new_size =  1 << FACTOR;
 170                 ret = ec_htable_table_resize(htable, new_size);
 171                 if (ret < 0)
 172                         return ret;
 173         }
 174
 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);
 178         htable->len++;
 179
 180         return 0;
 181 }
 182
 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)
 185 {
 186         struct ec_htable_elt *elt = NULL;
 187         struct ec_htable_elt_ref *ref = NULL;
 188         uint32_t h;
 189
 190         if (htable == NULL || key == NULL || key_len == 0) {
 191                 errno = EINVAL;
 192                 return -1;
 193         }
 194
 195         ref = ec_calloc(1, sizeof(*ref));
 196         if (ref == NULL)
 197                 goto fail;
 198
 199         elt = ec_calloc(1, sizeof(*elt));
 200         if (elt == NULL)
 201                 goto fail;
 202
 203         ref->elt = elt;
 204         elt->refcount = 1;
 205         elt->val = val;
 206         val = NULL;
 207         elt->free = free_cb;
 208         elt->key_len = key_len;
 209         elt->key = ec_malloc(key_len);
 210         if (elt->key == NULL)
 211                 goto fail;
 212         memcpy(elt->key, key, key_len);
 213         h = ec_murmurhash3(key, key_len, ec_htable_seed);
 214         elt->hash = h;
 215
 216         if (__ec_htable_set(htable, ref) < 0)
 217                 goto fail;
 218
 219         return 0;
 220
 221 fail:
 222         if (free_cb != NULL && val != NULL)
 223                 free_cb(val);
 224         ec_htable_elt_ref_free(ref);
 225         return -1;
 226 }
 227
 228 void ec_htable_free(struct ec_htable *htable)
 229 {
 230         struct ec_htable_elt_ref *ref;
 231         size_t idx;
 232
 233         if (htable == NULL)
 234                 return;
 235
 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);
 242         }
 243         ec_free(htable->table);
 244         ec_free(htable);
 245 }
 246
 247 size_t ec_htable_len(const struct ec_htable *htable)
 248 {
 249         return htable->len;
 250 }
 251
 252 struct ec_htable_elt_ref *
 253 ec_htable_iter(const struct ec_htable *htable)
 254 {
 255         if (htable == NULL)
 256                 return NULL;
 257
 258         return TAILQ_FIRST(&htable->list);
 259 }
 260
 261 struct ec_htable_elt_ref *
 262 ec_htable_iter_next(struct ec_htable_elt_ref *iter)
 263 {
 264         if (iter == NULL)
 265                 return NULL;
 266
 267         return TAILQ_NEXT(iter, next);
 268 }
 269
 270 const void *
 271 ec_htable_iter_get_key(const struct ec_htable_elt_ref *iter)
 272 {
 273         if (iter == NULL)
 274                 return NULL;
 275
 276         return iter->elt->key;
 277 }
 278
 279 size_t
 280 ec_htable_iter_get_key_len(const struct ec_htable_elt_ref *iter)
 281 {
 282         if (iter == NULL)
 283                 return 0;
 284
 285         return iter->elt->key_len;
 286 }
 287
 288 void *
 289 ec_htable_iter_get_val(const struct ec_htable_elt_ref *iter)
 290 {
 291         if (iter == NULL)
 292                 return NULL;
 293
 294         return iter->elt->val;
 295 }
 296
 297 void ec_htable_dump(FILE *out, const struct ec_htable *htable)
 298 {
 299         if (htable == NULL) {
 300                 fprintf(out, "empty htable\n");
 301                 return;
 302         }
 303
 304         fprintf(out, "htable: %zd elements\n", htable->len);
 305 }
 306
 307 struct ec_htable *ec_htable_dup(const struct ec_htable *htable)
 308 {
 309         struct ec_htable *dup = NULL;
 310         struct ec_htable_elt_ref *ref, *dup_ref = NULL;
 311
 312         dup = ec_htable();
 313         if (dup == NULL)
 314                 return NULL;
 315
 316         TAILQ_FOREACH(ref, &htable->list, next) {
 317                 dup_ref = ec_calloc(1, sizeof(*ref));
 318                 if (dup_ref == NULL)
 319                         goto fail;
 320                 dup_ref->elt = ref->elt;
 321                 ref->elt->refcount++;
 322
 323                 if (__ec_htable_set(dup, dup_ref) < 0)
 324                         goto fail;
 325         }
 326
 327         return dup;
 328
 329 fail:
 330         ec_htable_elt_ref_free(dup_ref);
 331         ec_htable_free(dup);
 332         return NULL;
 333 }
 334
 335 static int ec_htable_init_func(void)
 336 {
 337         int fd;
 338         ssize_t ret;
 339
 340         return 0;//XXX for test reproduceability
 341
 342         fd = open("/dev/urandom", 0);
 343         if (fd == -1) {
 344                 fprintf(stderr, "failed to open /dev/urandom\n");
 345                 return -1;
 346         }
 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");
 350                 return -1;
 351         }
 352         close(fd);
 353         return 0;
 354 }
 355
 356 static struct ec_init ec_htable_init = {
 357         .init = ec_htable_init_func,
 358         .priority = 50,
 359 };
 360
 361 EC_INIT_REGISTER(ec_htable_init);
 362
 363 /* LCOV_EXCL_START */
 364 static int ec_htable_testcase(void)
 365 {
 366         struct ec_htable *htable;
 367         struct ec_htable_elt_ref *iter;
 368         size_t count;
 369         int ret, testres = 0;
 370         FILE *f = NULL;
 371         char *buf = NULL;
 372         size_t buflen = 0;
 373
 374         /* Minimal test, since ec_dict also uses this code and is better
 375          * tested. */
 376
 377         htable = ec_htable();
 378         if (htable == NULL) {
 379                 EC_LOG(EC_LOG_ERR, "cannot create htable\n");
 380                 return -1;
 381         }
 382
 383         count = 0;
 384         for (iter = ec_htable_iter(htable);
 385              iter != NULL;
 386              iter = ec_htable_iter_next(iter)) {
 387                 count++;
 388         }
 389         testres |= EC_TEST_CHECK(count == 0, "invalid count in iterator");
 390
 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");
 397
 398         f = open_memstream(&buf, &buflen);
 399         if (f == NULL)
 400                 goto fail;
 401         ec_htable_dump(f, NULL);
 402         fclose(f);
 403         f = NULL;
 404         free(buf);
 405         buf = NULL;
 406
 407         f = open_memstream(&buf, &buflen);
 408         if (f == NULL)
 409                 goto fail;
 410         ec_htable_dump(f, htable);
 411         fclose(f);
 412         f = NULL;
 413         free(buf);
 414         buf = NULL;
 415
 416         ec_htable_free(htable);
 417
 418         return testres;
 419
 420 fail:
 421         ec_htable_free(htable);
 422         if (f)
 423                 fclose(f);
 424         free(buf);
 425         return -1;
 426 }
 427 /* LCOV_EXCL_STOP */
 428
 429 static struct ec_test ec_htable_test = {
 430         .name = "htable",
 431         .test = ec_htable_testcase,
 432 };
 433
 434 EC_TEST_REGISTER(ec_htable_test);