Implemented with an open-addressing hash table that does not support remove. More...

Classes
class	ConstIterator

class	Iterator

class	IteratorBase
	C++ STL style iterator variable. More...

Public Member Functions
	FastPODTable (int expectedSize=16)

virtual	~FastPODTable ()

ConstIterator	begin () const

Iterator	begin ()

void	clear (int newExpectedSize=-1)
	Removes all elements and shrinks table to its initial size. More...

void	clearAndSetMemoryManager (shared_ptr< MemoryManager > memoryManager)

bool	containsKey (const Key &key) const

void	debugCheckStatus () const
	Asserts that the table is well-conditioned for performance. More...

void	debugPrintStatus () const

void	fastClear ()
	Leaves slot memory allocated but removes the contents. More...

Value &	getCreate (const Key &key)
	Synonym for operator[]. More...

Value *	getPointer (const Key &key)
	Returns a pointer to the value for the specified key, or nullptr if that key is empty. More...

const Value *	getPointer (const Key &key) const

int	numSlots () const
	Exposes the total number of slots used for debugging, profiling, and porting purposes. More...

Value &	operator[] (const Key &key)
	Returns a reference to the value at key, creating the value if it did not previously exist. More...

int	size () const
	Returns the number of key-value pairs stored. More...

size_t	sizeInMemory (size_t(*valueSizeFunction)(const Value &)=nullptr) const
	Returns the size of everything in this table (not counting objects reference from Values by pointers). More...

Protected Types
enum	{ NOT_FOUND = -1 }
	Constant used as a return value for findSlot. More...

typedef _internal::FastPODTable_Entry< Key, Value, valueIsSimplePOD >	Entry
	The type of the individual slots in the hash table. More...

typedef FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >	MyType
	The type of this class. More...

Protected Member Functions
	FastPODTable (const MyType &other)

int	findSlot (const Key &key, bool createIfNotFound, const typename Entry::StoredValueType &valueToUse, bool useValue)
	Returns the index of the slot for key. More...

void	getStats (int &longestProbe, float &averageProbe) const

void	grow ()
	Double the size of the table (must be a power of two size) More...

int	hashCode (const Key &key) const

MyType &	operator= (const MyType &other)

void	probe (int &i, int &probeDistance) const
	Step to the next index while probing for a slot. More...

Protected Attributes
Entry::StoredValueType	m_empty
	A default "empty" value; nullptr if Entry stores pointers. More...

int	m_initialSlots

shared_ptr< MemoryManager >	m_memoryManager

int	m_numSlots
	Number of elements in m_slot. More...

Entry *	m_slot
	Hash table slots. More...

int	m_usedSlots
	Number of elements in m_slot currently storing valid Value pointers. More...

Static Protected Attributes
static const int	SLOTS_PER_ENTRY = 3
	Number of slots to allocate for every entry used. More...

Detailed Description

template<typename Key, typename Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>
class G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >

Implemented with an open-addressing hash table that does not support remove.

This is substantially faster than Table<Point3int16, Value>. Implemented with quadratic probing.

Parameters

Key	Must be plain-old-data (POD), i.e., not have a destructor, since it will be memset rather than constructed.
valueAssignmentIsFast	Set to true only if Value is relatively small (e.g., 128 bytes or less), the assignment operator is efficient when applied to it (e.g., G3D::Array assignment is slow), and that is a POD type. Default is true.

Member Typedef Documentation

◆ Entry

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

typedef _internal::FastPODTable_Entry<Key, Value, valueIsSimplePOD> G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::Entry

protected

The type of the individual slots in the hash table.

◆ MyType

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

typedef FastPODTable<Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD> G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::MyType

protected

The type of this class.

Member Enumeration Documentation

◆ anonymous enum

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

anonymous enum

protected

Constant used as a return value for findSlot.

Enumerator
NOT_FOUND

Constructor & Destructor Documentation

◆ FastPODTable() [1/2]

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::FastPODTable ( const MyType & other )

protected

◆ FastPODTable() [2/2]

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::FastPODTable ( int expectedSize = 16 )

inline

Parameters

expectedSize Number of key-value pairs that are expected to be stored in this table.

◆ ~FastPODTable()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

virtual G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::~FastPODTable ( )

inlinevirtual

Member Function Documentation

◆ begin() [1/2]

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

ConstIterator G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::begin ( ) const

inline

Referenced by G3D::FastPointHashGrid< Value, PosFunc >::debugPrintStatistics().

◆ begin() [2/2]

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

Iterator G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::begin ( )

inline

◆ clear()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

void G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::clear ( int newExpectedSize = -1 )

inline

Removes all elements and shrinks table to its initial size.

Referenced by G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::clearAndSetMemoryManager(), and G3D::FastPointHashGrid< Value, PosFunc >::fastClear().

◆ clearAndSetMemoryManager()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

void G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::clearAndSetMemoryManager ( shared_ptr< MemoryManager > memoryManager )

inline

◆ containsKey()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

bool G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::containsKey ( const Key & key ) const

inline

◆ debugCheckStatus()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

void G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::debugCheckStatus ( ) const

inline

Asserts that the table is well-conditioned for performance.

◆ debugPrintStatus()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

void G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::debugPrintStatus ( ) const

inline

Referenced by G3D::FastPointHashGrid< Value, PosFunc >::debugPrintStatistics().

◆ fastClear()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

void G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::fastClear ( )

inline

Leaves slot memory allocated but removes the contents.

◆ findSlot()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

