61 #define DSHASH_NUM_PARTITIONS_LOG2 7
62 #define DSHASH_NUM_PARTITIONS (1 << DSHASH_NUM_PARTITIONS_LOG2)
65 #define DSHASH_MAGIC 0x75ff6a20
118 #define ENTRY_FROM_ITEM(item) \
119 ((char *)(item) + MAXALIGN(sizeof(dshash_table_item)))
122 #define ITEM_FROM_ENTRY(entry) \
123 ((dshash_table_item *)((char *)(entry) - \
124 MAXALIGN(sizeof(dshash_table_item))))
127 #define NUM_SPLITS(size_log2) \
128 (size_log2 - DSHASH_NUM_PARTITIONS_LOG2)
131 #define NUM_BUCKETS(size_log2) \
132 (((size_t) 1) << (size_log2))
135 #define BUCKETS_PER_PARTITION(size_log2) \
136 (((size_t) 1) << NUM_SPLITS(size_log2))
139 #define MAX_COUNT_PER_PARTITION(hash_table) \
140 (BUCKETS_PER_PARTITION(hash_table->size_log2) / 2 + \
141 BUCKETS_PER_PARTITION(hash_table->size_log2) / 4)
144 #define PARTITION_FOR_HASH(hash) \
145 (hash >> ((sizeof(dshash_hash) * CHAR_BIT) - DSHASH_NUM_PARTITIONS_LOG2))
153 #define BUCKET_INDEX_FOR_HASH_AND_SIZE(hash, size_log2) \
154 (hash >> ((sizeof(dshash_hash) * CHAR_BIT) - (size_log2)))
157 #define BUCKET_INDEX_FOR_PARTITION(partition, size_log2) \
158 ((partition) << NUM_SPLITS(size_log2))
161 #define PARTITION_FOR_BUCKET_INDEX(bucket_idx, size_log2) \
162 ((bucket_idx) >> NUM_SPLITS(size_log2))
165 #define BUCKET_FOR_HASH(hash_table, hash) \
166 (hash_table->buckets[ \
167 BUCKET_INDEX_FOR_HASH_AND_SIZE(hash, \
168 hash_table->size_log2)])
192 const void *
a,
const void *
b);
194 #define PARTITION_LOCK(hash_table, i) \
195 (&(hash_table)->control->partitions[(i)].lock)
216 hash_table->
area = area;
217 hash_table->
params = *params;
253 (
errcode(ERRCODE_OUT_OF_MEMORY),
255 errdetail(
"Failed on DSA request of size %zu.",
284 hash_table->
area = area;
285 hash_table->
params = *params;
336 for (
i = 0;
i < size; ++
i)
346 next_item_pointer = item->
next;
348 item_pointer = next_item_pointer;
443 size_t partition_index;
591 return memcmp(
a,
b, size);
615 status->hash_table = hash_table;
620 status->curpartition = -1;
621 status->exclusive = exclusive;
644 if (
status->curpartition == -1)
659 next_item_pointer =
status->hash_table->buckets[
status->curbucket];
662 next_item_pointer =
status->pnextitem;
682 status->hash_table->size_log2);
684 if (
status->curpartition != next_partition)
697 status->curpartition = next_partition;
700 next_item_pointer =
status->hash_table->buckets[
status->curbucket];
705 status->hash_table->find_locked =
true;
706 status->hash_table->find_exclusively_locked =
status->exclusive;
725 status->hash_table->find_locked =
false;
726 status->hash_table->find_exclusively_locked =
false;
728 if (
status->curpartition >= 0)
776 "hash table size = %zu\n", (
size_t) 1 << hash_table->
size_log2);
783 fprintf(stderr,
" partition %zu\n",
i);
785 " active buckets (key count = %zu)\n", partition->
count);
787 for (
j = begin;
j < end; ++
j)
801 fprintf(stderr,
" bucket %zu (key count = %zu)\n",
j, count);
845 size_t new_size = ((size_t) 1) << new_size_log2;
880 for (
i = 0;
i < size; ++
i)
890 next_item_pointer = item->
next;
894 item_pointer = next_item_pointer;
902 hash_table->
buckets = new_buckets;
940 item_pointer = item->
next;
956 item->
next = *bucket;
957 *bucket = item_pointer;
1001 *bucket_head =
next;
1005 bucket_head = &item->
next;
1024 if (bucket_item == item)
1030 *bucket_head =
next;
1033 bucket_head = &bucket_item->
next;
1057 hash_table->
arg) == 0;
#define PG_USED_FOR_ASSERTS_ONLY
dsa_pointer dsa_allocate_extended(dsa_area *area, size_t size, int flags)
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
void dsa_free(dsa_area *area, dsa_pointer dp)
#define dsa_allocate0(area, size)
#define dsa_allocate(area, size)
#define InvalidDsaPointer
#define DsaPointerIsValid(x)
bool dshash_delete_key(dshash_table *hash_table, const void *key)
void dshash_delete_entry(dshash_table *hash_table, void *entry)
void dshash_destroy(dshash_table *hash_table)
void dshash_release_lock(dshash_table *hash_table, void *entry)
#define PARTITION_LOCK(hash_table, i)
void dshash_detach(dshash_table *hash_table)
void dshash_seq_init(dshash_seq_status *status, dshash_table *hash_table, bool exclusive)
static void resize(dshash_table *hash_table, size_t new_size)
#define BUCKET_INDEX_FOR_HASH_AND_SIZE(hash, size_log2)
static bool delete_key_from_bucket(dshash_table *hash_table, const void *key, dsa_pointer *bucket_head)
void * dshash_find(dshash_table *hash_table, const void *key, bool exclusive)
static dshash_hash hash_key(dshash_table *hash_table, const void *key)
#define ITEM_FROM_ENTRY(entry)
dshash_table_handle dshash_get_hash_table_handle(dshash_table *hash_table)
void dshash_dump(dshash_table *hash_table)
static bool equal_keys(dshash_table *hash_table, const void *a, const void *b)
void dshash_seq_term(dshash_seq_status *status)
static void insert_item_into_bucket(dshash_table *hash_table, dsa_pointer item_pointer, dshash_table_item *item, dsa_pointer *bucket)
static bool delete_item_from_bucket(dshash_table *hash_table, dshash_table_item *item, dsa_pointer *bucket_head)
#define DSHASH_NUM_PARTITIONS
#define PARTITION_FOR_BUCKET_INDEX(bucket_idx, size_log2)
static dshash_table_item * insert_into_bucket(dshash_table *hash_table, const void *key, dsa_pointer *bucket)
#define BUCKET_INDEX_FOR_PARTITION(partition, size_log2)
#define MAX_COUNT_PER_PARTITION(hash_table)
#define ENTRY_FROM_ITEM(item)
#define DSHASH_NUM_PARTITIONS_LOG2
static void delete_item(dshash_table *hash_table, dshash_table_item *item)
dshash_hash dshash_memhash(const void *v, size_t size, void *arg)
#define NUM_BUCKETS(size_log2)
static void ensure_valid_bucket_pointers(dshash_table *hash_table)
static dshash_table_item * find_in_bucket(dshash_table *hash_table, const void *key, dsa_pointer item_pointer)
void * dshash_find_or_insert(dshash_table *hash_table, const void *key, bool *found)
dshash_table * dshash_attach(dsa_area *area, const dshash_parameters *params, dshash_table_handle handle, void *arg)
int dshash_memcmp(const void *a, const void *b, size_t size, void *arg)
struct dshash_table_control dshash_table_control
dshash_table * dshash_create(dsa_area *area, const dshash_parameters *params, void *arg)
#define PARTITION_FOR_HASH(hash)
struct dshash_partition dshash_partition
void * dshash_seq_next(dshash_seq_status *status)
#define BUCKET_FOR_HASH(hash_table, hash)
void dshash_delete_current(dshash_seq_status *status)
dsa_pointer dshash_table_handle
int errdetail(const char *fmt,...)
int errcode(int sqlerrcode)
int errmsg(const char *fmt,...)
#define ereport(elevel,...)
uint32 tag_hash(const void *key, Size keysize)
Assert(fmt[strlen(fmt) - 1] !='\n')
bool LWLockAcquire(LWLock *lock, LWLockMode mode)
void LWLockRelease(LWLock *lock)
bool LWLockHeldByMeInMode(LWLock *l, LWLockMode mode)
void LWLockInitialize(LWLock *lock, int tranche_id)
bool LWLockHeldByMe(LWLock *l)
void pfree(void *pointer)
static void static void status(const char *fmt,...) pg_attribute_printf(1
static unsigned hash(unsigned *uv, int n)
dshash_hash_function hash_function
dshash_compare_function compare_function
dshash_partition partitions[DSHASH_NUM_PARTITIONS]
dshash_table_handle handle
bool find_exclusively_locked
dshash_table_control * control