contrib/libucl/src/ucl_hash.c

   1 /* Copyright (c) 2013, Vsevolod Stakhov
   2  * All rights reserved.
   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  *       * Redistributions of source code must retain the above copyright
   7  *         notice, this list of conditions and the following disclaimer.
   8  *       * Redistributions in binary form must reproduce the above copyright
   9  *         notice, this list of conditions and the following disclaimer in the
  10  *         documentation and/or other materials provided with the distribution.
  11  *
  12  * THIS SOFTWARE IS PROVIDED ''AS IS'' AND ANY
  13  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  14  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  15  * DISCLAIMED. IN NO EVENT SHALL AUTHOR BE LIABLE FOR ANY
  16  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  17  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  18  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  19  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  20  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  21  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  22  */
  23
  24 #include "ucl_internal.h"
  25 #include "ucl_hash.h"
  26 #include "khash.h"
  27 #include "kvec.h"
  28
  29 struct ucl_hash_elt {
  30         const ucl_object_t *obj;
  31         size_t ar_idx;
  32 };
  33
  34 struct ucl_hash_struct {
  35         void *hash;
  36         kvec_t(const ucl_object_t *) ar;
  37         bool caseless;
  38 };
  39
  40 static inline uint32_t
  41 ucl_hash_func (const ucl_object_t *o)
  42 {
  43         return XXH32 (o->key, o->keylen, 0xdeadbeef);
  44 }
  45
  46 static inline int
  47 ucl_hash_equal (const ucl_object_t *k1, const ucl_object_t *k2)
  48 {
  49         if (k1->keylen == k2->keylen) {
  50                 return strncmp (k1->key, k2->key, k1->keylen) == 0;
  51         }
  52
  53         return 0;
  54 }
  55
  56 KHASH_INIT (ucl_hash_node, const ucl_object_t *, struct ucl_hash_elt, 1,
  57                 ucl_hash_func, ucl_hash_equal)
  58
  59 static inline uint32_t
  60 ucl_hash_caseless_func (const ucl_object_t *o)
  61 {
  62         void *xxh = XXH32_init (0xdeadbeef);
  63         char hash_buf[64], *c;
  64         const char *p;
  65         ssize_t remain = o->keylen;
  66
  67         p = o->key;
  68         c = &hash_buf[0];
  69
  70         while (remain > 0) {
  71                 *c++ = tolower (*p++);
  72
  73                 if (c - &hash_buf[0] == sizeof (hash_buf)) {
  74                         XXH32_update (xxh, hash_buf, sizeof (hash_buf));
  75                         c = &hash_buf[0];
  76                 }
  77                 remain --;
  78         }
  79
  80         if (c - &hash_buf[0] != 0) {
  81                 XXH32_update (xxh, hash_buf, c - &hash_buf[0]);
  82         }
  83
  84         return XXH32_digest (xxh);
  85 }
  86
  87 static inline int
  88 ucl_hash_caseless_equal (const ucl_object_t *k1, const ucl_object_t *k2)
  89 {
  90         if (k1->keylen == k2->keylen) {
  91                 return strncasecmp (k1->key, k2->key, k1->keylen) == 0;
  92         }
  93
  94         return 0;
  95 }
  96
  97 KHASH_INIT (ucl_hash_caseless_node, const ucl_object_t *, struct ucl_hash_elt, 1,
  98                 ucl_hash_caseless_func, ucl_hash_caseless_equal)
  99
 100 ucl_hash_t*
 101 ucl_hash_create (bool ignore_case)
 102 {
 103         ucl_hash_t *new;
 104
 105         new = UCL_ALLOC (sizeof (ucl_hash_t));
 106         if (new != NULL) {
 107                 kv_init (new->ar);
 108
 109                 new->caseless = ignore_case;
 110                 if (ignore_case) {
 111                         khash_t(ucl_hash_caseless_node) *h = kh_init (ucl_hash_caseless_node);
 112                         new->hash = (void *)h;
 113                 }
 114                 else {
 115                         khash_t(ucl_hash_node) *h = kh_init (ucl_hash_node);
 116                         new->hash = (void *)h;
 117                 }
 118         }
 119         return new;
 120 }
 121
 122 void ucl_hash_destroy (ucl_hash_t* hashlin, ucl_hash_free_func *func)
 123 {
 124         const ucl_object_t *cur, *tmp;
 125
 126         if (hashlin == NULL) {
 127                 return;
 128         }
 129
 130         if (func != NULL) {
 131                 /* Iterate over the hash first */
 132                 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
 133                                 hashlin->hash;
 134                 khiter_t k;
 135
 136                 for (k = kh_begin (h); k != kh_end (h); ++k) {
 137                         if (kh_exist (h, k)) {
 138                                 cur = (kh_value (h, k)).obj;
 139                                 while (cur != NULL) {
 140                                         tmp = cur->next;
 141                                         func (__DECONST (ucl_object_t *, cur));
 142                                         cur = tmp;
 143                                 }
 144                         }
 145                 }
 146         }
 147
 148         if (hashlin->caseless) {
 149                 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *)
 150                         hashlin->hash;
 151                 kh_destroy (ucl_hash_caseless_node, h);
 152         }
 153         else {
 154                 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
 155                         hashlin->hash;
 156                 kh_destroy (ucl_hash_node, h);
 157         }
 158
 159         kv_destroy (hashlin->ar);
 160         UCL_FREE (sizeof (*hashlin), hashlin);
 161 }
 162
 163 void
 164 ucl_hash_insert (ucl_hash_t* hashlin, const ucl_object_t *obj,
 165                 const char *key, unsigned keylen)
 166 {
 167         khiter_t k;
 168         int ret;
 169         struct ucl_hash_elt *elt;
 170
 171         if (hashlin == NULL) {
 172                 return;
 173         }
 174
 175         if (hashlin->caseless) {
 176                 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *)
 177                                 hashlin->hash;
 178                 k = kh_put (ucl_hash_caseless_node, h, obj, &ret);
 179                 if (ret > 0) {
 180                         elt = &kh_value (h, k);
 181                         kv_push (const ucl_object_t *, hashlin->ar, obj);
 182                         elt->obj = obj;
 183                         elt->ar_idx = kv_size (hashlin->ar) - 1;
 184                 }
 185         }
 186         else {
 187                 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
 188                                 hashlin->hash;
 189                 k = kh_put (ucl_hash_node, h, obj, &ret);
 190                 if (ret > 0) {
 191                         elt = &kh_value (h, k);
 192                         kv_push (const ucl_object_t *, hashlin->ar, obj);
 193                         elt->obj = obj;
 194                         elt->ar_idx = kv_size (hashlin->ar) - 1;
 195                 }
 196         }
 197 }
 198
 199 void ucl_hash_replace (ucl_hash_t* hashlin, const ucl_object_t *old,
 200                 const ucl_object_t *new)
 201 {
 202         khiter_t k;
 203         int ret;
 204         struct ucl_hash_elt elt, *pelt;
 205
 206         if (hashlin == NULL) {
 207                 return;
 208         }
 209
 210         if (hashlin->caseless) {
 211                 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *)
 212                                 hashlin->hash;
 213                 k = kh_put (ucl_hash_caseless_node, h, old, &ret);
 214                 if (ret == 0) {
 215                         elt = kh_value (h, k);
 216                         kh_del (ucl_hash_caseless_node, h, k);
 217                         k = kh_put (ucl_hash_caseless_node, h, new, &ret);
 218                         pelt = &kh_value (h, k);
 219                         pelt->obj = new;
 220                         pelt->ar_idx = elt.ar_idx;
 221                         kv_A (hashlin->ar, elt.ar_idx) = new;
 222                 }
 223         }
 224         else {
 225                 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
 226                                 hashlin->hash;
 227                 k = kh_put (ucl_hash_node, h, old, &ret);
 228                 if (ret == 0) {
 229                         elt = kh_value (h, k);
 230                         kh_del (ucl_hash_node, h, k);
 231                         k = kh_put (ucl_hash_node, h, new, &ret);
 232                         pelt = &kh_value (h, k);
 233                         pelt->obj = new;
 234                         pelt->ar_idx = elt.ar_idx;
 235                         kv_A (hashlin->ar, elt.ar_idx) = new;
 236                 }
 237         }
 238 }
 239
 240 struct ucl_hash_real_iter {
 241         const ucl_object_t **cur;
 242         const ucl_object_t **end;
 243 };
 244
 245 const void*
 246 ucl_hash_iterate (ucl_hash_t *hashlin, ucl_hash_iter_t *iter)
 247 {
 248         struct ucl_hash_real_iter *it = (struct ucl_hash_real_iter *)(*iter);
 249         const ucl_object_t *ret = NULL;
 250
 251         if (hashlin == NULL) {
 252                 return NULL;
 253         }
 254
 255         if (it == NULL) {
 256                 it = UCL_ALLOC (sizeof (*it));
 257                 it->cur = &hashlin->ar.a[0];
 258                 it->end = it->cur + hashlin->ar.n;
 259         }
 260
 261         if (it->cur < it->end) {
 262                 ret = *it->cur++;
 263         }
 264         else {
 265                 UCL_FREE (sizeof (*it), it);
 266                 *iter = NULL;
 267                 return NULL;
 268         }
 269
 270         *iter = it;
 271
 272         return ret;
 273 }
 274
 275 bool
 276 ucl_hash_iter_has_next (ucl_hash_t *hashlin, ucl_hash_iter_t iter)
 277 {
 278         struct ucl_hash_real_iter *it = (struct ucl_hash_real_iter *)(iter);
 279
 280         return it->cur < it->end - 1;
 281 }
 282
 283
 284 const ucl_object_t*
 285 ucl_hash_search (ucl_hash_t* hashlin, const char *key, unsigned keylen)
 286 {
 287         khiter_t k;
 288         const ucl_object_t *ret = NULL;
 289         ucl_object_t search;
 290         struct ucl_hash_elt *elt;
 291
 292         search.key = key;
 293         search.keylen = keylen;
 294
 295         if (hashlin == NULL) {
 296                 return NULL;
 297         }
 298
 299         if (hashlin->caseless) {
 300                 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *)
 301                                                 hashlin->hash;
 302
 303                 k = kh_get (ucl_hash_caseless_node, h, &search);
 304                 if (k != kh_end (h)) {
 305                         elt = &kh_value (h, k);
 306                         ret = elt->obj;
 307                 }
 308         }
 309         else {
 310                 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
 311                                                 hashlin->hash;
 312                 k = kh_get (ucl_hash_node, h, &search);
 313                 if (k != kh_end (h)) {
 314                         elt = &kh_value (h, k);
 315                         ret = elt->obj;
 316                 }
 317         }
 318
 319         return ret;
 320 }
 321
 322 void
 323 ucl_hash_delete (ucl_hash_t* hashlin, const ucl_object_t *obj)
 324 {
 325         khiter_t k;
 326         struct ucl_hash_elt *elt;
 327
 328         if (hashlin == NULL) {
 329                 return;
 330         }
 331
 332         if (hashlin->caseless) {
 333                 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *)
 334                         hashlin->hash;
 335
 336                 k = kh_get (ucl_hash_caseless_node, h, obj);
 337                 if (k != kh_end (h)) {
 338                         elt = &kh_value (h, k);
 339                         kv_A (hashlin->ar, elt->ar_idx) = NULL;
 340                         kh_del (ucl_hash_caseless_node, h, k);
 341                 }
 342         }
 343         else {
 344                 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
 345                         hashlin->hash;
 346                 k = kh_get (ucl_hash_node, h, obj);
 347                 if (k != kh_end (h)) {
 348                         elt = &kh_value (h, k);
 349                         kv_A (hashlin->ar, elt->ar_idx) = NULL;
 350                         kh_del (ucl_hash_node, h, k);
 351                 }
 352         }
 353 }