ezEngine  Milestone 9
HashSet.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 Hasher>
20 {
21 public:
24  {
25  public:
27  bool IsValid() const; // [tested]
28 
30  bool operator==(const typename ezHashSetBase<KeyType, Hasher>::ConstIterator& it2) const;
31 
33  bool operator!=(const typename ezHashSetBase<KeyType, Hasher>::ConstIterator& it2) const;
34 
36  const KeyType& Key() const; // [tested]
37 
39  EZ_ALWAYS_INLINE const KeyType& operator*() { return Key(); }
40 
42  void Next(); // [tested]
43 
45  void operator++(); // [tested]
46 
47  protected:
48  friend class ezHashSetBase<KeyType, Hasher>;
49 
50  explicit ConstIterator(const ezHashSetBase<KeyType, Hasher>& hashSet);
51  void SetToBegin();
52  void SetToEnd();
53 
54  const ezHashSetBase<KeyType, Hasher>& m_hashSet;
55  ezUInt32 m_uiCurrentIndex; // current element index that this iterator points to.
56  ezUInt32 m_uiCurrentCount; // current number of valid elements that this iterator has found so far.
57  };
58 
59 protected:
61  ezHashSetBase(ezAllocatorBase* pAllocator); // [tested]
62 
64  ezHashSetBase(const ezHashSetBase<KeyType, Hasher>& rhs, ezAllocatorBase* pAllocator); // [tested]
65 
67  ezHashSetBase(ezHashSetBase<KeyType, Hasher>&& rhs, ezAllocatorBase* pAllocator); // [tested]
68 
70  ~ezHashSetBase(); // [tested]
71 
73  void operator=(const ezHashSetBase<KeyType, Hasher>& rhs); // [tested]
74 
76  void operator=(ezHashSetBase<KeyType, Hasher>&& rhs); // [tested]
77 
78 public:
80  bool operator==(const ezHashSetBase<KeyType, Hasher>& rhs) const; // [tested]
81 
83  bool operator!=(const ezHashSetBase<KeyType, Hasher>& rhs) const; // [tested]
84 
87  void Reserve(ezUInt32 uiCapacity); // [tested]
88 
93  void Compact(); // [tested]
94 
96  ezUInt32 GetCount() const; // [tested]
97 
99  bool IsEmpty() const; // [tested]
100 
102  void Clear(); // [tested]
103 
105  template <typename CompatibleKeyType>
106  bool Insert(CompatibleKeyType&& key); // [tested]
107 
109  bool Remove(const KeyType& key); // [tested]
110 
112  bool Contains(const KeyType& key) const; // [tested]
113 
115  ConstIterator GetIterator() const; // [tested]
116 
119  ConstIterator GetEndIterator() const;
120 
122  ezAllocatorBase* GetAllocator() const;
123 
125  ezUInt64 GetHeapMemoryUsage() const; // [tested]
126 
128  void Swap(ezHashSetBase<KeyType, Hasher>& other); // [tested]
129 
130 private:
131  KeyType* m_pEntries;
132  ezUInt32* m_pEntryFlags;
133 
134  ezUInt32 m_uiCount;
135  ezUInt32 m_uiCapacity;
136 
137  ezAllocatorBase* m_pAllocator;
138 
139  enum
140  {
141  FREE_ENTRY = 0,
142  VALID_ENTRY = 1,
143  DELETED_ENTRY = 2,
144  FLAGS_MASK = 3,
145  CAPACITY_ALIGNMENT = 32
146  };
147 
148  void SetCapacity(ezUInt32 uiCapacity);
149  ezUInt32 FindEntry(const KeyType& key) const;
150  ezUInt32 FindEntry(ezUInt32 uiHash, const KeyType& key) const;
151 
152  ezUInt32 GetFlagsCapacity() const;
153  ezUInt32 GetFlags(ezUInt32* pFlags, ezUInt32 uiEntryIndex) const;
154  void SetFlags(ezUInt32 uiEntryIndex, ezUInt32 uiFlags);
155 
156  bool IsFreeEntry(ezUInt32 uiEntryIndex) const;
157  bool IsValidEntry(ezUInt32 uiEntryIndex) const;
158  bool IsDeletedEntry(ezUInt32 uiEntryIndex) const;
159 
160  void MarkEntryAsFree(ezUInt32 uiEntryIndex);
161  void MarkEntryAsValid(ezUInt32 uiEntryIndex);
162  void MarkEntryAsDeleted(ezUInt32 uiEntryIndex);
163 };
164 
166 template <typename KeyType, typename Hasher = ezHashHelper<KeyType>, typename AllocatorWrapper = ezDefaultAllocatorWrapper>
167 class ezHashSet : public ezHashSetBase<KeyType, Hasher>
168 {
169 public:
170  ezHashSet();
171  ezHashSet(ezAllocatorBase* pAllocator);
172 
175 
178 
179  void operator=(const ezHashSet<KeyType, Hasher, AllocatorWrapper>& rhs);
180  void operator=(const ezHashSetBase<KeyType, Hasher>& rhs);
181 
182  void operator=(ezHashSet<KeyType, Hasher, AllocatorWrapper>&& rhs);
183  void operator=(ezHashSetBase<KeyType, Hasher>&& rhs);
184 };
185 
186 template <typename KeyType, typename Hasher>
188 {
189  return set.GetIterator();
190 }
191 
192 template <typename KeyType, typename Hasher>
194 {
195  return set.GetIterator();
196 }
197 
198 template <typename KeyType, typename Hasher>
200 {
201  return set.GetEndIterator();
202 }
203 
204 template <typename KeyType, typename Hasher>
206 {
207  return set.GetEndIterator();
208 }
209 
210 #include <Foundation/Containers/Implementation/HashSet_inl.h>
211 
bool Contains(const KeyType &key) const
Returns if an entry with given key exists in the table.
Definition: HashSet_inl.h:349
void Reserve(ezUInt32 uiCapacity)
Expands the hashset by over-allocating the internal storage so that the load factor is lower or equal...
Definition: HashSet_inl.h:210
Base class for all memory allocators.
Definition: AllocatorBase.h:21
bool operator==(const typename ezHashSetBase< KeyType, Hasher >::ConstIterator &it2) const
Checks whether the two iterators point to the same element.
Definition: HashSet_inl.h:39
ezUInt32 GetCount() const
Returns the number of active entries in the table.
Definition: HashSet_inl.h:239
Const iterator.
Definition: HashSet.h:23
bool IsValid() const
Checks whether this iterator points to a valid element.
Definition: HashSet_inl.h:33
ConstIterator GetIterator() const
Returns a constant Iterator to the very first element.
Definition: HashSet_inl.h:355
void operator++()
Shorthand for &#39;Next&#39;.
Definition: HashSet_inl.h:73
bool operator!=(const typename ezHashSetBase< KeyType, Hasher >::ConstIterator &it2) const
Checks whether the two iterators point to the same element.
Definition: HashSet_inl.h:45
EZ_ALWAYS_INLINE const KeyType & operator*()
Returns the &#39;key&#39; of the element that this iterator points to.
Definition: HashSet.h:39
Definition: HashSet.h:167
Implementation of a hashset.
Definition: HashSet.h:19
void Compact()
Tries to compact the hashset to avoid wasting memory.
Definition: HashSet_inl.h:221
bool operator==(const ezHashSetBase< KeyType, Hasher > &rhs) const
Compares this table to another table.
Definition: HashSet_inl.h:183
const KeyType & Key() const
Returns the &#39;key&#39; of the element that this iterator points to.
Definition: HashSet_inl.h:51
bool Insert(CompatibleKeyType &&key)
Inserts the key. Returns whether the key was already existing.
Definition: HashSet_inl.h:267
ezAllocatorBase * GetAllocator() const
Returns the allocator that is used by this instance.
Definition: HashSet_inl.h:371
bool operator!=(const ezHashSetBase< KeyType, Hasher > &rhs) const
Compares this table to another table.
Definition: HashSet_inl.h:204
void operator=(const ezHashSetBase< KeyType, Hasher > &rhs)
Copies the data from another hashset into this one.
Definition: HashSet_inl.h:125
ezHashSetBase(ezAllocatorBase *pAllocator)
Creates an empty hashset. Does not allocate any data yet.
Definition: HashSet_inl.h:82
ConstIterator GetEndIterator() const
Returns a constant Iterator to the first element that is not part of the hashset. Needed to implement...
Definition: HashSet_inl.h:363
void Next()
Advances the iterator to the next element in the map. The iterator will not be valid anymore...
Definition: HashSet_inl.h:57
ezUInt64 GetHeapMemoryUsage() const
Returns the amount of bytes that are currently allocated on the heap.
Definition: HashSet_inl.h:377
void Swap(ezHashSetBase< KeyType, Hasher > &other)
Swaps this map with the other one.
Definition: HashSet_inl.h:571
bool Remove(const KeyType &key)
Removes the entry with the given key. Returns if an entry was removed.
Definition: HashSet_inl.h:306
~ezHashSetBase()
Destructor.
Definition: HashSet_inl.h:116
bool IsEmpty() const
Returns true, if the hashset does not contain any elements.
Definition: HashSet_inl.h:245
void Clear()
Clears the table.
Definition: HashSet_inl.h:251