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

#include <hashtable.hpp>

Public Types
typedef Titem::Key	Tkey

Public Member Functions
int	Count () const
	item count

void	Clear ()
	simple clear - forget all items - used by CSegmentCostCacheT.Flush()

const Titem *	Find (const Tkey &key) const
	const item search

Titem *	Find (const Tkey &key)
	non-const item search

Titem *	TryPop (const Tkey &key)
	non-const item search & optional removal (if found)

Titem &	Pop (const Tkey &key)
	non-const item search & removal

bool	TryPop (Titem &item)
	non-const item search & optional removal (if found)

void	Pop (Titem &item)
	non-const item search & removal

void	Push (Titem &new_item)
	add one item - copy it from the given item

Static Public Attributes
static constexpr int	HASH_BITS = Thash_bits_

static constexpr int	CAPACITY = 1 << HASH_BITS

Protected Types
typedef HashTableSlot< Titem >	Slot
	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)
	static helper - return hash for the given key modulo number of slots

static int	CalcHash (const Titem &item)
	static helper - return hash for the given item modulo number of slots

Protected Attributes
Slot	slots [CAPACITY]

int	number_of_items = 0

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 133 of file hashtable.hpp.

Member Typedef Documentation

◆ Slot

template<class Titem , int Thash_bits_>

typedef HashTableSlot<Titem> HashTable< Titem, Thash_bits_ >::Slot

protected

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

Definition at line 144 of file hashtable.hpp.

◆ Tkey

template<class Titem , int Thash_bits_>

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

Definition at line 135 of file hashtable.hpp.

Member Function Documentation

◆ CalcHash() [1/2]

template<class Titem , int Thash_bits_>

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

inlinestaticprotected

static helper - return hash for the given item modulo number of slots

Definition at line 160 of file hashtable.hpp.

References HashTable< Titem, Thash_bits_ >::CalcHash().

◆ CalcHash() [2/2]

template<class Titem , int Thash_bits_>

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

inlinestaticprotected

static helper - return hash for the given key modulo number of slots

Definition at line 150 of file hashtable.hpp.

Referenced by HashTable< Titem, Thash_bits_ >::CalcHash(), HashTable< Titem, Thash_bits_ >::Find(), HashTable< Titem, Thash_bits_ >::Find(), HashTable< Titem, Thash_bits_ >::Push(), HashTable< Titem, Thash_bits_ >::TryPop(), and HashTable< Titem, Thash_bits_ >::TryPop().

◆ Clear()

template<class Titem , int Thash_bits_>

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

inline

simple clear - forget all items - used by CSegmentCostCacheT.Flush()

Definition at line 173 of file hashtable.hpp.

References HashTable< Titem, Thash_bits_ >::Clear().

Referenced by HashTable< Titem, Thash_bits_ >::Clear(), and CSegmentCostCacheT< Tsegment >::Flush().

◆ Count()

template<class Titem , int Thash_bits_>

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

inline

item count

Definition at line 167 of file hashtable.hpp.

Referenced by NodeList< Titem, Thash_bits_open, Thash_bits_closed >::ClosedCount(), and NodeList< Titem, Thash_bits_open, Thash_bits_closed >::OpenCount().

◆ Find() [1/2]

template<class Titem , int Thash_bits_>

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

inline

non-const item search

Definition at line 189 of file hashtable.hpp.

References HashTable< Titem, Thash_bits_ >::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

const item search

Definition at line 180 of file hashtable.hpp.

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

Referenced by NodeList< Titem, Thash_bits_open, Thash_bits_closed >::FindClosedNode(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::FindOpenNode(), NodeList< Titem, Thash_bits_open, Thash_bits_closed >::InsertClosedNode(), and NodeList< Titem, Thash_bits_open, Thash_bits_closed >::InsertOpenNode().

◆ Pop() [1/2]

template<class Titem , int Thash_bits_>

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

inline

non-const item search & removal

Definition at line 210 of file hashtable.hpp.

References HashTable< Titem, Thash_bits_ >::TryPop().

Referenced by NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopBestOpenNode(), and NodeList< Titem, Thash_bits_open, Thash_bits_closed >::PopOpenNode().

◆ Pop() [2/2]

template<class Titem , int Thash_bits_>

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

inline

non-const item search & removal

Definition at line 231 of file hashtable.hpp.

References HashTable< Titem, Thash_bits_ >::TryPop().

◆ Push()

template<class Titem , int Thash_bits_>

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

inline

add one item - copy it from the given item

Definition at line 238 of file hashtable.hpp.

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

Referenced by NodeList< Titem, Thash_bits_open, Thash_bits_closed >::InsertClosedNode(), and NodeList< Titem, Thash_bits_open, Thash_bits_closed >::InsertOpenNode().

◆ TryPop() [1/2]

template<class Titem , int Thash_bits_>

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

inline

non-const item search & optional removal (if found)

Definition at line 198 of file hashtable.hpp.

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

Referenced by HashTable< Titem, Thash_bits_ >::Pop(), and HashTable< Titem, Thash_bits_ >::Pop().

◆ TryPop() [2/2]

template<class Titem , int Thash_bits_>

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

inline

non-const item search & optional removal (if found)

Definition at line 218 of file hashtable.hpp.

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

Field Documentation

◆ CAPACITY

template<class Titem , int Thash_bits_>

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

staticconstexpr

Definition at line 137 of file hashtable.hpp.

◆ HASH_BITS

template<class Titem , int Thash_bits_>

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

staticconstexpr

Definition at line 136 of file hashtable.hpp.

◆ number_of_items

template<class Titem , int Thash_bits_>

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

protected

Definition at line 147 of file hashtable.hpp.

◆ slots

template<class Titem , int Thash_bits_>

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

protected

Definition at line 146 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