A set of pointers, allowing concurrent, lockless queries. More...

#include <ConcurrentPtrSet.h>

Collaboration diagram for CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >:

Classes
class	const_iterator
	Iterator class. More...

struct	Hasher
	Hash functional for keys. More...

struct	Matcher
	Matching functional for keys. More...

Public Types
using	key_type = VALUE *
	Standard STL types. More...

using	const_key_type = const VALUE *

using	size_type = size_t

using	Updater_t = typename Impl_t::Updater_t
	Updater object. More...

using	Context_t = typename Updater_t::Context_t
	Context type. More...

using	Lock_t = typename Impl_t::Lock_t
	Type for external locking. More...

using	const_iterator_value = const key_type
	Value type for iterators. More...

typedef boost::iterator_range< const_iterator >	const_iterator_range
	A range defined by two iterators. More...

Public Member Functions
	ConcurrentPtrSet (Updater_t &&updater, size_type capacity=64, const Context_t &ctx=Updater_t::defaultContext())
	Constructor. More...

	ConcurrentPtrSet (const ConcurrentPtrSet &other, Updater_t &&updater, size_t capacity=64, const Context_t &ctx=Updater_t::defaultContext())
	Constructor from another set. More...

template<class InputIterator >
	ConcurrentPtrSet (InputIterator f, InputIterator l, Updater_t &&updater, size_type capacity=64, const Context_t &ctx=Updater_t::defaultContext())
	Constructor from a range. More...

	ConcurrentPtrSet (const ConcurrentPtrSet &other)=delete
	Copy / move / assign not supported. More...

	ConcurrentPtrSet (ConcurrentPtrSet &&other)=delete

ConcurrentPtrSet &	operator= (const ConcurrentPtrSet &other)=delete

ConcurrentPtrSet &	operator= (ConcurrentPtrSet &&other)=delete

	~ConcurrentPtrSet ()
	Destructor. More...

size_type	size () const
	Return the number of items currently in the set. More...

bool	empty () const
	Test if the set is currently empty. More...

size_t	capacity () const
	Return the current size (capacity) of the hash table. More...

const_iterator_range	range () const
	Return an iterator range covering the entire set. More...

const_iterator	begin () const
	Iterator at the start of the set. More...

const_iterator	end () const
	Iterator at the end of the set. More...

const_iterator	cbegin () const
	Iterator at the start of the set. More...

const_iterator	cend () const
	Iterator at the end of the set. More...

bool	contains (const const_key_type key) const
	Test if a key is in the container. More...

size_type	count (const const_key_type key) const
	Return the number of times a given key is in the container. More...

const_iterator	find (const const_key_type key) const
	Look up an element in the set. More...

std::pair< const_iterator, const_iterator >	equal_range (const const_key_type key) const
	Return a range of iterators with entries matching `key`. More...

Lock_t	lock ()
	Take a lock on the container. More...

std::pair< const_iterator, bool >	emplace (const key_type key, const Context_t &ctx=Updater_t::defaultContext())
	Add an element to the set. More...

std::pair< const_iterator, bool >	emplace (const Lock_t &lock, const key_type key, const Context_t &ctx=Updater_t::defaultContext())
	Add an element to the set, with external locking. More...

std::pair< const_iterator, bool >	insert (const key_type p)
	Add an element to the set. More...

template<class InputIterator >
void	insert (InputIterator first, InputIterator last)
	Insert a range of elements to the set. More...

void	reserve (size_type capacity, const Context_t &ctx=Updater_t::defaultContext())
	Increase the table capacity. More...

void	rehash (size_type capacity)
	Increase the table capacity. More...

void	clear (size_t capacity, const Context_t &ctx=Updater_t::defaultContext())
	Erase the table and change the capacity. More...

