99 #define SH_MAKE_PREFIX(a) CppConcat(a,_)
100 #define SH_MAKE_NAME(name) SH_MAKE_NAME_(SH_MAKE_PREFIX(SH_PREFIX),name)
101 #define SH_MAKE_NAME_(a,b) CppConcat(a,b)
106 #define SH_TYPE SH_MAKE_NAME(hash)
107 #define SH_STATUS SH_MAKE_NAME(status)
108 #define SH_STATUS_EMPTY SH_MAKE_NAME(SH_EMPTY)
109 #define SH_STATUS_IN_USE SH_MAKE_NAME(SH_IN_USE)
110 #define SH_ITERATOR SH_MAKE_NAME(iterator)
113 #define SH_CREATE SH_MAKE_NAME(create)
114 #define SH_DESTROY SH_MAKE_NAME(destroy)
115 #define SH_RESET SH_MAKE_NAME(reset)
116 #define SH_INSERT SH_MAKE_NAME(insert)
117 #define SH_INSERT_HASH SH_MAKE_NAME(insert_hash)
118 #define SH_DELETE_ITEM SH_MAKE_NAME(delete_item)
119 #define SH_DELETE SH_MAKE_NAME(delete)
120 #define SH_LOOKUP SH_MAKE_NAME(lookup)
121 #define SH_LOOKUP_HASH SH_MAKE_NAME(lookup_hash)
122 #define SH_GROW SH_MAKE_NAME(grow)
123 #define SH_START_ITERATE SH_MAKE_NAME(start_iterate)
124 #define SH_START_ITERATE_AT SH_MAKE_NAME(start_iterate_at)
125 #define SH_ITERATE SH_MAKE_NAME(iterate)
126 #define SH_ALLOCATE SH_MAKE_NAME(allocate)
127 #define SH_FREE SH_MAKE_NAME(free)
128 #define SH_STAT SH_MAKE_NAME(stat)
131 #define SH_COMPUTE_PARAMETERS SH_MAKE_NAME(compute_parameters)
132 #define SH_NEXT SH_MAKE_NAME(next)
133 #define SH_PREV SH_MAKE_NAME(prev)
134 #define SH_DISTANCE_FROM_OPTIMAL SH_MAKE_NAME(distance)
135 #define SH_INITIAL_BUCKET SH_MAKE_NAME(initial_bucket)
136 #define SH_ENTRY_HASH SH_MAKE_NAME(entry_hash)
137 #define SH_INSERT_HASH_INTERNAL SH_MAKE_NAME(insert_hash_internal)
138 #define SH_LOOKUP_HASH_INTERNAL SH_MAKE_NAME(lookup_hash_internal)
165 #ifndef SH_RAW_ALLOCATOR
188 #ifdef SH_RAW_ALLOCATOR
253 #ifndef SH_RAW_ALLOCATOR
258 #define SH_MAX_SIZE (((uint64) PG_UINT32_MAX) + 1)
261 #ifndef SH_FILLFACTOR
262 #define SH_FILLFACTOR (0.9)
265 #define SH_MAX_FILLFACTOR (0.98)
267 #ifndef SH_GROW_MAX_DIB
268 #define SH_GROW_MAX_DIB 25
271 #ifndef SH_GROW_MAX_MOVE
272 #define SH_GROW_MAX_MOVE 150
274 #ifndef SH_GROW_MIN_FILLFACTOR
276 #define SH_GROW_MIN_FILLFACTOR 0.1
280 #define SH_COMPARE_KEYS(tb, ahash, akey, b) (ahash == SH_GET_HASH(tb, b) && SH_EQUAL(tb, b->SH_KEY, akey))
282 #define SH_COMPARE_KEYS(tb, ahash, akey, b) (SH_EQUAL(tb, b->SH_KEY, akey))
296 #define sh_error(...) pg_fatal(__VA_ARGS__)
297 #define sh_log(...) pg_log_info(__VA_ARGS__)
299 #define sh_error(...) elog(ERROR, __VA_ARGS__)
300 #define sh_log(...) elog(LOG, __VA_ARGS__)
315 size =
Max(newsize, 2);
319 Assert(size <= SH_MAX_SIZE);
326 sh_error(
"hash table too large");
336 if (tb->
size == SH_MAX_SIZE)
353 curelem = (curelem + 1) & tb->
sizemask;
355 Assert(curelem != startelem);
364 curelem = (curelem - 1) & tb->
sizemask;
366 Assert(curelem != startelem);
375 if (optimal <= bucket)
376 return bucket - optimal;
378 return (tb->
size + bucket) - optimal;
395 #ifndef SH_USE_NONDEFAULT_ALLOCATOR
401 #ifdef SH_RAW_ALLOCATOR
427 #ifdef SH_RAW_ALLOCATOR
438 #ifdef SH_RAW_ALLOCATOR
447 size =
Min((
double) SH_MAX_SIZE, ((
double) nelements) / SH_FILLFACTOR);
482 uint64 oldsize = tb->
size;
490 Assert(oldsize != SH_MAX_SIZE);
491 Assert(oldsize < newsize);
518 for (
i = 0;
i < oldsize;
i++)
541 copyelem = startelem;
542 for (
i = 0;
i < oldsize;
i++)
555 curelem = startelem2;
560 newentry = &newdata[curelem];
567 curelem =
SH_NEXT(tb, curelem, startelem2);
576 if (copyelem >= oldsize)
611 sh_error(
"hash table size exceeded");
653 if (SH_COMPARE_KEYS(tb,
hash,
key, entry))
664 if (insertdist > curdist)
667 uint32 emptyelem = curelem;
676 emptyelem =
SH_NEXT(tb, emptyelem, startelem);
677 emptyentry = &
data[emptyelem];
681 lastentry = emptyentry;
694 if (
unlikely(++emptydist > SH_GROW_MAX_MOVE) &&
695 ((
double) tb->
members / tb->
size) >= SH_GROW_MIN_FILLFACTOR)
709 moveelem = emptyelem;
710 while (moveelem != curelem)
714 moveelem =
SH_PREV(tb, moveelem, startelem);
715 moveentry = &
data[moveelem];
718 lastentry = moveentry;
733 curelem =
SH_NEXT(tb, curelem, startelem);
744 if (
unlikely(insertdist > SH_GROW_MAX_DIB) &&
745 ((
double) tb->
members / tb->
size) >= SH_GROW_MIN_FILLFACTOR)
785 uint32 curelem = startelem;
798 if (SH_COMPARE_KEYS(tb,
hash,
key, entry))
808 curelem =
SH_NEXT(tb, curelem, startelem);
843 uint32 curelem = startelem;
853 SH_COMPARE_KEYS(tb,
hash,
key, entry))
872 curelem =
SH_NEXT(tb, curelem, startelem);
873 curentry = &tb->
data[curelem];
885 if (curoptimal == curelem)
894 lastentry = curentry;
902 curelem =
SH_NEXT(tb, curelem, startelem);
918 curelem = entry - &tb->
data[0];
935 curelem =
SH_NEXT(tb, curelem, startelem);
936 curentry = &tb->
data[curelem];
948 if (curoptimal == curelem)
957 lastentry = curentry;
986 Assert(startelem < SH_MAX_SIZE);
992 iter->
cur = startelem;
1056 uint32 max_chain_length = 0;
1057 uint32 total_chain_length = 0;
1058 double avg_chain_length;
1063 uint32 total_collisions = 0;
1064 uint32 max_collisions = 0;
1065 double avg_collisions;
1067 for (
i = 0;
i < tb->
size;
i++)
1074 elem = &tb->
data[
i];
1083 if (dist > max_chain_length)
1084 max_chain_length = dist;
1085 total_chain_length += dist;
1087 collisions[optimal]++;
1090 for (
i = 0;
i < tb->
size;
i++)
1092 uint32 curcoll = collisions[
i];
1099 total_collisions += curcoll;
1100 if (curcoll > max_collisions)
1101 max_collisions = curcoll;
1107 avg_chain_length = ((double) total_chain_length) / tb->
members;
1108 avg_collisions = ((double) total_collisions) / tb->
members;
1113 avg_chain_length = 0;
1117 sh_log(
"size: " UINT64_FORMAT ", members: %u, filled: %f, total chain: %u, max chain: %u, avg chain: %f, total_collisions: %u, max_collisions: %u, avg_collisions: %f",
1119 total_collisions, max_collisions, avg_collisions);
1129 #undef SH_ELEMENT_TYPE
1135 #undef SH_STORE_HASH
1136 #undef SH_USE_NONDEFAULT_ALLOCATOR
1140 #undef SH_MAKE_PREFIX
1142 #undef SH_MAKE_NAME_
1143 #undef SH_FILLFACTOR
1144 #undef SH_MAX_FILLFACTOR
1145 #undef SH_GROW_MAX_DIB
1146 #undef SH_GROW_MAX_MOVE
1147 #undef SH_GROW_MIN_FILLFACTOR
1153 #undef SH_STATUS_EMPTY
1154 #undef SH_STATUS_IN_USE
1162 #undef SH_INSERT_HASH
1163 #undef SH_DELETE_ITEM
1166 #undef SH_LOOKUP_HASH
1168 #undef SH_START_ITERATE
1169 #undef SH_START_ITERATE_AT
1176 #undef SH_COMPUTE_PARAMETERS
1177 #undef SH_COMPARE_KEYS
1178 #undef SH_INITIAL_BUCKET
1181 #undef SH_DISTANCE_FROM_OPTIMAL
1182 #undef SH_ENTRY_HASH
1183 #undef SH_INSERT_HASH_INTERNAL
1184 #undef SH_LOOKUP_HASH_INTERNAL
#define SH_HASH_KEY(tb, key)
#define SH_GET_HASH(tb, a)
if(TABLE==NULL||TABLE_index==NULL)
Assert(fmt[strlen(fmt) - 1] !='\n')
void pfree(void *pointer)
void * palloc0(Size size)
void * MemoryContextAllocZero(MemoryContext context, Size size)
void * MemoryContextAllocExtended(MemoryContext context, Size size, int flags)
static uint64 pg_nextpower2_64(uint64 num)
static unsigned hash(unsigned *uv, int n)
#define SH_INITIAL_BUCKET
#define SH_COMPUTE_PARAMETERS
#define SH_DISTANCE_FROM_OPTIMAL
#define SH_LOOKUP_HASH_INTERNAL
#define SH_INSERT_HASH_INTERNAL
#define SH_START_ITERATE_AT