Sharded concurrent hash map: Shards independently-locked DynMapHashTable partitions, no single global lock. More...

#include <tpl_concurrent_hash_map.H>

Collaboration diagram for Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >:

Classes
struct	Shard

Public Types
using	Hash_Fct_Ptr = typename Map::Hash_Fct_Ptr
	Hash function pointer type, matching `DynMapHashTable`'s own.

Public Member Functions
	ConcurrentHashMap (Hash_Fct_Ptr hash_fct=dft_hash_ptr_fct< Key >, const Cmp &cmp=Cmp())
	Construct an empty map with `Shards` independently-locked partitions.

	ConcurrentHashMap (const ConcurrentHashMap &)=delete
	Deleted copy constructor: shards own non-copyable `std::shared_mutex` instances.

ConcurrentHashMap &	operator= (const ConcurrentHashMap &)=delete
	Deleted copy assignment operator.

	ConcurrentHashMap (ConcurrentHashMap &&)=delete
	Deleted move constructor: no defined ordering exists to safely transfer locked shards out from under concurrent callers.

ConcurrentHashMap &	operator= (ConcurrentHashMap &&)=delete
	Deleted move assignment operator.

bool	insert (const Key &key, const T &value)
	Insert `key` with a copy of `value`, only if `key` is absent.

bool	insert (const Key &key, T &&value)
	Insert `key` with `value` moved in, only if `key` is absent.

void	insert_or_assign (const Key &key, T value)
	Insert `key` with `value`, or overwrite the existing value if `key` is already present.

bool	erase (const Key &key)
	Remove `key` if present.

bool	contains (const Key &key) const
	Check whether `key` is present.

std::optional< T >	find_copy (const Key &key) const
	Look up `key` and return a copy of its value, if present.

template<typename F >
bool	with_value (const Key &key, F &&f) const
	Invoke `f` with a `const` reference to `key`'s value, while the owning shard is read-locked.

template<typename F >
bool	with_value_mut (const Key &key, F &&f)
	Invoke `f` with a mutable reference to `key`'s value, while the owning shard is write-locked.

void	clear ()
	Remove every entry from every shard.

size_t	size () const
	Return the total number of entries across all shards.

bool	is_empty () const
	Check whether every shard is currently empty.

Private Types
using	Map = DynMapHashTable< Key, T, LhashTable, Cmp >

Private Member Functions
Shard &	shard_for (const Key &key) noexcept
	Resolve which shard owns `key`.

const Shard &	shard_for (const Key &key) const noexcept
	`const` overload of shard_for(const Key&).

Private Attributes
std::array< std::unique_ptr< Shard >, Shards >	shards_

Hash_Fct_Ptr	hash_fct_

Detailed Description

template<typename Key, typename T, class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>
class Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >

Sharded concurrent hash map: Shards independently-locked DynMapHashTable partitions, no single global lock.

See the file-level documentation in tpl_concurrent_hash_map.H for the full design rationale, thread-safety contract, and the specific consistency model of size()/snapshot().

Template Parameters

Key	Key type. Must satisfy whatever `Cmp` and the hash function require (typically equality-comparable and hashable).
T	Mapped value type.
Cmp	Key equality comparator, defaulting to `Aleph::equal_to<Key>`.
Shards	Number of independently-locked partitions. Must be at least 1; higher values reduce lock contention between keys that hash to different shards at the cost of `Shards` separate (smaller) hash tables and mutexes.

Definition at line 153 of file tpl_concurrent_hash_map.H.

Member Typedef Documentation

◆ Hash_Fct_Ptr

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

using Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::Hash_Fct_Ptr = typename Map::Hash_Fct_Ptr

Hash function pointer type, matching DynMapHashTable's own.

Definition at line 161 of file tpl_concurrent_hash_map.H.

◆ Map

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

using Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::Map = DynMapHashTable<Key, T, LhashTable, Cmp>

private

Definition at line 157 of file tpl_concurrent_hash_map.H.

Constructor & Destructor Documentation

◆ ConcurrentHashMap() [1/3]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::ConcurrentHashMap	(	Hash_Fct_Ptr	hash_fct = `dft_hash_ptr_fct<Key>`,
		const Cmp &	cmp = `Cmp()`
	)

inlineexplicit

Construct an empty map with Shards independently-locked partitions.

Parameters

[in]	hash_fct	Hash function applied to keys to pick a shard and to place entries within it. Defaults to the same `dft_hash_ptr_fct<Key>` used by `DynMapHashTable`'s own default constructor.
[in]	cmp	Key equality comparator, copied into every shard.

Exceptions

std::bad_alloc if allocating any of the Shards shards fails.

Note: Not thread-safe against concurrent use of the object being constructed (ordinary construction rules).

Definition at line 222 of file tpl_concurrent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), cmp(), and Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shards_.

◆ ConcurrentHashMap() [2/3]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::ConcurrentHashMap ( const ConcurrentHashMap< Key, T, Cmp, Shards > & )

delete

Deleted copy constructor: shards own non-copyable std::shared_mutex instances.

