Key / data pair hash for quick lookup and retrieval. More...

Inheritance diagram for Burger::HashMap< T, U >:

[legend]

Collaboration diagram for Burger::HashMap< T, U >:

[legend]

Classes
class	const_iterator
	STL compatible constant iterator for HashMap. More...
class	Entry
	Key / data pair for HashMap. More...
class	iterator
	STL compatible iterator for HashMap. More...

Public Member Functions
	HashMap (HashProc pHashFunction=SDBMHashFunctor) noexcept
	Default constructor.
	HashMap (HashProc pHashFunction, TestProc pTestProc) noexcept
	Default constructor with hash and equality function declarations.
	HashMap (HashProc pHashFunction, uintptr_t uDefault) noexcept
	Default constructor with a set number of preallocated entries.
	HashMap (const HashMap< T, U > &rHashMap) noexcept
	Copy constructor.
	~HashMap ()
	Destructor.
HashMap< T, U > &	operator= (const HashMap< T, U > &rHashMap) noexcept
	Copy operator.
U &	operator[] (const T &rKey) noexcept
	Index operator.
void	Set (const T &rKey, const U &rValue) noexcept
	Set a key/data pair in the hash.
void	add (const T &rKey, const U &rValue) noexcept
	Add a key/data pair to the hash.
U *	GetData (const T &rKey) noexcept
	Get data by looking it up by a hash key.
const U *	GetData (const T &rKey) const noexcept
	Get data by looking it up by a hash key.
uint_t	GetData (const T &rKey, U *pOutput) const noexcept
	Get a copy of data by looking it up by a hash key.
iterator	begin (void) noexcept
	Set an iterator to the start of the hash.
const_iterator	begin (void) const noexcept
	Set an const_iterator to the start of the hash.
iterator	end (void) noexcept
	Set an iterator to the end of the hash.
const_iterator	end (void) const noexcept
	Set an const_iterator to the end of the hash.
iterator	find (const T &rKey) noexcept
	Set an iterator to a specific entry in the hash.
const_iterator	find (const T &rKey) const noexcept
	Set an iterator to a specific entry in the hash.
void	erase (const iterator &it) noexcept
	Erase a specific entry in the hash indexed by an iterator.
void	erase (const T &rKey) noexcept
	Erase a specific entry in the hash.
Public Member Functions inherited from Burger::HashMapShared
Entry *	GetEntry (uintptr_t uIndex) noexcept
	Return the pointer to an Entry.
const Entry *	GetEntry (uintptr_t uIndex) const noexcept
	Return a constant pointer to an Entry.
void	Clear (void) noexcept
	Purge all allocated data.
void	Resize (uintptr_t uNewSize) noexcept
	Sets a specific capacity to the hash.
void	SetCapacity (uintptr_t uNewSize) noexcept
	Sets a comfortable capacity of the hash.
uintptr_t	GetEntryCount (void) const noexcept
	Returns the number of valid entries in the hash.
uintptr_t	GetSizeMask (void) const noexcept
	Returns the mask used by the hash for rounding.
uint_t	IsEmpty (void) const noexcept
	Returns TRUE if the hash is empty.
uintptr_t	GetEntrySize (void) const noexcept
	Returns the size of each entry in bytes.

Static Private Member Functions
static void	Construct (HashMapShared::Entry *pEntry) noexcept
	Default constructor for an Entry.
static void	Copy (HashMapShared::Entry pEntry, const void pT, const void *pU) noexcept
	Default copy constructor for an Entry.
static void	Invalidate (HashMapShared::Entry *pEntry) noexcept
	Destructor for an Entry.
static uint_t	EqualsTest (const void pA, const void pB) noexcept
	Key comparison function.

Additional Inherited Members
Static Public Attributes inherited from Burger::HashMapShared
static const uintptr_t	INVALID_HASH = UINTPTR_MAX
	Invalid hash value for marking an Entry as uninitialized.
static const uintptr_t	INVALID_INDEX = UINTPTR_MAX
	Error value for invalid indexes.
static const uintptr_t	END_OF_CHAIN = UINTPTR_MAX
	Constant to mark the end of a hash chain.
static const uintptr_t	EMPTY_RECORD = UINTPTR_MAX - 1
	Constant to mark an unused hash record.
Protected Types inherited from Burger::HashMapShared
typedef uintptr_t(*	HashProc) (const void *pData, uintptr_t uDataSize)
	Function prototype for user supplied hash generator.
typedef uint_t(*	TestProc) (const void pA, const void pB)
	Function prototype for testing keys.
typedef void(*	EntryConstructProc) (Entry *pEntry)
	Function prototype for destroying entries.
