Table of hash entries. More...

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

void	operator delete (void *p)
	Deallocator for table objects. More...

size_t	probeRead (val_t key, size_t hash) const
	Find a table entry for reading. More...

size_t	probeWrite (val_t key, size_t hash, bool &insert)
	Find a table entry for writing. More...

size_t	capacity () const
	The number of entries in the table. More...

const entry_t &	entry (size_t offset) const
	Return the entry for an offset. More...

entry_t &	entry (size_t offset)
	Return the entry for an offset (non-const). More...

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

Private Attributes
const size_t	m_capacity
	Number of entries in the table. Must be a power of 2. More...

const size_t	m_maxProbe
	Maximum number of probes allowed before resizing the table. More...

const size_t	m_mask
	Mask for table indices (capacity-1). More...

const size_t	m_maskBits
	Number of bits in the mask. More...

const Hasher_t &	m_hasher
	The hash object. More...

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

std::atomic< size_t >	m_longestProbe
	Longest probe needed so far. More...

entry_t	m_entries [1]
	The actual table entries. 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_ >::Table

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 261 of file ConcurrentHashmapImpl.h.

Member Typedef Documentation

◆ TableIterator

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_ >::Table::TableIterator = CHMTableIterator<ENTRIES_PER_CACHELINE>

Definition at line 264 of file ConcurrentHashmapImpl.h.

Constructor & Destructor Documentation

◆ 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_>

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

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_ >::Table::capacity ( ) const

The number of entries in the table.

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

entry_t& CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::Table::entry ( size_t offset )

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

Parameters

offset The index of the desired entry.

◆ entry() [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 entry_t& CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::Table::entry ( size_t offset ) const

Return the entry for an offset.

Parameters

offset The index of the desired entry.

◆ operator delete()

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_ >::Table::operator delete ( void * p )

Deallocator for table objects.

◆ operator new()

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

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_ >::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()

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_ >::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

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

private

Number of entries in the table. Must be a power of 2.

Definition at line 340 of file ConcurrentHashmapImpl.h.

◆ m_entries

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_>

entry_t CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::Table::m_entries[1]

private

The actual table entries.

Definition at line 354 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_ >::Table::m_hasher

private

The hash object.

Definition at line 348 of file ConcurrentHashmapImpl.h.

◆ m_longestProbe

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_ >::Table::m_longestProbe

private

Longest probe needed so far.

Definition at line 352 of file ConcurrentHashmapImpl.h.

◆ m_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_>

const size_t CxxUtils::detail::ConcurrentHashmapImpl< UPDATER_, HASHER_, MATCHER_, NULLVAL_, TOMBSTONE_ >::Table::m_mask

private

Mask for table indices (capacity-1).

Definition at line 344 of file ConcurrentHashmapImpl.h.

◆ m_maskBits

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

private

Number of bits in the mask.

Definition at line 346 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_ >::Table::m_matcher

private

The key match object.

Definition at line 350 of file ConcurrentHashmapImpl.h.

◆ m_maxProbe

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

private

Maximum number of probes allowed before resizing the table.

Definition at line 342 of file ConcurrentHashmapImpl.h.

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

ConcurrentHashmapImpl.h

Public Types

Public Member Functions

Static Public Member Functions

Private Attributes

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_ >::Table

Member Typedef Documentation

◆ TableIterator

Constructor & Destructor Documentation

◆ Table()

Member Function Documentation

◆ capacity()

◆ entry() [1/2]

◆ entry() [2/2]

◆ operator delete()

◆ operator new()

◆ probeRead()

◆ probeWrite()

Member Data Documentation

◆ m_capacity

◆ m_entries

◆ m_hasher

◆ m_longestProbe

◆ m_mask

◆ m_maskBits

◆ m_matcher

◆ m_maxProbe

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_ >::Table