#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 ()

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)

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 66 of file HashTable.h.

Constructor & Destructor Documentation

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 142 of file HashTable.h.

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

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

inline

Clear the HashTable.

Definition at line 150 of file HashTable.h.

Referenced by HashTable< String, Filesystem *, HashedStringView >::copyFrom(), and Directory::empty().

Here is the caller graph for this function:

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 165 of file HashTable.h.

Referenced by VFS::aliasExists().

Here is the caller graph for this function:

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 477 of file HashTable.h.

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 443 of file HashTable.h.

Referenced by VFS::removeAllAliases().

Here is the caller graph for this function:

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 238 of file HashTable.h.

Referenced by Directory::getChild().

Here is the caller graph for this function:

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 264 of file HashTable.h.

Referenced by VFS::addAlias(), Directory::addDirectoryEntry(), Directory::addEphemeralFile(), and SymbolTable::insertShared().

Here is the caller graph for this function:

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 200 of file HashTable.h.

Referenced by VFS::addAlias(), Directory::addEphemeralFile(), Directory::lookup(), SymbolTable::lookup(), VFS::lookupFilesystem(), and Directory::remove().

Here is the caller graph for this function:

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 323 of file HashTable.h.

Referenced by Directory::remove(), and VFS::removeAlias().

Here is the caller graph for this function:

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 373 of file HashTable.h.

Referenced by Directory::preallocateDirectoryEntries().

Here is the caller graph for this function:

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 686 of file HashTable.h.

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

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 >

Constructor & Destructor Documentation

Member Function Documentation

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 >