1// [Blend2D]
2// 2D Vector Graphics Powered by a JIT Compiler.
3//
4// [License]
5// Zlib - See LICENSE.md file in the package.
6
7#ifndef BLEND2D_BLZONEALLOCATOR_P_H
8#define BLEND2D_BLZONEALLOCATOR_P_H
9
10#include "./blapi-internal_p.h"
11#include "./blsupport_p.h"
12
13//! \cond INTERNAL
14//! \addtogroup blend2d_internal
15//! \{
16
17// ============================================================================
18// [BLZoneAllocator]
19// ============================================================================
20
21//! Zone memory allocator.
22//!
23//! Zone is an incremental memory allocator that allocates memory by simply
24//! incrementing a pointer. It allocates blocks of memory by using standard
25//! C library `malloc/free`, but divides these blocks into smaller chunks
26//! requested by calling `BLZoneAllocator::alloc()` and friends.
27//!
28//! Zone memory allocators are designed to allocate data of short lifetime.
29//!
30//! \note It's not recommended to use `BLZoneAllocator` to allocate larger data
31//! structures than the initial `blockSize` passed to `BLZoneAllocator()`
32//! constructor. The block size should be always greater than the maximum `size`
33//! passed to `alloc()`. Zone is designed to handle such cases, but it may
34//! allocate new block for each call to `alloc()` that exceeds the default block
35//! size.
36class BLZoneAllocator {
37public:
38 BL_NONCOPYABLE(BLZoneAllocator)
39
40 //! A single block of memory managed by `BLZoneAllocator`.
41 struct Block {
42 BL_INLINE uint8_t* data() const noexcept {
43 return const_cast<uint8_t*>(reinterpret_cast<const uint8_t*>(this) + sizeof(*this));
44 }
45
46 //! Link to the previous block.
47 Block* prev;
48 //! Link to the next block.
49 Block* next;
50 //! Size of the block.
51 size_t size;
52 };
53
54 //! Saved state, used by `BLZoneAllocator::saveState()` and `BLZoneAllocator::restoreState()`.
55 struct State {
56 //! Current pointer.
57 uint8_t* ptr;
58 //! End pointer.
59 uint8_t* end;
60 //! Current block.
61 Block* block;
62 };
63
64 enum Limits : size_t {
65 kBlockSize = sizeof(Block),
66 kBlockOverhead = BL_ALLOC_OVERHEAD + sizeof(Block),
67
68 kMinBlockSize = 64, // The number is ridiculously small, but still possible.
69 kMaxBlockSize = size_t(1) << (sizeof(size_t) * 8 - 4 - 1),
70 kMinAlignment = 1,
71 kMaxAlignment = 64
72 };
73
74 //! Pointer in the current block.
75 uint8_t* _ptr;
76 //! End of the current block.
77 uint8_t* _end;
78 //! Current block.
79 Block* _block;
80
81 union {
82 struct {
83 //! Default block size.
84 size_t _blockSize : blBitSizeOf<size_t>() - 4;
85 //! First block is temporary (BLZoneAllocatorTmp).
86 size_t _hasStaticBlock : 1;
87 //! Block alignment (1 << alignment).
88 size_t _blockAlignmentShift : 3;
89 };
90 size_t _packedData;
91 };
92
93 static BL_HIDDEN const Block _zeroBlock;
94
95 // --------------------------------------------------------------------------
96 // [Construction / Destruction]
97 // --------------------------------------------------------------------------
98
99 //! Create a new `BLZoneAllocator`.
100 //!
101 //! The `blockSize` parameter describes the default size of the block. If the
102 //! `size` parameter passed to `alloc()` is greater than the default size
103 //! `BLZoneAllocator` will allocate and use a larger block, but it will not change the
104 //! default `blockSize`.
105 //!
106 //! It's not required, but it's good practice to set `blockSize` to a
107 //! reasonable value that depends on the usage of `BLZoneAllocator`. Greater block sizes
108 //! are generally safer and perform better than unreasonably low block sizes.
109 BL_INLINE explicit BLZoneAllocator(size_t blockSize, size_t blockAlignment = 1) noexcept {
110 _init(blockSize, blockAlignment, nullptr, 0);
111 }
112
113 BL_INLINE BLZoneAllocator(size_t blockSize, size_t blockAlignment, void* staticData, size_t staticSize) noexcept {
114 _init(blockSize, blockAlignment, staticData, staticSize);
115 }
116
117 //! Destroy the `BLZoneAllocator` instance.
118 //!
119 //! This will destroy the `BLZoneAllocator` instance and release all blocks of memory
120 //! allocated by it. It performs implicit `reset()`.
121 BL_INLINE ~BLZoneAllocator() noexcept { reset(); }
122
123 // --------------------------------------------------------------------------
124 // [Init / Reset]
125 // --------------------------------------------------------------------------
126
127 BL_HIDDEN void _init(size_t blockSize, size_t blockAlignment, void* staticData, size_t staticSize) noexcept;
128
129 //! Invalidates all allocations and moves the current block pointer to the
130 //! first block. It's similar to `reset()`, however, it doesn't free blocks
131 //! of memory it holds.
132 BL_INLINE void clear() noexcept {
133 Block* cur = _block;
134 while (cur->prev)
135 cur = cur->prev;
136 _assignBlock(cur);
137 }
138
139 //! Reset the `BLZoneAllocator` invalidating all blocks allocated.
140 BL_HIDDEN void reset() noexcept;
141
142 // --------------------------------------------------------------------------
143 // [Swap]
144 // --------------------------------------------------------------------------
145
146 BL_INLINE void swap(BLZoneAllocator& other) noexcept {
147 // This could lead to a disaster.
148 BL_ASSERT(!this->hasStaticBlock());
149 BL_ASSERT(!other.hasStaticBlock());
150
151 std::swap(_ptr, other._ptr);
152 std::swap(_end, other._end);
153 std::swap(_block, other._block);
154 std::swap(_packedData, other._packedData);
155 }
156
157 //! Tests whether this `BLZoneAllocator` is actually a `BLZoneAllocatorTmp` that
158 //! uses temporary memory.
159 BL_INLINE bool hasStaticBlock() const noexcept { return _hasStaticBlock != 0; }
160
161 //! Returns the default block size.
162 BL_INLINE size_t blockSize() const noexcept { return _blockSize; }
163 //! Returns the default block alignment.
164 BL_INLINE size_t blockAlignment() const noexcept { return size_t(1) << _blockAlignmentShift; }
165 //! Returns the remaining size of the current block.
166 BL_INLINE size_t remainingSize() const noexcept { return (size_t)(_end - _ptr); }
167
168 //! Returns the current zone cursor (dangerous).
169 //!
170 //! This is a function that can be used to get exclusive access to the current
171 //! block's memory buffer.
172 template<typename T = uint8_t>
173 BL_INLINE T* ptr() noexcept { return reinterpret_cast<T*>(_ptr); }
174 //! Returns the end of the current zone block, only useful if you use `ptr()`.
175 template<typename T = uint8_t>
176 BL_INLINE T* end() noexcept { return reinterpret_cast<T*>(_end); }
177
178 // NOTE: The following two functions `setPtr()` and `setEnd()` can be used
179 // to perform manual memory allocation in case that an incremental allocation
180 // is needed - for example you build some data structure without knowing the
181 // final size. This is used for example by BLAnalyticRasterizer to build list
182 // of edges.
183
184 //! Sets the current zone pointer to `ptr` (must be within the current block).
185 template<typename T>
186 BL_INLINE void setPtr(T* ptr) noexcept {
187 uint8_t* p = reinterpret_cast<uint8_t*>(ptr);
188 BL_ASSERT(p >= _ptr && p <= _end);
189 _ptr = p;
190 }
191
192 //! Sets the end zone pointer to `end` (must be within the current block).
193 template<typename T>
194 BL_INLINE void setEnd(T* end) noexcept {
195 uint8_t* p = reinterpret_cast<uint8_t*>(end);
196 BL_ASSERT(p >= _ptr && p <= _end);
197 _end = p;
198 }
199
200 //! Align the current pointer to `alignment`.
201 BL_INLINE void align(size_t alignment) noexcept {
202 _ptr = blMin(blAlignUp(_ptr, alignment), _end);
203 }
204
205 //! Ensures the remaining size is at least equal or greater than `size`.
206 //!
207 //! \note This function doesn't respect any alignment. If you need to ensure
208 //! there is enough room for an aligned allocation you need to call `align()`
209 //! before calling `ensure()`.
210 BL_INLINE BLResult ensure(size_t size) noexcept {
211 if (size <= remainingSize())
212 return BL_SUCCESS;
213 else
214 return _alloc(0, 1) ? BL_SUCCESS : blTraceError(BL_ERROR_OUT_OF_MEMORY);
215 }
216
217 BL_INLINE void _assignBlock(Block* block) noexcept {
218 size_t alignment = blockAlignment();
219 _ptr = blAlignUp(block->data(), alignment);
220 _end = blAlignDown(block->data() + block->size, alignment);
221 _block = block;
222 }
223
224 BL_INLINE void _assignZeroBlock() noexcept {
225 Block* block = const_cast<Block*>(&_zeroBlock);
226 _ptr = block->data();
227 _end = block->data();
228 _block = block;
229 }
230
231 //! Internal alloc function.
232 BL_HIDDEN void* _alloc(size_t size, size_t alignment) noexcept;
233
234 //! Allocates the requested memory specified by `size`.
235 //!
236 //! Pointer returned is valid until the `BLZoneAllocator` instance is destroyed or reset
237 //! by calling `reset()`. If you plan to make an instance of C++ from the
238 //! given pointer use placement `new` and `delete` operators:
239 //!
240 //! ```
241 //! class Object { ... };
242 //!
243 //! // Create Zone with default block size of approximately 65536 bytes.
244 //! BLZoneAllocator zone(65536 - BLZoneAllocator::kBlockOverhead);
245 //!
246 //! // Create your objects using zone object allocating, for example:
247 //! Object* obj = static_cast<Object*>(zone.alloc(sizeof(Object)));
248 //
249 //! if (!obj) {
250 //! // Handle out of memory error.
251 //! }
252 //!
253 //! // Placement `new` and `delete` operators can be used to instantiate it.
254 //! new(obj) Object();
255 //!
256 //! // ... lifetime of your objects ...
257 //!
258 //! // To destroy the instance (if required).
259 //! obj->~Object();
260 //!
261 //! // Reset or destroy `BLZoneAllocator`.
262 //! zone.reset();
263 //! ```
264 BL_INLINE void* alloc(size_t size) noexcept {
265 if (BL_UNLIKELY(size > remainingSize()))
266 return _alloc(size, 1);
267
268 uint8_t* ptr = _ptr;
269 _ptr += size;
270 return static_cast<void*>(ptr);
271 }
272
273 //! Allocates the requested memory specified by `size` and `alignment`.
274 //!
275 //! Performs the same operation as `BLZoneAllocator::alloc(size)` with `alignment` applied.
276 BL_INLINE void* alloc(size_t size, size_t alignment) noexcept {
277 BL_ASSERT(blIsPowerOf2(alignment));
278 uint8_t* ptr = blAlignUp(_ptr, alignment);
279
280 if (size > (size_t)(_end - ptr))
281 return _alloc(size, alignment);
282
283 _ptr = ptr + size;
284 return static_cast<void*>(ptr);
285 }
286
287 //! Allocates the requested memory specified by `size` without doing any checks.
288 //!
289 //! Can only be called if `remainingSize()` returns size at least equal to `size`.
290 BL_INLINE void* allocNoCheck(size_t size) noexcept {
291 BL_ASSERT(remainingSize() >= size);
292
293 uint8_t* ptr = _ptr;
294 _ptr += size;
295 return static_cast<void*>(ptr);
296 }
297
298 //! Allocates the requested memory specified by `size` and `alignment` without doing any checks.
299 //!
300 //! Performs the same operation as `BLZoneAllocator::allocNoCheck(size)` with `alignment` applied.
301 BL_INLINE void* allocNoCheck(size_t size, size_t alignment) noexcept {
302 BL_ASSERT(blIsPowerOf2(alignment));
303
304 uint8_t* ptr = blAlignUp(_ptr, alignment);
305 BL_ASSERT(size <= (size_t)(_end - ptr));
306
307 _ptr = ptr + size;
308 return static_cast<void*>(ptr);
309 }
310
311 //! Allocates the requested memory specified by `size` and `alignment` and clears
312 //! it before returning its pointer.
313 //!
314 //! See `alloc()` for more details.
315 BL_HIDDEN void* allocZeroed(size_t size, size_t alignment = 1) noexcept;
316
317 //! Like `alloc()`, but the return pointer is casted to `T*`.
318 template<typename T>
319 BL_INLINE T* allocT(size_t size = sizeof(T), size_t alignment = alignof(T)) noexcept {
320 return static_cast<T*>(alloc(size, alignment));
321 }
322
323 //! Like `allocNoCheck()`, but the return pointer is casted to `T*`.
324 template<typename T>
325 BL_INLINE T* allocNoCheckT(size_t size = sizeof(T), size_t alignment = alignof(T)) noexcept {
326 return static_cast<T*>(allocNoCheck(size, alignment));
327 }
328
329 //! Like `allocZeroed()`, but the return pointer is casted to `T*`.
330 template<typename T>
331 BL_INLINE T* allocZeroedT(size_t size = sizeof(T), size_t alignment = alignof(T)) noexcept {
332 return static_cast<T*>(allocZeroed(size, alignment));
333 }
334
335 //! Like `new(std::nothrow) T(...)`, but allocated by `BLZoneAllocator`.
336 template<typename T>
337 BL_INLINE T* newT() noexcept {
338 void* p = alloc(sizeof(T), alignof(T));
339 if (BL_UNLIKELY(!p))
340 return nullptr;
341 return new(p) T();
342 }
343
344 //! Like `new(std::nothrow) T(...)`, but allocated by `BLZoneAllocator`.
345 template<typename T, typename... Args>
346 BL_INLINE T* newT(Args&&... args) noexcept {
347 void* p = alloc(sizeof(T), alignof(T));
348 if (BL_UNLIKELY(!p))
349 return nullptr;
350 return new(p) T(std::forward<Args>(args)...);
351 }
352
353 //! Stores the current state to `state`.
354 BL_INLINE void saveState(State* state) noexcept {
355 state->ptr = _ptr;
356 state->end = _end;
357 state->block = _block;
358 }
359
360 //! Restores the state of `BLZoneAllocator` from the previously saved `state`.
361 BL_INLINE void restoreState(State* state) noexcept {
362 Block* block = state->block;
363 _ptr = state->ptr;
364 _end = state->end;
365 _block = block;
366 }
367};
368
369// ============================================================================
370// [BLZoneAllocatorTmp]
371// ============================================================================
372
373//! A temporary `BLZoneAllocator`.
374template<size_t N>
375class BLZoneAllocatorTmp : public BLZoneAllocator {
376public:
377 BL_NONCOPYABLE(BLZoneAllocatorTmp<N>)
378
379 BL_INLINE explicit BLZoneAllocatorTmp(size_t blockSize, size_t blockAlignment = 1) noexcept
380 : BLZoneAllocator(blockSize, blockAlignment, _storage.data, N) {}
381
382 struct Storage {
383 char data[N];
384 } _storage;
385};
386
387// ============================================================================
388// [BLZonePool]
389// ============================================================================
390
391//! Helper class for implementing pooling of zone-allocated objects.
392template<typename T, size_t SizeOfT = sizeof(T)>
393class BLZonePool {
394public:
395 BL_NONCOPYABLE(BLZonePool)
396
397 struct Link { Link* next; };
398 BLZoneAllocator* _zone;
399 Link* _pool;
400
401 BL_INLINE BLZonePool(BLZoneAllocator* zone) noexcept
402 : _zone(zone),
403 _pool(nullptr) {}
404
405 //! Resets the zone pool.
406 //!
407 //! Reset must be called after the associated `BLZoneAllocator` has been reset, otherwise
408 //! the existing pool will collide with possible allocations made on the `BLZoneAllocator`
409 //! object after the reset.
410 BL_INLINE void reset() noexcept { _pool = nullptr; }
411
412 //! Ensures that there is at least one object in the pool.
413 BL_INLINE bool ensure() noexcept {
414 if (_pool) return true;
415
416 Link* p = static_cast<Link*>(_zone->alloc(SizeOfT));
417 if (p == nullptr) return false;
418
419 p->next = nullptr;
420 _pool = p;
421 return true;
422 }
423
424 //! Allocates a memory (or reuse the existing allocation) of `size` (in byts).
425 BL_INLINE T* alloc() noexcept {
426 Link* p = _pool;
427 if (BL_UNLIKELY(p == nullptr))
428 return static_cast<T*>(_zone->alloc(SizeOfT));
429 _pool = p->next;
430 return static_cast<T*>(static_cast<void*>(p));
431 }
432
433 //! Like `alloc()`, but can be only called after `ensure()` returned `true`.
434 BL_INLINE T* allocEnsured() noexcept {
435 Link* p = _pool;
436 BL_ASSERT(p != nullptr);
437
438 _pool = p->next;
439 return static_cast<T*>(static_cast<void*>(p));
440 }
441
442 //! Pools the previously allocated memory.
443 BL_INLINE void free(T* _p) noexcept {
444 BL_ASSERT(_p != nullptr);
445 Link* p = reinterpret_cast<Link*>(_p);
446
447 p->next = _pool;
448 _pool = p;
449 }
450};
451
452//! \}
453//! \endcond
454
455#endif // BLEND2D_BLZONEALLOCATOR_P_H
456