CxxUtils::detail::CHMTableIterator< ENTRIES_PER_CACHELINE > Struct Template Reference

Helper to generate hash probes. More...

#include <ConcurrentHashmapImpl.h>

Collaboration diagram for CxxUtils::detail::CHMTableIterator< ENTRIES_PER_CACHELINE >:

Public Member Functions
	CHMTableIterator (size_t hash, size_t mask, size_t maskBits, size_t probeLimit)
	Constructor. More...
size_t	offset () const
	Offset of the element currently being probed. More...
size_t	nprobes () const
	Return the number of probes performed so far. More...
bool	next ()
	Move to the next probe. More...

Static Public Attributes
static constexpr size_t	ENTRIES_PER_CACHELINE_MASK = ENTRIES_PER_CACHELINE-1
	Mask for the within-cacheline part of indices. More...

Private Attributes
const size_t	m_mask
	Mask for the table; i.e., capacity-1, but with the low bits corresponding to ENTRIES_PER_CACHELINE also masked off. More...
const size_t	m_boffs
	Offset of the first entry we probe within its cacheline. More...
const size_t	m_stride
	Base increment between probes. More...
const size_t	m_probeLimit
	Maximum number of probes to try. More...
size_t	m_bucket
	Index of the start of the cacheline currently being probed. More...
size_t	m_nprobes
	Number of probes tried so far. More...

Detailed Description

template<unsigned ENTRIES_PER_CACHELINE>
struct CxxUtils::detail::CHMTableIterator< ENTRIES_PER_CACHELINE >

Helper to generate hash probes.

To search for an entry with hash code hash in the table pointed at by entries:

CHMTableIterator<ENTRIES_PER_CACHELINE> it (hash, mask, maskBits, probeLimit);
do {
  entry_t* ent = entries + it.offset();
  <<test if ent is the desired entry and handle if so>>
} while (it.next());
// Too many probes --- failed.

The template argument is the number of table entries per cache line. We try to be cache friendly by first searching all entries in a cache line, then moving to another line.

Definition at line 92 of file ConcurrentHashmapImpl.h.

Constructor & Destructor Documentation

CHMTableIterator()

template<unsigned ENTRIES_PER_CACHELINE>

CxxUtils::detail::CHMTableIterator< ENTRIES_PER_CACHELINE >::CHMTableIterator	(	size_t	hash,
		size_t	mask,
		size_t	maskBits,
		size_t	probeLimit
	)

Constructor.

Parameters

hash	The hash of the entry we're looking for.
mask	Table mask; i.e., the table capacity - 1.
maskBits	Number of 1 bits in mask.
probeLimit	Maximum number of probes to try before failing.

Member Function Documentation

next()

template<unsigned ENTRIES_PER_CACHELINE>

bool CxxUtils::detail::CHMTableIterator< ENTRIES_PER_CACHELINE >::next

(

)

Move to the next probe.

Returns true if we should continue, or false if we've hit the maximum number of probes.

nprobes()

template<unsigned ENTRIES_PER_CACHELINE>

size_t CxxUtils::detail::CHMTableIterator< ENTRIES_PER_CACHELINE >::nprobes

(

)

const

Return the number of probes performed so far.

offset()

template<unsigned ENTRIES_PER_CACHELINE>

size_t CxxUtils::detail::CHMTableIterator< ENTRIES_PER_CACHELINE >::offset

(

)

const

Offset of the element currently being probed.

Member Data Documentation

ENTRIES_PER_CACHELINE_MASK

template<unsigned ENTRIES_PER_CACHELINE>

constexpr size_t CxxUtils::detail::CHMTableIterator< ENTRIES_PER_CACHELINE >::ENTRIES_PER_CACHELINE_MASK = ENTRIES_PER_CACHELINE-1

staticconstexpr

Mask for the within-cacheline part of indices.

Definition at line 95 of file ConcurrentHashmapImpl.h.

m_boffs

template<unsigned ENTRIES_PER_CACHELINE>

const size_t CxxUtils::detail::CHMTableIterator< ENTRIES_PER_CACHELINE >::m_boffs

private

Offset of the first entry we probe within its cacheline.

Definition at line 132 of file ConcurrentHashmapImpl.h.

m_bucket

template<unsigned ENTRIES_PER_CACHELINE>

size_t CxxUtils::detail::CHMTableIterator< ENTRIES_PER_CACHELINE >::m_bucket

private

Index of the start of the cacheline currently being probed.

Definition at line 138 of file ConcurrentHashmapImpl.h.

m_mask

template<unsigned ENTRIES_PER_CACHELINE>

const size_t CxxUtils::detail::CHMTableIterator< ENTRIES_PER_CACHELINE >::m_mask

private

Mask for the table; i.e., capacity-1, but with the low bits corresponding to ENTRIES_PER_CACHELINE also masked off.

Definition at line 130 of file ConcurrentHashmapImpl.h.

m_nprobes

template<unsigned ENTRIES_PER_CACHELINE>

size_t CxxUtils::detail::CHMTableIterator< ENTRIES_PER_CACHELINE >::m_nprobes

private

Number of probes tried so far.

Definition at line 140 of file ConcurrentHashmapImpl.h.

m_probeLimit

template<unsigned ENTRIES_PER_CACHELINE>

const size_t CxxUtils::detail::CHMTableIterator< ENTRIES_PER_CACHELINE >::m_probeLimit

private

Maximum number of probes to try.

Definition at line 136 of file ConcurrentHashmapImpl.h.

m_stride

template<unsigned ENTRIES_PER_CACHELINE>

const size_t CxxUtils::detail::CHMTableIterator< ENTRIES_PER_CACHELINE >::m_stride

private

Base increment between probes.

Definition at line 134 of file ConcurrentHashmapImpl.h.

---

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

• ConcurrentHashmapImpl.h