Inheritance diagram for Burger::HashMapShared:

[legend]

Collaboration diagram for Burger::HashMapShared:

Classes
class	const_iterator
	STL compatible iterator base class. More...

class	Entry
	Base data entry for HashMap. More...

Public Member Functions
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 Public Attributes
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
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
	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
void *	m_pEntries
	Pointer to the hash table Burger::Alloc(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

Base class for HashMap.

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 this class 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.

Note: This class is not intended to be directly used, it's intended to be derived to allow its functionality to be shared with different HashMap template types

See also: HashMap

Member Typedef Documentation

◆ EntryConstructProc

typedef void( * Burger::HashMapShared::EntryConstructProc) (Entry *pEntry)

protected

Function prototype for destroying entries.

◆ EntryCopyProc

typedef void( * Burger::HashMapShared::EntryCopyProc) (Entry *pEntry, const void *pT, const void *pU)

protected

Function prototype for destroying entries.

◆ EntryInvalidateProc

typedef void( * Burger::HashMapShared::EntryInvalidateProc) (Entry *pEntry)

protected

Function prototype for destroying entries.

◆ HashProc

typedef uintptr_t( * Burger::HashMapShared::HashProc) (const void *pData, uintptr_t uDataSize)

protected

Function prototype for user supplied hash generator.

◆ TestProc

typedef uint_t( * Burger::HashMapShared::TestProc) (const void *pA, const void *pB)

protected

Function prototype for testing keys.

Constructor & Destructor Documentation

◆ HashMapShared()

Burger::HashMapShared::HashMapShared	(	uintptr_t	uEntrySize,
		uintptr_t	uFirstSize,
		uintptr_t	uSecondOffset,
		TestProc	pTestFunction,
		EntryConstructProc	pEntryConstructFunction,
		EntryCopyProc	pEntryCopyFunction,
		EntryInvalidateProc	pEntryInvalidationFunction,
		HashProc	pHashFunction = SDBMHashFunctor )

inlineprotectednoexcept

Default constructor.

A HashMapShared needs values to properly support the derived class, notably the byte size of each data entry and a function to perform the hash calculation. This constructor is called by derived classes, it's not meant to be used by an application.

Parameters

uEntrySize	Size of each Entry in bytes
uFirstSize	Size in bytes for the key class, usually sizeof(T)
uSecondOffset	Offset in bytes for the data value in Entry
pTestFunction	Function that returns TRUE if the keys match
pEntryConstructFunction	Function that invokes the default constructors for the Entry
pEntryCopyFunction	Function that invokes the copy constructors for the Entry
pEntryInvalidationFunction	Function that invokes the destructors for the Entry
pHashFunction	Function that hashes the key value

See also: HashMap

Member Function Documentation

◆ Add()

void BURGER_API Burger::HashMapShared::Add	(	const void *	pT,
		const void *	pU )

protectednoexcept

Add a new key data pair into the hash.

Expand the size of the hash if needed, and then insert a new key data pair into the hash. This function should now be called if a key should be replaced if present. Use the HashMap::Set() function for that.

Parameters

pT	Pointer to the key to add
pU	Pointer to the data to add

See also: HashMap::Set()

◆ Clear()

void BURGER_API Burger::HashMapShared::Clear ( void )

noexcept

Purge all allocated data.

Iterate over all of the initialized entries and destroy any entry that has valid data using a function that will handle the derived class disposal.

If the invalidation function is NULL, the main buffer is discarded immediately.

See also: CreateBuffer(uintptr_t,uintptr_t)

◆ ComputeHash()

uintptr_t BURGER_API Burger::HashMapShared::ComputeHash ( const void * pKey ) const

protectednoexcept

Calculate the hash for a key.

Given a pointer to a key and the length in bytes of the key, call the hash algorithm using the stored function pointer. If it the very rare case that a hash matches INVALID_HASH, it will be changed to INVALID_HASH -0x8000 to "validate" the hash.

Parameters

pKey	Pointer to the key value

Returns: A valid hash value for the key

See also: HashProc

◆ Copy()

void BURGER_API Burger::HashMapShared::Copy ( const HashMapShared * pInput )

protectednoexcept

Replace the contents of this hash with a copy of another.

Clear out all the data in this hash and copy the entries from another hash into this one.

Parameters

pInput Pointer to the HashMap to copy data from

See also: Clear() and EntryInvalidateProc

◆ CreateBuffer()

void BURGER_API Burger::HashMapShared::CreateBuffer	(	uintptr_t	uCount,
		uintptr_t	uEntrySize )

protectednoexcept

Create a buffer to store all of the data entries.

This helper function assumes that there is no data already allocated by the HashMapShared class. It will allocate a buffer and then mark each entry as empty and initialize all of the internal variables.

Parameters

uCount	Number of entries to allocate (Must be a power of 2)
uEntrySize	Size in bytes of each Entry record

See also: Clear(void)

◆ CreateHashBuffer()

void BURGER_API Burger::HashMapShared::CreateHashBuffer ( uintptr_t uNewSize )

protectednoexcept

Function to change the size of the buffer.

Dynamically resize the buffer and retain all data within by reentering every entry into the newly resized hash table

If uNewSize is zero, delete all data in the hash

Note: If the data buffer is already a comparable size, no action will be performed.

Parameters

uNewSize Number of entries to allocate (Will be rounded up to a power of 2)

See also: CreateBuffer(uintptr_t,uintptr_t) or Clear(void)

◆ Erase() [1/2]

void BURGER_API Burger::HashMapShared::Erase ( const void * pKey )

protectednoexcept

Erase a hash entry by searching for it.

Search the hash for a key and dispose of the Entry if one is found.

Parameters

pKey	Pointer to the key value

See also: Erase(uintptr_t)

◆ Erase() [2/2]

void BURGER_API Burger::HashMapShared::Erase ( uintptr_t uIndex )

protectednoexcept

Erase a specific hash entry.

Assuming a data entry is initialized, this function will remove it from the linked list and call the invalidation function.

If the entry being erased is part of a linked list chain, it will be destroyed, but the linked list will be retained. This is to allow iterators to continue to function without error.

Parameters

uIndex Index into the hash for the entry to erase.

See also: Erase(const void *)

◆ FindFirst()

uintptr_t BURGER_API Burger::HashMapShared::FindFirst ( void ) const

protectednoexcept

Find the index for the first valid entry.

Iterate over the hash data and find the index to the first entry that contains valid data. This is used by HashMap::begin() and HashMap::begin() const

Returns: Index to the first valid entry or INVALID_INDEX if no entries are valid.

See also: FindIndex(const void *) const

◆ FindIndex()

uintptr_t BURGER_API Burger::HashMapShared::FindIndex ( const void * pKey ) const

protectednoexcept

Locate an entry in the hash.

Hash the key and use the hash to look up the data in the entry table. If found, an entry index is returned. If not, INVALID_INDEX is returned.

Parameters

pKey	Pointer to the key value

Returns: A valid index or INVALID_INDEX if not found.

See also: FindFirst(void) const or ComputeHash(const void*) const

◆ GetData()

const void * Burger::HashMapShared::GetData ( const void * pT ) const

protectednoexcept

Get the pointer to the data index by a key.

Given a pointer to a key, scan for it using FindIndex(const void *) and if found, return the pointer to the data pointed by the Entry pointer added with m_uSecondOffset.

Parameters

pT	Pointer to the key look for

Returns: NULL if the record wasn't found or a pointer to the data attached to the key.

See also: HashMap::GetData(const T&) const

◆ GetEntry() [1/2]

const Burger::HashMapShared::Entry * Burger::HashMapShared::GetEntry ( uintptr_t uIndex ) const

inlinenoexcept

Return a constant pointer to an Entry.

Since the Entry class is of a runtime decided size, this function manually performs the indexing into the array.

Parameters

uIndex Valid index into the array.

Returns: Constant pointer to a specific Entry into the array.

See also: GetEntry(uintptr_t)

◆ GetEntry() [2/2]

Burger::HashMapShared::Entry * Burger::HashMapShared::GetEntry ( uintptr_t uIndex )

inlinenoexcept

Return the pointer to an Entry.

Since the Entry class is of a runtime decided size, this function manually performs the indexing into the array.

Parameters

uIndex Valid index into the array.

Returns: Pointer to a specific Entry into the array.

See also: GetEntry(uintptr_t) const

◆ GetEntryCount()

uintptr_t Burger::HashMapShared::GetEntryCount ( void ) const

inlinenoexcept

Returns the number of valid entries in the hash.

Returns: The number of valid entries in the hash.

See also: IsEmpty(void) const or GetSizeMask(void) const

◆ GetEntrySize()

uint_t Burger::HashMapShared::GetEntrySize ( void ) const

inlinenoexcept

Returns the size of each entry in bytes.

Returns: The number of bytes each Entry occupies in the hash array.

See also: GetEntryCount(void) const or GetSizeMask(void) const

◆ GetSizeMask()

uintptr_t Burger::HashMapShared::GetSizeMask ( void ) const

inlinenoexcept

Returns the mask used by the hash for rounding.

When the hash buffer is created, it's set to a size that's a power of two and that value is stored as (size-1) to use as a wrap around mask. To get the hash size, take this value and add one to it.

HashMap<int,int> foo;
DoStuffToAddEntriesToTheHash(&foo);
printf("Maximum entries in the hash %u\n",foo.GetSizeMask()+1);

Returns: Zero if hash hasn't been used, or the entry count - 1

See also: GetEntryCount(void) const or IsEmpty(void) const

◆ IsEmpty()

uint_t Burger::HashMapShared::IsEmpty ( void ) const

inlinenoexcept

Returns TRUE if the hash is empty.

Returns: TRUE if the hash is empty, FALSE if not

See also: GetEntryCount(void) const or GetSizeMask(void) const

◆ Resize()

void BURGER_API Burger::HashMapShared::Resize ( uintptr_t uNewSize )

noexcept

Sets a specific capacity to the hash.

A non-destructive function to resize the hash to a specific size.

Parameters

uNewSize Number of entries for the new hash buffer

See also: SetCapacity(uintptr_t)

◆ SetCapacity()

void BURGER_API Burger::HashMapShared::SetCapacity ( uintptr_t uNewSize )

noexcept

Sets a comfortable capacity of the hash.

A non-destructive function to resize the hash to a size that has padding for new entries to be added with minimal memory allocations.

Parameters

uNewSize Minimum number of entries to size the cache

See also: Resize(uintptr_t)

Member Data Documentation

◆ EMPTY_RECORD

const uintptr_t Burger::HashMapShared::EMPTY_RECORD = UINTPTR_MAX - 1

static

Constant to mark an unused hash record.

◆ END_OF_CHAIN

const uintptr_t Burger::HashMapShared::END_OF_CHAIN = UINTPTR_MAX

static

Constant to mark the end of a hash chain.

◆ INVALID_HASH

const uintptr_t Burger::HashMapShared::INVALID_HASH = UINTPTR_MAX

static

Invalid hash value for marking an Entry as uninitialized.

◆ INVALID_INDEX

const uintptr_t Burger::HashMapShared::INVALID_INDEX = UINTPTR_MAX

static

Error value for invalid indexes.

◆ m_pEntries

void* Burger::HashMapShared::m_pEntries

protected

Pointer to the hash table Burger::Alloc(m_uEntrySize*(m_uSizeMask+1))

◆ m_pEntryConstructFunction

EntryConstructProc Burger::HashMapShared::m_pEntryConstructFunction

protected

Pointer to function to construct Entry data.

◆ m_pEntryCopyFunction

EntryCopyProc Burger::HashMapShared::m_pEntryCopyFunction

protected

Pointer to function to copy construct Entry data.

◆ m_pEntryInvalidationFunction

EntryInvalidateProc Burger::HashMapShared::m_pEntryInvalidationFunction

protected

Pointer to function to destroy data in an Entry.

◆ m_pHashFunction

HashProc Burger::HashMapShared::m_pHashFunction

protected

Pointer to the hash function.

◆ m_pTestFunction

TestProc Burger::HashMapShared::m_pTestFunction

protected

Pointer to the equality test function.

◆ m_uEntryCount

uintptr_t Burger::HashMapShared::m_uEntryCount

protected

Number of valid entries in the hash.

◆ m_uEntrySize

uintptr_t Burger::HashMapShared::m_uEntrySize

protected

Size in bytes of each entry in the table.

◆ m_uFirstSize

uintptr_t Burger::HashMapShared::m_uFirstSize

protected

Size of the key in bytes.

◆ m_uSecondOffset

uintptr_t Burger::HashMapShared::m_uSecondOffset

protected

Offset in bytes to the start of the data chunk.

◆ m_uSizeMask

uintptr_t Burger::HashMapShared::m_uSizeMask

protected

(Power of 2)-1 size mask used for masking indexes for instant table rounding

Classes

Public Member Functions

Static Public Attributes

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ EntryConstructProc

◆ EntryCopyProc

◆ EntryInvalidateProc

◆ HashProc

◆ TestProc

Constructor & Destructor Documentation

◆ HashMapShared()

Member Function Documentation

◆ Add()

◆ Clear()

◆ ComputeHash()

◆ Copy()

◆ CreateBuffer()

◆ CreateHashBuffer()

◆ Erase() [1/2]

◆ Erase() [2/2]

◆ FindFirst()

◆ FindIndex()

◆ GetData()

◆ GetEntry() [1/2]

◆ GetEntry() [2/2]

◆ GetEntryCount()

◆ GetEntrySize()

◆ GetSizeMask()

◆ IsEmpty()

◆ Resize()

◆ SetCapacity()

Member Data Documentation

◆ EMPTY_RECORD

◆ END_OF_CHAIN

◆ INVALID_HASH

◆ INVALID_INDEX

◆ m_pEntries

◆ m_pEntryConstructFunction

◆ m_pEntryCopyFunction

◆ m_pEntryInvalidationFunction

◆ m_pHashFunction

◆ m_pTestFunction

◆ m_uEntryCount

◆ m_uEntrySize

◆ m_uFirstSize

◆ m_uSecondOffset

◆ m_uSizeMask