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 #include "mum.h" 29 30 #include <time.h> 31 #include <limits.h> 32 33 struct ucl_hash_elt { 34 const ucl_object_t *obj; 35 size_t ar_idx; 36 }; 37 38 struct ucl_hash_struct { 39 void *hash; 40 kvec_t(const ucl_object_t *) ar; 41 bool caseless; 42 }; 43 44 static uint64_t 45 ucl_hash_seed (void) 46 { 47 static uint64_t seed; 48 49 if (seed == 0) { 50 #ifdef UCL_RANDOM_FUNCTION 51 seed = UCL_RANDOM_FUNCTION; 52 #else 53 /* Not very random but can be useful for our purposes */ 54 seed = time (NULL); 55 #endif 56 } 57 58 return seed; 59 } 60 61 static const unsigned char lc_map[256] = { 62 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 63 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 64 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 65 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 66 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 67 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f, 68 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 69 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f, 70 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 71 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 72 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 73 0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, 74 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, 75 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, 76 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, 77 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f, 78 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 79 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f, 80 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97, 81 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f, 82 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7, 83 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf, 84 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7, 85 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 86 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 87 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf, 88 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7, 89 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf, 90 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7, 91 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef, 92 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7, 93 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff 94 }; 95 96 #if (defined(WORD_BIT) && WORD_BIT == 64) || \ 97 (defined(__WORDSIZE) && __WORDSIZE == 64) || \ 98 defined(__x86_64__) || \ 99 defined(__amd64__) 100 #define UCL64_BIT_HASH 1 101 #endif 102 103 static inline uint32_t 104 ucl_hash_func (const ucl_object_t *o) 105 { 106 return mum_hash (o->key, o->keylen, ucl_hash_seed ()); 107 } 108 static inline int 109 ucl_hash_equal (const ucl_object_t *k1, const ucl_object_t *k2) 110 { 111 if (k1->keylen == k2->keylen) { 112 return memcmp (k1->key, k2->key, k1->keylen) == 0; 113 } 114 115 return 0; 116 } 117 118 KHASH_INIT (ucl_hash_node, const ucl_object_t *, struct ucl_hash_elt, 1, 119 ucl_hash_func, ucl_hash_equal) 120 121 static inline uint32_t 122 ucl_hash_caseless_func (const ucl_object_t *o) 123 { 124 unsigned len = o->keylen; 125 unsigned leftover = o->keylen % 8; 126 unsigned fp, i; 127 const uint8_t* s = (const uint8_t*)o->key; 128 union { 129 struct { 130 unsigned char c1, c2, c3, c4, c5, c6, c7, c8; 131 } c; 132 uint64_t pp; 133 } u; 134 uint64_t r; 135 136 fp = len - leftover; 137 r = ucl_hash_seed (); 138 139 for (i = 0; i != fp; i += 8) { 140 u.c.c1 = s[i], u.c.c2 = s[i + 1], u.c.c3 = s[i + 2], u.c.c4 = s[i + 3]; 141 u.c.c5 = s[i + 4], u.c.c6 = s[i + 5], u.c.c7 = s[i + 6], u.c.c8 = s[i + 7]; 142 u.c.c1 = lc_map[u.c.c1]; 143 u.c.c2 = lc_map[u.c.c2]; 144 u.c.c3 = lc_map[u.c.c3]; 145 u.c.c4 = lc_map[u.c.c4]; 146 u.c.c5 = lc_map[u.c.c5]; 147 u.c.c6 = lc_map[u.c.c6]; 148 u.c.c7 = lc_map[u.c.c7]; 149 u.c.c8 = lc_map[u.c.c8]; 150 r = mum_hash_step (r, u.pp); 151 } 152 153 u.pp = 0; 154 switch (leftover) { 155 case 7: 156 u.c.c7 = lc_map[(unsigned char)s[i++]]; 157 /* FALLTHRU */ 158 case 6: 159 u.c.c6 = lc_map[(unsigned char)s[i++]]; 160 /* FALLTHRU */ 161 case 5: 162 u.c.c5 = lc_map[(unsigned char)s[i++]]; 163 /* FALLTHRU */ 164 case 4: 165 u.c.c4 = lc_map[(unsigned char)s[i++]]; 166 /* FALLTHRU */ 167 case 3: 168 u.c.c3 = lc_map[(unsigned char)s[i++]]; 169 /* FALLTHRU */ 170 case 2: 171 u.c.c2 = lc_map[(unsigned char)s[i++]]; 172 /* FALLTHRU */ 173 case 1: 174 u.c.c1 = lc_map[(unsigned char)s[i]]; 175 r = mum_hash_step (r, u.pp); 176 break; 177 } 178 179 return mum_hash_finish (r); 180 } 181 182 static inline int 183 ucl_hash_caseless_equal (const ucl_object_t *k1, const ucl_object_t *k2) 184 { 185 if (k1->keylen == k2->keylen) { 186 unsigned fp, i; 187 const char *s = k1->key, *d = k2->key; 188 unsigned char c1, c2, c3, c4; 189 union { 190 unsigned char c[4]; 191 uint32_t n; 192 } cmp1, cmp2; 193 size_t leftover = k1->keylen % 4; 194 195 fp = k1->keylen - leftover; 196 197 for (i = 0; i != fp; i += 4) { 198 c1 = s[i], c2 = s[i + 1], c3 = s[i + 2], c4 = s[i + 3]; 199 cmp1.c[0] = lc_map[c1]; 200 cmp1.c[1] = lc_map[c2]; 201 cmp1.c[2] = lc_map[c3]; 202 cmp1.c[3] = lc_map[c4]; 203 204 c1 = d[i], c2 = d[i + 1], c3 = d[i + 2], c4 = d[i + 3]; 205 cmp2.c[0] = lc_map[c1]; 206 cmp2.c[1] = lc_map[c2]; 207 cmp2.c[2] = lc_map[c3]; 208 cmp2.c[3] = lc_map[c4]; 209 210 if (cmp1.n != cmp2.n) { 211 return 0; 212 } 213 } 214 215 while (leftover > 0) { 216 if (lc_map[(unsigned char)s[i]] != lc_map[(unsigned char)d[i]]) { 217 return 0; 218 } 219 220 leftover--; 221 i++; 222 } 223 224 return 1; 225 } 226 227 return 0; 228 } 229 230 KHASH_INIT (ucl_hash_caseless_node, const ucl_object_t *, struct ucl_hash_elt, 1, 231 ucl_hash_caseless_func, ucl_hash_caseless_equal) 232 233 ucl_hash_t* 234 ucl_hash_create (bool ignore_case) 235 { 236 ucl_hash_t *new; 237 238 new = UCL_ALLOC (sizeof (ucl_hash_t)); 239 if (new != NULL) { 240 void *h; 241 kv_init (new->ar); 242 243 new->caseless = ignore_case; 244 if (ignore_case) { 245 h = (void *)kh_init (ucl_hash_caseless_node); 246 } 247 else { 248 h = (void *)kh_init (ucl_hash_node); 249 } 250 if (h == NULL) { 251 UCL_FREE (sizeof (ucl_hash_t), new); 252 return NULL; 253 } 254 new->hash = h; 255 } 256 return new; 257 } 258 259 void ucl_hash_destroy (ucl_hash_t* hashlin, ucl_hash_free_func func) 260 { 261 const ucl_object_t *cur, *tmp; 262 263 if (hashlin == NULL) { 264 return; 265 } 266 267 if (func != NULL) { 268 /* Iterate over the hash first */ 269 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *) 270 hashlin->hash; 271 khiter_t k; 272 273 for (k = kh_begin (h); k != kh_end (h); ++k) { 274 if (kh_exist (h, k)) { 275 cur = (kh_value (h, k)).obj; 276 while (cur != NULL) { 277 tmp = cur->next; 278 func (__DECONST (ucl_object_t *, cur)); 279 cur = tmp; 280 } 281 } 282 } 283 } 284 285 if (hashlin->caseless) { 286 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *) 287 hashlin->hash; 288 kh_destroy (ucl_hash_caseless_node, h); 289 } 290 else { 291 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *) 292 hashlin->hash; 293 kh_destroy (ucl_hash_node, h); 294 } 295 296 kv_destroy (hashlin->ar); 297 UCL_FREE (sizeof (*hashlin), hashlin); 298 } 299 300 bool 301 ucl_hash_insert (ucl_hash_t* hashlin, const ucl_object_t *obj, 302 const char *key, unsigned keylen) 303 { 304 khiter_t k; 305 int ret; 306 struct ucl_hash_elt *elt; 307 308 if (hashlin == NULL) { 309 return false; 310 } 311 312 if (hashlin->caseless) { 313 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *) 314 hashlin->hash; 315 k = kh_put (ucl_hash_caseless_node, h, obj, &ret); 316 if (ret > 0) { 317 elt = &kh_value (h, k); 318 kv_push_safe (const ucl_object_t *, hashlin->ar, obj, e0); 319 elt->obj = obj; 320 elt->ar_idx = kv_size (hashlin->ar) - 1; 321 } 322 } 323 else { 324 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *) 325 hashlin->hash; 326 k = kh_put (ucl_hash_node, h, obj, &ret); 327 if (ret > 0) { 328 elt = &kh_value (h, k); 329 kv_push_safe (const ucl_object_t *, hashlin->ar, obj, e0); 330 elt->obj = obj; 331 elt->ar_idx = kv_size (hashlin->ar) - 1; 332 } else if (ret < 0) { 333 goto e0; 334 } 335 } 336 return true; 337 e0: 338 return false; 339 } 340 341 void ucl_hash_replace (ucl_hash_t* hashlin, const ucl_object_t *old, 342 const ucl_object_t *new) 343 { 344 khiter_t k; 345 int ret; 346 struct ucl_hash_elt elt, *pelt; 347 348 if (hashlin == NULL) { 349 return; 350 } 351 352 if (hashlin->caseless) { 353 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *) 354 hashlin->hash; 355 k = kh_put (ucl_hash_caseless_node, h, old, &ret); 356 if (ret == 0) { 357 elt = kh_value (h, k); 358 kh_del (ucl_hash_caseless_node, h, k); 359 k = kh_put (ucl_hash_caseless_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 else { 367 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *) 368 hashlin->hash; 369 k = kh_put (ucl_hash_node, h, old, &ret); 370 if (ret == 0) { 371 elt = kh_value (h, k); 372 kh_del (ucl_hash_node, h, k); 373 k = kh_put (ucl_hash_node, h, new, &ret); 374 pelt = &kh_value (h, k); 375 pelt->obj = new; 376 pelt->ar_idx = elt.ar_idx; 377 kv_A (hashlin->ar, elt.ar_idx) = new; 378 } 379 } 380 } 381 382 struct ucl_hash_real_iter { 383 const ucl_object_t **cur; 384 const ucl_object_t **end; 385 }; 386 387 #define UHI_SETERR(ep, ern) {if (ep != NULL) *ep = (ern);} 388 389 const void* 390 ucl_hash_iterate2 (ucl_hash_t *hashlin, ucl_hash_iter_t *iter, int *ep) 391 { 392 struct ucl_hash_real_iter *it = (struct ucl_hash_real_iter *)(*iter); 393 const ucl_object_t *ret = NULL; 394 395 if (hashlin == NULL) { 396 UHI_SETERR(ep, EINVAL); 397 return NULL; 398 } 399 400 if (it == NULL) { 401 it = UCL_ALLOC (sizeof (*it)); 402 403 if (it == NULL) { 404 UHI_SETERR(ep, ENOMEM); 405 return NULL; 406 } 407 408 it->cur = &hashlin->ar.a[0]; 409 it->end = it->cur + hashlin->ar.n; 410 } 411 412 UHI_SETERR(ep, 0); 413 if (it->cur < it->end) { 414 ret = *it->cur++; 415 } 416 else { 417 UCL_FREE (sizeof (*it), it); 418 *iter = NULL; 419 return NULL; 420 } 421 422 *iter = it; 423 424 return ret; 425 } 426 427 bool 428 ucl_hash_iter_has_next (ucl_hash_t *hashlin, ucl_hash_iter_t iter) 429 { 430 struct ucl_hash_real_iter *it = (struct ucl_hash_real_iter *)(iter); 431 432 return it->cur < it->end - 1; 433 } 434 435 436 const ucl_object_t* 437 ucl_hash_search (ucl_hash_t* hashlin, const char *key, unsigned keylen) 438 { 439 khiter_t k; 440 const ucl_object_t *ret = NULL; 441 ucl_object_t search; 442 struct ucl_hash_elt *elt; 443 444 search.key = key; 445 search.keylen = keylen; 446 447 if (hashlin == NULL) { 448 return NULL; 449 } 450 451 if (hashlin->caseless) { 452 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *) 453 hashlin->hash; 454 455 k = kh_get (ucl_hash_caseless_node, h, &search); 456 if (k != kh_end (h)) { 457 elt = &kh_value (h, k); 458 ret = elt->obj; 459 } 460 } 461 else { 462 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *) 463 hashlin->hash; 464 k = kh_get (ucl_hash_node, h, &search); 465 if (k != kh_end (h)) { 466 elt = &kh_value (h, k); 467 ret = elt->obj; 468 } 469 } 470 471 return ret; 472 } 473 474 void 475 ucl_hash_delete (ucl_hash_t* hashlin, const ucl_object_t *obj) 476 { 477 khiter_t k; 478 struct ucl_hash_elt *elt; 479 size_t i; 480 481 if (hashlin == NULL) { 482 return; 483 } 484 485 if (hashlin->caseless) { 486 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *) 487 hashlin->hash; 488 489 k = kh_get (ucl_hash_caseless_node, h, obj); 490 if (k != kh_end (h)) { 491 elt = &kh_value (h, k); 492 i = elt->ar_idx; 493 kv_del (const ucl_object_t *, hashlin->ar, elt->ar_idx); 494 kh_del (ucl_hash_caseless_node, h, k); 495 496 /* Update subsequent elts */ 497 for (; i < hashlin->ar.n; i ++) { 498 elt = &kh_value (h, i); 499 elt->ar_idx --; 500 } 501 } 502 } 503 else { 504 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *) 505 hashlin->hash; 506 k = kh_get (ucl_hash_node, h, obj); 507 if (k != kh_end (h)) { 508 elt = &kh_value (h, k); 509 i = elt->ar_idx; 510 kv_del (const ucl_object_t *, hashlin->ar, elt->ar_idx); 511 kh_del (ucl_hash_node, h, k); 512 513 /* Update subsequent elts */ 514 for (; i < hashlin->ar.n; i ++) { 515 elt = &kh_value (h, i); 516 elt->ar_idx --; 517 } 518 } 519 } 520 } 521 522 bool ucl_hash_reserve (ucl_hash_t *hashlin, size_t sz) 523 { 524 if (hashlin == NULL) { 525 return false; 526 } 527 528 if (sz > hashlin->ar.m) { 529 kv_resize_safe (const ucl_object_t *, hashlin->ar, sz, e0); 530 531 if (hashlin->caseless) { 532 khash_t(ucl_hash_caseless_node) *h = (khash_t( 533 ucl_hash_caseless_node) *) 534 hashlin->hash; 535 kh_resize (ucl_hash_caseless_node, h, sz * 2); 536 } else { 537 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *) 538 hashlin->hash; 539 kh_resize (ucl_hash_node, h, sz * 2); 540 } 541 } 542 return true; 543 e0: 544 return false; 545 } 546 547 static int 548 ucl_lc_cmp (const char *s, const char *d, size_t l) 549 { 550 unsigned int fp, i; 551 unsigned char c1, c2, c3, c4; 552 union { 553 unsigned char c[4]; 554 uint32_t n; 555 } cmp1, cmp2; 556 size_t leftover = l % 4; 557 int ret = 0; 558 559 fp = l - leftover; 560 561 for (i = 0; i != fp; i += 4) { 562 c1 = s[i], c2 = s[i + 1], c3 = s[i + 2], c4 = s[i + 3]; 563 cmp1.c[0] = lc_map[c1]; 564 cmp1.c[1] = lc_map[c2]; 565 cmp1.c[2] = lc_map[c3]; 566 cmp1.c[3] = lc_map[c4]; 567 568 c1 = d[i], c2 = d[i + 1], c3 = d[i + 2], c4 = d[i + 3]; 569 cmp2.c[0] = lc_map[c1]; 570 cmp2.c[1] = lc_map[c2]; 571 cmp2.c[2] = lc_map[c3]; 572 cmp2.c[3] = lc_map[c4]; 573 574 if (cmp1.n != cmp2.n) { 575 return cmp1.n - cmp2.n; 576 } 577 } 578 579 while (leftover > 0) { 580 if (lc_map[(unsigned char)s[i]] != lc_map[(unsigned char)d[i]]) { 581 return s[i] - d[i]; 582 } 583 584 leftover--; 585 i++; 586 } 587 588 return ret; 589 } 590 591 static int 592 ucl_hash_cmp_icase (const void *a, const void *b) 593 { 594 const ucl_object_t *oa = *(const ucl_object_t **)a, 595 *ob = *(const ucl_object_t **)b; 596 597 if (oa->keylen == ob->keylen) { 598 return ucl_lc_cmp (oa->key, ob->key, oa->keylen); 599 } 600 601 return ((int)(oa->keylen)) - ob->keylen; 602 } 603 604 static int 605 ucl_hash_cmp_case_sens (const void *a, const void *b) 606 { 607 const ucl_object_t *oa = *(const ucl_object_t **)a, 608 *ob = *(const ucl_object_t **)b; 609 610 if (oa->keylen == ob->keylen) { 611 return memcmp (oa->key, ob->key, oa->keylen); 612 } 613 614 return ((int)(oa->keylen)) - ob->keylen; 615 } 616 617 void 618 ucl_hash_sort (ucl_hash_t *hashlin, enum ucl_object_keys_sort_flags fl) 619 { 620 621 if (fl & UCL_SORT_KEYS_ICASE) { 622 qsort (hashlin->ar.a, hashlin->ar.n, sizeof (ucl_object_t *), 623 ucl_hash_cmp_icase); 624 } 625 else { 626 qsort (hashlin->ar.a, hashlin->ar.n, sizeof (ucl_object_t *), 627 ucl_hash_cmp_case_sens); 628 } 629 630 if (fl & UCL_SORT_KEYS_RECURSIVE) { 631 for (size_t i = 0; i < hashlin->ar.n; i ++) { 632 if (ucl_object_type (hashlin->ar.a[i]) == UCL_OBJECT) { 633 ucl_hash_sort (hashlin->ar.a[i]->value.ov, fl); 634 } 635 } 636 } 637 } 638