#include "postgres.h"
#include "common/hashfn.h"
#include "lib/dshash.h"
#include "storage/ipc.h"
#include "storage/lwlock.h"
#include "utils/dsa.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	NUM_BUCKETS(size_log2) (((size_t) 1) << (size_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	PARTITION_FOR_BUCKET_INDEX(bucket_idx, size_log2) ((bucket_idx) >> 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_item *	find_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_item *	insert_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_table *	dshash_create (dsa_area area, const dshash_parameters params, void *arg)

dshash_table *	dshash_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_seq_init (dshash_seq_status status, dshash_table hash_table, bool exclusive)

void *	dshash_seq_next (dshash_seq_status *status)

void	dshash_seq_term (dshash_seq_status *status)

void	dshash_delete_current (dshash_seq_status *status)

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)])

Definition at line 165 of file dshash.c.

◆ 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 153 of file dshash.c.

◆ BUCKET_INDEX_FOR_PARTITION

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

Definition at line 157 of file dshash.c.

◆ BUCKETS_PER_PARTITION

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

Definition at line 135 of file dshash.c.

◆ DSHASH_MAGIC

#define DSHASH_MAGIC 0x75ff6a20

Definition at line 65 of file dshash.c.

◆ DSHASH_NUM_PARTITIONS

#define DSHASH_NUM_PARTITIONS (1 << DSHASH_NUM_PARTITIONS_LOG2)

Definition at line 62 of file dshash.c.

◆ DSHASH_NUM_PARTITIONS_LOG2

#define DSHASH_NUM_PARTITIONS_LOG2 7

Definition at line 61 of file dshash.c.

◆ ENTRY_FROM_ITEM

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

Definition at line 118 of file dshash.c.

◆ ITEM_FROM_ENTRY

#define ITEM_FROM_ENTRY ( entry )

Value:

((dshash_table_item *)((char *)(entry) - \

MAXALIGN(sizeof(dshash_table_item))))

MAXALIGN

#define MAXALIGN(LEN)

Definition: c.h:757

dshash_table_item

Definition: dshash.c:47

Definition at line 122 of file dshash.c.

◆ 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)

BUCKETS_PER_PARTITION

#define BUCKETS_PER_PARTITION(size_log2)

Definition: dshash.c:135

Definition at line 139 of file dshash.c.

◆ NUM_BUCKETS

#define NUM_BUCKETS ( size_log2 ) (((size_t) 1) << (size_log2))

Definition at line 131 of file dshash.c.

◆ NUM_SPLITS

#define NUM_SPLITS ( size_log2 ) (size_log2 - DSHASH_NUM_PARTITIONS_LOG2)

Definition at line 127 of file dshash.c.

◆ PARTITION_FOR_BUCKET_INDEX

#define PARTITION_FOR_BUCKET_INDEX	(	bucket_idx,
		size_log2
	)	((bucket_idx) >> NUM_SPLITS(size_log2))

Definition at line 161 of file dshash.c.

◆ PARTITION_FOR_HASH

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

Definition at line 144 of file dshash.c.

◆ PARTITION_LOCK

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

Definition at line 194 of file dshash.c.

Typedef Documentation

◆ dshash_partition

typedef struct dshash_partition dshash_partition

◆ dshash_table_control

typedef struct dshash_table_control dshash_table_control

Function Documentation

◆ delete_item()

static void delete_item	(	dshash_table *	hash_table,
		dshash_table_item *	item
	)

static

Definition at line 813 of file dshash.c.

 {
     size_t      hash = item->hash;
     size_t      partition = PARTITION_FOR_HASH(hash);
  
     Assert(LWLockHeldByMe(PARTITION_LOCK(hash_table, partition)));
  
     if (delete_item_from_bucket(hash_table, item,
                                 &BUCKET_FOR_HASH(hash_table, hash)))
     {
         Assert(hash_table->control->partitions[partition].count > 0);
         --hash_table->control->partitions[partition].count;
     }
     else
     {
         Assert(false);
     }
 }

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