◆ ConcurrentHashMap() [3/3]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::ConcurrentHashMap ( ConcurrentHashMap< Key, T, Cmp, Shards > && )

delete

Deleted move constructor: no defined ordering exists to safely transfer locked shards out from under concurrent callers.

Member Function Documentation

◆ clear()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

void Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::clear ( )

inline

Remove every entry from every shard.

Exceptions

std::system_error if acquiring a shard's std::shared_mutex fails at the OS level; nothing otherwise (not noexcept specifically because that lock acquisition is not).

Note: Safe to call concurrently with other operations, but is not a single atomic point in time across the whole map: shards are cleared one at a time, each under its own lock, so a concurrent insert into a not-yet-cleared shard can still be present when this returns.

Definition at line 467 of file tpl_concurrent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shards_.

◆ contains()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

bool Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::contains ( const Key & key ) const

inline

Check whether key is present.

Parameters

[in] key Key to look up.

Returns: true if present at the moment of the check.

Exceptions

std::system_error if acquiring the shard's std::shared_mutex fails at the OS level; nothing otherwise.

Note: Safe to call concurrently from any number of threads, including concurrently with other readers of the same shard. A concurrent insert/erase of the same key may change the answer immediately after this returns.

Definition at line 360 of file tpl_concurrent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shard_for().

Referenced by TEST().

◆ erase()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

bool Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::erase ( const Key & key )

inline

Remove key if present.

Parameters

[in] key Key to remove.

Returns: true if key was present and removed, false otherwise.

Exceptions

std::system_error if acquiring the shard's std::shared_mutex fails at the OS level; nothing else (unlinking a located entry does not move- or copy-construct T, only destroys it).

Note: Safe to call concurrently from any number of threads. Blocks only other operations on the same shard.

Definition at line 331 of file tpl_concurrent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shard_for().

Referenced by TEST().

◆ find_copy()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

std::optional< T > Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::find_copy ( const Key & key ) const

inline

Look up key and return a copy of its value, if present.

Parameters

[in] key Key to look up.

Returns: A copy of the value if key is present, std::nullopt otherwise.

Exceptions

Whatever T's copy constructor throws. Also throws std::system_error if acquiring the shard's std::shared_mutex fails at the OS level.

Note: Safe to call concurrently from any number of threads, including concurrently with other readers of the same shard.

Definition at line 378 of file tpl_concurrent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shard_for().

◆ insert() [1/2]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

bool Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::insert	(	const Key &	key,
		const T &	value
	)

inline

Insert key with a copy of value, only if key is absent.

Parameters

[in]	key	Key to insert.
[in]	value	Value to copy in.

Returns: true if inserted, false if key was already present (the existing value is left untouched).

Exceptions

Whatever Key's or T's copy constructor throws, or std::bad_alloc. If it throws, the map is left exactly as it was before the call. Also throws std::system_error if acquiring the shard's std::shared_mutex fails at the OS level.

Note: Safe to call concurrently from any number of threads. Blocks only other operations on the same shard.

Definition at line 255 of file tpl_concurrent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shard_for(), and value.

Referenced by TEST().

◆ insert() [2/2]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

bool Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::insert	(	const Key &	key,
		T &&	value
	)

inline

Insert key with value moved in, only if key is absent.

Parameters

[in]	key	Key to insert.
[in,out]	value	Value to move in.

Returns: true if inserted, false if key was already present.

Exceptions

Whatever Key's copy constructor or T's move constructor throws, or std::bad_alloc. If it throws, the map is left exactly as it was before the call. Also throws std::system_error if acquiring the shard's std::shared_mutex fails at the OS level.

Warning: On a false return (duplicate key), value has still been moved from: the underlying table constructs the entry's Pair (moving value into it) before discovering the key already exists and discarding that entry. Do not read value after a false return; if you need to reuse it, check contains(key) first, or capture a copy before calling insert.

Note: Safe to call concurrently from any number of threads. Blocks only other operations on the same shard.

Definition at line 282 of file tpl_concurrent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shard_for(), and value.

◆ insert_or_assign()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

void Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::insert_or_assign	(	const Key &	key,
		T	value
	)

inline

Insert key with value, or overwrite the existing value if key is already present.

Parameters

[in]	key	Key to insert or update.
[in]	value	New value, moved into the map either as a fresh entry or via move-assignment over the existing one.

Exceptions

Whatever Key's copy constructor, T's move constructor, or T's move assignment throws, or std::bad_alloc. If updating an existing entry's move assignment throws, that entry is left in whatever state T::operator=(T&&) leaves a failed assignment in (the map itself remains structurally valid: the key is still present). Also throws std::system_error if acquiring the shard's std::shared_mutex fails at the OS level.

Note: Safe to call concurrently from any number of threads. Blocks only other operations on the same shard.

Definition at line 306 of file tpl_concurrent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shard_for(), and value.

◆ is_empty()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

bool Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::is_empty ( ) const

inline

Check whether every shard is currently empty.

Returns: true if no shard held any entry at the moment each was checked.

Exceptions

