Nebula
Loading...
Searching...
No Matches
queue.h
Go to the documentation of this file.
1#pragma once
2//------------------------------------------------------------------------------
12#include "core/types.h"
13#include "math/scalar.h"
14#include "util/round.h"
15#include <type_traits>
16
17#if (__cplusplus >= 201703L ) || (_MSVC_LANG >= 201703L)
18#define IFCONSTEXPR if constexpr
19#else
20#define IFCONSTEXPR if
21#endif
22
23
24//------------------------------------------------------------------------------
25namespace Util
26{
27template<class TYPE> class Queue
28{
29public:
35 Queue(const Queue<TYPE>& rhs);
38
40 void operator=(const Queue<TYPE>& rhs);
44 TYPE& operator[](IndexT index) const;
46 bool operator==(const Queue<TYPE>& rhs) const;
48 bool operator!=(const Queue<TYPE>& rhs) const;
50 void Reserve(SizeT num);
52 void Grow();
54 SizeT Size() const;
56 SizeT Capacity() const;
58 bool IsEmpty() const;
60 void Clear();
62 bool Contains(const TYPE& e) const;
64 void EraseIndex(const IndexT i);
65
67 void Enqueue(const TYPE& e);
68 void Enqueue(TYPE&& e);
70 TYPE Dequeue();
72 TYPE& Peek() const;
73
74protected:
75 template<typename X>
76 __forceinline
77 typename std::enable_if<std::is_trivially_destructible<X>::value == false>::type
79 {
80 this->data[idx].~X();
81 }
82
83 template<typename X>
84 __forceinline
85 typename std::enable_if<std::is_trivially_destructible<X>::value == true>::type
87 {
88 // empty
89 }
90
91 template<typename X>
92 __forceinline
93 typename std::enable_if<std::is_trivially_destructible<X>::value == false>::type
95 {
96 for (IndexT i = 0; i < this->size; i++)
97 {
98 this->data[this->MapIndex(i)].~X();
99 }
100 }
101
102 template<typename X>
103 __forceinline
104 typename std::enable_if<std::is_trivially_destructible<X>::value == true>::type
106 {
107 // empty
108 }
109
111 IndexT MapIndex(IndexT index) const;
112 TYPE * data;
113
114 static const SizeT MinGrowSize = 16;
115 static const SizeT MaxGrowSize = 65536;
120};
121
122//------------------------------------------------------------------------------
125template<class TYPE>
127 data(nullptr),
128 grow(16),
129 start(0),
130 size(0),
131 capacity(0)
132{
133 // empty
134}
135
136//------------------------------------------------------------------------------
139template<class TYPE>
141{
142 if (this->data)
143 {
144 this->Clear();
145 delete[] this->data;
146 }
147 this->data = nullptr;
148}
149
150
151//------------------------------------------------------------------------------
154template<class TYPE>
156 data(nullptr),
157 capacity(0)
158{
159 this->Reserve(rhs.size);
160 for (IndexT i = 0; i < rhs.size; i++)
161 {
162 this->data[i] = rhs[i];
163 }
164 this->size = rhs.size;
165 this->grow = rhs.grow;
166 this->start = 0;
167}
168
169//------------------------------------------------------------------------------
172template<class TYPE>
174 data(rhs.data),
175 capacity(rhs.capacity),
176 size(rhs.size),
177 grow(rhs.grow),
178 start(rhs.start)
179{
180 rhs.data = nullptr;
181 rhs.capacity = 0;
182 rhs.size = 0;
183}
184
185//------------------------------------------------------------------------------
188template<class TYPE>
189void
191{
192 if (this != &rhs)
193 {
194 this->Reserve(rhs.size);
195 for (IndexT i = 0; i < rhs.size; i++)
196 {
197 this->data[i] = rhs[i];
198 }
199 this->size = rhs.size;
200 this->grow = rhs.grow;
201 this->start = 0;
202 }
203}
204
205//------------------------------------------------------------------------------
208template<class TYPE>
209void
211{
212 if (this != &rhs)
213 {
214 this->data = rhs.data;
215 this->size = rhs.size;
216 this->grow = rhs.grow;
217 this->capacity = rhs.capacity;
218 this->start = rhs.start;
219 rhs.data = nullptr;
220 rhs.size = 0;
221 }
222}
223
224//------------------------------------------------------------------------------
227template<class TYPE>
228__forceinline
229TYPE&
231{
232 n_assert(index < this->size);
233 return this->data[MapIndex(index)];
234}
235
236//------------------------------------------------------------------------------
239template<class TYPE>
240bool
242{
243 if(this->size != rhs.size) return false;
244
245 for(IndexT i= 0; i < this->size; i++)
246 {
247 if(!((*this)[i] == rhs[i] ))
248 {
249 return false;
250 }
251 }
252 return true;
253}
254
255//------------------------------------------------------------------------------
258template<class TYPE>
259bool
261{
262 return ! this->operator==(rhs);
263}
264
265//------------------------------------------------------------------------------
268template<class TYPE>
269bool
270Queue<TYPE>::Contains(const TYPE& e) const
271{
272 for(IndexT i = 0 ; i<this->size; i++)
273 {
274 if (this->operator[](i) == e)
275 return true;
276 }
277 return false;
278}
279
280//------------------------------------------------------------------------------
283template<class TYPE>
284void
286{
287 n_assert(i < this->size);
288
289 if (i == 0)
290 {
291 this->Dequeue();
292 }
293 else
294 {
295 IndexT idx = this->MapIndex(i);
296
297 this->DestroyElement<TYPE>(idx);
298
299 // check if wrapped around
300 if (idx < this->start)
301 {
302 for (IndexT j = 0; j < this->size - i; ++j)
303 {
304 this->data[idx] = this->data[idx+1];
305 idx++;
306 }
307 }
308 else
309 {
310 for (IndexT j = 0; j < i; j++)
311 {
312 this->data[idx] = this->data[idx-1];
313 --idx;
314 }
315 this->start = this->MapIndex(1);
316 }
317 --this->size;
318 }
319}
320
321//------------------------------------------------------------------------------
324template<class TYPE>
325void
327{
328 this->ClearAll<TYPE>();
329 this->size = 0;
330 this->start = 0;
331}
332
333//------------------------------------------------------------------------------
336template<class TYPE>
337void
339{
340 if (num > this->capacity)
341 {
342 // round up to next multiple of 64
343 num = num<64? num: Util::Round::RoundUp(num, 64);
344
345 TYPE * newdata = new TYPE[num];
346
347 // check if empty
348 if (this->capacity > 0)
349 {
350 // we could use SFINAE here as well, but as its a single if in a (rare) call its not worth the bother
351 IFCONSTEXPR(std::is_trivially_copyable_v<TYPE>)
352 {
353 if (this->size > 0)
354 {
355 SizeT upper = this->capacity - this->start;
356 SizeT lower = this->size - (this->capacity - this->start);
357
358 if (lower < 0)
359 {
360 Memory::Copy(&this->data[this->start], newdata, this->size * sizeof(TYPE));
361 }
362 else
363 {
364 Memory::Copy(&this->data[this->start], newdata, upper * sizeof(TYPE));
365 Memory::Copy(this->data, &newdata[upper], lower * sizeof(TYPE));
366 }
367 }
368 if (this->data != nullptr)
369 {
370 delete[] this->data;
371 }
372 }
373 else
374 {
375 for (IndexT i = 0; i < this->size; i++)
376 {
377 IndexT idx = this->MapIndex(i);
378 newdata[i] = std::move(this->data[idx]);
379 this->DestroyElement<TYPE>(idx);
380 }
381 if (this->data != nullptr)
382 {
383 delete[] this->data;
384 }
385 }
386 }
387 this->data = newdata;
388 this->capacity = num;
389 this->start = 0;
390 }
391}
392
393//------------------------------------------------------------------------------
396template<class TYPE> void
398{
399 SizeT growToSize;
400 if (0 == this->capacity)
401 {
402 growToSize = this->grow;
403 }
404 else
405 {
406 // grow by half of the current capacity, but never more then MaxGrowSize
407 SizeT growBy = this->capacity >> 1;
408
409 if (growBy == 0)
410 {
411 growBy = MinGrowSize;
412 }
413 else if (growBy > MaxGrowSize)
414 {
415 growBy = MaxGrowSize;
416 }
417 growToSize = this->capacity + growBy;
418 }
419 this->Reserve(growToSize);
420}
421
422//------------------------------------------------------------------------------
425template<class TYPE>
426__forceinline
427SizeT
429{
430 return this->size;
431}
432
433//------------------------------------------------------------------------------
436template<class TYPE>
437__forceinline
438SizeT
440{
441 return this->capacity;
442}
443
444//------------------------------------------------------------------------------
447template<class TYPE>
448__forceinline
449bool
451{
452 return this->size == 0;
453}
454
455//------------------------------------------------------------------------------
458template<class TYPE>
459__forceinline
460void
462{
463 if (this->size == this->capacity)
464 {
465 this->Grow();
466 }
467 this->data[this->MapIndex(this->size++)] = e;
468}
469
470//------------------------------------------------------------------------------
473template<class TYPE>
474__forceinline
475void
477{
478 if (this->size == this->capacity)
479 {
480 this->Grow();
481 }
482
483 this->data[this->MapIndex(this->size++)]= std::move(e);
484}
485
486//------------------------------------------------------------------------------
489template<class TYPE>
490__forceinline
491TYPE
493{
494 n_assert(this->size > 0);
495
496 TYPE t = this->data[this->start];
497 #if __cplusplus > 201703L
498 if constexpr (!std::is_nothrow_destructible_v<TYPE>)
499 {
500 (&(this->data[this->start]))->~TYPE();
501 }
502 #else
503 this->DestroyElement<TYPE>(this->start);
504 #endif
505 this->start = this->MapIndex(1);
506 --this->size;
507 return t;
508}
509
510//------------------------------------------------------------------------------
513template<class TYPE>
514__forceinline
515TYPE&
517{
518 n_assert(this->size > 0);
519 return this->data[this->start];
520}
521
522//------------------------------------------------------------------------------
528template<class TYPE>
529__forceinline
530IndexT
532{
533 idx = (idx + this->start) % this->capacity;
534 if (idx > 0)
535 {
536 return idx;
537 }
538 else
539 {
540 return (idx + this->capacity) % this->capacity;
541 }
542}
543
544
545} // namespace Util
546//------------------------------------------------------------------------------
Nebula's queue class (a FIFO container).
Definition queue.h:28
Queue(Queue< TYPE > &&rhs)
move constructor
Definition queue.h:173
void Enqueue(const TYPE &e)
add element to the back of the Dequeue, can trigger grow
Definition queue.h:461
bool Contains(const TYPE &e) const
return true if Dequeue contains element
Definition queue.h:270
void Enqueue(TYPE &&e)
Definition queue.h:476
__forceinline std::enable_if< std::is_trivially_destructible< X >::value==true >::type DestroyElement(IndexT idx)
Definition queue.h:86
static const SizeT MinGrowSize
Definition queue.h:114
SizeT capacity
Definition queue.h:119
bool operator!=(const Queue< TYPE > &rhs) const
inequality operator
Definition queue.h:260
bool operator==(const Queue< TYPE > &rhs) const
equality operator
Definition queue.h:241
SizeT size
Definition queue.h:118
void Clear()
remove all elements from the Dequeue
Definition queue.h:326
__forceinline std::enable_if< std::is_trivially_destructible< X >::value==true >::type ClearAll()
Definition queue.h:105
void Grow()
grow Dequeue by internal growing rules (slow)
Definition queue.h:397
~Queue()
destructor
Definition queue.h:140
void operator=(Queue< TYPE > &&rhs)
move assignment operator
Definition queue.h:210
Queue()
constructor
Definition queue.h:126
Queue(const Queue< TYPE > &rhs)
copy constructor
Definition queue.h:155
SizeT Capacity() const
returns allocation of elements in the Dequeue
Definition queue.h:439
void EraseIndex(const IndexT i)
erase element at index (slow!!)
bool IsEmpty() const
return true if Dequeue is empty
Definition queue.h:450
TYPE * data
Definition queue.h:112
__forceinline std::enable_if< std::is_trivially_destructible< X >::value==false >::type DestroyElement(IndexT idx)
Definition queue.h:78
void operator=(const Queue< TYPE > &rhs)
assignment operator
Definition queue.h:190
__forceinline std::enable_if< std::is_trivially_destructible< X >::value==false >::type ClearAll()
Definition queue.h:94
SizeT grow
Definition queue.h:116
static const SizeT MaxGrowSize
Definition queue.h:115
void Reserve(SizeT num)
increase capacity to fit N more elements into the Dequeue (slow)
Definition queue.h:338
TYPE & Peek() const
access to element at front of Dequeue without removing it
Definition queue.h:516
SizeT start
Definition queue.h:117
TYPE Dequeue()
remove the element from the front of the Dequeue
Definition queue.h:492
IndexT MapIndex(IndexT index) const
maps index to actual item position using wrapping
Definition queue.h:531
TYPE & operator[](IndexT index) const
access element by index, 0 is the frontmost element (next to be dequeued)
Definition queue.h:230
SizeT Size() const
returns number of elements in the Dequeue
Definition queue.h:428
static uint RoundUp(uint val, uint boundary)
generic roundup
Definition round.h:83
#define n_assert(exp)
Definition debug.h:50
void Copy(const void *from, void *to, size_t numBytes)
Copy a chunk of memory (note the argument order is different from memcpy()!!!)
Definition osxmemory.cc:213
Math::float2 size
Definition histogramcontext.cc:36
A pinned array is an array which manages its own virtual memory.
Definition String.cs:6
bool operator==(const String &a, const String &b)
Definition string.cc:830
#define IFCONSTEXPR
Definition queue.h:20
Nebula's scalar datatype.
int SizeT
Definition types.h:49
int IndexT
Definition types.h:48