Referenced by dshash_delete_current(), and dshash_delete_entry().

◆ 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 1014 of file dshash.c.

 {
     while (DsaPointerIsValid(*bucket_head))
     {
         dshash_table_item *bucket_item;
  
         bucket_item = dsa_get_address(hash_table->area, *bucket_head);
  
         if (bucket_item == item)
         {
             dsa_pointer next;
  
             next = item->next;
             dsa_free(hash_table->area, *bucket_head);
             *bucket_head = next;
             return true;
         }
         bucket_head = &bucket_item->next;
     }
     return false;
 }

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

Referenced by delete_item().

◆ 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 985 of file dshash.c.

 {
     while (DsaPointerIsValid(*bucket_head))
     {
         dshash_table_item *item;
  
         item = dsa_get_address(hash_table->area, *bucket_head);
  
         if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
         {
             dsa_pointer next;
  
             next = item->next;
             dsa_free(hash_table->area, *bucket_head);
             *bucket_head = next;
  
             return true;
         }
         bucket_head = &item->next;
     }
     return false;
 }

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

Referenced by dshash_delete_key().

◆ dshash_attach()

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

Definition at line 271 of file dshash.c.

 {
     dshash_table *hash_table;
     dsa_pointer control;
  
     /* Allocate the backend-local object representing the hash table. */
     hash_table = palloc(sizeof(dshash_table));
  
     /* Find the control object in shared memory. */
     control = handle;
  
     /* Set up the local hash table struct. */
     hash_table->area = area;
     hash_table->params = *params;
     hash_table->arg = arg;
     hash_table->control = dsa_get_address(area, control);
     hash_table->find_locked = false;
     hash_table->find_exclusively_locked = false;
     Assert(hash_table->control->magic == DSHASH_MAGIC);
  
     /*
      * These will later be set to the correct values by
      * ensure_valid_bucket_pointers(), at which time we'll be holding a
      * partition lock for interlocking against concurrent resizing.
      */
     hash_table->buckets = NULL;
     hash_table->size_log2 = 0;
  
     return hash_table;
 }

References dshash_table::area, dshash_table::arg, 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 pgstat_attach_shmem(), and SharedRecordTypmodRegistryAttach().

◆ dshash_create()

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

Definition at line 204 of file dshash.c.

 {
     dshash_table *hash_table;
     dsa_pointer control;
  
     /* Allocate the backend-local object representing the hash table. */
     hash_table = palloc(sizeof(dshash_table));
  
     /* Allocate the control object in shared memory. */
     control = dsa_allocate(area, sizeof(dshash_table_control));
  
     /* Set up the local and shared hash table structs. */
     hash_table->area = area;
     hash_table->params = *params;
     hash_table->arg = arg;
     hash_table->control = dsa_get_address(area, control);
     hash_table->control->handle = control;
     hash_table->control->magic = DSHASH_MAGIC;
     hash_table->control->lwlock_tranche_id = params->tranche_id;
  
     /* Set up the array of lock partitions. */
     {
         dshash_partition *partitions = hash_table->control->partitions;
         int         tranche_id = hash_table->control->lwlock_tranche_id;
         int         i;
  
         for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
         {
             LWLockInitialize(&partitions[i].lock, tranche_id);
             partitions[i].count = 0;
         }
     }
  
     hash_table->find_locked = false;
     hash_table->find_exclusively_locked = false;
  
     /*
      * Set up the initial array of buckets.  Our initial size is the same as
      * the number of partitions.
      */
     hash_table->control->size_log2 = DSHASH_NUM_PARTITIONS_LOG2;
     hash_table->control->buckets =
         dsa_allocate_extended(area,
                               sizeof(dsa_pointer) * DSHASH_NUM_PARTITIONS,
                               DSA_ALLOC_NO_OOM | DSA_ALLOC_ZERO);
     if (!DsaPointerIsValid(hash_table->control->buckets))
     {
         dsa_free(area, control);
         ereport(ERROR,
                 (errcode(ERRCODE_OUT_OF_MEMORY),
                  errmsg("out of memory"),
                  errdetail("Failed on DSA request of size %zu.",
                            sizeof(dsa_pointer) * DSHASH_NUM_PARTITIONS)));
     }
     hash_table->buckets = dsa_get_address(area,
                                           hash_table->control->buckets);
     hash_table->size_log2 = hash_table->control->size_log2;
  
     return hash_table;
 }

