PostgreSQL Source Code  git master
dshash.c File Reference
#include "postgres.h"
#include "lib/dshash.h"
#include "storage/ipc.h"
#include "storage/lwlock.h"
#include "utils/dsa.h"
#include "utils/hsearch.h"
#include "utils/memutils.h"
Include dependency graph for dshash.c:

Go to the source code of this file.

Data Structures

struct  dshash_table_item
 
struct  dshash_partition
 
struct  dshash_table_control
 
struct  dshash_table
 

Macros

#define DSHASH_NUM_PARTITIONS_LOG2   7
 
#define DSHASH_NUM_PARTITIONS   (1 << DSHASH_NUM_PARTITIONS_LOG2)
 
#define DSHASH_MAGIC   0x75ff6a20
 
#define ENTRY_FROM_ITEM(item)   ((char *)(item) + MAXALIGN(sizeof(dshash_table_item)))
 
#define ITEM_FROM_ENTRY(entry)
 
#define NUM_SPLITS(size_log2)   (size_log2 - DSHASH_NUM_PARTITIONS_LOG2)
 
#define BUCKETS_PER_PARTITION(size_log2)   (((size_t) 1) << NUM_SPLITS(size_log2))
 
#define MAX_COUNT_PER_PARTITION(hash_table)
 
#define PARTITION_FOR_HASH(hash)   (hash >> ((sizeof(dshash_hash) * CHAR_BIT) - DSHASH_NUM_PARTITIONS_LOG2))
 
#define BUCKET_INDEX_FOR_HASH_AND_SIZE(hash, size_log2)   (hash >> ((sizeof(dshash_hash) * CHAR_BIT) - (size_log2)))
 
#define BUCKET_INDEX_FOR_PARTITION(partition, size_log2)   ((partition) << NUM_SPLITS(size_log2))
 
#define BUCKET_FOR_HASH(hash_table, hash)
 
#define PARTITION_LOCK(hash_table, i)   (&(hash_table)->control->partitions[(i)].lock)
 

Typedefs

typedef struct dshash_partition dshash_partition
 
typedef struct dshash_table_control dshash_table_control
 

Functions

static void delete_item (dshash_table *hash_table, dshash_table_item *item)
 
static void resize (dshash_table *hash_table, size_t new_size)
 
static void ensure_valid_bucket_pointers (dshash_table *hash_table)
 
static dshash_table_itemfind_in_bucket (dshash_table *hash_table, const void *key, dsa_pointer item_pointer)
 
static void insert_item_into_bucket (dshash_table *hash_table, dsa_pointer item_pointer, dshash_table_item *item, dsa_pointer *bucket)
 
static dshash_table_iteminsert_into_bucket (dshash_table *hash_table, const void *key, dsa_pointer *bucket)
 
static bool delete_key_from_bucket (dshash_table *hash_table, const void *key, dsa_pointer *bucket_head)
 
static bool delete_item_from_bucket (dshash_table *hash_table, dshash_table_item *item, dsa_pointer *bucket_head)
 
static dshash_hash hash_key (dshash_table *hash_table, const void *key)
 
static bool equal_keys (dshash_table *hash_table, const void *a, const void *b)
 
dshash_tabledshash_create (dsa_area *area, const dshash_parameters *params, void *arg)
 
dshash_tabledshash_attach (dsa_area *area, const dshash_parameters *params, dshash_table_handle handle, void *arg)
 
void dshash_detach (dshash_table *hash_table)
 
void dshash_destroy (dshash_table *hash_table)
 
dshash_table_handle dshash_get_hash_table_handle (dshash_table *hash_table)
 
void * dshash_find (dshash_table *hash_table, const void *key, bool exclusive)
 
void * dshash_find_or_insert (dshash_table *hash_table, const void *key, bool *found)
 
bool dshash_delete_key (dshash_table *hash_table, const void *key)
 
void dshash_delete_entry (dshash_table *hash_table, void *entry)
 
void dshash_release_lock (dshash_table *hash_table, void *entry)
 
int dshash_memcmp (const void *a, const void *b, size_t size, void *arg)
 
dshash_hash dshash_memhash (const void *v, size_t size, void *arg)
 
void dshash_dump (dshash_table *hash_table)
 

Macro Definition Documentation

◆ BUCKET_FOR_HASH

#define BUCKET_FOR_HASH (   hash_table,
  hash 
)
Value:
(hash_table->buckets[ \
BUCKET_INDEX_FOR_HASH_AND_SIZE(hash, \
hash_table->size_log2)])
static unsigned hash(unsigned *uv, int n)
Definition: rege_dfa.c:541

Definition at line 157 of file dshash.c.

Referenced by delete_item(), dshash_delete_key(), dshash_find(), and dshash_find_or_insert().

◆ BUCKET_INDEX_FOR_HASH_AND_SIZE

#define BUCKET_INDEX_FOR_HASH_AND_SIZE (   hash,
  size_log2 
)    (hash >> ((sizeof(dshash_hash) * CHAR_BIT) - (size_log2)))

Definition at line 149 of file dshash.c.

Referenced by resize().

◆ BUCKET_INDEX_FOR_PARTITION

#define BUCKET_INDEX_FOR_PARTITION (   partition,
  size_log2 
)    ((partition) << NUM_SPLITS(size_log2))

Definition at line 153 of file dshash.c.

Referenced by dshash_dump().

◆ BUCKETS_PER_PARTITION

#define BUCKETS_PER_PARTITION (   size_log2)    (((size_t) 1) << NUM_SPLITS(size_log2))

Definition at line 131 of file dshash.c.

◆ DSHASH_MAGIC

◆ DSHASH_NUM_PARTITIONS

#define DSHASH_NUM_PARTITIONS   (1 << DSHASH_NUM_PARTITIONS_LOG2)

Definition at line 62 of file dshash.c.

Referenced by dshash_create(), dshash_dump(), and resize().

◆ DSHASH_NUM_PARTITIONS_LOG2

#define DSHASH_NUM_PARTITIONS_LOG2   7

Definition at line 61 of file dshash.c.

Referenced by dshash_create().

◆ ENTRY_FROM_ITEM

#define ENTRY_FROM_ITEM (   item)    ((char *)(item) + MAXALIGN(sizeof(dshash_table_item)))

◆ ITEM_FROM_ENTRY

