Hash table allowing concurrent, lockless reads. More...

#include <ConcurrentHashmapImpl.h>

Collaboration diagram for CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >:

Classes
class	const_iterator
	Bidirectional iterator over occupied table entries. More...

struct	entry_t
	One entry in the hash table. More...

class	Table
	Table of hash entries. More...

Public Types
using	val_t = ConcurrentHashmapVal_t
	Type used for keys and values — an unsigned big enough to hold a pointer. More...

using	Hasher_t = HASHER_
	Hash object. More...

using	Matcher_t = MATCHER_
	Key match object. More...

using	Lock_t = HashmapLock
	Lock class used for external locking. More...

using	Updater_t = UPDATER_< Table >
	Updater object. More...

using	Context_t = typename Updater_t::Context_t
	Context type for the updater. More...

using	const_iterator_range = std::pair< const_iterator, const_iterator >
	Two iterators defining a range. More...

Public Member 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. More...

	ConcurrentHashmapImpl (const ConcurrentHashmapImpl &)=delete

ConcurrentHashmapImpl &	operator= (const ConcurrentHashmapImpl &)=delete

size_t	size () const
	Return the number of items currently stored. More...

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

size_t	erased () const
	The number of erased elements in the current table. More...

const Hasher_t &	hasher () const
	Return the hasher object. More...

const Matcher_t &	matcher () const
	Return the matcher object. More...

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

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

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

const_iterator	get (val_t key, size_t hash) const
	Look up an entry in the table. More...

bool	erase (val_t key, size_t hash)
	Erase an entry from the table. More...

bool	erase (const Lock_t &lock, val_t key, size_t hash)
	Erase an entry from the table, with external locking. More...

const_iterator_range	range () const
	Return a range that can be used to iterate over the container. More...

const_iterator	begin () const
	A begin iterator for the container. More...

const_iterator	end () const
	An end iterator for the container. More...

const_iterator	clear (size_t capacity, const typename Updater_t::Context_t &ctx)
	Erase the table and change the capacity. More...

