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