#define ITEM_FROM_ENTRY (   entry)
Value:
((dshash_table_item *)((char *)(entry) - \
#define MAXALIGN(LEN)
Definition: c.h:692

Definition at line 122 of file dshash.c.

Referenced by dshash_delete_entry(), and dshash_release_lock().

◆ MAX_COUNT_PER_PARTITION

#define MAX_COUNT_PER_PARTITION (   hash_table)
Value:
(BUCKETS_PER_PARTITION(hash_table->size_log2) / 2 + \
BUCKETS_PER_PARTITION(hash_table->size_log2) / 4)
#define BUCKETS_PER_PARTITION(size_log2)
Definition: dshash.c:131

Definition at line 135 of file dshash.c.

Referenced by dshash_find_or_insert().

◆ NUM_SPLITS

#define NUM_SPLITS (   size_log2)    (size_log2 - DSHASH_NUM_PARTITIONS_LOG2)

Definition at line 127 of file dshash.c.

◆ PARTITION_FOR_HASH

#define PARTITION_FOR_HASH (   hash)    (hash >> ((sizeof(dshash_hash) * CHAR_BIT) - DSHASH_NUM_PARTITIONS_LOG2))

◆ PARTITION_LOCK

#define PARTITION_LOCK (   hash_table,
  i 
)    (&(hash_table)->control->partitions[(i)].lock)

Typedef Documentation

◆ dshash_partition

◆ dshash_table_control

Function Documentation

◆ delete_item()

static void delete_item ( dshash_table hash_table,
dshash_table_item item 
)
static

Definition at line 654 of file dshash.c.

References Assert, BUCKET_FOR_HASH, dshash_table::control, dshash_partition::count, delete_item_from_bucket(), dshash_table_item::hash, LWLockHeldByMe(), PARTITION_FOR_HASH, PARTITION_LOCK, and dshash_table_control::partitions.

Referenced by dshash_delete_entry().

655 {
656  size_t hash = item->hash;
657  size_t partition = PARTITION_FOR_HASH(hash);
658 
659  Assert(LWLockHeldByMe(PARTITION_LOCK(hash_table, partition)));
660 
661  if (delete_item_from_bucket(hash_table, item,
662  &BUCKET_FOR_HASH(hash_table, hash)))
663  {
664  Assert(hash_table->control->partitions[partition].count > 0);
665  --hash_table->control->partitions[partition].count;
666  }
667  else
668  {
669  Assert(false);
670  }
671 }
bool LWLockHeldByMe(LWLock *l)
Definition: lwlock.c:1842
#define BUCKET_FOR_HASH(hash_table, hash)
Definition: dshash.c:157
dshash_partition partitions[DSHASH_NUM_PARTITIONS]
Definition: dshash.c:89
#define PARTITION_FOR_HASH(hash)
Definition: dshash.c:140
dshash_table_control * control
Definition: dshash.c:110
#define Assert(condition)
Definition: c.h:739
size_t count
Definition: dshash.c:78
dshash_hash hash
Definition: dshash.c:51
static bool delete_item_from_bucket(dshash_table *hash_table, dshash_table_item *item, dsa_pointer *bucket_head)
Definition: dshash.c:855
static unsigned hash(unsigned *uv, int n)
Definition: rege_dfa.c:541
#define PARTITION_LOCK(hash_table, i)
Definition: dshash.c:186

◆ delete_item_from_bucket()

static bool delete_item_from_bucket ( dshash_table hash_table,
dshash_table_item item,
dsa_pointer bucket_head 
)
static

Definition at line 855 of file dshash.c.

References dshash_table::area, dsa_free(), dsa_get_address(), DsaPointerIsValid, and dshash_table_item::next.

Referenced by delete_item().

858 {
859  while (DsaPointerIsValid(*bucket_head))
860  {
861  dshash_table_item *bucket_item;
862 
863  bucket_item = dsa_get_address(hash_table->area, *bucket_head);
864 
865  if (bucket_item == item)
866  {
868 
869  next = item->next;
870  dsa_free(hash_table->area, *bucket_head);
871  *bucket_head = next;
872  return true;
873  }
874  bucket_head = &bucket_item->next;
875  }
876  return false;
877 }
static int32 next
Definition: blutils.c:213
uint64 dsa_pointer
Definition: dsa.h:62
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:932
dsa_area * area
Definition: dshash.c:107
#define DsaPointerIsValid(x)
Definition: dsa.h:81
dsa_pointer next
Definition: dshash.c:49
void dsa_free(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:820

◆ delete_key_from_bucket()

static bool delete_key_from_bucket ( dshash_table hash_table,
const void *  key,
dsa_pointer bucket_head 
)
static

Definition at line 826 of file dshash.c.

References dshash_table::area, dsa_free(), dsa_get_address(), DsaPointerIsValid, ENTRY_FROM_ITEM, equal_keys(), and dshash_table_item::next.

Referenced by dshash_delete_key().

829 {
830  while (DsaPointerIsValid(*bucket_head))
831  {
832  dshash_table_item *item;
833 
834  item = dsa_get_address(hash_table->area, *bucket_head);
835 
836  if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
837  {
839 
840  next = item->next;
841  dsa_free(hash_table->area, *bucket_head);
842  *bucket_head = next;
843 
844  return true;
845  }
846  bucket_head = &item->next;
847  }
848  return false;
849 }
static int32 next
Definition: blutils.c:213
uint64 dsa_pointer
Definition: dsa.h:62
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:932
dsa_area * area
Definition: dshash.c:107
static bool equal_keys(dshash_table *hash_table, const void *a, const void *b)
Definition: dshash.c:894
#define DsaPointerIsValid(x)
Definition: dsa.h:81
dsa_pointer next
Definition: dshash.c:49
void dsa_free(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:820
#define ENTRY_FROM_ITEM(item)
Definition: dshash.c:118

◆ dshash_attach()

dshash_table* dshash_attach ( dsa_area area,
const dshash_parameters params,
dshash_table_handle  handle,
void *  arg 
)

Definition at line 263 of file dshash.c.

References dshash_table::area, arg, dshash_table::arg, Assert, dshash_table::buckets, dshash_table::control, dsa_get_address(), DSHASH_MAGIC, dshash_table::find_exclusively_locked, dshash_table::find_locked, dshash_table_control::magic, palloc(), dshash_table::params, and dshash_table::size_log2.

Referenced by SharedRecordTypmodRegistryAttach().

265 {
266  dshash_table *hash_table;
267  dsa_pointer control;
268 
269  /* Allocate the backend-local object representing the hash table. */
270  hash_table = palloc(sizeof(dshash_table));
271 
272  /* Find the control object in shared memory. */
273  control = handle;
274 
275  /* Set up the local hash table struct. */
276  hash_table->area = area;
277  hash_table->params = *params;
278  hash_table->arg = arg;
279  hash_table->control = dsa_get_address(area, control);
280  hash_table->find_locked = false;
281  hash_table->find_exclusively_locked = false;
282  Assert(hash_table->control->magic == DSHASH_MAGIC);
283 
284  /*
285  * These will later be set to the correct values by
286  * ensure_valid_bucket_pointers(), at which time we'll be holding a
287  * partition lock for interlocking against concurrent resizing.
288  */
289  hash_table->buckets = NULL;
290  hash_table->size_log2 = 0;
291 
292  return hash_table;
293 }
bool find_exclusively_locked
Definition: dshash.c:114
uint64 dsa_pointer
Definition: dsa.h:62
dshash_parameters params
Definition: dshash.c:108
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:932
#define DSHASH_MAGIC
Definition: dshash.c:65
dsa_pointer * buckets
Definition: dshash.c:111
dsa_area * area
Definition: dshash.c:107
void * arg
Definition: dshash.c:109
bool find_locked
Definition: dshash.c:113
dshash_table_control * control
Definition: dshash.c:110
#define Assert(condition)
Definition: c.h:739
size_t size_log2
Definition: dshash.c:112
void * palloc(Size size)
Definition: mcxt.c:949
void * arg

◆ dshash_create()

dshash_table* dshash_create ( dsa_area area,
const dshash_parameters params,
void *  arg 
)

Definition at line 196 of file dshash.c.

References dshash_table::area, arg, dshash_table::arg, dshash_table_control::buckets, dshash_table::buckets, dshash_table::control, dshash_partition::count, DSA_ALLOC_NO_OOM, DSA_ALLOC_ZERO, dsa_allocate, dsa_allocate_extended(), dsa_free(), dsa_get_address(), DsaPointerIsValid, DSHASH_MAGIC, DSHASH_NUM_PARTITIONS, DSHASH_NUM_PARTITIONS_LOG2, ereport, errcode(), errdetail(), errmsg(), ERROR, dshash_table::find_exclusively_locked, dshash_table::find_locked, dshash_table_control::handle, i, dshash_table_control::lwlock_tranche_id, LWLockInitialize(), dshash_table_control::magic, palloc(), dshash_table::params, dshash_table_control::partitions, partitions, dshash_table_control::size_log2, dshash_table::size_log2, and dshash_parameters::tranche_id.

Referenced by SharedRecordTypmodRegistryInit().

197 {
198  dshash_table *hash_table;
199  dsa_pointer control;
200 
201  /* Allocate the backend-local object representing the hash table. */
202  hash_table = palloc(sizeof(dshash_table));
203 
204  /* Allocate the control object in shared memory. */
205  control = dsa_allocate(area, sizeof(dshash_table_control));
206 
207  /* Set up the local and shared hash table structs. */
208  hash_table->area = area;
209  hash_table->params = *params;
210  hash_table->arg = arg;
211  hash_table->control = dsa_get_address(area, control);
212  hash_table->control->handle = control;
213  hash_table->control->magic = DSHASH_MAGIC;
214  hash_table->control->lwlock_tranche_id = params->tranche_id;
215 
216  /* Set up the array of lock partitions. */
217  {
219  int tranche_id = hash_table->control->lwlock_tranche_id;
220  int i;
221 
222  for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
223  {
224  LWLockInitialize(&partitions[i].lock, tranche_id);
225  partitions[i].count = 0;
226  }
227  }
228 
229  hash_table->find_locked = false;
230  hash_table->find_exclusively_locked = false;
231 
232  /*
233  * Set up the initial array of buckets. Our initial size is the same as
234  * the number of partitions.
235  */
237  hash_table->control->buckets =
241  if (!DsaPointerIsValid(hash_table->control->buckets))
242  {
243  dsa_free(area, control);
244  ereport(ERROR,
245  (errcode(ERRCODE_OUT_OF_MEMORY),
246  errmsg("out of memory"),
247  errdetail("Failed on DSA request of size %zu.",
248  sizeof(dsa_pointer) * DSHASH_NUM_PARTITIONS)));
249  }
250  hash_table->buckets = dsa_get_address(area,
251  hash_table->control->buckets);
252  hash_table->size_log2 = hash_table->control->size_log2;
253 
254  return hash_table;
255 }
static int partitions
Definition: pgbench.c:196
dsa_pointer buckets
Definition: dshash.c:99
#define DSA_ALLOC_NO_OOM
Definition: dsa.h:74
#define DSHASH_NUM_PARTITIONS
Definition: dshash.c:62
#define DSA_ALLOC_ZERO
Definition: dsa.h:75
bool find_exclusively_locked
Definition: dshash.c:114
int errcode(int sqlerrcode)
Definition: elog.c:608
uint64 dsa_pointer
Definition: dsa.h:62
dshash_parameters params
Definition: dshash.c:108
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:932
#define ERROR
Definition: elog.h:43
#define DSHASH_MAGIC
Definition: dshash.c:65
size_t size_log2
Definition: dshash.c:98
int errdetail(const char *fmt,...)
Definition: elog.c:955
dsa_pointer * buckets
Definition: dshash.c:111
#define ereport(elevel, rest)
Definition: elog.h:141
dshash_partition partitions[DSHASH_NUM_PARTITIONS]
Definition: dshash.c:89
#define DSHASH_NUM_PARTITIONS_LOG2
Definition: dshash.c:61
void LWLockInitialize(LWLock *lock, int tranche_id)
Definition: lwlock.c:678
dsa_area * area
Definition: dshash.c:107
void * arg
Definition: dshash.c:109
bool find_locked
Definition: dshash.c:113
dshash_table_control * control
Definition: dshash.c:110
size_t count
Definition: dshash.c:78
size_t size_log2
Definition: dshash.c:112
#define DsaPointerIsValid(x)
Definition: dsa.h:81
dshash_table_handle handle
Definition: dshash.c:87
void dsa_free(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:820
void * palloc(Size size)
Definition: mcxt.c:949
int errmsg(const char *fmt,...)
Definition: elog.c:822
int i
void * arg
dsa_pointer dsa_allocate_extended(dsa_area *area, size_t size, int flags)
Definition: dsa.c:665
#define dsa_allocate(area, size)
Definition: dsa.h:84

◆ dshash_delete_entry()

void dshash_delete_entry ( dshash_table hash_table,
void *  entry 
)

Definition at line 540 of file dshash.c.

References Assert, dshash_table::control, delete_item(), DSHASH_MAGIC, dshash_table::find_exclusively_locked, dshash_table::find_locked, dshash_table_item::hash, ITEM_FROM_ENTRY, LW_EXCLUSIVE, LWLockHeldByMeInMode(), LWLockRelease(), dshash_table_control::magic, PARTITION_FOR_HASH, and PARTITION_LOCK.

541 {
542  dshash_table_item *item = ITEM_FROM_ENTRY(entry);
543  size_t partition = PARTITION_FOR_HASH(item->hash);
544 
545  Assert(hash_table->control->magic == DSHASH_MAGIC);
546  Assert(hash_table->find_locked);
547  Assert(hash_table->find_exclusively_locked);
548  Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
549  LW_EXCLUSIVE));
550 
551  delete_item(hash_table, item);
552  hash_table->find_locked = false;
553  hash_table->find_exclusively_locked = false;
554  LWLockRelease(PARTITION_LOCK(hash_table, partition));
555 }
bool LWLockHeldByMeInMode(LWLock *l, LWLockMode mode)
Definition: lwlock.c:1860
#define ITEM_FROM_ENTRY(entry)
Definition: dshash.c:122
bool find_exclusively_locked
Definition: dshash.c:114
void LWLockRelease(LWLock *lock)
Definition: lwlock.c:1726
#define DSHASH_MAGIC
Definition: dshash.c:65
#define PARTITION_FOR_HASH(hash)
Definition: dshash.c:140
static void delete_item(dshash_table *hash_table, dshash_table_item *item)
Definition: dshash.c:654
bool find_locked
Definition: dshash.c:113
dshash_table_control * control
Definition: dshash.c:110
#define Assert(condition)
Definition: c.h:739
dshash_hash hash
Definition: dshash.c:51
#define PARTITION_LOCK(hash_table, i)
Definition: dshash.c:186

◆ dshash_delete_key()

bool dshash_delete_key ( dshash_table hash_table,
const void *  key 
)

Definition at line 502 of file dshash.c.

References Assert, BUCKET_FOR_HASH, dshash_table::control, dshash_partition::count, delete_key_from_bucket(), DSHASH_MAGIC, ensure_valid_bucket_pointers(), dshash_table::find_locked, dshash_table_item::hash, hash_key(), LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), dshash_table_control::magic, PARTITION_FOR_HASH, PARTITION_LOCK, and dshash_table_control::partitions.

Referenced by find_or_make_matching_shared_tupledesc().

503 {
505  size_t partition;
506  bool found;
507 
508  Assert(hash_table->control->magic == DSHASH_MAGIC);
509  Assert(!hash_table->find_locked);
510 
511  hash = hash_key(hash_table, key);
512  partition = PARTITION_FOR_HASH(hash);
513 
514  LWLockAcquire(PARTITION_LOCK(hash_table, partition), LW_EXCLUSIVE);
515  ensure_valid_bucket_pointers(hash_table);
516 
517  if (delete_key_from_bucket(hash_table, key,
518  &BUCKET_FOR_HASH(hash_table, hash)))
519  {
520  Assert(hash_table->control->partitions[partition].count > 0);
521  found = true;
522  --hash_table->control->partitions[partition].count;
523  }
524  else
525  found = false;
526 
527  LWLockRelease(PARTITION_LOCK(hash_table, partition));
528 
529  return found;
530 }
uint32 dshash_hash
Definition: dshash.h:27
#define BUCKET_FOR_HASH(hash_table, hash)
Definition: dshash.c:157
void LWLockRelease(LWLock *lock)
Definition: lwlock.c:1726
#define DSHASH_MAGIC
Definition: dshash.c:65
dshash_partition partitions[DSHASH_NUM_PARTITIONS]
Definition: dshash.c:89
#define PARTITION_FOR_HASH(hash)
Definition: dshash.c:140
static bool delete_key_from_bucket(dshash_table *hash_table, const void *key, dsa_pointer *bucket_head)
Definition: dshash.c:826
bool find_locked
Definition: dshash.c:113
dshash_table_control * control
Definition: dshash.c:110
#define Assert(condition)
Definition: c.h:739
size_t count
Definition: dshash.c:78
bool LWLockAcquire(LWLock *lock, LWLockMode mode)
Definition: lwlock.c:1122
static dshash_hash hash_key(dshash_table *hash_table, const void *key)
Definition: dshash.c:883
static void ensure_valid_bucket_pointers(dshash_table *hash_table)
Definition: dshash.c:757
static unsigned hash(unsigned *uv, int n)
Definition: rege_dfa.c:541
#define PARTITION_LOCK(hash_table, i)
Definition: dshash.c:186

◆ dshash_destroy()

void dshash_destroy ( dshash_table hash_table)

Definition at line 318 of file dshash.c.

References dshash_table::area, Assert, dshash_table_control::buckets, dshash_table::buckets, dshash_table::control, dsa_free(), dsa_get_address(), DsaPointerIsValid, DSHASH_MAGIC, ensure_valid_bucket_pointers(), dshash_table_control::handle, i, dshash_table_control::magic, dshash_table_item::next, pfree(), and dshash_table::size_log2.

319 {
320  size_t size;
321  size_t i;
322 
323  Assert(hash_table->control->magic == DSHASH_MAGIC);
324  ensure_valid_bucket_pointers(hash_table);
325 
326  /* Free all the entries. */
327  size = ((size_t) 1) << hash_table->size_log2;
328  for (i = 0; i < size; ++i)
329  {
330  dsa_pointer item_pointer = hash_table->buckets[i];
331 
332  while (DsaPointerIsValid(item_pointer))
333  {
334  dshash_table_item *item;
335  dsa_pointer next_item_pointer;
336 
337  item = dsa_get_address(hash_table->area, item_pointer);
338  next_item_pointer = item->next;
339  dsa_free(hash_table->area, item_pointer);
340  item_pointer = next_item_pointer;
341  }
342  }
343 
344  /*
345  * Vandalize the control block to help catch programming errors where
346  * other backends access the memory formerly occupied by this hash table.
347  */
348  hash_table->control->magic = 0;
349 
350  /* Free the active table and control object. */
351  dsa_free(hash_table->area, hash_table->control->buckets);
352  dsa_free(hash_table->area, hash_table->control->handle);
353 
354  pfree(hash_table);
355 }
dsa_pointer buckets
Definition: dshash.c:99
uint64 dsa_pointer
Definition: dsa.h:62
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:932
void pfree(void *pointer)
Definition: mcxt.c:1056
#define DSHASH_MAGIC
Definition: dshash.c:65
dsa_pointer * buckets
Definition: dshash.c:111
dsa_area * area
Definition: dshash.c:107
dshash_table_control * control
Definition: dshash.c:110
#define Assert(condition)
Definition: c.h:739
size_t size_log2
Definition: dshash.c:112
#define DsaPointerIsValid(x)
Definition: dsa.h:81
dshash_table_handle handle
Definition: dshash.c:87
dsa_pointer next
Definition: dshash.c:49
void dsa_free(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:820
int i
static void ensure_valid_bucket_pointers(dshash_table *hash_table)
Definition: dshash.c:757

◆ dshash_detach()

void dshash_detach ( dshash_table hash_table)

Definition at line 302 of file dshash.c.

References Assert, dshash_table::find_locked, and pfree().

Referenced by shared_record_typmod_registry_detach().

303 {
304  Assert(!hash_table->find_locked);
305 
306  /* The hash table may have been destroyed. Just free local memory. */
307  pfree(hash_table);
308 }
void pfree(void *pointer)
Definition: mcxt.c:1056
bool find_locked
Definition: dshash.c:113
#define Assert(condition)
Definition: c.h:739

◆ dshash_dump()

void dshash_dump ( dshash_table hash_table)

Definition at line 600 of file dshash.c.

References dshash_table::area, Assert, BUCKET_INDEX_FOR_PARTITION, dshash_table::buckets, dshash_table::control, dshash_partition::count, dsa_get_address(), DsaPointerIsValid, DSHASH_MAGIC, DSHASH_NUM_PARTITIONS, ensure_valid_bucket_pointers(), dshash_table::find_locked, fprintf, i, LW_SHARED, LWLockAcquire(), LWLockHeldByMe(), LWLockRelease(), dshash_table_control::magic, dshash_table_item::next, PARTITION_LOCK, dshash_table_control::partitions, and dshash_table::size_log2.

601 {
602  size_t i;
603  size_t j;
604 
605  Assert(hash_table->control->magic == DSHASH_MAGIC);
606  Assert(!hash_table->find_locked);
607 
608  for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
609  {
610  Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
611  LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_SHARED);
612  }
613 
614  ensure_valid_bucket_pointers(hash_table);
615 
616  fprintf(stderr,
617  "hash table size = %zu\n", (size_t) 1 << hash_table->size_log2);
618  for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
619  {
620  dshash_partition *partition = &hash_table->control->partitions[i];
621  size_t begin = BUCKET_INDEX_FOR_PARTITION(i, hash_table->size_log2);
622  size_t end = BUCKET_INDEX_FOR_PARTITION(i + 1, hash_table->size_log2);
623 
624  fprintf(stderr, " partition %zu\n", i);
625  fprintf(stderr,
626  " active buckets (key count = %zu)\n", partition->count);
627 
628  for (j = begin; j < end; ++j)
629  {
630  size_t count = 0;
631  dsa_pointer bucket = hash_table->buckets[j];
632 
633  while (DsaPointerIsValid(bucket))
634  {
635  dshash_table_item *item;
636 
637  item = dsa_get_address(hash_table->area, bucket);
638 
639  bucket = item->next;
640  ++count;
641  }
642  fprintf(stderr, " bucket %zu (key count = %zu)\n", j, count);
643  }
644  }
645 
646  for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
647  LWLockRelease(PARTITION_LOCK(hash_table, i));
648 }
bool LWLockHeldByMe(LWLock *l)
Definition: lwlock.c:1842
#define DSHASH_NUM_PARTITIONS
Definition: dshash.c:62
#define fprintf
Definition: port.h:196
uint64 dsa_pointer
Definition: dsa.h:62
#define BUCKET_INDEX_FOR_PARTITION(partition, size_log2)
Definition: dshash.c:153
void LWLockRelease(LWLock *lock)
Definition: lwlock.c:1726
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:932
#define DSHASH_MAGIC
Definition: dshash.c:65
dsa_pointer * buckets
Definition: dshash.c:111
dshash_partition partitions[DSHASH_NUM_PARTITIONS]
Definition: dshash.c:89
dsa_area * area
Definition: dshash.c:107
bool find_locked
Definition: dshash.c:113
dshash_table_control * control
Definition: dshash.c:110
#define Assert(condition)
Definition: c.h:739
size_t count
Definition: dshash.c:78
bool LWLockAcquire(LWLock *lock, LWLockMode mode)
Definition: lwlock.c:1122
size_t size_log2
Definition: dshash.c:112
#define DsaPointerIsValid(x)
Definition: dsa.h:81
dsa_pointer next
Definition: dshash.c:49
int i
static void ensure_valid_bucket_pointers(dshash_table *hash_table)
Definition: dshash.c:757
#define PARTITION_LOCK(hash_table, i)
Definition: dshash.c:186

◆ dshash_find()

void* dshash_find ( dshash_table hash_table,
const void *  key,
bool  exclusive 
)

Definition at line 385 of file dshash.c.

References Assert, BUCKET_FOR_HASH, dshash_table::control, DSHASH_MAGIC, ensure_valid_bucket_pointers(), ENTRY_FROM_ITEM, dshash_table::find_exclusively_locked, find_in_bucket(), dshash_table::find_locked, dshash_table_item::hash, hash_key(), LW_EXCLUSIVE, LW_SHARED, LWLockAcquire(), LWLockRelease(), dshash_table_control::magic, PARTITION_FOR_HASH, and PARTITION_LOCK.

Referenced by find_or_make_matching_shared_tupledesc(), and lookup_rowtype_tupdesc_internal().

386 {
388  size_t partition;
389  dshash_table_item *item;
390 
391  hash = hash_key(hash_table, key);
392  partition = PARTITION_FOR_HASH(hash);
393 
394  Assert(hash_table->control->magic == DSHASH_MAGIC);
395  Assert(!hash_table->find_locked);
396 
397  LWLockAcquire(PARTITION_LOCK(hash_table, partition),
398  exclusive ? LW_EXCLUSIVE : LW_SHARED);
399  ensure_valid_bucket_pointers(hash_table);
400 
401  /* Search the active bucket. */
402  item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
403 
404  if (!item)
405  {
406  /* Not found. */
407  LWLockRelease(PARTITION_LOCK(hash_table, partition));
408  return NULL;
409  }
410  else
411  {
412  /* The caller will free the lock by calling dshash_release_lock. */
413  hash_table->find_locked = true;
414  hash_table->find_exclusively_locked = exclusive;
415  return ENTRY_FROM_ITEM(item);
416  }
417 }
bool find_exclusively_locked
Definition: dshash.c:114
uint32 dshash_hash
Definition: dshash.h:27
#define BUCKET_FOR_HASH(hash_table, hash)
Definition: dshash.c:157
void LWLockRelease(LWLock *lock)
Definition: lwlock.c:1726
#define DSHASH_MAGIC
Definition: dshash.c:65
#define PARTITION_FOR_HASH(hash)
Definition: dshash.c:140
bool find_locked
Definition: dshash.c:113
dshash_table_control * control
Definition: dshash.c:110
#define Assert(condition)
Definition: c.h:739
bool LWLockAcquire(LWLock *lock, LWLockMode mode)
Definition: lwlock.c:1122
static dshash_hash hash_key(dshash_table *hash_table, const void *key)
Definition: dshash.c:883
static void ensure_valid_bucket_pointers(dshash_table *hash_table)
Definition: dshash.c:757
static unsigned hash(unsigned *uv, int n)
Definition: rege_dfa.c:541
#define ENTRY_FROM_ITEM(item)
Definition: dshash.c:118
#define PARTITION_LOCK(hash_table, i)
Definition: dshash.c:186
static dshash_table_item * find_in_bucket(dshash_table *hash_table, const void *key, dsa_pointer item_pointer)
Definition: dshash.c:771

◆ dshash_find_or_insert()

void* dshash_find_or_insert ( dshash_table hash_table,
const void *  key,
bool found 
)

Definition at line 430 of file dshash.c.

References Assert, BUCKET_FOR_HASH, dshash_table::control, dshash_partition::count, DSHASH_MAGIC, ensure_valid_bucket_pointers(), ENTRY_FROM_ITEM, dshash_table::find_exclusively_locked, find_in_bucket(), dshash_table::find_locked, dshash_table_item::hash, hash_key(), insert_into_bucket(), LW_EXCLUSIVE, LWLockAcquire(), LWLockRelease(), dshash_table_control::magic, MAX_COUNT_PER_PARTITION, PARTITION_FOR_HASH, PARTITION_LOCK, dshash_table_control::partitions, resize(), and dshash_table::size_log2.

Referenced by find_or_make_matching_shared_tupledesc(), and SharedRecordTypmodRegistryInit().

433 {
435  size_t partition_index;
436  dshash_partition *partition;
437  dshash_table_item *item;
438 
439  hash = hash_key(hash_table, key);
440  partition_index = PARTITION_FOR_HASH(hash);
441  partition = &hash_table->control->partitions[partition_index];
442 
443  Assert(hash_table->control->magic == DSHASH_MAGIC);
444  Assert(!hash_table->find_locked);
445 
446 restart:
447  LWLockAcquire(PARTITION_LOCK(hash_table, partition_index),
448  LW_EXCLUSIVE);
449  ensure_valid_bucket_pointers(hash_table);
450 
451  /* Search the active bucket. */
452  item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
453 
454  if (item)
455  *found = true;
456  else
457  {
458  *found = false;
459 
460  /* Check if we are getting too full. */
461  if (partition->count > MAX_COUNT_PER_PARTITION(hash_table))
462  {
463  /*
464  * The load factor (= keys / buckets) for all buckets protected by
465  * this partition is > 0.75. Presumably the same applies
466  * generally across the whole hash table (though we don't attempt
467  * to track that directly to avoid contention on some kind of
468  * central counter; we just assume that this partition is
469  * representative). This is a good time to resize.
470  *
471  * Give up our existing lock first, because resizing needs to
472  * reacquire all the locks in the right order to avoid deadlocks.
473  */
474  LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
475  resize(hash_table, hash_table->size_log2 + 1);
476 
477  goto restart;
478  }
479 
480  /* Finally we can try to insert the new item. */
481  item = insert_into_bucket(hash_table, key,
482  &BUCKET_FOR_HASH(hash_table, hash));
483  item->hash = hash;
484  /* Adjust per-lock-partition counter for load factor knowledge. */
485  ++partition->count;
486  }
487 
488  /* The caller must release the lock with dshash_release_lock. */
489  hash_table->find_locked = true;
490  hash_table->find_exclusively_locked = true;
491  return ENTRY_FROM_ITEM(item);
492 }
static dshash_table_item * insert_into_bucket(dshash_table *hash_table, const void *key, dsa_pointer *bucket)
Definition: dshash.c:806
bool find_exclusively_locked
Definition: dshash.c:114
uint32 dshash_hash
Definition: dshash.h:27
#define BUCKET_FOR_HASH(hash_table, hash)
Definition: dshash.c:157
void LWLockRelease(LWLock *lock)
Definition: lwlock.c:1726
#define MAX_COUNT_PER_PARTITION(hash_table)
Definition: dshash.c:135
#define DSHASH_MAGIC
Definition: dshash.c:65
dshash_partition partitions[DSHASH_NUM_PARTITIONS]
Definition: dshash.c:89
#define PARTITION_FOR_HASH(hash)
Definition: dshash.c:140
bool find_locked
Definition: dshash.c:113
dshash_table_control * control
Definition: dshash.c:110
#define Assert(condition)
Definition: c.h:739
size_t count
Definition: dshash.c:78
bool LWLockAcquire(LWLock *lock, LWLockMode mode)
Definition: lwlock.c:1122
size_t size_log2
Definition: dshash.c:112
dshash_hash hash
Definition: dshash.c:51
static dshash_hash hash_key(dshash_table *hash_table, const void *key)
Definition: dshash.c:883
static void resize(dshash_table *hash_table, size_t new_size)
Definition: dshash.c:680
static void ensure_valid_bucket_pointers(dshash_table *hash_table)
Definition: dshash.c:757
static unsigned hash(unsigned *uv, int n)
Definition: rege_dfa.c:541
#define ENTRY_FROM_ITEM(item)
Definition: dshash.c:118
#define PARTITION_LOCK(hash_table, i)
Definition: dshash.c:186
static dshash_table_item * find_in_bucket(dshash_table *hash_table, const void *key, dsa_pointer item_pointer)
Definition: dshash.c:771

◆ dshash_get_hash_table_handle()

dshash_table_handle dshash_get_hash_table_handle ( dshash_table hash_table)

Definition at line 362 of file dshash.c.

References Assert, dshash_table::control, DSHASH_MAGIC, dshash_table_control::handle, and dshash_table_control::magic.

Referenced by SharedRecordTypmodRegistryInit().

363 {
364  Assert(hash_table->control->magic == DSHASH_MAGIC);
365 
366  return hash_table->control->handle;
367 }
#define DSHASH_MAGIC
Definition: dshash.c:65
dshash_table_control * control
Definition: dshash.c:110
#define Assert(condition)
Definition: c.h:739
dshash_table_handle handle
Definition: dshash.c:87

◆ dshash_memcmp()

int dshash_memcmp ( const void *  a,
const void *  b,
size_t  size,
void *  arg 
)

Definition at line 581 of file dshash.c.

582 {
583  return memcmp(a, b, size);
584 }

◆ dshash_memhash()

dshash_hash dshash_memhash ( const void *  v,
size_t  size,
void *  arg 
)

Definition at line 590 of file dshash.c.

References tag_hash().

591 {
592  return tag_hash(v, size);
593 }
uint32 tag_hash(const void *key, Size keysize)
Definition: hashfn.c:681

◆ dshash_release_lock()

void dshash_release_lock ( dshash_table hash_table,
void *  entry 
)

Definition at line 561 of file dshash.c.

References Assert, dshash_table::control, DSHASH_MAGIC, dshash_table::find_exclusively_locked, dshash_table::find_locked, dshash_table_item::hash, ITEM_FROM_ENTRY, LW_EXCLUSIVE, LW_SHARED, LWLockHeldByMeInMode(), LWLockRelease(), dshash_table_control::magic, PARTITION_FOR_HASH, and PARTITION_LOCK.

Referenced by find_or_make_matching_shared_tupledesc(), lookup_rowtype_tupdesc_internal(), and SharedRecordTypmodRegistryInit().

562 {
563  dshash_table_item *item = ITEM_FROM_ENTRY(entry);
564  size_t partition_index = PARTITION_FOR_HASH(item->hash);
565 
566  Assert(hash_table->control->magic == DSHASH_MAGIC);
567  Assert(hash_table->find_locked);
568  Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition_index),
569  hash_table->find_exclusively_locked
570  ? LW_EXCLUSIVE : LW_SHARED));
571 
572  hash_table->find_locked = false;
573  hash_table->find_exclusively_locked = false;
574  LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
575 }
bool LWLockHeldByMeInMode(LWLock *l, LWLockMode mode)
Definition: lwlock.c:1860
#define ITEM_FROM_ENTRY(entry)
Definition: dshash.c:122
bool find_exclusively_locked
Definition: dshash.c:114
void LWLockRelease(LWLock *lock)
Definition: lwlock.c:1726
#define DSHASH_MAGIC
Definition: dshash.c:65
#define PARTITION_FOR_HASH(hash)
Definition: dshash.c:140
bool find_locked
Definition: dshash.c:113
dshash_table_control * control
Definition: dshash.c:110
#define Assert(condition)
Definition: c.h:739
dshash_hash hash
Definition: dshash.c:51
#define PARTITION_LOCK(hash_table, i)
Definition: dshash.c:186

