Nebula
Loading...
Searching...
No Matches
idpool.h
Go to the documentation of this file.
1#pragma once
2//------------------------------------------------------------------------------
19//------------------------------------------------------------------------------
20#include <cstdint>
21#include "core/types.h"
22#include "util/array.h"
23#include "math/scalar.h"
24#include <functional>
25
26namespace Ids
27{
28class IdPool
29{
30public:
32 IdPool();
34 IdPool(const uint max, const uint grow = 512);
36 ~IdPool();
37
39 uint Alloc();
41 void Dealloc(uint id);
43 void Reserve(uint numIds);
45 uint GetNumUsed() const;
47 uint GetNumFree() const;
49 void ForEachFree(const std::function<void(uint, uint)> fun, SizeT num);
51 void Move(uint lhs, uint rhs);
53 const uint GetGrow() const;
54private:
55
59};
60
61//------------------------------------------------------------------------------
64inline
66 maxId(0xFFFFFFFF), // int max
67 grow(512)
68{
69 // empty
70}
71
72//------------------------------------------------------------------------------
75inline
76IdPool::IdPool(const uint max, const uint grow) :
77 maxId(max),
78 grow(grow)
79{
80 // empty
81}
82
83//------------------------------------------------------------------------------
86inline
88{
89 // empty
90}
91
92//------------------------------------------------------------------------------
95inline uint
97{
98 // if we're out of ids, allocate more, but with a controlled grow (not log2 as per Array)
99 if (this->free.Size() == 0)
100 {
101 // calculate how many more indices we are allowed to get
102 SizeT growTo = Math::min(this->maxId, this->grow);
103 SizeT oldCapacity = this->free.Capacity();
104
105 // make sure we don't allocate too many indices
106 n_assert2((uint)(oldCapacity + growTo) < this->maxId, "Pool is full! Be careful with how much you allocate!\n");
107
108 // reserve more space for new Ids
109 this->free.Reserve(oldCapacity + growTo);
110 IndexT i;
111 for (i = this->free.Capacity()-1; i >= oldCapacity; i--)
112 {
113 // count backwards from the max id
114 this->free.Append(this->maxId - i);
115 }
116 }
117
118 // if we do an inverse erase, we don't have to move elements, and since we know the max id, subtract it
119 uint id = this->maxId - this->free.Back();
120 this->free.EraseIndex(this->free.Size() - 1);
121 return id;
122}
123
124//------------------------------------------------------------------------------
127inline void
129{
130 this->free.Append(this->maxId - id);
131}
132
133//------------------------------------------------------------------------------
136inline void
138{
139 this->maxId = numIds;
140 this->free.Reserve(numIds);
141 for (int i = numIds - 1; i >= 0; i--)
142 {
143 this->free.Append(this->maxId - i);
144 }
145}
146
147//------------------------------------------------------------------------------
150inline uint
152{
153 return this->free.Capacity() - this->free.Size();
154}
155
156//------------------------------------------------------------------------------
159inline uint
161{
162 return this->free.Size();
163}
164
165//------------------------------------------------------------------------------
168inline void
169IdPool::ForEachFree(const std::function<void(uint, uint)> fun, SizeT num)
170{
171 SizeT size = this->free.Size();
172 for (IndexT i = size - 1; i >= 0; i--)
173 {
174 const uint id = this->maxId - this->free[i];
175 if (id < (uint)num)
176 {
177 fun(id, i);
178 num--;
179 }
180 }
181}
182
183//------------------------------------------------------------------------------
186inline void
188{
189 this->free.Append(this->maxId - id);
190 this->free.EraseIndex(idx);
191}
192
193//------------------------------------------------------------------------------
196inline const uint
198{
199 return this->grow;
200}
201
202} // namespace Ids
Definition idpool.h:29
~IdPool()
destructor
Definition idpool.h:87
void Move(uint lhs, uint rhs)
frees up lhs and erases rhs
Definition idpool.h:187
Util::Array< uint > free
Definition idpool.h:56
IdPool()
constructor
Definition idpool.h:65
uint GetNumFree() const
get number of free elements
Definition idpool.h:160
const uint GetGrow() const
get grow
Definition idpool.h:197
uint maxId
Definition idpool.h:57
uint GetNumUsed() const
get number of active ids
Definition idpool.h:151
void ForEachFree(const std::function< void(uint, uint)> fun, SizeT num)
iterate free indices
Definition idpool.h:169
uint Alloc()
get new id
Definition idpool.h:96
uint grow
Definition idpool.h:58
void Reserve(uint numIds)
reserve ids
Definition idpool.h:137
void Dealloc(uint id)
free id
Definition idpool.h:128
Nebula's dynamic array class.
Definition array.h:60
void Reserve(SizeT num)
increase capacity to fit N more elements into the array.
Definition array.h:862
TYPE & Back() const
return reference to last element
Definition array.h:993
const SizeT Capacity() const
get overall allocated size of array in number of elements
Definition array.h:900
void Append(const TYPE &first, const ELEM_TYPE &... elements)
Append multiple elements to the end of the array.
Definition array.h:1334
void EraseIndex(IndexT index)
erase element at index, keep sorting intact
Definition array.h:1036
const SizeT Size() const
get number of elements in array
Definition array.h:880
#define n_assert2(exp, msg)
Definition debug.h:51
This simple Id pool implements a set of free and used consecutive integers.
Definition id.h:135
__forceinline TYPE min(TYPE a, TYPE b)
Definition scalar.h:390
Nebula's scalar datatype.
int SizeT
Definition types.h:49
unsigned int uint
Definition types.h:31
int IndexT
Definition types.h:48