Classes
class	HashmapLock
	Helper to allow for external locking with put(). More...
struct	CHMTableIterator
	Helper to generate hash probes. More...
class	Table
	Hash table allowing concurrent, lockless reads. More...
class	const_iterator
	Bidirectional iterator over occupied table entries. More...
struct	SizedUInt
struct	SizedUInt< 1 >
struct	SizedUInt< 2 >
struct	SizedUInt< 4 >
struct	SizedUInt< 8 >
union	UIntConv
	Helpers for converting between uintptr_t and a pointer or integer. More...
union	UIntConv< uintptr_t >

Concepts
concept	IsHash
concept	IsBinaryPredicate
concept	IsContiguousContainer
concept	InputValIterator
concept	SimpleAssociativeContainer
concept	PairAssociativeContainer
concept	AllocationFunction
concept	RefCounted
	Has addRef() and release().
concept	IsConcurrentHashmapPayload
	Concept for a value that can be saved in a concurrent hash map.
concept	IsConcurrentRangeCompare
	Concept for comparison template argument.
concept	IsUpdater
	Concept check for Updater class used by concurrent classes.

Typedefs
using	ConcurrentHashmapVal_t = uintptr_t
	Type used for keys and values — an unsigned big enough to hold a pointer.
using	Updater_t = UPDATER_<Table>
using	Context_t = typename Updater_t::Context_t
using	const_iterator_range = std::pair<const_iterator, const_iterator>

Functions
	ConcurrentHashmapImpl (Updater_t &&updater, size_t capacity_in, const Hasher_t &hasher, const Matcher_t &matcher, const typename Updater_t::Context_t &ctx)
	Constructor.
	ConcurrentHashmapImpl (const ConcurrentHashmapImpl &)=delete
ConcurrentHashmapImpl &	operator= (const ConcurrentHashmapImpl &)=delete
size_t	size () const
	Return the number of items currently stored.
size_t	capacity () const
	Return the current table size.
size_t	erased () const
	The number of erased elements in the current table.
const Hasher_t &	hasher () const
	Return the hasher object.
const Matcher_t &	matcher () const
	Return the matcher object.
Lock_t	lock ()
	Take a lock on the container.
std::pair< const_iterator, bool >	put (val_t key, size_t hash, val_t val, bool overwrite, const typename Updater_t::Context_t &ctx)
	Add an entry to the table.
std::pair< const_iterator, bool >	put (const Lock_t &lock, val_t key, size_t hash, val_t val, bool overwrite, const typename Updater_t::Context_t &ctx)
	Add an entry to the table, with external locking.
const_iterator	get (val_t key, size_t hash) const
	Look up an entry in the table.
bool	erase (val_t key, size_t hash)
	Erase an entry from the table.
bool	erase (const Lock_t &lock, val_t key, size_t hash)
	Erase an entry from the table, with external locking.
const_iterator_range	range () const
	Return a range that can be used to iterate over the container.
const_iterator	begin () const
	A begin iterator for the container.
const_iterator	end () const
	An end iterator for the container.
const_iterator	clear (size_t capacity, const typename Updater_t::Context_t &ctx)
	Erase the table and change the capacity.