◆ ensure_valid_bucket_pointers()

static void ensure_valid_bucket_pointers ( dshash_table hash_table)
inlinestatic

Definition at line 757 of file dshash.c.

References dshash_table::area, dshash_table_control::buckets, dshash_table::buckets, dshash_table::control, dsa_get_address(), dshash_table_control::size_log2, and dshash_table::size_log2.

Referenced by dshash_delete_key(), dshash_destroy(), dshash_dump(), dshash_find(), and dshash_find_or_insert().

758 {
759  if (hash_table->size_log2 != hash_table->control->size_log2)
760  {
761  hash_table->buckets = dsa_get_address(hash_table->area,
762  hash_table->control->buckets);
763  hash_table->size_log2 = hash_table->control->size_log2;
764  }
765 }
dsa_pointer buckets
Definition: dshash.c:99
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:932
size_t size_log2
Definition: dshash.c:98
dsa_pointer * buckets
Definition: dshash.c:111
dsa_area * area
Definition: dshash.c:107
dshash_table_control * control
Definition: dshash.c:110
size_t size_log2
Definition: dshash.c:112

◆ equal_keys()

static bool equal_keys ( dshash_table hash_table,
const void *  a,
const void *  b 
)
inlinestatic

Definition at line 894 of file dshash.c.