typedef void(*	EntryCopyProc) (Entry pEntry, const void pT, const void *pU)
	Function prototype for destroying entries.
typedef void(*	EntryInvalidateProc) (Entry *pEntry)
	Function prototype for destroying entries.
Protected Member Functions inherited from Burger::HashMapShared
	HashMapShared (uintptr_t uEntrySize, uintptr_t uFirstSize, uintptr_t uSecondOffset, TestProc pTestFunction, EntryConstructProc pEntryConstructFunction, EntryCopyProc pEntryCopyFunction, EntryInvalidateProc pEntryInvalidationFunction, HashProc pHashFunction=SDBMHashFunctor) noexcept
	Default constructor.
uintptr_t	FindIndex (const void *pKey) const noexcept
	Locate an entry in the hash.
void	CreateBuffer (uintptr_t uCount, uintptr_t uEntrySize) noexcept
	Create a buffer to store all of the data entries.
void	CreateHashBuffer (uintptr_t uNewSize) noexcept
	Function to change the size of the buffer.
void	Erase (uintptr_t uIndex) noexcept
	Erase a specific hash entry.
void	Erase (const void *pKey) noexcept
	Erase a hash entry by searching for it.
uintptr_t	FindFirst (void) const noexcept
	Find the index for the first valid entry.
uintptr_t	ComputeHash (const void *pKey) const noexcept
	Calculate the hash for a key.
void	Copy (const HashMapShared *pInput) noexcept
	Replace the contents of this hash with a copy of another.
void	Add (const void pT, const void pU) noexcept
	Add a new key data pair into the hash.
const void *	GetData (const void *pT) const noexcept
	Get the pointer to the data index by a key.
Protected Attributes inherited from Burger::HashMapShared
void *	m_pEntries
	Pointer to the hash table Burger::allocate_memory(m_uEntrySize*(m_uSizeMask+1))
uintptr_t	m_uEntrySize
	Size in bytes of each entry in the table.
uintptr_t	m_uFirstSize
	Size of the key in bytes.
uintptr_t	m_uSecondOffset
	Offset in bytes to the start of the data chunk.
uintptr_t	m_uEntryCount
	Number of valid entries in the hash.
uintptr_t	m_uSizeMask
	(Power of 2)-1 size mask used for masking indexes for instant table rounding
HashProc	m_pHashFunction
	Pointer to the hash function.
TestProc	m_pTestFunction
	Pointer to the equality test function.
EntryConstructProc	m_pEntryConstructFunction
	Pointer to function to construct Entry data.
EntryCopyProc	m_pEntryCopyFunction
	Pointer to function to copy construct Entry data.
EntryInvalidateProc	m_pEntryInvalidationFunction
	Pointer to function to destroy data in an Entry.

Detailed Description

template<class T, class U>
class Burger::HashMap< T, U >

Key / data pair hash for quick lookup and retrieval.

HashMap is a template class to quickly look up data chunks using a key value. To cut down on compile time and reduce code bloat, a majority of the runtime it contained in a parent class HashMapShared and the template creates a front end with only the minimum amount of code to support the class.

From a users point of view, HashMap is a 100% template based class, from a code point of view, HashMap is a dispatcher to HashMapShared.

See also: HashMapShared

Constructor & Destructor Documentation

◆ HashMap() [1/4]

template<class T, class U>

Burger::HashMap< T, U >::HashMap ( HashProc pHashFunction = SDBMHashFunctor )

inlinenoexcept

Default constructor.

Create an empty hash and select a hash algorithm.

Parameters

pHashFunction Pointer to a hash function

See also: HashMap(HashProc,uintptr_t) or HashMap(const HashMap &)

◆ HashMap() [2/4]

template<class T, class U>

Burger::HashMap< T, U >::HashMap	(	HashProc	pHashFunction,
		TestProc	pTestProc )

inlinenoexcept

Default constructor with hash and equality function declarations.

Create an empty hash and select a hash algorithm and an Entry test function.

Parameters

pHashFunction	Pointer to a hash function
pTestProc	Pointer to an Entry equality test

See also: HashMap(HashProc,uintptr_t) or HashMap(const HashMap &)

◆ HashMap() [3/4]

template<class T, class U>

Burger::HashMap< T, U >::HashMap	(	HashProc	pHashFunction,
		uintptr_t	uDefault )

inlinenoexcept

Default constructor with a set number of preallocated entries.

Construct the hash with a minimum number of entries so they don't need to be allocated as data is inserted into the hash during runtime.

Parameters

pHashFunction	Pointer to a hash function
uDefault	Number of entries to allocate (Will be rounded up to a power of 2)

See also: HashMap(HashProc) or HashMap(const HashMap &)

◆ HashMap() [4/4]

template<class T, class U>

