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 } 354