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

typedef uint32 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

typedef struct dshash_parameters dshash_parameters

dshash_table

typedef struct dshash_table dshash_table

Definition at line 21 of file dshash.h.

dshash_table_handle

typedef dsa_pointer dshash_table_handle

Definition at line 24 of file dshash.h.

dshash_table_item

typedef struct dshash_table_item 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().

{
    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;
}

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

{
    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;
}

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.

{
    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));
}

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

{
    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;
}

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.

{
    size_t      size;
    size_t      i;

    Assert(hash_table->control->magic == DSHASH_MAGIC);
    ensure_valid_bucket_pointers(hash_table);

    /* Free all the entries. */
    size = ((size_t) 1) << 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);
}

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

{
    Assert(!hash_table->find_locked);

    /* The hash table may have been destroyed.  Just free local memory. */
    pfree(hash_table);
}

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.

{
    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));
}

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

{
    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);
    }
}

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

{
    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);
}

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

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

    return hash_table->control->handle;
}

dshash_memcmp()

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

Definition at line 581 of file dshash.c.

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

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

{
    return tag_hash(v, size);
}

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

{
    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));
}