void	clear (const Context_t &ctx=Updater_t::defaultContext())
	Erase the table (don't change the capacity). More...

void	quiescent (const Context_t &ctx)
	Called when this thread is no longer referencing anything from this container. More...

void	swap (ConcurrentPtrSet &other)
	Swap this container with another. More...

Updater_t &	updater ()
	Access the Updater instance. More...

Private Types
using	Impl_t = typename detail::ConcurrentHashmapImpl< UPDATER, Hasher, Matcher >

using	val_t = CxxUtils::detail::ConcurrentHashmapVal_t
	Representation type in the underlying map. More...

Private Member Functions
Impl_t::const_iterator	get (const const_key_type key) const
	Do a lookup in the table. More...

std::pair< const_iterator, bool >	put (const key_type key, const Context_t &ctx=Updater_t::defaultContext())
	Insert an entry in the table. More...

std::pair< const_iterator, bool >	put (const Lock_t &lock, const key_type key, const Context_t &ctx=Updater_t::defaultContext())
	Insert an entry in the table, with external locking. More...

Static Private Member Functions
static key_type	keyAsPtr (val_t val)
	Convert an underlying key value to a pointer. More...

static val_t	keyAsVal (const const_key_type p)
	Convert a pointer to an underlying key value. More...

Private Attributes
Impl_t	m_impl
	The underlying hash table. More...

Detailed Description

template<class VALUE, template< class > class UPDATER>
class CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >

A set of pointers, allowing concurrent, lockless queries.

This class implements a set of pointers, allowing for concurrent access from many threads. Queries can proceed without taking out a lock, while insertions are serialized with each other. Thus, this is appropriate for sets which are read-mostly.

This is based on ConcurrentHashmapImpl.

Besides the pointer target type, 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.)

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

No try_emplace.
No insert methods with hints.
No erase() methods.
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 12.1.1:

ConcurrentPtrSet lookup: 1.225s wall, 1.220s user + 0.000s system = 1.220s CPU (99.6%) iterate: 0.646s wall, 0.640s user + 0.000s system = 0.640s CPU (99.0%) UnorderedSet lookup: 1.894s wall, 1.880s user + 0.000s system = 1.880s CPU (99.3%) iterate: 1.064s wall, 1.060s user + 0.000s system = 1.060s CPU (99.6%) concurrent_unordered_set lookup: 5.369s wall, 5.320s user + 0.000s system = 5.320s CPU (99.1%) iterate: 4.151s wall, 4.130s user + 0.000s system = 4.130s CPU (99.5%) ck_ht lookup: 2.034s wall, 2.020s user + 0.000s system = 2.020s CPU (99.3%) iterate: 1.500s wall, 1.500s user + 0.000s system = 1.500s CPU (100.0%)

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

Definition at line 76 of file ConcurrentPtrSet.h.

Member Typedef Documentation

◆ const_iterator_range

template<class VALUE , template< class > class UPDATER>

typedef boost::iterator_range<const_iterator> CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::const_iterator_range

A range defined by two iterators.

Definition at line 250 of file ConcurrentPtrSet.h.

◆ const_iterator_value

template<class VALUE , template< class > class UPDATER>

using CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::const_iterator_value = const key_type

Value type for iterators.

Definition at line 181 of file ConcurrentPtrSet.h.

◆ const_key_type

template<class VALUE , template< class > class UPDATER>

using CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::const_key_type = const VALUE*

Definition at line 90 of file ConcurrentPtrSet.h.

◆ Context_t

template<class VALUE , template< class > class UPDATER>

using CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::Context_t = typename Updater_t::Context_t

Context type.

Definition at line 95 of file ConcurrentPtrSet.h.

◆ Impl_t

template<class VALUE , template< class > class UPDATER>

using CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::Impl_t = typename detail::ConcurrentHashmapImpl<UPDATER, Hasher, Matcher>

private

Definition at line 82 of file ConcurrentPtrSet.h.

◆ key_type

template<class VALUE , template< class > class UPDATER>

using CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::key_type = VALUE*

Standard STL types.

Definition at line 89 of file ConcurrentPtrSet.h.

◆ Lock_t

template<class VALUE , template< class > class UPDATER>

using CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::Lock_t = typename Impl_t::Lock_t

Type for external locking.

Definition at line 97 of file ConcurrentPtrSet.h.

◆ size_type

template<class VALUE , template< class > class UPDATER>

using CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::size_type = size_t

Definition at line 91 of file ConcurrentPtrSet.h.

◆ Updater_t

template<class VALUE , template< class > class UPDATER>

using CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::Updater_t = typename Impl_t::Updater_t

Updater object.

Definition at line 93 of file ConcurrentPtrSet.h.

◆ val_t

template<class VALUE , template< class > class UPDATER>

using CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::val_t = CxxUtils::detail::ConcurrentHashmapVal_t

