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
217 uint32 hash,
bool *found);
253#ifndef SH_RAW_ALLOCATOR
254#include "utils/memutils.h"
258#define SH_MAX_SIZE (((uint64) PG_UINT32_MAX) + 1)
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");
330 tb->sizemask = (
uint32) (size - 1);
336 if (tb->size == SH_MAX_SIZE)
337 tb->grow_threshold = ((double) tb->size) * SH_MAX_FILLFACTOR;
339 tb->grow_threshold = ((double) tb->size) * SH_FILLFACTOR;
346 return hash & tb->sizemask;
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;
385 return SH_GET_HASH(tb, entry);
395#ifndef SH_USE_NONDEFAULT_ALLOCATOR
401#ifdef SH_RAW_ALLOCATOR
402 return SH_RAW_ALLOCATOR(size);
404 return MemoryContextAllocExtended(type->ctx, size,
405 MCXT_ALLOC_HUGE | MCXT_ALLOC_ZERO);
427#ifdef SH_RAW_ALLOCATOR
438#ifdef SH_RAW_ALLOCATOR
444 tb->private_data = private_data;
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++)
560 newentry = &newdata[curelem];
567 curelem =
SH_NEXT(tb, curelem, startelem);
576 if (copyelem >= oldsize)
608 if (
unlikely(tb->members >= tb->grow_threshold))
610 if (
unlikely(tb->size == SH_MAX_SIZE))
611 sh_error(
"hash table size exceeded");
638 SH_GET_HASH(tb, entry) = hash;
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)
697 tb->grow_threshold = 0;
709 moveelem = emptyelem;
710 while (moveelem != curelem)
714 moveelem =
SH_PREV(tb, moveelem, startelem);
715 moveentry = &data[moveelem];
718 lastentry = moveentry;
726 SH_GET_HASH(tb, entry) = hash;
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)
747 tb->grow_threshold = 0;
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;
975 for (i = 0; i < tb->size; i++)
986 Assert(startelem < SH_MAX_SIZE);
992 iter->cur = startelem;
993 iter->end = iter->cur;
1011 iter->cur = at & tb->sizemask;
1012 iter->end = iter->cur;
1033 elem = &tb->data[iter->cur];
1036 iter->cur = (iter->cur - 1) & tb->sizemask;
1038 if ((iter->cur & tb->sizemask) == (iter->end & tb->sizemask))
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;
1104 if (tb->members > 0)
1106 fillfactor = tb->members / ((double) tb->size);
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",
1118 tb->size, tb->members, fillfactor, total_chain_length, max_chain_length, avg_chain_length,
1119 total_collisions, max_collisions, avg_collisions);
1129#undef SH_ELEMENT_TYPE
1136#undef SH_USE_NONDEFAULT_ALLOCATOR
1140#undef SH_MAKE_PREFIX
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
1183#undef SH_INSERT_HASH_INTERNAL
1184#undef SH_LOOKUP_HASH_INTERNAL
#define Min(x, y)
Definition: c.h:993
#define Max(x, y)
Definition: c.h:987
#define Assert(condition)
Definition: c.h:811
#define UINT64_FORMAT
Definition: c.h:489
#define unlikely(x)
Definition: c.h:274
#define PG_UINT64_MAX
Definition: c.h:533
size_t Size
Definition: c.h:545
if(${POSTGRESQL_VERSION_NUMBER} GREATER_EQUAL 110000) set(072_tpoint_spgist 072_tpoint_spgist) endif() SET(LOCAL_FILES 050_geoset 050_stbox 051_tpoint 052_tpoint_inout 054_tpoint_compops 055_geography_functions 056_tpoint_spatialfuncs 057_tpoint_tile 058_tpoint_boxops 060_tpoint_posops 062_tpoint_distance 063_tpoint_similarity 064_tpoint_aggfuncs 066_tpoint_spatialrels 068_tpoint_tempspatialrels 070_tpoint_gist $
Definition: CMakeLists.txt:3
#define SH_HASH_KEY(tb, key)
Definition: meos_catalog.c:98
#define SH_ELEMENT_TYPE
Definition: meos_catalog.c:95
#define SH_KEY_TYPE
Definition: meos_catalog.c:96
#define SH_SCOPE
Definition: meos_catalog.c:100
static uint64 pg_nextpower2_64(uint64 num)
Definition: pg_bitutils.h:169
unsigned int uint32
Definition: pg_ext_defs.in.h:13
signed int int32
Definition: pg_ext_defs.in.h:8
unsigned long int uint64
Definition: pg_ext_defs.in.h:14
#define palloc0(X)
Definition: postgres.h:62
#define pfree
Definition: postgres.h:65
#define SH_GROW
Definition: simplehash.h:122
#define SH_STAT
Definition: simplehash.h:128
#define SH_INITIAL_BUCKET
Definition: simplehash.h:135
#define SH_INSERT_HASH
Definition: simplehash.h:117
#define SH_PREV
Definition: simplehash.h:133
#define SH_STATUS
Definition: simplehash.h:107
#define SH_CREATE
Definition: simplehash.h:113
#define SH_LOOKUP_HASH
Definition: simplehash.h:121
#define SH_START_ITERATE
Definition: simplehash.h:123
#define SH_COMPUTE_PARAMETERS
Definition: simplehash.h:131
#define SH_FREE
Definition: simplehash.h:127
#define SH_STATUS_IN_USE
Definition: simplehash.h:109
#define SH_DISTANCE_FROM_OPTIMAL
Definition: simplehash.h:134
#define SH_LOOKUP_HASH_INTERNAL
Definition: simplehash.h:138
#define SH_ITERATOR
Definition: simplehash.h:110
#define SH_NEXT
Definition: simplehash.h:132
#define SH_ITERATE
Definition: simplehash.h:125
#define SH_DELETE
Definition: simplehash.h:119
#define SH_INSERT
Definition: simplehash.h:116
#define SH_INSERT_HASH_INTERNAL
Definition: simplehash.h:137
#define SH_RESET
Definition: simplehash.h:115
#define SH_ENTRY_HASH
Definition: simplehash.h:136
#define SH_DELETE_ITEM
Definition: simplehash.h:118
#define SH_ALLOCATE
Definition: simplehash.h:126
#define SH_LOOKUP
Definition: simplehash.h:120
#define SH_TYPE
Definition: simplehash.h:106
#define SH_START_ITERATE_AT
Definition: simplehash.h:124
#define SH_STATUS_EMPTY
Definition: simplehash.h:108
#define SH_DESTROY
Definition: simplehash.h:114