ezEngine  Milestone 7
HashTable.h
1 #pragma once
2 
3 #include <Foundation/Algorithm/Hashing.h>
4 #include <Foundation/Types/ArrayPtr.h>
5 #include <Foundation/Math/Math.h>
6 #include <Foundation/Memory/AllocatorWrapper.h>
7 
16 
18 template <typename KeyType, typename ValueType, typename Hasher>
20 {
21 public:
24  {
25  public:
27  bool IsValid() const; // [tested]
28 
31 
34 
36  const KeyType& Key() const; // [tested]
37 
39  const ValueType& Value() const; // [tested]
40 
42  void Next(); // [tested]
43 
45  void operator++(); // [tested]
46 
47  protected:
48  friend class ezHashTableBase<KeyType, ValueType, Hasher>;
49 
51 
53  ezUInt32 m_uiCurrentIndex; // current element index that this iterator points to.
54  ezUInt32 m_uiCurrentCount; // current number of valid elements that this iterator has found so far.
55  };
56 
58  class Iterator : public ConstIterator
59  {
60  public:
61  // this is required to pull in the const version of this function
63 
65  ValueType& Value(); // [tested]
66 
67  private:
68  friend class ezHashTableBase<KeyType, ValueType, Hasher>;
69 
70  explicit Iterator(const ezHashTableBase<KeyType, ValueType, Hasher>& hashTable);
71  };
72 
73 protected:
75  ezHashTableBase(ezAllocatorBase* pAllocator); // [tested]
76 
79 
81  ~ezHashTableBase(); // [tested]
82 
84  void operator= (const ezHashTableBase<KeyType, ValueType, Hasher>& rhs); // [tested]
85 
86 public:
87 
89  bool operator== (const ezHashTableBase<KeyType, ValueType, Hasher>& rhs) const; // [tested]
90 
92  bool operator!= (const ezHashTableBase<KeyType, ValueType, Hasher>& rhs) const; // [tested]
93 
95  void Reserve(ezUInt32 uiCapacity); // [tested]
96 
101  void Compact(); // [tested]
102 
104  ezUInt32 GetCount() const; // [tested]
105 
107  bool IsEmpty() const; // [tested]
108 
110  void Clear(); // [tested]
111 
115  bool Insert(const KeyType& key, const ValueType& value, ValueType* out_oldValue = nullptr); // [tested]
116 
118  bool Remove(const KeyType& key, ValueType* out_oldValue = nullptr); // [tested]
119 
121  bool TryGetValue(const KeyType& key, ValueType& out_value) const; // [tested]
122 
124  bool TryGetValue(const KeyType& key, ValueType*& out_pValue) const; // [tested]
125 
127  ValueType& operator[](const KeyType& key); // [tested]
128 
130  bool Contains(const KeyType& key) const; // [tested]
131 
133  Iterator GetIterator(); // [tested]
134 
136  ConstIterator GetIterator() const; // [tested]
137 
139  ezAllocatorBase* GetAllocator() const;
140 
142  ezUInt64 GetHeapMemoryUsage() const; // [tested]
143 
144 private:
145 
146  struct Entry
147  {
148  KeyType key;
149  ValueType value;
150  };
151 
152  Entry* m_pEntries;
153  ezUInt32* m_pEntryFlags;
154 
155  ezUInt32 m_uiCount;
156  ezUInt32 m_uiCapacity;
157 
158  ezAllocatorBase* m_pAllocator;
159 
160  enum
161  {
162  FREE_ENTRY = 0,
163  VALID_ENTRY = 1,
164  DELETED_ENTRY = 2,
165  FLAGS_MASK = 3,
166  CAPACITY_ALIGNMENT = 32
167  };
168 
169  void SetCapacity(ezUInt32 uiCapacity);
170  ezUInt32 FindEntry(const KeyType& key) const;
171  ezUInt32 FindEntry(ezUInt32 uiHash, const KeyType& key) const;
172 
173  ezUInt32 GetFlagsCapacity() const;
174  ezUInt32 GetFlags(ezUInt32* pFlags, ezUInt32 uiEntryIndex) const;
175  void SetFlags(ezUInt32 uiEntryIndex, ezUInt32 uiFlags);
176 
177  bool IsFreeEntry(ezUInt32 uiEntryIndex) const;
178  bool IsValidEntry(ezUInt32 uiEntryIndex) const;
179  bool IsDeletedEntry(ezUInt32 uiEntryIndex) const;
180 
181  void MarkEntryAsFree(ezUInt32 uiEntryIndex);
182  void MarkEntryAsValid(ezUInt32 uiEntryIndex);
183  void MarkEntryAsDeleted(ezUInt32 uiEntryIndex);
184 };
185 
187 template <typename KeyType, typename ValueType, typename Hasher = ezHashHelper<KeyType>, typename AllocatorWrapper = ezDefaultAllocatorWrapper>
188 class ezHashTable : public ezHashTableBase<KeyType, ValueType, Hasher>
189 {
190 public:
191  ezHashTable();
192  ezHashTable(ezAllocatorBase* pAllocator);
193 
196 
198  void operator=(const ezHashTableBase<KeyType, ValueType, Hasher>& rhs);
199 };
200 
201 #include <Foundation/Containers/Implementation/HashTable_inl.h>
202