src/ecoli_keyval.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_keyval.h>
  21
  22 #define FACTOR 3
  23
  24 EC_LOG_TYPE_REGISTER(keyval);
  25
  26 static uint32_t ec_keyval_seed;
  27
  28 struct ec_keyval_elt {
  29         char *key;
  30         void *val;
  31         uint32_t hash;
  32         ec_keyval_elt_free_t free;
  33         unsigned int refcount;
  34 };
  35
  36 struct ec_keyval_elt_ref {
  37         LIST_ENTRY(ec_keyval_elt_ref) next;
  38         struct ec_keyval_elt *elt;
  39 };
  40
  41 LIST_HEAD(ec_keyval_elt_ref_list, ec_keyval_elt_ref);
  42
  43 struct ec_keyval {
  44         size_t len;
  45         size_t table_size;
  46         struct ec_keyval_elt_ref_list *table;
  47 };
  48
  49 struct ec_keyval_iter {
  50         const struct ec_keyval *keyval;
  51         size_t cur_idx;
  52         const struct ec_keyval_elt_ref *cur_ref;
  53 };
  54
  55 struct ec_keyval *ec_keyval(void)
  56 {
  57         struct ec_keyval *keyval;
  58
  59         keyval = ec_calloc(1, sizeof(*keyval));
  60         if (keyval == NULL)
  61                 return NULL;
  62
  63         return keyval;
  64 }
  65
  66 static struct ec_keyval_elt_ref *
  67 ec_keyval_lookup(const struct ec_keyval *keyval, const char *key)
  68 {
  69         struct ec_keyval_elt_ref *ref;
  70         uint32_t h, mask = keyval->table_size - 1;
  71
  72         if (keyval == NULL || key == NULL) {
  73                 errno = EINVAL;
  74                 return NULL;
  75         }
  76         if (keyval->table_size == 0) {
  77                 errno = ENOENT;
  78                 return NULL;
  79         }
  80
  81         h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
  82         LIST_FOREACH(ref, &keyval->table[h & mask], next) {
  83                 if (strcmp(ref->elt->key, key) == 0)
  84                         return ref;
  85         }
  86
  87         errno = ENOENT;
  88         return NULL;
  89 }
  90
  91 static void ec_keyval_elt_ref_free(struct ec_keyval_elt_ref *ref)
  92 {
  93         struct ec_keyval_elt *elt;
  94
  95         if (ref == NULL)
  96                 return;
  97
  98         elt = ref->elt;
  99         if (elt != NULL && --elt->refcount == 0) {
 100                 ec_free(elt->key);
 101                 if (elt->free != NULL)
 102                         elt->free(elt->val);
 103                 ec_free(elt);
 104         }
 105         ec_free(ref);
 106 }
 107
 108 bool ec_keyval_has_key(const struct ec_keyval *keyval, const char *key)
 109 {
 110         return !!ec_keyval_lookup(keyval, key);
 111 }
 112
 113 void *ec_keyval_get(const struct ec_keyval *keyval, const char *key)
 114 {
 115         struct ec_keyval_elt_ref *ref;
 116
 117         ref = ec_keyval_lookup(keyval, key);
 118         if (ref == NULL)
 119                 return NULL;
 120
 121         return ref->elt->val;
 122 }
 123
 124 int ec_keyval_del(struct ec_keyval *keyval, const char *key)
 125 {
 126         struct ec_keyval_elt_ref *ref;
 127
 128         ref = ec_keyval_lookup(keyval, key);
 129         if (ref == NULL)
 130                 return -1;
 131
 132         /* we could resize table here */
 133
 134         LIST_REMOVE(ref, next);
 135         ec_keyval_elt_ref_free(ref);
 136         keyval->len--;
 137
 138         return 0;
 139 }
 140
 141 static int ec_keyval_table_resize(struct ec_keyval *keyval, size_t new_size)
 142 {
 143         struct ec_keyval_elt_ref_list *new_table;
 144         struct ec_keyval_elt_ref *ref;
 145         size_t i;
 146
 147         if (new_size == 0 || (new_size & (new_size - 1))) {
 148                 errno = EINVAL;
 149                 return -1;
 150         }
 151
 152         new_table = ec_calloc(new_size, sizeof(*keyval->table));
 153         if (new_table == NULL)
 154                 return -1;
 155
 156         for (i = 0; i < keyval->table_size; i++) {
 157                 while (!LIST_EMPTY(&keyval->table[i])) {
 158                         ref = LIST_FIRST(&keyval->table[i]);
 159                         LIST_REMOVE(ref, next);
 160                         LIST_INSERT_HEAD(
 161                                 &new_table[ref->elt->hash & (new_size - 1)],
 162                                 ref, next);
 163                 }
 164         }
 165
 166         ec_free(keyval->table);
 167         keyval->table = new_table;
 168         keyval->table_size = new_size;
 169
 170         return 0;
 171 }
 172
 173 static int
 174 __ec_keyval_set(struct ec_keyval *keyval, struct ec_keyval_elt_ref *ref)
 175 {
 176         size_t new_size;
 177         uint32_t mask;
 178         int ret;
 179
 180         /* remove previous entry if any */
 181         ec_keyval_del(keyval, ref->elt->key);
 182
 183         if (keyval->len >= keyval->table_size) {
 184                 if (keyval->table_size != 0)
 185                         new_size =  keyval->table_size << FACTOR;
 186                 else
 187                         new_size =  1 << FACTOR;
 188                 ret = ec_keyval_table_resize(keyval, new_size);
 189                 if (ret < 0)
 190                         return ret;
 191         }
 192
 193         mask = keyval->table_size - 1;
 194         LIST_INSERT_HEAD(&keyval->table[ref->elt->hash & mask], ref, next);
 195         keyval->len++;
 196
 197         return 0;
 198 }
 199
 200 int ec_keyval_set(struct ec_keyval *keyval, const char *key, void *val,
 201         ec_keyval_elt_free_t free_cb)
 202 {
 203         struct ec_keyval_elt *elt = NULL;
 204         struct ec_keyval_elt_ref *ref = NULL;
 205         uint32_t h;
 206
 207         if (keyval == NULL || key == NULL) {
 208                 errno = EINVAL;
 209                 return -1;
 210         }
 211
 212         ref = ec_calloc(1, sizeof(*ref));
 213         if (ref == NULL)
 214                 goto fail;
 215
 216         elt = ec_calloc(1, sizeof(*elt));
 217         if (elt == NULL)
 218                 goto fail;
 219
 220         ref->elt = elt;
 221         elt->refcount = 1;
 222         elt->val = val;
 223         val = NULL;
 224         elt->free = free_cb;
 225         elt->key = ec_strdup(key);
 226         if (elt->key == NULL)
 227                 goto fail;
 228         h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
 229         elt->hash = h;
 230
 231         if (__ec_keyval_set(keyval, ref) < 0)
 232                 goto fail;
 233
 234         return 0;
 235
 236 fail:
 237         if (free_cb != NULL && val != NULL)
 238                 free_cb(val);
 239         ec_keyval_elt_ref_free(ref);
 240         return -1;
 241 }
 242
 243 void ec_keyval_free(struct ec_keyval *keyval)
 244 {
 245         struct ec_keyval_elt_ref *ref;
 246         size_t i;
 247
 248         if (keyval == NULL)
 249                 return;
 250
 251         for (i = 0; i < keyval->table_size; i++) {
 252                 while (!LIST_EMPTY(&keyval->table[i])) {
 253                         ref = LIST_FIRST(&keyval->table[i]);
 254                         LIST_REMOVE(ref, next);
 255                         ec_keyval_elt_ref_free(ref);
 256                 }
 257         }
 258         ec_free(keyval->table);
 259         ec_free(keyval);
 260 }
 261
 262 size_t ec_keyval_len(const struct ec_keyval *keyval)
 263 {
 264         return keyval->len;
 265 }
 266
 267 void
 268 ec_keyval_iter_free(struct ec_keyval_iter *iter)
 269 {
 270         ec_free(iter);
 271 }
 272
 273 struct ec_keyval_iter *
 274 ec_keyval_iter(const struct ec_keyval *keyval)
 275 {
 276         struct ec_keyval_iter *iter = NULL;
 277
 278         iter = ec_calloc(1, sizeof(*iter));
 279         if (iter == NULL)
 280                 return NULL;
 281
 282         iter->keyval = keyval;
 283         iter->cur_idx = 0;
 284         iter->cur_ref = NULL;
 285
 286         ec_keyval_iter_next(iter);
 287
 288         return iter;
 289 }
 290
 291 void
 292 ec_keyval_iter_next(struct ec_keyval_iter *iter)
 293 {
 294         const struct ec_keyval_elt_ref *ref;
 295         size_t i;
 296
 297         i = iter->cur_idx;
 298         if (i == iter->keyval->table_size)
 299                 return; /* no more element */
 300
 301         if (iter->cur_ref != NULL) {
 302                 ref = LIST_NEXT(iter->cur_ref, next);
 303                 if (ref != NULL) {
 304                         iter->cur_ref = ref;
 305                         return;
 306                 }
 307                 i++;
 308         }
 309
 310         for (; i < iter->keyval->table_size; i++) {
 311                 LIST_FOREACH(ref, &iter->keyval->table[i], next) {
 312                         iter->cur_idx = i;
 313                         iter->cur_ref = LIST_FIRST(&iter->keyval->table[i]);
 314                         return;
 315                 }
 316         }
 317
 318         iter->cur_idx = iter->keyval->table_size;
 319         iter->cur_ref = NULL;
 320 }
 321
 322 bool
 323 ec_keyval_iter_valid(const struct ec_keyval_iter *iter)
 324 {
 325         if (iter == NULL || iter->cur_ref == NULL)
 326                 return false;
 327
 328         return true;
 329 }
 330
 331 const char *
 332 ec_keyval_iter_get_key(const struct ec_keyval_iter *iter)
 333 {
 334         if (iter == NULL || iter->cur_ref == NULL)
 335                 return NULL;
 336
 337         return iter->cur_ref->elt->key;
 338 }
 339
 340 void *
 341 ec_keyval_iter_get_val(const struct ec_keyval_iter *iter)
 342 {
 343         if (iter == NULL || iter->cur_ref == NULL)
 344                 return NULL;
 345
 346         return iter->cur_ref->elt->val;
 347 }
 348
 349 void ec_keyval_dump(FILE *out, const struct ec_keyval *keyval)
 350 {
 351         struct ec_keyval_iter *iter;
 352
 353         if (keyval == NULL) {
 354                 fprintf(out, "empty keyval\n");
 355                 return;
 356         }
 357
 358         fprintf(out, "keyval:\n");
 359         for (iter = ec_keyval_iter(keyval);
 360              ec_keyval_iter_valid(iter);
 361              ec_keyval_iter_next(iter)) {
 362                 fprintf(out, "  %s: %p\n",
 363                         ec_keyval_iter_get_key(iter),
 364                         ec_keyval_iter_get_val(iter));
 365         }
 366         ec_keyval_iter_free(iter);
 367 }
 368
 369 struct ec_keyval *ec_keyval_dup(const struct ec_keyval *keyval)
 370 {
 371         struct ec_keyval *dup = NULL;
 372         struct ec_keyval_elt_ref *ref, *dup_ref = NULL;
 373         size_t i;
 374
 375         dup = ec_keyval();
 376         if (dup == NULL)
 377                 return NULL;
 378
 379         for (i = 0; i < keyval->table_size; i++) {
 380                 LIST_FOREACH(ref, &keyval->table[i], next) {
 381                         dup_ref = ec_calloc(1, sizeof(*ref));
 382                         if (dup_ref == NULL)
 383                                 goto fail;
 384                         dup_ref->elt = ref->elt;
 385                         ref->elt->refcount++;
 386
 387                         if (__ec_keyval_set(dup, dup_ref) < 0)
 388                                 goto fail;
 389                 }
 390         }
 391
 392         return dup;
 393
 394 fail:
 395         ec_keyval_elt_ref_free(dup_ref);
 396         ec_keyval_free(dup);
 397         return NULL;
 398 }
 399
 400 static int ec_keyval_init_func(void)
 401 {
 402         int fd;
 403         ssize_t ret;
 404
 405         return 0;//XXX for test reproduceability
 406
 407         fd = open("/dev/urandom", 0);
 408         if (fd == -1) {
 409                 fprintf(stderr, "failed to open /dev/urandom\n");
 410                 return -1;
 411         }
 412         ret = read(fd, &ec_keyval_seed, sizeof(ec_keyval_seed));
 413         if (ret != sizeof(ec_keyval_seed)) {
 414                 fprintf(stderr, "failed to read /dev/urandom\n");
 415                 return -1;
 416         }
 417         close(fd);
 418         return 0;
 419 }
 420
 421 static struct ec_init ec_keyval_init = {
 422         .init = ec_keyval_init_func,
 423         .priority = 50,
 424 };
 425
 426 EC_INIT_REGISTER(ec_keyval_init);
 427
 428 /* LCOV_EXCL_START */
 429 static int ec_keyval_testcase(void)
 430 {
 431         struct ec_keyval *keyval, *dup;
 432         struct ec_keyval_iter *iter;
 433         char *val;
 434         size_t i, count;
 435         int ret, testres = 0;
 436         FILE *f = NULL;
 437         char *buf = NULL;
 438         size_t buflen = 0;
 439
 440         keyval = ec_keyval();
 441         if (keyval == NULL) {
 442                 EC_LOG(EC_LOG_ERR, "cannot create keyval\n");
 443                 return -1;
 444         }
 445
 446         count = 0;
 447         for (iter = ec_keyval_iter(keyval);
 448              ec_keyval_iter_valid(iter);
 449              ec_keyval_iter_next(iter)) {
 450                 count++;
 451         }
 452         ec_keyval_iter_free(iter);
 453         testres |= EC_TEST_CHECK(count == 0, "invalid count in iterator");
 454
 455         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 0, "bad keyval len");
 456         ret = ec_keyval_set(keyval, "key1", "val1", NULL);
 457         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 458         ret = ec_keyval_set(keyval, "key2", ec_strdup("val2"), ec_free_func);
 459         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 460         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2, "bad keyval len");
 461
 462         val = ec_keyval_get(keyval, "key1");
 463         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val1"),
 464                                 "invalid keyval value");
 465         val = ec_keyval_get(keyval, "key2");
 466         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val2"),
 467                                 "invalid keyval value");
 468         val = ec_keyval_get(keyval, "key3");
 469         testres |= EC_TEST_CHECK(val == NULL, "key3 should be NULL");
 470
 471         ret = ec_keyval_set(keyval, "key1", "another_val1", NULL);
 472         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 473         ret = ec_keyval_set(keyval, "key2", ec_strdup("another_val2"),
 474                         ec_free_func);
 475         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 476         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2,
 477                                 "bad keyval len");
 478
 479         val = ec_keyval_get(keyval, "key1");
 480         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val1"),
 481                 "invalid keyval value");
 482         val = ec_keyval_get(keyval, "key2");
 483         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val2"),
 484                 "invalid keyval value");
 485         testres |= EC_TEST_CHECK(ec_keyval_has_key(keyval, "key1"),
 486                 "key1 should be in keyval");
 487
 488         f = open_memstream(&buf, &buflen);
 489         if (f == NULL)
 490                 goto fail;
 491         ec_keyval_dump(f, NULL);
 492         fclose(f);
 493         f = NULL;
 494         free(buf);
 495         buf = NULL;
 496
 497         f = open_memstream(&buf, &buflen);
 498         if (f == NULL)
 499                 goto fail;
 500         ec_keyval_dump(f, keyval);
 501         fclose(f);
 502         f = NULL;
 503         free(buf);
 504         buf = NULL;
 505
 506         ret = ec_keyval_del(keyval, "key1");
 507         testres |= EC_TEST_CHECK(ret == 0, "cannot del key1");
 508         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 1,
 509                 "invalid keyval len");
 510         ret = ec_keyval_del(keyval, "key2");
 511         testres |= EC_TEST_CHECK(ret == 0, "cannot del key2");
 512         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 0,
 513                 "invalid keyval len");
 514
 515         for (i = 0; i < 100; i++) {
 516                 char key[8];
 517                 snprintf(key, sizeof(key), "k%zd", i);
 518                 ret = ec_keyval_set(keyval, key, "val", NULL);
 519                 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 520         }
 521         dup = ec_keyval_dup(keyval);
 522         testres |= EC_TEST_CHECK(dup != NULL, "cannot duplicate keyval");
 523         if (dup != NULL) {
 524                 for (i = 0; i < 100; i++) {
 525                         char key[8];
 526                         snprintf(key, sizeof(key), "k%zd", i);
 527                         val = ec_keyval_get(dup, key);
 528                         testres |= EC_TEST_CHECK(
 529                                 val != NULL && !strcmp(val, "val"),
 530                                 "invalid keyval value");
 531                 }
 532                 ec_keyval_free(dup);
 533                 dup = NULL;
 534         }
 535
 536         count = 0;
 537         for (iter = ec_keyval_iter(keyval);
 538              ec_keyval_iter_valid(iter);
 539              ec_keyval_iter_next(iter)) {
 540                 count++;
 541         }
 542         ec_keyval_iter_free(iter);
 543         testres |= EC_TEST_CHECK(count == 100, "invalid count in iterator");
 544
 545         /* einval */
 546         ret = ec_keyval_set(keyval, NULL, "val1", NULL);
 547         testres |= EC_TEST_CHECK(ret == -1, "should not be able to set key");
 548         val = ec_keyval_get(keyval, NULL);
 549         testres |= EC_TEST_CHECK(val == NULL, "get(NULL) should no success");
 550
 551         ec_keyval_free(keyval);
 552
 553         return testres;
 554
 555 fail:
 556         ec_keyval_free(keyval);
 557         if (f)
 558                 fclose(f);
 559         free(buf);
 560         return -1;
 561 }
 562 /* LCOV_EXCL_STOP */
 563
 564 static struct ec_test ec_keyval_test = {
 565         .name = "keyval",
 566         .test = ec_keyval_testcase,
 567 };
 568
 569 EC_TEST_REGISTER(ec_keyval_test);