int G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::findSlot	(	const Key &	key,
		bool	createIfNotFound,
		const typename Entry::StoredValueType &	valueToUse,
		bool	useValue
	)

inlineprotected

Returns the index of the slot for key.

If key is not in the table and createIfNotFound is true, then this creates the slot. If key is not in the table and createIfNotFound is false, then this returns NOT_FOUND;

Parameters

valueToUse if a spot is created and useValue true, this is used as the value (allows the implementation of grow to re-insert existing values).

Referenced by G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::getPointer(), G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::grow(), and G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::operator[]().

◆ getCreate()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

Value& G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::getCreate ( const Key & key )

inline

Synonym for operator[].

◆ getPointer() [1/2]

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

Value* G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::getPointer ( const Key & key )

inline

Returns a pointer to the value for the specified key, or nullptr if that key is empty.

Referenced by G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::containsKey(), and G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::getPointer().

◆ getPointer() [2/2]

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

const Value* G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::getPointer ( const Key & key ) const

inline

◆ getStats()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

void G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::getStats	(	int &	longestProbe,
		float &	averageProbe
	)		const

inlineprotected

Referenced by G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::debugCheckStatus(), and G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::debugPrintStatus().

◆ grow()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

void G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::grow ( )

inlineprotected

Double the size of the table (must be a power of two size)

Referenced by G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::findSlot().

◆ hashCode()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

int G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::hashCode ( const Key & key ) const

inlineprotected

Referenced by G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::findSlot(), and G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::getStats().

◆ numSlots()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

int G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::numSlots ( ) const

inline

Exposes the total number of slots used for debugging, profiling, and porting purposes.

◆ operator=()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

MyType& G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::operator= ( const MyType & other )

protected

◆ operator[]()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

Value& G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::operator[] ( const Key & key )

inline

Returns a reference to the value at key, creating the value if it did not previously exist.

◆ probe()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

void G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::probe	(	int &	i,
		int &	probeDistance
	)		const

inlineprotected

Step to the next index while probing for a slot.

Parameters

probeDistance Number of times probed. 0 on the first call.

Referenced by G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::findSlot(), and G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::getStats().

◆ size()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

int G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::size ( ) const

inline

Returns the number of key-value pairs stored.

Referenced by G3D::FastPointHashGrid< Value, PosFunc >::clear(), G3D::FastPointHashGrid< Value, PosFunc >::debugPrintStatistics(), and G3D::FastPointHashGrid< Value, PosFunc >::numCells().

◆ sizeInMemory()

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

size_t G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::sizeInMemory ( size_t(*)(const Value &) valueSizeFunction = nullptr ) const

inline

Returns the size of everything in this table (not counting objects reference from Values by pointers).

Parameters

valueSizeFunction A function that computes the size of a Value. If nullptr, sizeof(Value) is used.

Example for a table of Arrays, where it is desirable to recurse into the arrays:

size_t arraySize(const Array<X>& y) {
   return y.sizeInMemory();
}
FastPODTable<int, Array<X> > table;
...
size_t s = table.sizeInMemory(&arraySize);

Member Data Documentation

◆ m_empty

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

Entry::StoredValueType G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::m_empty

protected

A default "empty" value; nullptr if Entry stores pointers.

Referenced by G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::FastPODTable(), G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::getPointer(), and G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::operator[]().

◆ m_initialSlots

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

int G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::m_initialSlots

protected

Referenced by G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::clear(), and G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::FastPODTable().

◆ m_memoryManager

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

shared_ptr<MemoryManager> G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::m_memoryManager

protected

Referenced by G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::clearAndSetMemoryManager().

◆ m_numSlots

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

int G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::m_numSlots

protected

Number of elements in m_slot.

◆ m_slot

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

Entry* G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::m_slot

protected

Hash table slots.

◆ m_usedSlots

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

int G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::m_usedSlots

protected

Number of elements in m_slot currently storing valid Value pointers.

◆ SLOTS_PER_ENTRY

template<typename Key , typename Value , class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>

const int G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::SLOTS_PER_ENTRY = 3

staticprotected

Number of slots to allocate for every entry used.

Load factor is 1 / SLOTS_PER_ENTRY. This was tuned for performance.

Referenced by G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::clear(), G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::debugPrintStatus(), G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::FastPODTable(), and G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >::findSlot().

Classes

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

template<typename Key, typename Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false> class G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >

Member Typedef Documentation

◆ Entry

◆ MyType

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ FastPODTable() [1/2]

◆ FastPODTable() [2/2]

◆ ~FastPODTable()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ clear()

◆ clearAndSetMemoryManager()

◆ containsKey()

◆ debugCheckStatus()

◆ debugPrintStatus()

◆ fastClear()

◆ findSlot()

◆ getCreate()

◆ getPointer() [1/2]

◆ getPointer() [2/2]

◆ getStats()

◆ grow()

◆ hashCode()

◆ numSlots()

◆ operator=()

◆ operator[]()

◆ probe()

◆ size()

◆ sizeInMemory()

Member Data Documentation

◆ m_empty

◆ m_initialSlots

◆ m_memoryManager

◆ m_numSlots

◆ m_slot

◆ m_usedSlots

◆ SLOTS_PER_ENTRY

template<typename Key, typename Value, class HashFunc = HashTrait<Key>, class EqualsFunc = EqualsTrait<Key>, bool valueIsSimplePOD = false>
class G3D::FastPODTable< Key, Value, HashFunc, EqualsFunc, valueIsSimplePOD >