ezEngine  Milestone 7
Deque_inl.h
1 #pragma once
2 
3 #include <Foundation/Math/Math.h>
4 
5 #define REDUCE_SIZE(iReduction) \
6  m_iReduceSizeTimer -= iReduction; \
7  if (m_iReduceSizeTimer <= 0) \
8  ReduceSize(0);
9 
10 #define RESERVE(uiCount) \
11  if (uiCount > m_uiCount) { \
12  m_uiMaxCount = ezMath::Max(m_uiMaxCount, uiCount); \
13  if ((m_uiFirstElement <= 0) || (GetCurMaxCount() < uiCount)) \
14  Reserve(uiCount); }
15 
16 #define CHUNK_SIZE(Type) \
17  (4096 / sizeof(Type) < 32 ? 32 : 4096 / sizeof(Type))
18  //(sizeof(Type) <= 8 ? 256 : (sizeof(Type) <= 16 ? 128 : (sizeof(Type) <= 32 ? 64 : 32))) // although this is Pow(2), this is slower than just having larger chunks
19 
20 template <typename T, bool Construct>
22 {
23  m_pAllocator = pAllocator;
24  m_pChunks = nullptr;
25  m_uiChunks = 0;
26  m_uiFirstElement = 0;
27  m_uiCount = 0;
28  m_uiAllocatedChunks = 0;
29  m_uiMaxCount = 0;
30 
31  ResetReduceSizeCounter();
32 
33 #if EZ_ENABLED(EZ_COMPILE_FOR_DEBUG)
34  m_uiChunkSize = CHUNK_SIZE(T);
35 #endif
36 }
37 
38 template <typename T, bool Construct>
40 {
41  Constructor(pAllocator);
42 }
43 
44 template <typename T, bool Construct>
46 {
47  EZ_CHECK_AT_COMPILETIME_MSG(Construct, "This function is not supported on Deques that do not construct their data.");
48 
49  Constructor(pAllocator);
50 
51  *this = rhs;
52 }
53 
54 template <typename T, bool Construct>
56 {
57  EZ_CHECK_AT_COMPILETIME_MSG(Construct, "This function is not supported on Deques that do not construct their data.");
58 
59  Constructor(pAllocator);
60 
61  *this = std::move(rhs);
62 }
63 
64 template <typename T, bool Construct>
66 {
67  DeallocateAll();
68 }
69 
70 template <typename T, bool Construct>
72 {
73  EZ_CHECK_AT_COMPILETIME_MSG(Construct, "This function is not supported on Deques that do not construct their data.");
74 
75  Clear(); // does not deallocate anything
76  RESERVE(rhs.m_uiCount); // allocates data, if required
77  m_uiCount = rhs.m_uiCount;
78 
79  // copy construct all the elements
80  for (ezUInt32 i = 0; i < rhs.m_uiCount; ++i)
81  ezMemoryUtils::CopyConstruct(&ElementAt(i), &rhs[i], 1);
82 }
83 
84 template <typename T, bool Construct>
86 {
87  EZ_CHECK_AT_COMPILETIME_MSG(Construct, "This function is not supported on Deques that do not construct their data.");
88 
89  if (m_pAllocator != rhs.m_pAllocator)
90  operator=(static_cast<ezDequeBase<T, Construct>&>(rhs));
91  else
92  {
93  DeallocateAll();
94 
95  m_uiCount = rhs.m_uiCount;
96  m_iReduceSizeTimer = rhs.m_iReduceSizeTimer;
97  m_pChunks = rhs.m_pChunks;
98  m_uiAllocatedChunks = rhs.m_uiAllocatedChunks;
99  m_uiChunks = rhs.m_uiChunks;
100  m_uiFirstElement = rhs.m_uiFirstElement;
101  m_uiMaxCount = rhs.m_uiMaxCount;
102 
103  rhs.m_uiCount = 0;
104  rhs.m_pChunks = nullptr;
105  rhs.m_uiAllocatedChunks = 0;
106  rhs.m_uiChunks = 0;
107  rhs.m_uiFirstElement = 0;
108  rhs.m_uiMaxCount = 0;
109  }
110 }
111 
112 template <typename T, bool Construct>
114 {
115  if (GetCount() != rhs.GetCount())
116  return false;
117 
118  for (ezUInt32 i = 0; i < GetCount(); ++i)
119  {
120  if ((*this)[i] != rhs[i])
121  return false;
122  }
123 
124  return true;
125 }
126 
127 template <typename T, bool Construct>
129 {
130  return !operator==(rhs);
131 }
132 
133 template <typename T, bool Construct>
135 {
136  if (Construct)
137  {
138  for (ezUInt32 i = 0; i < m_uiCount; ++i)
139  ezMemoryUtils::Destruct<T>(&operator[](i), 1);
140  }
141 
142  m_uiCount = 0;
143 
144  // since it is much more likely that data is appended at the back of the deque,
145  // we do not use the center of the chunk index array, but instead set the first element
146  // somewhere more at the front
147 
148  // set the first element to a position that allows to add elements at the front
149  if (m_uiChunks > 30)
150  m_uiFirstElement = CHUNK_SIZE(T) * 16;
151  else
152  if (m_uiChunks > 8)
153  m_uiFirstElement = CHUNK_SIZE(T) * 4;
154  else
155  if (m_uiChunks > 1)
156  m_uiFirstElement = CHUNK_SIZE(T) * 1;
157  else
158  if (m_uiChunks > 0)
159  m_uiFirstElement = 1; // with the current implementation this case should not be possible.
160  else
161  m_uiFirstElement = 0; // must also work, if Clear is called on a deallocated (not yet allocated) deque
162 }
163 
164 template <typename T, bool Construct>
166 {
167  // This is the function where all the complicated stuff happens.
168  // The basic idea is as follows:
169  // * do not do anything unless necessary
170  // * if the index array (for the redirection) is already large enough to handle the 'address space', try to reuse it
171  // by moving data around (shift it left or right), if necessary
172  // * if the chunk index array is not large enough to handle the required amount of redirections, allocate a new
173  // index array and move the old data over
174  // This function does not allocate any of the chunks itself (that's what 'ElementAt' does), it only takes care
175  // that the amount of reserved elements can be redirected once the deque is enlarged accordingly.
176 
177  // no need to change anything in this case
178  if (uiCount <= m_uiCount)
179  return;
180 
181  // keeps track of the largest amount of used elements since the last memory reduction
182  m_uiMaxCount = ezMath::Max(m_uiMaxCount, uiCount);
183 
184  // if there is enough room to hold all requested elements AND one can prepend at least one element (PushFront)
185  // do not reallocate
186  if ((m_uiFirstElement > 0) && (GetCurMaxCount() >= uiCount))
187  return;
188 
189  const ezUInt32 uiCurFirstChunk = GetFirstUsedChunk();
190  const ezUInt32 uiRequiredChunks = GetRequiredChunks(uiCount);
191 
192  // if we already have enough chunks, just rearrange them
193  if (m_uiChunks > uiRequiredChunks + 1) // have at least one spare chunk for the front, and one for the back
194  {
195  const ezUInt32 uiSpareChunks = m_uiChunks - uiRequiredChunks;
196  const ezUInt32 uiSpareChunksStart = uiSpareChunks / 2;
197 
198  EZ_ASSERT_DEBUG(uiSpareChunksStart > 0, "Implementation error.");
199 
200  // always leave one spare chunk at the front, to ensure that one can prepend elements
201 
202  EZ_ASSERT_DEBUG(uiSpareChunksStart != uiCurFirstChunk, "No rearrangement possible.");
203 
204  // if the new first active chunk is to the left
205  if (uiSpareChunksStart < uiCurFirstChunk)
206  MoveIndexChunksLeft(uiCurFirstChunk - uiSpareChunksStart);
207  else
208  MoveIndexChunksRight(uiSpareChunksStart - uiCurFirstChunk);
209 
210  EZ_ASSERT_DEBUG(m_uiFirstElement > 0, "Did not achieve the desired effect.");
211  EZ_ASSERT_DEBUG(GetCurMaxCount() >= uiCount, "Did not achieve the desired effect (%i >= %i).", GetCurMaxCount(), uiCount);
212  }
213  else
214  {
215  const ezUInt32 uiReallocSize = 16 + uiRequiredChunks + 16;
216 
217  T** pNewChunksArray = EZ_NEW_RAW_BUFFER(m_pAllocator, T*, uiReallocSize);
218  ezMemoryUtils::ZeroFill(pNewChunksArray, uiReallocSize);
219 
220  const ezUInt32 uiFirstUsedChunk = m_uiFirstElement / CHUNK_SIZE(T);
221 
222  // move all old chunks over
223  ezUInt32 pos = 16;
224 
225  // first the used chunks at the start of the new array
226  for (ezUInt32 i = 0; i < m_uiChunks - uiFirstUsedChunk; ++i)
227  {
228  pNewChunksArray[pos] = m_pChunks[uiFirstUsedChunk + i];
229  ++pos;
230  }
231 
232  m_uiFirstElement -= uiFirstUsedChunk * CHUNK_SIZE(T);
233 
234  // then the unused chunks at the end of the new array
235  for (ezUInt32 i = 0; i < uiFirstUsedChunk; ++i)
236  {
237  pNewChunksArray[pos] = m_pChunks[i];
238  ++pos;
239  }
240 
241  m_uiFirstElement += 16 * CHUNK_SIZE(T);
242 
243  EZ_ASSERT_DEBUG(m_uiFirstElement == (16 * CHUNK_SIZE(T)) + (m_uiFirstElement % CHUNK_SIZE(T)), "");
244 
245 
246  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pChunks);
247  m_pChunks = pNewChunksArray;
248  m_uiChunks = uiReallocSize;
249  }
250 }
251 
252 template <typename T, bool Construct>
254 {
255  ResetReduceSizeCounter();
256 
257  if (IsEmpty())
258  {
259  DeallocateAll();
260  return;
261  }
262 
263  // this will deallocate ALL unused chunks
264  DeallocateUnusedChunks(GetRequiredChunks(m_uiCount));
265 
266  // reduces the size of the index array, but keeps some spare pointers, so that scaling up is still possible without reallocation
267  CompactIndexArray(0);
268 }
269 
270 template <typename T, bool Construct>
271 void ezDequeBase<T, Construct>::CompactIndexArray(ezUInt32 uiMinChunksToKeep)
272 {
273  const ezUInt32 uiRequiredChunks = ezMath::Max<ezUInt32>(1, GetRequiredChunks(m_uiCount));
274  uiMinChunksToKeep = ezMath::Max(uiRequiredChunks, uiMinChunksToKeep);
275 
276  // keep some spare pointers for scaling the deque up again
277  const ezUInt32 uiChunksToKeep = 16 + uiMinChunksToKeep + 16;
278 
279  // only reduce the index array, if we can reduce its size at least to half (the +4 is for the very small cases)
280  if (uiChunksToKeep + 4 >= m_uiChunks / 2)
281  return;
282 
283  T** pNewChunkArray = EZ_NEW_RAW_BUFFER(m_pAllocator, T*, uiChunksToKeep);
284  ezMemoryUtils::ZeroFill<T*>(pNewChunkArray, uiChunksToKeep);
285 
286  const ezUInt32 uiFirstChunk = GetFirstUsedChunk();
287 
288  // makes sure that no more than this amount of chunks is still allocated -> those can be copied over
289  DeallocateUnusedChunks(uiChunksToKeep);
290 
291  // moves the used chunks into the new array
292  for (ezUInt32 i = 0; i < uiRequiredChunks; ++i)
293  {
294  pNewChunkArray[16 + i] = m_pChunks[uiFirstChunk + i];
295  m_pChunks[uiFirstChunk + i] = nullptr;
296  }
297 
298  // copy all still allocated chunks over to the new index array
299  // since we just deallocated enough chunks, all that are found can be copied over as spare chunks
300  {
301  ezUInt32 iPos = 0;
302  for (ezUInt32 i = 0; i < uiFirstChunk; ++i)
303  {
304  if (m_pChunks[i])
305  {
306  EZ_ASSERT_DEBUG(iPos < 16 || ((iPos >= 16 + uiRequiredChunks) && (iPos < uiChunksToKeep)), "Implementation error.");
307 
308  pNewChunkArray[iPos] = m_pChunks[i];
309  m_pChunks[i] = nullptr;
310  ++iPos;
311 
312  if (iPos == 16)
313  iPos += uiRequiredChunks;
314  }
315  }
316 
317  for (ezUInt32 i = GetLastUsedChunk() + 1; i < m_uiChunks; ++i)
318  {
319  if (m_pChunks[i])
320  {
321  EZ_ASSERT_DEBUG(iPos < 16 || ((iPos >= 16 + uiRequiredChunks) && (iPos < uiChunksToKeep)), "Implementation error.");
322 
323  pNewChunkArray[iPos] = m_pChunks[i];
324  m_pChunks[i] = nullptr;
325  ++iPos;
326 
327  if (iPos == 16)
328  iPos += uiRequiredChunks;
329  }
330  }
331  }
332 
333  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pChunks);
334  m_pChunks = pNewChunkArray;
335  m_uiChunks = uiChunksToKeep;
336  m_uiFirstElement = (16 * CHUNK_SIZE(T)) + (m_uiFirstElement % CHUNK_SIZE(T));
337 }
338 
339 template <typename T, bool Construct>
341 {
342  const ezUInt32 uiOldCount = m_uiCount;
343  const ezUInt32 uiNewCount = uiCount;
344 
345  if (uiNewCount > uiOldCount)
346  {
347  // grow the deque
348 
349  RESERVE(uiNewCount);
350  m_uiCount = uiNewCount;
351 
352  if (Construct)
353  {
354  // default construct the new elements
355  for (ezUInt32 i = uiOldCount; i < uiNewCount; ++i)
356  ezMemoryUtils::DefaultConstruct(&ElementAt(i), 1);
357  }
358  else
359  {
360  for (ezUInt32 i = uiOldCount; i < uiNewCount; ++i)
361  ElementAt(i);
362  }
363  }
364  else
365  {
366  if (Construct)
367  {
368  // destruct elements at the end of the deque
369  for (ezUInt32 i = uiNewCount; i < uiOldCount; ++i)
370  ezMemoryUtils::Destruct(&operator[](i), 1);
371  }
372 
373  m_uiCount = uiNewCount;
374 
375  // if enough elements have been destructed, trigger a size reduction (the first time will not deallocate anything though)
376  ReduceSize(uiOldCount - uiNewCount);
377  }
378 }
379 
380 template <typename T, bool Construct>
381 EZ_FORCE_INLINE ezUInt32 ezDequeBase<T, Construct>::GetContiguousRange(ezUInt32 uiIndex) const
382 {
383  EZ_ASSERT_DEV(uiIndex < m_uiCount, "The deque has %i elements. Cannot access element %i.", m_uiCount, uiIndex);
384 
385  const ezUInt32 uiChunkSize = CHUNK_SIZE(T);
386 
387  const ezUInt32 uiRealIndex = m_uiFirstElement + uiIndex;
388  const ezUInt32 uiChunkOffset = uiRealIndex % uiChunkSize;
389 
390  const ezUInt32 uiRange = uiChunkSize - uiChunkOffset;
391 
392  return ezMath::Min(uiRange, GetCount() - uiIndex);
393 }
394 
395 template <typename T, bool Construct>
396 EZ_FORCE_INLINE T& ezDequeBase<T, Construct>::operator[](ezUInt32 uiIndex)
397 {
398  EZ_ASSERT_DEV(uiIndex < m_uiCount, "The deque has %i elements. Cannot access element %i.", m_uiCount, uiIndex);
399 
400  const ezUInt32 uiRealIndex = m_uiFirstElement + uiIndex;
401 
402  const ezUInt32 uiChunkIndex = uiRealIndex / CHUNK_SIZE(T);
403  const ezUInt32 uiChunkOffset= uiRealIndex % CHUNK_SIZE(T);
404 
405  return m_pChunks[uiChunkIndex][uiChunkOffset];
406 }
407 
408 template <typename T, bool Construct>
409 EZ_FORCE_INLINE const T& ezDequeBase<T, Construct>::operator[](ezUInt32 uiIndex) const
410 {
411  EZ_ASSERT_DEV(uiIndex < m_uiCount, "The deque has %i elements. Cannot access element %i.", m_uiCount, uiIndex);
412 
413  const ezUInt32 uiRealIndex = m_uiFirstElement + uiIndex;
414 
415  const ezUInt32 uiChunkIndex = uiRealIndex / CHUNK_SIZE(T);
416  const ezUInt32 uiChunkOffset= uiRealIndex % CHUNK_SIZE(T);
417 
418  return m_pChunks[uiChunkIndex][uiChunkOffset];
419 }
420 
421 template <typename T, bool Construct>
423 {
424  RESERVE(m_uiCount + 1);
425  ++m_uiCount;
426 
427  T* pElement = &ElementAt(m_uiCount - 1);
428 
429  if (Construct)
430  ezMemoryUtils::DefaultConstruct(pElement, 1);
431 
432  return *pElement;
433 }
434 
435 template <typename T, bool Construct>
437 {
438  RESERVE(m_uiCount + 1);
439  ++m_uiCount;
440 
441  T* pElement = &ElementAt(m_uiCount - 1);
442 
443  if (Construct)
444  ezMemoryUtils::DefaultConstruct(pElement, 1);
445 }
446 
447 template <typename T, bool Construct>
448 EZ_FORCE_INLINE void ezDequeBase<T, Construct>::PushBack(const T& element)
449 {
450  EZ_CHECK_AT_COMPILETIME_MSG(Construct, "This function is not supported on Deques that do not construct their data.");
451 
452  RESERVE(m_uiCount + 1);
453  ++m_uiCount;
454 
455  ezMemoryUtils::CopyConstruct(&ElementAt(m_uiCount - 1), element, 1);
456 }
457 
458 template <typename T, bool Construct>
459 EZ_FORCE_INLINE void ezDequeBase<T, Construct>::PopBack(ezUInt32 uiElements)
460 {
461  EZ_ASSERT_DEV(uiElements <= GetCount(), "Cannot remove %i elements, the deque only contains %i elements.", uiElements, GetCount());
462 
463  for (ezUInt32 i = 0; i < uiElements; ++i)
464  {
465  if (Construct)
466  ezMemoryUtils::Destruct(&operator[](m_uiCount - 1), 1);
467 
468  --m_uiCount;
469  }
470 
471  // might trigger a memory reduction
472  REDUCE_SIZE(uiElements);
473 }
474 
475 template <typename T, bool Construct>
476 EZ_FORCE_INLINE void ezDequeBase<T, Construct>::PushFront(const T& element)
477 {
478  EZ_CHECK_AT_COMPILETIME_MSG(Construct, "This function is not supported on Deques that do not construct their data.");
479 
480  RESERVE(m_uiCount + 1);
481  ++m_uiCount;
482  --m_uiFirstElement;
483 
484  ezMemoryUtils::CopyConstruct(&ElementAt(0), &element, 1);
485 }
486 
487 template <typename T, bool Construct>
489 {
490  RESERVE(m_uiCount + 1);
491  ++m_uiCount;
492  --m_uiFirstElement;
493 
494  T* pElement = &ElementAt(0);
495 
496  if (Construct)
497  ezMemoryUtils::Construct(pElement, 1);
498 }
499 
500 template <typename T, bool Construct>
501 EZ_FORCE_INLINE void ezDequeBase<T, Construct>::PopFront(ezUInt32 uiElements)
502 {
503  EZ_ASSERT_DEV(uiElements <= GetCount(), "Cannot remove %i elements, the deque only contains %i elements.", uiElements, GetCount());
504 
505  for (ezUInt32 i = 0; i < uiElements; ++i)
506  {
507  if (Construct)
508  ezMemoryUtils::Destruct(&operator[](0), 1);
509 
510  --m_uiCount;
511  ++m_uiFirstElement;
512  }
513 
514  // might trigger a memory reduction
515  REDUCE_SIZE(uiElements);
516 }
517 
518 template <typename T, bool Construct>
519 EZ_FORCE_INLINE bool ezDequeBase<T, Construct>::IsEmpty() const
520 {
521  return m_uiCount == 0;
522 }
523 
524 template <typename T, bool Construct>
525 EZ_FORCE_INLINE ezUInt32 ezDequeBase<T, Construct>::GetCount() const
526 {
527  return m_uiCount;
528 }
529 
530 template <typename T, bool Construct>
531 EZ_FORCE_INLINE const T& ezDequeBase<T, Construct>::PeekFront() const
532 {
533  return operator[](0);
534 }
535 
536 template <typename T, bool Construct>
538 {
539  return operator[](0);
540 }
541 
542 template <typename T, bool Construct>
543 EZ_FORCE_INLINE const T& ezDequeBase<T, Construct>::PeekBack() const
544 {
545  return operator[](m_uiCount - 1);
546 }
547 
548 template <typename T, bool Construct>
550 {
551  return operator[](m_uiCount - 1);
552 }
553 
554 template <typename T, bool Construct>
555 EZ_FORCE_INLINE bool ezDequeBase<T, Construct>::Contains(const T& value) const
556 {
557  return IndexOf(value) != ezInvalidIndex;
558 }
559 
560 template <typename T, bool Construct>
561 ezUInt32 ezDequeBase<T, Construct>::IndexOf(const T& value, ezUInt32 uiStartIndex) const
562 {
563  for (ezUInt32 i = uiStartIndex; i < m_uiCount; ++i)
564  {
565  if (ezMemoryUtils::IsEqual(&operator[](i), &value))
566  return i;
567  }
568 
569  return ezInvalidIndex;
570 }
571 
572 template <typename T, bool Construct>
573 ezUInt32 ezDequeBase<T, Construct>::LastIndexOf(const T& value, ezUInt32 uiStartIndex) const
574 {
575  for (ezUInt32 i = ezMath::Min(uiStartIndex, m_uiCount); i-- > 0;)
576  {
577  if (ezMemoryUtils::IsEqual(&operator[](i), &value))
578  return i;
579  }
580  return ezInvalidIndex;
581 }
582 
583 template <typename T, bool Construct>
585 {
586  EZ_CHECK_AT_COMPILETIME_MSG(Construct, "This function is not supported on Deques that do not construct their data.");
587 
588  EZ_ASSERT_DEV(uiIndex < m_uiCount, "Cannot remove element %i, the deque only contains %i elements.", uiIndex, m_uiCount);
589 
590  if (uiIndex + 1 < m_uiCount) // do not copy over the same element, if uiIndex is actually the last element
591  operator[](uiIndex) = PeekBack();
592 
593  PopBack();
594 }
595 
596 template <typename T, bool Construct>
597 EZ_FORCE_INLINE void ezDequeBase<T, Construct>::MoveIndexChunksLeft(ezUInt32 uiChunkDiff)
598 {
599  const ezUInt32 uiCurFirstChunk = GetFirstUsedChunk();
600  const ezUInt32 uiRemainingChunks = m_uiChunks - uiCurFirstChunk;
601  const ezUInt32 uiNewFirstChunk = uiCurFirstChunk - uiChunkDiff;
602 
603  // ripple the chunks from the back to the front (in place)
604  for (ezUInt32 front = 0; front < uiRemainingChunks; ++front)
605  ezMath::Swap(m_pChunks[uiNewFirstChunk + front], m_pChunks[front + uiCurFirstChunk]);
606 
607  // just ensures that the following subtraction is possible
608  EZ_ASSERT_DEBUG(m_uiFirstElement > uiChunkDiff * CHUNK_SIZE(T), "");
609 
610  // adjust which element is the first by how much the index array has been moved
611  m_uiFirstElement -= uiChunkDiff * CHUNK_SIZE(T);
612 }
613 
614 template <typename T, bool Construct>
615 EZ_FORCE_INLINE void ezDequeBase<T, Construct>::MoveIndexChunksRight(ezUInt32 uiChunkDiff)
616 {
617  const ezUInt32 uiCurFirstChunk = GetFirstUsedChunk();
618  const ezUInt32 uiLastChunk = (m_uiCount == 0) ? (m_uiFirstElement / CHUNK_SIZE(T)) : ((m_uiFirstElement + m_uiCount - 1) / CHUNK_SIZE(T));
619  const ezUInt32 uiCopyChunks = (uiLastChunk - uiCurFirstChunk) + 1;
620 
621  // ripple the chunks from the front to the back (in place)
622  for (ezUInt32 i = 0; i < uiCopyChunks; ++i)
623  ezMath::Swap(m_pChunks[uiLastChunk - i], m_pChunks[uiLastChunk + uiChunkDiff - i]);
624 
625  // adjust which element is the first by how much the index array has been moved
626  m_uiFirstElement += uiChunkDiff * CHUNK_SIZE(T);
627 }
628 
629 template <typename T, bool Construct>
630 EZ_FORCE_INLINE ezUInt32 ezDequeBase<T, Construct>::GetFirstUsedChunk() const
631 {
632  return m_uiFirstElement / CHUNK_SIZE(T);
633 }
634 
635 template <typename T, bool Construct>
636 EZ_FORCE_INLINE ezUInt32 ezDequeBase<T, Construct>::GetLastUsedChunk(ezUInt32 uiAtSize) const
637 {
638  if (uiAtSize == 0)
639  return GetFirstUsedChunk();
640 
641  return (m_uiFirstElement + uiAtSize - 1) / CHUNK_SIZE(T);
642 }
643 
644 template <typename T, bool Construct>
645 EZ_FORCE_INLINE ezUInt32 ezDequeBase<T, Construct>::GetLastUsedChunk() const
646 {
647  return GetLastUsedChunk(m_uiCount);
648 }
649 
650 template <typename T, bool Construct>
651 EZ_FORCE_INLINE ezUInt32 ezDequeBase<T, Construct>::GetRequiredChunks(ezUInt32 uiAtSize) const
652 {
653  if (uiAtSize == 0)
654  return 0;
655 
656  return GetLastUsedChunk(uiAtSize) - GetFirstUsedChunk() + 1;
657 }
658 
659 template <typename T, bool Construct>
661 {
662  if (m_uiAllocatedChunks <= uiMaxChunks)
663  return;
664 
665  // check all unused chunks at the end, deallocate all that are allocated
666  for (ezUInt32 i = GetLastUsedChunk() + 1; i < m_uiChunks; ++i)
667  {
668  if (m_pChunks[i])
669  {
670  --m_uiAllocatedChunks;
671  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pChunks[i]);
672 
673  if (m_uiAllocatedChunks <= uiMaxChunks)
674  return;
675  }
676  }
677 
678  // check all unused chunks at the front, deallocate all that are allocated
679  const ezUInt32 uiFirstChunk = GetFirstUsedChunk();
680 
681  for (ezUInt32 i = 0; i < uiFirstChunk; ++i)
682  {
683  if (m_pChunks[i])
684  {
685  --m_uiAllocatedChunks;
686  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pChunks[i]);
687 
688  if (m_uiAllocatedChunks <= uiMaxChunks)
689  return;
690  }
691  }
692 }
693 
694 template <typename T, bool Construct>
696 {
697  m_iReduceSizeTimer = CHUNK_SIZE(T) * 8; // every time 8 chunks might be unused -> check whether to reduce the deque's size
698 }
699 
700 template <typename T, bool Construct>
702 {
703  m_iReduceSizeTimer -= iReduction;
704 
705  // only trigger the size reduction every once in a while (after enough size reduction that actually a few chunks might be unused)
706  if (m_iReduceSizeTimer > 0)
707  return;
708 
709  ResetReduceSizeCounter();
710 
711  // we keep this amount of chunks
712  // m_uiMaxCount will be adjusted over time
713  // if the deque is shrunk and operates in this state long enough, m_uiMaxCount will be reduced more and more
714  const ezUInt32 uiMaxChunks = (m_uiMaxCount / CHUNK_SIZE(T)) + 3; // +1 because of rounding, +2 spare chunks
715 
716  EZ_ASSERT_DEBUG(uiMaxChunks >= GetRequiredChunks(m_uiCount), "Implementation Error.");
717 
718  DeallocateUnusedChunks(uiMaxChunks);
719 
720  // lerp between the current MaxCount and the actually active number of elements
721  // m_uiMaxCount is never smaller than m_uiCount, but m_uiCount might be smaller
722  // thus m_uiMaxCount might be reduced over time
723  m_uiMaxCount = ezMath::Max(m_uiCount, (m_uiMaxCount / 2) + (m_uiCount / 2));
724 
725  // Should we really adjust the size of the index array here?
726  CompactIndexArray(uiMaxChunks);
727 }
728 
729 template <typename T, bool Construct>
730 EZ_FORCE_INLINE ezUInt32 ezDequeBase<T, Construct>::GetCurMaxCount() const
731 {
732  return m_uiChunks * CHUNK_SIZE(T) - m_uiFirstElement;
733 }
734 
735 template <typename T, bool Construct>
737 {
738  // first search for an unused, but already allocated, chunk and reuse it, if possible
739  const ezUInt32 uiCurFirstChunk = GetFirstUsedChunk();
740 
741  // search the unused blocks at the start
742  for (ezUInt32 i = 0; i < uiCurFirstChunk; ++i)
743  {
744  if (m_pChunks[i])
745  {
746  T* pChunk = m_pChunks[i];
747  m_pChunks[i] = nullptr;
748  return pChunk;
749  }
750  }
751 
752  const ezUInt32 uiCurLastChunk = GetLastUsedChunk();
753 
754  // search the unused blocks at the end
755  for (ezUInt32 i = m_uiChunks - 1; i > uiCurLastChunk; --i)
756  {
757  if (m_pChunks[i])
758  {
759  T* pChunk = m_pChunks[i];
760  m_pChunks[i] = nullptr;
761  return pChunk;
762  }
763  }
764 
765  // nothing unused found, allocate a new block
766  ResetReduceSizeCounter();
767  ++m_uiAllocatedChunks;
768  return EZ_NEW_RAW_BUFFER(m_pAllocator, T, CHUNK_SIZE(T));
769 }
770 
771 template <typename T, bool Construct>
773 {
774  EZ_ASSERT_DEV(uiIndex < m_uiCount, "");
775 
776  const ezUInt32 uiRealIndex = m_uiFirstElement + uiIndex;
777 
778  const ezUInt32 uiChunkIndex = uiRealIndex / CHUNK_SIZE(T);
779  const ezUInt32 uiChunkOffset= uiRealIndex % CHUNK_SIZE(T);
780 
781  EZ_ASSERT_DEBUG(uiChunkIndex < m_uiChunks, "");
782 
783  if (m_pChunks[uiChunkIndex] == nullptr)
784  m_pChunks[uiChunkIndex] = GetUnusedChunk();
785 
786  return m_pChunks[uiChunkIndex][uiChunkOffset];
787 }
788 
789 template <typename T, bool Construct>
791 {
792  Clear();
793 
794  ezUInt32 i = 0;
795  while (m_uiAllocatedChunks > 0)
796  {
797  if (m_pChunks[i])
798  {
799  --m_uiAllocatedChunks;
800  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pChunks[i]);
801  }
802 
803  ++i;
804  }
805 
806  EZ_DELETE_RAW_BUFFER(m_pAllocator, m_pChunks);
807 
808  Constructor(m_pAllocator);
809 }
810 
811 template <typename T, bool Construct>
813 {
814  EZ_CHECK_AT_COMPILETIME_MSG(Construct, "This function is not supported on Deques that do not construct their data.");
815 
816  EZ_ASSERT_DEV(uiIndex < m_uiCount, "Out of bounds access. Array has %i elements, trying to remove element at index %i.", m_uiCount, uiIndex);
817 
818  for (ezUInt32 i = uiIndex + 1; i < m_uiCount; ++i)
819  ezMemoryUtils::CopyOverlapped(&operator[](i - 1), &operator[](i), 1);
820 
821  PopBack();
822 }
823 
824 template <typename T, bool Construct>
826 {
827  EZ_CHECK_AT_COMPILETIME_MSG(Construct, "This function is not supported on Deques that do not construct their data.");
828 
829  ezUInt32 uiIndex = IndexOf(value);
830 
831  if (uiIndex == ezInvalidIndex)
832  return false;
833 
834  RemoveAt(uiIndex);
835  return true;
836 }
837 
838 template <typename T, bool Construct>
840 {
841  EZ_CHECK_AT_COMPILETIME_MSG(Construct, "This function is not supported on Deques that do not construct their data.");
842 
843  ezUInt32 uiIndex = IndexOf(value);
844 
845  if (uiIndex == ezInvalidIndex)
846  return false;
847 
848  RemoveAtSwap(uiIndex);
849  return true;
850 }
851 
852 template <typename T, bool Construct>
853 void ezDequeBase<T, Construct>::Insert(const T& value, ezUInt32 uiIndex)
854 {
855  EZ_CHECK_AT_COMPILETIME_MSG(Construct, "This function is not supported on Deques that do not construct their data.");
856 
857  // Index 0 inserts before the first element, Index m_uiCount inserts after the last element.
858  EZ_ASSERT_DEV(uiIndex <= m_uiCount, "The deque has %i elements. Cannot insert an element at index %i.", m_uiCount, uiIndex);
859 
860  PushBack();
861 
862  for (ezUInt32 i = m_uiCount - 1; i > uiIndex; --i)
863  ezMemoryUtils::Copy(&operator[](i), &operator[](i - 1), 1);
864 
865  ezMemoryUtils::Copy(&operator[](uiIndex), &value, 1);
866 }
867 
868 template <typename T, bool Construct>
869 template <typename Comparer>
870 void ezDequeBase<T, Construct>::Sort(const Comparer& comparer)
871 {
872  if (m_uiCount > 1)
873  ezSorting::QuickSort(*this, comparer);
874 }
875 
876 template <typename T, bool Construct>
878 {
879  if (m_uiCount > 1)
881 }
882 
883 template <typename T, bool Construct>
885 {
886  if (m_pChunks == nullptr)
887  return 0;
888 
889  ezUInt64 res = m_uiChunks * sizeof(T*);
890 
891  for (ezUInt32 i = 0; i < m_uiChunks; ++i)
892  {
893  if (m_pChunks[i] != nullptr)
894  {
895  res += (ezUInt64) (CHUNK_SIZE(T)) * (ezUInt64) sizeof(T);
896  }
897  }
898 
899  return res;
900 }
901 
902 #undef REDUCE_SIZE
903 #undef RESERVE
904 
905 
906 template <typename T, typename A, bool Construct>
907 ezDeque<T, A, Construct>::ezDeque() : ezDequeBase<T, Construct>(A::GetAllocator())
908 {
909 }
910 
911 template <typename T, typename A, bool Construct>
912 ezDeque<T, A, Construct>::ezDeque(ezAllocatorBase* pAllocator) : ezDequeBase<T, Construct>(pAllocator)
913 {
914 }
915 
916 template <typename T, typename A, bool Construct>
917 ezDeque<T, A, Construct>::ezDeque(const ezDeque<T, A, Construct>& other) : ezDequeBase<T, Construct>(other, A::GetAllocator())
918 {
919 }
920 
921 template <typename T, typename A, bool Construct>
922 ezDeque<T, A, Construct>::ezDeque(ezDeque<T, A, Construct>&& other) : ezDequeBase<T, Construct>(std::move(other), A::GetAllocator())
923 {
924 }
925 
926 template <typename T, typename A, bool Construct>
927 ezDeque<T, A, Construct>::ezDeque(const ezDequeBase<T, Construct>& other) : ezDequeBase<T, Construct>(other, A::GetAllocator())
928 {
929 }
930 
931 template <typename T, typename A, bool Construct>
932 ezDeque<T, A, Construct>::ezDeque(ezDequeBase<T, Construct>&& other) : ezDequeBase<T, Construct>(std::move(other), A::GetAllocator())
933 {
934 }
935 
936 template <typename T, typename A, bool Construct>
938 {
940 }
941 
942 template <typename T, typename A, bool Construct>
944 {
945  ezDequeBase<T, Construct>::operator=(std::move(rhs));
946 }
947 
948 template <typename T, typename A, bool Construct>
950 {
952 }
953 
954 template <typename T, typename A, bool Construct>
956 {
957  ezDequeBase<T, Construct>::operator=(std::move(rhs));
958 }
959 
960