std::system_error if acquiring a shard's std::shared_mutex fails at the OS level; nothing otherwise.

Note: Same consistency caveat as size().

Definition at line 505 of file tpl_concurrent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shards_.

◆ operator=() [1/2]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

ConcurrentHashMap & Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::operator= ( ConcurrentHashMap< Key, T, Cmp, Shards > && )

delete

Deleted move assignment operator.

◆ operator=() [2/2]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

ConcurrentHashMap & Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::operator= ( const ConcurrentHashMap< Key, T, Cmp, Shards > & )

delete

Deleted copy assignment operator.

◆ shard_for() [1/2]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

const Shard & Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shard_for ( const Key & key ) const

inlineprivatenoexcept

const overload of shard_for(const Key&).

Definition at line 204 of file tpl_concurrent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::hash_fct_, and Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shards_.

◆ shard_for() [2/2]

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

Shard & Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shard_for ( const Key & key )

inlineprivatenoexcept

Resolve which shard owns key.

Parameters

[in] key Key to hash.

Returns: The shard whose lock and table must be used for key.

Precondition: hash_fct_ is a deterministic, pure function of key alone: calling it twice with an equal key must yield the same shard index, or a key can effectively "move" between shards between calls and become invisible to later lookups.; hash_fct_ must not throw: this function is noexcept but calls hash_fct_(key) directly, so a throwing hash function would call std::terminate() here instead of propagating.

Definition at line 198 of file tpl_concurrent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::hash_fct_, and Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shards_.

◆ size()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

size_t Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::size ( ) const

inline

Return the total number of entries across all shards.

Returns: Sum of each shard's entry count, each read under that shard's own lock.

Exceptions

std::system_error if acquiring a shard's std::shared_mutex fails at the OS level; nothing otherwise.

Note: Safe to call concurrently with other operations. Not a transactionally consistent count across the whole map – see the class-level note on size()/snapshot() consistency.

Definition at line 486 of file tpl_concurrent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shards_.

◆ with_value()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

template<typename F >

bool Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::with_value	(	const Key &	key,
		F &&	f
	)		const

inline

Invoke f with a const reference to key's value, while the owning shard is read-locked.

Template Parameters

F	Callable, invocable as `f(const T&)`, whose return value (if any) must not be a reference.

Parameters

[in]	key	Key to look up.
[in]	f	Callback invoked with the value if `key` is present.

Returns: true if key was present and f was invoked, false otherwise.

Exceptions

Whatever f throws, propagated after the lock is released. Also throws std::system_error if acquiring the shard's std::shared_mutex fails at the OS level (before f is ever invoked).

Note: Safe to call concurrently from any number of threads, including concurrently with other readers of the same shard. f runs with the shard locked: keep it short, and never call back into this same ConcurrentHashMap from within f (that would deadlock if it targets the same shard).

Definition at line 409 of file tpl_concurrent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shard_for().

◆ with_value_mut()

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

template<typename F >

bool Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::with_value_mut	(	const Key &	key,
		F &&	f
	)

inline

Invoke f with a mutable reference to key's value, while the owning shard is write-locked.

Template Parameters

F	Callable, invocable as `f(T&)`, whose return value (if any) must not be a reference.

Parameters

[in]	key	Key to look up.
[in]	f	Callback invoked with the value if `key` is present; may mutate it in place.

Returns: true if key was present and f was invoked, false otherwise.

Exceptions

Whatever f throws, propagated after the lock is released. Also throws std::system_error if acquiring the shard's std::shared_mutex fails at the OS level (before f is ever invoked).

Note: Safe to call concurrently from any number of threads. f runs with the shard exclusively locked: keep it short, and never call back into this same ConcurrentHashMap from within f.

Definition at line 442 of file tpl_concurrent_hash_map.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shard_for().

Member Data Documentation

◆ hash_fct_

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

Hash_Fct_Ptr Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::hash_fct_

private

Definition at line 184 of file tpl_concurrent_hash_map.H.

Referenced by Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shard_for(), and Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shard_for().

◆ shards_

template<typename Key , typename T , class Cmp = Aleph::equal_to<Key>, size_t Shards = 64>

std::array<std::unique_ptr<Shard>, Shards> Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shards_

private

Definition at line 183 of file tpl_concurrent_hash_map.H.

Referenced by Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::ConcurrentHashMap(), Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::clear(), Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::is_empty(), Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shard_for(), Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::shard_for(), and Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::size().

The documentation for this class was generated from the following file:

tpl_concurrent_hash_map.H

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Hash_Fct_Ptr

◆ Map

Constructor & Destructor Documentation

◆ ConcurrentHashMap() [1/3]

◆ ConcurrentHashMap() [2/3]

◆ ConcurrentHashMap() [3/3]

Member Function Documentation

◆ clear()

◆ contains()

◆ erase()

◆ find_copy()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_or_assign()

◆ is_empty()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ shard_for() [1/2]

◆ shard_for() [2/2]

◆ size()

◆ with_value()

◆ with_value_mut()

Member Data Documentation

◆ hash_fct_

◆ shards_