ezEngine  Milestone 9
HashSet_inl.h
1 
2 #define ezInvalidIndex 0xFFFFFFFF
3 
4 // ***** Const Iterator *****
5 
6 template <typename K, typename H>
7 ezHashSetBase<K, H>::ConstIterator::ConstIterator(const ezHashSetBase<K, H>& hashSet) : m_hashSet(hashSet), m_uiCurrentIndex(0), m_uiCurrentCount(0)
8 {
9 }
10 
11 template <typename K, typename H>
13 {
14  if (m_hashSet.IsEmpty())
15  {
16  m_uiCurrentIndex = m_hashSet.m_uiCapacity;
17  return;
18  }
19  while (!m_hashSet.IsValidEntry(m_uiCurrentIndex))
20  {
21  ++m_uiCurrentIndex;
22  }
23 }
24 
25 template <typename K, typename H>
27 {
28  m_uiCurrentCount = m_hashSet.m_uiCount;
29  m_uiCurrentIndex = m_hashSet.m_uiCapacity;
30 }
31 
32 template <typename K, typename H>
33 EZ_ALWAYS_INLINE bool ezHashSetBase<K, H>::ConstIterator::IsValid() const
34 {
35  return m_uiCurrentCount < m_hashSet.m_uiCount;
36 }
37 
38 template <typename K, typename H>
40 {
41  return m_hashSet.m_pEntries == it2.m_hashSet.m_pEntries && m_uiCurrentIndex == it2.m_uiCurrentIndex;
42 }
43 
44 template <typename K, typename H>
46 {
47  return !(*this == it2);
48 }
49 
50 template <typename K, typename H>
51 EZ_FORCE_INLINE const K& ezHashSetBase<K, H>::ConstIterator::Key() const
52 {
53  return m_hashSet.m_pEntries[m_uiCurrentIndex];
54 }
55 
56 template <typename K, typename H>
58 {
59  ++m_uiCurrentCount;
60  if (m_uiCurrentCount == m_hashSet.m_uiCount)
61  {
62  m_uiCurrentIndex = m_hashSet.m_uiCapacity;
63  return;
64  }
65 
66  do
67  {
68  ++m_uiCurrentIndex;
69  } while (!m_hashSet.IsValidEntry(m_uiCurrentIndex));
70 }
71 
72 template <typename K, typename H>
74 {
75  Next();
76 }
77 
78 
79 // ***** ezHashSetBase *****
80 
81 template <typename K, typename H>
83 {
84  m_pEntries = nullptr;
85  m_pEntryFlags = nullptr;
86  m_uiCount = 0;
87  m_uiCapacity = 0;
88  m_pAllocator = pAllocator;
89 }
90 
91 template <typename K, typename H>
93 {
94  m_pEntries = nullptr;
95  m_pEntryFlags = nullptr;
96  m_uiCount = 0;
97  m_uiCapacity = 0;
98  m_pAllocator = pAllocator;
99 
100  *this = other;
101 }
102 
103 template <typename K, typename H>
105 {
106  m_pEntries = nullptr;
107  m_pEntryFlags = nullptr;
108  m_uiCount = 0;
109  m_uiCapacity = 0;
110  m_pAllocator = pAllocator;
111 
112  *this = std::move(other);
113 }
114 
115 template <typename K, typename H>
117 {
118  Clear();
119  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntries);
120  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntryFlags);
121  m_uiCapacity = 0;
122 }
123 
124 template <typename K, typename H>
126 {
127  Clear();
128  Reserve(rhs.GetCount());
129 
130  ezUInt32 uiCopied = 0;
131  for (ezUInt32 i = 0; uiCopied < rhs.GetCount(); ++i)
132  {
133  if (rhs.IsValidEntry(i))
134  {
135  Insert(rhs.m_pEntries[i]);
136  ++uiCopied;
137  }
138  }
139 }
140 
141 template <typename K, typename H>
143 {
144  // Clear any existing data (calls destructors if necessary)
145  Clear();
146 
147  if (m_pAllocator != rhs.m_pAllocator)
148  {
149  Reserve(rhs.m_uiCapacity);
150 
151  ezUInt32 uiCopied = 0;
152  for (ezUInt32 i = 0; uiCopied < rhs.GetCount(); ++i)
153  {
154  if (rhs.IsValidEntry(i))
155  {
156  Insert(std::move(rhs.m_pEntries[i]));
157  ++uiCopied;
158  }
159  }
160 
161  rhs.Clear();
162  }
163  else
164  {
165  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntries);
166  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntryFlags);
167 
168  // Move all data over.
169  m_pEntries = rhs.m_pEntries;
170  m_pEntryFlags = rhs.m_pEntryFlags;
171  m_uiCount = rhs.m_uiCount;
172  m_uiCapacity = rhs.m_uiCapacity;
173 
174  // Temp copy forgets all its state.
175  rhs.m_pEntries = nullptr;
176  rhs.m_pEntryFlags = nullptr;
177  rhs.m_uiCount = 0;
178  rhs.m_uiCapacity = 0;
179  }
180 }
181 
182 template <typename K, typename H>
184 {
185  if (m_uiCount != rhs.m_uiCount)
186  return false;
187 
188  ezUInt32 uiCompared = 0;
189  for (ezUInt32 i = 0; uiCompared < m_uiCount; ++i)
190  {
191  if (IsValidEntry(i))
192  {
193  if (!rhs.Contains(m_pEntries[i]))
194  return false;
195 
196  ++uiCompared;
197  }
198  }
199 
200  return true;
201 }
202 
203 template <typename K, typename H>
204 EZ_ALWAYS_INLINE bool ezHashSetBase<K, H>::operator!=(const ezHashSetBase<K, H>& rhs) const
205 {
206  return !(*this == rhs);
207 }
208 
209 template <typename K, typename H>
210 void ezHashSetBase<K, H>::Reserve(ezUInt32 uiCapacity)
211 {
212  ezUInt32 uiNewCapacity = uiCapacity + (uiCapacity / 3) * 2; // ensure a maximum load of 60%
213  if (m_uiCapacity >= uiNewCapacity)
214  return;
215 
216  uiNewCapacity = ezMath::Max<ezUInt32>(ezMath::PowerOfTwo_Ceil(uiNewCapacity), CAPACITY_ALIGNMENT);
217  SetCapacity(uiNewCapacity);
218 }
219 
220 template <typename K, typename H>
222 {
223  if (IsEmpty())
224  {
225  // completely deallocate all data, if the table is empty.
226  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntries);
227  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntryFlags);
228  m_uiCapacity = 0;
229  }
230  else
231  {
232  const ezUInt32 uiNewCapacity = (m_uiCount + (CAPACITY_ALIGNMENT - 1)) & ~(CAPACITY_ALIGNMENT - 1);
233  if (m_uiCapacity != uiNewCapacity)
234  SetCapacity(uiNewCapacity);
235  }
236 }
237 
238 template <typename K, typename H>
239 EZ_ALWAYS_INLINE ezUInt32 ezHashSetBase<K, H>::GetCount() const
240 {
241  return m_uiCount;
242 }
243 
244 template <typename K, typename H>
245 EZ_ALWAYS_INLINE bool ezHashSetBase<K, H>::IsEmpty() const
246 {
247  return m_uiCount == 0;
248 }
249 
250 template <typename K, typename H>
252 {
253  for (ezUInt32 i = 0; i < m_uiCapacity; ++i)
254  {
255  if (IsValidEntry(i))
256  {
257  ezMemoryUtils::Destruct(&m_pEntries[i], 1);
258  }
259  }
260 
261  ezMemoryUtils::ZeroFill(m_pEntryFlags, GetFlagsCapacity());
262  m_uiCount = 0;
263 }
264 
265 template <typename K, typename H>
266 template <typename CompatibleKeyType>
267 bool ezHashSetBase<K, H>::Insert(CompatibleKeyType&& key)
268 {
269  Reserve(m_uiCount + 1);
270 
271  ezUInt32 uiIndex = H::Hash(key) % m_uiCapacity;
272  ezUInt32 uiDeletedIndex = ezInvalidIndex;
273 
274  ezUInt32 uiCounter = 0;
275  while (!IsFreeEntry(uiIndex) && uiCounter < m_uiCapacity)
276  {
277  if (IsDeletedEntry(uiIndex))
278  {
279  if (uiDeletedIndex == ezInvalidIndex)
280  uiDeletedIndex = uiIndex;
281  }
282  else if (H::Equal(m_pEntries[uiIndex], key))
283  {
284  return true;
285  }
286  ++uiIndex;
287  if (uiIndex == m_uiCapacity)
288  uiIndex = 0;
289 
290  ++uiCounter;
291  }
292 
293  // new entry
294  uiIndex = uiDeletedIndex != ezInvalidIndex ? uiDeletedIndex : uiIndex;
295 
296  // Constructions might either be a move or a copy.
297  ezMemoryUtils::CopyOrMoveConstruct(&m_pEntries[uiIndex], std::forward<CompatibleKeyType>(key));
298 
299  MarkEntryAsValid(uiIndex);
300  ++m_uiCount;
301 
302  return false;
303 }
304 
305 template <typename K, typename H>
306 bool ezHashSetBase<K, H>::Remove(const K& key)
307 {
308  ezUInt32 uiIndex = FindEntry(key);
309  if (uiIndex != ezInvalidIndex)
310  {
311  ezMemoryUtils::Destruct(&m_pEntries[uiIndex], 1);
312 
313  ezUInt32 uiNextIndex = uiIndex + 1;
314  if (uiNextIndex == m_uiCapacity)
315  uiNextIndex = 0;
316 
317  // if the next entry is free we are at the end of a chain and
318  // can immediately mark this entry as free as well
319  if (IsFreeEntry(uiNextIndex))
320  {
321  MarkEntryAsFree(uiIndex);
322 
323  // run backwards and free all deleted entries in this chain
324  ezUInt32 uiPrevIndex = (uiIndex != 0) ? uiIndex : m_uiCapacity;
325  --uiPrevIndex;
326 
327  while (IsDeletedEntry(uiPrevIndex))
328  {
329  MarkEntryAsFree(uiPrevIndex);
330 
331  if (uiPrevIndex == 0)
332  uiPrevIndex = m_uiCapacity;
333  --uiPrevIndex;
334  }
335  }
336  else
337  {
338  MarkEntryAsDeleted(uiIndex);
339  }
340 
341  --m_uiCount;
342  return true;
343  }
344 
345  return false;
346 }
347 
348 template <typename K, typename H>
349 EZ_FORCE_INLINE bool ezHashSetBase<K, H>::Contains(const K& key) const
350 {
351  return FindEntry(key) != ezInvalidIndex;
352 }
353 
354 template <typename K, typename H>
356 {
357  ConstIterator iterator(*this);
358  iterator.SetToBegin();
359  return iterator;
360 }
361 
362 template <typename K, typename H>
364 {
365  ConstIterator iterator(*this);
366  iterator.SetToEnd();
367  return iterator;
368 }
369 
370 template <typename K, typename H>
372 {
373  return m_pAllocator;
374 }
375 
376 template <typename K, typename H>
378 {
379  return ((ezUInt64)m_uiCapacity * sizeof(K)) + (sizeof(ezUInt32) * (ezUInt64)GetFlagsCapacity());
380 }
381 
382 // private methods
383 template <typename K, typename H>
384 void ezHashSetBase<K, H>::SetCapacity(ezUInt32 uiCapacity)
385 {
386  const ezUInt32 uiOldCapacity = m_uiCapacity;
387  m_uiCapacity = uiCapacity;
388 
389  K* pOldEntries = m_pEntries;
390  ezUInt32* pOldEntryFlags = m_pEntryFlags;
391 
392  m_pEntries = EZ_NEW_RAW_BUFFER(m_pAllocator, K, m_uiCapacity);
393  m_pEntryFlags = EZ_NEW_RAW_BUFFER(m_pAllocator, ezUInt32, GetFlagsCapacity());
394  ezMemoryUtils::ZeroFill(m_pEntryFlags, GetFlagsCapacity());
395 
396  m_uiCount = 0;
397  for (ezUInt32 i = 0; i < uiOldCapacity; ++i)
398  {
399  if (GetFlags(pOldEntryFlags, i) == VALID_ENTRY)
400  {
401  EZ_VERIFY(!Insert(std::move(pOldEntries[i])), "Implementation error");
402 
403  ezMemoryUtils::Destruct(&pOldEntries[i], 1);
404  }
405  }
406 
407  EZ_DELETE_RAW_BUFFER(m_pAllocator, pOldEntries);
408  EZ_DELETE_RAW_BUFFER(m_pAllocator, pOldEntryFlags);
409 }
410 
411 template <typename K, typename H>
412 EZ_FORCE_INLINE ezUInt32 ezHashSetBase<K, H>::FindEntry(const K& key) const
413 {
414  return FindEntry(H::Hash(key), key);
415 }
416 
417 template <typename K, typename H>
418 inline ezUInt32 ezHashSetBase<K, H>::FindEntry(ezUInt32 uiHash, const K& key) const
419 {
420  if (m_uiCapacity > 0)
421  {
422  ezUInt32 uiIndex = uiHash % m_uiCapacity;
423  ezUInt32 uiCounter = 0;
424  while (!IsFreeEntry(uiIndex) && uiCounter < m_uiCapacity)
425  {
426  if (IsValidEntry(uiIndex) && H::Equal(m_pEntries[uiIndex], key))
427  return uiIndex;
428 
429  ++uiIndex;
430  if (uiIndex == m_uiCapacity)
431  uiIndex = 0;
432 
433  ++uiCounter;
434  }
435  }
436  // not found
437  return ezInvalidIndex;
438 }
439 
440 #define EZ_HASHSET_USE_BITFLAGS EZ_ON
441 
442 template <typename K, typename H>
443 EZ_FORCE_INLINE ezUInt32 ezHashSetBase<K, H>::GetFlagsCapacity() const
444 {
445 #if EZ_ENABLED(EZ_HASHSET_USE_BITFLAGS)
446  return (m_uiCapacity + 15) / 16;
447 #else
448  return m_uiCapacity;
449 #endif
450 }
451 
452 template <typename K, typename H>
453 ezUInt32 ezHashSetBase<K, H>::GetFlags(ezUInt32* pFlags, ezUInt32 uiEntryIndex) const
454 {
455 #if EZ_ENABLED(EZ_HASHSET_USE_BITFLAGS)
456  const ezUInt32 uiIndex = uiEntryIndex / 16;
457  const ezUInt32 uiSubIndex = (uiEntryIndex & 15) * 2;
458  return (pFlags[uiIndex] >> uiSubIndex) & FLAGS_MASK;
459 #else
460  return pFlags[uiEntryIndex] & FLAGS_MASK;
461 #endif
462 }
463 
464 template <typename K, typename H>
465 void ezHashSetBase<K, H>::SetFlags(ezUInt32 uiEntryIndex, ezUInt32 uiFlags)
466 {
467 #if EZ_ENABLED(EZ_HASHSET_USE_BITFLAGS)
468  const ezUInt32 uiIndex = uiEntryIndex / 16;
469  const ezUInt32 uiSubIndex = (uiEntryIndex & 15) * 2;
470  EZ_ASSERT_DEV(uiIndex < GetFlagsCapacity(), "Out of bounds access");
471  m_pEntryFlags[uiIndex] &= ~(FLAGS_MASK << uiSubIndex);
472  m_pEntryFlags[uiIndex] |= (uiFlags << uiSubIndex);
473 #else
474  EZ_ASSERT_DEV(uiEntryIndex < GetFlagsCapacity(), "Out of bounds access");
475  m_pEntryFlags[uiEntryIndex] = uiFlags;
476 #endif
477 }
478 
479 template <typename K, typename H>
480 EZ_FORCE_INLINE bool ezHashSetBase<K, H>::IsFreeEntry(ezUInt32 uiEntryIndex) const
481 {
482  return GetFlags(m_pEntryFlags, uiEntryIndex) == FREE_ENTRY;
483 }
484 
485 template <typename K, typename H>
486 EZ_FORCE_INLINE bool ezHashSetBase<K, H>::IsValidEntry(ezUInt32 uiEntryIndex) const
487 {
488  return GetFlags(m_pEntryFlags, uiEntryIndex) == VALID_ENTRY;
489 }
490 
491 template <typename K, typename H>
492 EZ_FORCE_INLINE bool ezHashSetBase<K, H>::IsDeletedEntry(ezUInt32 uiEntryIndex) const
493 {
494  return GetFlags(m_pEntryFlags, uiEntryIndex) == DELETED_ENTRY;
495 }
496 
497 template <typename K, typename H>
498 EZ_FORCE_INLINE void ezHashSetBase<K, H>::MarkEntryAsFree(ezUInt32 uiEntryIndex)
499 {
500  SetFlags(uiEntryIndex, FREE_ENTRY);
501 }
502 
503 template <typename K, typename H>
504 EZ_FORCE_INLINE void ezHashSetBase<K, H>::MarkEntryAsValid(ezUInt32 uiEntryIndex)
505 {
506  SetFlags(uiEntryIndex, VALID_ENTRY);
507 }
508 
509 template <typename K, typename H>
510 EZ_FORCE_INLINE void ezHashSetBase<K, H>::MarkEntryAsDeleted(ezUInt32 uiEntryIndex)
511 {
512  SetFlags(uiEntryIndex, DELETED_ENTRY);
513 }
514 
515 
516 template <typename K, typename H, typename A>
518 {
519 }
520 
521 template <typename K, typename H, typename A>
522 ezHashSet<K, H, A>::ezHashSet(ezAllocatorBase* pAllocator) : ezHashSetBase<K, H>(pAllocator)
523 {
524 }
525 
526 template <typename K, typename H, typename A>
527 ezHashSet<K, H, A>::ezHashSet(const ezHashSet<K, H, A>& other) : ezHashSetBase<K, H>(other, A::GetAllocator())
528 {
529 }
530 
531 template <typename K, typename H, typename A>
532 ezHashSet<K, H, A>::ezHashSet(const ezHashSetBase<K, H>& other) : ezHashSetBase<K, H>(other, A::GetAllocator())
533 {
534 }
535 
536 template <typename K, typename H, typename A>
537 ezHashSet<K, H, A>::ezHashSet(ezHashSet<K, H, A>&& other) : ezHashSetBase<K, H>(std::move(other), A::GetAllocator())
538 {
539 }
540 
541 template <typename K, typename H, typename A>
542 ezHashSet<K, H, A>::ezHashSet(ezHashSetBase<K, H>&& other) : ezHashSetBase<K, H>(std::move(other), A::GetAllocator())
543 {
544 }
545 
546 template <typename K, typename H, typename A>
548 {
550 }
551 
552 template <typename K, typename H, typename A>
554 {
556 }
557 
558 template <typename K, typename H, typename A>
560 {
561  ezHashSetBase<K, H>::operator=(std::move(rhs));
562 }
563 
564 template <typename K, typename H, typename A>
566 {
567  ezHashSetBase<K, H>::operator=(std::move(rhs));
568 }
569 
570 template <typename KeyType, typename Hasher>
572 {
573  ezMath::Swap(this->m_pEntries, other.m_pEntries);
574  ezMath::Swap(this->m_pEntryFlags, other.m_pEntryFlags);
575  ezMath::Swap(this->m_uiCount, other.m_uiCount);
576  ezMath::Swap(this->m_uiCapacity, other.m_uiCapacity);
577  ezMath::Swap(this->m_pAllocator, other.m_pAllocator);
578 }
579 
EZ_ALWAYS_INLINE void Swap(T &f1, T &f2)
Swaps the values in the two variables f1 and f2.
Definition: Math_inl.h:112
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
Definition: HashSet.h:167
#define EZ_ASSERT_DEV(bCondition, szErrorMsg,...)
Macro to raise an error, if a condition is not met.
Definition: Assert.h:116
Implementation of a hashset.
Definition: HashSet.h:19
void Compact()
Tries to compact the hashset to avoid wasting memory.
Definition: HashSet_inl.h:221
static void Destruct(T *pDestination, size_t uiCount)
Destructs uiCount objects of type T at pDestination.
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
EZ_FOUNDATION_DLL ezUInt32 PowerOfTwo_Ceil(ezUInt32 value)
Returns the next power-of-two that is >= value.
Definition: Math.cpp:46
#define EZ_VERIFY(bCondition, szErrorMsg,...)
Macro to raise an error, if a condition is not met.
Definition: Assert.h:123
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
#define EZ_NEW_RAW_BUFFER(allocator, type, count)
creates a raw buffer of type using the given allocator with count elements, but does NOT call the def...
Definition: AllocatorBase.h:77
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
#define EZ_DELETE_RAW_BUFFER(allocator, ptr)
deletes a raw buffer stored in ptr using the given allocator, but does NOT call destructor ...
Definition: AllocatorBase.h:80
void Swap(ezHashSetBase< KeyType, Hasher > &other)
Swaps this map with the other one.
Definition: HashSet_inl.h:571
static void ZeroFill(T *pDestination, size_t uiCount)
Zeros out buffer of a raw memory.
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
static void CopyOrMoveConstruct(Destination *pDestination, Source &&source)
This function will either move call MoveConstruct or CopyConstruct for a single element source...
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