OpenTTD Source  20241111-master-gce64d5f5d9
Public Types | Public Member Functions | Static Public Attributes | Protected Types | Static Protected Member Functions | Protected Attributes
HashTable< Titem, Thash_bits_ > Class Template Reference

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.

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