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