diff options
author | Jacques Lucke <jacques@blender.org> | 2020-06-09 11:10:56 +0300 |
---|---|---|
committer | Jacques Lucke <jacques@blender.org> | 2020-06-09 11:15:43 +0300 |
commit | d8678e02ecec9375bec1dcf1388c6fc8b4ce3ad2 (patch) | |
tree | 6e7d2a7452091877f73d413d830e6cb12e86745f /source/blender/blenlib/BLI_array.hh | |
parent | 50258d55e7c1360274d40e303386cf70b16c8b2f (diff) |
BLI: generally improve C++ data structures
The main focus here was to improve the docs significantly. Furthermore,
I reimplemented `Set`, `Map` and `VectorSet`. They are now (usually)
faster, simpler and more customizable. I also rewrote `Stack` to make
it more efficient by avoiding unnecessary copies.
Thanks to everyone who helped with constructive feedback.
Approved by brecht and sybren.
Differential Revision: https://developer.blender.org/D7931
Diffstat (limited to 'source/blender/blenlib/BLI_array.hh')
-rw-r--r-- | source/blender/blenlib/BLI_array.hh | 158 |
1 files changed, 132 insertions, 26 deletions
diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh index 9dd8341aa76..09eeb321abf 100644 --- a/source/blender/blenlib/BLI_array.hh +++ b/source/blender/blenlib/BLI_array.hh @@ -19,8 +19,23 @@ /** \file * \ingroup bli * - * This is a container that contains a fixed size array. Note however, the size of the array is not - * a template argument. Instead it can be specified at the construction time. + * A `BLI::Array<T>` is a container for a fixed size array the size of which is NOT known at + * compile time. + * + * If the size is known at compile time, `std::array<T, N>` should be used instead. + * + * BLI::Array should usually be used instead of BLI::Vector whenever the number of elements is + * known at construction time. Note however, that BLI::Array will default construct all elements + * when initialized with the size-constructor. For trivial types, this does nothing. In all other + * cases, this adds overhead. If this becomes a problem, a different constructor which does not do + * default construction can be added. + * + * A main benefit of using Array over Vector is that it expresses the intent of the developer + * better. It indicates that the size of the data structure is not expected to change. Furthermore, + * you can be more certain that an array does not overallocate. + * + * BLI::Array supports small object optimization to improve performance when the size turns out to + * be small at run-time. */ #include "BLI_allocator.hh" @@ -31,42 +46,83 @@ namespace BLI { -template<typename T, uint InlineBufferCapacity = 4, typename Allocator = GuardedAllocator> +template< + /** + * The type of the values stored in the array. + */ + typename T, + /** + * The number of values that can be stored in the array, without doing a heap allocation. + * + * 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 array. Should rarely be changed, except when you don't want that + * MEM_* functions are used internally. + */ + typename Allocator = GuardedAllocator> class Array { private: + /** The beginning of the array. It might point into the inline buffer. */ T *m_data; + + /** Number of elements in the array. */ uint m_size; + + /** Used for allocations when the inline buffer is too small. */ Allocator m_allocator; - AlignedBuffer<sizeof(T) * InlineBufferCapacity, alignof(T)> m_inline_storage; + + /** A placeholder buffer that will remain uninitialized until it is used. */ + AlignedBuffer<sizeof(T) * InlineBufferCapacity, alignof(T)> m_inline_buffer; public: + /** + * By default an empty array is created. + */ Array() { - m_data = this->inline_storage(); + m_data = this->inline_buffer(); m_size = 0; } + /** + * Create a new array that contains copies of all values. + */ Array(ArrayRef<T> values) { m_size = values.size(); m_data = this->get_buffer_for_size(values.size()); - uninitialized_copy_n(values.begin(), m_size, m_data); + uninitialized_copy_n(values.data(), m_size, m_data); } + /** + * Create a new array that contains copies of all values. + */ Array(const std::initializer_list<T> &values) : Array(ArrayRef<T>(values)) { } + /** + * Create a new array with the given size. All values will be default constructed. For trivial + * types like int, default construction does nothing. + * + * We might want another version of this in the future, that does not do default construction + * even for non-trivial types. This should not be the default though, because one can easily mess + * up when dealing with uninitialized memory. + */ explicit Array(uint size) { m_size = size; m_data = this->get_buffer_for_size(size); - - for (uint i = 0; i < m_size; i++) { - new (m_data + i) T(); - } + default_construct_n(m_data, size); } + /** + * Create a new array with the given size. All values will be initialized by copying the given + * default. + */ Array(uint size, const T &value) { m_size = size; @@ -74,21 +130,19 @@ class Array { uninitialized_fill_n(m_data, m_size, value); } - Array(const Array &other) + Array(const Array &other) : m_allocator(other.m_allocator) { m_size = other.size(); - m_allocator = other.m_allocator; m_data = this->get_buffer_for_size(other.size()); - uninitialized_copy_n(other.begin(), m_size, m_data); + uninitialized_copy_n(other.data(), m_size, m_data); } - Array(Array &&other) noexcept + Array(Array &&other) noexcept : m_allocator(other.m_allocator) { m_size = other.m_size; - m_allocator = other.m_allocator; - if (!other.uses_inline_storage()) { + if (!other.uses_inline_buffer()) { m_data = other.m_data; } else { @@ -96,14 +150,14 @@ class Array { uninitialized_relocate_n(other.m_data, m_size, m_data); } - other.m_data = other.inline_storage(); + other.m_data = other.inline_buffer(); other.m_size = 0; } ~Array() { destruct_n(m_data, m_size); - if (!this->uses_inline_storage()) { + if (!this->uses_inline_buffer()) { m_allocator.deallocate((void *)m_data); } } @@ -162,21 +216,50 @@ class Array { return m_data[index]; } + /** + * Returns the number of elements in the array. + */ uint size() const { return m_size; } + /** + * Returns true when the number of elements in the array is zero. + */ + bool is_empty() const + { + return m_size == 0; + } + + /** + * Copies the value to all indices in the array. + */ void fill(const T &value) { - MutableArrayRef<T>(*this).fill(value); + initialized_fill_n(m_data, m_size, value); } + /** + * Copies the value to the given indices in the array. + */ void fill_indices(ArrayRef<uint> indices, const T &value) { MutableArrayRef<T>(*this).fill_indices(indices, value); } + /** + * Get a pointer to the beginning of the array. + */ + const T *data() const + { + return m_data; + } + T *data() + { + return m_data; + } + const T *begin() const { return m_data; @@ -197,41 +280,64 @@ class Array { return m_data + m_size; } + /** + * Get an index range containing all valid indices for this array. + */ IndexRange index_range() const { return IndexRange(m_size); } + /** + * Sets the size to zero. This should only be used when you have manually destructed all elements + * in the array beforehand. Use with care. + */ + void clear_without_destruct() + { + m_size = 0; + } + + /** + * Access the allocator used by this array. + */ Allocator &allocator() { return m_allocator; } + /** + * Get the value of the InlineBufferCapacity template argument. This is the number of elements + * that can be stored without doing an allocation. + */ + static uint inline_buffer_capacity() + { + return InlineBufferCapacity; + } + private: T *get_buffer_for_size(uint size) { if (size <= InlineBufferCapacity) { - return this->inline_storage(); + return this->inline_buffer(); } else { return this->allocate(size); } } - T *inline_storage() const + T *inline_buffer() const { - return (T *)m_inline_storage.ptr(); + return (T *)m_inline_buffer.ptr(); } T *allocate(uint size) { - return (T *)m_allocator.allocate_aligned( - size * sizeof(T), std::alignment_of<T>::value, __func__); + return (T *)m_allocator.allocate(size * sizeof(T), alignof(T), AT); } - bool uses_inline_storage() const + bool uses_inline_buffer() const { - return m_data == this->inline_storage(); + return m_data == this->inline_buffer(); } }; |