diff options
Diffstat (limited to 'source/blender/blenlib/BLI_stack.hh')
| -rw-r--r-- | source/blender/blenlib/BLI_stack.hh | 345 |
1 files changed, 292 insertions, 53 deletions
diff --git a/source/blender/blenlib/BLI_stack.hh b/source/blender/blenlib/BLI_stack.hh index 7f1f9f9cc10..4645535876d 100644 --- a/source/blender/blenlib/BLI_stack.hh +++ b/source/blender/blenlib/BLI_stack.hh @@ -20,48 +20,208 @@ /** \file * \ingroup bli * - * Basic stack implementation with support for small object optimization. + * A `BLI::Stack<T>` is a dynamically growing FILO (first-in, last-out) data structure. It is + * designed to be a more convenient and efficient replacement for `std::stack`. + * + * The improved efficiency is mainly achieved by supporting small buffer optimization. As long as + * the number of elements added to the stack stays below InlineBufferCapacity, no heap allocation + * is done. Consequently, values stored in the stack have to be movable and they might be moved, + * when the stack is moved. + * + * A Vector can be used to emulate a stack. However, this stack implementation is more efficient + * when all you have to do is to push and pop elements. That is because a vector guarantees that + * all elements are in a contiguous array. Therefore, it has to copy all elements to a new buffer + * when it grows. This stack implementation does not have to copy all previously pushed elements + * when it grows. + * + * BLI::Stack is implemented using a double linked list of chunks. Each chunk contains an array of + * elements. The chunk size increases exponentially with every new chunk that is required. The + * lowest chunk, i.e. the one that is used for the first few pushed elements, is embedded into the + * stack. */ -#include "BLI_vector.hh" +#include "BLI_allocator.hh" +#include "BLI_array_ref.hh" +#include "BLI_memory_utils.hh" namespace BLI { -template<typename T, uint InlineBufferCapacity = 4, typename Allocator = GuardedAllocator> +/** + * A StackChunk references a contiguous memory buffer. Multiple StackChunk instances are linked in + * a double linked list. + */ +template<typename T> struct StackChunk { + /** The below chunk contains the elements that have been pushed on the stack before. */ + StackChunk *below; + /** The above chunk contains the elements that have been pushed on the stack afterwards. */ + StackChunk *above; + /** Pointer to the first element of the referenced buffer. */ + T *begin; + /** Pointer to one element past the end of the referenced buffer. */ + T *capacity_end; + + uint capacity() const + { + return capacity_end - begin; + } +}; + +template< + /** Type of the elements that are stored in the stack. */ + typename T, + /** + * The number of values that can be stored in this stack, without doing a heap allocation. + * Sometimes it can make sense to increase this value a lot. The memory in the inline buffer is + * not initialized when it is not needed. + * + * When T is large, the small buffer optimization is disabled by default to avoid large + * unexpected allocations on the stack. It can still be enabled explicitely though. + */ + uint InlineBufferCapacity = (sizeof(T) < 100) ? 4 : 0, + /** + * The allocator used by this stack. Should rarely be changed, except when you don't want that + * MEM_* is used internally. + */ + typename Allocator = GuardedAllocator> class Stack { private: - Vector<T, InlineBufferCapacity, Allocator> m_elements; + using Chunk = StackChunk<T>; - public: - Stack() = default; + /** + * Points to one element after top-most value in the stack. + * + * Invariant: + * If m_size == 0 + * then: m_top == m_inline_chunk.begin + * else: &peek() == m_top - 1; + */ + T *m_top; + + /** Points to the chunk that references the memory pointed to by m_top. */ + Chunk *m_top_chunk; /** - * Construct a stack from an array ref. The elements will be pushed in the same order they are in - * the array. + * Number of elements in the entire stack. The sum of initialized element counts in the chunks. */ - Stack(ArrayRef<T> values) : m_elements(values) - { - } + uint m_size; + + /** The buffer used to implement small object optimization. */ + AlignedBuffer<sizeof(T) * InlineBufferCapacity, alignof(T)> m_inline_buffer; + + /** + * A chunk referencing the inline buffer. This is always the bottom-most chunk. + * So m_inline_chunk.below == nullptr. + */ + Chunk m_inline_chunk; - operator ArrayRef<T>() + /** Used for allocations when the inline buffer is not large enough. */ + Allocator m_allocator; + + public: + /** + * Initialize an empty stack. No heap allocation is done. + */ + Stack(Allocator allocator = {}) : m_allocator(allocator) { - return m_elements; + T *inline_buffer = this->inline_buffer(); + + m_inline_chunk.below = nullptr; + m_inline_chunk.above = nullptr; + m_inline_chunk.begin = inline_buffer; + m_inline_chunk.capacity_end = inline_buffer + InlineBufferCapacity; + + m_top = inline_buffer; + m_top_chunk = &m_inline_chunk; + m_size = 0; } /** - * Return the number of elements in the stack. + * Create a new stack that contains the given elements. The values are pushed to the stack in + * the order they are in the array. */ - uint size() const + Stack(ArrayRef<T> values) : Stack() { - return m_elements.size(); + this->push_multiple(values); } /** - * Return true when the stack is empty, otherwise false. + * Create a new stack that contains the given elements. The values are pushed to the stack in the + * order they are in the array. + * + * Example: + * Stack<int> stack = {4, 5, 6}; + * assert(stack.pop() == 6); + * assert(stack.pop() == 5); */ - bool is_empty() const + Stack(const std::initializer_list<T> &values) : Stack(ArrayRef<T>(values)) + { + } + + Stack(const Stack &other) : Stack(other.m_allocator) + { + for (const Chunk *chunk = &other.m_inline_chunk; chunk; chunk = chunk->above) { + const T *begin = chunk->begin; + const T *end = (chunk == other.m_top_chunk) ? other.m_top : chunk->capacity_end; + this->push_multiple(ArrayRef<T>(begin, end - begin)); + } + } + + Stack(Stack &&other) noexcept : Stack(other.m_allocator) + { + uninitialized_relocate_n(other.inline_buffer(), + std::min(other.m_size, InlineBufferCapacity), + this->inline_buffer()); + + m_inline_chunk.above = other.m_inline_chunk.above; + m_size = other.m_size; + + if (m_size <= InlineBufferCapacity) { + m_top_chunk = &m_inline_chunk; + m_top = this->inline_buffer() + m_size; + } + else { + m_top_chunk = other.m_top_chunk; + m_top = other.m_top; + } + + other.m_size = 0; + other.m_inline_chunk.above = nullptr; + other.m_top_chunk = &other.m_inline_chunk; + other.m_top = other.m_top_chunk->begin; + } + + ~Stack() { - return this->size() == 0; + this->destruct_all_elements(); + Chunk *above_chunk; + for (Chunk *chunk = m_inline_chunk.above; chunk; chunk = above_chunk) { + above_chunk = chunk->above; + m_allocator.deallocate(chunk); + } + } + + Stack &operator=(const Stack &stack) + { + if (this == &stack) { + return *this; + } + + this->~Stack(); + new (this) Stack(stack); + + return *this; + } + + Stack &operator=(Stack &&stack) + { + if (this == &stack) { + return *this; + } + + this->~Stack(); + new (this) Stack(std::move(stack)); + + return *this; } /** @@ -69,80 +229,159 @@ class Stack { */ void push(const T &value) { - m_elements.append(value); + if (m_top == m_top_chunk->capacity_end) { + this->activate_next_chunk(1); + } + new (m_top) T(value); + m_top++; + m_size++; } - void push(T &&value) { - m_elements.append(std::move(value)); - } - - void push_multiple(ArrayRef<T> values) - { - m_elements.extend(values); + if (m_top == m_top_chunk->capacity_end) { + this->activate_next_chunk(1); + } + new (m_top) T(std::move(value)); + m_top++; + m_size++; } /** - * Remove the element from the top of the stack and return it. - * This will assert when the stack is empty. + * Remove and return the top-most element from the stack. This invokes undefined behavior when + * the stack is empty. */ T pop() { - return m_elements.pop_last(); + BLI_assert(m_size > 0); + m_top--; + T value = std::move(*m_top); + m_top->~T(); + m_size--; + + if (m_top == m_top_chunk->begin) { + if (m_top_chunk->below != nullptr) { + m_top_chunk = m_top_chunk->below; + m_top = m_top_chunk->capacity_end; + } + } + return value; } /** - * Return a reference to the value a the top of the stack. - * This will assert when the stack is empty. + * Get a reference to the top-most element without removing it from the stack. This invokes + * undefined behavior when the stack is empty. */ T &peek() { - BLI_assert(!this->is_empty()); - return m_elements[this->size() - 1]; + BLI_assert(m_size > 0); + BLI_assert(m_top > m_top_chunk->begin); + return *(m_top - 1); } - - T *begin() + const T &peek() const { - return m_elements.begin(); + BLI_assert(m_size > 0); + BLI_assert(m_top > m_top_chunk->begin); + return *(m_top - 1); } - T *end() + /** + * Add multiple elements to the stack. The values are pushed in the order they are in the array. + * This method is more efficient than pushing multiple elements individually and might cause less + * heap allocations. + */ + void push_multiple(ArrayRef<T> values) { - return m_elements.end(); + ArrayRef<T> remaining_values = values; + while (!remaining_values.is_empty()) { + if (m_top == m_top_chunk->capacity_end) { + this->activate_next_chunk(remaining_values.size()); + } + + uint remaining_capacity = m_top_chunk->capacity_end - m_top; + uint amount = std::min(remaining_values.size(), remaining_capacity); + uninitialized_copy_n(remaining_values.data(), amount, m_top); + m_top += amount; + + remaining_values = remaining_values.drop_front(amount); + } + + m_size += values.size(); } - const T *begin() const + /** + * Returns true when the size is zero. + */ + bool is_empty() const { - return m_elements.begin(); + return m_size == 0; } - const T *end() const + /** + * Returns the number of elements in the stack. + */ + uint size() const { - return m_elements.end(); + return m_size; } /** - * Remove all elements from the stack but keep the memory. + * Removes all elements from the stack. The memory is not freed, so it is more efficient to reuse + * the stack than to create a new one. */ void clear() { - m_elements.clear(); + this->destruct_all_elements(); + m_top_chunk = &m_inline_chunk; + m_top = m_top_chunk->begin; } - /** - * Remove all elements and free any allocated memory. - */ - void clear_and_make_small() + private: + T *inline_buffer() const { - m_elements.clear_and_make_small(); + return (T *)m_inline_buffer.ptr(); } /** - * Does a linear search to check if the value is in the stack. + * Changes m_top_chunk to point to a new chunk that is above the current one. The new chunk might + * be smaller than the given size_hint. This happens when a chunk that has been allocated before + * is reused. The size of the new chunk will be at least one. + * + * This invokes undefined behavior when the currently active chunk is not full. */ - bool contains(const T &value) + void activate_next_chunk(uint size_hint) + { + BLI_assert(m_top == m_top_chunk->capacity_end); + if (m_top_chunk->above == nullptr) { + uint new_capacity = std::max(size_hint, m_top_chunk->capacity() * 2 + 10); + + /* Do a single memory allocation for the Chunk and the array it references. */ + void *buffer = m_allocator.allocate( + sizeof(Chunk) + sizeof(T) * new_capacity + alignof(T), alignof(Chunk), AT); + void *chunk_buffer = buffer; + void *data_buffer = (void *)(((uintptr_t)buffer + sizeof(Chunk) + alignof(T) - 1) & + ~(alignof(T) - 1)); + + Chunk *new_chunk = new (chunk_buffer) Chunk(); + new_chunk->begin = (T *)data_buffer; + new_chunk->capacity_end = new_chunk->begin + new_capacity; + new_chunk->above = nullptr; + new_chunk->below = m_top_chunk; + m_top_chunk->above = new_chunk; + } + m_top_chunk = m_top_chunk->above; + m_top = m_top_chunk->begin; + } + + void destruct_all_elements() { - return m_elements.contains(value); + for (T *value = m_top_chunk->begin; value != m_top; value++) { + value->~T(); + } + for (Chunk *chunk = m_top_chunk->below; chunk; chunk = chunk->below) { + for (T *value = chunk->begin; value != chunk->capacity_end; value++) { + value->~T(); + } + } } }; |