const_iterator	clear (const typename Updater_t::Context_t &ctx)
	Erase the table (don't change the capacity).
void	forceClear ()
	Erase the table by filling it with nulls.
void	reserve (size_t capacity, const typename Updater_t::Context_t &ctx)
	Increase the table capacity.
void	quiescent (const typename Updater_t::Context_t &ctx)
	Called when this thread is no longer referencing anything from this container.
void	swap (ConcurrentHashmapImpl &other)
	Swap this container with another.
Updater_t &	updater ()
	Access the Updater instance.
bool	grow (const Lock_t &lock, const typename Updater_t::Context_t &ctx)
	Make the table larger.
bool	grow (const Lock_t &lock, size_t new_capacity, const typename Updater_t::Context_t &ctx)
	Make the table larger.
static uint64_t	round_up (uint64_t)

Variables
*Updater object managing memory See above Updater_t	m_updater
*The hash object const Hasher_t	m_hasher
*The key match object const Matcher_t	m_matcher
The current table instance Must be holding the mutex to access this Table	m_table
*Number of entries in the map std::atomic< size_t >	m_size
*Number of entries that have been erased std::atomic< size_t >	m_erased
*Mutex to serialize changes to the map std::mutex	m_mutex

Typedef Documentation

◆ ConcurrentHashmapVal_t

using CxxUtils::detail::ConcurrentHashmapVal_t = uintptr_t

Type used for keys and values — an unsigned big enough to hold a pointer.

Need to have this defined outside of ConcurrentHashmapImpl itself in order to avoid instantiation circularities, as the HASHER_ and MATCHER_ classes will probably want to use it.

Definition at line 40 of file ConcurrentHashmapImpl.h.

◆ const_iterator_range

using CxxUtils::detail::const_iterator_range = std::pair<const_iterator, const_iterator>

Definition at line 584 of file ConcurrentHashmapImpl.h.

◆ Context_t

using CxxUtils::detail::Context_t = typename Updater_t::Context_t

Definition at line 354 of file ConcurrentHashmapImpl.h.

◆ Updater_t

using CxxUtils::detail::Updater_t = UPDATER_<Table>

Definition at line 352 of file ConcurrentHashmapImpl.h.

Function Documentation

◆ begin()

const_iterator CxxUtils::detail::begin ( ) const

A begin iterator for the container.

◆ capacity()

size_t CxxUtils::detail::capacity ( ) const

Return the current table size.

◆ clear() [1/2]

const_iterator CxxUtils::detail::clear ( const typename Updater_t::Context_t & ctx )

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

Parameters

ctx	Execution context.

Returns an iterator pointing at the start of the old table.

◆ clear() [2/2]

const_iterator CxxUtils::detail::clear	(	size_t	capacity,
		const typename Updater_t::Context_t &	ctx )

Erase the table and change the capacity.

Parameters

capacity	The new table capacity.
ctx	Execution context.

Returns an iterator pointing at the start of the old table.

◆ ConcurrentHashmapImpl() [1/2]

CxxUtils::detail::ConcurrentHashmapImpl ( const ConcurrentHashmapImpl & )

delete

◆ ConcurrentHashmapImpl() [2/2]

CxxUtils::detail::ConcurrentHashmapImpl	(	Updater_t &&	updater,
		size_t	capacity_in,
		const Hasher_t &	hasher,
		const Matcher_t &	matcher,
		const typename Updater_t::Context_t &	ctx )

Constructor.

Parameters

updater	Object used to manage memory (see comments at the start of the class).
capacity	Minimum initial table size.
hasher	Hash object to use.
matcher	Key match object to use.
ctx	Execution context.

◆ end()

const_iterator CxxUtils::detail::end ( ) const

An end iterator for the container.

◆ erase() [1/2]

bool CxxUtils::detail::erase	(	const Lock_t &	lock,
		val_t	key,
		size_t	hash )

Erase an entry from the table, with external locking.

Parameters

lock	The lock object returned from lock().
key	The key to erase.
hash	The hash of the key.

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.

Take care if the key or value types require memory allocation.

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

◆ erase() [2/2]

bool CxxUtils::detail::erase	(	val_t	key,
		size_t	hash )

Erase an entry from the table.

Parameters

key	The key to erase.
hash	The hash of the key.

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.

Take care if the key or value types require memory allocation.

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

◆ erased()

size_t CxxUtils::detail::erased ( ) const

The number of erased elements in the current table.

◆ forceClear()

void CxxUtils::detail::forceClear ( )

Erase the table by filling it with nulls.

This method is not safe to use concurrently — no other threads may be accessing the container at the same time, either for read or write.

◆ get()

const_iterator CxxUtils::detail::get	(	val_t	key,
		size_t	hash ) const

Look up an entry in the table.

Parameters

key	The key to find.
hash	The hash of the key.

Returns an iterator pointing at the found entry, or end().

◆ grow() [1/2]

bool CxxUtils::detail::grow	(	const Lock_t &	lock,
		const typename Updater_t::Context_t &	ctx )

private

Make the table larger.

Parameters

ctx	Execution context.

Must be holding a lock on the mutex to call this.

◆ grow() [2/2]

bool CxxUtils::detail::grow	(	const Lock_t &	lock,
		size_t	new_capacity,
		const typename Updater_t::Context_t &	ctx )

private

Make the table larger.

Parameters

new_capacity	The new table capacity (must be a power of 2).
ctx	Execution context.

Must be holding a lock on the mutex to call this.

◆ hasher()

const Hasher_t & CxxUtils::detail::hasher ( ) const

Return the hasher object.

◆ lock()

Lock_t CxxUtils::detail::lock ( )

Take a lock on the container.

Take a lock on the container. The lock can then be passed to put(), allowing to factor out the locking when put() gets used in a loop. The lock will be released when the lock object is destroyed.

◆ matcher()

const Matcher_t & CxxUtils::detail::matcher ( ) const

Return the matcher object.

◆ operator=()

ConcurrentHashmapImpl & CxxUtils::detail::operator= ( const ConcurrentHashmapImpl & )

delete

◆ put() [1/2]

std::pair< const_iterator, bool > CxxUtils::detail::put	(	const Lock_t &	lock,
		val_t	key,
		size_t	hash,
		val_t	val,
		bool	overwrite,
		const typename Updater_t::Context_t &	ctx )

Add an entry to the table, with external locking.

Parameters

lock	The lock object returned from lock().
key	The key to insert.
hash	The hash of the key.
val	The value to insert.
overwrite	If true, then overwrite an existing entry. If false, an existing entry will not be changed.
ctx	Execution context.

If the key already exists, then its value will be updated. Returns an iterator pointing at the entry and a flag which is true if a new element was added.

◆ put() [2/2]

std::pair< const_iterator, bool > CxxUtils::detail::put	(	val_t	key,
		size_t	hash,
		val_t	val,
		bool	overwrite,
		const typename Updater_t::Context_t &	ctx )

Add an entry to the table.

Parameters

key	The key to insert.
hash	The hash of the key.
val	The value to insert.
overwrite	If true, then overwrite an existing entry. If false, an existing entry will not be changed.
ctx	Execution context.

If the key already exists, then its value will be updated. Returns an iterator pointing at the entry and a flag which is true if a new element was added.

◆ quiescent()

void CxxUtils::detail::quiescent ( const typename Updater_t::Context_t & ctx )

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

Parameters

ctx	Execution context.

◆ range()

const_iterator_range CxxUtils::detail::range ( ) const

Return a range that can be used to iterate over the container.

◆ reserve()

void CxxUtils::detail::reserve	(	size_t	capacity,
		const typename Updater_t::Context_t &	ctx )

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.

◆ round_up()

uint64_t CxxUtils::detail::round_up ( uint64_t )

staticprivate

◆ size()

size_t CxxUtils::detail::size ( ) const

Return the number of items currently stored.

(not necessarily synced)

◆ swap()

void CxxUtils::detail::swap ( ConcurrentHashmapImpl & 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()

Updater_t & CxxUtils::detail::updater ( )

Access the Updater instance.

Variable Documentation

◆ m_erased

* Number of entries that have been erased std::atomic<size_t> CxxUtils::detail::m_erased

private

Definition at line 709 of file ConcurrentHashmapImpl.h.

◆ m_hasher

* The hash object const Hasher_t CxxUtils::detail::m_hasher

private

Definition at line 701 of file ConcurrentHashmapImpl.h.

◆ m_matcher

* The key match object const Matcher_t CxxUtils::detail::m_matcher

private

Definition at line 703 of file ConcurrentHashmapImpl.h.

◆ m_mutex

* Mutex to serialize changes to the map std::mutex CxxUtils::detail::m_mutex

private

Definition at line 711 of file ConcurrentHashmapImpl.h.

◆ m_size

* Number of entries in the map std::atomic<size_t> CxxUtils::detail::m_size

private

Definition at line 707 of file ConcurrentHashmapImpl.h.

◆ m_table

* The current table instance Must be holding the mutex to access this Table* CxxUtils::detail::m_table

private

Definition at line 705 of file ConcurrentHashmapImpl.h.

◆ m_updater

* Updater object managing memory See above Updater_t CxxUtils::detail::m_updater

private

Definition at line 699 of file ConcurrentHashmapImpl.h.

Classes

Concepts

Typedefs

Functions

Variables

Typedef Documentation

◆ ConcurrentHashmapVal_t

◆ const_iterator_range

◆ Context_t

◆ Updater_t

Function Documentation

◆ begin()

◆ capacity()

◆ clear() [1/2]

◆ clear() [2/2]

◆ ConcurrentHashmapImpl() [1/2]

◆ ConcurrentHashmapImpl() [2/2]

◆ end()

◆ erase() [1/2]

◆ erase() [2/2]

◆ erased()

◆ forceClear()

◆ get()

◆ grow() [1/2]

◆ grow() [2/2]

◆ hasher()

◆ lock()

◆ matcher()

◆ operator=()

◆ put() [1/2]

◆ put() [2/2]

◆ quiescent()

◆ range()

◆ reserve()

◆ round_up()

◆ size()

◆ swap()

◆ updater()

Variable Documentation

◆ m_erased

◆ m_hasher

◆ m_matcher

◆ m_mutex

◆ m_size

◆ m_table

◆ m_updater