References dshash_table::area, dshash_table::arg, arg, dshash_table_control::buckets, dshash_table::buckets, dshash_table::control, 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(), and StatsShmemInit().

◆ dshash_delete_current()

void dshash_delete_current ( dshash_seq_status * status )

Definition at line 736 of file dshash.c.

 {
     dshash_table *hash_table = status->hash_table;
     dshash_table_item *item = status->curitem;
     size_t      partition PG_USED_FOR_ASSERTS_ONLY;
  
     partition = PARTITION_FOR_HASH(item->hash);
  
     Assert(status->exclusive);
     Assert(hash_table->control->magic == DSHASH_MAGIC);
     Assert(hash_table->find_locked);
     Assert(hash_table->find_exclusively_locked);
     Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
                                 LW_EXCLUSIVE));
  
     delete_item(hash_table, item);
 }

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

Referenced by pgstat_free_entry().

◆ dshash_delete_entry()

void dshash_delete_entry	(	dshash_table *	hash_table,
		void *	entry
	)

Definition at line 548 of file dshash.c.

 {
     dshash_table_item *item = ITEM_FROM_ENTRY(entry);
     size_t      partition = PARTITION_FOR_HASH(item->hash);
  
     Assert(hash_table->control->magic == DSHASH_MAGIC);
     Assert(hash_table->find_locked);
     Assert(hash_table->find_exclusively_locked);
     Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition),
                                 LW_EXCLUSIVE));
  
     delete_item(hash_table, item);
     hash_table->find_locked = false;
     hash_table->find_exclusively_locked = false;
     LWLockRelease(PARTITION_LOCK(hash_table, partition));
 }

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.

Referenced by pgstat_free_entry().

◆ dshash_delete_key()

bool dshash_delete_key	(	dshash_table *	hash_table,
		const void *	key
	)

Definition at line 510 of file dshash.c.

 {
     dshash_hash hash;
     size_t      partition;
     bool        found;
  
     Assert(hash_table->control->magic == DSHASH_MAGIC);
     Assert(!hash_table->find_locked);
  
     hash = hash_key(hash_table, key);
     partition = PARTITION_FOR_HASH(hash);
  
     LWLockAcquire(PARTITION_LOCK(hash_table, partition), LW_EXCLUSIVE);
     ensure_valid_bucket_pointers(hash_table);
  
     if (delete_key_from_bucket(hash_table, key,
                                &BUCKET_FOR_HASH(hash_table, hash)))
     {
         Assert(hash_table->control->partitions[partition].count > 0);
         found = true;
         --hash_table->control->partitions[partition].count;
     }
     else
         found = false;
  
     LWLockRelease(PARTITION_LOCK(hash_table, partition));
  
     return found;
 }

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, hash(), hash_key(), sort-test::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().

◆ dshash_destroy()

void dshash_destroy ( dshash_table * hash_table )

Definition at line 326 of file dshash.c.

 {
     size_t      size;
     size_t      i;
  
     Assert(hash_table->control->magic == DSHASH_MAGIC);
     ensure_valid_bucket_pointers(hash_table);
  
     /* Free all the entries. */
     size = NUM_BUCKETS(hash_table->size_log2);
     for (i = 0; i < size; ++i)
     {
         dsa_pointer item_pointer = hash_table->buckets[i];
  
         while (DsaPointerIsValid(item_pointer))
         {
             dshash_table_item *item;
             dsa_pointer next_item_pointer;
  
             item = dsa_get_address(hash_table->area, item_pointer);
             next_item_pointer = item->next;
             dsa_free(hash_table->area, item_pointer);
             item_pointer = next_item_pointer;
         }
     }
  
     /*
      * Vandalize the control block to help catch programming errors where
      * other backends access the memory formerly occupied by this hash table.
      */
     hash_table->control->magic = 0;
  
     /* Free the active table and control object. */
     dsa_free(hash_table->area, hash_table->control->buckets);
     dsa_free(hash_table->area, hash_table->control->handle);
  
     pfree(hash_table);
 }

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, NUM_BUCKETS, pfree(), and dshash_table::size_log2.

