#include <HashTable.h>

Inheritance diagram for HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >:

Collaboration diagram for HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >:

Classes
struct	bucket

Public Types
typedef ::Iterator< V, struct bucket >	Iterator

typedef Iterator::Const	ConstIterator

typedef Result< const V &, HashTableError::Error >	LookupResult

typedef Result< Pair< K, V >, HashTableError::Error >	PairLookupResult

Public Member Functions
	HashTable (const V &customDefault)

void	clear () noexcept

bool	contains (const K &k) const

LookupResult	lookup (const K &k) const

template<typename SK = SiblingK>
pedigree_std::enable_if<!pedigree_std::is_same< K, SK >::value, LookupResult >::type	lookup (const SK &k) const

PairLookupResult	getNth (size_t n) const

bool	insert (const K &k, const V &v)

bool	update (const K &k, const V &v)

void	remove (const K &k)

void	reserve (size_t numItems)

size_t	count () const

Iterator	begin ()

ConstIterator	begin () const

Iterator	end ()

ConstIterator	end () const

Iterator	erase (Iterator &at)

	HashTable (const SelfType &other)=delete

SelfType &	operator= (const SelfType &p)=delete

void	copyFrom (const SelfType &other)

SelfType &	operator= (SelfType &&p) noexcept(noexcept(m_Default=static_cast< V && >(p.m_Default)))

Private Types
typedef HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >	SelfType

Private Member Functions
struct bucket *	getFirstSetBucket () const

void	check ()

void	rehash (size_t oldCount=0)

size_t	nextIndex (size_t i, size_t &index, size_t &step) const

bucket *	findNextEmpty (size_t currentHash)

bucket *	findNextSet (size_t currentHash, const K &k, uint32_t khash=0)

template<class FindK = K>
const bucket *	findNextSet (size_t currentHash, const FindK &k, uint32_t khash=0) const

template<class LookupK >
const struct bucket *	doLookup (const LookupK &k, HashTableError::Error &err) const

void	setDefaults (bool reparentToo=false)

void	resetParents ()

Private Attributes
bucket *	m_Buckets

V	m_Default

size_t	m_nBuckets

size_t	m_nItems

size_t	m_nMask

Detailed Description

template<class K, class V, class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>
class HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >

Hash table class.

Handles hash collisions by chaining keys.

The key type 'K' should have a method hash() which returns a size_t hash that can be used to index into the bucket array.

The key type 'K' should also be able to compare against other 'K' types for equality.

An optional type 'SiblingK' can be provided for a type which can be used as an alternative to type 'K' for lookups. It should be able to hash in the same way as well as being able to compare with 'K' types successfully.

GrowthFactor defines how quickly the bucket count should grow. The default of two balances memory usage against performance, but some use cases would be better served by significant growth in each resize.

Todo:: check InitialBuckets for is a power of two

Definition at line 59 of file HashTable.h.

Member Typedef Documentation

◆ ConstIterator

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

typedef Iterator::Const HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::ConstIterator

Definition at line 106 of file HashTable.h.

◆ Iterator

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

typedef ::Iterator<V, struct bucket> HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::Iterator

Definition at line 105 of file HashTable.h.

◆ LookupResult

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

typedef Result<const V&, HashTableError::Error> HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::LookupResult

Definition at line 108 of file HashTable.h.

◆ PairLookupResult

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

typedef Result<Pair<K, V>, HashTableError::Error> HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::PairLookupResult

Definition at line 109 of file HashTable.h.

◆ SelfType

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

typedef HashTable<K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor> HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::SelfType

private

Definition at line 61 of file HashTable.h.

Constructor & Destructor Documentation

◆ HashTable() [1/3]

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::HashTable ( )

inline

Definition at line 111 of file HashTable.h.

◆ HashTable() [2/3]

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::HashTable ( const V & customDefault )

inline

Constructor with custom default value.

Definition at line 116 of file HashTable.h.

◆ ~HashTable()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::~HashTable ( )

inline

Definition at line 131 of file HashTable.h.

◆ HashTable() [3/3]

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::HashTable ( const SelfType & other )

