/* Copyright (c) 2003-2010, Troy D. Hanson http://uthash.sourceforge.net All rights reserved. SPDX-License-Identifier: BSD-1-Clause */ #ifndef UTHASH_H #define UTHASH_H #include <string.h> /* memcmp,strlen */ #include <stddef.h> /* ptrdiff_t */ /* These macros use decltype or the earlier __typeof GNU extension. As decltype is only available in newer compilers (VS2010 or gcc 4.3+ when compiling c++ source) this code uses whatever method is needed or, for VS2008 where neither is available, uses casting workarounds. */ #ifdef _MSC_VER /* MS compiler */ #if _MSC_VER >= 1600 && __cplusplus /* VS2010 or newer in C++ mode */ #define DECLTYPE … #else /* VS2008 or older (or VS2010 in C mode) */ #define NO_DECLTYPE #define DECLTYPE … #endif #else /* GNU, Sun and other compilers */ #define DECLTYPE(x) … #endif #ifdef NO_DECLTYPE #define DECLTYPE_ASSIGN … #else #define DECLTYPE_ASSIGN(dst,src) … #endif /* a number of the hash function use uint32_t which isn't defined on win32 */ #ifdef _MSC_VER typedef unsigned int uint32_t; #else #include <inttypes.h> /* uint32_t */ #endif #define UTHASH_VERSION … #define uthash_fatal(msg) … #define uthash_malloc(sz) … #define uthash_free(ptr) … #define uthash_noexpand_fyi(tbl) … #define uthash_expand_fyi(tbl) … /* initial number of buckets */ #define HASH_INITIAL_NUM_BUCKETS … #define HASH_INITIAL_NUM_BUCKETS_LOG2 … #define HASH_BKT_CAPACITY_THRESH … /* calculate the element whose hash handle address is hhe */ #define ELMT_FROM_HH(tbl,hhp) … #define HASH_FIND(hh,head,keyptr,keylen,out) … #ifdef HASH_BLOOM #define HASH_BLOOM_BITLEN … #define HASH_BLOOM_BYTELEN … #define HASH_BLOOM_MAKE … #define HASH_BLOOM_FREE … #define HASH_BLOOM_BITSET … #define HASH_BLOOM_BITTEST … #define HASH_BLOOM_ADD … #define HASH_BLOOM_TEST … #else #define HASH_BLOOM_MAKE(tbl) … #define HASH_BLOOM_FREE(tbl) … #define HASH_BLOOM_ADD(tbl,hashv) … #define HASH_BLOOM_TEST(tbl,hashv) … #endif #define HASH_MAKE_TABLE(hh,head) … #define HASH_ADD(hh,head,fieldname,keylen_in,add) … #define HASH_ADD_KEYPTR(hh,head,keyptr,keylen_in,add) … #define HASH_TO_BKT( hashv, num_bkts, bkt ) … /* delete "delptr" from the hash table. * "the usual" patch-up process for the app-order doubly-linked-list. * The use of _hd_hh_del below deserves special explanation. * These used to be expressed using (delptr) but that led to a bug * if someone used the same symbol for the head and deletee, like * HASH_DELETE(hh,users,users); * We want that to work, but by changing the head (users) below * we were forfeiting our ability to further refer to the deletee (users) * in the patch-up process. Solution: use scratch space to * copy the deletee pointer, then the latter references are via that * scratch pointer rather than through the repointed (users) symbol. */ #define HASH_DELETE(hh,head,delptr) … /* convenience forms of HASH_FIND/HASH_ADD/HASH_DEL */ #define HASH_FIND_STR(head,findstr,out) … #define HASH_ADD_STR(head,strfield,add) … #define HASH_FIND_INT(head,findint,out) … #define HASH_ADD_INT(head,intfield,add) … #define HASH_FIND_PTR(head,findptr,out) … #define HASH_ADD_PTR(head,ptrfield,add) … #define HASH_DEL(head,delptr) … /* HASH_FSCK checks hash integrity on every add/delete when HASH_DEBUG is defined. * This is for uthash developer only; it compiles away if HASH_DEBUG isn't defined. */ #ifdef HASH_DEBUG #define HASH_OOPS … #define HASH_FSCK … #else #define HASH_FSCK(hh,head) … #endif /* When compiled with -DHASH_EMIT_KEYS, length-prefixed keys are emitted to * the descriptor to which this macro is defined for tuning the hash function. * The app can #include <unistd.h> to get the prototype for write(2). */ #ifdef HASH_EMIT_KEYS #define HASH_EMIT_KEY … #else #define HASH_EMIT_KEY(hh,head,keyptr,fieldlen) … #endif /* default to Jenkin's hash unless overridden e.g. DHASH_FUNCTION=HASH_SAX */ #ifdef HASH_FUNCTION #define HASH_FCN … #else #define HASH_FCN … #endif /* The Bernstein hash function, used in Perl prior to v5.6 */ #define HASH_BER(key,keylen,num_bkts,hashv,bkt) … /* SAX/FNV/OAT/JEN hash functions are macro variants of those listed at * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx */ #define HASH_SAX(key,keylen,num_bkts,hashv,bkt) … #define HASH_FNV(key,keylen,num_bkts,hashv,bkt) … #define HASH_OAT(key,keylen,num_bkts,hashv,bkt) … #define HASH_JEN_MIX(a,b,c) … #define HASH_JEN(key,keylen,num_bkts,hashv,bkt) … /* The Paul Hsieh hash function */ #undef get16bits #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) #define get16bits … #endif #if !defined (get16bits) #define get16bits(d) … #endif #define HASH_SFH(key,keylen,num_bkts,hashv,bkt) … #ifdef HASH_USING_NO_STRICT_ALIASING /* The MurmurHash exploits some CPU's (e.g. x86) tolerance for unaligned reads. * For other types of CPU's (e.g. Sparc) an unaligned read causes a bus error. * So MurmurHash comes in two versions, the faster unaligned one and the slower * aligned one. We only use the faster one on CPU's where we know it's safe. * * Note the preprocessor built-in defines can be emitted using: * * gcc -m64 -dM -E - < /dev/null (on gcc) * cc -## a.c (where a.c is a simple test file) (Sun Studio) */ #if (defined(__i386__) || defined(__x86_64__)) #define HASH_MUR … #else #define HASH_MUR … #endif /* Appleby's MurmurHash fast version for unaligned-tolerant archs like i386 */ #define HASH_MUR_UNALIGNED … /* Appleby's MurmurHash version for alignment-sensitive archs like Sparc */ #define HASH_MUR_ALIGNED … #endif /* HASH_USING_NO_STRICT_ALIASING */ /* key comparison function; return 0 if keys equal */ #define HASH_KEYCMP(a,b,len) … /* iterate over items in a known bucket to find desired item */ #define HASH_FIND_IN_BKT(tbl,hh,head,keyptr,keylen_in,out) … /* add an item to a bucket */ #define HASH_ADD_TO_BKT(head,addhh) … /* remove an item from a given bucket */ #define HASH_DEL_IN_BKT(hh,head,hh_del) … /* Bucket expansion has the effect of doubling the number of buckets * and redistributing the items into the new buckets. Ideally the * items will distribute more or less evenly into the new buckets * (the extent to which this is true is a measure of the quality of * the hash function as it applies to the key domain). * * With the items distributed into more buckets, the chain length * (item count) in each bucket is reduced. Thus by expanding buckets * the hash keeps a bound on the chain length. This bounded chain * length is the essence of how a hash provides constant time lookup. * * The calculation of tbl->ideal_chain_maxlen below deserves some * explanation. First, keep in mind that we're calculating the ideal * maximum chain length based on the *new* (doubled) bucket count. * In fractions this is just n/b (n=number of items,b=new num buckets). * Since the ideal chain length is an integer, we want to calculate * ceil(n/b). We don't depend on floating point arithmetic in this * hash, so to calculate ceil(n/b) with integers we could write * * ceil(n/b) = (n/b) + ((n%b)?1:0) * * and in fact a previous version of this hash did just that. * But now we have improved things a bit by recognizing that b is * always a power of two. We keep its base 2 log handy (call it lb), * so now we can write this with a bit shift and logical AND: * * ceil(n/b) = (n>>lb) + ( (n & (b-1)) ? 1:0) * */ #define HASH_EXPAND_BUCKETS(tbl) … /* This is an adaptation of Simon Tatham's O(n log(n)) mergesort */ /* Note that HASH_SORT assumes the hash handle name to be hh. * HASH_SRT was added to allow the hash handle name to be passed in. */ #define HASH_SORT(head,cmpfcn) … #define HASH_SRT(hh,head,cmpfcn) … /* This function selects items from one hash into another hash. * The end result is that the selected items have dual presence * in both hashes. There is no copy of the items made; rather * they are added into the new hash through a secondary hash * hash handle that must be present in the structure. */ #define HASH_SELECT(hh_dst, dst, hh_src, src, cond) … #define HASH_CLEAR(hh,head) … /* obtain a count of items in the hash */ #define HASH_COUNT(head) … #define HASH_CNT(hh,head) … UT_hash_bucket; /* random signature used only to find hash tables in external analysis */ #define HASH_SIGNATURE … #define HASH_BLOOM_SIGNATURE … UT_hash_table; UT_hash_handle; #endif /* UTHASH_H */
Codebase Browser
godot