References dshash_table::arg, dshash_parameters::compare_function, dshash_parameters::key_size, and dshash_table::params.

Referenced by delete_key_from_bucket(), and find_in_bucket().

895 {
896  return hash_table->params.compare_function(a, b,
897  hash_table->params.key_size,
898  hash_table->arg) == 0;
899 }
dshash_compare_function compare_function
Definition: dshash.h:53
dshash_parameters params
Definition: dshash.c:108
void * arg
Definition: dshash.c:109
size_t key_size
Definition: dshash.h:51

◆ find_in_bucket()

static dshash_table_item * find_in_bucket ( dshash_table hash_table,
const void *  key,
dsa_pointer  item_pointer 
)
inlinestatic

Definition at line 771 of file dshash.c.

References dshash_table::area, dsa_get_address(), DsaPointerIsValid, ENTRY_FROM_ITEM, equal_keys(), and dshash_table_item::next.

Referenced by dshash_find(), and dshash_find_or_insert().

773 {
774  while (DsaPointerIsValid(item_pointer))
775  {
776  dshash_table_item *item;
777 
778  item = dsa_get_address(hash_table->area, item_pointer);
779  if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
780  return item;
781  item_pointer = item->next;
782  }
783  return NULL;
784 }
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:932
dsa_area * area
Definition: dshash.c:107
static bool equal_keys(dshash_table *hash_table, const void *a, const void *b)
Definition: dshash.c:894
#define DsaPointerIsValid(x)
Definition: dsa.h:81
dsa_pointer next
Definition: dshash.c:49
#define ENTRY_FROM_ITEM(item)
Definition: dshash.c:118

