A parallel hash table. Properties: More...

#include <ParallelHashTable.h>

Inherits gts::AlignedAllocator< GTS_NO_SHARING_CACHE_LINE_SIZE >.

Classes
class	const_iterator
	A constant forward iterator. Read-locks the referenced element until destruction. More...

class	iterator
	A forward iterator. Write-locks the referenced element until destruction. More...

Public Types
using	key_type = TKey

using	mapped_type = TValue

using	value_type = KeyValue< key_type, mapped_type >

using	size_type = size_t

using	allocator_type = TAllocator

using	hasher_type = THasher

Public Member Functions
	ParallelHashTable (allocator_type const &allocator=allocator_type())

	ParallelHashTable (uint32_t growMutexCount, allocator_type const &allocator=allocator_type())

	~ParallelHashTable ()

	ParallelHashTable (ParallelHashTable const &other)

	ParallelHashTable (ParallelHashTable &&other)

ParallelHashTable &	operator= (ParallelHashTable const &other)

ParallelHashTable &	operator= (ParallelHashTable &&other)

const_iterator	cbegin () const

const_iterator	cend () const

iterator	begin () const

iterator	end () const

size_type	capacity () const

size_type	max_size () const

const_iterator	cfind (key_type const &key) const

iterator	find (key_type const &key)

allocator_type	get_allocator () const
	Get this Vectors allocator. More...

void	reserve (size_type sizePow2)

iterator	insert (value_type const &keyVal)

iterator	insert (value_type &&keyVal)

iterator	insert_or_assign (value_type const &keyVal)

iterator	insert_or_assign (value_type &&keyVal)

size_type	erase (key_type const &key)

iterator	erase (iterator &iter)

void	cleanup ()

void	clear ()

template<bool useLocks>
bool	_tryGrowTable (table_type *pTable, size_type sizePow2)

template<bool useLocks, typename... TArgs>
ParallelHashTable< TKey, TValue, THasher, TAccessorSharedMutex, TGrowSharedMutex, TAllocator >::iterator	_tryInsert (bool assignable, TKey const &key, TArgs &&... args)

template<bool useLocks, typename... TArgs>
ParallelHashTable< TKey, TValue, THasher, TAccessorSharedMutex, TGrowSharedMutex, TAllocator >::ProbeResult	_probeWrite (bool assignable, TKey const &key, table_type *&pOutTable, size_type &outIndex)

Friends
class	base_const_iterator

class	const_iterator

class	iterator

Detailed Description

template<typename TKey, typename TValue, typename THasher = MurmurHash<TKey>, typename TAccessorSharedMutex = UnfairSharedSpinMutex<>, typename TGrowSharedMutex = UnfairSharedSpinMutex<>, typename TAllocator = AlignedAllocator<GTS_NO_SHARING_CACHE_LINE_SIZE>>
class gts::ParallelHashTable< TKey, TValue, THasher, TAccessorSharedMutex, TGrowSharedMutex, TAllocator >

A parallel hash table. Properties:

Open addressing with O(log2*log2(N)) probing.
Grows when insert probing reaches O(log2*log2(N)).
Unbound.
Reference Stable.
Linearizable if Mutexes are fair.
Remarks
User is responsible for calling cleanup() to delete stale tables after table doubling.
Iterators contain spin-locks that are unlocked in the iterator's destructor. Holding onto them may cause deadlocks.

Bad hash functions may cause huge tables. Author has only had this occur with pathologically bad hashers.

Template Parameters

TKey	The unique identifier associated with each element in the container.
TValue	The element type stored in the container.
THasher	The hashing function.
TAccessorSharedMutex	The shared mutex type to access individual elements.
TGrowSharedMutex	The shared mutex type used to grow the table.
TAllocator	The allocator used by the storage backing.

Todo:

Try Robin Hood hashing. (Lock cost may be prohibitive.)

Try Striped locks to protect slots instead of locks per slot.

Try 1-byte per table entry trick and use SSE for compares. (see Skarupke and Kulukundis)

Implement table shrinking.

Divise a reclaimation system (hazard pointers etc.) the avoid the need for cleanup().

Add equals template parameter.

Add size() and empty()? requires shared counter :(