class HashTable<Titem, HASH_BITS> - simple hash table of pointers allocated elsewhere. More...

#include <hashtable.hpp>

Public Types
typedef Titem::Key	Tkey
	Make Titem::Key a property of HashTable.

Public Member Functions
int	Count () const
	Get the number of elements.
void	Clear ()
	Clear all items.
const Titem *	Find (const Tkey &key) const
	Try to find an item by key.
Titem *	Find (const Tkey &key)
	Try to find an item by key.
Titem *	TryPop (const Tkey &key)
	Remove an item by key if found.
Titem &	Pop (const Tkey &key)
	Remove an item by key that must exist.
bool	TryPop (Titem &item)
	Remove an item if found.
void	Pop (Titem &item)
	Remove an item that must exist.
void	Push (Titem &new_item)
	Add an item that may not exist.

Static Public Attributes
static constexpr int	HASH_BITS = Thash_bits_
	Publish num of hash bits.
static constexpr int	CAPACITY = 1 << HASH_BITS
	And num of slots 2^bits.

Protected Types
using	Slot = HashTableSlot<Titem>
	each slot contains pointer to the first item in the list, Titem contains pointer to the next item - GetHashNext(), SetHashNext()

Static Protected Member Functions
static int	CalcHash (const Tkey &key)
	Return hash for the given key modulo number of slots.
static int	CalcHash (const Titem &item)
	Return hash for the given item modulo number of slots.

Protected Attributes
Slot	slots [CAPACITY]
	Data storage (array of blobs).
int	number_of_items = 0
	Item counter.

Detailed Description

template<class Titem, int Thash_bits_>
class HashTable< Titem, Thash_bits_ >

class HashTable<Titem, HASH_BITS> - simple hash table of pointers allocated elsewhere.

Supports: Add/Find/Remove of Titems.

Your Titem must meet some extra requirements to be HashTable compliant:

its constructor/destructor (if any) must be public
if the copying of item requires an extra resource management, you must define also copy constructor
must support nested type (struct, class or typedef) Titem::Key that defines the type of key class for that item
must support public method: const Key& GetKey() const; // return the item's key object

In addition, the Titem::Key class must support:

public method that calculates key's hash: int CalcHash() const;
public 'equality' operator to compare the key with another one bool operator==(const Key &other) const;

Definition at line 149 of file hashtable.hpp.

Member Typedef Documentation

◆ Slot

template<class Titem, int Thash_bits_>

using HashTable< Titem, Thash_bits_ >::Slot = HashTableSlot<Titem>

protected

each slot contains pointer to the first item in the list, Titem contains pointer to the next item - GetHashNext(), SetHashNext()

Definition at line 160 of file hashtable.hpp.

◆ Tkey

template<class Titem, int Thash_bits_>

typedef Titem::Key HashTable< Titem, Thash_bits_ >::Tkey

Make Titem::Key a property of HashTable.

Definition at line 151 of file hashtable.hpp.

Member Function Documentation

◆ CalcHash() [1/2]

template<class Titem, int Thash_bits_>

int HashTable< Titem, Thash_bits_ >::CalcHash ( const Titem & item )

inlinestaticprotected

Return hash for the given item modulo number of slots.

Parameters

item	The item to consider.

Returns: The hash of its key.

Definition at line 184 of file hashtable.hpp.

References CalcHash().

◆ CalcHash() [2/2]

template<class Titem, int Thash_bits_>

int HashTable< Titem, Thash_bits_ >::CalcHash ( const Tkey & key )

inlinestaticprotected

Return hash for the given key modulo number of slots.

Parameters

key	The key to consider.

Returns: The hash of the key.

Definition at line 170 of file hashtable.hpp.

References HASH_BITS.

Referenced by CalcHash(), Find(), Find(), Push(), TryPop(), and TryPop().

◆ Clear()

template<class Titem, int Thash_bits_>

void HashTable< Titem, Thash_bits_ >::Clear ( )

inline

Clear all items.

Definition at line 200 of file hashtable.hpp.

References CAPACITY, and Clear().

Referenced by Clear(), and CSegmentCostCacheT< CachedData >::Flush().

◆ Count()

template<class Titem, int Thash_bits_>

int HashTable< Titem, Thash_bits_ >::Count ( ) const

inline

Get the number of elements.

Returns: The item count.

Definition at line 194 of file hashtable.hpp.

Referenced by NodeList< CYapfRailNode, 8, 10 >::ClosedCount(), and NodeList< CYapfRailNode, 8, 10 >::OpenCount().

◆ Find() [1/2]

template<class Titem, int Thash_bits_>

Titem * HashTable< Titem, Thash_bits_ >::Find ( const Tkey & key )

inline

Try to find an item by key.

Parameters

