ezEngine  Milestone 7
HashTable_inl.h
1 
2 #define ezInvalidIndex 0xFFFFFFFF
3 
4 // ***** Const Iterator *****
5 
6 template <typename K, typename V, typename H>
8  m_hashTable(hashTable), m_uiCurrentIndex(0), m_uiCurrentCount(0)
9 {
10  if (m_hashTable.IsEmpty())
11  return;
12 
13  while (!m_hashTable.IsValidEntry(m_uiCurrentIndex))
14  {
15  ++m_uiCurrentIndex;
16  }
17 }
18 
19 template <typename K, typename V, typename H>
21 {
22  return m_uiCurrentCount < m_hashTable.m_uiCount;
23 }
24 
25 template <typename K, typename V, typename H>
27 {
28  return m_hashTable.m_pEntries == it2.m_hashTable.m_pEntries && m_uiCurrentIndex == it2.m_uiCurrentIndex;
29 }
30 
31 template <typename K, typename V, typename H>
33 {
34  return !(*this == it2);
35 }
36 
37 template <typename K, typename V, typename H>
38 EZ_FORCE_INLINE const K& ezHashTableBase<K, V, H>::ConstIterator::Key() const
39 {
40  return m_hashTable.m_pEntries[m_uiCurrentIndex].key;
41 }
42 
43 template <typename K, typename V, typename H>
44 EZ_FORCE_INLINE const V& ezHashTableBase<K, V, H>::ConstIterator::Value() const
45 {
46  return m_hashTable.m_pEntries[m_uiCurrentIndex].value;
47 }
48 
49 template <typename K, typename V, typename H>
51 {
52  ++m_uiCurrentCount;
53  if (m_uiCurrentCount == m_hashTable.m_uiCount)
54  return;
55 
56  do
57  {
58  ++m_uiCurrentIndex;
59  }
60  while (!m_hashTable.IsValidEntry(m_uiCurrentIndex));
61 }
62 
63 template <typename K, typename V, typename H>
65 {
66  Next();
67 }
68 
69 
70 // ***** Iterator *****
71 
72 template <typename K, typename V, typename H>
74  ConstIterator(hashTable)
75 {
76 }
77 
78 template <typename K, typename V, typename H>
80 {
81  return this->m_hashTable.m_pEntries[this->m_uiCurrentIndex].value;
82 }
83 
84 
85 // ***** ezHashTableBase *****
86 
87 template <typename K, typename V, typename H>
89 {
90  m_pEntries = nullptr;
91  m_pEntryFlags = nullptr;
92  m_uiCount = 0;
93  m_uiCapacity = 0;
94  m_pAllocator = pAllocator;
95 }
96 
97 template <typename K, typename V, typename H>
99 {
100  m_pEntries = nullptr;
101  m_pEntryFlags = nullptr;
102  m_uiCount = 0;
103  m_uiCapacity = 0;
104  m_pAllocator = pAllocator;
105 
106  *this = other;
107 }
108 
109 template <typename K, typename V, typename H>
111 {
112  Clear();
113  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntries);
114  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntryFlags);
115  m_uiCapacity = 0;
116 }
117 
118 template <typename K, typename V, typename H>
120 {
121  Clear();
122  Reserve(rhs.GetCount());
123 
124  ezUInt32 uiCopied = 0;
125  for (ezUInt32 i = 0; uiCopied < rhs.GetCount(); ++i)
126  {
127  if (rhs.IsValidEntry(i))
128  {
129  Insert(rhs.m_pEntries[i].key, rhs.m_pEntries[i].value);
130  ++uiCopied;
131  }
132  }
133 }
134 
135 template <typename K, typename V, typename H>
137 {
138  if (m_uiCount != rhs.m_uiCount)
139  return false;
140 
141  ezUInt32 uiCompared = 0;
142  for (ezUInt32 i = 0; uiCompared < m_uiCount; ++i)
143  {
144  if (IsValidEntry(i))
145  {
146  V* pRhsValue = nullptr;
147  if (!rhs.TryGetValue(m_pEntries[i].key, pRhsValue))
148  return false;
149 
150  if (m_pEntries[i].value != *pRhsValue)
151  return false;
152 
153  ++uiCompared;
154  }
155  }
156 
157  return true;
158 }
159 
160 template <typename K, typename V, typename H>
162 {
163  return !(*this == rhs);
164 }
165 
166 template <typename K, typename V, typename H>
167 void ezHashTableBase<K, V, H>::Reserve(ezUInt32 uiCapacity)
168 {
169  ezUInt32 uiNewCapacity = uiCapacity + (uiCapacity / 3) * 2; // ensure a maximum load of 60%
170  if (m_uiCapacity >= uiNewCapacity)
171  return;
172 
173  uiNewCapacity = ezMath::Max<ezUInt32>(ezMath::PowerOfTwo_Ceil(uiNewCapacity), CAPACITY_ALIGNMENT);
174  SetCapacity(uiNewCapacity);
175 }
176 
177 template <typename K, typename V, typename H>
179 {
180  if (IsEmpty())
181  {
182  // completely deallocate all data, if the table is empty.
183  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntries);
184  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntryFlags);
185  m_uiCapacity = 0;
186  }
187  else
188  {
189  const ezUInt32 uiNewCapacity = (m_uiCount + (CAPACITY_ALIGNMENT - 1)) & ~(CAPACITY_ALIGNMENT - 1);
190  if (m_uiCapacity != uiNewCapacity)
191  SetCapacity(uiNewCapacity);
192  }
193 }
194 
195 template <typename K, typename V, typename H>
196 EZ_FORCE_INLINE ezUInt32 ezHashTableBase<K, V, H>::GetCount() const
197 {
198  return m_uiCount;
199 }
200 
201 template <typename K, typename V, typename H>
202 EZ_FORCE_INLINE bool ezHashTableBase<K, V, H>::IsEmpty() const
203 {
204  return m_uiCount == 0;
205 }
206 
207 template <typename K, typename V, typename H>
209 {
210  for (ezUInt32 i = 0; i < m_uiCapacity; ++i)
211  {
212  if (IsValidEntry(i))
213  {
214  ezMemoryUtils::Destruct(&m_pEntries[i].key, 1);
215  ezMemoryUtils::Destruct(&m_pEntries[i].value, 1);
216  }
217  }
218 
219  ezMemoryUtils::ZeroFill(m_pEntryFlags, GetFlagsCapacity());
220  m_uiCount = 0;
221 }
222 
223 template <typename K, typename V, typename H>
224 bool ezHashTableBase<K, V, H>::Insert(const K& key, const V& value, V* out_oldValue /*= nullptr*/)
225 {
226  Reserve(m_uiCount + 1);
227 
228  ezUInt32 uiIndex = H::Hash(key) % m_uiCapacity;
229  ezUInt32 uiDeletedIndex = ezInvalidIndex;
230 
231  ezUInt32 uiCounter = 0;
232  while (!IsFreeEntry(uiIndex) && uiCounter < m_uiCapacity)
233  {
234  if (IsDeletedEntry(uiIndex))
235  {
236  if (uiDeletedIndex == ezInvalidIndex)
237  uiDeletedIndex = uiIndex;
238  }
239  else if (H::Equal(m_pEntries[uiIndex].key, key))
240  {
241  if (out_oldValue != nullptr)
242  *out_oldValue = std::move(m_pEntries[uiIndex].value);
243 
244  m_pEntries[uiIndex].value = value;
245  return true;
246  }
247  ++uiIndex;
248  if (uiIndex == m_uiCapacity)
249  uiIndex = 0;
250 
251  ++uiCounter;
252  }
253 
254  // new entry
255  uiIndex = uiDeletedIndex != ezInvalidIndex ? uiDeletedIndex : uiIndex;
256 
257  ezMemoryUtils::CopyConstruct(&m_pEntries[uiIndex].key, &key, 1);
258  ezMemoryUtils::CopyConstruct(&m_pEntries[uiIndex].value, &value, 1);
259  MarkEntryAsValid(uiIndex);
260  ++m_uiCount;
261 
262  return false;
263 }
264 
265 template <typename K, typename V, typename H>
266 bool ezHashTableBase<K, V, H>::Remove(const K& key, V* out_oldValue /*= nullptr*/)
267 {
268  ezUInt32 uiIndex = FindEntry(key);
269  if (uiIndex != ezInvalidIndex)
270  {
271  if (out_oldValue != nullptr)
272  *out_oldValue = std::move(m_pEntries[uiIndex].value);
273 
274  ezMemoryUtils::Destruct(&m_pEntries[uiIndex].key, 1);
275  ezMemoryUtils::Destruct(&m_pEntries[uiIndex].value, 1);
276 
277  ezUInt32 uiNextIndex = uiIndex + 1;
278  if (uiNextIndex == m_uiCapacity)
279  uiNextIndex = 0;
280 
281  // if the next entry is free we are at the end of a chain and
282  // can immediately mark this entry as free as well
283  if (IsFreeEntry(uiNextIndex))
284  {
285  MarkEntryAsFree(uiIndex);
286 
287  // run backwards and free all deleted entries in this chain
288  ezUInt32 uiPrevIndex = (uiIndex != 0) ? uiIndex : m_uiCapacity;
289  --uiPrevIndex;
290 
291  while (IsDeletedEntry(uiPrevIndex))
292  {
293  MarkEntryAsFree(uiPrevIndex);
294 
295  if (uiPrevIndex == 0)
296  uiPrevIndex = m_uiCapacity;
297  --uiPrevIndex;
298  }
299  }
300  else
301  {
302  MarkEntryAsDeleted(uiIndex);
303  }
304 
305  --m_uiCount;
306  return true;
307  }
308 
309  return false;
310 }
311 
312 template <typename K, typename V, typename H>
313 inline bool ezHashTableBase<K, V, H>::TryGetValue(const K& key, V& out_value) const
314 {
315  ezUInt32 uiIndex = FindEntry(key);
316  if (uiIndex != ezInvalidIndex)
317  {
318  out_value = m_pEntries[uiIndex].value;
319  return true;
320  }
321 
322  return false;
323 }
324 
325 template <typename K, typename V, typename H>
326 inline bool ezHashTableBase<K, V, H>::TryGetValue(const K& key, V*& out_pValue) const
327 {
328  ezUInt32 uiIndex = FindEntry(key);
329  if (uiIndex != ezInvalidIndex)
330  {
331  out_pValue = &m_pEntries[uiIndex].value;
332  return true;
333  }
334 
335  return false;
336 }
337 
338 template <typename K, typename V, typename H>
340 {
341  const ezUInt32 uiHash = H::Hash(key);
342  ezUInt32 uiIndex = FindEntry(uiHash, key);
343 
344  if (uiIndex == ezInvalidIndex)
345  {
346  Reserve(m_uiCount + 1);
347 
348  // search for suitable insertion index again, table might have been resized
349  uiIndex = uiHash % m_uiCapacity;
350  while (IsValidEntry(uiIndex))
351  {
352  ++uiIndex;
353  if (uiIndex == m_uiCapacity)
354  uiIndex = 0;
355  }
356 
357  // new entry
358  ezMemoryUtils::CopyConstruct(&m_pEntries[uiIndex].key, key, 1);
359  ezMemoryUtils::DefaultConstruct(&m_pEntries[uiIndex].value, 1);
360  MarkEntryAsValid(uiIndex);
361  ++m_uiCount;
362  }
363  return m_pEntries[uiIndex].value;
364 }
365 
366 template <typename K, typename V, typename H>
367 EZ_FORCE_INLINE bool ezHashTableBase<K, V, H>::Contains(const K& key) const
368 {
369  return FindEntry(key) != ezInvalidIndex;
370 }
371 
372 template <typename K, typename V, typename H>
374 {
375  return Iterator(*this);
376 }
377 
378 template <typename K, typename V, typename H>
380 {
381  return ConstIterator(*this);
382 }
383 
384 template <typename K, typename V, typename H>
386 {
387  return m_pAllocator;
388 }
389 
390 template <typename K, typename V, typename H>
392 {
393  return ((ezUInt64) m_uiCapacity * sizeof(Entry)) + (sizeof(ezUInt32) * (ezUInt64) GetFlagsCapacity());
394 }
395 
396 // private methods
397 template <typename K, typename V, typename H>
398 void ezHashTableBase<K, V, H>::SetCapacity(ezUInt32 uiCapacity)
399 {
400  const ezUInt32 uiOldCapacity = m_uiCapacity;
401  m_uiCapacity = uiCapacity;
402 
403  Entry* pOldEntries = m_pEntries;
404  ezUInt32* pOldEntryFlags = m_pEntryFlags;
405 
406  m_pEntries = EZ_NEW_RAW_BUFFER(m_pAllocator, Entry, m_uiCapacity);
407  m_pEntryFlags = EZ_NEW_RAW_BUFFER(m_pAllocator, ezUInt32, GetFlagsCapacity());
408  ezMemoryUtils::ZeroFill(m_pEntryFlags, GetFlagsCapacity());
409 
410  m_uiCount = 0;
411  for (ezUInt32 i = 0; i < uiOldCapacity; ++i)
412  {
413  if (GetFlags(pOldEntryFlags, i) == VALID_ENTRY)
414  {
415  EZ_VERIFY(!Insert(pOldEntries[i].key, pOldEntries[i].value), "Implementation error");
416 
417  ezMemoryUtils::Destruct(&pOldEntries[i].key, 1);
418  ezMemoryUtils::Destruct(&pOldEntries[i].value, 1);
419  }
420  }
421 
422  EZ_DELETE_RAW_BUFFER(m_pAllocator, pOldEntries);
423  EZ_DELETE_RAW_BUFFER(m_pAllocator, pOldEntryFlags);
424 }
425 
426 template <typename K, typename V, typename H>
427 EZ_FORCE_INLINE ezUInt32 ezHashTableBase<K, V, H>::FindEntry(const K& key) const
428 {
429  return FindEntry(H::Hash(key), key);
430 }
431 
432 template <typename K, typename V, typename H>
433 inline ezUInt32 ezHashTableBase<K, V, H>::FindEntry(ezUInt32 uiHash, const K& key) const
434 {
435  if (m_uiCapacity > 0)
436  {
437  ezUInt32 uiIndex = uiHash % m_uiCapacity;
438  ezUInt32 uiCounter = 0;
439  while (!IsFreeEntry(uiIndex) && uiCounter < m_uiCapacity)
440  {
441  if (IsValidEntry(uiIndex) && H::Equal(m_pEntries[uiIndex].key, key))
442  return uiIndex;
443 
444  ++uiIndex;
445  if (uiIndex == m_uiCapacity)
446  uiIndex = 0;
447 
448  ++uiCounter;
449  }
450  }
451  // not found
452  return ezInvalidIndex;
453 }
454 
455 #define EZ_HASHTABLE_USE_BITFLAGS EZ_ON
456 
457 template <typename K, typename V, typename H>
458 EZ_FORCE_INLINE ezUInt32 ezHashTableBase<K, V, H>::GetFlagsCapacity() const
459 {
460 #if EZ_ENABLED(EZ_HASHTABLE_USE_BITFLAGS)
461  return (m_uiCapacity + 15) / 16;
462 #else
463  return m_uiCapacity;
464 #endif
465 }
466 
467 template <typename K, typename V, typename H>
468 ezUInt32 ezHashTableBase<K, V, H>::GetFlags(ezUInt32* pFlags, ezUInt32 uiEntryIndex) const
469 {
470 #if EZ_ENABLED(EZ_HASHTABLE_USE_BITFLAGS)
471  const ezUInt32 uiIndex = uiEntryIndex / 16;
472  const ezUInt32 uiSubIndex = (uiEntryIndex & 15) * 2;
473  return (pFlags[uiIndex] >> uiSubIndex) & FLAGS_MASK;
474 #else
475  return pFlags[uiEntryIndex] & FLAGS_MASK;
476 #endif
477 }
478 
479 template <typename K, typename V, typename H>
480 void ezHashTableBase<K, V, H>::SetFlags(ezUInt32 uiEntryIndex, ezUInt32 uiFlags)
481 {
482 #if EZ_ENABLED(EZ_HASHTABLE_USE_BITFLAGS)
483  const ezUInt32 uiIndex = uiEntryIndex / 16;
484  const ezUInt32 uiSubIndex = (uiEntryIndex & 15) * 2;
485  EZ_ASSERT_DEV(uiIndex < GetFlagsCapacity(), "Out of bounds access");
486  m_pEntryFlags[uiIndex] &= ~(FLAGS_MASK << uiSubIndex);
487  m_pEntryFlags[uiIndex] |= (uiFlags << uiSubIndex);
488 #else
489  EZ_ASSERT_DEV(uiEntryIndex < GetFlagsCapacity(), "Out of bounds access");
490  m_pEntryFlags[uiEntryIndex] = uiFlags;
491 #endif
492 }
493 
494 template <typename K, typename V, typename H>
495 EZ_FORCE_INLINE bool ezHashTableBase<K, V, H>::IsFreeEntry(ezUInt32 uiEntryIndex) const
496 {
497  return GetFlags(m_pEntryFlags, uiEntryIndex) == FREE_ENTRY;
498 }
499 
500 template <typename K, typename V, typename H>
501 EZ_FORCE_INLINE bool ezHashTableBase<K, V, H>::IsValidEntry(ezUInt32 uiEntryIndex) const
502 {
503  return GetFlags(m_pEntryFlags, uiEntryIndex) == VALID_ENTRY;
504 }
505 
506 template <typename K, typename V, typename H>
507 EZ_FORCE_INLINE bool ezHashTableBase<K, V, H>::IsDeletedEntry(ezUInt32 uiEntryIndex) const
508 {
509  return GetFlags(m_pEntryFlags, uiEntryIndex) == DELETED_ENTRY;
510 }
511 
512 template <typename K, typename V, typename H>
513 EZ_FORCE_INLINE void ezHashTableBase<K, V, H>::MarkEntryAsFree(ezUInt32 uiEntryIndex)
514 {
515  SetFlags(uiEntryIndex, FREE_ENTRY);
516 }
517 
518 template <typename K, typename V, typename H>
519 EZ_FORCE_INLINE void ezHashTableBase<K, V, H>::MarkEntryAsValid(ezUInt32 uiEntryIndex)
520 {
521  SetFlags(uiEntryIndex, VALID_ENTRY);
522 }
523 
524 template <typename K, typename V, typename H>
525 EZ_FORCE_INLINE void ezHashTableBase<K, V, H>::MarkEntryAsDeleted(ezUInt32 uiEntryIndex)
526 {
527  SetFlags(uiEntryIndex, DELETED_ENTRY);
528 }
529 
530 
531 template <typename K, typename V, typename H, typename A>
533 {
534 }
535 
536 template <typename K, typename V, typename H, typename A>
537 ezHashTable<K, V, H, A>::ezHashTable(ezAllocatorBase* pAllocator) : ezHashTableBase<K, V, H>(pAllocator)
538 {
539 }
540 
541 template <typename K, typename V, typename H, typename A>
542 ezHashTable<K, V, H, A>::ezHashTable(const ezHashTable<K, V, H, A>& other) : ezHashTableBase<K, V, H>(other, A::GetAllocator())
543 {
544 }
545 
546 template <typename K, typename V, typename H, typename A>
547 ezHashTable<K, V, H, A>::ezHashTable(const ezHashTableBase<K, V, H>& other) : ezHashTableBase<K, V, H>(other, A::GetAllocator())
548 {
549 }
550 
551 template <typename K, typename V, typename H, typename A>
553 {
555 }
556 
557 template <typename K, typename V, typename H, typename A>
559 {
561 }
562