Burger::HashMap< T, U >::HashMap ( const HashMap< T, U > & rHashMap )

inlinenoexcept

Copy constructor.

Make a copy of a hash.

Parameters

rHashMap Reference to a hash to copy

See also: HashMap(HashProc) or HashMap(HashProc,uintptr_t)

◆ ~HashMap()

template<class T, class U>

Burger::HashMap< T, U >::~HashMap ( )

inline

Destructor.

Dispose of all data in the hash

See also: Clear(), HashMap(HashProc), HashMap(HashProc,uintptr_t) or HashMap(const HashMap &)

Member Function Documentation

◆ add()

template<class T, class U>

void Burger::HashMap< T, U >::add	(	const T &	rKey,
		const U &	rValue )

inlinenoexcept

Add a key/data pair to the hash.

Using a key / data pair, add the entry into the hash. This function is a helper, it will fail if the key was already present in the hash.

Parameters

rKey	Reference to the key to look up
rValue	Reference to the data to copy

See also: Set(const T&,const U&)

◆ begin() [1/2]

template<class T, class U>

const_iterator Burger::HashMap< T, U >::begin ( void ) const

inlinenoexcept

Set an const_iterator to the start of the hash.

Return an STL compatible const_iterator pointing to the first entry in the hash table. The const_iterator can be set to end() const if there is no data in the hash.

Returns: const_iterator preset to the beginning of the hash

See also: end(void) const

◆ begin() [2/2]

template<class T, class U>

iterator Burger::HashMap< T, U >::begin ( void )

inlinenoexcept

Set an iterator to the start of the hash.

Return an STL compatible iterator pointing to the first entry in the hash table. The iterator can be set to end() if there is no data in the hash.

Returns: iterator preset to the beginning of the hash

See also: end(void)

◆ Construct()

template<class T, class U>

void Burger::HashMap< T, U >::Construct ( HashMapShared::Entry * pEntry )

inlinestaticprivatenoexcept

Default constructor for an Entry.

Callback function to default initialize the template Entry structure

Parameters

pEntry Pointer to an uninitialized Entry record

See also: EntryConstructProc, Copy(HashMapShared::Entry *,const void *,const void ) or Invalidate(HashMapShared::Entry *)

◆ Copy()

template<class T, class U>

void Burger::HashMap< T, U >::Copy	(	HashMapShared::Entry *	pEntry,
		const void *	pT,
		const void *	pU )

inlinestaticprivatenoexcept

Default copy constructor for an Entry.

Callback function to copy construct an uninitialized template Entry structure

Parameters

pEntry	Pointer to an uninitialized Entry record
pT	Pointer to a key record to copy
pU	Pointer to a data record to copy

See also: EntryCopyProc, Construct(HashMapShared::Entry *) or Invalidate(HashMapShared::Entry *)

◆ end() [1/2]

template<class T, class U>

const_iterator Burger::HashMap< T, U >::end ( void ) const

inlinenoexcept

Set an const_iterator to the end of the hash.

Return an STL compatible const_iterator pointing to the first entry in the hash table. This is the value to test to determine if the end of the iterations has been reached.

Returns: const_iterator preset to the terminator of the hash

See also: begin(void) const

◆ end() [2/2]

template<class T, class U>

iterator Burger::HashMap< T, U >::end ( void )

inlinenoexcept

Set an iterator to the end of the hash.

Return an STL compatible iterator pointing to the terminating entry in the hash table. This is the value to test to determine if the end of the iterations has been reached.

Returns: iterator preset to the terminator of the hash

See also: begin(void)

◆ EqualsTest()

template<class T, class U>

uint_t Burger::HashMap< T, U >::EqualsTest	(	const void *	pA,
		const void *	pB )

inlinestaticprivatenoexcept

Key comparison function.

Callback function to test two keys and return TRUE if equal.

Parameters

pA	Pointer to the first key to test
pB	Pointer to the second key to test

See also: TestProc

◆ erase() [1/2]

template<class T, class U>

void Burger::HashMap< T, U >::erase ( const iterator & it )

inlinenoexcept

Erase a specific entry in the hash indexed by an iterator.

Using an iterator to look up an entry in the hash, delete the entry.

Parameters

it	Reference to the iterator pointing to the entry to delete

See also: erase(const T&)

◆ erase() [2/2]

template<class T, class U>

void Burger::HashMap< T, U >::erase ( const T & rKey )

inlinenoexcept

Erase a specific entry in the hash.

Using a key to look up an entry in the hash, if it's found, delete it.

Parameters

rKey	Reference to the key to look up

See also: erase(const iterator &it)

◆ find() [1/2]

template<class T, class U>

const_iterator Burger::HashMap< T, U >::find ( const T & rKey ) const