const_iterator	clear (const typename Updater_t::Context_t &ctx)
	Erase the table (don't change the capacity). More...

void	forceClear ()
	Erase the table by filling it with nulls. More...

void	reserve (size_t capacity, const typename Updater_t::Context_t &ctx)
	Increase the table capacity. More...

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

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

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

Static Public Attributes
static constexpr uintptr_t	nullval = NULLVAL_
	Null key value. More...

static constexpr uintptr_t	tombstone = TOMBSTONE_
	Tombstone key value. Must be different from nullval to allow erasures. More...

static constexpr size_t	INVALID = static_cast<size_t>(-1)
	Used to represent an invalid table index. More...

Private Member Functions
bool	grow (const Lock_t &lock, const typename Updater_t::Context_t &ctx)
	Make the table larger. More...

bool	grow (const Lock_t &lock, size_t new_capacity, const typename Updater_t::Context_t &ctx)
	Make the table larger. More...

Static Private Member Functions
static uint64_t	round_up (uint64_t)

Private Attributes
Updater_t	m_updater
	Updater object managing memory. See above. More...

const Hasher_t	m_hasher
	The hash object. More...

const Matcher_t	m_matcher
	The key match object. More...

Table *	m_table
	The current table instance. Must be holding the mutex to access this. More...

std::atomic< size_t >	m_size
	Number of entries in the map. More...

std::atomic< size_t >	m_erased
	Number of entries that have been erased. More...

std::mutex	m_mutex
	Mutex to serialize changes to the map. More...

Static Private Attributes
static constexpr size_t	CACHELINE = 64
	Assumed length in bytes of one cache line. More...

static constexpr size_t	ENTRIES_PER_CACHELINE = CACHELINE / sizeof(entry_t)
	Number of entries in one cache line. More...

static constexpr size_t	ENTRIES_PER_CACHELINE_MASK = (ENTRIES_PER_CACHELINE-1)
	Mask for the cache line part of an index. More...

Friends
class	::ConcurrentHashmapImplTest
	For unit testing. More...

Detailed Description

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>
class CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >

Hash table allowing concurrent, lockless reads.

This class implements a simple hash map from uintptr_t to uintptr_t. This class isn't meant to be used directly; rather, a more user-friendly interface can be built on top of this. Although here we deal only with uintptr_t values, the hash and comparison operations are templated. This allows for handling more complex types, where the values stored in the map are pointers to the actual objects. We support inserting new items and modifying existing ones, and, with caveats, deletion. One value of the key must be reserved to indicate null; no keys with that value may be inserted. For deletion, a second distinct (tombstone) value of the key must be reserved to mark deleted entries.

Further caveats for deletion:

Deleted entries continue to occupy space in the table until the next time the table is reallocated.
Care must be taken if the key or value types require memory allocation. Additional functionality may be required here to really support this.
An item may be deleted while there is a valid iterator referencing it. In that case, the key returned by the iterator will change to the tombstone value.

There can be only one writer at a time; this is enforced with internal locks. However, there can be any number of concurrent readers at any time. The reads are lockless. So this is appropriate when reads are much more frequent than writes.

Template arguments: UPDATER_ - Object used for memory management; see below. This has the same requirements as for ConcurrentRangeMap; see there for further details. HASHER_ - Functional to compute a hash value from a key. Defaults to std::hash. MATCHER_ - Functional to compare two keys for equality. Defaults to std::equal_to. NULLVAL_ - Value of the key to be considered null. A key with this value may not be inserted. TOMBSTONE_ - Value of the key used to mark a deleted entry. If identical to NULLVAL_, then deletions are not allowed.

Implementation notes: We use open addressing (see, eg, knuth AOCP 6.4), in which the payloads are kept in the hash table itself. We try to be cache friendly by probing all entries within a cache line before trying anything in a different cache line. If the table gets full, we make a new, larger, instance copying the data from the old one. The old table instances are then given to the Updater object to handle.

The implementation here is inspired by the hash maps from ConcurrencyKit (http://concurrencykit.org), though the code is all new.

nb. Can't use plain ‘MATCHER’ as a template argument because it collides with gtest.

Definition at line 199 of file ConcurrentHashmapImpl.h.

Member Typedef Documentation

◆ const_iterator_range

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

using CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::const_iterator_range = std::pair<const_iterator, const_iterator>

Two iterators defining a range.

Definition at line 584 of file ConcurrentHashmapImpl.h.

◆ Context_t

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

using CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::Context_t = typename Updater_t::Context_t

Context type for the updater.

Definition at line 354 of file ConcurrentHashmapImpl.h.

◆ Hasher_t

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

using CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::Hasher_t = HASHER_

Hash object.

Definition at line 205 of file ConcurrentHashmapImpl.h.

◆ Lock_t

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

using CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::Lock_t = HashmapLock

Lock class used for external locking.

Definition at line 216 of file ConcurrentHashmapImpl.h.

◆ Matcher_t

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

using CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::Matcher_t = MATCHER_

Key match object.

Definition at line 207 of file ConcurrentHashmapImpl.h.

◆ Updater_t

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

using CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::Updater_t = UPDATER_<Table>

Updater object.

Definition at line 352 of file ConcurrentHashmapImpl.h.

◆ val_t

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

using CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::val_t = ConcurrentHashmapVal_t

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

Definition at line 203 of file ConcurrentHashmapImpl.h.

Constructor & Destructor Documentation

◆ ConcurrentHashmapImpl() [1/2]

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::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.

◆ ConcurrentHashmapImpl() [2/2]

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::ConcurrentHashmapImpl ( const ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ > & )

delete

Member Function Documentation

◆ begin()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

const_iterator CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::begin ( ) const

A begin iterator for the container.

◆ capacity()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

size_t CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::capacity ( ) const

Return the current table size.

◆ clear() [1/2]

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

const_iterator CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::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]

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

const_iterator CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::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.

◆ end()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

const_iterator CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::end ( ) const

An end iterator for the container.

◆ erase() [1/2]

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

bool CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::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]

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

bool CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::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()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

size_t CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::erased ( ) const

The number of erased elements in the current table.

◆ forceClear()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

void CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::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()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

const_iterator CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::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]

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

bool CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::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]

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

bool CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::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()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

const Hasher_t& CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::hasher ( ) const

Return the hasher object.

◆ lock()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

Lock_t CxxUtils::detail::ConcurrentHashmapImpl< 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 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()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

const Matcher_t& CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::matcher ( ) const

Return the matcher object.

◆ operator=()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

ConcurrentHashmapImpl& CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::operator= ( const ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ > & )

delete

◆ put() [1/2]

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

std::pair<const_iterator, bool> CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::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]

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

std::pair<const_iterator, bool> CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::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()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

void CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::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()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

const_iterator_range CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::range ( ) const

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

◆ reserve()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

void CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::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()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

static uint64_t CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::round_up ( uint64_t )

