ezEngine  Milestone 9
HashTable_inl.h
1 
2 #define ezInvalidIndex 0xFFFFFFFF
3 
4 // ***** Const Iterator *****
5 
6 template <typename K, typename V, typename H>
7 ezHashTableBase<K, V, H>::ConstIterator::ConstIterator(const ezHashTableBase<K, V, H>& hashTable) : m_hashTable(&hashTable), m_uiCurrentIndex(0), m_uiCurrentCount(0)
8 {
9  if (m_hashTable->IsEmpty())
10  return;
11 
12  while (!m_hashTable->IsValidEntry(m_uiCurrentIndex))
13  {
14  ++m_uiCurrentIndex;
15  }
16 }
17 
18 template <typename K, typename V, typename H>
20 {
21  return m_uiCurrentCount < m_hashTable->m_uiCount;
22 }
23 
24 template <typename K, typename V, typename H>
26 {
27  return m_hashTable->m_pEntries == it2.m_hashTable->m_pEntries && m_uiCurrentIndex == it2.m_uiCurrentIndex;
28 }
29 
30 template <typename K, typename V, typename H>
32 {
33  return !(*this == it2);
34 }
35 
36 template <typename K, typename V, typename H>
37 EZ_ALWAYS_INLINE const K& ezHashTableBase<K, V, H>::ConstIterator::Key() const
38 {
39  return m_hashTable->m_pEntries[m_uiCurrentIndex].key;
40 }
41 
42 template <typename K, typename V, typename H>
43 EZ_ALWAYS_INLINE const V& ezHashTableBase<K, V, H>::ConstIterator::Value() const
44 {
45  return m_hashTable->m_pEntries[m_uiCurrentIndex].value;
46 }
47 
48 template <typename K, typename V, typename H>
50 {
51  ++m_uiCurrentCount;
52  if (m_uiCurrentCount == m_hashTable->m_uiCount)
53  return;
54 
55  do
56  {
57  ++m_uiCurrentIndex;
58  } while (!m_hashTable->IsValidEntry(m_uiCurrentIndex));
59 }
60 
61 template <typename K, typename V, typename H>
63 {
64  Next();
65 }
66 
67 
68 // ***** Iterator *****
69 
70 template <typename K, typename V, typename H>
72  : ConstIterator(hashTable)
73 {
74 }
75 
76 template <typename K, typename V, typename H>
78  : ConstIterator(*rhs.m_hashTable)
79 {
80  this->m_uiCurrentIndex = rhs.m_uiCurrentIndex;
81  this->m_uiCurrentCount = rhs.m_uiCurrentCount;
82 }
83 
84 template <typename K, typename V, typename H>
85 EZ_ALWAYS_INLINE void ezHashTableBase<K, V, H>::Iterator::operator=(const Iterator& rhs) // [tested]
86 {
87  this->m_hashTable = rhs.m_hashTable;
88  this->m_uiCurrentIndex = rhs.m_uiCurrentIndex;
89  this->m_uiCurrentCount = rhs.m_uiCurrentCount;
90 }
91 
92 template <typename K, typename V, typename H>
94 {
95  return this->m_hashTable->m_pEntries[this->m_uiCurrentIndex].value;
96 }
97 
98 
99 // ***** ezHashTableBase *****
100 
101 template <typename K, typename V, typename H>
103 {
104  m_pEntries = nullptr;
105  m_pEntryFlags = nullptr;
106  m_uiCount = 0;
107  m_uiCapacity = 0;
108  m_pAllocator = pAllocator;
109 }
110 
111 template <typename K, typename V, typename H>
113 {
114  m_pEntries = nullptr;
115  m_pEntryFlags = nullptr;
116  m_uiCount = 0;
117  m_uiCapacity = 0;
118  m_pAllocator = pAllocator;
119 
120  *this = other;
121 }
122 
123 template <typename K, typename V, typename H>
125 {
126  m_pEntries = nullptr;
127  m_pEntryFlags = nullptr;
128  m_uiCount = 0;
129  m_uiCapacity = 0;
130  m_pAllocator = pAllocator;
131 
132  *this = std::move(other);
133 }
134 
135 template <typename K, typename V, typename H>
137 {
138  Clear();
139  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntries);
140  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntryFlags);
141  m_uiCapacity = 0;
142 }
143 
144 template <typename K, typename V, typename H>
146 {
147  Clear();
148  Reserve(rhs.GetCount());
149 
150  ezUInt32 uiCopied = 0;
151  for (ezUInt32 i = 0; uiCopied < rhs.GetCount(); ++i)
152  {
153  if (rhs.IsValidEntry(i))
154  {
155  Insert(rhs.m_pEntries[i].key, rhs.m_pEntries[i].value);
156  ++uiCopied;
157  }
158  }
159 }
160 
161 template <typename K, typename V, typename H>
163 {
164  // Clear any existing data (calls destructors if necessary)
165  Clear();
166 
167  if (m_pAllocator != rhs.m_pAllocator)
168  {
169  Reserve(rhs.m_uiCapacity);
170 
171  ezUInt32 uiCopied = 0;
172  for (ezUInt32 i = 0; uiCopied < rhs.GetCount(); ++i)
173  {
174  if (rhs.IsValidEntry(i))
175  {
176  Insert(std::move(rhs.m_pEntries[i].key), std::move(rhs.m_pEntries[i].value));
177  ++uiCopied;
178  }
179  }
180 
181  rhs.Clear();
182  }
183  else
184  {
185  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntries);
186  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntryFlags);
187 
188  // Move all data over.
189  m_pEntries = rhs.m_pEntries;
190  m_pEntryFlags = rhs.m_pEntryFlags;
191  m_uiCount = rhs.m_uiCount;
192  m_uiCapacity = rhs.m_uiCapacity;
193 
194  // Temp copy forgets all its state.
195  rhs.m_pEntries = nullptr;
196  rhs.m_pEntryFlags = nullptr;
197  rhs.m_uiCount = 0;
198  rhs.m_uiCapacity = 0;
199  }
200 }
201 
202 template <typename K, typename V, typename H>
204 {
205  if (m_uiCount != rhs.m_uiCount)
206  return false;
207 
208  ezUInt32 uiCompared = 0;
209  for (ezUInt32 i = 0; uiCompared < m_uiCount; ++i)
210  {
211  if (IsValidEntry(i))
212  {
213  const V* pRhsValue = nullptr;
214  if (!rhs.TryGetValue(m_pEntries[i].key, pRhsValue))
215  return false;
216 
217  if (m_pEntries[i].value != *pRhsValue)
218  return false;
219 
220  ++uiCompared;
221  }
222  }
223 
224  return true;
225 }
226 
227 template <typename K, typename V, typename H>
228 EZ_ALWAYS_INLINE bool ezHashTableBase<K, V, H>::operator!=(const ezHashTableBase<K, V, H>& rhs) const
229 {
230  return !(*this == rhs);
231 }
232 
233 template <typename K, typename V, typename H>
234 void ezHashTableBase<K, V, H>::Reserve(ezUInt32 uiCapacity)
235 {
236  ezUInt32 uiNewCapacity = uiCapacity + (uiCapacity / 3) * 2; // ensure a maximum load of 60%
237  if (m_uiCapacity >= uiNewCapacity)
238  return;
239 
240  uiNewCapacity = ezMath::Max<ezUInt32>(ezMath::PowerOfTwo_Ceil(uiNewCapacity), CAPACITY_ALIGNMENT);
241  SetCapacity(uiNewCapacity);
242 }
243 
244 template <typename K, typename V, typename H>
246 {
247  if (IsEmpty())
248  {
249  // completely deallocate all data, if the table is empty.
250  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntries);
251  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntryFlags);
252  m_uiCapacity = 0;
253  }
254  else
255  {
256  const ezUInt32 uiNewCapacity = (m_uiCount + (CAPACITY_ALIGNMENT - 1)) & ~(CAPACITY_ALIGNMENT - 1);
257  if (m_uiCapacity != uiNewCapacity)
258  SetCapacity(uiNewCapacity);
259  }
260 }
261 
262 template <typename K, typename V, typename H>
263 EZ_ALWAYS_INLINE ezUInt32 ezHashTableBase<K, V, H>::GetCount() const
264 {
265  return m_uiCount;
266 }
267 
268 template <typename K, typename V, typename H>
269 EZ_ALWAYS_INLINE bool ezHashTableBase<K, V, H>::IsEmpty() const
270 {
271  return m_uiCount == 0;
272 }
273 
274 template <typename K, typename V, typename H>
276 {
277  for (ezUInt32 i = 0; i < m_uiCapacity; ++i)
278  {
279  if (IsValidEntry(i))
280  {
281  ezMemoryUtils::Destruct(&m_pEntries[i].key, 1);
282  ezMemoryUtils::Destruct(&m_pEntries[i].value, 1);
283  }
284  }
285 
286  ezMemoryUtils::ZeroFill(m_pEntryFlags, GetFlagsCapacity());
287  m_uiCount = 0;
288 }
289 
290 template <typename K, typename V, typename H>
291 template <typename CompatibleKeyType, typename CompatibleValueType>
292 bool ezHashTableBase<K, V, H>::Insert(CompatibleKeyType&& key, CompatibleValueType&& value, V* out_oldValue /*= nullptr*/)
293 {
294  Reserve(m_uiCount + 1);
295 
296  ezUInt32 uiIndex = H::Hash(key) % m_uiCapacity;
297  ezUInt32 uiDeletedIndex = ezInvalidIndex;
298 
299  ezUInt32 uiCounter = 0;
300  while (!IsFreeEntry(uiIndex) && uiCounter < m_uiCapacity)
301  {
302  if (IsDeletedEntry(uiIndex))
303  {
304  if (uiDeletedIndex == ezInvalidIndex)
305  uiDeletedIndex = uiIndex;
306  }
307  else if (H::Equal(m_pEntries[uiIndex].key, key))
308  {
309  if (out_oldValue != nullptr)
310  *out_oldValue = std::move(m_pEntries[uiIndex].value);
311 
312  m_pEntries[uiIndex].value = std::forward<CompatibleValueType>(value); // Either move or copy assignment.
313  return true;
314  }
315  ++uiIndex;
316  if (uiIndex == m_uiCapacity)
317  uiIndex = 0;
318 
319  ++uiCounter;
320  }
321 
322  // new entry
323  uiIndex = uiDeletedIndex != ezInvalidIndex ? uiDeletedIndex : uiIndex;
324 
325  // Both constructions might either be a move or a copy.
326  ezMemoryUtils::CopyOrMoveConstruct(&m_pEntries[uiIndex].key, std::forward<CompatibleKeyType>(key));
327  ezMemoryUtils::CopyOrMoveConstruct(&m_pEntries[uiIndex].value, std::forward<CompatibleValueType>(value));
328 
329  MarkEntryAsValid(uiIndex);
330  ++m_uiCount;
331 
332  return false;
333 }
334 
335 template <typename K, typename V, typename H>
336 template <typename CompatibleKeyType>
337 bool ezHashTableBase<K, V, H>::Remove(const CompatibleKeyType& key, V* out_oldValue /*= nullptr*/)
338 {
339  ezUInt32 uiIndex = FindEntry(key);
340  if (uiIndex != ezInvalidIndex)
341  {
342  if (out_oldValue != nullptr)
343  *out_oldValue = std::move(m_pEntries[uiIndex].value);
344 
345  RemoveInternal(uiIndex);
346  return true;
347  }
348 
349  return false;
350 }
351 
352 template <typename K, typename V, typename H>
354 {
355  Iterator it = pos;
356  ezUInt32 uiIndex = pos.m_uiCurrentIndex;
357  ++it;
358  --it.m_uiCurrentCount;
359  RemoveInternal(uiIndex);
360  return it;
361 }
362 
363 template <typename K, typename V, typename H>
364 void ezHashTableBase<K, V, H>::RemoveInternal(ezUInt32 uiIndex)
365 {
366  ezMemoryUtils::Destruct(&m_pEntries[uiIndex].key, 1);
367  ezMemoryUtils::Destruct(&m_pEntries[uiIndex].value, 1);
368 
369  ezUInt32 uiNextIndex = uiIndex + 1;
370  if (uiNextIndex == m_uiCapacity)
371  uiNextIndex = 0;
372 
373  // if the next entry is free we are at the end of a chain and
374  // can immediately mark this entry as free as well
375  if (IsFreeEntry(uiNextIndex))
376  {
377  MarkEntryAsFree(uiIndex);
378 
379  // run backwards and free all deleted entries in this chain
380  ezUInt32 uiPrevIndex = (uiIndex != 0) ? uiIndex : m_uiCapacity;
381  --uiPrevIndex;
382 
383  while (IsDeletedEntry(uiPrevIndex))
384  {
385  MarkEntryAsFree(uiPrevIndex);
386 
387  if (uiPrevIndex == 0)
388  uiPrevIndex = m_uiCapacity;
389  --uiPrevIndex;
390  }
391  }
392  else
393  {
394  MarkEntryAsDeleted(uiIndex);
395  }
396 
397  --m_uiCount;
398 }
399 
400 template <typename K, typename V, typename H>
401 template <typename CompatibleKeyType>
402 inline bool ezHashTableBase<K, V, H>::TryGetValue(const CompatibleKeyType& key, V& out_value) const
403 {
404  ezUInt32 uiIndex = FindEntry(key);
405  if (uiIndex != ezInvalidIndex)
406  {
407  out_value = m_pEntries[uiIndex].value;
408  return true;
409  }
410 
411  return false;
412 }
413 
414 template <typename K, typename V, typename H>
415 template <typename CompatibleKeyType>
416 inline bool ezHashTableBase<K, V, H>::TryGetValue(const CompatibleKeyType& key, const V*& out_pValue) const
417 {
418  ezUInt32 uiIndex = FindEntry(key);
419  if (uiIndex != ezInvalidIndex)
420  {
421  out_pValue = &m_pEntries[uiIndex].value;
422  return true;
423  }
424 
425  return false;
426 }
427 
428 template <typename K, typename V, typename H>
429 template <typename CompatibleKeyType>
430 inline bool ezHashTableBase<K, V, H>::TryGetValue(const CompatibleKeyType& key, V*& out_pValue)
431 {
432  ezUInt32 uiIndex = FindEntry(key);
433  if (uiIndex != ezInvalidIndex)
434  {
435  out_pValue = &m_pEntries[uiIndex].value;
436  return true;
437  }
438 
439  return false;
440 }
441 
442 template <typename K, typename V, typename H>
443 template <typename CompatibleKeyType>
444 inline const V* ezHashTableBase<K, V, H>::GetValue(const CompatibleKeyType& key) const
445 {
446  ezUInt32 uiIndex = FindEntry(key);
447  return (uiIndex != ezInvalidIndex) ? &m_pEntries[uiIndex].value : nullptr;
448 }
449 
450 template <typename K, typename V, typename H>
451 template <typename CompatibleKeyType>
452 inline V* ezHashTableBase<K, V, H>::GetValue(const CompatibleKeyType& key)
453 {
454  ezUInt32 uiIndex = FindEntry(key);
455  return (uiIndex != ezInvalidIndex) ? &m_pEntries[uiIndex].value : nullptr;
456 }
457 
458 template <typename K, typename V, typename H>
460 {
461  const ezUInt32 uiHash = H::Hash(key);
462  ezUInt32 uiIndex = FindEntry(uiHash, key);
463 
464  if (uiIndex == ezInvalidIndex)
465  {
466  Reserve(m_uiCount + 1);
467 
468  // search for suitable insertion index again, table might have been resized
469  uiIndex = uiHash % m_uiCapacity;
470  while (IsValidEntry(uiIndex))
471  {
472  ++uiIndex;
473  if (uiIndex == m_uiCapacity)
474  uiIndex = 0;
475  }
476 
477  // new entry
478  ezMemoryUtils::CopyConstruct(&m_pEntries[uiIndex].key, key, 1);
479  ezMemoryUtils::DefaultConstruct(&m_pEntries[uiIndex].value, 1);
480  MarkEntryAsValid(uiIndex);
481  ++m_uiCount;
482  }
483  return m_pEntries[uiIndex].value;
484 }
485 
486 template <typename K, typename V, typename H>
487 template <typename CompatibleKeyType>
488 EZ_FORCE_INLINE bool ezHashTableBase<K, V, H>::Contains(const CompatibleKeyType& key) const
489 {
490  return FindEntry(key) != ezInvalidIndex;
491 }
492 
493 template <typename K, typename V, typename H>
495 {
496  return Iterator(*this);
497 }
498 
499 template <typename K, typename V, typename H>
501 {
502  return ConstIterator(*this);
503 }
504 
505 template <typename K, typename V, typename H>
507 {
508  return m_pAllocator;
509 }
510 
511 template <typename K, typename V, typename H>
513 {
514  return ((ezUInt64)m_uiCapacity * sizeof(Entry)) + (sizeof(ezUInt32) * (ezUInt64)GetFlagsCapacity());
515 }
516 
517 // private methods
518 template <typename K, typename V, typename H>
519 void ezHashTableBase<K, V, H>::SetCapacity(ezUInt32 uiCapacity)
520 {
521  const ezUInt32 uiOldCapacity = m_uiCapacity;
522  m_uiCapacity = uiCapacity;
523 
524  Entry* pOldEntries = m_pEntries;
525  ezUInt32* pOldEntryFlags = m_pEntryFlags;
526 
527  m_pEntries = EZ_NEW_RAW_BUFFER(m_pAllocator, Entry, m_uiCapacity);
528  m_pEntryFlags = EZ_NEW_RAW_BUFFER(m_pAllocator, ezUInt32, GetFlagsCapacity());
529  ezMemoryUtils::ZeroFill(m_pEntryFlags, GetFlagsCapacity());
530 
531  m_uiCount = 0;
532  for (ezUInt32 i = 0; i < uiOldCapacity; ++i)
533  {
534  if (GetFlags(pOldEntryFlags, i) == VALID_ENTRY)
535  {
536  EZ_VERIFY(!Insert(std::move(pOldEntries[i].key), std::move(pOldEntries[i].value)), "Implementation error");
537 
538  ezMemoryUtils::Destruct(&pOldEntries[i].key, 1);
539  ezMemoryUtils::Destruct(&pOldEntries[i].value, 1);
540  }
541  }
542 
543  EZ_DELETE_RAW_BUFFER(m_pAllocator, pOldEntries);
544  EZ_DELETE_RAW_BUFFER(m_pAllocator, pOldEntryFlags);
545 }
546 
547 template <typename K, typename V, typename H>
548 template <typename CompatibleKeyType>
549 EZ_ALWAYS_INLINE ezUInt32 ezHashTableBase<K, V, H>::FindEntry(const CompatibleKeyType& key) const
550 {
551  return FindEntry(H::Hash(key), key);
552 }
553 
554 template <typename K, typename V, typename H>
555 template <typename CompatibleKeyType>
556 inline ezUInt32 ezHashTableBase<K, V, H>::FindEntry(ezUInt32 uiHash, const CompatibleKeyType& key) const
557 {
558  if (m_uiCapacity > 0)
559  {
560  ezUInt32 uiIndex = uiHash % m_uiCapacity;
561  ezUInt32 uiCounter = 0;
562  while (!IsFreeEntry(uiIndex) && uiCounter < m_uiCapacity)
563  {
564  if (IsValidEntry(uiIndex) && H::Equal(m_pEntries[uiIndex].key, key))
565  return uiIndex;
566 
567  ++uiIndex;
568  if (uiIndex == m_uiCapacity)
569  uiIndex = 0;
570 
571  ++uiCounter;
572  }
573  }
574  // not found
575  return ezInvalidIndex;
576 }
577 
578 #define EZ_HASHTABLE_USE_BITFLAGS EZ_ON
579 
580 template <typename K, typename V, typename H>
581 EZ_FORCE_INLINE ezUInt32 ezHashTableBase<K, V, H>::GetFlagsCapacity() const
582 {
583 #if EZ_ENABLED(EZ_HASHTABLE_USE_BITFLAGS)
584  return (m_uiCapacity + 15) / 16;
585 #else
586  return m_uiCapacity;
587 #endif
588 }
589 
590 template <typename K, typename V, typename H>
591 ezUInt32 ezHashTableBase<K, V, H>::GetFlags(ezUInt32* pFlags, ezUInt32 uiEntryIndex) const
592 {
593 #if EZ_ENABLED(EZ_HASHTABLE_USE_BITFLAGS)
594  const ezUInt32 uiIndex = uiEntryIndex / 16;
595  const ezUInt32 uiSubIndex = (uiEntryIndex & 15) * 2;
596  return (pFlags[uiIndex] >> uiSubIndex) & FLAGS_MASK;
597 #else
598  return pFlags[uiEntryIndex] & FLAGS_MASK;
599 #endif
600 }
601 
602 template <typename K, typename V, typename H>
603 void ezHashTableBase<K, V, H>::SetFlags(ezUInt32 uiEntryIndex, ezUInt32 uiFlags)
604 {
605 #if EZ_ENABLED(EZ_HASHTABLE_USE_BITFLAGS)
606  const ezUInt32 uiIndex = uiEntryIndex / 16;
607  const ezUInt32 uiSubIndex = (uiEntryIndex & 15) * 2;
608  EZ_ASSERT_DEV(uiIndex < GetFlagsCapacity(), "Out of bounds access");
609  m_pEntryFlags[uiIndex] &= ~(FLAGS_MASK << uiSubIndex);
610  m_pEntryFlags[uiIndex] |= (uiFlags << uiSubIndex);
611 #else
612  EZ_ASSERT_DEV(uiEntryIndex < GetFlagsCapacity(), "Out of bounds access");
613  m_pEntryFlags[uiEntryIndex] = uiFlags;
614 #endif
615 }
616 
617 template <typename K, typename V, typename H>
618 EZ_FORCE_INLINE bool ezHashTableBase<K, V, H>::IsFreeEntry(ezUInt32 uiEntryIndex) const
619 {
620  return GetFlags(m_pEntryFlags, uiEntryIndex) == FREE_ENTRY;
621 }
622 
623 template <typename K, typename V, typename H>
624 EZ_FORCE_INLINE bool ezHashTableBase<K, V, H>::IsValidEntry(ezUInt32 uiEntryIndex) const
625 {
626  return GetFlags(m_pEntryFlags, uiEntryIndex) == VALID_ENTRY;
627 }
628 
629 template <typename K, typename V, typename H>
630 EZ_FORCE_INLINE bool ezHashTableBase<K, V, H>::IsDeletedEntry(ezUInt32 uiEntryIndex) const
631 {
632  return GetFlags(m_pEntryFlags, uiEntryIndex) == DELETED_ENTRY;
633 }
634 
635 template <typename K, typename V, typename H>
636 EZ_FORCE_INLINE void ezHashTableBase<K, V, H>::MarkEntryAsFree(ezUInt32 uiEntryIndex)
637 {
638  SetFlags(uiEntryIndex, FREE_ENTRY);
639 }
640 
641 template <typename K, typename V, typename H>
642 EZ_FORCE_INLINE void ezHashTableBase<K, V, H>::MarkEntryAsValid(ezUInt32 uiEntryIndex)
643 {
644  SetFlags(uiEntryIndex, VALID_ENTRY);
645 }
646 
647 template <typename K, typename V, typename H>
648 EZ_FORCE_INLINE void ezHashTableBase<K, V, H>::MarkEntryAsDeleted(ezUInt32 uiEntryIndex)
649 {
650  SetFlags(uiEntryIndex, DELETED_ENTRY);
651 }
652 
653 
654 template <typename K, typename V, typename H, typename A>
656 {
657 }
658 
659 template <typename K, typename V, typename H, typename A>
660 ezHashTable<K, V, H, A>::ezHashTable(ezAllocatorBase* pAllocator) : ezHashTableBase<K, V, H>(pAllocator)
661 {
662 }
663 
664 template <typename K, typename V, typename H, typename A>
665 ezHashTable<K, V, H, A>::ezHashTable(const ezHashTable<K, V, H, A>& other) : ezHashTableBase<K, V, H>(other, A::GetAllocator())
666 {
667 }
668 
669 template <typename K, typename V, typename H, typename A>
670 ezHashTable<K, V, H, A>::ezHashTable(const ezHashTableBase<K, V, H>& other) : ezHashTableBase<K, V, H>(other, A::GetAllocator())
671 {
672 }
673 
674 template <typename K, typename V, typename H, typename A>
675 ezHashTable<K, V, H, A>::ezHashTable(ezHashTable<K, V, H, A>&& other) : ezHashTableBase<K, V, H>(std::move(other), A::GetAllocator())
676 {
677 }
678 
679 template <typename K, typename V, typename H, typename A>
680 ezHashTable<K, V, H, A>::ezHashTable(ezHashTableBase<K, V, H>&& other) : ezHashTableBase<K, V, H>(std::move(other), A::GetAllocator())
681 {
682 }
683 
684 template <typename K, typename V, typename H, typename A>
686 {
688 }
689 
690 template <typename K, typename V, typename H, typename A>
692 {
694 }
695 
696 template <typename K, typename V, typename H, typename A>
698 {
699  ezHashTableBase<K, V, H>::operator=(std::move(rhs));
700 }
701 
702 template <typename K, typename V, typename H, typename A>
704 {
705  ezHashTableBase<K, V, H>::operator=(std::move(rhs));
706 }
707 
708 template <typename KeyType, typename ValueType, typename Hasher>
710 {
711  ezMath::Swap(this->m_pEntries, other.m_pEntries);
712  ezMath::Swap(this->m_pEntryFlags, other.m_pEntryFlags);
713  ezMath::Swap(this->m_uiCount, other.m_uiCount);
714  ezMath::Swap(this->m_uiCapacity, other.m_uiCapacity);
715  ezMath::Swap(this->m_pAllocator, other.m_pAllocator);
716 }
717 
EZ_ALWAYS_INLINE void Swap(T &f1, T &f2)
Swaps the values in the two variables f1 and f2.
Definition: Math_inl.h:112
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
static void CopyConstruct(Destination *pDestination, const Source &copy, size_t uiCount)
Constructs uiCount objects of type T in a raw buffer at pDestination, by creating uiCount copies of c...
#define EZ_ASSERT_DEV(bCondition, szErrorMsg,...)
Macro to raise an error, if a condition is not met.
Definition: Assert.h:116
void Next()
Advances the iterator to the next element in the map. The iterator will not be valid anymore...
Definition: HashTable_inl.h:49
static void Destruct(T *pDestination, size_t uiCount)
Destructs uiCount objects of type T at pDestination.
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
static void DefaultConstruct(T *pDestination, size_t uiCount)
Default constructs uiCount objects of type T in a raw buffer at pDestination regardless of T being a ...
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
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
#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
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
#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
Iterator GetIterator()
Returns an Iterator to the very first element.
Definition: HashTable_inl.h:494
static void ZeroFill(T *pDestination, size_t uiCount)
Zeros out buffer of a raw memory.
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
void Clear()
Clears the table.
Definition: HashTable_inl.h:275
static void CopyOrMoveConstruct(Destination *pDestination, Source &&source)
This function will either move call MoveConstruct or CopyConstruct for a single element source...
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