CxxUtils::detail::Table Class Reference

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

#include <ConcurrentHashmapImpl.h>

Collaboration diagram for CxxUtils::detail::Table:

Public Types
using	TableIterator = CHMTableIterator<ENTRIES_PER_CACHELINE>

Public Member Functions
	Table (size_t capacity, const Hasher_t &hasher=Hasher_t(), const Matcher_t &matcher=Matcher_t())
	Constructor.
void	operator delete (void *p)
	Deallocator for table objects.
size_t	probeRead (val_t key, size_t hash) const
	Find a table entry for reading.
size_t	probeWrite (val_t key, size_t hash, bool &insert)
	Find a table entry for writing.
size_t	capacity () const
	The number of entries in the table.
const entry_t &	entry (size_t offset) const
	Return the entry for an offset.
entry_t &	entry (size_t offset)
	Return the entry for an offset (non-const).

Static Public Member Functions
static void *	operator new (size_t, size_t capacity)
	Allocator for table objects.

Private Member Functions
*Mask for table	indices (capacity-1). const size_t m_mask

Private Attributes
*Number of entries in the table Must be a power of const size_t	m_capacity
*Maximum number of probes allowed before resizing the table const size_t	m_maxProbe
*Number of bits in the mask const size_t	m_maskBits
*The hash object const Hasher_t &	m_hasher
*The key match object const Matcher_t &	m_matcher
*Longest probe needed so far std::atomic< size_t >	m_longestProbe
*The actual table entries entry_t	m_entries [1]

Detailed Description

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. */ 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 ConcurrentHashmapImpl { public: Type used for keys and values — an unsigned big enough to hold a pointer. using val_t = ConcurrentHashmapVal_t; Hash object. using Hasher_t = HASHER_; Key match object. using Matcher_t = MATCHER_; Null key value. static constexpr uintptr_t nullval = NULLVAL_; Tombstone key value. Must be different from nullval to allow erasures. static constexpr uintptr_t tombstone = TOMBSTONE_; Used to represent an invalid table index. static constexpr size_t INVALID = static_cast<size_t>(-1);

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

private: One entry in the hash table. struct entry_t { std::atomic<val_t> m_key; std::atomic<val_t> m_val; };

Assumed length in bytes of one cache line. static constexpr size_t CACHELINE = 64;

Ensure that entries will evenly pack a cache line. If CACHELINE is a power of two, this implies that sizeof(entry_t) is as well. static_assert (CACHELINE >= sizeof (entry_t) && CACHELINE % sizeof(entry_t) == 0);

Number of entries in one cache line. static constexpr size_t ENTRIES_PER_CACHELINE = CACHELINE / sizeof(entry_t); Mask for the cache line part of an index. static constexpr size_t ENTRIES_PER_CACHELINE_MASK = (ENTRIES_PER_CACHELINE-1);

For unit testing. friend class ::ConcurrentHashmapImplTest;

/**

Table of hash entries.

This is the actual table of hash entries. It consists of a fixed-size header, followed by the actual array of entries. We override new in order to be able to properly allocate the space for the array. The start of the array of entries need to be aligned on a cache line. We make a new instance of this if the table needs to be grown.

Definition at line 253 of file ConcurrentHashmapImpl.h.

Member Typedef Documentation

TableIterator

using CxxUtils::detail::Table::TableIterator = CHMTableIterator<ENTRIES_PER_CACHELINE>

Definition at line 256 of file ConcurrentHashmapImpl.h.

Constructor & Destructor Documentation

Table()

CxxUtils::detail::Table::Table	(	size_t	capacity,
		const Hasher_t &	hasher = Hasher_t(),
		const Matcher_t &	matcher = Matcher_t() )

Constructor.

Parameters

capacity	Number of entries in the table. Must be a power of 2.
hasher	Hash object to use.
matcher	Key match object to use.

Member Function Documentation

capacity()

size_t CxxUtils::detail::Table::capacity

(

)

const

The number of entries in the table.

entry() [1/2]

entry_t & CxxUtils::detail::Table::entry

(

size_t

offset

)

Return the entry for an offset (non-const).

Parameters

offset

The index of the desired entry.

entry() [2/2]

const entry_t & CxxUtils::detail::Table::entry

(

size_t

offset

)

const

Return the entry for an offset.

Parameters

offset

The index of the desired entry.

indices()

*Mask for table CxxUtils::detail::Table::indices ( capacity- 1 ) const

private

operator delete()

void CxxUtils::detail::Table::operator delete

(

void *

p

)

Deallocator for table objects.

operator new()

void * CxxUtils::detail::Table::operator new ( size_t , size_t capacity )

static

Allocator for table objects.

Parameters

capacity

Size of the table (must be a power of 2).

Allocate with enough space for the table of entries. Also align on a cache line.

probeRead()

size_t CxxUtils::detail::Table::probeRead	(	val_t	key,
		size_t	hash ) const

Find a table entry for reading.

Parameters

key	The key for which to search.
hash	The hash of the key.

Returns the matching entry, or nullptr.

probeWrite()

size_t CxxUtils::detail::Table::probeWrite	(	val_t	key,
		size_t	hash,
		bool &	insert )

Find a table entry for writing.

Parameters

key	The key for which to search.
hash	The hash of the key.
entry[out]	The entry found.

If we find the entry, return true with entry pointing at it. If we don't find it, and there's still room in the table, return false with entry pointing at the next empty entry. Otherwise, return false with entry set to nullptr.

Member Data Documentation

m_capacity

* Number of entries in the table Must be a power of const size_t CxxUtils::detail::Table::m_capacity

private

Definition at line 332 of file ConcurrentHashmapImpl.h.

m_entries

* The actual table entries entry_t CxxUtils::detail::Table::m_entries[1]

private

Definition at line 346 of file ConcurrentHashmapImpl.h.

m_hasher

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

private

Definition at line 340 of file ConcurrentHashmapImpl.h.

m_longestProbe

* Longest probe needed so far std::atomic<size_t> CxxUtils::detail::Table::m_longestProbe

private

Definition at line 344 of file ConcurrentHashmapImpl.h.

m_maskBits

* Number of bits in the mask const size_t CxxUtils::detail::Table::m_maskBits

private

Definition at line 338 of file ConcurrentHashmapImpl.h.

m_matcher

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

private

Definition at line 342 of file ConcurrentHashmapImpl.h.

m_maxProbe

* Maximum number of probes allowed before resizing the table const size_t CxxUtils::detail::Table::m_maxProbe

private

Definition at line 334 of file ConcurrentHashmapImpl.h.

---

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

• ConcurrentHashmapImpl.h