◆ hash_key()

static dshash_hash hash_key ( dshash_table hash_table,
const void *  key 
)
inlinestatic

Definition at line 883 of file dshash.c.

References dshash_table::arg, dshash_parameters::hash_function, dshash_parameters::key_size, and dshash_table::params.

Referenced by compute_tsvector_stats(), dshash_delete_key(), dshash_find(), and dshash_find_or_insert().

884 {
885  return hash_table->params.hash_function(key,
886  hash_table->params.key_size,
887  hash_table->arg);
888 }
dshash_parameters params
Definition: dshash.c:108
void * arg
Definition: dshash.c:109
dshash_hash_function hash_function
Definition: dshash.h:54
size_t key_size
Definition: dshash.h:51

◆ insert_into_bucket()

static dshash_table_item * insert_into_bucket ( dshash_table hash_table,
const void *  key,
dsa_pointer bucket 
)
static

Definition at line 806 of file dshash.c.

References dshash_table::area, dsa_allocate, dsa_get_address(), ENTRY_FROM_ITEM, dshash_parameters::entry_size, insert_item_into_bucket(), dshash_parameters::key_size, MAXALIGN, and dshash_table::params.

Referenced by dshash_find_or_insert().

809 {
810  dsa_pointer item_pointer;
811  dshash_table_item *item;
812 
813  item_pointer = dsa_allocate(hash_table->area,
814  hash_table->params.entry_size +
815  MAXALIGN(sizeof(dshash_table_item)));
816  item = dsa_get_address(hash_table->area, item_pointer);
817  memcpy(ENTRY_FROM_ITEM(item), key, hash_table->params.key_size);
818  insert_item_into_bucket(hash_table, item_pointer, item, bucket);
819  return item;
820 }
uint64 dsa_pointer
Definition: dsa.h:62
dshash_parameters params
Definition: dshash.c:108
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:932
size_t entry_size
Definition: dshash.h:52
dsa_area * area
Definition: dshash.c:107
size_t key_size
Definition: dshash.h:51
#define MAXALIGN(LEN)
Definition: c.h:692
static void insert_item_into_bucket(dshash_table *hash_table, dsa_pointer item_pointer, dshash_table_item *item, dsa_pointer *bucket)
Definition: dshash.c:790
#define ENTRY_FROM_ITEM(item)
Definition: dshash.c:118
#define dsa_allocate(area, size)
Definition: dsa.h:84