delete

Note: We allow move assignment but not copy assignment/construction for HashTable. To copy a HashTable, the owner of the table needs to manage this itself - allowing for correct handling of copying elements (e.g. if V is a pointer type) without it happening "behind the scenes".

Member Function Documentation

◆ begin() [1/2]

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

Iterator HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::begin ( )

inline

Definition at line 351 of file HashTable.h.

◆ begin() [2/2]

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

ConstIterator HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::begin ( ) const

inline

Definition at line 355 of file HashTable.h.

◆ check()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

void HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::check ( )

inlineprivate

Definition at line 449 of file HashTable.h.

◆ clear()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

void HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::clear ( )

inlinenoexcept

Clear the HashTable.

Definition at line 123 of file HashTable.h.

Referenced by HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::copyFrom(), and Directory::emptyCache().

Here is the caller graph for this function:

◆ contains()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

bool HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::contains ( const K & k ) const

inline

Check if the given key exists in the hash table.

Definition at line 138 of file HashTable.h.

Referenced by Directory::removeEphemeralFiles().

Here is the caller graph for this function:

◆ copyFrom()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

void HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::copyFrom ( const SelfType & other )

inline

Forceful opt-in to copy values from the other table into this one. This is an explicit call which can be used for data types that are safe to copy, or in cases where callers accept the risk or will handle the lack of safety some other way.

Definition at line 400 of file HashTable.h.

References HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::clear().

◆ count()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

size_t HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::count ( ) const

inline

Definition at line 347 of file HashTable.h.

◆ doLookup()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

template<class LookupK >

const struct bucket * HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::doLookup	(	const LookupK &	k,
		HashTableError::Error &	err
	)		const

inlineprivate

Definition at line 560 of file HashTable.h.

◆ end() [1/2]

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

Iterator HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::end ( )

inline

Definition at line 359 of file HashTable.h.

◆ end() [2/2]

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

ConstIterator HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::end ( ) const

inline

Definition at line 363 of file HashTable.h.

◆ erase()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

Iterator HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::erase ( Iterator & at )

inline

Erase the value at the given iterator position.

Definition at line 370 of file HashTable.h.

References Iterator< originalT, Struct, FunctionPrev, FunctionNext, T >::__getNode().

◆ findNextEmpty()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

bucket * HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::findNextEmpty ( size_t currentHash )

inlineprivate

Definition at line 492 of file HashTable.h.

◆ findNextSet() [1/2]

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

template<class FindK = K>

const bucket * HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::findNextSet	(	size_t	currentHash,
		const FindK &	k,
		uint32_t	khash = `0`
	)		const

inlineprivate

Definition at line 533 of file HashTable.h.

◆ findNextSet() [2/2]

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

bucket * HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::findNextSet	(	size_t	currentHash,
		const K &	k,
		uint32_t	khash = `0`
	)

inlineprivate

Definition at line 506 of file HashTable.h.

◆ getFirstSetBucket()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

struct bucket * HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::getFirstSetBucket ( ) const

inlineprivate

Definition at line 436 of file HashTable.h.

◆ getNth()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

PairLookupResult HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::getNth ( size_t n ) const

inline

Get the nth item in the hash table.

Because the table is unordered, this should only be used to provide an indexed access into the table rather than used to find a specific item. Insertions and removals may completely change the order of the table.

Definition at line 197 of file HashTable.h.

◆ insert()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

bool HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::insert	(	const K &	k,
		const V &	v
	)

inline

Insert the given value with the given key.

Definition at line 218 of file HashTable.h.

References HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::reserve().

Referenced by Directory::addCachedDirectoryEntry(), Directory::reserveDirectoryEntry(), and Directory::reserveRenameEntry().

Here is the caller graph for this function:

◆ lookup() [1/2]

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

LookupResult HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::lookup ( const K & k ) const

inline

Do a lookup of the given key, and return either the value, or NULL if the key is not in the hashtable.

O(1) in the average case, with a hash function that rarely collides.

Definition at line 168 of file HashTable.h.