staticprivate

◆ size()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

size_t CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::size ( ) const

Return the number of items currently stored.

(not necessarily synced)

◆ swap()

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

void CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::swap ( ConcurrentHashmapImpl< 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<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

Updater_t& CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::updater ( )

Access the Updater instance.

Friends And Related Function Documentation

◆ ::ConcurrentHashmapImplTest

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

friend class ::ConcurrentHashmapImplTest

friend

For unit testing.

Definition at line 241 of file ConcurrentHashmapImpl.h.

Member Data Documentation

◆ CACHELINE

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

constexpr size_t CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::CACHELINE = 64

staticconstexprprivate

Assumed length in bytes of one cache line.

Definition at line 227 of file ConcurrentHashmapImpl.h.

◆ ENTRIES_PER_CACHELINE

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

constexpr size_t CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::ENTRIES_PER_CACHELINE = CACHELINE / sizeof(entry_t)

staticconstexprprivate

Number of entries in one cache line.

Definition at line 236 of file ConcurrentHashmapImpl.h.

◆ ENTRIES_PER_CACHELINE_MASK

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

constexpr size_t CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::ENTRIES_PER_CACHELINE_MASK = (ENTRIES_PER_CACHELINE-1)

staticconstexprprivate

Mask for the cache line part of an index.

Definition at line 238 of file ConcurrentHashmapImpl.h.

◆ INVALID

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

constexpr size_t CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::INVALID = static_cast<size_t>(-1)

staticconstexpr

Used to represent an invalid table index.

Definition at line 213 of file ConcurrentHashmapImpl.h.

◆ m_erased

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

std::atomic<size_t> CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::m_erased

private

Number of entries that have been erased.

Definition at line 709 of file ConcurrentHashmapImpl.h.

◆ m_hasher

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

const Hasher_t CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::m_hasher

private

The hash object.

Definition at line 701 of file ConcurrentHashmapImpl.h.

◆ m_matcher

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

const Matcher_t CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::m_matcher

private

The key match object.

Definition at line 703 of file ConcurrentHashmapImpl.h.

◆ m_mutex

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

std::mutex CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::m_mutex

private

Mutex to serialize changes to the map.

Definition at line 711 of file ConcurrentHashmapImpl.h.

◆ m_size

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

std::atomic<size_t> CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::m_size

private

Number of entries in the map.

Definition at line 707 of file ConcurrentHashmapImpl.h.

◆ m_table

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

Table* CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::m_table

private

The current table instance. Must be holding the mutex to access this.

Definition at line 705 of file ConcurrentHashmapImpl.h.

◆ m_updater

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

Updater_t CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::m_updater

private

Updater object managing memory. See above.

Definition at line 699 of file ConcurrentHashmapImpl.h.

◆ nullval

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

constexpr uintptr_t CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::nullval = NULLVAL_

staticconstexpr

Null key value.

Definition at line 209 of file ConcurrentHashmapImpl.h.

◆ tombstone

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>

constexpr uintptr_t CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::tombstone = TOMBSTONE_

staticconstexpr

Tombstone key value. Must be different from nullval to allow erasures.

Definition at line 211 of file ConcurrentHashmapImpl.h.

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

ConcurrentHashmapImpl.h

Classes

Public Types

Public Member Functions

Static Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Friends

Detailed Description

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_> class CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >

Member Typedef Documentation

◆ const_iterator_range

◆ Context_t

◆ Hasher_t

◆ Lock_t

◆ Matcher_t

◆ Updater_t

◆ val_t

Constructor & Destructor Documentation

◆ ConcurrentHashmapImpl() [1/2]

◆ ConcurrentHashmapImpl() [2/2]

Member Function Documentation

◆ begin()

◆ capacity()

◆ clear() [1/2]

◆ clear() [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()

Friends And Related Function Documentation

◆ ::ConcurrentHashmapImplTest

Member Data Documentation

◆ CACHELINE

◆ ENTRIES_PER_CACHELINE

◆ ENTRIES_PER_CACHELINE_MASK

◆ INVALID

◆ m_erased

◆ m_hasher

◆ m_matcher

◆ m_mutex

◆ m_size

◆ m_table

◆ m_updater

◆ nullval

◆ tombstone

template<template< class > class UPDATER_, typename HASHER_ = std::hash<uintptr_t>, typename MATCHER_ = std::equal_to<uintptr_t>, uintptr_t NULLVAL_ = 0, uintptr_t TOMBSTONE_ = NULLVAL_>
class CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >