Hash map from integers/pointers allowing concurrent, lockless reads. More...

#include <ConcurrentMap.h>

Collaboration diagram for CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >:

Classes
class	const_iterator
	Iterator class. More...
struct	Hasher
struct	Matcher

Public Types
using	key_type = KEY
	Standard STL types.
using	mapped_type = VALUE
using	size_type = size_t
using	Updater_t = typename Impl_t::Updater_t
	Updater object.
using	Context_t = typename Updater_t::Context_t
	Context type.
using	Lock_t = typename Impl_t::Lock_t
	Type for external locking.
using	const_iterator_value = std::pair<const key_type, mapped_type>
	Value structure for iterators.
using	const_iterator_range = CxxUtils::iterator_range<const_iterator>
	A range defined by two iterators.

Public Member Functions
	ConcurrentMap (Updater_t &&updater, size_type capacity=64, const Context_t &ctx=Updater_t::defaultContext())
	Ensure that the underlying map can store our types.
	ConcurrentMap (const ConcurrentMap &other, Updater_t &&updater, size_t capacity=64, const Context_t &ctx=Updater_t::defaultContext())
	Constructor from another map.
template<class InputIterator>
	ConcurrentMap (InputIterator f, InputIterator l, Updater_t &&updater, size_type capacity=64, const Context_t &ctx=Updater_t::defaultContext())
	Constructor from a range.
	ConcurrentMap (const ConcurrentMap &other)=delete
	Copy / move / assign not supported.
	ConcurrentMap (ConcurrentMap &&other)=delete
ConcurrentMap &	operator= (const ConcurrentMap &other)=delete
ConcurrentMap &	operator= (ConcurrentMap &&other)=delete
	~ConcurrentMap ()=default
	Destructor.
size_type	size () const
	Return the number of items currently in the map.
bool	empty () const
	Test if the map is currently empty.
size_t	capacity () const
	Return the current size (capacity) of the hash table.
size_t	erased () const
	The number of erased elements in the current table.
const_iterator_range	range () const
	Return an iterator range covering the entire map.
const_iterator	begin () const
	Iterator at the start of the map.
const_iterator	end () const
	Iterator at the end of the map.
const_iterator	cbegin () const
	Iterator at the start of the map.
const_iterator	cend () const
	Iterator at the end of the map.
bool	contains (key_type key) const
	Test if a key is in the container.
size_type	count (key_type key) const
	Return the number of times a given key is in the container.
const_iterator	find (key_type key) const
	Look up an element in the map.
mapped_type	at (key_type key) const
	Look up an element in the map.
std::pair< const_iterator, const_iterator >	equal_range (key_type key) const
	Return a range of iterators with entries matching `key`.
Lock_t	lock ()
	Take a lock on the container.
std::pair< const_iterator, bool >	emplace (key_type key, mapped_type val, const Context_t &ctx=Updater_t::defaultContext())
	Add an element to the map.
std::pair< const_iterator, bool >	emplace (const Lock_t &lock, key_type key, mapped_type val, const Context_t &ctx=Updater_t::defaultContext())
	Add an element to the map, with external locking.
std::pair< const_iterator, bool >	insert_or_assign (key_type key, mapped_type val, const Context_t &ctx=Updater_t::defaultContext())
	Add an element to the map, or overwrite an existing one.
std::pair< const_iterator, bool >	insert_or_assign (const Lock_t &lock, key_type key, mapped_type val, const Context_t &ctx=Updater_t::defaultContext())
	Add an element to the map, or overwrite an existing one, with external locking.
template<class PAIR>
std::pair< const_iterator, bool >	insert (const PAIR &p)
	Add an element to the map.
template<class InputIterator>
void	insert (InputIterator first, InputIterator last)
	Insert a range of elements to the map.
bool	erase (key_type key)
	Erase an entry from the table.
bool	erase (const Lock_t &lock, key_type key)
	Erase an entry from the table, with external locking.
