PostgreSQL Source Code  git master
dshash.h File Reference
#include "utils/dsa.h"
Include dependency graph for dshash.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  dshash_parameters
 

Typedefs

typedef struct dshash_table dshash_table
 
typedef dsa_pointer dshash_table_handle
 
typedef uint32 dshash_hash
 
typedef int(* dshash_compare_function) (const void *a, const void *b, size_t size, void *arg)
 
typedef dshash_hash(* dshash_hash_function) (const void *v, size_t size, void *arg)
 
typedef struct dshash_parameters dshash_parameters
 
typedef struct dshash_table_item dshash_table_item
 

Functions

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)
 
dshash_table_handle dshash_get_hash_table_handle (dshash_table *hash_table)
 
void dshash_destroy (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)
 

Typedef Documentation

◆ dshash_compare_function

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

Definition at line 30 of file dshash.h.

◆ dshash_hash

Definition at line 27 of file dshash.h.

◆ dshash_hash_function

typedef dshash_hash(* dshash_hash_function) (const void *v, size_t size, void *arg)

Definition at line 34 of file dshash.h.

◆ dshash_parameters

◆ dshash_table

typedef struct dshash_table dshash_table

Definition at line 21 of file dshash.h.

◆ dshash_table_handle

Definition at line 24 of file dshash.h.

◆ dshash_table_item

Definition at line 60 of file dshash.h.

Function Documentation

◆ 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:733
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:195
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:957
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:733
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:733
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:733
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:733

◆ 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:733
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:733
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:733
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:733
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:733
dshash_hash hash
Definition: dshash.c:51
#define PARTITION_LOCK(hash_table, i)
Definition: dshash.c:186