diff options
Diffstat (limited to 'source/blender/blenlib/BLI_linear_allocator.hh')
-rw-r--r-- | source/blender/blenlib/BLI_linear_allocator.hh | 220 |
1 files changed, 220 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_linear_allocator.hh b/source/blender/blenlib/BLI_linear_allocator.hh new file mode 100644 index 00000000000..285af49f500 --- /dev/null +++ b/source/blender/blenlib/BLI_linear_allocator.hh @@ -0,0 +1,220 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +/** \file + * \ingroup bli + * + * A linear allocator is the simplest form of an allocator. It never reuses any memory, and + * therefore does not need a deallocation method. It simply hands out consecutive buffers of + * memory. When the current buffer is full, it reallocates a new larger buffer and continues. + */ + +#ifndef __BLI_LINEAR_ALLOCATOR_HH__ +#define __BLI_LINEAR_ALLOCATOR_HH__ + +#include "BLI_string_ref.hh" +#include "BLI_utility_mixins.hh" +#include "BLI_vector.hh" + +namespace BLI { + +template<typename Allocator = GuardedAllocator> class LinearAllocator : NonCopyable, NonMovable { + private: + Allocator m_allocator; + Vector<void *> m_owned_buffers; + Vector<ArrayRef<char>> m_unused_borrowed_buffers; + + uintptr_t m_current_begin; + uintptr_t m_current_end; + uint m_next_min_alloc_size; + +#ifdef DEBUG + uint m_debug_allocated_amount = 0; +#endif + + public: + LinearAllocator() + { + m_current_begin = 0; + m_current_end = 0; + m_next_min_alloc_size = 64; + } + + ~LinearAllocator() + { + for (void *ptr : m_owned_buffers) { + m_allocator.deallocate(ptr); + } + } + + /** + * Get a pointer to a memory buffer with the given size an alignment. The memory buffer will be + * freed when this LinearAllocator is destructed. + * + * The alignment has to be a power of 2. + */ + void *allocate(uint size, uint alignment) + { + BLI_assert(alignment >= 1); + BLI_assert(is_power_of_2_i(alignment)); + +#ifdef DEBUG + m_debug_allocated_amount += size; +#endif + + uintptr_t alignment_mask = alignment - 1; + uintptr_t potential_allocation_begin = (m_current_begin + alignment_mask) & ~alignment_mask; + uintptr_t potential_allocation_end = potential_allocation_begin + size; + + if (potential_allocation_end <= m_current_end) { + m_current_begin = potential_allocation_end; + return (void *)potential_allocation_begin; + } + else { + this->allocate_new_buffer(size + alignment); + return this->allocate(size, alignment); + } + }; + + /** + * Allocate a memory buffer that can hold an instance of T. + * + * This method only allocates memory and does not construct the instance. + */ + template<typename T> T *allocate() + { + return (T *)this->allocate(sizeof(T), alignof(T)); + } + + /** + * Allocate a memory buffer that can hold T array with the given size. + * + * This method only allocates memory and does not construct the instance. + */ + template<typename T> MutableArrayRef<T> allocate_array(uint size) + { + return MutableArrayRef<T>((T *)this->allocate(sizeof(T) * size, alignof(T)), size); + } + + /** + * Construct an instance of T in memory provided by this allocator. + * + * Arguments passed to this method will be forwarded to the constructor of T. + * + * You must not call `delete` on the returned pointer. + * Instead, the destruct has to be called explicitly. + */ + template<typename T, typename... Args> T *construct(Args &&... args) + { + void *buffer = this->allocate(sizeof(T), alignof(T)); + T *value = new (buffer) T(std::forward<Args>(args)...); + return value; + } + + /** + * Copy the given array into a memory buffer provided by this allocator. + */ + template<typename T> MutableArrayRef<T> construct_array_copy(ArrayRef<T> src) + { + MutableArrayRef<T> dst = this->allocate_array<T>(src.size()); + uninitialized_copy_n(src.begin(), src.size(), dst.begin()); + return dst; + } + + /** + * Copy the given string into a memory buffer provided by this allocator. The returned string is + * always null terminated. + */ + StringRefNull copy_string(StringRef str) + { + uint alloc_size = str.size() + 1; + char *buffer = (char *)this->allocate(alloc_size, 1); + str.copy(buffer, alloc_size); + return StringRefNull((const char *)buffer); + } + + MutableArrayRef<void *> allocate_elements_and_pointer_array(uint element_amount, + uint element_size, + uint element_alignment) + { + void *pointer_buffer = this->allocate(element_amount * sizeof(void *), alignof(void *)); + void *elements_buffer = this->allocate(element_amount * element_size, element_alignment); + + MutableArrayRef<void *> pointers((void **)pointer_buffer, element_amount); + void *next_element_buffer = elements_buffer; + for (uint i : IndexRange(element_amount)) { + pointers[i] = next_element_buffer; + next_element_buffer = POINTER_OFFSET(next_element_buffer, element_size); + } + + return pointers; + } + + template<typename T, typename... Args> + ArrayRef<T *> construct_elements_and_pointer_array(uint n, Args &&... args) + { + MutableArrayRef<void *> void_pointers = this->allocate_elements_and_pointer_array( + n, sizeof(T), alignof(T)); + MutableArrayRef<T *> pointers = void_pointers.cast<T *>(); + + for (uint i : IndexRange(n)) { + new (pointers[i]) T(std::forward<Args>(args)...); + } + + return pointers; + } + + /** + * Tell the allocator to use up the given memory buffer, before allocating new memory from the + * system. + */ + void provide_buffer(void *buffer, uint size) + { + m_unused_borrowed_buffers.append(ArrayRef<char>((char *)buffer, size)); + } + + template<uint Size, uint Alignment> + void provide_buffer(AlignedBuffer<Size, Alignment> &aligned_buffer) + { + this->provide_buffer(aligned_buffer.ptr(), Size); + } + + private: + void allocate_new_buffer(uint min_allocation_size) + { + for (uint i : m_unused_borrowed_buffers.index_range()) { + ArrayRef<char> buffer = m_unused_borrowed_buffers[i]; + if (buffer.size() >= min_allocation_size) { + m_unused_borrowed_buffers.remove_and_reorder(i); + m_current_begin = (uintptr_t)buffer.begin(); + m_current_end = (uintptr_t)buffer.end(); + return; + } + } + + uint size_in_bytes = power_of_2_min_u(std::max(min_allocation_size, m_next_min_alloc_size)); + m_next_min_alloc_size = size_in_bytes * 2; + + void *buffer = m_allocator.allocate(size_in_bytes, __func__); + m_owned_buffers.append(buffer); + m_current_begin = (uintptr_t)buffer; + m_current_end = m_current_begin + size_in_bytes; + } +}; + +} // namespace BLI + +#endif /* __BLI_LINEAR_ALLOCATOR_HH__ */ |