ezEngine  Milestone 7
IdTable_inl.h
1 
2 // ***** Const Iterator *****
3 
4 template <typename IdType, typename ValueType>
6  m_idTable(idTable), m_uiCurrentIndex(0), m_uiCurrentCount(0)
7 {
8  if (m_idTable.IsEmpty())
9  return;
10 
11  while (m_idTable.m_pEntries[m_uiCurrentIndex].id.m_InstanceIndex != m_uiCurrentIndex)
12  {
13  ++m_uiCurrentIndex;
14  }
15 }
16 
17 template <typename IdType, typename ValueType>
19 {
20  return m_uiCurrentCount < m_idTable.m_uiCount;
21 }
22 
23 template <typename IdType, typename ValueType>
25 {
26  return m_idTable.m_pEntries == it2.m_idTable.m_pEntries && m_uiCurrentIndex == it2.m_uiCurrentIndex;
27 }
28 
29 template <typename IdType, typename ValueType>
31 {
32  return !(*this == it2);
33 }
34 
35 template <typename IdType, typename ValueType>
37 {
38  return m_idTable.m_pEntries[m_uiCurrentIndex].id;
39 }
40 
41 template <typename IdType, typename ValueType>
42 EZ_FORCE_INLINE const ValueType& ezIdTableBase<IdType, ValueType>::ConstIterator::Value() const
43 {
44  return m_idTable.m_pEntries[m_uiCurrentIndex].value;
45 }
46 
47 template <typename IdType, typename ValueType>
49 {
50  ++m_uiCurrentCount;
51  if (m_uiCurrentCount == m_idTable.m_uiCount)
52  return;
53 
54  do
55  {
56  ++m_uiCurrentIndex;
57  }
58  while (m_idTable.m_pEntries[m_uiCurrentIndex].id.m_InstanceIndex != m_uiCurrentIndex);
59 }
60 
61 template <typename IdType, typename ValueType>
63 {
64  Next();
65 }
66 
67 
68 // ***** Iterator *****
69 
70 template <typename IdType, typename ValueType>
72  ConstIterator(idTable)
73 {
74 }
75 
76 template <typename IdType, typename ValueType>
78 {
79  return this->m_idTable.m_pEntries[this->m_uiCurrentIndex].value;
80 }
81 
82 
83 // ***** ezIdTableBase *****
84 
85 template <typename IdType, typename ValueType>
87 {
88  m_pEntries = nullptr;
89  m_uiCount = 0;
90  m_uiCapacity = 0;
91  m_uiFreelistEnqueue = -1;
92  m_uiFreelistDequeue = 0;
93  m_pAllocator = pAllocator;
94 }
95 
96 template <typename IdType, typename ValueType>
98 {
99  m_pEntries = nullptr;
100  m_uiCount = 0;
101  m_uiCapacity = 0;
102  m_uiFreelistEnqueue = -1;
103  m_uiFreelistDequeue = 0;
104  m_pAllocator = pAllocator;
105 
106  *this = other;
107 }
108 
109 template <typename IdType, typename ValueType>
111 {
112  for (IndexType i = 0; i < m_uiCapacity; ++i)
113  {
114  if (m_pEntries[i].id.m_InstanceIndex == i)
115  {
116  ezMemoryUtils::Destruct(&m_pEntries[i].value, 1);
117  }
118  }
119 
120  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntries);
121  m_uiCapacity = 0;
122 }
123 
124 template <typename IdType, typename ValueType>
126 {
127  Clear();
128  Reserve(rhs.m_uiCapacity);
129 
130  for (IndexType i = 0; i < rhs.m_uiCapacity; ++i)
131  {
132  Entry& entry = m_pEntries[i];
133 
134  entry.id = rhs.m_pEntries[i].id;
135  if (entry.id.m_InstanceIndex == i)
136  {
137  ezMemoryUtils::CopyConstruct(&entry.value, rhs.m_pEntries[i].value, 1);
138  }
139  }
140 
141  m_uiCount = rhs.m_uiCount;
142  m_uiFreelistDequeue = rhs.m_uiFreelistDequeue;
143 }
144 
145 template <typename IdType, typename ValueType>
147 {
148  if (m_uiCapacity >= uiCapacity + CAPACITY_ALIGNMENT)
149  return;
150 
151  IndexType uiNewCapacity = ezMath::Max(m_uiCapacity + (m_uiCapacity / 2), uiCapacity + CAPACITY_ALIGNMENT);
152  uiNewCapacity = (uiNewCapacity + (CAPACITY_ALIGNMENT - 1)) & ~(CAPACITY_ALIGNMENT - 1);
153  SetCapacity(uiNewCapacity);
154 }
155 
156 template <typename IdType, typename ValueType>
157 EZ_FORCE_INLINE typename ezIdTableBase<IdType, ValueType>::IndexType ezIdTableBase<IdType, ValueType>::GetCount() const
158 {
159  return m_uiCount;
160 }
161 
162 template <typename IdType, typename ValueType>
163 EZ_FORCE_INLINE bool ezIdTableBase<IdType, ValueType>::IsEmpty() const
164 {
165  return m_uiCount == 0;
166 }
167 
168 template <typename IdType, typename ValueType>
170 {
171  for (IndexType i = 0; i < m_uiCapacity; ++i)
172  {
173  Entry& entry = m_pEntries[i];
174 
175  if (entry.id.m_InstanceIndex == i)
176  {
177  ezMemoryUtils::Destruct(&entry.value, 1);
178  ++entry.id.m_Generation;
179  }
180 
181  entry.id.m_InstanceIndex = i + 1;
182  }
183 
184  m_uiFreelistDequeue = 0;
185  m_uiFreelistEnqueue = m_uiCapacity - 1;
186  m_uiCount = 0;
187 }
188 
189 template <typename IdType, typename ValueType>
190 IdType ezIdTableBase<IdType, ValueType>::Insert(const ValueType& value)
191 {
192  Reserve(m_uiCount + 1);
193 
194  const IndexType uiNewIndex = m_uiFreelistDequeue;
195  Entry& entry = m_pEntries[uiNewIndex];
196 
197  m_uiFreelistDequeue = entry.id.m_InstanceIndex;
198  entry.id.m_InstanceIndex = uiNewIndex;
199  ezMemoryUtils::CopyConstruct(&entry.value, value, 1);
200 
201  ++m_uiCount;
202 
203  return entry.id;
204 }
205 
206 template <typename IdType, typename ValueType>
207 bool ezIdTableBase<IdType, ValueType>::Remove(const IdType id, ValueType* out_oldValue /*= nullptr*/)
208 {
209  if (m_uiCapacity <= id.m_InstanceIndex)
210  return false;
211 
212  const IndexType uiIndex = id.m_InstanceIndex;
213  Entry& entry = m_pEntries[uiIndex];
214  if (!entry.id.IsIndexAndGenerationEqual(id))
215  return false;
216 
217  if (out_oldValue != nullptr)
218  *out_oldValue = m_pEntries[uiIndex].value;
219 
220  ezMemoryUtils::Destruct(&entry.value, 1);
221 
222  entry.id.m_InstanceIndex = m_pEntries[m_uiFreelistEnqueue].id.m_InstanceIndex;
223  ++entry.id.m_Generation;
224 
225  m_pEntries[m_uiFreelistEnqueue].id.m_InstanceIndex = uiIndex;
226  m_uiFreelistEnqueue = uiIndex;
227 
228  --m_uiCount;
229  return true;
230 }
231 
232 template <typename IdType, typename ValueType>
233 EZ_FORCE_INLINE bool ezIdTableBase<IdType, ValueType>::TryGetValue(const IdType id, ValueType& out_value) const
234 {
235  const IndexType index = id.m_InstanceIndex;
236  if (index < m_uiCapacity && m_pEntries[index].id.IsIndexAndGenerationEqual(id))
237  {
238  out_value = m_pEntries[index].value;
239  return true;
240  }
241  return false;
242 }
243 
244 template <typename IdType, typename ValueType>
245 EZ_FORCE_INLINE bool ezIdTableBase<IdType, ValueType>::TryGetValue(const IdType id, ValueType*& out_pValue) const
246 {
247  const IndexType index = id.m_InstanceIndex;
248  if (index < m_uiCapacity && m_pEntries[index].id.IsIndexAndGenerationEqual(id))
249  {
250  out_pValue = &m_pEntries[index].value;
251  return true;
252  }
253  return false;
254 }
255 
256 template <typename IdType, typename ValueType>
257 EZ_FORCE_INLINE const ValueType& ezIdTableBase<IdType, ValueType>::operator[](const IdType id) const
258 {
259  EZ_ASSERT_DEV(id.m_InstanceIndex < m_uiCapacity, "Out of bounds access. Table has %i elements, trying to access element at index %i.", m_uiCapacity, id.m_InstanceIndex);
260  Entry& entry = m_pEntries[id.m_InstanceIndex];
261  EZ_ASSERT_DEV(entry.id.IsIndexAndGenerationEqual(id),
262  "Stale access. Trying to access a value (generation: %i) that has been removed and replaced by a new value (generation: %i)", entry.id.m_Generation, id.m_Generation);
263 
264  return entry.value;
265 }
266 
267 template <typename IdType, typename ValueType>
268 EZ_FORCE_INLINE ValueType& ezIdTableBase<IdType, ValueType>::operator[](const IdType id)
269 {
270  EZ_ASSERT_DEV(id.m_InstanceIndex < m_uiCapacity, "Out of bounds access. Table has %i elements, trying to access element at index %i.", m_uiCapacity, id.m_InstanceIndex);
271  Entry& entry = m_pEntries[id.m_InstanceIndex];
272  EZ_ASSERT_DEV(entry.id.IsIndexAndGenerationEqual(id),
273  "Stale access. Trying to access a value (generation: %i) that has been removed and replaced by a new value (generation: %i)", entry.id.m_Generation, id.m_Generation);
274 
275  return entry.value;
276 }
277 
278 template <typename IdType, typename ValueType>
279 EZ_FORCE_INLINE const ValueType& ezIdTableBase<IdType, ValueType>::GetValueUnchecked(const IndexType index) const
280 {
281  EZ_ASSERT_DEV(index < m_uiCapacity, "Out of bounds access. Table has %i elements, trying to access element at index %i.", m_uiCapacity, index);
282  return m_pEntries[index].value;
283 }
284 
285 template <typename IdType, typename ValueType>
286 EZ_FORCE_INLINE ValueType& ezIdTableBase<IdType, ValueType>::GetValueUnchecked(const IndexType index)
287 {
288  EZ_ASSERT_DEV(index < m_uiCapacity, "Out of bounds access. Table has %i elements, trying to access element at index %i.", m_uiCapacity, index);
289  return m_pEntries[index].value;
290 }
291 
292 template <typename IdType, typename ValueType>
293 EZ_FORCE_INLINE bool ezIdTableBase<IdType, ValueType>::Contains(const IdType id) const
294 {
295  const IndexType index = id.m_InstanceIndex;
296  return index < m_uiCapacity && m_pEntries[index].id.IsIndexAndGenerationEqual(id);
297 }
298 
299 template <typename IdType, typename ValueType>
301 {
302  return Iterator(*this);
303 }
304 
305 template <typename IdType, typename ValueType>
307 {
308  return ConstIterator(*this);
309 }
310 
311 template <typename IdType, typename ValueType>
313 {
314  return m_pAllocator;
315 }
316 
317 template <typename IdType, typename ValueType>
319 {
320  if (m_pEntries == nullptr)
321  return true;
322 
323  IndexType uiIndex = m_uiFreelistDequeue;
324  const Entry* pEntry = m_pEntries + uiIndex;
325 
326  while (pEntry->id.m_InstanceIndex < m_uiCapacity)
327  {
328  uiIndex = pEntry->id.m_InstanceIndex;
329  pEntry = m_pEntries + uiIndex;
330  }
331 
332  return uiIndex == m_uiFreelistEnqueue;
333 }
334 
335 
336 // private methods
337 template <typename IdType, typename ValueType>
338 void ezIdTableBase<IdType, ValueType>::SetCapacity(IndexType uiCapacity)
339 {
340  Entry* pNewEntries = EZ_NEW_RAW_BUFFER(m_pAllocator, Entry, (size_t) uiCapacity);
341 
342  for (IndexType i = 0; i < m_uiCapacity; ++i)
343  {
344  pNewEntries[i].id = m_pEntries[i].id;
345 
346  if (m_pEntries[i].id.m_InstanceIndex == i)
347  {
348  ezMemoryUtils::RelocateConstruct(&pNewEntries[i].value, &m_pEntries[i].value, 1);
349  }
350  }
351 
352  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pEntries);
353  m_pEntries = pNewEntries;
354 
355  InitializeFreelist(m_uiCapacity, uiCapacity);
356  m_uiCapacity = uiCapacity;
357 }
358 
359 template <typename IdType, typename ValueType>
360 inline void ezIdTableBase<IdType, ValueType>::InitializeFreelist(IndexType uiStart, IndexType uiEnd)
361 {
362  for (IndexType i = uiStart; i < uiEnd; ++i)
363  {
364  IdType& id = m_pEntries[i].id;
365  id = IdType(i + 1, 0);
366  }
367 
368  m_uiFreelistEnqueue = uiEnd - 1;
369 }
370 
371 
372 template <typename IdType, typename V, typename A>
374 {
375 }
376 
377 template <typename IdType, typename V, typename A>
378 ezIdTable<IdType, V, A>::ezIdTable(ezAllocatorBase* pAllocator) : ezIdTableBase<IdType, V>(pAllocator)
379 {
380 }
381 
382 template <typename IdType, typename V, typename A>
383 ezIdTable<IdType, V, A>::ezIdTable(const ezIdTable<IdType, V, A>& other) : ezIdTableBase<IdType, V>(other, A::GetAllocator())
384 {
385 }
386 
387 template <typename IdType, typename V, typename A>
388 ezIdTable<IdType, V, A>::ezIdTable(const ezIdTableBase<IdType, V>& other) : ezIdTableBase<IdType, V>(other, A::GetAllocator())
389 {
390 }
391 
392 template <typename IdType, typename V, typename A>
394 {
396 }
397 
398 template <typename IdType, typename V, typename A>
400 {
402 }
403