1//************************************ bs::framework - Copyright 2018 Marko Pintera **************************************//
2//*********** Licensed under the MIT license. See LICENSE.md for full terms. This notice is not to be removed. ***********//
3#pragma once
4
5namespace bs
6{
7 /** @addtogroup Internal-Utility
8 * @{
9 */
10
11 /** @addtogroup Memory-Internal
12 * @{
13 */
14
15 /**
16 * Static allocator that attempts to perform zero heap (dynamic) allocations by always keeping an active preallocated
17 * buffer. The allocator provides a fixed amount of preallocated memory, and if the size of the allocated data goes over
18 * that limit the allocator will fall back to dynamic heap allocations using the selected allocator.
19 *
20 * @note Static allocations can only be freed if memory is deallocated in opposite order it is allocated.
21 * Otherwise static memory gets orphaned until a call to clear(). Dynamic memory allocations behave
22 * depending on the selected allocator.
23 *
24 * @tparam BlockSize Size of the initially allocated static block, and minimum size of any dynamically
25 * allocated memory.
26 * @tparam DynamicAllocator Allocator to fall-back to when static buffer is full.
27 */
28 template<int BlockSize = 512, class DynamicAllocator = TFrameAlloc<BlockSize>>
29 class StaticAlloc
30 {
31 private:
32 /** A single block of memory within a static allocator. */
33 class MemBlock
34 {
35 public:
36 MemBlock(UINT8* data, UINT32 size)
37 :mData(data), mSize(size)
38 { }
39
40 /** Allocates a piece of memory within the block. Caller must ensure the block has enough empty space. */
41 UINT8* alloc(UINT32 amount)
42 {
43 UINT8* freePtr = &mData[mFreePtr];
44 mFreePtr += amount;
45
46 return freePtr;
47 }
48
49 /**
50 * Frees a piece of memory within the block. If the memory isn't the last allocated memory, no deallocation
51 * happens and that memory is instead orphaned.
52 */
53 void free(UINT8* data, UINT32 allocSize)
54 {
55 if((data + allocSize) == (mData + mFreePtr))
56 mFreePtr -= allocSize;
57 }
58
59 /** Releases all allocations within a block but doesn't actually free the memory. */
60 void clear()
61 {
62 mFreePtr = 0;
63 }
64
65 UINT8* mData = nullptr;
66 UINT32 mFreePtr = 0;
67 UINT32 mSize = 0;
68 MemBlock* mNextBlock = nullptr;
69 };
70
71 public:
72 StaticAlloc() = default;
73 ~StaticAlloc() = default;
74
75 /**
76 * Allocates a new piece of memory of the specified size.
77 *
78 * @param[in] amount Amount of memory to allocate, in bytes.
79 */
80 UINT8* alloc(UINT32 amount)
81 {
82 if (amount == 0)
83 return nullptr;
84
85#if BS_DEBUG_MODE
86 amount += sizeof(UINT32);
87#endif
88
89 UINT32 freeMem = BlockSize - mFreePtr;
90
91 UINT8* data;
92 if (amount > freeMem)
93 data = mDynamicAlloc.alloc(amount);
94 else
95 {
96 data = &mStaticData[mFreePtr];
97 mFreePtr += amount;
98 }
99
100#if BS_DEBUG_MODE
101 mTotalAllocBytes += amount;
102
103 UINT32* storedSize = reinterpret_cast<UINT32*>(data);
104 *storedSize = amount;
105
106 return data + sizeof(UINT32);
107#else
108 return data;
109#endif
110 }
111
112 /** Deallocates a previously allocated piece of memory. */
113 void free(void* data, UINT32 allocSize)
114 {
115 if (data == nullptr)
116 return;
117
118 UINT8* dataPtr = (UINT8*)data;
119#if BS_DEBUG_MODE
120 dataPtr -= sizeof(UINT32);
121
122 UINT32* storedSize = (UINT32*)(dataPtr);
123 mTotalAllocBytes -= *storedSize;
124#endif
125
126 if(data > mStaticData && data < (mStaticData + BlockSize))
127 {
128 if((((UINT8*)data) + allocSize) == (mStaticData + mFreePtr))
129 mFreePtr -= allocSize;
130 }
131 else
132 mDynamicAlloc.free(dataPtr);
133 }
134
135 /** Deallocates a previously allocated piece of memory. */
136 void free(void* data)
137 {
138 if (data == nullptr)
139 return;
140
141 UINT8* dataPtr = (UINT8*)data;
142#if BS_DEBUG_MODE
143 dataPtr -= sizeof(UINT32);
144
145 UINT32* storedSize = (UINT32*)(dataPtr);
146 mTotalAllocBytes -= *storedSize;
147#endif
148 if(data < mStaticData || data >= (mStaticData + BlockSize))
149 mDynamicAlloc.free(dataPtr);
150 }
151
152 /**
153 * Allocates enough memory to hold the object(s) of specified type using the static allocator, and constructs them.
154 */
155 template<class T>
156 T* construct(UINT32 count = 0)
157 {
158 T* data = (T*)alloc(sizeof(T) * count);
159
160 for(unsigned int i = 0; i < count; i++)
161 new ((void*)&data[i]) T;
162
163 return data;
164 }
165
166 /**
167 * Allocates enough memory to hold the object(s) of specified type using the static allocator, and constructs them.
168 */
169 template<class T, class... Args>
170 T* construct(Args &&...args, UINT32 count = 0)
171 {
172 T* data = (T*)alloc(sizeof(T) * count);
173
174 for(unsigned int i = 0; i < count; i++)
175 new ((void*)&data[i]) T(std::forward<Args>(args)...);
176
177 return data;
178 }
179
180 /** Destructs and deallocates an object allocated with the static allocator. */
181 template<class T>
182 void destruct(T* data)
183 {
184 data->~T();
185
186 free(data, sizeof(T));
187 }
188
189 /** Destructs and deallocates an array of objects allocated with the static frame allocator. */
190 template<class T>
191 void destruct(T* data, UINT32 count)
192 {
193 for(unsigned int i = 0; i < count; i++)
194 data[i].~T();
195
196 free(data, sizeof(T) * count);
197 }
198
199 /** Frees the internal memory buffers. All external allocations must be freed before calling this. */
200 void clear()
201 {
202 assert(mTotalAllocBytes == 0);
203
204 mFreePtr = 0;
205 mDynamicAlloc.clear();
206 }
207
208 private:
209 UINT8 mStaticData[BlockSize];
210 UINT32 mFreePtr = 0;
211 DynamicAllocator mDynamicAlloc;
212
213 UINT32 mTotalAllocBytes = 0;
214 };
215
216 /** Allocator for the standard library that internally uses a static allocator. */
217 template <int BlockSize, class T>
218 class StdStaticAlloc
219 {
220 public:
221 typedef T value_type;
222 typedef value_type* pointer;
223 typedef const value_type* const_pointer;
224 typedef value_type& reference;
225 typedef const value_type& const_reference;
226 typedef std::size_t size_type;
227 typedef std::ptrdiff_t difference_type;
228
229 StdStaticAlloc() = default;
230
231 StdStaticAlloc(StaticAlloc<BlockSize, FreeAlloc>* alloc) noexcept
232 :mStaticAlloc(alloc)
233 { }
234
235 template<class U> StdStaticAlloc(const StdStaticAlloc<BlockSize, U>& alloc) noexcept
236 :mStaticAlloc(alloc.mStaticAlloc)
237 { }
238
239 template<class U> class rebind { public: typedef StdStaticAlloc<BlockSize, U> other; };
240
241 /** Allocate but don't initialize number elements of type T.*/
242 T* allocate(const size_t num) const
243 {
244 if (num == 0)
245 return nullptr;
246
247 if (num > static_cast<size_t>(-1) / sizeof(T))
248 return nullptr; // Error
249
250 void* const pv = mStaticAlloc->alloc((UINT32)(num * sizeof(T)));
251 if (!pv)
252 return nullptr; // Error
253
254 return static_cast<T*>(pv);
255 }
256
257 /** Deallocate storage p of deleted elements. */
258 void deallocate(T* p, size_t num) const noexcept
259 {
260 mStaticAlloc->free((UINT8*)p, (UINT32)num);
261 }
262
263 StaticAlloc<BlockSize, FreeAlloc>* mStaticAlloc = nullptr;
264
265 size_t max_size() const { return std::numeric_limits<UINT32>::max() / sizeof(T); }
266 void construct(pointer p, const_reference t) { new (p) T(t); }
267 void destroy(pointer p) { p->~T(); }
268 template<class U, class... Args>
269 void construct(U* p, Args&&... args) { new(p) U(std::forward<Args>(args)...); }
270
271 template <class T1, int N1, class T2, int N2>
272 friend bool operator== (const StdStaticAlloc<N1, T1>& a, const StdStaticAlloc<N2, T2>& b) throw();
273
274 };
275
276 /** Return that all specializations of this allocator are interchangeable. */
277 template <class T1, int N1, class T2, int N2>
278 bool operator== (const StdStaticAlloc<N1, T1>& a, const StdStaticAlloc<N2, T2>& b) throw()
279 {
280 return N1 == N2 && a.mStaticAlloc == b.mStaticAlloc;
281 }
282
283 /** Return that all specializations of this allocator are interchangeable. */
284 template <class T1, int N1, class T2, int N2>
285 bool operator!= (const StdStaticAlloc<N1, T1>& a, const StdStaticAlloc<N2, T2>& b) throw()
286 {
287 return !(a == b);
288 }
289
290 /** @} */
291 /** @} */
292
293
294 /** @addtogroup Memory
295 * @{
296 */
297
298 /**
299 * Equivalent to Vector, except it avoids any dynamic allocations until the number of elements exceeds @p Count.
300 * Requires allocator to be explicitly provided.
301 */
302 template <typename T, int Count>
303 using StaticVector = std::vector<T, StdStaticAlloc<sizeof(T) * Count, T>>;
304
305 /** @} */
306}
307