◆ dshash_detach()

void dshash_detach ( dshash_table * hash_table )

Definition at line 310 of file dshash.c.

 {
     Assert(!hash_table->find_locked);
  
     /* The hash table may have been destroyed.  Just free local memory. */
     pfree(hash_table);
 }

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

Referenced by pgstat_detach_shmem(), shared_record_typmod_registry_detach(), and StatsShmemInit().

◆ dshash_dump()

void dshash_dump ( dshash_table * hash_table )

Definition at line 759 of file dshash.c.

 {
     size_t      i;
     size_t      j;
  
     Assert(hash_table->control->magic == DSHASH_MAGIC);
     Assert(!hash_table->find_locked);
  
     for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
     {
         Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
         LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_SHARED);
     }
  
     ensure_valid_bucket_pointers(hash_table);
  
     fprintf(stderr,
             "hash table size = %zu\n", (size_t) 1 << hash_table->size_log2);
     for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
     {
         dshash_partition *partition = &hash_table->control->partitions[i];
         size_t      begin = BUCKET_INDEX_FOR_PARTITION(i, hash_table->size_log2);
         size_t      end = BUCKET_INDEX_FOR_PARTITION(i + 1, hash_table->size_log2);
  
         fprintf(stderr, "  partition %zu\n", i);
         fprintf(stderr,
                 "    active buckets (key count = %zu)\n", partition->count);
  
         for (j = begin; j < end; ++j)
         {
             size_t      count = 0;
             dsa_pointer bucket = hash_table->buckets[j];
  
             while (DsaPointerIsValid(bucket))
             {
                 dshash_table_item *item;
  
                 item = dsa_get_address(hash_table->area, bucket);
  
                 bucket = item->next;
                 ++count;
             }
             fprintf(stderr, "      bucket %zu (key count = %zu)\n", j, count);
         }
     }
  
     for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
         LWLockRelease(PARTITION_LOCK(hash_table, i));
 }

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, j, LW_SHARED, LWLockAcquire(), LWLockHeldByMe(), LWLockRelease(), dshash_table_control::magic, dshash_table_item::next, PARTITION_LOCK, dshash_table_control::partitions, and dshash_table::size_log2.

◆ dshash_find()

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

Definition at line 393 of file dshash.c.

 {
     dshash_hash hash;
     size_t      partition;
     dshash_table_item *item;
  
     hash = hash_key(hash_table, key);
     partition = PARTITION_FOR_HASH(hash);
  
     Assert(hash_table->control->magic == DSHASH_MAGIC);
     Assert(!hash_table->find_locked);
  
     LWLockAcquire(PARTITION_LOCK(hash_table, partition),
                   exclusive ? LW_EXCLUSIVE : LW_SHARED);
     ensure_valid_bucket_pointers(hash_table);
  
     /* Search the active bucket. */
     item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
  
     if (!item)
     {
         /* Not found. */
         LWLockRelease(PARTITION_LOCK(hash_table, partition));
         return NULL;
     }
     else
     {
         /* The caller will free the lock by calling dshash_release_lock. */
         hash_table->find_locked = true;
         hash_table->find_exclusively_locked = exclusive;
         return ENTRY_FROM_ITEM(item);
     }
 }

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, hash(), hash_key(), sort-test::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(), lookup_rowtype_tupdesc_internal(), pgstat_drop_entry(), pgstat_get_entry_ref(), and pgstat_release_entry_ref().

