lib/ecoli_keyval.c

   1 /*
   2  * Copyright (c) 2016, Olivier MATZ <zer0@droids-corp.org>
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are met:
   6  *
   7  *     * Redistributions of source code must retain the above copyright
   8  *       notice, this list of conditions and the following disclaimer.
   9  *     * Redistributions in binary form must reproduce the above copyright
  10  *       notice, this list of conditions and the following disclaimer in the
  11  *       documentation and/or other materials provided with the distribution.
  12  *     * Neither the name of the University of California, Berkeley nor the
  13  *       names of its contributors may be used to endorse or promote products
  14  *       derived from this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
  17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
  20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include <sys/types.h>
  29 #include <sys/stat.h>
  30 #include <sys/queue.h>
  31 #include <stdlib.h>
  32 #include <stdint.h>
  33 #include <unistd.h>
  34 #include <assert.h>
  35 #include <errno.h>
  36 #include <fcntl.h>
  37
  38 #include <ecoli_init.h>
  39 #include <ecoli_malloc.h>
  40 #include <ecoli_log.h>
  41 #include <ecoli_test.h>
  42 #include <ecoli_murmurhash.h>
  43 #include <ecoli_keyval.h>
  44
  45 #define FACTOR 3
  46
  47 EC_LOG_TYPE_REGISTER(keyval);
  48
  49 static uint32_t ec_keyval_seed;
  50
  51 struct ec_keyval_elt {
  52         LIST_ENTRY(ec_keyval_elt) next;
  53         char *key;
  54         void *val;
  55         uint32_t hash;
  56         ec_keyval_elt_free_t free;
  57 };
  58
  59 LIST_HEAD(ec_keyval_elt_list, ec_keyval_elt);
  60
  61 struct ec_keyval {
  62         size_t len;
  63         size_t table_size;
  64         struct ec_keyval_elt_list *table;
  65 };
  66
  67 struct ec_keyval *ec_keyval(void)
  68 {
  69         struct ec_keyval *keyval;
  70
  71         keyval = ec_calloc(1, sizeof(*keyval));
  72         if (keyval == NULL)
  73                 return NULL;
  74
  75         return keyval;
  76 }
  77
  78 static struct ec_keyval_elt *ec_keyval_lookup(const struct ec_keyval *keyval,
  79         const char *key)
  80 {
  81         struct ec_keyval_elt *elt;
  82         uint32_t h, mask = keyval->table_size - 1;
  83
  84         if (keyval == NULL || key == NULL) {
  85                 errno = EINVAL;
  86                 return NULL;
  87         }
  88         if (keyval->table_size == 0) {
  89                 errno = ENOENT;
  90                 return NULL;
  91         }
  92
  93         h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
  94         LIST_FOREACH(elt, &keyval->table[h & mask], next) {
  95                 if (strcmp(elt->key, key) == 0) {
  96                         errno = 0;
  97                         return elt;
  98                 }
  99         }
 100
 101         errno = ENOENT;
 102         return NULL;
 103 }
 104
 105 static void ec_keyval_elt_free(struct ec_keyval_elt *elt)
 106 {
 107         if (elt == NULL)
 108                 return;
 109
 110         ec_free(elt->key);
 111         if (elt->free != NULL)
 112                 elt->free(elt->val);
 113         ec_free(elt);
 114 }
 115
 116 bool ec_keyval_has_key(const struct ec_keyval *keyval, const char *key)
 117 {
 118         return !!ec_keyval_lookup(keyval, key);
 119 }
 120
 121 void *ec_keyval_get(const struct ec_keyval *keyval, const char *key)
 122 {
 123         struct ec_keyval_elt *elt;
 124
 125         elt = ec_keyval_lookup(keyval, key);
 126         if (elt == NULL)
 127                 return NULL;
 128
 129         return elt->val;
 130 }
 131
 132 int ec_keyval_del(struct ec_keyval *keyval, const char *key)
 133 {
 134         struct ec_keyval_elt *elt;
 135
 136         elt = ec_keyval_lookup(keyval, key);
 137         if (elt == NULL)
 138                 return -1;
 139
 140         /* we could resize table here */
 141
 142         LIST_REMOVE(elt, next);
 143         ec_keyval_elt_free(elt);
 144         keyval->len--;
 145
 146         return 0;
 147 }
 148
 149 static int ec_keyval_table_resize(struct ec_keyval *keyval, size_t new_size)
 150 {
 151         struct ec_keyval_elt_list *new_table;
 152         struct ec_keyval_elt *elt;
 153         size_t i;
 154
 155         if (new_size == 0 || (new_size & (new_size - 1))) {
 156                 errno = EINVAL;
 157                 return -1;
 158         }
 159
 160         new_table = ec_calloc(new_size, sizeof(*keyval->table));
 161         if (new_table == NULL)
 162                 return -1;
 163
 164         for (i = 0; i < keyval->table_size; i++) {
 165                 while (!LIST_EMPTY(&keyval->table[i])) {
 166                         elt = LIST_FIRST(&keyval->table[i]);
 167                         LIST_REMOVE(elt, next);
 168                         LIST_INSERT_HEAD(&new_table[elt->hash & (new_size - 1)],
 169                                         elt, next);
 170                 }
 171         }
 172
 173         ec_free(keyval->table);
 174         keyval->table = new_table;
 175         keyval->table_size = new_size;
 176
 177         return 0;
 178 }
 179
 180 int ec_keyval_set(struct ec_keyval *keyval, const char *key, void *val,
 181         ec_keyval_elt_free_t free_cb)
 182 {
 183         struct ec_keyval_elt *elt;
 184         uint32_t h, mask;
 185         size_t new_size;
 186         int ret;
 187
 188         if (keyval == NULL || key == NULL) {
 189                 errno = EINVAL;
 190                 return -1;
 191         }
 192
 193         elt = ec_keyval_lookup(keyval, key);
 194         if (elt != NULL) {
 195                 if (elt->free != NULL)
 196                         elt->free(elt->val);
 197                 elt->val = val;
 198                 elt->free = free_cb;
 199                 return 0;
 200         }
 201
 202         if (keyval->len >= keyval->table_size) {
 203                 if (keyval->table_size != 0)
 204                         new_size =  keyval->table_size << FACTOR;
 205                 else
 206                         new_size =  1 << FACTOR;
 207                 ret = ec_keyval_table_resize(keyval, new_size);
 208                 if (ret < 0)
 209                         goto fail;
 210         }
 211
 212         elt = ec_calloc(1, sizeof(*elt));
 213         if (elt == NULL)
 214                 goto fail;
 215         elt->key = ec_strdup(key);
 216         if (elt->key == NULL)
 217                 goto fail;
 218         elt->val = val;
 219         elt->free = free_cb;
 220         h = ec_murmurhash3(key, strlen(key), ec_keyval_seed);
 221         elt->hash = h;
 222
 223         mask = keyval->table_size - 1;
 224         LIST_INSERT_HEAD(&keyval->table[h & mask], elt, next);
 225         keyval->len++;
 226
 227         return 0;
 228
 229 fail:
 230         if (free_cb != NULL)
 231                 free_cb(val);
 232         if (elt != NULL) {
 233                 ec_free(elt->key);
 234                 ec_free(elt);
 235         }
 236
 237         return ret;
 238 }
 239
 240 void ec_keyval_free(struct ec_keyval *keyval)
 241 {
 242         struct ec_keyval_elt *elt;
 243         size_t i;
 244
 245         if (keyval == NULL)
 246                 return;
 247
 248         for (i = 0; i < keyval->table_size; i++) {
 249                 while (!LIST_EMPTY(&keyval->table[i])) {
 250                         elt = LIST_FIRST(&keyval->table[i]);
 251                         LIST_REMOVE(elt, next);
 252                         ec_keyval_elt_free(elt);
 253                 }
 254         }
 255         ec_free(keyval->table);
 256         ec_free(keyval);
 257 }
 258
 259 size_t ec_keyval_len(const struct ec_keyval *keyval)
 260 {
 261         return keyval->len;
 262 }
 263
 264 void ec_keyval_dump(FILE *out, const struct ec_keyval *keyval)
 265 {
 266         struct ec_keyval_elt *elt;
 267         size_t i;
 268
 269         if (keyval == NULL) {
 270                 fprintf(out, "empty keyval\n");
 271                 return;
 272         }
 273
 274         fprintf(out, "keyval:\n");
 275         for (i = 0; i < keyval->table_size; i++) {
 276                 LIST_FOREACH(elt, &keyval->table[i], next) {
 277                         fprintf(out, "  %s: %p\n",
 278                                 elt->key, elt->val);
 279                 }
 280         }
 281 }
 282
 283 static int ec_keyval_init_func(void)
 284 {
 285         int fd;
 286         ssize_t ret;
 287
 288         fd = open("/dev/urandom", 0);
 289         if (fd == -1) {
 290                 fprintf(stderr, "failed to open /dev/urandom\n");
 291                 return -1;
 292         }
 293         ret = read(fd, &ec_keyval_seed, sizeof(ec_keyval_seed));
 294         if (ret != sizeof(ec_keyval_seed)) {
 295                 fprintf(stderr, "failed to read /dev/urandom\n");
 296                 return -1;
 297         }
 298         close(fd);
 299         return 0;
 300 }
 301
 302 static struct ec_init ec_keyval_init = {
 303         .init = ec_keyval_init_func,
 304         .priority = 50,
 305 };
 306
 307 EC_INIT_REGISTER(ec_keyval_init);
 308
 309 /* LCOV_EXCL_START */
 310 static int ec_keyval_testcase(void)
 311 {
 312         struct ec_keyval *keyval;
 313         char *val;
 314         size_t i;
 315         int ret;
 316
 317         keyval = ec_keyval();
 318         if (keyval == NULL) {
 319                 EC_LOG(EC_LOG_ERR, "cannot create keyval\n");
 320                 return -1;
 321         }
 322
 323         EC_TEST_ASSERT(ec_keyval_len(keyval) == 0);
 324         ret = ec_keyval_set(keyval, "key1", "val1", NULL);
 325         EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
 326         ret = ec_keyval_set(keyval, "key2", ec_strdup("val2"), ec_free_func);
 327         EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
 328         EC_TEST_ASSERT(ec_keyval_len(keyval) == 2);
 329
 330         val = ec_keyval_get(keyval, "key1");
 331         EC_TEST_ASSERT(val != NULL && !strcmp(val, "val1"));
 332         val = ec_keyval_get(keyval, "key2");
 333         EC_TEST_ASSERT(val != NULL && !strcmp(val, "val2"));
 334         val = ec_keyval_get(keyval, "key3");
 335         EC_TEST_ASSERT(val == NULL);
 336
 337         ret = ec_keyval_set(keyval, "key1", "another_val1", NULL);
 338         EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
 339         ret = ec_keyval_set(keyval, "key2", ec_strdup("another_val2"),
 340                         ec_free_func);
 341         EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
 342         EC_TEST_ASSERT(ec_keyval_len(keyval) == 2);
 343
 344         val = ec_keyval_get(keyval, "key1");
 345         EC_TEST_ASSERT(val != NULL && !strcmp(val, "another_val1"));
 346         val = ec_keyval_get(keyval, "key2");
 347         EC_TEST_ASSERT(val != NULL && !strcmp(val, "another_val2"));
 348         EC_TEST_ASSERT(ec_keyval_has_key(keyval, "key1"));
 349
 350         ret = ec_keyval_del(keyval, "key1");
 351         EC_TEST_ASSERT_STR(ret == 0, "cannot del key");
 352         EC_TEST_ASSERT(ec_keyval_len(keyval) == 1);
 353
 354         ec_keyval_dump(stdout, NULL);
 355         ec_keyval_dump(stdout, keyval);
 356
 357         for (i = 0; i < 100; i++) {
 358                 char buf[8];
 359                 snprintf(buf, sizeof(buf), "k%zd", i);
 360                 ret = ec_keyval_set(keyval, buf, "val", NULL);
 361                 EC_TEST_ASSERT_STR(ret == 0, "cannot set key");
 362         }
 363
 364         /* einval */
 365         ret = ec_keyval_set(keyval, NULL, "val1", NULL);
 366         EC_TEST_ASSERT(ret == -1);
 367         val = ec_keyval_get(keyval, NULL);
 368         EC_TEST_ASSERT(val == NULL);
 369
 370         ec_keyval_free(keyval);
 371
 372
 373         return 0;
 374 }
 375 /* LCOV_EXCL_STOP */
 376
 377 static struct ec_test ec_keyval_test = {
 378         .name = "keyval",
 379         .test = ec_keyval_testcase,
 380 };
 381
 382 EC_TEST_REGISTER(ec_keyval_test);