key	The key to find.

Returns: The found item, or nullptr.

Definition at line 224 of file hashtable.hpp.

References CalcHash(), and HashTableSlot< TItem >::Find().

◆ Find() [2/2]

template<class Titem, int Thash_bits_>

const Titem * HashTable< Titem, Thash_bits_ >::Find ( const Tkey & key ) const

inline

Try to find an item by key.

Parameters

key	The key to find.

Returns: The found item, or nullptr.

Definition at line 211 of file hashtable.hpp.

References CalcHash(), and HashTableSlot< TItem >::Find().

Referenced by NodeList< CYapfRailNode, 8, 10 >::FindClosedNode(), NodeList< CYapfRailNode, 8, 10 >::FindOpenNode(), NodeList< CYapfRailNode, 8, 10 >::InsertClosedNode(), and NodeList< CYapfRailNode, 8, 10 >::InsertOpenNode().

◆ Pop() [1/2]

template<class Titem, int Thash_bits_>

Titem & HashTable< Titem, Thash_bits_ >::Pop ( const Tkey & key )

inline

Remove an item by key that must exist.

Parameters

key	The key to search for.

Returns: The popped element; never nullptr.

Definition at line 253 of file hashtable.hpp.

References TryPop().

Referenced by NodeList< CYapfRailNode, 8, 10 >::PopBestOpenNode(), and NodeList< CYapfRailNode, 8, 10 >::PopOpenNode().

◆ Pop() [2/2]

template<class Titem, int Thash_bits_>

void HashTable< Titem, Thash_bits_ >::Pop ( Titem & item )

inline

Remove an item that must exist.

Parameters

item	The item to remove.

Definition at line 281 of file hashtable.hpp.

References TryPop().

◆ Push()

template<class Titem, int Thash_bits_>

void HashTable< Titem, Thash_bits_ >::Push ( Titem & new_item )

inline

Add an item that may not exist.

Parameters

new_item The item to add.

Definition at line 291 of file hashtable.hpp.

References HashTableSlot< TItem >::Attach(), CalcHash(), and HashTableSlot< TItem >::Find().

Referenced by NodeList< CYapfRailNode, 8, 10 >::InsertClosedNode(), and NodeList< CYapfRailNode, 8, 10 >::InsertOpenNode().

◆ TryPop() [1/2]

template<class Titem, int Thash_bits_>

Titem * HashTable< Titem, Thash_bits_ >::TryPop ( const Tkey & key )

inline

Remove an item by key if found.

Parameters

key	The key to search for.

Returns: The popped element, or nullptr.

Definition at line 237 of file hashtable.hpp.

References CalcHash(), and HashTableSlot< TItem >::Detach().

Referenced by Pop(), and Pop().

◆ TryPop() [2/2]

template<class Titem, int Thash_bits_>

bool HashTable< Titem, Thash_bits_ >::TryPop ( Titem & item )

inline

Remove an item if found.

Parameters

item	The item to remove.

Returns: true iff the item existed.

Definition at line 265 of file hashtable.hpp.

References CalcHash(), and HashTableSlot< TItem >::Detach().

Field Documentation

◆ CAPACITY

template<class Titem, int Thash_bits_>

int HashTable< Titem, Thash_bits_ >::CAPACITY = 1 << HASH_BITS

staticconstexpr

And num of slots 2^bits.

Definition at line 153 of file hashtable.hpp.

Referenced by Clear().

◆ HASH_BITS

template<class Titem, int Thash_bits_>

int HashTable< Titem, Thash_bits_ >::HASH_BITS = Thash_bits_

staticconstexpr

Publish num of hash bits.

Definition at line 152 of file hashtable.hpp.

Referenced by CalcHash().

◆ number_of_items

template<class Titem, int Thash_bits_>

int HashTable< Titem, Thash_bits_ >::number_of_items = 0

protected

Item counter.

Definition at line 163 of file hashtable.hpp.

◆ slots

template<class Titem, int Thash_bits_>

Slot HashTable< Titem, Thash_bits_ >::slots[CAPACITY]

protected

Data storage (array of blobs).

Definition at line 162 of file hashtable.hpp.

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

src/misc/hashtable.hpp

Public Types

Public Member Functions

Static Public Attributes

Protected Types

Static Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ Slot

◆ Tkey

Member Function Documentation

◆ CalcHash() [1/2]

◆ CalcHash() [2/2]

◆ Clear()

◆ Count()

◆ Find() [1/2]

◆ Find() [2/2]

◆ Pop() [1/2]

◆ Pop() [2/2]

◆ Push()

◆ TryPop() [1/2]

◆ TryPop() [2/2]

Field Documentation

◆ CAPACITY

◆ HASH_BITS

◆ number_of_items

◆ slots