◆ dshash_find_or_insert()

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

Definition at line 438 of file dshash.c.

 {
     dshash_hash hash;
     size_t      partition_index;
     dshash_partition *partition;
     dshash_table_item *item;
  
     hash = hash_key(hash_table, key);
     partition_index = PARTITION_FOR_HASH(hash);
     partition = &hash_table->control->partitions[partition_index];
  
     Assert(hash_table->control->magic == DSHASH_MAGIC);
     Assert(!hash_table->find_locked);
  
 restart:
     LWLockAcquire(PARTITION_LOCK(hash_table, partition_index),
                   LW_EXCLUSIVE);
     ensure_valid_bucket_pointers(hash_table);
  
     /* Search the active bucket. */
     item = find_in_bucket(hash_table, key, BUCKET_FOR_HASH(hash_table, hash));
  
     if (item)
         *found = true;
     else
     {
         *found = false;
  
         /* Check if we are getting too full. */
         if (partition->count > MAX_COUNT_PER_PARTITION(hash_table))
         {
             /*
              * The load factor (= keys / buckets) for all buckets protected by
              * this partition is > 0.75.  Presumably the same applies
              * generally across the whole hash table (though we don't attempt
              * to track that directly to avoid contention on some kind of
              * central counter; we just assume that this partition is
              * representative).  This is a good time to resize.
              *
              * Give up our existing lock first, because resizing needs to
              * reacquire all the locks in the right order to avoid deadlocks.
              */
             LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
             resize(hash_table, hash_table->size_log2 + 1);
  
             goto restart;
         }
  
         /* Finally we can try to insert the new item. */
         item = insert_into_bucket(hash_table, key,
                                   &BUCKET_FOR_HASH(hash_table, hash));
         item->hash = hash;
         /* Adjust per-lock-partition counter for load factor knowledge. */
         ++partition->count;
     }
  
     /* The caller must release the lock with dshash_release_lock. */
     hash_table->find_locked = true;
     hash_table->find_exclusively_locked = true;
     return ENTRY_FROM_ITEM(item);
 }

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(), hash_key(), insert_into_bucket(), sort-test::key, 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(), pgstat_get_entry_ref(), pgstat_read_statsfile(), and SharedRecordTypmodRegistryInit().

◆ dshash_get_hash_table_handle()

dshash_table_handle dshash_get_hash_table_handle ( dshash_table * hash_table )

Definition at line 370 of file dshash.c.

 {
     Assert(hash_table->control->magic == DSHASH_MAGIC);
  
     return hash_table->control->handle;
 }

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

Referenced by SharedRecordTypmodRegistryInit(), and StatsShmemInit().

◆ dshash_memcmp()

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

Definition at line 589 of file dshash.c.

 {
     return memcmp(a, b, size);
 }

References a, and b.

◆ dshash_memhash()

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

Definition at line 598 of file dshash.c.

 {
     return tag_hash(v, size);
 }

References tag_hash().

◆ dshash_release_lock()

void dshash_release_lock	(	dshash_table *	hash_table,
		void *	entry
	)

Definition at line 569 of file dshash.c.

 {
     dshash_table_item *item = ITEM_FROM_ENTRY(entry);
     size_t      partition_index = PARTITION_FOR_HASH(item->hash);
  
     Assert(hash_table->control->magic == DSHASH_MAGIC);
     Assert(hash_table->find_locked);
     Assert(LWLockHeldByMeInMode(PARTITION_LOCK(hash_table, partition_index),
                                 hash_table->find_exclusively_locked
                                 ? LW_EXCLUSIVE : LW_SHARED));
  
     hash_table->find_locked = false;
     hash_table->find_exclusively_locked = false;
     LWLockRelease(PARTITION_LOCK(hash_table, partition_index));
 }

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(), pgstat_acquire_entry_ref(), pgstat_drop_entry_internal(), pgstat_get_entry_ref(), pgstat_read_statsfile(), and SharedRecordTypmodRegistryInit().