void	reserve (size_type capacity, const Context_t &ctx=Updater_t::defaultContext())
	Increase the table capacity.
void	rehash (size_type capacity)
	Increase the table capacity.
void	clear (size_t capacity, const Context_t &ctx=Updater_t::defaultContext())
	Erase the table and change the capacity.
void	clear (const Context_t &ctx=Updater_t::defaultContext())
	Erase the table (don't change the capacity).
void	forceClear ()
	Erase the table in-place.
void	quiescent (const Context_t &ctx)
	Called when this thread is no longer referencing anything from this container.
void	swap (ConcurrentMap &other)
	Swap this container with another.
Updater_t &	updater ()
	Access the Updater instance.

Private Types
using	val_t = CxxUtils::detail::ConcurrentHashmapVal_t
	Representation type in the underlying map.
using	Impl_t
	The underlying uint->uint hash table.

Private Member Functions
Impl_t::const_iterator	get (key_type key) const
	Do a lookup in the table.
std::pair< const_iterator, bool >	put (key_type key, mapped_type val, bool overwrite=true, const Context_t &ctx=Updater_t::defaultContext())
	Insert / overwrite an entry in the table.
std::pair< const_iterator, bool >	put (const Lock_t &lock, key_type key, mapped_type val, bool overwrite=true, const Context_t &ctx=Updater_t::defaultContext())
	Insert / overwrite an entry in the table, with external locking.

Static Private Member Functions
static key_type	keyAsKey (val_t val)
	Convert an underlying key value to this type's key value.
static val_t	keyAsVal (key_type k)
	Convert this type's key value to an underlying key value.
static mapped_type	mappedAsMapped (val_t val)
	Convert an underlying mapped value to this type's mapped value.
static val_t	mappedAsVal (mapped_type val)
	Convert this type's mapped value to an underlying mapped value.

Private Attributes
Impl_t	m_impl
	The underlying hash table.

Detailed Description

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>
requires (detail::IsConcurrentHashmapPayload<KEY> && detail::IsConcurrentHashmapPayload<VALUE> && detail::IsUpdater<UPDATER> && detail::IsHash<HASHER, KEY> && detail::IsBinaryPredicate<MATCHER, KEY>)
class CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >

Hash map from integers/pointers allowing concurrent, lockless reads.

This class implements a hash map. Both the key and mapped types may be pointers or any numeric type that can fit in a uintptr_t. (However, using floating types for the key is not recommended.) It allows for concurrent access from many threads. Reads can proceed without taking out a lock, while writes are serialized with each other. Thus, this is appropriate for maps which are read-mostly.

This is based on ConcurrentHashmapImpl.

Besides the mapped key and value types, this class is templated on an UPDATER class, which is used to manage the underlying memory. See IsUpdater.h for details. (AthenaKernel/RCUUpdater is a concrete version that should work in the context of Athena.)

The operations used for calculating the hash of the keys and comparing keys can be customized with the HASHER and MATCHER template arguments (though the defaults should usually be fine).

One value of the key must be reserved as a null value, which no real keys may take. By default this is ‘0’, but it may be customized with the NULLVAL template argument. The map may optionally support erasures (via tombstones). To allow this, a second reserved key value must be identified and specified by the TOMBSTONE template argument. Note that the type of the NULLPTR and TOMBSTONE template arguments is a uintptr_t, not KEY.

This mostly supports the interface of std::unordered_map, with a few differences / omissions:

Dereferencing the iterator returns a structure by value, not a reference.
No try_emplace.
No insert methods with hints.
No operator==.
Nothing dealing with the bucket/node interface or merge().

Performance: This is the result from running the test with –perf on my machine, with gcc 13.0.0

ConcurrentMap lookup: 0.843s wall, 0.840s user + 0.000s system = 0.840s CPU (99.6%) iterate: 0.551s wall, 0.540s user + 0.000s system = 0.540s CPU (97.9%) UnorderedMap lookup: 1.890s wall, 1.870s user + 0.000s system = 1.870s CPU (99.0%) iterate: 0.966s wall, 0.970s user + 0.000s system = 0.970s CPU (100.4%) concurrent_unordered_map lookup: 3.718s wall, 3.690s user + 0.010s system = 3.700s CPU (99.5%) iterate: 5.719s wall, 5.690s user + 0.000s system = 5.690s CPU (99.5%) ck_ht lookup: 1.471s wall, 1.460s user + 0.000s system = 1.460s CPU (99.2%) iterate: 1.519s wall, 1.500s user + 0.000s system = 1.500s CPU (98.7%)

The timing for the lookup test of UnorderedMap is probably overly-optimistic, since the test doesn't do any locking in that case.

Definition at line 99 of file ConcurrentMap.h.

Member Typedef Documentation

◆ const_iterator_range

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

using CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::const_iterator_range = CxxUtils::iterator_range<const_iterator>

A range defined by two iterators.

Definition at line 305 of file ConcurrentMap.h.

◆ const_iterator_value

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

using CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::const_iterator_value = std::pair<const key_type, mapped_type>

Value structure for iterators.

Definition at line 236 of file ConcurrentMap.h.

◆ Context_t

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

using CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::Context_t = typename Updater_t::Context_t

Context type.

Definition at line 139 of file ConcurrentMap.h.

◆ Impl_t

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

using CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::Impl_t

private

Initial value:

 typename detail::ConcurrentHashmapImpl<UPDATER,
                                                        Hasher,
                                                        Matcher,
                                                        NULLVAL,
                                                        TOMBSTONE>

The underlying uint->uint hash table.

Definition at line 124 of file ConcurrentMap.h.

◆ key_type

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

using CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::key_type = KEY

Standard STL types.

Definition at line 133 of file ConcurrentMap.h.

◆ Lock_t

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

using CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::Lock_t = typename Impl_t::Lock_t

Type for external locking.

Definition at line 141 of file ConcurrentMap.h.

◆ mapped_type

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

using CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::mapped_type = VALUE

Definition at line 134 of file ConcurrentMap.h.

◆ size_type

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

using CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::size_type = size_t

Definition at line 135 of file ConcurrentMap.h.

◆ Updater_t

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

using CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::Updater_t = typename Impl_t::Updater_t

Updater object.

Definition at line 137 of file ConcurrentMap.h.

◆ val_t

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

using CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::val_t = CxxUtils::detail::ConcurrentHashmapVal_t

private

Representation type in the underlying map.

Definition at line 103 of file ConcurrentMap.h.

Constructor & Destructor Documentation

◆ ConcurrentMap() [1/5]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::ConcurrentMap	(	Updater_t &&	updater,
		size_type	capacity = 64,
		const Context_t &	ctx = Updater_t::defaultContext() )

Ensure that the underlying map can store our types.

Constructor.

Parameters

updater	Object used to manage memory (see comments at the start of the class).
capacity	The initial table capacity. (Will be rounded up to a power of two.)
ctx	Execution context.

◆ ConcurrentMap() [2/5]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::ConcurrentMap	(	const ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE > &	other,
		Updater_t &&	updater,
		size_t	capacity = 64,
		const Context_t &	ctx = Updater_t::defaultContext() )

Constructor from another map.

Parameters

updater	Object used to manage memory (see comments at the start of the class).
capacity	The initial table capacity of the new table. (Will be rounded up to a power of two.)
ctx	Execution context.

(Not really a copy constructor since we need to pass updater.)

◆ ConcurrentMap() [3/5]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

template<class InputIterator>

CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::ConcurrentMap	(	InputIterator	f,
		InputIterator	l,
		Updater_t &&	updater,
		size_type	capacity = 64,
		const Context_t &	ctx = Updater_t::defaultContext() )

Constructor from a range.

Parameters

f	Start iterator for the range.
l	End iterator for the range.
updater	Object used to manage memory (see comments at the start of the class).
capacity	The initial table capacity of the new table. (Will be rounded up to a power of two.)
ctx	Execution context.

Constructor from a range of pairs.

◆ ConcurrentMap() [4/5]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::ConcurrentMap ( const ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE > & other )

delete

Copy / move / assign not supported.

◆ ConcurrentMap() [5/5]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::ConcurrentMap ( ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE > && other )

delete

◆ ~ConcurrentMap()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::~ConcurrentMap ( )

default

Destructor.

Member Function Documentation

◆ at()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

mapped_type CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::at ( key_type key ) const

Look up an element in the map.

Parameters

key	The element to find.

Returns the value associated with the key. Throws std::out_of_range if the key does not exist in the map.

◆ begin()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

const_iterator CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::begin ( ) const

Iterator at the start of the map.

◆ capacity()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

size_t CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::capacity ( ) const

Return the current size (capacity) of the hash table.

◆ cbegin()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

const_iterator CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::cbegin ( ) const

Iterator at the start of the map.

◆ cend()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

const_iterator CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::cend ( ) const

Iterator at the end of the map.

◆ clear() [1/2]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

void CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::clear ( const Context_t & ctx = Updater_t::defaultContext() )

Erase the table (don't change the capacity).

Parameters

ctx	Execution context.

◆ clear() [2/2]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

void CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::clear	(	size_t	capacity,
		const Context_t &	ctx = Updater_t::defaultContext() )

Erase the table and change the capacity.

Parameters

capacity	The new table capacity.
ctx	Execution context.

◆ contains()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

bool CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::contains ( key_type key ) const

Test if a key is in the container.

Parameters

key	The key to test.

◆ count()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

size_type CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::count ( key_type key ) const

Return the number of times a given key is in the container.

Parameters

key	The key to test.

Returns either 0 or 1, depending on whether or not the key is in the map.

◆ emplace() [1/2]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

std::pair< const_iterator, bool > CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::emplace	(	const Lock_t &	lock,
		key_type	key,
		mapped_type	val,
		const Context_t &	ctx = Updater_t::defaultContext() )

Add an element to the map, with external locking.

Parameters

lock	The lock object returned from lock().
key	The key of the new item to add.
val	The value of the new item to add.
ctx	Execution context.

This will not overwrite an existing entry. The first element in the returned pair is an iterator referencing the added item. The second is a flag that is true if a new element was added.

◆ emplace() [2/2]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

std::pair< const_iterator, bool > CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::emplace	(	key_type	key,
		mapped_type	val,
		const Context_t &	ctx = Updater_t::defaultContext() )

Add an element to the map.

Parameters

key	The key of the new item to add.
val	The value of the new item to add.
ctx	Execution context.

This will not overwrite an existing entry. The first element in the returned pair is an iterator referencing the added item. The second is a flag that is true if a new element was added.

◆ empty()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

bool CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::empty ( ) const

Test if the map is currently empty.

◆ end()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

const_iterator CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::end ( ) const

Iterator at the end of the map.

◆ equal_range()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

std::pair< const_iterator, const_iterator > CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::equal_range ( key_type key ) const

Return a range of iterators with entries matching key.

Parameters

key	The element to find.

As keys are unique in this container, this is either a single-element range, or both iterators are equal to end().

◆ erase() [1/2]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

bool CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::erase	(	const Lock_t &	lock,
		key_type	key )

Erase an entry from the table, with external locking.

Parameters

lock	The lock object returned from lock().
key	The key to erase.

Mark the corresponding entry as deleted. Return true on success, false on failure (key not found).

The tombstone value must be different from the null value.

This may cause the key type returned by an iterator to change asynchronously to the tombstone value.

◆ erase() [2/2]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

bool CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::erase ( key_type key )

Erase an entry from the table.

Parameters

key	The key to erase.

Mark the corresponding entry as deleted. Return true on success, false on failure (key not found).

The tombstone value must be different from the null value.

This may cause the key type returned by an iterator to change asynchronously to the tombstone value.

◆ erased()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

size_t CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::erased ( ) const

The number of erased elements in the current table.

◆ find()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

const_iterator CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::find ( key_type key ) const

Look up an element in the map.

Parameters

key	The element to find.

Returns either an iterator referencing the found element or end().

◆ forceClear()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

void CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::forceClear ( )

Erase the table in-place.

This method avoids allocating a new version of the table. However, it is not safe to use concurrently — no other threads may be accessing the container at the same time, either for read or write.

◆ get()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

Impl_t::const_iterator CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::get ( key_type key ) const

private

Do a lookup in the table.

Parameters

key	The key to look up.

Returns an iterator of the underlying map pointing at the found entry or end();

◆ insert() [1/2]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

template<class PAIR>

std::pair< const_iterator, bool > CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::insert ( const PAIR & p )

Add an element to the map.

Parameters

p	The item to add. Should be a pair where first is the key and second is the integer value.

This will not overwrite an existing entry. The first element in the returned pair is an iterator referencing the added item. The second is a flag that is true if a new element was added.

For external locking, use emplace().

◆ insert() [2/2]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

template<class InputIterator>

void CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::insert	(	InputIterator	first,
		InputIterator	last )

Insert a range of elements to the map.

Parameters

first	Start of the range.
last	End of the range.

The range should be a sequence of pairs where first is the string key and second is the integer value.

◆ insert_or_assign() [1/2]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

std::pair< const_iterator, bool > CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::insert_or_assign	(	const Lock_t &	lock,
		key_type	key,
		mapped_type	val,
		const Context_t &	ctx = Updater_t::defaultContext() )

Add an element to the map, or overwrite an existing one, with external locking.

Parameters

lock	The lock object returned from lock().
key	The key of the new item to add.
val	The value of the new item to add.
ctx	Execution context.

This will overwrite an existing entry. The first element in the returned pair is an iterator referencing the added item. The second is a flag that is true if a new element was added.

◆ insert_or_assign() [2/2]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

std::pair< const_iterator, bool > CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::insert_or_assign	(	key_type	key,
		mapped_type	val,
		const Context_t &	ctx = Updater_t::defaultContext() )

Add an element to the map, or overwrite an existing one.

Parameters

key	The key of the new item to add.
val	The value of the new item to add.
ctx	Execution context.

This will overwrite an existing entry. The first element in the returned pair is an iterator referencing the added item. The second is a flag that is true if a new element was added.

◆ keyAsKey()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

key_type CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::keyAsKey ( val_t val )

staticprivate

Convert an underlying key value to this type's key value.

Parameters

val	The underlying key value.

◆ keyAsVal()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

val_t CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::keyAsVal ( key_type k )

staticprivate

Convert this type's key value to an underlying key value.

Parameters

k The key.

◆ lock()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

Lock_t CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::lock ( )

Take a lock on the container.

Take a lock on the container. The lock can then be passed to insertion methods, allowing to factor out the locking inside loops. The lock will be released when the lock object is destroyed.

◆ mappedAsMapped()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

mapped_type CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::mappedAsMapped ( val_t val )

staticprivate

Convert an underlying mapped value to this type's mapped value.

Parameters

val	The underlying mapped value.

◆ mappedAsVal()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

val_t CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::mappedAsVal ( mapped_type val )

staticprivate

Convert this type's mapped value to an underlying mapped value.

Parameters

val	The mapped value.

◆ operator=() [1/2]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

ConcurrentMap & CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::operator= ( ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE > && other )

delete

◆ operator=() [2/2]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

ConcurrentMap & CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::operator= ( const ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE > & other )

delete

◆ put() [1/2]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

std::pair< const_iterator, bool > CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::put	(	const Lock_t &	lock,
		key_type	key,
		mapped_type	val,
		bool	overwrite = true,
		const Context_t &	ctx = Updater_t::defaultContext() )

private

Insert / overwrite an entry in the table, with external locking.

Parameters

lock	The lock object returned from lock().
key	The key of the new item to add.
val	The value of the new item to add.
overwrite	If true, allow overwriting an existing entry.
ctx	Execution context.

The first element in the returned pair is an iterator referencing the added item. The second is a flag that is true if a new element was added.

◆ put() [2/2]

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

std::pair< const_iterator, bool > CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::put	(	key_type	key,
		mapped_type	val,
		bool	overwrite = true,
		const Context_t &	ctx = Updater_t::defaultContext() )

private

Insert / overwrite an entry in the table.

Parameters

key	The key of the new item to add.
val	The value of the new item to add.
overwrite	If true, allow overwriting an existing entry.
ctx	Execution context.

The first element in the returned pair is an iterator referencing the added item. The second is a flag that is true if a new element was added.

◆ quiescent()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

void CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::quiescent ( const Context_t & ctx )

Called when this thread is no longer referencing anything from this container.

Parameters

ctx	Execution context.

◆ range()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

const_iterator_range CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::range ( ) const

Return an iterator range covering the entire map.

◆ rehash()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

void CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::rehash ( size_type capacity )

Increase the table capacity.

Parameters

capacity The new table capacity.

No action will be taken if capacity is smaller than the current capacity.

◆ reserve()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

void CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::reserve	(	size_type	capacity,
		const Context_t &	ctx = Updater_t::defaultContext() )

Increase the table capacity.

Parameters

capacity	The new table capacity.
ctx	Execution context.

No action will be taken if capacity is smaller than the current capacity.

◆ size()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

size_type CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::size ( ) const

Return the number of items currently in the map.

◆ swap()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

void CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::swap ( ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE > & other )

Swap this container with another.

Parameters

other The container with which to swap.

This will also call swap on the Updater object; hence, the Updater object must also support swap. The Hasher and Matcher instances are NOT swapped.

This operation is NOT thread-safe. No other threads may be accessing either container during this operation.

◆ updater()

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

Updater_t & CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::updater ( )

Access the Updater instance.

Member Data Documentation

◆ m_impl

template<class KEY, class VALUE, template< class > class UPDATER, class HASHER = std::hash<KEY>, class MATCHER = std::equal_to<KEY>, detail::ConcurrentHashmapVal_t NULLVAL = 0, detail::ConcurrentHashmapVal_t TOMBSTONE = NULLVAL>

Impl_t CxxUtils::ConcurrentMap< KEY, VALUE, UPDATER, HASHER, MATCHER, NULLVAL, TOMBSTONE >::m_impl

private

The underlying hash table.

Definition at line 679 of file ConcurrentMap.h.

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

ConcurrentMap.h

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator_range

◆ const_iterator_value

◆ Context_t

◆ Impl_t

◆ key_type

◆ Lock_t

◆ mapped_type

◆ size_type

◆ Updater_t

◆ val_t

Constructor & Destructor Documentation

◆ ConcurrentMap() [1/5]

◆ ConcurrentMap() [2/5]

◆ ConcurrentMap() [3/5]

◆ ConcurrentMap() [4/5]

◆ ConcurrentMap() [5/5]

◆ ~ConcurrentMap()

Member Function Documentation

◆ at()

◆ begin()

◆ capacity()

◆ cbegin()

◆ cend()

◆ clear() [1/2]

◆ clear() [2/2]

◆ contains()

◆ count()

◆ emplace() [1/2]

◆ emplace() [2/2]

◆ empty()

◆ end()

◆ equal_range()

◆ erase() [1/2]

◆ erase() [2/2]

◆ erased()

◆ find()

◆ forceClear()

◆ get()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_or_assign() [1/2]

◆ insert_or_assign() [2/2]

◆ keyAsKey()

◆ keyAsVal()

◆ lock()

◆ mappedAsMapped()

◆ mappedAsVal()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ put() [1/2]

◆ put() [2/2]

◆ quiescent()

◆ range()

◆ rehash()

◆ reserve()

◆ size()

◆ swap()

◆ updater()

Member Data Documentation

◆ m_impl