inlinenoexcept

Set an iterator to a specific entry in the hash.

Return an STL compatible const_iterator pointing to the requested entry in the hash table or end() const in case the entry was not found.

Parameters

rKey	Reference to the key to look up

Returns: const_iterator preset to the terminator of the hash or the requested entry

See also: find(const T&rKey)

◆ find() [2/2]

template<class T, class U>

iterator Burger::HashMap< T, U >::find ( const T & rKey )

inlinenoexcept

Set an iterator to a specific entry in the hash.

Return an STL compatible iterator pointing to the requested entry in the hash table or end() in case the entry was not found.

Parameters

rKey	Reference to the key to look up

Returns: iterator preset to the terminator of the hash or the requested entry

See also: find(const T&rKey) const

◆ GetData() [1/3]

template<class T, class U>

const U * Burger::HashMap< T, U >::GetData ( const T & rKey ) const

inlinenoexcept

Get data by looking it up by a hash key.

Scan the hash for data indexed by the key. If found, return a pointer to the data or NULL if the data wasn't found.

Parameters

rKey	Reference to the key to look up

Returns: NULL if the key wasn't in the hash or a valid pointer to the data if so.

See also: GetData(const T &,U *) const

◆ GetData() [2/3]

template<class T, class U>

U * Burger::HashMap< T, U >::GetData ( const T & rKey )

inlinenoexcept

Get data by looking it up by a hash key.

Scan the hash for data indexed by the key. If found, return a pointer to the data or NULL if the data wasn't found.

Parameters

rKey	Reference to the key to look up

Returns: NULL if the key wasn't in the hash or a valid pointer to the data if so.

See also: GetData(const T &,U *) const

◆ GetData() [3/3]

template<class T, class U>

uint_t Burger::HashMap< T, U >::GetData	(	const T &	rKey,
		U *	pOutput ) const

inlinenoexcept

Get a copy of data by looking it up by a hash key.

Scan the hash for data indexed by the key. If found, copy the data and return TRUE. Return FALSE on failure.

Parameters

rKey	Reference to the key to look up
pOutput	Pointer to a buffer to receive a copy of the data

Returns: TRUE if the data was found, FALSE if not.

See also: GetData(const T &) const

◆ Invalidate()

template<class T, class U>

void Burger::HashMap< T, U >::Invalidate ( HashMapShared::Entry * pEntry )

inlinestaticprivatenoexcept

Destructor for an Entry.

Callback function to destroy an initialized template Entry structure

Parameters

pEntry Pointer to an initialized Entry record

See also: EntryInvalidateProc, Copy(HashMapShared::Entry *,const void *,const void ) or Construct(HashMapShared::Entry *)

◆ operator=()

template<class T, class U>

HashMap< T, U > & Burger::HashMap< T, U >::operator= ( const HashMap< T, U > & rHashMap )

inlinenoexcept

Copy operator.

Delete all of the data and make a copy of another hash and place it in this class.

Parameters

rHashMap Reference to a hash to copy

Returns: *this

See also: HashMap(const HashMap &rHashMap)

◆ operator[]()

template<class T, class U>

U & Burger::HashMap< T, U >::operator[] ( const T & rKey )

inlinenoexcept

Index operator.

Using a key, look up the item in the hash and if present, return a reference to the data. If the entry didn't exist, create it with a default constructor for the data.

Parameters

rKey	Reference to the key to look up

Returns: Reference to the data found or created.

See also: GetData(const T&)const or GetData(const T&,U*) const

◆ Set()

template<class T, class U>

void Burger::HashMap< T, U >::Set	(	const T &	rKey,
		const U &	rValue )

inlinenoexcept

Set a key/data pair in the hash.

Using a key, look up the item in the hash and if present, replace the data with the a copy of the data passed. If the entry didn't exist, create it with a copy of the passed data.

Parameters

rKey	Reference to the key to look up
rValue	Reference to the data to copy

See also: GetData(const T&)const or GetData(const T&,U*) const

Classes

Public Member Functions

Static Private Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ HashMap() [1/4]

◆ HashMap() [2/4]

◆ HashMap() [3/4]

◆ HashMap() [4/4]

◆ ~HashMap()

Member Function Documentation

◆ add()

◆ begin() [1/2]

◆ begin() [2/2]

◆ Construct()

◆ Copy()

◆ end() [1/2]

◆ end() [2/2]

◆ EqualsTest()

◆ erase() [1/2]

◆ erase() [2/2]

◆ find() [1/2]

◆ find() [2/2]

◆ GetData() [1/3]

◆ GetData() [2/3]

◆ GetData() [3/3]

◆ Invalidate()

◆ operator=()

◆ operator[]()

◆ Set()