lib/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 *ec_keyval(void)
  50 {
  51         struct ec_keyval *keyval;
  52
  53         keyval = ec_calloc(1, sizeof(*keyval));
  54         if (keyval == NULL)
  55                 return NULL;
  56
  57         return keyval;
  58 }
  59
  60 static struct ec_keyval_elt_ref *
  61 ec_keyval_lookup(const struct ec_keyval *keyval, const char *key)
  62 {
  63         struct ec_keyval_elt_ref *ref;
  64         uint32_t h, mask = keyval->table_size - 1;
  65
  66         if (keyval == NULL || key == NULL) {
  67                 errno = EINVAL;
  68                 return NULL;
  69         }
  70         if (keyval->table_size == 0) {
  71                 errno = ENOENT;
  72                 return NULL;
  73         }
  74
  75         h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
  76         LIST_FOREACH(ref, &keyval->table[h & mask], next) {
  77                 if (strcmp(ref->elt->key, key) == 0) {
  78                         errno = 0;
  79                         return ref;
  80                 }
  81         }
  82
  83         errno = ENOENT;
  84         return NULL;
  85 }
  86
  87 static void ec_keyval_elt_ref_free(struct ec_keyval_elt_ref *ref)
  88 {
  89         struct ec_keyval_elt *elt;
  90
  91         if (ref == NULL)
  92                 return;
  93
  94         elt = ref->elt;
  95         if (elt != NULL && --elt->refcount == 0) {
  96                 ec_free(elt->key);
  97                 if (elt->free != NULL)
  98                         elt->free(elt->val);
  99                 ec_free(elt);
 100         }
 101         ec_free(ref);
 102 }
 103
 104 bool ec_keyval_has_key(const struct ec_keyval *keyval, const char *key)
 105 {
 106         return !!ec_keyval_lookup(keyval, key);
 107 }
 108
 109 void *ec_keyval_get(const struct ec_keyval *keyval, const char *key)
 110 {
 111         struct ec_keyval_elt_ref *ref;
 112
 113         ref = ec_keyval_lookup(keyval, key);
 114         if (ref == NULL)
 115                 return NULL;
 116
 117         return ref->elt->val;
 118 }
 119
 120 int ec_keyval_del(struct ec_keyval *keyval, const char *key)
 121 {
 122         struct ec_keyval_elt_ref *ref;
 123
 124         ref = ec_keyval_lookup(keyval, key);
 125         if (ref == NULL)
 126                 return -1;
 127
 128         /* we could resize table here */
 129
 130         LIST_REMOVE(ref, next);
 131         ec_keyval_elt_ref_free(ref);
 132         keyval->len--;
 133
 134         return 0;
 135 }
 136
 137 static int ec_keyval_table_resize(struct ec_keyval *keyval, size_t new_size)
 138 {
 139         struct ec_keyval_elt_ref_list *new_table;
 140         struct ec_keyval_elt_ref *ref;
 141         size_t i;
 142
 143         if (new_size == 0 || (new_size & (new_size - 1))) {
 144                 errno = EINVAL;
 145                 return -1;
 146         }
 147
 148         new_table = ec_calloc(new_size, sizeof(*keyval->table));
 149         if (new_table == NULL)
 150                 return -1;
 151
 152         for (i = 0; i < keyval->table_size; i++) {
 153                 while (!LIST_EMPTY(&keyval->table[i])) {
 154                         ref = LIST_FIRST(&keyval->table[i]);
 155                         LIST_REMOVE(ref, next);
 156                         LIST_INSERT_HEAD(
 157                                 &new_table[ref->elt->hash & (new_size - 1)],
 158                                 ref, next);
 159                 }
 160         }
 161
 162         ec_free(keyval->table);
 163         keyval->table = new_table;
 164         keyval->table_size = new_size;
 165
 166         return 0;
 167 }
 168
 169 static int
 170 __ec_keyval_set(struct ec_keyval *keyval, struct ec_keyval_elt_ref *ref)
 171 {
 172         size_t new_size;
 173         uint32_t mask;
 174         int ret;
 175
 176         /* remove previous entry if any */
 177         ec_keyval_del(keyval, ref->elt->key);
 178
 179         if (keyval->len >= keyval->table_size) {
 180                 if (keyval->table_size != 0)
 181                         new_size =  keyval->table_size << FACTOR;
 182                 else
 183                         new_size =  1 << FACTOR;
 184                 ret = ec_keyval_table_resize(keyval, new_size);
 185                 if (ret < 0)
 186                         return ret;
 187         }
 188
 189         mask = keyval->table_size - 1;
 190         LIST_INSERT_HEAD(&keyval->table[ref->elt->hash & mask], ref, next);
 191         keyval->len++;
 192
 193         return 0;
 194 }
 195
 196 int ec_keyval_set(struct ec_keyval *keyval, const char *key, void *val,
 197         ec_keyval_elt_free_t free_cb)
 198 {
 199         struct ec_keyval_elt *elt = NULL;
 200         struct ec_keyval_elt_ref *ref = NULL;
 201         uint32_t h;
 202
 203         if (keyval == NULL || key == NULL) {
 204                 errno = EINVAL;
 205                 return -1;
 206         }
 207
 208         ref = ec_calloc(1, sizeof(*ref));
 209         if (ref == NULL)
 210                 goto fail;
 211
 212         elt = ec_calloc(1, sizeof(*elt));
 213         if (elt == NULL)
 214                 goto fail;
 215
 216         ref->elt = elt;
 217         elt->refcount = 1;
 218         elt->val = val;
 219         val = NULL;
 220         elt->free = free_cb;
 221         elt->key = ec_strdup(key);
 222         if (elt->key == NULL)
 223                 goto fail;
 224         h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
 225         elt->hash = h;
 226
 227         if (__ec_keyval_set(keyval, ref) < 0)
 228                 goto fail;
 229
 230         return 0;
 231
 232 fail:
 233         if (free_cb != NULL && val != NULL)
 234                 free_cb(val);
 235         ec_keyval_elt_ref_free(ref);
 236         return -1;
 237 }
 238
 239 void ec_keyval_free(struct ec_keyval *keyval)
 240 {
 241         struct ec_keyval_elt_ref *ref;
 242         size_t i;
 243
 244         if (keyval == NULL)
 245                 return;
 246
 247         for (i = 0; i < keyval->table_size; i++) {
 248                 while (!LIST_EMPTY(&keyval->table[i])) {
 249                         ref = LIST_FIRST(&keyval->table[i]);
 250                         LIST_REMOVE(ref, next);
 251                         ec_keyval_elt_ref_free(ref);
 252                 }
 253         }
 254         ec_free(keyval->table);
 255         ec_free(keyval);
 256 }
 257
 258 size_t ec_keyval_len(const struct ec_keyval *keyval)
 259 {
 260         return keyval->len;
 261 }
 262
 263 void ec_keyval_dump(FILE *out, const struct ec_keyval *keyval)
 264 {
 265         struct ec_keyval_elt_ref *ref;
 266         size_t i;
 267
 268         if (keyval == NULL) {
 269                 fprintf(out, "empty keyval\n");
 270                 return;
 271         }
 272
 273         fprintf(out, "keyval:\n");
 274         for (i = 0; i < keyval->table_size; i++) {
 275                 LIST_FOREACH(ref, &keyval->table[i], next) {
 276                         fprintf(out, "  %s: %p\n",
 277                                 ref->elt->key, ref->elt->val);
 278                 }
 279         }
 280 }
 281
 282 struct ec_keyval *ec_keyval_dup(const struct ec_keyval *keyval)
 283 {
 284         struct ec_keyval *dup = NULL;
 285         struct ec_keyval_elt_ref *ref, *dup_ref = NULL;
 286         size_t i;
 287
 288         dup = ec_keyval();
 289         if (dup == NULL)
 290                 return NULL;
 291
 292         for (i = 0; i < keyval->table_size; i++) {
 293                 LIST_FOREACH(ref, &keyval->table[i], next) {
 294                         dup_ref = ec_calloc(1, sizeof(*ref));
 295                         if (dup_ref == NULL)
 296                                 goto fail;
 297                         dup_ref->elt = ref->elt;
 298                         ref->elt->refcount++;
 299
 300                         if (__ec_keyval_set(dup, dup_ref) < 0)
 301                                 goto fail;
 302                 }
 303         }
 304
 305         return dup;
 306
 307 fail:
 308         ec_keyval_elt_ref_free(dup_ref);
 309         ec_keyval_free(dup);
 310         return NULL;
 311 }
 312
 313 static int ec_keyval_init_func(void)
 314 {
 315         int fd;
 316         ssize_t ret;
 317
 318         fd = open("/dev/urandom", 0);
 319         if (fd == -1) {
 320                 fprintf(stderr, "failed to open /dev/urandom\n");
 321                 return -1;
 322         }
 323         ret = read(fd, &ec_keyval_seed, sizeof(ec_keyval_seed));
 324         if (ret != sizeof(ec_keyval_seed)) {
 325                 fprintf(stderr, "failed to read /dev/urandom\n");
 326                 return -1;
 327         }
 328         close(fd);
 329         return 0;
 330 }
 331
 332 static struct ec_init ec_keyval_init = {
 333         .init = ec_keyval_init_func,
 334         .priority = 50,
 335 };
 336
 337 EC_INIT_REGISTER(ec_keyval_init);
 338
 339 /* LCOV_EXCL_START */
 340 static int ec_keyval_testcase(void)
 341 {
 342         struct ec_keyval *keyval, *dup;
 343         char *val;
 344         size_t i;
 345         int ret, testres = 0;
 346
 347         keyval = ec_keyval();
 348         if (keyval == NULL) {
 349                 EC_LOG(EC_LOG_ERR, "cannot create keyval\n");
 350                 return -1;
 351         }
 352
 353         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 0, "bad keyval len");
 354         ret = ec_keyval_set(keyval, "key1", "val1", NULL);
 355         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 356         ret = ec_keyval_set(keyval, "key2", ec_strdup("val2"), ec_free_func);
 357         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 358         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2, "bad keyval len");
 359
 360         val = ec_keyval_get(keyval, "key1");
 361         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val1"),
 362                                 "invalid keyval value");
 363         val = ec_keyval_get(keyval, "key2");
 364         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "val2"),
 365                                 "invalid keyval value");
 366         val = ec_keyval_get(keyval, "key3");
 367         testres |= EC_TEST_CHECK(val == NULL, "key3 should be NULL");
 368
 369         ret = ec_keyval_set(keyval, "key1", "another_val1", NULL);
 370         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 371         ret = ec_keyval_set(keyval, "key2", ec_strdup("another_val2"),
 372                         ec_free_func);
 373         testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 374         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 2,
 375                                 "bad keyval len");
 376
 377         val = ec_keyval_get(keyval, "key1");
 378         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val1"),
 379                 "invalid keyval value");
 380         val = ec_keyval_get(keyval, "key2");
 381         testres |= EC_TEST_CHECK(val != NULL && !strcmp(val, "another_val2"),
 382                 "invalid keyval value");
 383         testres |= EC_TEST_CHECK(ec_keyval_has_key(keyval, "key1"),
 384                 "key1 should be in keyval");
 385
 386         ret = ec_keyval_del(keyval, "key1");
 387         testres |= EC_TEST_CHECK(ret == 0, "cannot del key");
 388         testres |= EC_TEST_CHECK(ec_keyval_len(keyval) == 1,
 389                 "invalid keyval len");
 390
 391         ec_keyval_dump(stdout, NULL);
 392         ec_keyval_dump(stdout, keyval);
 393
 394         for (i = 0; i < 100; i++) {
 395                 char key[8];
 396                 snprintf(key, sizeof(key), "k%zd", i);
 397                 ret = ec_keyval_set(keyval, key, "val", NULL);
 398                 testres |= EC_TEST_CHECK(ret == 0, "cannot set key");
 399         }
 400         dup = ec_keyval_dup(keyval);
 401         testres |= EC_TEST_CHECK(dup != NULL, "cannot duplicate keyval");
 402         if (dup != NULL) {
 403                 for (i = 0; i < 100; i++) {
 404                         char key[8];
 405                         snprintf(key, sizeof(key), "k%zd", i);
 406                         val = ec_keyval_get(dup, key);
 407                         testres |= EC_TEST_CHECK(
 408                                 val != NULL && !strcmp(val, "val"),
 409                                 "invalid keyval value");
 410                 }
 411                 ec_keyval_free(dup);
 412                 dup = NULL;
 413         }
 414
 415         /* einval */
 416         ret = ec_keyval_set(keyval, NULL, "val1", NULL);
 417         testres |= EC_TEST_CHECK(ret == -1, "should not be able to set key");
 418         val = ec_keyval_get(keyval, NULL);
 419         testres |= EC_TEST_CHECK(val == NULL, "get(NULL) should no success");
 420
 421         ec_keyval_free(keyval);
 422
 423         return testres;
 424 }
 425 /* LCOV_EXCL_STOP */
 426
 427 static struct ec_test ec_keyval_test = {
 428         .name = "keyval",
 429         .test = ec_keyval_testcase,
 430 };
 431
 432 EC_TEST_REGISTER(ec_keyval_test);