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. |
36 | class BLZoneAllocator { |
37 | public: |
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`. |
374 | template<size_t N> |
375 | class BLZoneAllocatorTmp : public BLZoneAllocator { |
376 | public: |
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. |
392 | template<typename T, size_t SizeOfT = sizeof(T)> |
393 | class BLZonePool { |
394 | public: |
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 | |