private

Representation type in the underlying map.

Definition at line 84 of file ConcurrentPtrSet.h.

Constructor & Destructor Documentation

◆ ConcurrentPtrSet() [1/5]

template<class VALUE , template< class > class UPDATER>

CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::ConcurrentPtrSet	(	Updater_t &&	updater,
		size_type	capacity = `64`,
		const Context_t &	ctx = `Updater_t::defaultContext()`
	)

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.

◆ ConcurrentPtrSet() [2/5]

template<class VALUE , template< class > class UPDATER>

CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::ConcurrentPtrSet	(	const ConcurrentPtrSet< VALUE, UPDATER > &	other,
		Updater_t &&	updater,
		size_t	capacity = `64`,
		const Context_t &	ctx = `Updater_t::defaultContext()`
	)

Constructor from another set.

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

◆ ConcurrentPtrSet() [3/5]

template<class VALUE , template< class > class UPDATER>

template<class InputIterator >

CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::ConcurrentPtrSet	(	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.

◆ ConcurrentPtrSet() [4/5]

template<class VALUE , template< class > class UPDATER>

CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::ConcurrentPtrSet ( const ConcurrentPtrSet< VALUE, UPDATER > & other )

delete

Copy / move / assign not supported.

◆ ConcurrentPtrSet() [5/5]

template<class VALUE , template< class > class UPDATER>

CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::ConcurrentPtrSet ( ConcurrentPtrSet< VALUE, UPDATER > && other )

delete

◆ ~ConcurrentPtrSet()

template<class VALUE , template< class > class UPDATER>

CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::~ConcurrentPtrSet ( )

Destructor.

Member Function Documentation

◆ begin()

template<class VALUE , template< class > class UPDATER>

const_iterator CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::begin ( ) const

Iterator at the start of the set.

◆ capacity()

template<class VALUE , template< class > class UPDATER>

size_t CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::capacity ( ) const

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

◆ cbegin()

template<class VALUE , template< class > class UPDATER>

const_iterator CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::cbegin ( ) const

Iterator at the start of the set.

◆ cend()

template<class VALUE , template< class > class UPDATER>

const_iterator CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::cend ( ) const

Iterator at the end of the set.

◆ clear() [1/2]

template<class VALUE , template< class > class UPDATER>

void CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::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 VALUE , template< class > class UPDATER>

void CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::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 VALUE , template< class > class UPDATER>

bool CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::contains ( const const_key_type key ) const

Test if a key is in the container.

Parameters

key	The key to test.

◆ count()

template<class VALUE , template< class > class UPDATER>

size_type CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::count ( const const_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 set.

◆ emplace() [1/2]

template<class VALUE , template< class > class UPDATER>

std::pair<const_iterator, bool> CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::emplace	(	const key_type	key,
		const Context_t &	ctx = `Updater_t::defaultContext()`
	)

Add an element to the set.

Parameters

key	The key 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 VALUE , template< class > class UPDATER>

std::pair<const_iterator, bool> CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::emplace	(	const Lock_t &	lock,
		const key_type	key,
		const Context_t &	ctx = `Updater_t::defaultContext()`
	)

Add an element to the set, with external locking.

Parameters

lock	The lock object returned from lock().
key	The key 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 VALUE , template< class > class UPDATER>

bool CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::empty ( ) const

Test if the set is currently empty.

◆ end()

template<class VALUE , template< class > class UPDATER>

const_iterator CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::end ( ) const

Iterator at the end of the set.

◆ equal_range()

template<class VALUE , template< class > class UPDATER>

std::pair<const_iterator, const_iterator> CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::equal_range ( const const_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().

◆ find()

template<class VALUE , template< class > class UPDATER>

const_iterator CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::find ( const const_key_type key ) const

Look up an element in the set.

Parameters

key	The element to find.

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

◆ get()

template<class VALUE , template< class > class UPDATER>

Impl_t::const_iterator CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::get ( const const_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 VALUE , template< class > class UPDATER>

std::pair<const_iterator, bool> CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::insert ( const key_type p )

Add an element to the set.

Parameters

p	The item to add.

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.

This is the same as emplace(). Use that for the case of external locking.

◆ insert() [2/2]

template<class VALUE , template< class > class UPDATER>

template<class InputIterator >

void CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::insert	(	InputIterator	first,
		InputIterator	last
	)

Insert a range of elements to the set.

Parameters

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

◆ keyAsPtr()

template<class VALUE , template< class > class UPDATER>

static key_type CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::keyAsPtr ( val_t val )

staticprivate

Convert an underlying key value to a pointer.

Parameters

val	The underlying key value.

◆ keyAsVal()

template<class VALUE , template< class > class UPDATER>

static val_t CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::keyAsVal ( const const_key_type p )

staticprivate

Convert a pointer to an underlying key value.

Parameters

p	The pointer.

◆ lock()

template<class VALUE , template< class > class UPDATER>

Lock_t CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::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.

◆ operator=() [1/2]

template<class VALUE , template< class > class UPDATER>

ConcurrentPtrSet& CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::operator= ( ConcurrentPtrSet< VALUE, UPDATER > && other )

delete

◆ operator=() [2/2]

template<class VALUE , template< class > class UPDATER>

ConcurrentPtrSet& CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::operator= ( const ConcurrentPtrSet< VALUE, UPDATER > & other )

delete

◆ put() [1/2]

template<class VALUE , template< class > class UPDATER>

std::pair<const_iterator, bool> CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::put	(	const key_type	key,
		const Context_t &	ctx = `Updater_t::defaultContext()`
	)

private

Insert an entry in the table.

Parameters

key	The new item to add.
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 VALUE , template< class > class UPDATER>

std::pair<const_iterator, bool> CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::put	(	const Lock_t &	lock,
		const key_type	key,
		const Context_t &	ctx = `Updater_t::defaultContext()`
	)

private

Insert an entry in the table, with external locking.

Parameters

lock	The lock object returned from lock().
key	The new item to add.
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 VALUE , template< class > class UPDATER>

void CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::quiescent ( const Context_t & ctx )

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

Parameters

ctx	Execution context.

◆ range()

template<class VALUE , template< class > class UPDATER>

const_iterator_range CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::range ( ) const

Return an iterator range covering the entire set.

◆ rehash()

template<class VALUE , template< class > class UPDATER>

void CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::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 VALUE , template< class > class UPDATER>

void CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::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 VALUE , template< class > class UPDATER>

size_type CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::size ( ) const

Return the number of items currently in the set.

◆ swap()

template<class VALUE , template< class > class UPDATER>

void CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::swap ( ConcurrentPtrSet< VALUE, UPDATER > & 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.

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

◆ updater()

template<class VALUE , template< class > class UPDATER>

Updater_t& CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::updater ( )

Access the Updater instance.

Member Data Documentation

◆ m_impl

template<class VALUE , template< class > class UPDATER>

Impl_t CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >::m_impl

private

The underlying hash table.

Definition at line 533 of file ConcurrentPtrSet.h.

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

ConcurrentPtrSet.h

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

template<class VALUE, template< class > class UPDATER> class CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >

Member Typedef Documentation

◆ const_iterator_range

◆ const_iterator_value

◆ const_key_type

◆ Context_t

◆ Impl_t

◆ key_type

◆ Lock_t

◆ size_type

◆ Updater_t

◆ val_t

Constructor & Destructor Documentation

◆ ConcurrentPtrSet() [1/5]

◆ ConcurrentPtrSet() [2/5]

◆ ConcurrentPtrSet() [3/5]

◆ ConcurrentPtrSet() [4/5]

◆ ConcurrentPtrSet() [5/5]

◆ ~ConcurrentPtrSet()

Member Function Documentation

◆ begin()

◆ capacity()

◆ cbegin()

◆ cend()

◆ clear() [1/2]

◆ clear() [2/2]

◆ contains()

◆ count()

◆ emplace() [1/2]

◆ emplace() [2/2]

◆ empty()

◆ end()

◆ equal_range()

◆ find()

◆ get()

◆ insert() [1/2]

◆ insert() [2/2]

◆ keyAsPtr()

◆ keyAsVal()

◆ lock()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ put() [1/2]

◆ put() [2/2]

◆ quiescent()

◆ range()

◆ rehash()

◆ reserve()

◆ size()

◆ swap()

◆ updater()

Member Data Documentation

◆ m_impl

template<class VALUE, template< class > class UPDATER>
class CxxUtils::ConcurrentPtrSet< VALUE, UPDATER >