Referenced by Directory::addCachedDirectoryEntry(), Directory::invalidateDirectoryEntry(), Directory::lookupChildAt(), Directory::remove(), Directory::removeDirectoryEntry(), Directory::removeEphemeralFiles(), Directory::reserveDirectoryEntry(), and Directory::reserveRenameEntry().

Here is the caller graph for this function:

◆ lookup() [2/2]

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

template<typename SK = SiblingK>

pedigree_std::enable_if<!pedigree_std::is_same< K, SK >::value, LookupResult >::type HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::lookup ( const SK & k ) const

inline

Definition at line 179 of file HashTable.h.

◆ nextIndex()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

size_t HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::nextIndex	(	size_t	i,
		size_t &	index,
		size_t &	step
	)		const

inlineprivate

Definition at line 481 of file HashTable.h.

◆ operator=()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

SelfType & HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::operator= ( SelfType && p )

inlinenoexcept

Definition at line 417 of file HashTable.h.

◆ rehash()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

void HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::rehash ( size_t oldCount = 0 )

inlineprivate

Definition at line 458 of file HashTable.h.

◆ remove()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

void HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::remove ( const K & k )

inline

Remove the given key.

Definition at line 271 of file HashTable.h.

Referenced by Directory::invalidateDirectoryEntry(), Directory::remove(), and Directory::removeDirectoryEntry().

Here is the caller graph for this function:

◆ reserve()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

void HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::reserve ( size_t numItems )

inline

Reserve space for the given number of items in the hash table.

Definition at line 312 of file HashTable.h.

References HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::setDefaults().

Referenced by HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::insert(), and Directory::preallocateDirectoryEntries().

Here is the caller graph for this function:

◆ resetParents()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

void HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::resetParents ( )

inlineprivate

Definition at line 601 of file HashTable.h.

◆ setDefaults()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

void HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::setDefaults ( bool reparentToo = false )

inlineprivate

Set default value on all un-set buckets.

Definition at line 587 of file HashTable.h.

Referenced by HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::reserve().

Here is the caller graph for this function:

◆ update()

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

bool HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::update	(	const K &	k,
		const V &	v
	)

inline

Update the value at the given key.

Definition at line 255 of file HashTable.h.

Member Data Documentation

◆ m_Buckets

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

bucket* HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::m_Buckets

private

Definition at line 607 of file HashTable.h.

◆ m_Default

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

V HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::m_Default

private

Definition at line 608 of file HashTable.h.

◆ m_nBuckets

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

size_t HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::m_nBuckets

private

Definition at line 609 of file HashTable.h.

◆ m_nItems

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

size_t HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::m_nItems

private

Definition at line 610 of file HashTable.h.

◆ m_nMask

template<class K , class V , class SiblingK = K, size_t InitialBuckets = 4, bool QuadraticProbe = true, size_t GrowthFactor = 2>

size_t HashTable< K, V, SiblingK, InitialBuckets, QuadraticProbe, GrowthFactor >::m_nMask

private

Definition at line 611 of file HashTable.h.

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

HashTable.h

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ ConstIterator

◆ Iterator

◆ LookupResult

◆ PairLookupResult

◆ SelfType

Constructor & Destructor Documentation

◆ HashTable() [1/3]

◆ HashTable() [2/3]

◆ ~HashTable()

◆ HashTable() [3/3]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ check()

◆ clear()

◆ contains()

◆ copyFrom()

◆ count()

◆ doLookup()

◆ end() [1/2]

◆ end() [2/2]

◆ erase()

◆ findNextEmpty()

◆ findNextSet() [1/2]

◆ findNextSet() [2/2]

◆ getFirstSetBucket()

◆ getNth()

◆ insert()

◆ lookup() [1/2]

◆ lookup() [2/2]

◆ nextIndex()

◆ operator=()

◆ rehash()

◆ remove()

◆ reserve()

◆ resetParents()

◆ setDefaults()

◆ update()

Member Data Documentation

◆ m_Buckets

◆ m_Default

◆ m_nBuckets

◆ m_nItems

◆ m_nMask