ezEngine  Milestone 9
HashTable.h
1 #pragma once
2 
3 #include <Foundation/Algorithm/HashingUtils.h>
4 #include <Foundation/Math/Math.h>
5 #include <Foundation/Memory/AllocatorWrapper.h>
6 #include <Foundation/Types/ArrayPtr.h>
7 
16 
18 template <typename KeyType, typename ValueType, typename Hasher>
20 {
21 public:
24  {
25  EZ_DECLARE_POD_TYPE();
26 
28  bool IsValid() const; // [tested]
29 
32 
35 
37  const KeyType& Key() const; // [tested]
38 
40  const ValueType& Value() const; // [tested]
41 
43  void Next(); // [tested]
44 
46  void operator++(); // [tested]
47 
48  protected:
49  friend class ezHashTableBase<KeyType, ValueType, Hasher>;
50 
52 
54  ezUInt32 m_uiCurrentIndex; // current element index that this iterator points to.
55  ezUInt32 m_uiCurrentCount; // current number of valid elements that this iterator has found so far.
56  };
57 
59  struct Iterator : public ConstIterator
60  {
61  EZ_DECLARE_POD_TYPE();
62 
64  EZ_ALWAYS_INLINE Iterator(const Iterator& rhs); // [tested]
65 
67  EZ_ALWAYS_INLINE void operator=(const Iterator& rhs); // [tested]
68 
69  // this is required to pull in the const version of this function
71 
73  EZ_FORCE_INLINE ValueType& Value(); // [tested]
74 
76  EZ_ALWAYS_INLINE ValueType& operator*() { return Value(); }
77 
78  private:
79  friend class ezHashTableBase<KeyType, ValueType, Hasher>;
80 
81  explicit Iterator(const ezHashTableBase<KeyType, ValueType, Hasher>& hashTable);
82  };
83 
84 protected:
86  ezHashTableBase(ezAllocatorBase* pAllocator); // [tested]
87 
90 
93 
95  ~ezHashTableBase(); // [tested]
96 
98  void operator=(const ezHashTableBase<KeyType, ValueType, Hasher>& rhs); // [tested]
99 
102 
103 public:
105  bool operator==(const ezHashTableBase<KeyType, ValueType, Hasher>& rhs) const; // [tested]
106 
108  bool operator!=(const ezHashTableBase<KeyType, ValueType, Hasher>& rhs) const; // [tested]
109 
111  void Reserve(ezUInt32 uiCapacity); // [tested]
112 
117  void Compact(); // [tested]
118 
120  ezUInt32 GetCount() const; // [tested]
121 
123  bool IsEmpty() const; // [tested]
124 
126  void Clear(); // [tested]
127 
131  template <typename CompatibleKeyType, typename CompatibleValueType>
132  bool Insert(CompatibleKeyType&& key, CompatibleValueType&& value, ValueType* out_oldValue = nullptr); // [tested]
133 
135  template <typename CompatibleKeyType>
136  bool Remove(const CompatibleKeyType& key, ValueType* out_oldValue = nullptr); // [tested]
137 
139  Iterator Remove(const Iterator& pos); // [tested]
140 
142  template <typename CompatibleKeyType>
143  bool TryGetValue(const CompatibleKeyType& key, ValueType& out_value) const; // [tested]
144 
146  template <typename CompatibleKeyType>
147  bool TryGetValue(const CompatibleKeyType& key, const ValueType*& out_pValue) const; // [tested]
148 
150  template <typename CompatibleKeyType>
151  bool TryGetValue(const CompatibleKeyType& key, ValueType*& out_pValue); // [tested]
152 
154  template <typename CompatibleKeyType>
155  const ValueType* GetValue(const CompatibleKeyType& key) const; // [tested]
156 
158  template <typename CompatibleKeyType>
159  ValueType* GetValue(const CompatibleKeyType& key); // [tested]
160 
162  ValueType& operator[](const KeyType& key); // [tested]
163 
165  template <typename CompatibleKeyType>
166  bool Contains(const CompatibleKeyType& key) const; // [tested]
167 
169  Iterator GetIterator(); // [tested]
170 
172  ConstIterator GetIterator() const; // [tested]
173 
175  ezAllocatorBase* GetAllocator() const;
176 
178  ezUInt64 GetHeapMemoryUsage() const; // [tested]
179 
181  void Swap(ezHashTableBase<KeyType, ValueType, Hasher>& other); // [tested]
182 
183 
184 private:
185  struct Entry
186  {
187  KeyType key;
188  ValueType value;
189  };
190 
191  Entry* m_pEntries;
192  ezUInt32* m_pEntryFlags;
193 
194  ezUInt32 m_uiCount;
195  ezUInt32 m_uiCapacity;
196 
197  ezAllocatorBase* m_pAllocator;
198 
199  enum
200  {
201  FREE_ENTRY = 0,
202  VALID_ENTRY = 1,
203  DELETED_ENTRY = 2,
204  FLAGS_MASK = 3,
205  CAPACITY_ALIGNMENT = 32
206  };
207 
208  void SetCapacity(ezUInt32 uiCapacity);
209 
210  void RemoveInternal(ezUInt32 uiIndex);
211  template <typename CompatibleKeyType>
212  ezUInt32 FindEntry(const CompatibleKeyType& key) const;
213 
214  template <typename CompatibleKeyType>
215  ezUInt32 FindEntry(ezUInt32 uiHash, const CompatibleKeyType& key) const;
216 
217  ezUInt32 GetFlagsCapacity() const;
218  ezUInt32 GetFlags(ezUInt32* pFlags, ezUInt32 uiEntryIndex) const;
219  void SetFlags(ezUInt32 uiEntryIndex, ezUInt32 uiFlags);
220 
221  bool IsFreeEntry(ezUInt32 uiEntryIndex) const;
222  bool IsValidEntry(ezUInt32 uiEntryIndex) const;
223  bool IsDeletedEntry(ezUInt32 uiEntryIndex) const;
224 
225  void MarkEntryAsFree(ezUInt32 uiEntryIndex);
226  void MarkEntryAsValid(ezUInt32 uiEntryIndex);
227  void MarkEntryAsDeleted(ezUInt32 uiEntryIndex);
228 };
229 
231 template <typename KeyType, typename ValueType, typename Hasher = ezHashHelper<KeyType>, typename AllocatorWrapper = ezDefaultAllocatorWrapper>
232 class ezHashTable : public ezHashTableBase<KeyType, ValueType, Hasher>
233 {
234 public:
235  ezHashTable();
236  ezHashTable(ezAllocatorBase* pAllocator);
237 
240 
243 
244 
246  void operator=(const ezHashTableBase<KeyType, ValueType, Hasher>& rhs);
247 
249  void operator=(ezHashTableBase<KeyType, ValueType, Hasher>&& rhs);
250 };
251 
252 #include <Foundation/Containers/Implementation/HashTable_inl.h>
253 
EZ_ALWAYS_INLINE Iterator(const Iterator &rhs)
Creates a new iterator from another.
bool IsValid() const
Checks whether this iterator points to a valid element.
Definition: HashTable_inl.h:19
const KeyType & Key() const
Returns the &#39;key&#39; of the element that this iterator points to.
Definition: HashTable_inl.h:37
Base class for all memory allocators.
Definition: AllocatorBase.h:21
const ValueType & Value() const
Returns the &#39;value&#39; of the element that this iterator points to.
Definition: HashTable_inl.h:43
void operator=(const ezHashTableBase< KeyType, ValueType, Hasher > &rhs)
Copies the data from another hashtable into this one.
Definition: HashTable_inl.h:145
~ezHashTableBase()
Destructor.
Definition: HashTable_inl.h:136
const ValueType * GetValue(const CompatibleKeyType &key) const
Returns a pointer to the value of the entry with the given key if found, otherwise returns nullptr...
bool operator!=(const ezHashTableBase< KeyType, ValueType, Hasher > &rhs) const
Compares this table to another table.
Definition: HashTable_inl.h:228
Implementation of a hashtable which stores key/value pairs.
Definition: HashTable.h:19
bool operator==(const typename ezHashTableBase< KeyType, ValueType, Hasher >::ConstIterator &it2) const
Checks whether the two iterators point to the same element.
Definition: HashTable_inl.h:25
bool Contains(const CompatibleKeyType &key) const
Returns if an entry with given key exists in the table.
bool Remove(const CompatibleKeyType &key, ValueType *out_oldValue=nullptr)
Removes the entry with the given key. Returns if an entry was removed and optionally writes out the o...
Definition: HashTable_inl.h:337
ezAllocatorBase * GetAllocator() const
Returns the allocator that is used by this instance.
Definition: HashTable_inl.h:506
bool IsEmpty() const
Returns true, if the hashtable does not contain any elements.
Definition: HashTable_inl.h:269
bool TryGetValue(const CompatibleKeyType &key, ValueType &out_value) const
Returns if an entry with the given key was found and if found writes out the corresponding value to o...
Definition: HashTable_inl.h:402
Const iterator.
Definition: HashTable.h:23
Definition: HashTable.h:232
void Next()
Advances the iterator to the next element in the map. The iterator will not be valid anymore...
Definition: HashTable_inl.h:49
EZ_FORCE_INLINE ValueType & Value()
Returns the &#39;value&#39; of the element that this iterator points to.
Definition: HashTable_inl.h:93
EZ_ALWAYS_INLINE void operator=(const Iterator &rhs)
Assigns one iterator no another.
Definition: HashTable_inl.h:85
ValueType & operator[](const KeyType &key)
Returns the value to the given key if found or creates a new entry with the given key and a default c...
Definition: HashTable_inl.h:459
void operator++()
Shorthand for &#39;Next&#39;.
Definition: HashTable_inl.h:62
bool operator!=(const typename ezHashTableBase< KeyType, ValueType, Hasher >::ConstIterator &it2) const
Checks whether the two iterators point to the same element.
Definition: HashTable_inl.h:31
void Reserve(ezUInt32 uiCapacity)
Expands the hashtable by over-allocating the internal storage so that the load factor is lower or equ...
Definition: HashTable_inl.h:234
bool Insert(CompatibleKeyType &&key, CompatibleValueType &&value, ValueType *out_oldValue=nullptr)
Inserts the key value pair or replaces value if an entry with the given key already exists...
Definition: HashTable_inl.h:292
Iterator GetIterator()
Returns an Iterator to the very first element.
Definition: HashTable_inl.h:494
Iterator with write access.
Definition: HashTable.h:59
ezUInt32 GetCount() const
Returns the number of active entries in the table.
Definition: HashTable_inl.h:263
EZ_ALWAYS_INLINE ValueType & operator*()
Returns the &#39;value&#39; of the element that this iterator points to.
Definition: HashTable.h:76
void Clear()
Clears the table.
Definition: HashTable_inl.h:275
void Swap(ezHashTableBase< KeyType, ValueType, Hasher > &other)
Swaps this map with the other one.
Definition: HashTable_inl.h:709
void Compact()
Tries to compact the hashtable to avoid wasting memory.
Definition: HashTable_inl.h:245
ezHashTableBase(ezAllocatorBase *pAllocator)
Creates an empty hashtable. Does not allocate any data yet.
Definition: HashTable_inl.h:102
bool operator==(const ezHashTableBase< KeyType, ValueType, Hasher > &rhs) const
Compares this table to another table.
Definition: HashTable_inl.h:203
ezUInt64 GetHeapMemoryUsage() const
Returns the amount of bytes that are currently allocated on the heap.
Definition: HashTable_inl.h:512