◆ insert_item_into_bucket()

static void insert_item_into_bucket ( dshash_table hash_table,
dsa_pointer  item_pointer,
dshash_table_item item,
dsa_pointer bucket 
)
static

Definition at line 790 of file dshash.c.

References dshash_table::area, Assert, dsa_get_address(), and dshash_table_item::next.

Referenced by insert_into_bucket(), and resize().

794 {
795  Assert(item == dsa_get_address(hash_table->area, item_pointer));
796 
797  item->next = *bucket;
798  *bucket = item_pointer;
799 }
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:932
dsa_area * area
Definition: dshash.c:107
#define Assert(condition)
Definition: c.h:739
dsa_pointer next
Definition: dshash.c:49

◆ resize()

static void resize ( dshash_table hash_table,
size_t  new_size 
)
static

Definition at line 680 of file dshash.c.

References dshash_table::area, Assert, BUCKET_INDEX_FOR_HASH_AND_SIZE, dshash_table_control::buckets, dshash_table::buckets, dshash_table::control, dsa_allocate0, dsa_free(), dsa_get_address(), DsaPointerIsValid, DSHASH_NUM_PARTITIONS, dshash_table_item::hash, i, insert_item_into_bucket(), LW_EXCLUSIVE, LWLockAcquire(), LWLockHeldByMe(), LWLockRelease(), dshash_table_item::next, PARTITION_LOCK, and dshash_table_control::size_log2.

