1 /* 2 Copyright (c) 2003-2018, Troy D. Hanson http://troydhanson.github.com/uthash/ 3 All rights reserved. 4 5 Redistribution and use in source and binary forms, with or without 6 modification, are permitted provided that the following conditions are met: 7 8 * Redistributions of source code must retain the above copyright 9 notice, this list of conditions and the following disclaimer. 10 11 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 12 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 13 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 14 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 15 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 16 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 17 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 18 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 19 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 20 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 #ifndef UTHASH_H 25 #define UTHASH_H 26 27 #define UTHASH_VERSION 2.1.0 28 29 #include <string.h> /* memcmp, memset, strlen */ 30 #include <stddef.h> /* ptrdiff_t */ 31 #include <stdlib.h> /* exit */ 32 33 /* These macros use decltype or the earlier __typeof GNU extension. 34 As decltype is only available in newer compilers (VS2010 or gcc 4.3+ 35 when compiling c++ source) this code uses whatever method is needed 36 or, for VS2008 where neither is available, uses casting workarounds. */ 37 #if !defined(DECLTYPE) && !defined(NO_DECLTYPE) 38 #if defined(_MSC_VER) /* MS compiler */ 39 #if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ 40 #define DECLTYPE(x) (decltype(x)) 41 #else /* VS2008 or older (or VS2010 in C mode) */ 42 #define NO_DECLTYPE 43 #endif 44 #elif defined(__BORLANDC__) || defined(__ICCARM__) || defined(__LCC__) || defined(__WATCOMC__) 45 #define NO_DECLTYPE 46 #else /* GNU, Sun and other compilers */ 47 #define DECLTYPE(x) (__typeof(x)) 48 #endif 49 #endif 50 51 #ifdef NO_DECLTYPE 52 #define DECLTYPE(x) 53 #define DECLTYPE_ASSIGN(dst,src) \ 54 do { \ 55 char **_da_dst = (char**)(&(dst)); \ 56 *_da_dst = (char*)(src); \ 57 } while (0) 58 #else 59 #define DECLTYPE_ASSIGN(dst,src) \ 60 do { \ 61 (dst) = DECLTYPE(dst)(src); \ 62 } while (0) 63 #endif 64 65 /* a number of the hash function use uint32_t which isn't defined on Pre VS2010 */ 66 #if defined(_WIN32) 67 #if defined(_MSC_VER) && _MSC_VER >= 1600 68 #include <stdint.h> 69 #elif defined(__WATCOMC__) || defined(__MINGW32__) || defined(__CYGWIN__) 70 #include <stdint.h> 71 #else 72 typedef unsigned int uint32_t; 73 typedef unsigned char uint8_t; 74 #endif 75 #elif defined(__GNUC__) && !defined(__VXWORKS__) 76 #include <stdint.h> 77 #else 78 typedef unsigned int uint32_t; 79 typedef unsigned char uint8_t; 80 #endif 81 82 #ifndef uthash_malloc 83 #define uthash_malloc(sz) malloc(sz) /* malloc fcn */ 84 #endif 85 #ifndef uthash_free 86 #define uthash_free(ptr,sz) free(ptr) /* free fcn */ 87 #endif 88 #ifndef uthash_bzero 89 #define uthash_bzero(a,n) memset(a,'\0',n) 90 #endif 91 #ifndef uthash_strlen 92 #define uthash_strlen(s) strlen(s) 93 #endif 94 95 #ifdef uthash_memcmp 96 /* This warning will not catch programs that define uthash_memcmp AFTER including uthash.h. */ 97 #warning "uthash_memcmp is deprecated; please use HASH_KEYCMP instead" 98 #else 99 #define uthash_memcmp(a,b,n) memcmp(a,b,n) 100 #endif 101 102 #ifndef HASH_KEYCMP 103 #define HASH_KEYCMP(a,b,n) uthash_memcmp(a,b,n) 104 #endif 105 106 #ifndef uthash_noexpand_fyi 107 #define uthash_noexpand_fyi(tbl) /* can be defined to log noexpand */ 108 #endif 109 #ifndef uthash_expand_fyi 110 #define uthash_expand_fyi(tbl) /* can be defined to log expands */ 111 #endif 112 113 #ifndef HASH_NONFATAL_OOM 114 #define HASH_NONFATAL_OOM 0 115 #endif 116 117 #if HASH_NONFATAL_OOM 118 /* malloc failures can be recovered from */ 119 120 #ifndef uthash_nonfatal_oom 121 #define uthash_nonfatal_oom(obj) do {} while (0) /* non-fatal OOM error */ 122 #endif 123 124 #define HASH_RECORD_OOM(oomed) do { (oomed) = 1; } while (0) 125 #define IF_HASH_NONFATAL_OOM(x) x 126 127 #else 128 /* malloc failures result in lost memory, hash tables are unusable */ 129 130 #ifndef uthash_fatal 131 #define uthash_fatal(msg) exit(-1) /* fatal OOM error */ 132 #endif 133 134 #define HASH_RECORD_OOM(oomed) uthash_fatal("out of memory") 135 #define IF_HASH_NONFATAL_OOM(x) 136 137 #endif 138 139 /* initial number of buckets */ 140 #define HASH_INITIAL_NUM_BUCKETS 32U /* initial number of buckets */ 141 #define HASH_INITIAL_NUM_BUCKETS_LOG2 5U /* lg2 of initial number of buckets */ 142 #define HASH_BKT_CAPACITY_THRESH 10U /* expand when bucket count reaches */ 143 144 /* calculate the element whose hash handle address is hhp */ 145 #define ELMT_FROM_HH(tbl,hhp) ((void*)(((char*)(hhp)) - ((tbl)->hho))) 146 /* calculate the hash handle from element address elp */ 147 #define HH_FROM_ELMT(tbl,elp) ((UT_hash_handle *)(((char*)(elp)) + ((tbl)->hho))) 148 149 #define HASH_ROLLBACK_BKT(hh, head, itemptrhh) \ 150 do { \ 151 struct UT_hash_handle *_hd_hh_item = (itemptrhh); \ 152 unsigned _hd_bkt; \ 153 HASH_TO_BKT(_hd_hh_item->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \ 154 (head)->hh.tbl->buckets[_hd_bkt].count++; \ 155 _hd_hh_item->hh_next = NULL; \ 156 _hd_hh_item->hh_prev = NULL; \ 157 } while (0) 158 159 #define HASH_VALUE(keyptr,keylen,hashv) \ 160 do { \ 161 HASH_FCN(keyptr, keylen, hashv); \ 162 } while (0) 163 164 #define HASH_FIND_BYHASHVALUE(hh,head,keyptr,keylen,hashval,out) \ 165 do { \ 166 (out) = NULL; \ 167 if (head) { \ 168 unsigned _hf_bkt; \ 169 HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _hf_bkt); \ 170 if (HASH_BLOOM_TEST((head)->hh.tbl, hashval) != 0) { \ 171 HASH_FIND_IN_BKT((head)->hh.tbl, hh, (head)->hh.tbl->buckets[ _hf_bkt ], keyptr, keylen, hashval, out); \ 172 } \ 173 } \ 174 } while (0) 175 176 #define HASH_FIND(hh,head,keyptr,keylen,out) \ 177 do { \ 178 (out) = NULL; \ 179 if (head) { \ 180 unsigned _hf_hashv; \ 181 HASH_VALUE(keyptr, keylen, _hf_hashv); \ 182 HASH_FIND_BYHASHVALUE(hh, head, keyptr, keylen, _hf_hashv, out); \ 183 } \ 184 } while (0) 185 186 #ifdef HASH_BLOOM 187 #define HASH_BLOOM_BITLEN (1UL << HASH_BLOOM) 188 #define HASH_BLOOM_BYTELEN (HASH_BLOOM_BITLEN/8UL) + (((HASH_BLOOM_BITLEN%8UL)!=0UL) ? 1UL : 0UL) 189 #define HASH_BLOOM_MAKE(tbl,oomed) \ 190 do { \ 191 (tbl)->bloom_nbits = HASH_BLOOM; \ 192 (tbl)->bloom_bv = (uint8_t*)uthash_malloc(HASH_BLOOM_BYTELEN); \ 193 if (!(tbl)->bloom_bv) { \ 194 HASH_RECORD_OOM(oomed); \ 195 } else { \ 196 uthash_bzero((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \ 197 (tbl)->bloom_sig = HASH_BLOOM_SIGNATURE; \ 198 } \ 199 } while (0) 200 201 #define HASH_BLOOM_FREE(tbl) \ 202 do { \ 203 uthash_free((tbl)->bloom_bv, HASH_BLOOM_BYTELEN); \ 204 } while (0) 205 206 #define HASH_BLOOM_BITSET(bv,idx) (bv[(idx)/8U] |= (1U << ((idx)%8U))) 207 #define HASH_BLOOM_BITTEST(bv,idx) (bv[(idx)/8U] & (1U << ((idx)%8U))) 208 209 #define HASH_BLOOM_ADD(tbl,hashv) \ 210 HASH_BLOOM_BITSET((tbl)->bloom_bv, ((hashv) & (uint32_t)((1UL << (tbl)->bloom_nbits) - 1U))) 211 212 #define HASH_BLOOM_TEST(tbl,hashv) \ 213 HASH_BLOOM_BITTEST((tbl)->bloom_bv, ((hashv) & (uint32_t)((1UL << (tbl)->bloom_nbits) - 1U))) 214 215 #else 216 #define HASH_BLOOM_MAKE(tbl,oomed) 217 #define HASH_BLOOM_FREE(tbl) 218 #define HASH_BLOOM_ADD(tbl,hashv) 219 #define HASH_BLOOM_TEST(tbl,hashv) (1) 220 #define HASH_BLOOM_BYTELEN 0U 221 #endif 222 223 #define HASH_MAKE_TABLE(hh,head,oomed) \ 224 do { \ 225 (head)->hh.tbl = (UT_hash_table*)uthash_malloc(sizeof(UT_hash_table)); \ 226 if (!(head)->hh.tbl) { \ 227 HASH_RECORD_OOM(oomed); \ 228 } else { \ 229 uthash_bzero((head)->hh.tbl, sizeof(UT_hash_table)); \ 230 (head)->hh.tbl->tail = &((head)->hh); \ 231 (head)->hh.tbl->num_buckets = HASH_INITIAL_NUM_BUCKETS; \ 232 (head)->hh.tbl->log2_num_buckets = HASH_INITIAL_NUM_BUCKETS_LOG2; \ 233 (head)->hh.tbl->hho = (char*)(&(head)->hh) - (char*)(head); \ 234 (head)->hh.tbl->buckets = (UT_hash_bucket*)uthash_malloc( \ 235 HASH_INITIAL_NUM_BUCKETS * sizeof(struct UT_hash_bucket)); \ 236 (head)->hh.tbl->signature = HASH_SIGNATURE; \ 237 if (!(head)->hh.tbl->buckets) { \ 238 HASH_RECORD_OOM(oomed); \ 239 uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ 240 } else { \ 241 uthash_bzero((head)->hh.tbl->buckets, \ 242 HASH_INITIAL_NUM_BUCKETS * sizeof(struct UT_hash_bucket)); \ 243 HASH_BLOOM_MAKE((head)->hh.tbl, oomed); \ 244 IF_HASH_NONFATAL_OOM( \ 245 if (oomed) { \ 246 uthash_free((head)->hh.tbl->buckets, \ 247 HASH_INITIAL_NUM_BUCKETS*sizeof(struct UT_hash_bucket)); \ 248 uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ 249 } \ 250 ) \ 251 } \ 252 } \ 253 } while (0) 254 255 #define HASH_REPLACE_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,replaced,cmpfcn) \ 256 do { \ 257 (replaced) = NULL; \ 258 HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \ 259 if (replaced) { \ 260 HASH_DELETE(hh, head, replaced); \ 261 } \ 262 HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn); \ 263 } while (0) 264 265 #define HASH_REPLACE_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add,replaced) \ 266 do { \ 267 (replaced) = NULL; \ 268 HASH_FIND_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, replaced); \ 269 if (replaced) { \ 270 HASH_DELETE(hh, head, replaced); \ 271 } \ 272 HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add); \ 273 } while (0) 274 275 #define HASH_REPLACE(hh,head,fieldname,keylen_in,add,replaced) \ 276 do { \ 277 unsigned _hr_hashv; \ 278 HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv); \ 279 HASH_REPLACE_BYHASHVALUE(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced); \ 280 } while (0) 281 282 #define HASH_REPLACE_INORDER(hh,head,fieldname,keylen_in,add,replaced,cmpfcn) \ 283 do { \ 284 unsigned _hr_hashv; \ 285 HASH_VALUE(&((add)->fieldname), keylen_in, _hr_hashv); \ 286 HASH_REPLACE_BYHASHVALUE_INORDER(hh, head, fieldname, keylen_in, _hr_hashv, add, replaced, cmpfcn); \ 287 } while (0) 288 289 #define HASH_APPEND_LIST(hh, head, add) \ 290 do { \ 291 (add)->hh.next = NULL; \ 292 (add)->hh.prev = ELMT_FROM_HH((head)->hh.tbl, (head)->hh.tbl->tail); \ 293 (head)->hh.tbl->tail->next = (add); \ 294 (head)->hh.tbl->tail = &((add)->hh); \ 295 } while (0) 296 297 #define HASH_AKBI_INNER_LOOP(hh,head,add,cmpfcn) \ 298 do { \ 299 do { \ 300 if (cmpfcn(DECLTYPE(head)(_hs_iter), add) > 0) { \ 301 break; \ 302 } \ 303 } while ((_hs_iter = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->next)); \ 304 } while (0) 305 306 #ifdef NO_DECLTYPE 307 #undef HASH_AKBI_INNER_LOOP 308 #define HASH_AKBI_INNER_LOOP(hh,head,add,cmpfcn) \ 309 do { \ 310 char *_hs_saved_head = (char*)(head); \ 311 do { \ 312 DECLTYPE_ASSIGN(head, _hs_iter); \ 313 if (cmpfcn(head, add) > 0) { \ 314 DECLTYPE_ASSIGN(head, _hs_saved_head); \ 315 break; \ 316 } \ 317 DECLTYPE_ASSIGN(head, _hs_saved_head); \ 318 } while ((_hs_iter = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->next)); \ 319 } while (0) 320 #endif 321 322 #if HASH_NONFATAL_OOM 323 324 #define HASH_ADD_TO_TABLE(hh,head,keyptr,keylen_in,hashval,add,oomed) \ 325 do { \ 326 if (!(oomed)) { \ 327 unsigned _ha_bkt; \ 328 (head)->hh.tbl->num_items++; \ 329 HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt); \ 330 HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], hh, &(add)->hh, oomed); \ 331 if (oomed) { \ 332 HASH_ROLLBACK_BKT(hh, head, &(add)->hh); \ 333 HASH_DELETE_HH(hh, head, &(add)->hh); \ 334 (add)->hh.tbl = NULL; \ 335 uthash_nonfatal_oom(add); \ 336 } else { \ 337 HASH_BLOOM_ADD((head)->hh.tbl, hashval); \ 338 HASH_EMIT_KEY(hh, head, keyptr, keylen_in); \ 339 } \ 340 } else { \ 341 (add)->hh.tbl = NULL; \ 342 uthash_nonfatal_oom(add); \ 343 } \ 344 } while (0) 345 346 #else 347 348 #define HASH_ADD_TO_TABLE(hh,head,keyptr,keylen_in,hashval,add,oomed) \ 349 do { \ 350 unsigned _ha_bkt; \ 351 (head)->hh.tbl->num_items++; \ 352 HASH_TO_BKT(hashval, (head)->hh.tbl->num_buckets, _ha_bkt); \ 353 HASH_ADD_TO_BKT((head)->hh.tbl->buckets[_ha_bkt], hh, &(add)->hh, oomed); \ 354 HASH_BLOOM_ADD((head)->hh.tbl, hashval); \ 355 HASH_EMIT_KEY(hh, head, keyptr, keylen_in); \ 356 } while (0) 357 358 #endif 359 360 361 #define HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh,head,keyptr,keylen_in,hashval,add,cmpfcn) \ 362 do { \ 363 IF_HASH_NONFATAL_OOM( int _ha_oomed = 0; ) \ 364 (add)->hh.hashv = (hashval); \ 365 (add)->hh.key = (char*) (keyptr); \ 366 (add)->hh.keylen = (unsigned) (keylen_in); \ 367 if (!(head)) { \ 368 (add)->hh.next = NULL; \ 369 (add)->hh.prev = NULL; \ 370 HASH_MAKE_TABLE(hh, add, _ha_oomed); \ 371 IF_HASH_NONFATAL_OOM( if (!_ha_oomed) { ) \ 372 (head) = (add); \ 373 IF_HASH_NONFATAL_OOM( } ) \ 374 } else { \ 375 void *_hs_iter = (head); \ 376 (add)->hh.tbl = (head)->hh.tbl; \ 377 HASH_AKBI_INNER_LOOP(hh, head, add, cmpfcn); \ 378 if (_hs_iter) { \ 379 (add)->hh.next = _hs_iter; \ 380 if (((add)->hh.prev = HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->prev)) { \ 381 HH_FROM_ELMT((head)->hh.tbl, (add)->hh.prev)->next = (add); \ 382 } else { \ 383 (head) = (add); \ 384 } \ 385 HH_FROM_ELMT((head)->hh.tbl, _hs_iter)->prev = (add); \ 386 } else { \ 387 HASH_APPEND_LIST(hh, head, add); \ 388 } \ 389 } \ 390 HASH_ADD_TO_TABLE(hh, head, keyptr, keylen_in, hashval, add, _ha_oomed); \ 391 HASH_FSCK(hh, head, "HASH_ADD_KEYPTR_BYHASHVALUE_INORDER"); \ 392 } while (0) 393 394 #define HASH_ADD_KEYPTR_INORDER(hh,head,keyptr,keylen_in,add,cmpfcn) \ 395 do { \ 396 unsigned _hs_hashv; \ 397 HASH_VALUE(keyptr, keylen_in, _hs_hashv); \ 398 HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, keyptr, keylen_in, _hs_hashv, add, cmpfcn); \ 399 } while (0) 400 401 #define HASH_ADD_BYHASHVALUE_INORDER(hh,head,fieldname,keylen_in,hashval,add,cmpfcn) \ 402 HASH_ADD_KEYPTR_BYHASHVALUE_INORDER(hh, head, &((add)->fieldname), keylen_in, hashval, add, cmpfcn) 403 404 #define HASH_ADD_INORDER(hh,head,fieldname,keylen_in,add,cmpfcn) \ 405 HASH_ADD_KEYPTR_INORDER(hh, head, &((add)->fieldname), keylen_in, add, cmpfcn) 406 407 #define HASH_ADD_KEYPTR_BYHASHVALUE(hh,head,keyptr,keylen_in,hashval,add) \ 408 do { \ 409 IF_HASH_NONFATAL_OOM( int _ha_oomed = 0; ) \ 410 (add)->hh.hashv = (hashval); \ 411 (add)->hh.key = (char*) (keyptr); \ 412 (add)->hh.keylen = (unsigned) (keylen_in); \ 413 if (!(head)) { \ 414 (add)->hh.next = NULL; \ 415 (add)->hh.prev = NULL; \ 416 HASH_MAKE_TABLE(hh, add, _ha_oomed); \ 417 IF_HASH_NONFATAL_OOM( if (!_ha_oomed) { ) \ 418 (head) = (add); \ 419 IF_HASH_NONFATAL_OOM( } ) \ 420 } else { \ 421 (add)->hh.tbl = (head)->hh.tbl; \ 422 HASH_APPEND_LIST(hh, head, add); \ 423 } \ 424 HASH_ADD_TO_TABLE(hh, head, keyptr, keylen_in, hashval, add, _ha_oomed); \ 425 HASH_FSCK(hh, head, "HASH_ADD_KEYPTR_BYHASHVALUE"); \ 426 } while (0) 427 428 #define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) \ 429 do { \ 430 unsigned _ha_hashv; \ 431 HASH_VALUE(keyptr, keylen_in, _ha_hashv); \ 432 HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, keyptr, keylen_in, _ha_hashv, add); \ 433 } while (0) 434 435 #define HASH_ADD_BYHASHVALUE(hh,head,fieldname,keylen_in,hashval,add) \ 436 HASH_ADD_KEYPTR_BYHASHVALUE(hh, head, &((add)->fieldname), keylen_in, hashval, add) 437 438 #define HASH_ADD(hh,head,fieldname,keylen_in,add) \ 439 HASH_ADD_KEYPTR(hh, head, &((add)->fieldname), keylen_in, add) 440 441 #define HASH_TO_BKT(hashv,num_bkts,bkt) \ 442 do { \ 443 bkt = ((hashv) & ((num_bkts) - 1U)); \ 444 } while (0) 445 446 /* delete "delptr" from the hash table. 447 * "the usual" patch-up process for the app-order doubly-linked-list. 448 * The use of _hd_hh_del below deserves special explanation. 449 * These used to be expressed using (delptr) but that led to a bug 450 * if someone used the same symbol for the head and deletee, like 451 * HASH_DELETE(hh,users,users); 452 * We want that to work, but by changing the head (users) below 453 * we were forfeiting our ability to further refer to the deletee (users) 454 * in the patch-up process. Solution: use scratch space to 455 * copy the deletee pointer, then the latter references are via that 456 * scratch pointer rather than through the repointed (users) symbol. 457 */ 458 #define HASH_DELETE(hh,head,delptr) \ 459 HASH_DELETE_HH(hh, head, &(delptr)->hh) 460 461 #define HASH_DELETE_HH(hh,head,delptrhh) \ 462 do { \ 463 struct UT_hash_handle *_hd_hh_del = (delptrhh); \ 464 if ((_hd_hh_del->prev == NULL) && (_hd_hh_del->next == NULL)) { \ 465 HASH_BLOOM_FREE((head)->hh.tbl); \ 466 uthash_free((head)->hh.tbl->buckets, \ 467 (head)->hh.tbl->num_buckets * sizeof(struct UT_hash_bucket)); \ 468 uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ 469 (head) = NULL; \ 470 } else { \ 471 unsigned _hd_bkt; \ 472 if (_hd_hh_del == (head)->hh.tbl->tail) { \ 473 (head)->hh.tbl->tail = HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->prev); \ 474 } \ 475 if (_hd_hh_del->prev != NULL) { \ 476 HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->prev)->next = _hd_hh_del->next; \ 477 } else { \ 478 DECLTYPE_ASSIGN(head, _hd_hh_del->next); \ 479 } \ 480 if (_hd_hh_del->next != NULL) { \ 481 HH_FROM_ELMT((head)->hh.tbl, _hd_hh_del->next)->prev = _hd_hh_del->prev; \ 482 } \ 483 HASH_TO_BKT(_hd_hh_del->hashv, (head)->hh.tbl->num_buckets, _hd_bkt); \ 484 HASH_DEL_IN_BKT((head)->hh.tbl->buckets[_hd_bkt], _hd_hh_del); \ 485 (head)->hh.tbl->num_items--; \ 486 } \ 487 HASH_FSCK(hh, head, "HASH_DELETE_HH"); \ 488 } while (0) 489 490 /* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */ 491 #define HASH_FIND_STR(head,findstr,out) \ 492 do { \ 493 unsigned _uthash_hfstr_keylen = (unsigned)uthash_strlen(findstr); \ 494 HASH_FIND(hh, head, findstr, _uthash_hfstr_keylen, out); \ 495 } while (0) 496 #define HASH_ADD_STR(head,strfield,add) \ 497 do { \ 498 unsigned _uthash_hastr_keylen = (unsigned)uthash_strlen((add)->strfield); \ 499 HASH_ADD(hh, head, strfield[0], _uthash_hastr_keylen, add); \ 500 } while (0) 501 #define HASH_REPLACE_STR(head,strfield,add,replaced) \ 502 do { \ 503 unsigned _uthash_hrstr_keylen = (unsigned)uthash_strlen((add)->strfield); \ 504 HASH_REPLACE(hh, head, strfield[0], _uthash_hrstr_keylen, add, replaced); \ 505 } while (0) 506 #define HASH_FIND_INT(head,findint,out) \ 507 HASH_FIND(hh,head,findint,sizeof(int),out) 508 #define HASH_ADD_INT(head,intfield,add) \ 509 HASH_ADD(hh,head,intfield,sizeof(int),add) 510 #define HASH_REPLACE_INT(head,intfield,add,replaced) \ 511 HASH_REPLACE(hh,head,intfield,sizeof(int),add,replaced) 512 #define HASH_FIND_PTR(head,findptr,out) \ 513 HASH_FIND(hh,head,findptr,sizeof(void *),out) 514 #define HASH_ADD_PTR(head,ptrfield,add) \ 515 HASH_ADD(hh,head,ptrfield,sizeof(void *),add) 516 #define HASH_REPLACE_PTR(head,ptrfield,add,replaced) \ 517 HASH_REPLACE(hh,head,ptrfield,sizeof(void *),add,replaced) 518 #define HASH_DEL(head,delptr) \ 519 HASH_DELETE(hh,head,delptr) 520 521 /* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined. 522 * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined. 523 */ 524 #ifdef HASH_DEBUG 525 #define HASH_OOPS(...) do { fprintf(stderr,__VA_ARGS__); exit(-1); } while (0) 526 #define HASH_FSCK(hh,head,where) \ 527 do { \ 528 struct UT_hash_handle *_thh; \ 529 if (head) { \ 530 unsigned _bkt_i; \ 531 unsigned _count = 0; \ 532 char *_prev; \ 533 for (_bkt_i = 0; _bkt_i < (head)->hh.tbl->num_buckets; ++_bkt_i) { \ 534 unsigned _bkt_count = 0; \ 535 _thh = (head)->hh.tbl->buckets[_bkt_i].hh_head; \ 536 _prev = NULL; \ 537 while (_thh) { \ 538 if (_prev != (char*)(_thh->hh_prev)) { \ 539 HASH_OOPS("%s: invalid hh_prev %p, actual %p\n", \ 540 (where), (void*)_thh->hh_prev, (void*)_prev); \ 541 } \ 542 _bkt_count++; \ 543 _prev = (char*)(_thh); \ 544 _thh = _thh->hh_next; \ 545 } \ 546 _count += _bkt_count; \ 547 if ((head)->hh.tbl->buckets[_bkt_i].count != _bkt_count) { \ 548 HASH_OOPS("%s: invalid bucket count %u, actual %u\n", \ 549 (where), (head)->hh.tbl->buckets[_bkt_i].count, _bkt_count); \ 550 } \ 551 } \ 552 if (_count != (head)->hh.tbl->num_items) { \ 553 HASH_OOPS("%s: invalid hh item count %u, actual %u\n", \ 554 (where), (head)->hh.tbl->num_items, _count); \ 555 } \ 556 _count = 0; \ 557 _prev = NULL; \ 558 _thh = &(head)->hh; \ 559 while (_thh) { \ 560 _count++; \ 561 if (_prev != (char*)_thh->prev) { \ 562 HASH_OOPS("%s: invalid prev %p, actual %p\n", \ 563 (where), (void*)_thh->prev, (void*)_prev); \ 564 } \ 565 _prev = (char*)ELMT_FROM_HH((head)->hh.tbl, _thh); \ 566 _thh = (_thh->next ? HH_FROM_ELMT((head)->hh.tbl, _thh->next) : NULL); \ 567 } \ 568 if (_count != (head)->hh.tbl->num_items) { \ 569 HASH_OOPS("%s: invalid app item count %u, actual %u\n", \ 570 (where), (head)->hh.tbl->num_items, _count); \ 571 } \ 572 } \ 573 } while (0) 574 #else 575 #define HASH_FSCK(hh,head,where) 576 #endif 577 578 /* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to 579 * the descriptor to which this macro is defined for tuning the hash function. 580 * The app can #include <unistd.h> to get the prototype for write(2). */ 581 #ifdef HASH_EMIT_KEYS 582 #define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) \ 583 do { \ 584 unsigned _klen = fieldlen; \ 585 write(HASH_EMIT_KEYS, &_klen, sizeof(_klen)); \ 586 write(HASH_EMIT_KEYS, keyptr, (unsigned long)fieldlen); \ 587 } while (0) 588 #else 589 #define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) 590 #endif 591 592 /* default to Jenkin's hash unless overridden e.g. DHASH_FUNCTION=HASH_SAX */ 593 #ifdef HASH_FUNCTION 594 #define HASH_FCN HASH_FUNCTION 595 #else 596 #define HASH_FCN HASH_JEN 597 #endif 598 599 /* The Bernstein hash function, used in Perl prior to v5.6. Note (x<<5+x)=x*33. */ 600 #define HASH_BER(key,keylen,hashv) \ 601 do { \ 602 unsigned _hb_keylen = (unsigned)keylen; \ 603 const unsigned char *_hb_key = (const unsigned char*)(key); \ 604 (hashv) = 0; \ 605 while (_hb_keylen-- != 0U) { \ 606 (hashv) = (((hashv) << 5) + (hashv)) + *_hb_key++; \ 607 } \ 608 } while (0) 609 610 611 /* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at 612 * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */ 613 #define HASH_SAX(key,keylen,hashv) \ 614 do { \ 615 unsigned _sx_i; \ 616 const unsigned char *_hs_key = (const unsigned char*)(key); \ 617 hashv = 0; \ 618 for (_sx_i=0; _sx_i < keylen; _sx_i++) { \ 619 hashv ^= (hashv << 5) + (hashv >> 2) + _hs_key[_sx_i]; \ 620 } \ 621 } while (0) 622 /* FNV-1a variation */ 623 #define HASH_FNV(key,keylen,hashv) \ 624 do { \ 625 unsigned _fn_i; \ 626 const unsigned char *_hf_key = (const unsigned char*)(key); \ 627 (hashv) = 2166136261U; \ 628 for (_fn_i=0; _fn_i < keylen; _fn_i++) { \ 629 hashv = hashv ^ _hf_key[_fn_i]; \ 630 hashv = hashv * 16777619U; \ 631 } \ 632 } while (0) 633 634 #define HASH_OAT(key,keylen,hashv) \ 635 do { \ 636 unsigned _ho_i; \ 637 const unsigned char *_ho_key=(const unsigned char*)(key); \ 638 hashv = 0; \ 639 for(_ho_i=0; _ho_i < keylen; _ho_i++) { \ 640 hashv += _ho_key[_ho_i]; \ 641 hashv += (hashv << 10); \ 642 hashv ^= (hashv >> 6); \ 643 } \ 644 hashv += (hashv << 3); \ 645 hashv ^= (hashv >> 11); \ 646 hashv += (hashv << 15); \ 647 } while (0) 648 649 #define HASH_JEN_MIX(a,b,c) \ 650 do { \ 651 a -= b; a -= c; a ^= ( c >> 13 ); \ 652 b -= c; b -= a; b ^= ( a << 8 ); \ 653 c -= a; c -= b; c ^= ( b >> 13 ); \ 654 a -= b; a -= c; a ^= ( c >> 12 ); \ 655 b -= c; b -= a; b ^= ( a << 16 ); \ 656 c -= a; c -= b; c ^= ( b >> 5 ); \ 657 a -= b; a -= c; a ^= ( c >> 3 ); \ 658 b -= c; b -= a; b ^= ( a << 10 ); \ 659 c -= a; c -= b; c ^= ( b >> 15 ); \ 660 } while (0) 661 662 #define HASH_JEN(key,keylen,hashv) \ 663 do { \ 664 unsigned _hj_i,_hj_j,_hj_k; \ 665 unsigned const char *_hj_key=(unsigned const char*)(key); \ 666 hashv = 0xfeedbeefu; \ 667 _hj_i = _hj_j = 0x9e3779b9u; \ 668 _hj_k = (unsigned)(keylen); \ 669 while (_hj_k >= 12U) { \ 670 _hj_i += (_hj_key[0] + ( (unsigned)_hj_key[1] << 8 ) \ 671 + ( (unsigned)_hj_key[2] << 16 ) \ 672 + ( (unsigned)_hj_key[3] << 24 ) ); \ 673 _hj_j += (_hj_key[4] + ( (unsigned)_hj_key[5] << 8 ) \ 674 + ( (unsigned)_hj_key[6] << 16 ) \ 675 + ( (unsigned)_hj_key[7] << 24 ) ); \ 676 hashv += (_hj_key[8] + ( (unsigned)_hj_key[9] << 8 ) \ 677 + ( (unsigned)_hj_key[10] << 16 ) \ 678 + ( (unsigned)_hj_key[11] << 24 ) ); \ 679 \ 680 HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ 681 \ 682 _hj_key += 12; \ 683 _hj_k -= 12U; \ 684 } \ 685 hashv += (unsigned)(keylen); \ 686 switch ( _hj_k ) { \ 687 case 11: hashv += ( (unsigned)_hj_key[10] << 24 ); /* FALLTHROUGH */ \ 688 case 10: hashv += ( (unsigned)_hj_key[9] << 16 ); /* FALLTHROUGH */ \ 689 case 9: hashv += ( (unsigned)_hj_key[8] << 8 ); /* FALLTHROUGH */ \ 690 case 8: _hj_j += ( (unsigned)_hj_key[7] << 24 ); /* FALLTHROUGH */ \ 691 case 7: _hj_j += ( (unsigned)_hj_key[6] << 16 ); /* FALLTHROUGH */ \ 692 case 6: _hj_j += ( (unsigned)_hj_key[5] << 8 ); /* FALLTHROUGH */ \ 693 case 5: _hj_j += _hj_key[4]; /* FALLTHROUGH */ \ 694 case 4: _hj_i += ( (unsigned)_hj_key[3] << 24 ); /* FALLTHROUGH */ \ 695 case 3: _hj_i += ( (unsigned)_hj_key[2] << 16 ); /* FALLTHROUGH */ \ 696 case 2: _hj_i += ( (unsigned)_hj_key[1] << 8 ); /* FALLTHROUGH */ \ 697 case 1: _hj_i += _hj_key[0]; \ 698 } \ 699 HASH_JEN_MIX(_hj_i, _hj_j, hashv); \ 700 } while (0) 701 702 /* The Paul Hsieh hash function */ 703 #undef get16bits 704 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ 705 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) 706 #define get16bits(d) (*((const uint16_t *) (d))) 707 #endif 708 709 #if !defined (get16bits) 710 #define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \ 711 +(uint32_t)(((const uint8_t *)(d))[0]) ) 712 #endif 713 #define HASH_SFH(key,keylen,hashv) \ 714 do { \ 715 unsigned const char *_sfh_key=(unsigned const char*)(key); \ 716 uint32_t _sfh_tmp, _sfh_len = (uint32_t)keylen; \ 717 \ 718 unsigned _sfh_rem = _sfh_len & 3U; \ 719 _sfh_len >>= 2; \ 720 hashv = 0xcafebabeu; \ 721 \ 722 /* Main loop */ \ 723 for (;_sfh_len > 0U; _sfh_len--) { \ 724 hashv += get16bits (_sfh_key); \ 725 _sfh_tmp = ((uint32_t)(get16bits (_sfh_key+2)) << 11) ^ hashv; \ 726 hashv = (hashv << 16) ^ _sfh_tmp; \ 727 _sfh_key += 2U*sizeof (uint16_t); \ 728 hashv += hashv >> 11; \ 729 } \ 730 \ 731 /* Handle end cases */ \ 732 switch (_sfh_rem) { \ 733 case 3: hashv += get16bits (_sfh_key); \ 734 hashv ^= hashv << 16; \ 735 hashv ^= (uint32_t)(_sfh_key[sizeof (uint16_t)]) << 18; \ 736 hashv += hashv >> 11; \ 737 break; \ 738 case 2: hashv += get16bits (_sfh_key); \ 739 hashv ^= hashv << 11; \ 740 hashv += hashv >> 17; \ 741 break; \ 742 case 1: hashv += *_sfh_key; \ 743 hashv ^= hashv << 10; \ 744 hashv += hashv >> 1; \ 745 } \ 746 \ 747 /* Force "avalanching" of final 127 bits */ \ 748 hashv ^= hashv << 3; \ 749 hashv += hashv >> 5; \ 750 hashv ^= hashv << 4; \ 751 hashv += hashv >> 17; \ 752 hashv ^= hashv << 25; \ 753 hashv += hashv >> 6; \ 754 } while (0) 755 756 #ifdef HASH_USING_NO_STRICT_ALIASING 757 /* The MurmurHash exploits some CPU's (x86,x86_64) tolerance for unaligned reads. 758 * For other types of CPU's (e.g. Sparc) an unaligned read causes a bus error. 759 * MurmurHash uses the faster approach only on CPU's where we know it's safe. 760 * 761 * Note the preprocessor built-in defines can be emitted using: 762 * 763 * gcc -m64 -dM -E - < /dev/null (on gcc) 764 * cc -## a.c (where a.c is a simple test file) (Sun Studio) 765 */ 766 #if (defined(__i386__) || defined(__x86_64__) || defined(_M_IX86)) 767 #define MUR_GETBLOCK(p,i) p[i] 768 #else /* non intel */ 769 #define MUR_PLUS0_ALIGNED(p) (((unsigned long)p & 3UL) == 0UL) 770 #define MUR_PLUS1_ALIGNED(p) (((unsigned long)p & 3UL) == 1UL) 771 #define MUR_PLUS2_ALIGNED(p) (((unsigned long)p & 3UL) == 2UL) 772 #define MUR_PLUS3_ALIGNED(p) (((unsigned long)p & 3UL) == 3UL) 773 #define WP(p) ((uint32_t*)((unsigned long)(p) & ~3UL)) 774 #if (defined(__BIG_ENDIAN__) || defined(SPARC) || defined(__ppc__) || defined(__ppc64__)) 775 #define MUR_THREE_ONE(p) ((((*WP(p))&0x00ffffff) << 8) | (((*(WP(p)+1))&0xff000000) >> 24)) 776 #define MUR_TWO_TWO(p) ((((*WP(p))&0x0000ffff) <<16) | (((*(WP(p)+1))&0xffff0000) >> 16)) 777 #define MUR_ONE_THREE(p) ((((*WP(p))&0x000000ff) <<24) | (((*(WP(p)+1))&0xffffff00) >> 8)) 778 #else /* assume little endian non-intel */ 779 #define MUR_THREE_ONE(p) ((((*WP(p))&0xffffff00) >> 8) | (((*(WP(p)+1))&0x000000ff) << 24)) 780 #define MUR_TWO_TWO(p) ((((*WP(p))&0xffff0000) >>16) | (((*(WP(p)+1))&0x0000ffff) << 16)) 781 #define MUR_ONE_THREE(p) ((((*WP(p))&0xff000000) >>24) | (((*(WP(p)+1))&0x00ffffff) << 8)) 782 #endif 783 #define MUR_GETBLOCK(p,i) (MUR_PLUS0_ALIGNED(p) ? ((p)[i]) : \ 784 (MUR_PLUS1_ALIGNED(p) ? MUR_THREE_ONE(p) : \ 785 (MUR_PLUS2_ALIGNED(p) ? MUR_TWO_TWO(p) : \ 786 MUR_ONE_THREE(p)))) 787 #endif 788 #define MUR_ROTL32(x,r) (((x) << (r)) | ((x) >> (32 - (r)))) 789 #define MUR_FMIX(_h) \ 790 do { \ 791 _h ^= _h >> 16; \ 792 _h *= 0x85ebca6bu; \ 793 _h ^= _h >> 13; \ 794 _h *= 0xc2b2ae35u; \ 795 _h ^= _h >> 16; \ 796 } while (0) 797 798 #define HASH_MUR(key,keylen,hashv) \ 799 do { \ 800 const uint8_t *_mur_data = (const uint8_t*)(key); \ 801 const int _mur_nblocks = (int)(keylen) / 4; \ 802 uint32_t _mur_h1 = 0xf88D5353u; \ 803 uint32_t _mur_c1 = 0xcc9e2d51u; \ 804 uint32_t _mur_c2 = 0x1b873593u; \ 805 uint32_t _mur_k1 = 0; \ 806 const uint8_t *_mur_tail; \ 807 const uint32_t *_mur_blocks = (const uint32_t*)(_mur_data+(_mur_nblocks*4)); \ 808 int _mur_i; \ 809 for (_mur_i = -_mur_nblocks; _mur_i != 0; _mur_i++) { \ 810 _mur_k1 = MUR_GETBLOCK(_mur_blocks,_mur_i); \ 811 _mur_k1 *= _mur_c1; \ 812 _mur_k1 = MUR_ROTL32(_mur_k1,15); \ 813 _mur_k1 *= _mur_c2; \ 814 \ 815 _mur_h1 ^= _mur_k1; \ 816 _mur_h1 = MUR_ROTL32(_mur_h1,13); \ 817 _mur_h1 = (_mur_h1*5U) + 0xe6546b64u; \ 818 } \ 819 _mur_tail = (const uint8_t*)(_mur_data + (_mur_nblocks*4)); \ 820 _mur_k1=0; \ 821 switch ((keylen) & 3U) { \ 822 case 0: break; \ 823 case 3: _mur_k1 ^= (uint32_t)_mur_tail[2] << 16; /* FALLTHROUGH */ \ 824 case 2: _mur_k1 ^= (uint32_t)_mur_tail[1] << 8; /* FALLTHROUGH */ \ 825 case 1: _mur_k1 ^= (uint32_t)_mur_tail[0]; \ 826 _mur_k1 *= _mur_c1; \ 827 _mur_k1 = MUR_ROTL32(_mur_k1,15); \ 828 _mur_k1 *= _mur_c2; \ 829 _mur_h1 ^= _mur_k1; \ 830 } \ 831 _mur_h1 ^= (uint32_t)(keylen); \ 832 MUR_FMIX(_mur_h1); \ 833 hashv = _mur_h1; \ 834 } while (0) 835 #endif /* HASH_USING_NO_STRICT_ALIASING */ 836 837 /* iterate over items in a known bucket to find desired item */ 838 #define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,hashval,out) \ 839 do { \ 840 if ((head).hh_head != NULL) { \ 841 DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (head).hh_head)); \ 842 } else { \ 843 (out) = NULL; \ 844 } \ 845 while ((out) != NULL) { \ 846 if ((out)->hh.hashv == (hashval) && (out)->hh.keylen == (keylen_in)) { \ 847 if (HASH_KEYCMP((out)->hh.key, keyptr, keylen_in) == 0) { \ 848 break; \ 849 } \ 850 } \ 851 if ((out)->hh.hh_next != NULL) { \ 852 DECLTYPE_ASSIGN(out, ELMT_FROM_HH(tbl, (out)->hh.hh_next)); \ 853 } else { \ 854 (out) = NULL; \ 855 } \ 856 } \ 857 } while (0) 858 859 /* add an item to a bucket */ 860 #define HASH_ADD_TO_BKT(head,hh,addhh,oomed) \ 861 do { \ 862 UT_hash_bucket *_ha_head = &(head); \ 863 _ha_head->count++; \ 864 (addhh)->hh_next = _ha_head->hh_head; \ 865 (addhh)->hh_prev = NULL; \ 866 if (_ha_head->hh_head != NULL) { \ 867 _ha_head->hh_head->hh_prev = (addhh); \ 868 } \ 869 _ha_head->hh_head = (addhh); \ 870 if ((_ha_head->count >= ((_ha_head->expand_mult + 1U) * HASH_BKT_CAPACITY_THRESH)) \ 871 && !(addhh)->tbl->noexpand) { \ 872 HASH_EXPAND_BUCKETS(addhh,(addhh)->tbl, oomed); \ 873 IF_HASH_NONFATAL_OOM( \ 874 if (oomed) { \ 875 HASH_DEL_IN_BKT(head,addhh); \ 876 } \ 877 ) \ 878 } \ 879 } while (0) 880 881 /* remove an item from a given bucket */ 882 #define HASH_DEL_IN_BKT(head,delhh) \ 883 do { \ 884 UT_hash_bucket *_hd_head = &(head); \ 885 _hd_head->count--; \ 886 if (_hd_head->hh_head == (delhh)) { \ 887 _hd_head->hh_head = (delhh)->hh_next; \ 888 } \ 889 if ((delhh)->hh_prev) { \ 890 (delhh)->hh_prev->hh_next = (delhh)->hh_next; \ 891 } \ 892 if ((delhh)->hh_next) { \ 893 (delhh)->hh_next->hh_prev = (delhh)->hh_prev; \ 894 } \ 895 } while (0) 896 897 /* Bucket expansion has the effect of doubling the number of buckets 898 * and redistributing the items into the new buckets. Ideally the 899 * items will distribute more or less evenly into the new buckets 900 * (the extent to which this is true is a measure of the quality of 901 * the hash function as it applies to the key domain). 902 * 903 * With the items distributed into more buckets, the chain length 904 * (item count) in each bucket is reduced. Thus by expanding buckets 905 * the hash keeps a bound on the chain length. This bounded chain 906 * length is the essence of how a hash provides constant time lookup. 907 * 908 * The calculation of tbl->ideal_chain_maxlen below deserves some 909 * explanation. First, keep in mind that we're calculating the ideal 910 * maximum chain length based on the *new* (doubled) bucket count. 911 * In fractions this is just n/b (n=number of items,b=new num buckets). 912 * Since the ideal chain length is an integer, we want to calculate 913 * ceil(n/b). We don't depend on floating point arithmetic in this 914 * hash, so to calculate ceil(n/b) with integers we could write 915 * 916 * ceil(n/b) = (n/b) + ((n%b)?1:0) 917 * 918 * and in fact a previous version of this hash did just that. 919 * But now we have improved things a bit by recognizing that b is 920 * always a power of two. We keep its base 2 log handy (call it lb), 921 * so now we can write this with a bit shift and logical AND: 922 * 923 * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0) 924 * 925 */ 926 #define HASH_EXPAND_BUCKETS(hh,tbl,oomed) \ 927 do { \ 928 unsigned _he_bkt; \ 929 unsigned _he_bkt_i; \ 930 struct UT_hash_handle *_he_thh, *_he_hh_nxt; \ 931 UT_hash_bucket *_he_new_buckets, *_he_newbkt; \ 932 _he_new_buckets = (UT_hash_bucket*)uthash_malloc( \ 933 2UL * (tbl)->num_buckets * sizeof(struct UT_hash_bucket)); \ 934 if (!_he_new_buckets) { \ 935 HASH_RECORD_OOM(oomed); \ 936 } else { \ 937 uthash_bzero(_he_new_buckets, \ 938 2UL * (tbl)->num_buckets * sizeof(struct UT_hash_bucket)); \ 939 (tbl)->ideal_chain_maxlen = \ 940 ((tbl)->num_items >> ((tbl)->log2_num_buckets+1U)) + \ 941 ((((tbl)->num_items & (((tbl)->num_buckets*2U)-1U)) != 0U) ? 1U : 0U); \ 942 (tbl)->nonideal_items = 0; \ 943 for (_he_bkt_i = 0; _he_bkt_i < (tbl)->num_buckets; _he_bkt_i++) { \ 944 _he_thh = (tbl)->buckets[ _he_bkt_i ].hh_head; \ 945 while (_he_thh != NULL) { \ 946 _he_hh_nxt = _he_thh->hh_next; \ 947 HASH_TO_BKT(_he_thh->hashv, (tbl)->num_buckets * 2U, _he_bkt); \ 948 _he_newbkt = &(_he_new_buckets[_he_bkt]); \ 949 if (++(_he_newbkt->count) > (tbl)->ideal_chain_maxlen) { \ 950 (tbl)->nonideal_items++; \ 951 if (_he_newbkt->count > _he_newbkt->expand_mult * (tbl)->ideal_chain_maxlen) { \ 952 _he_newbkt->expand_mult++; \ 953 } \ 954 } \ 955 _he_thh->hh_prev = NULL; \ 956 _he_thh->hh_next = _he_newbkt->hh_head; \ 957 if (_he_newbkt->hh_head != NULL) { \ 958 _he_newbkt->hh_head->hh_prev = _he_thh; \ 959 } \ 960 _he_newbkt->hh_head = _he_thh; \ 961 _he_thh = _he_hh_nxt; \ 962 } \ 963 } \ 964 uthash_free((tbl)->buckets, (tbl)->num_buckets * sizeof(struct UT_hash_bucket)); \ 965 (tbl)->num_buckets *= 2U; \ 966 (tbl)->log2_num_buckets++; \ 967 (tbl)->buckets = _he_new_buckets; \ 968 (tbl)->ineff_expands = ((tbl)->nonideal_items > ((tbl)->num_items >> 1)) ? \ 969 ((tbl)->ineff_expands+1U) : 0U; \ 970 if ((tbl)->ineff_expands > 1U) { \ 971 (tbl)->noexpand = 1; \ 972 uthash_noexpand_fyi(tbl); \ 973 } \ 974 uthash_expand_fyi(tbl); \ 975 } \ 976 } while (0) 977 978 979 /* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */ 980 /* Note that HASH_SORT assumes the hash handle name to be hh. 981 * HASH_SRT was added to allow the hash handle name to be passed in. */ 982 #define HASH_SORT(head,cmpfcn) HASH_SRT(hh,head,cmpfcn) 983 #define HASH_SRT(hh,head,cmpfcn) \ 984 do { \ 985 unsigned _hs_i; \ 986 unsigned _hs_looping,_hs_nmerges,_hs_insize,_hs_psize,_hs_qsize; \ 987 struct UT_hash_handle *_hs_p, *_hs_q, *_hs_e, *_hs_list, *_hs_tail; \ 988 if (head != NULL) { \ 989 _hs_insize = 1; \ 990 _hs_looping = 1; \ 991 _hs_list = &((head)->hh); \ 992 while (_hs_looping != 0U) { \ 993 _hs_p = _hs_list; \ 994 _hs_list = NULL; \ 995 _hs_tail = NULL; \ 996 _hs_nmerges = 0; \ 997 while (_hs_p != NULL) { \ 998 _hs_nmerges++; \ 999 _hs_q = _hs_p; \ 1000 _hs_psize = 0; \ 1001 for (_hs_i = 0; _hs_i < _hs_insize; ++_hs_i) { \ 1002 _hs_psize++; \ 1003 _hs_q = ((_hs_q->next != NULL) ? \ 1004 HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \ 1005 if (_hs_q == NULL) { \ 1006 break; \ 1007 } \ 1008 } \ 1009 _hs_qsize = _hs_insize; \ 1010 while ((_hs_psize != 0U) || ((_hs_qsize != 0U) && (_hs_q != NULL))) { \ 1011 if (_hs_psize == 0U) { \ 1012 _hs_e = _hs_q; \ 1013 _hs_q = ((_hs_q->next != NULL) ? \ 1014 HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \ 1015 _hs_qsize--; \ 1016 } else if ((_hs_qsize == 0U) || (_hs_q == NULL)) { \ 1017 _hs_e = _hs_p; \ 1018 if (_hs_p != NULL) { \ 1019 _hs_p = ((_hs_p->next != NULL) ? \ 1020 HH_FROM_ELMT((head)->hh.tbl, _hs_p->next) : NULL); \ 1021 } \ 1022 _hs_psize--; \ 1023 } else if ((cmpfcn( \ 1024 DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl, _hs_p)), \ 1025 DECLTYPE(head)(ELMT_FROM_HH((head)->hh.tbl, _hs_q)) \ 1026 )) <= 0) { \ 1027 _hs_e = _hs_p; \ 1028 if (_hs_p != NULL) { \ 1029 _hs_p = ((_hs_p->next != NULL) ? \ 1030 HH_FROM_ELMT((head)->hh.tbl, _hs_p->next) : NULL); \ 1031 } \ 1032 _hs_psize--; \ 1033 } else { \ 1034 _hs_e = _hs_q; \ 1035 _hs_q = ((_hs_q->next != NULL) ? \ 1036 HH_FROM_ELMT((head)->hh.tbl, _hs_q->next) : NULL); \ 1037 _hs_qsize--; \ 1038 } \ 1039 if ( _hs_tail != NULL ) { \ 1040 _hs_tail->next = ((_hs_e != NULL) ? \ 1041 ELMT_FROM_HH((head)->hh.tbl, _hs_e) : NULL); \ 1042 } else { \ 1043 _hs_list = _hs_e; \ 1044 } \ 1045 if (_hs_e != NULL) { \ 1046 _hs_e->prev = ((_hs_tail != NULL) ? \ 1047 ELMT_FROM_HH((head)->hh.tbl, _hs_tail) : NULL); \ 1048 } \ 1049 _hs_tail = _hs_e; \ 1050 } \ 1051 _hs_p = _hs_q; \ 1052 } \ 1053 if (_hs_tail != NULL) { \ 1054 _hs_tail->next = NULL; \ 1055 } \ 1056 if (_hs_nmerges <= 1U) { \ 1057 _hs_looping = 0; \ 1058 (head)->hh.tbl->tail = _hs_tail; \ 1059 DECLTYPE_ASSIGN(head, ELMT_FROM_HH((head)->hh.tbl, _hs_list)); \ 1060 } \ 1061 _hs_insize *= 2U; \ 1062 } \ 1063 HASH_FSCK(hh, head, "HASH_SRT"); \ 1064 } \ 1065 } while (0) 1066 1067 /* This function selects items from one hash into another hash. 1068 * The end result is that the selected items have dual presence 1069 * in both hashes. There is no copy of the items made; rather 1070 * they are added into the new hash through a secondary hash 1071 * hash handle that must be present in the structure. */ 1072 #define HASH_SELECT(hh_dst, dst, hh_src, src, cond) \ 1073 do { \ 1074 unsigned _src_bkt, _dst_bkt; \ 1075 void *_last_elt = NULL, *_elt; \ 1076 UT_hash_handle *_src_hh, *_dst_hh, *_last_elt_hh=NULL; \ 1077 ptrdiff_t _dst_hho = ((char*)(&(dst)->hh_dst) - (char*)(dst)); \ 1078 if ((src) != NULL) { \ 1079 for (_src_bkt=0; _src_bkt < (src)->hh_src.tbl->num_buckets; _src_bkt++) { \ 1080 for (_src_hh = (src)->hh_src.tbl->buckets[_src_bkt].hh_head; \ 1081 _src_hh != NULL; \ 1082 _src_hh = _src_hh->hh_next) { \ 1083 _elt = ELMT_FROM_HH((src)->hh_src.tbl, _src_hh); \ 1084 if (cond(_elt)) { \ 1085 IF_HASH_NONFATAL_OOM( int _hs_oomed = 0; ) \ 1086 _dst_hh = (UT_hash_handle*)(((char*)_elt) + _dst_hho); \ 1087 _dst_hh->key = _src_hh->key; \ 1088 _dst_hh->keylen = _src_hh->keylen; \ 1089 _dst_hh->hashv = _src_hh->hashv; \ 1090 _dst_hh->prev = _last_elt; \ 1091 _dst_hh->next = NULL; \ 1092 if (_last_elt_hh != NULL) { \ 1093 _last_elt_hh->next = _elt; \ 1094 } \ 1095 if ((dst) == NULL) { \ 1096 DECLTYPE_ASSIGN(dst, _elt); \ 1097 HASH_MAKE_TABLE(hh_dst, dst, _hs_oomed); \ 1098 IF_HASH_NONFATAL_OOM( \ 1099 if (_hs_oomed) { \ 1100 uthash_nonfatal_oom(_elt); \ 1101 (dst) = NULL; \ 1102 continue; \ 1103 } \ 1104 ) \ 1105 } else { \ 1106 _dst_hh->tbl = (dst)->hh_dst.tbl; \ 1107 } \ 1108 HASH_TO_BKT(_dst_hh->hashv, _dst_hh->tbl->num_buckets, _dst_bkt); \ 1109 HASH_ADD_TO_BKT(_dst_hh->tbl->buckets[_dst_bkt], hh_dst, _dst_hh, _hs_oomed); \ 1110 (dst)->hh_dst.tbl->num_items++; \ 1111 IF_HASH_NONFATAL_OOM( \ 1112 if (_hs_oomed) { \ 1113 HASH_ROLLBACK_BKT(hh_dst, dst, _dst_hh); \ 1114 HASH_DELETE_HH(hh_dst, dst, _dst_hh); \ 1115 _dst_hh->tbl = NULL; \ 1116 uthash_nonfatal_oom(_elt); \ 1117 continue; \ 1118 } \ 1119 ) \ 1120 HASH_BLOOM_ADD(_dst_hh->tbl, _dst_hh->hashv); \ 1121 _last_elt = _elt; \ 1122 _last_elt_hh = _dst_hh; \ 1123 } \ 1124 } \ 1125 } \ 1126 } \ 1127 HASH_FSCK(hh_dst, dst, "HASH_SELECT"); \ 1128 } while (0) 1129 1130 #define HASH_CLEAR(hh,head) \ 1131 do { \ 1132 if ((head) != NULL) { \ 1133 HASH_BLOOM_FREE((head)->hh.tbl); \ 1134 uthash_free((head)->hh.tbl->buckets, \ 1135 (head)->hh.tbl->num_buckets*sizeof(struct UT_hash_bucket)); \ 1136 uthash_free((head)->hh.tbl, sizeof(UT_hash_table)); \ 1137 (head) = NULL; \ 1138 } \ 1139 } while (0) 1140 1141 #define HASH_OVERHEAD(hh,head) \ 1142 (((head) != NULL) ? ( \ 1143 (size_t)(((head)->hh.tbl->num_items * sizeof(UT_hash_handle)) + \ 1144 ((head)->hh.tbl->num_buckets * sizeof(UT_hash_bucket)) + \ 1145 sizeof(UT_hash_table) + \ 1146 (HASH_BLOOM_BYTELEN))) : 0U) 1147 1148 #ifdef NO_DECLTYPE 1149 #define HASH_ITER(hh,head,el,tmp) \ 1150 for(((el)=(head)), ((*(char**)(&(tmp)))=(char*)((head!=NULL)?(head)->hh.next:NULL)); \ 1151 (el) != NULL; ((el)=(tmp)), ((*(char**)(&(tmp)))=(char*)((tmp!=NULL)?(tmp)->hh.next:NULL))) 1152 #else 1153 #define HASH_ITER(hh,head,el,tmp) \ 1154 for(((el)=(head)), ((tmp)=DECLTYPE(el)((head!=NULL)?(head)->hh.next:NULL)); \ 1155 (el) != NULL; ((el)=(tmp)), ((tmp)=DECLTYPE(el)((tmp!=NULL)?(tmp)->hh.next:NULL))) 1156 #endif 1157 1158 /* obtain a count of items in the hash */ 1159 #define HASH_COUNT(head) HASH_CNT(hh,head) 1160 #define HASH_CNT(hh,head) ((head != NULL)?((head)->hh.tbl->num_items):0U) 1161 1162 typedef struct UT_hash_bucket { 1163 struct UT_hash_handle *hh_head; 1164 unsigned count; 1165 1166 /* expand_mult is normally set to 0. In this situation, the max chain length 1167 * threshold is enforced at its default value, HASH_BKT_CAPACITY_THRESH. (If 1168 * the bucket's chain exceeds this length, bucket expansion is triggered). 1169 * However, setting expand_mult to a non-zero value delays bucket expansion 1170 * (that would be triggered by additions to this particular bucket) 1171 * until its chain length reaches a *multiple* of HASH_BKT_CAPACITY_THRESH. 1172 * (The multiplier is simply expand_mult+1). The whole idea of this 1173 * multiplier is to reduce bucket expansions, since they are expensive, in 1174 * situations where we know that a particular bucket tends to be overused. 1175 * It is better to let its chain length grow to a longer yet-still-bounded 1176 * value, than to do an O(n) bucket expansion too often. 1177 */ 1178 unsigned expand_mult; 1179 1180 } UT_hash_bucket; 1181 1182 /* random signature used only to find hash tables in external analysis */ 1183 #define HASH_SIGNATURE 0xa0111fe1u 1184 #define HASH_BLOOM_SIGNATURE 0xb12220f2u 1185 1186 typedef struct UT_hash_table { 1187 UT_hash_bucket *buckets; 1188 unsigned num_buckets, log2_num_buckets; 1189 unsigned num_items; 1190 struct UT_hash_handle *tail; /* tail hh in app order, for fast append */ 1191 ptrdiff_t hho; /* hash handle offset (byte pos of hash handle in element */ 1192 1193 /* in an ideal situation (all buckets used equally), no bucket would have 1194 * more than ceil(#items/#buckets) items. that's the ideal chain length. */ 1195 unsigned ideal_chain_maxlen; 1196 1197 /* nonideal_items is the number of items in the hash whose chain position 1198 * exceeds the ideal chain maxlen. these items pay the penalty for an uneven 1199 * hash distribution; reaching them in a chain traversal takes >ideal steps */ 1200 unsigned nonideal_items; 1201 1202 /* ineffective expands occur when a bucket doubling was performed, but 1203 * afterward, more than half the items in the hash had nonideal chain 1204 * positions. If this happens on two consecutive expansions we inhibit any 1205 * further expansion, as it's not helping; this happens when the hash 1206 * function isn't a good fit for the key domain. When expansion is inhibited 1207 * the hash will still work, albeit no longer in constant time. */ 1208 unsigned ineff_expands, noexpand; 1209 1210 uint32_t signature; /* used only to find hash tables in external analysis */ 1211 #ifdef HASH_BLOOM 1212 uint32_t bloom_sig; /* used only to test bloom exists in external analysis */ 1213 uint8_t *bloom_bv; 1214 uint8_t bloom_nbits; 1215 #endif 1216 1217 } UT_hash_table; 1218 1219 typedef struct UT_hash_handle { 1220 struct UT_hash_table *tbl; 1221 void *prev; /* prev element in app order */ 1222 void *next; /* next element in app order */ 1223 struct UT_hash_handle *hh_prev; /* previous hh in bucket order */ 1224 struct UT_hash_handle *hh_next; /* next hh in bucket order */ 1225 void *key; /* ptr to enclosing struct's key */ 1226 unsigned keylen; /* enclosing struct's key len */ 1227 unsigned hashv; /* result of hash-fcn(key) */ 1228 } UT_hash_handle; 1229 1230 #endif /* UTHASH_H */ 1231