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 #include <time.h> 30 #include <limits.h> 31 32 struct ucl_hash_elt { 33 const ucl_object_t *obj; 34 size_t ar_idx; 35 }; 36 37 struct ucl_hash_struct { 38 void *hash; 39 kvec_t(const ucl_object_t *) ar; 40 bool caseless; 41 }; 42 43 static uint64_t 44 ucl_hash_seed (void) 45 { 46 static uint64_t seed; 47 48 if (seed == 0) { 49 #ifdef UCL_RANDOM_FUNCTION 50 seed = UCL_RANDOM_FUNCTION; 51 #else 52 /* Not very random but can be useful for our purposes */ 53 seed = time (NULL); 54 #endif 55 } 56 57 return seed; 58 } 59 60 static const unsigned char lc_map[256] = { 61 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 62 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 63 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 64 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 65 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 66 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 67 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 68 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 69 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 70 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 71 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 72 0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 73 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 74 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 75 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 76 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 77 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 78 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f, 79 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 80 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 81 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 82 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 83 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 84 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 85 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 86 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 87 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 88 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf, 89 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 90 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 91 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 92 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff 93 }; 94 95 #if (defined(WORD_BIT) && WORD_BIT == 64) || \ 96 (defined(__WORDSIZE) && __WORDSIZE == 64) || \ 97 defined(__x86_64__) || \ 98 defined(__amd64__) 99 #define UCL64_BIT_HASH 1 100 #endif 101 102 #ifdef UCL64_BIT_HASH 103 static inline uint32_t 104 ucl_hash_func (const ucl_object_t *o) 105 { 106 return XXH64 (o->key, o->keylen, ucl_hash_seed ()); 107 } 108 #else 109 static inline uint32_t 110 ucl_hash_func (const ucl_object_t *o) 111 { 112 return XXH32 (o->key, o->keylen, ucl_hash_seed ()); 113 } 114 #endif 115 116 static inline int 117 ucl_hash_equal (const ucl_object_t *k1, const ucl_object_t *k2) 118 { 119 if (k1->keylen == k2->keylen) { 120 return strncmp (k1->key, k2->key, k1->keylen) == 0; 121 } 122 123 return 0; 124 } 125 126 KHASH_INIT (ucl_hash_node, const ucl_object_t *, struct ucl_hash_elt, 1, 127 ucl_hash_func, ucl_hash_equal) 128 129 #ifdef UCL64_BIT_HASH 130 static inline uint32_t 131 ucl_hash_caseless_func (const ucl_object_t *o) 132 { 133 unsigned len = o->keylen; 134 unsigned leftover = o->keylen % 4; 135 unsigned fp, i; 136 const uint8_t* s = (const uint8_t*)o->key; 137 union { 138 struct { 139 unsigned char c1, c2, c3, c4; 140 } c; 141 uint32_t pp; 142 } u; 143 XXH64_state_t st; 144 145 fp = len - leftover; 146 XXH64_reset (&st, ucl_hash_seed ()); 147 148 for (i = 0; i != fp; i += 4) { 149 u.c.c1 = s[i], u.c.c2 = s[i + 1], u.c.c3 = s[i + 2], u.c.c4 = s[i + 3]; 150 u.c.c1 = lc_map[u.c.c1]; 151 u.c.c2 = lc_map[u.c.c2]; 152 u.c.c3 = lc_map[u.c.c3]; 153 u.c.c4 = lc_map[u.c.c4]; 154 XXH64_update (&st, &u.pp, sizeof (u)); 155 } 156 157 u.pp = 0; 158 switch (leftover) { 159 case 3: 160 u.c.c3 = lc_map[(unsigned char)s[i++]]; 161 case 2: 162 u.c.c2 = lc_map[(unsigned char)s[i++]]; 163 case 1: 164 u.c.c1 = lc_map[(unsigned char)s[i]]; 165 XXH64_update (&st, &u.pp, leftover); 166 break; 167 } 168 169 return XXH64_digest (&st); 170 } 171 #else 172 static inline uint32_t 173 ucl_hash_caseless_func (const ucl_object_t *o) 174 { 175 unsigned len = o->keylen; 176 unsigned leftover = o->keylen % 4; 177 unsigned fp, i; 178 const uint8_t* s = (const uint8_t*)o->key; 179 union { 180 struct { 181 unsigned char c1, c2, c3, c4; 182 } c; 183 uint32_t pp; 184 } u; 185 XXH32_state_t st; 186 187 fp = len - leftover; 188 XXH32_reset (&st, ucl_hash_seed ()); 189 190 for (i = 0; i != fp; i += 4) { 191 u.c.c1 = s[i], u.c.c2 = s[i + 1], u.c.c3 = s[i + 2], u.c.c4 = s[i + 3]; 192 u.c.c1 = lc_map[u.c.c1]; 193 u.c.c2 = lc_map[u.c.c2]; 194 u.c.c3 = lc_map[u.c.c3]; 195 u.c.c4 = lc_map[u.c.c4]; 196 XXH32_update (&st, &u.pp, sizeof (u)); 197 } 198 199 u.pp = 0; 200 switch (leftover) { 201 case 3: 202 u.c.c3 = lc_map[(unsigned char)s[i++]]; 203 case 2: 204 u.c.c2 = lc_map[(unsigned char)s[i++]]; 205 case 1: 206 u.c.c1 = lc_map[(unsigned char)s[i]]; 207 XXH32_update (&st, &u.pp, leftover); 208 break; 209 } 210 211 return XXH32_digest (&st); 212 } 213 #endif 214 215 static inline int 216 ucl_hash_caseless_equal (const ucl_object_t *k1, const ucl_object_t *k2) 217 { 218 if (k1->keylen == k2->keylen) { 219 return strncasecmp (k1->key, k2->key, k1->keylen) == 0; 220 } 221 222 return 0; 223 } 224 225 KHASH_INIT (ucl_hash_caseless_node, const ucl_object_t *, struct ucl_hash_elt, 1, 226 ucl_hash_caseless_func, ucl_hash_caseless_equal) 227 228 ucl_hash_t* 229 ucl_hash_create (bool ignore_case) 230 { 231 ucl_hash_t *new; 232 233 new = UCL_ALLOC (sizeof (ucl_hash_t)); 234 if (new != NULL) { 235 kv_init (new->ar); 236 237 new->caseless = ignore_case; 238 if (ignore_case) { 239 khash_t(ucl_hash_caseless_node) *h = kh_init (ucl_hash_caseless_node); 240 new->hash = (void *)h; 241 } 242 else { 243 khash_t(ucl_hash_node) *h = kh_init (ucl_hash_node); 244 new->hash = (void *)h; 245 } 246 } 247 return new; 248 } 249 250 void ucl_hash_destroy (ucl_hash_t* hashlin, ucl_hash_free_func *func) 251 { 252 const ucl_object_t *cur, *tmp; 253 254 if (hashlin == NULL) { 255 return; 256 } 257 258 if (func != NULL) { 259 /* Iterate over the hash first */ 260 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *) 261 hashlin->hash; 262 khiter_t k; 263 264 for (k = kh_begin (h); k != kh_end (h); ++k) { 265 if (kh_exist (h, k)) { 266 cur = (kh_value (h, k)).obj; 267 while (cur != NULL) { 268 tmp = cur->next; 269 func (__DECONST (ucl_object_t *, cur)); 270 cur = tmp; 271 } 272 } 273 } 274 } 275 276 if (hashlin->caseless) { 277 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *) 278 hashlin->hash; 279 kh_destroy (ucl_hash_caseless_node, h); 280 } 281 else { 282 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *) 283 hashlin->hash; 284 kh_destroy (ucl_hash_node, h); 285 } 286 287 kv_destroy (hashlin->ar); 288 UCL_FREE (sizeof (*hashlin), hashlin); 289 } 290 291 void 292 ucl_hash_insert (ucl_hash_t* hashlin, const ucl_object_t *obj, 293 const char *key, unsigned keylen) 294 { 295 khiter_t k; 296 int ret; 297 struct ucl_hash_elt *elt; 298 299 if (hashlin == NULL) { 300 return; 301 } 302 303 if (hashlin->caseless) { 304 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *) 305 hashlin->hash; 306 k = kh_put (ucl_hash_caseless_node, h, obj, &ret); 307 if (ret > 0) { 308 elt = &kh_value (h, k); 309 kv_push (const ucl_object_t *, hashlin->ar, obj); 310 elt->obj = obj; 311 elt->ar_idx = kv_size (hashlin->ar) - 1; 312 } 313 } 314 else { 315 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *) 316 hashlin->hash; 317 k = kh_put (ucl_hash_node, h, obj, &ret); 318 if (ret > 0) { 319 elt = &kh_value (h, k); 320 kv_push (const ucl_object_t *, hashlin->ar, obj); 321 elt->obj = obj; 322 elt->ar_idx = kv_size (hashlin->ar) - 1; 323 } 324 } 325 } 326 327 void ucl_hash_replace (ucl_hash_t* hashlin, const ucl_object_t *old, 328 const ucl_object_t *new) 329 { 330 khiter_t k; 331 int ret; 332 struct ucl_hash_elt elt, *pelt; 333 334 if (hashlin == NULL) { 335 return; 336 } 337 338 if (hashlin->caseless) { 339 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *) 340 hashlin->hash; 341 k = kh_put (ucl_hash_caseless_node, h, old, &ret); 342 if (ret == 0) { 343 elt = kh_value (h, k); 344 kh_del (ucl_hash_caseless_node, h, k); 345 k = kh_put (ucl_hash_caseless_node, h, new, &ret); 346 pelt = &kh_value (h, k); 347 pelt->obj = new; 348 pelt->ar_idx = elt.ar_idx; 349 kv_A (hashlin->ar, elt.ar_idx) = new; 350 } 351 } 352 else { 353 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *) 354 hashlin->hash; 355 k = kh_put (ucl_hash_node, h, old, &ret); 356 if (ret == 0) { 357 elt = kh_value (h, k); 358 kh_del (ucl_hash_node, h, k); 359 k = kh_put (ucl_hash_node, h, new, &ret); 360 pelt = &kh_value (h, k); 361 pelt->obj = new; 362 pelt->ar_idx = elt.ar_idx; 363 kv_A (hashlin->ar, elt.ar_idx) = new; 364 } 365 } 366 } 367 368 struct ucl_hash_real_iter { 369 const ucl_object_t **cur; 370 const ucl_object_t **end; 371 }; 372 373 const void* 374 ucl_hash_iterate (ucl_hash_t *hashlin, ucl_hash_iter_t *iter) 375 { 376 struct ucl_hash_real_iter *it = (struct ucl_hash_real_iter *)(*iter); 377 const ucl_object_t *ret = NULL; 378 379 if (hashlin == NULL) { 380 return NULL; 381 } 382 383 if (it == NULL) { 384 it = UCL_ALLOC (sizeof (*it)); 385 386 if (it == NULL) { 387 return NULL; 388 } 389 390 it->cur = &hashlin->ar.a[0]; 391 it->end = it->cur + hashlin->ar.n; 392 } 393 394 if (it->cur < it->end) { 395 ret = *it->cur++; 396 } 397 else { 398 UCL_FREE (sizeof (*it), it); 399 *iter = NULL; 400 return NULL; 401 } 402 403 *iter = it; 404 405 return ret; 406 } 407 408 bool 409 ucl_hash_iter_has_next (ucl_hash_t *hashlin, ucl_hash_iter_t iter) 410 { 411 struct ucl_hash_real_iter *it = (struct ucl_hash_real_iter *)(iter); 412 413 return it->cur < it->end - 1; 414 } 415 416 417 const ucl_object_t* 418 ucl_hash_search (ucl_hash_t* hashlin, const char *key, unsigned keylen) 419 { 420 khiter_t k; 421 const ucl_object_t *ret = NULL; 422 ucl_object_t search; 423 struct ucl_hash_elt *elt; 424 425 search.key = key; 426 search.keylen = keylen; 427 428 if (hashlin == NULL) { 429 return NULL; 430 } 431 432 if (hashlin->caseless) { 433 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *) 434 hashlin->hash; 435 436 k = kh_get (ucl_hash_caseless_node, h, &search); 437 if (k != kh_end (h)) { 438 elt = &kh_value (h, k); 439 ret = elt->obj; 440 } 441 } 442 else { 443 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *) 444 hashlin->hash; 445 k = kh_get (ucl_hash_node, h, &search); 446 if (k != kh_end (h)) { 447 elt = &kh_value (h, k); 448 ret = elt->obj; 449 } 450 } 451 452 return ret; 453 } 454 455 void 456 ucl_hash_delete (ucl_hash_t* hashlin, const ucl_object_t *obj) 457 { 458 khiter_t k; 459 struct ucl_hash_elt *elt; 460 461 if (hashlin == NULL) { 462 return; 463 } 464 465 if (hashlin->caseless) { 466 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *) 467 hashlin->hash; 468 469 k = kh_get (ucl_hash_caseless_node, h, obj); 470 if (k != kh_end (h)) { 471 elt = &kh_value (h, k); 472 kv_del (const ucl_object_t *, hashlin->ar, elt->ar_idx); 473 kh_del (ucl_hash_caseless_node, h, k); 474 } 475 } 476 else { 477 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *) 478 hashlin->hash; 479 k = kh_get (ucl_hash_node, h, obj); 480 if (k != kh_end (h)) { 481 elt = &kh_value (h, k); 482 kv_del (const ucl_object_t *, hashlin->ar, elt->ar_idx); 483 kh_del (ucl_hash_node, h, k); 484 } 485 } 486 } 487