Referenced by dshash_find_or_insert().

681 {
682  dsa_pointer old_buckets;
683  dsa_pointer new_buckets_shared;
684  dsa_pointer *new_buckets;
685  size_t size;
686  size_t new_size = ((size_t) 1) << new_size_log2;
687  size_t i;
688 
689  /*
690  * Acquire the locks for all lock partitions. This is expensive, but we
691  * shouldn't have to do it many times.
692  */
693  for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
694  {
695  Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
696 
697  LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_EXCLUSIVE);
698  if (i == 0 && hash_table->control->size_log2 >= new_size_log2)
699  {
700  /*
701  * Another backend has already increased the size; we can avoid
702  * obtaining all the locks and return early.
703  */
704  LWLockRelease(PARTITION_LOCK(hash_table, 0));
705  return;
706  }
707  }
708 
709  Assert(new_size_log2 == hash_table->control->size_log2 + 1);
710 
711  /* Allocate the space for the new table. */
712  new_buckets_shared = dsa_allocate0(hash_table->area,
713  sizeof(dsa_pointer) * new_size);
714  new_buckets = dsa_get_address(hash_table->area, new_buckets_shared);
715 
716  /*
717  * We've allocated the new bucket array; all that remains to do now is to
718  * reinsert all items, which amounts to adjusting all the pointers.
719  */
720  size = ((size_t) 1) << hash_table->control->size_log2;
721  for (i = 0; i < size; ++i)
722  {
723  dsa_pointer item_pointer = hash_table->buckets[i];
724 
725  while (DsaPointerIsValid(item_pointer))
726  {
727  dshash_table_item *item;
728  dsa_pointer next_item_pointer;
729 
730  item = dsa_get_address(hash_table->area, item_pointer);
731  next_item_pointer = item->next;
732  insert_item_into_bucket(hash_table, item_pointer, item,
733  &new_buckets[BUCKET_INDEX_FOR_HASH_AND_SIZE(item->hash,
734  new_size_log2)]);
735  item_pointer = next_item_pointer;
736  }
737  }
738 
739  /* Swap the hash table into place and free the old one. */
740  old_buckets = hash_table->control->buckets;
741  hash_table->control->buckets = new_buckets_shared;
742  hash_table->control->size_log2 = new_size_log2;
743  hash_table->buckets = new_buckets;
744  dsa_free(hash_table->area, old_buckets);
745 
746  /* Release all the locks. */
747  for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
748  LWLockRelease(PARTITION_LOCK(hash_table, i));
749 }
dsa_pointer buckets
Definition: dshash.c:99
bool LWLockHeldByMe(LWLock *l)
Definition: lwlock.c:1842
#define DSHASH_NUM_PARTITIONS
Definition: dshash.c:62
uint64 dsa_pointer
Definition: dsa.h:62
void LWLockRelease(LWLock *lock)
Definition: lwlock.c:1726
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:932
size_t size_log2
Definition: dshash.c:98
#define dsa_allocate0(area, size)
Definition: dsa.h:88
dsa_pointer * buckets
Definition: dshash.c:111
#define BUCKET_INDEX_FOR_HASH_AND_SIZE(hash, size_log2)
Definition: dshash.c:149
dsa_area * area
Definition: dshash.c:107
dshash_table_control * control
Definition: dshash.c:110
#define Assert(condition)
Definition: c.h:739
bool LWLockAcquire(LWLock *lock, LWLockMode mode)
Definition: lwlock.c:1122
dshash_hash hash
Definition: dshash.c:51
#define DsaPointerIsValid(x)
Definition: dsa.h:81
dsa_pointer next
Definition: dshash.c:49
void dsa_free(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:820
int i
static void insert_item_into_bucket(dshash_table *hash_table, dsa_pointer item_pointer, dshash_table_item *item, dsa_pointer *bucket)
Definition: dshash.c:790
#define PARTITION_LOCK(hash_table, i)
Definition: dshash.c:186