◆ dshash_seq_init()

void dshash_seq_init	(	dshash_seq_status *	status,
		dshash_table *	hash_table,
		bool	exclusive
	)

Definition at line 612 of file dshash.c.

 {
     status->hash_table = hash_table;
     status->curbucket = 0;
     status->nbuckets = 0;
     status->curitem = NULL;
     status->pnextitem = InvalidDsaPointer;
     status->curpartition = -1;
     status->exclusive = exclusive;
 }

References InvalidDsaPointer, and status().

Referenced by pgstat_build_snapshot(), pgstat_drop_all_entries(), pgstat_drop_database_and_contents(), pgstat_reset_matching_entries(), and pgstat_write_statsfile().

◆ dshash_seq_next()

void* dshash_seq_next ( dshash_seq_status * status )

Definition at line 631 of file dshash.c.

 {
     dsa_pointer next_item_pointer;
  
     /*
      * Not yet holding any partition locks. Need to determine the size of the
      * hash table, it could have been resized since we were looking last.
      * Since we iterate in partition order, we can start by unconditionally
      * lock partition 0.
      *
      * Once we hold the lock, no resizing can happen until the scan ends. So
      * we don't need to repeatedly call ensure_valid_bucket_pointers().
      */
     if (status->curpartition == -1)
     {
         Assert(status->curbucket == 0);
         Assert(!status->hash_table->find_locked);
  
         status->curpartition = 0;
  
         LWLockAcquire(PARTITION_LOCK(status->hash_table,
                                      status->curpartition),
                       status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
  
         ensure_valid_bucket_pointers(status->hash_table);
  
         status->nbuckets =
             NUM_BUCKETS(status->hash_table->control->size_log2);
         next_item_pointer = status->hash_table->buckets[status->curbucket];
     }
     else
         next_item_pointer = status->pnextitem;
  
     Assert(LWLockHeldByMeInMode(PARTITION_LOCK(status->hash_table,
                                                status->curpartition),
                                 status->exclusive ? LW_EXCLUSIVE : LW_SHARED));
  
     /* Move to the next bucket if we finished the current bucket */
     while (!DsaPointerIsValid(next_item_pointer))
     {
         int         next_partition;
  
         if (++status->curbucket >= status->nbuckets)
         {
             /* all buckets have been scanned. finish. */
             return NULL;
         }
  
         /* Check if move to the next partition */
         next_partition =
             PARTITION_FOR_BUCKET_INDEX(status->curbucket,
                                        status->hash_table->size_log2);
  
         if (status->curpartition != next_partition)
         {
             /*
              * Move to the next partition. Lock the next partition then
              * release the current, not in the reverse order to avoid
              * concurrent resizing.  Avoid dead lock by taking lock in the
              * same order with resize().
              */
             LWLockAcquire(PARTITION_LOCK(status->hash_table,
                                          next_partition),
                           status->exclusive ? LW_EXCLUSIVE : LW_SHARED);
             LWLockRelease(PARTITION_LOCK(status->hash_table,
                                          status->curpartition));
             status->curpartition = next_partition;
         }
  
         next_item_pointer = status->hash_table->buckets[status->curbucket];
     }
  
     status->curitem =
         dsa_get_address(status->hash_table->area, next_item_pointer);
     status->hash_table->find_locked = true;
     status->hash_table->find_exclusively_locked = status->exclusive;
  
     /*
      * The caller may delete the item. Store the next item in case of
      * deletion.
      */
     status->pnextitem = status->curitem->next;
  
     return ENTRY_FROM_ITEM(status->curitem);
 }

References Assert(), dsa_get_address(), DsaPointerIsValid, ensure_valid_bucket_pointers(), ENTRY_FROM_ITEM, LW_EXCLUSIVE, LW_SHARED, LWLockAcquire(), LWLockHeldByMeInMode(), LWLockRelease(), NUM_BUCKETS, PARTITION_FOR_BUCKET_INDEX, PARTITION_LOCK, and status().

Referenced by pgstat_build_snapshot(), pgstat_drop_all_entries(), pgstat_drop_database_and_contents(), pgstat_reset_matching_entries(), and pgstat_write_statsfile().

◆ dshash_seq_term()

void dshash_seq_term ( dshash_seq_status * status )

Definition at line 723 of file dshash.c.

 {
     status->hash_table->find_locked = false;
     status->hash_table->find_exclusively_locked = false;
  
     if (status->curpartition >= 0)
         LWLockRelease(PARTITION_LOCK(status->hash_table, status->curpartition));
 }

References LWLockRelease(), PARTITION_LOCK, and status().

Referenced by pgstat_build_snapshot(), pgstat_drop_all_entries(), pgstat_drop_database_and_contents(), pgstat_reset_matching_entries(), and pgstat_write_statsfile().

◆ ensure_valid_bucket_pointers()

static void ensure_valid_bucket_pointers ( dshash_table * hash_table )

inlinestatic

Definition at line 916 of file dshash.c.

 {
     if (hash_table->size_log2 != hash_table->control->size_log2)
     {
         hash_table->buckets = dsa_get_address(hash_table->area,
                                               hash_table->control->buckets);
         hash_table->size_log2 = hash_table->control->size_log2;
     }
 }

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(), dshash_find_or_insert(), and dshash_seq_next().

◆ equal_keys()

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

inlinestatic

Definition at line 1053 of file dshash.c.

 {
     return hash_table->params.compare_function(a, b,
                                                hash_table->params.key_size,
                                                hash_table->arg) == 0;
 }

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

Referenced by delete_key_from_bucket(), and find_in_bucket().

◆ 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 930 of file dshash.c.

 {
     while (DsaPointerIsValid(item_pointer))
     {
         dshash_table_item *item;
  
         item = dsa_get_address(hash_table->area, item_pointer);
         if (equal_keys(hash_table, key, ENTRY_FROM_ITEM(item)))
             return item;
         item_pointer = item->next;
     }
     return NULL;
 }

References dshash_table::area, dsa_get_address(), DsaPointerIsValid, ENTRY_FROM_ITEM, equal_keys(), sort-test::key, and dshash_table_item::next.

Referenced by dshash_find(), and dshash_find_or_insert().

◆ hash_key()

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

inlinestatic

Definition at line 1042 of file dshash.c.

 {
     return hash_table->params.hash_function(key,
                                             hash_table->params.key_size,
                                             hash_table->arg);
 }

References dshash_table::arg, dshash_parameters::hash_function, sort-test::key, dshash_parameters::key_size, and dshash_table::params.

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

◆ insert_into_bucket()

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

static

Definition at line 965 of file dshash.c.

 {
     dsa_pointer item_pointer;
     dshash_table_item *item;
  
     item_pointer = dsa_allocate(hash_table->area,
                                 hash_table->params.entry_size +
                                 MAXALIGN(sizeof(dshash_table_item)));
     item = dsa_get_address(hash_table->area, item_pointer);
     memcpy(ENTRY_FROM_ITEM(item), key, hash_table->params.key_size);
     insert_item_into_bucket(hash_table, item_pointer, item, bucket);
     return item;
 }

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

Referenced by dshash_find_or_insert().

◆ 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 949 of file dshash.c.

 {
     Assert(item == dsa_get_address(hash_table->area, item_pointer));
  
     item->next = *bucket;
     *bucket = item_pointer;
 }

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

Referenced by insert_into_bucket(), and resize().

◆ resize()

static void resize	(	dshash_table *	hash_table,
		size_t	new_size
	)

static

Definition at line 839 of file dshash.c.

 {
     dsa_pointer old_buckets;
     dsa_pointer new_buckets_shared;
     dsa_pointer *new_buckets;
     size_t      size;
     size_t      new_size = ((size_t) 1) << new_size_log2;
     size_t      i;
  
     /*
      * Acquire the locks for all lock partitions.  This is expensive, but we
      * shouldn't have to do it many times.
      */
     for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
     {
         Assert(!LWLockHeldByMe(PARTITION_LOCK(hash_table, i)));
  
         LWLockAcquire(PARTITION_LOCK(hash_table, i), LW_EXCLUSIVE);
         if (i == 0 && hash_table->control->size_log2 >= new_size_log2)
         {
             /*
              * Another backend has already increased the size; we can avoid
              * obtaining all the locks and return early.
              */
             LWLockRelease(PARTITION_LOCK(hash_table, 0));
             return;
         }
     }
  
     Assert(new_size_log2 == hash_table->control->size_log2 + 1);
  
     /* Allocate the space for the new table. */
     new_buckets_shared = dsa_allocate0(hash_table->area,
                                        sizeof(dsa_pointer) * new_size);
     new_buckets = dsa_get_address(hash_table->area, new_buckets_shared);
  
     /*
      * We've allocated the new bucket array; all that remains to do now is to
      * reinsert all items, which amounts to adjusting all the pointers.
      */
     size = ((size_t) 1) << hash_table->control->size_log2;
     for (i = 0; i < size; ++i)
     {
         dsa_pointer item_pointer = hash_table->buckets[i];
  
         while (DsaPointerIsValid(item_pointer))
         {
             dshash_table_item *item;
             dsa_pointer next_item_pointer;
  
             item = dsa_get_address(hash_table->area, item_pointer);
             next_item_pointer = item->next;
             insert_item_into_bucket(hash_table, item_pointer, item,
                                     &new_buckets[BUCKET_INDEX_FOR_HASH_AND_SIZE(item->hash,
                                                                                 new_size_log2)]);
             item_pointer = next_item_pointer;
         }
     }
  
     /* Swap the hash table into place and free the old one. */
     old_buckets = hash_table->control->buckets;
     hash_table->control->buckets = new_buckets_shared;
     hash_table->control->size_log2 = new_size_log2;
     hash_table->buckets = new_buckets;
     dsa_free(hash_table->area, old_buckets);
  
     /* Release all the locks. */
     for (i = 0; i < DSHASH_NUM_PARTITIONS; ++i)
         LWLockRelease(PARTITION_LOCK(hash_table, i));
 }

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().

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ BUCKET_FOR_HASH

◆ BUCKET_INDEX_FOR_HASH_AND_SIZE

◆ BUCKET_INDEX_FOR_PARTITION

◆ BUCKETS_PER_PARTITION

◆ DSHASH_MAGIC

◆ DSHASH_NUM_PARTITIONS

◆ DSHASH_NUM_PARTITIONS_LOG2

◆ ENTRY_FROM_ITEM

◆ ITEM_FROM_ENTRY

◆ MAX_COUNT_PER_PARTITION

◆ NUM_BUCKETS

◆ NUM_SPLITS

◆ PARTITION_FOR_BUCKET_INDEX

◆ PARTITION_FOR_HASH

◆ PARTITION_LOCK

Typedef Documentation

◆ dshash_partition

◆ dshash_table_control

Function Documentation

◆ delete_item()

◆ delete_item_from_bucket()

◆ delete_key_from_bucket()

◆ dshash_attach()

◆ dshash_create()

◆ dshash_delete_current()

◆ dshash_delete_entry()

◆ dshash_delete_key()

◆ dshash_destroy()

◆ dshash_detach()

◆ dshash_dump()

◆ dshash_find()

◆ dshash_find_or_insert()

◆ dshash_get_hash_table_handle()

◆ dshash_memcmp()

◆ dshash_memhash()

◆ dshash_release_lock()

◆ dshash_seq_init()

◆ dshash_seq_next()

◆ dshash_seq_term()

◆ ensure_valid_bucket_pointers()

◆ equal_keys()

◆ find_in_bucket()

◆ hash_key()

◆ insert_into_bucket()

◆ insert_item_into_bucket()

◆ resize()