diff options
Diffstat (limited to 'source/blender/blenlib/BLI_vector.hh')
| -rw-r--r-- | source/blender/blenlib/BLI_vector.hh | 413 |
1 files changed, 297 insertions, 116 deletions
diff --git a/source/blender/blenlib/BLI_vector.hh b/source/blender/blenlib/BLI_vector.hh index 49cf41c2005..052cee23028 100644 --- a/source/blender/blenlib/BLI_vector.hh +++ b/source/blender/blenlib/BLI_vector.hh @@ -20,9 +20,21 @@ /** \file * \ingroup bli * - * This vector wraps a dynamically sized array of a specific type. It supports small object - * optimization. That means, when the vector only contains a few elements, no memory allocation is - * performed. Instead, those elements are stored directly in the vector. + * A `BLI::Vector<T>` is a dynamically growing contiguous array for values of type T. It is + * designed to be a more convenient and efficient replacement for `std::vector`. Note that the term + * "vector" has nothing to do with a vector from computer graphics here. + * + * A vector supports efficient insertion and removal at the end (O(1) amortized). Removal in other + * places takes O(n) time, because all elements afterwards have to be moved. If the order of + * elements is not important, `remove_and_reorder` can be used instead of `remove` for better + * performance. + * + * The improved efficiency is mainly achieved by supporting small buffer optimization. As long as + * the number of elements in the vector does not become larger than InlineBufferCapacity, no memory + * allocation is done. As a consequence, iterators are invalidated when a BLI::Vector is moved + * (iterators of std::vector remain valid when the vector is moved). + * + * `BLI::Vector` should be your default choice for a vector data structure in Blender. */ #include <algorithm> @@ -37,30 +49,69 @@ #include "BLI_listbase_wrapper.hh" #include "BLI_math_base.h" #include "BLI_memory_utils.hh" +#include "BLI_string.h" +#include "BLI_string_ref.hh" #include "BLI_utildefines.h" #include "MEM_guardedalloc.h" namespace BLI { -template<typename T, uint InlineBufferCapacity = 4, typename Allocator = GuardedAllocator> +template< + /** + * Type of the values stored in this vector. It has to be movable. + */ + typename T, + /** + * The number of values that can be stored in this vector, without doing a heap allocation. + * Sometimes it makes 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 vector. Should rarely be changed, except when you don't want that + * MEM_* is used internally. + */ + typename Allocator = GuardedAllocator> class Vector { private: + /** + * Use pointers instead of storing the size explicitely. This reduces the number of instructions + * in `append`. + * + * The pointers might point to the memory in the inline buffer. + */ T *m_begin; T *m_end; T *m_capacity_end; + + /** Used for allocations when the inline buffer is too small. */ Allocator m_allocator; - AlignedBuffer<(uint)sizeof(T) * InlineBufferCapacity, (uint)alignof(T)> m_small_buffer; + /** A placeholder buffer that will remain uninitialized until it is used. */ + AlignedBuffer<(uint)sizeof(T) * InlineBufferCapacity, (uint)alignof(T)> m_inline_buffer; + + /** + * Store the size of the vector explicitely in debug builds. Otherwise you'd always have to call + * the `size` function or do the math to compute it from the pointers manually. This is rather + * annoying. Knowing the size of a vector is often quite essential when debugging some code. + */ #ifndef NDEBUG - /* Storing size in debug builds, because it makes debugging much easier sometimes. */ uint m_debug_size; # define UPDATE_VECTOR_SIZE(ptr) (ptr)->m_debug_size = (uint)((ptr)->m_end - (ptr)->m_begin) #else # define UPDATE_VECTOR_SIZE(ptr) ((void)0) #endif - template<typename OtherT, uint OtherN, typename OtherAllocator> friend class Vector; + /** + * Be a friend with other vector instanciations. This is necessary to implement some memory + * management logic. + */ + template<typename OtherT, uint OtherInlineBufferCapacity, typename OtherAllocator> + friend class Vector; public: /** @@ -69,7 +120,7 @@ class Vector { */ Vector() { - m_begin = this->small_buffer(); + m_begin = this->inline_buffer(); m_end = m_begin; m_capacity_end = m_begin + InlineBufferCapacity; UPDATE_VECTOR_SIZE(this); @@ -77,15 +128,12 @@ class Vector { /** * Create a vector with a specific size. - * The elements will be default initialized. + * The elements will be default constructed. + * If T is trivially constructible, the elements in the vector are not touched. */ explicit Vector(uint size) : Vector() { - this->reserve(size); - this->increase_size_unchecked(size); - for (T *current = m_begin; current != m_end; current++) { - new (current) T(); - } + this->resize(size); } /** @@ -94,25 +142,29 @@ class Vector { Vector(uint size, const T &value) : Vector() { this->reserve(size); - this->increase_size_unchecked(size); + this->increase_size_by_unchecked(size); BLI::uninitialized_fill_n(m_begin, size, value); } /** - * Create a vector from an initializer list. + * Create a vector that contains copys of the values in the initialized list. + * + * This allows you to write code like: + * Vector<int> vec = {3, 4, 5}; */ - Vector(std::initializer_list<T> values) : Vector(ArrayRef<T>(values)) + Vector(const std::initializer_list<T> &values) : Vector(ArrayRef<T>(values)) { } /** - * Create a vector from an array ref. + * Create a vector from an array ref. The values in the vector are copy constructed. */ Vector(ArrayRef<T> values) : Vector() { - this->reserve(values.size()); - this->increase_size_unchecked(values.size()); - BLI::uninitialized_copy_n(values.begin(), values.size(), this->begin()); + uint size = values.size(); + this->reserve(size); + this->increase_size_by_unchecked(size); + BLI::uninitialized_copy_n(values.data(), size, m_begin); } /** @@ -129,45 +181,53 @@ class Vector { } /** - * Create a vector from a ListBase. + * Create a vector from a ListBase. The caller has to make sure that the values in the linked + * list have the correct type. + * + * Example Usage: + * Vector<ModifierData *> modifiers(ob->modifiers); */ Vector(ListBase &values) : Vector() { - for (T value : ListBaseWrapper<typename std::remove_pointer<T>::type>(values)) { + LISTBASE_FOREACH (T, value, &values) { this->append(value); } } /** - * Create a copy of another vector. - * The other vector will not be changed. - * If the other vector has less than InlineBufferCapacity elements, no allocation will be made. + * Create a copy of another vector. The other vector will not be changed. If the other vector has + * less than InlineBufferCapacity elements, no allocation will be made. */ Vector(const Vector &other) : m_allocator(other.m_allocator) { this->init_copy_from_other_vector(other); } - template<uint OtherN> - Vector(const Vector<T, OtherN, Allocator> &other) : m_allocator(other.m_allocator) + /** + * Create a copy of a vector with a different InlineBufferCapacity. This needs to be handled + * separately, so that the other one is a valid copy constructor. + */ + template<uint OtherInlineBufferCapacity> + Vector(const Vector<T, OtherInlineBufferCapacity, Allocator> &other) + : m_allocator(other.m_allocator) { this->init_copy_from_other_vector(other); } /** - * Steal the elements from another vector. - * This does not do an allocation. - * The other vector will have zero elements afterwards. + * Steal the elements from another vector. This does not do an allocation. The other vector will + * have zero elements afterwards. */ - template<uint OtherN> - Vector(Vector<T, OtherN, Allocator> &&other) noexcept : m_allocator(other.m_allocator) + template<uint OtherInlineBufferCapacity> + Vector(Vector<T, OtherInlineBufferCapacity, Allocator> &&other) noexcept + : m_allocator(other.m_allocator) { uint size = other.size(); - if (other.is_small()) { + if (other.is_inline()) { if (size <= InlineBufferCapacity) { /* Copy between inline buffers. */ - m_begin = this->small_buffer(); + m_begin = this->inline_buffer(); m_end = m_begin + size; m_capacity_end = m_begin + InlineBufferCapacity; uninitialized_relocate_n(other.m_begin, size, m_begin); @@ -175,8 +235,7 @@ class Vector { else { /* Copy from inline buffer to newly allocated buffer. */ uint capacity = size; - m_begin = (T *)m_allocator.allocate_aligned( - sizeof(T) * capacity, std::alignment_of<T>::value, __func__); + m_begin = (T *)m_allocator.allocate(sizeof(T) * capacity, alignof(T), AT); m_end = m_begin + size; m_capacity_end = m_begin + capacity; uninitialized_relocate_n(other.m_begin, size, m_begin); @@ -189,9 +248,9 @@ class Vector { m_capacity_end = other.m_capacity_end; } - other.m_begin = other.small_buffer(); + other.m_begin = other.inline_buffer(); other.m_end = other.m_begin; - other.m_capacity_end = other.m_begin + OtherN; + other.m_capacity_end = other.m_begin + OtherInlineBufferCapacity; UPDATE_VECTOR_SIZE(this); UPDATE_VECTOR_SIZE(&other); } @@ -199,7 +258,7 @@ class Vector { ~Vector() { destruct_n(m_begin, this->size()); - if (!this->is_small()) { + if (!this->is_inline()) { m_allocator.deallocate(m_begin); } } @@ -242,8 +301,8 @@ class Vector { return *this; } - /* This can fail, when the vector is used to build a recursive data structure. - See https://youtu.be/7Qgd9B1KuMQ?t=840. */ + /* This can be incorrect, when the vector is used to build a recursive data structure. However, + we don't take care of it at this low level. See https://youtu.be/7Qgd9B1KuMQ?t=840. */ this->~Vector(); new (this) Vector(std::move(other)); @@ -251,13 +310,55 @@ class Vector { } /** - * Make sure that enough memory is allocated to hold size elements. - * This won't necessarily make an allocation when size is small. + * Make sure that enough memory is allocated to hold min_capacity elements. + * This won't necessarily make an allocation when min_capacity is small. * The actual size of the vector does not change. */ - void reserve(uint size) + void reserve(uint min_capacity) + { + if (min_capacity > this->capacity()) { + this->realloc_to_at_least(min_capacity); + } + } + + /** + * Change the size of the vector so that it contains new_size elements. + * If new_size is smaller than the old size, the elements at the end of the vector are + * destructed. If new_size is larger than the old size, the new elements at the end are default + * constructed. If T is trivially constructible, the memory is not touched by this function. + */ + void resize(uint new_size) { - this->grow(size); + uint old_size = this->size(); + if (new_size > old_size) { + this->reserve(new_size); + default_construct_n(m_begin + old_size, new_size - old_size); + } + else { + destruct_n(m_begin + new_size, old_size - new_size); + } + m_end = m_begin + new_size; + UPDATE_VECTOR_SIZE(this); + } + + /** + * Change the size of the vector so that it contains new_size elements. + * If new_size is smaller than the old size, the elements at the end of the vector are + * destructed. If new_size is larger than the old size, the new elements will be copy constructed + * from the given value. + */ + void resize(uint new_size, const T &value) + { + uint old_size = this->size(); + if (new_size > old_size) { + this->reserve(new_size); + uninitialized_fill_n(m_begin + old_size, new_size - old_size, value); + } + else { + destruct_n(m_begin + new_size, old_size - new_size); + } + m_end = m_begin + new_size; + UPDATE_VECTOR_SIZE(this); } /** @@ -275,14 +376,14 @@ class Vector { * Afterwards the vector has 0 elements and any allocated memory * will be freed. */ - void clear_and_make_small() + void clear_and_make_inline() { destruct_n(m_begin, this->size()); - if (!this->is_small()) { + if (!this->is_inline()) { m_allocator.deallocate(m_begin); } - m_begin = this->small_buffer(); + m_begin = this->inline_buffer(); m_end = m_begin; m_capacity_end = m_begin + InlineBufferCapacity; UPDATE_VECTOR_SIZE(this); @@ -291,19 +392,24 @@ class Vector { /** * Insert a new element at the end of the vector. * This might cause a reallocation with the capacity is exceeded. + * + * This is similar to std::vector::push_back. */ void append(const T &value) { this->ensure_space_for_one(); this->append_unchecked(value); } - void append(T &&value) { this->ensure_space_for_one(); this->append_unchecked(std::move(value)); } + /** + * Append the value to the vector and return the index that can be used to access the newly + * added value. + */ uint append_and_get_index(const T &value) { uint index = this->size(); @@ -311,6 +417,11 @@ class Vector { return index; } + /** + * Append the value if it is not yet in the vector. This has to do a linear search to check if + * the value is in the vector. Therefore, this should only be called when it is known that the + * vector is small. + */ void append_non_duplicates(const T &value) { if (!this->contains(value)) { @@ -318,6 +429,11 @@ class Vector { } } + /** + * Append the value and assume that vector has enough memory reserved. This invokes undefined + * behavior when not enough capacity has been reserved beforehand. Only use this in performance + * critical code. + */ void append_unchecked(const T &value) { BLI_assert(m_end < m_capacity_end); @@ -325,7 +441,6 @@ class Vector { m_end++; UPDATE_VECTOR_SIZE(this); } - void append_unchecked(T &&value) { BLI_assert(m_end < m_capacity_end); @@ -342,10 +457,16 @@ class Vector { { this->reserve(this->size() + n); BLI::uninitialized_fill_n(m_end, n, value); - this->increase_size_unchecked(n); + this->increase_size_by_unchecked(n); } - void increase_size_unchecked(uint n) + /** + * Enlarges the size of the internal buffer that is considered to be initialized. This invokes + * undefined behavior when when the new size is larger than the capacity. The method can be + * useful when you want to call constructors in the vector yourself. This should only be done in + * very rare cases and has to be justified every time. + */ + void increase_size_by_unchecked(uint n) { BLI_assert(m_end + n <= m_capacity_end); m_end += n; @@ -354,18 +475,24 @@ class Vector { /** * Copy the elements of another array to the end of this vector. + * + * This can be used to emulate parts of std::vector::insert. */ void extend(ArrayRef<T> array) { - this->extend(array.begin(), array.size()); + this->extend(array.data(), array.size()); } - void extend(const T *start, uint amount) { this->reserve(this->size() + amount); this->extend_unchecked(start, amount); } + /** + * Adds all elements from the array that are not already in the vector. This is an expensive + * operation when the vector is large, but can be very cheap when it is known that the vector is + * small. + */ void extend_non_duplicates(ArrayRef<T> array) { for (const T &value : array) { @@ -373,11 +500,14 @@ class Vector { } } + /** + * Extend the vector without bounds checking. It is assumed that enough memory has been reserved + * beforehand. Only use this in performance critical code. + */ void extend_unchecked(ArrayRef<T> array) { - this->extend_unchecked(array.begin(), array.size()); + this->extend_unchecked(array.data(), array.size()); } - void extend_unchecked(const T *start, uint amount) { BLI_assert(m_begin + amount <= m_capacity_end); @@ -395,7 +525,6 @@ class Vector { BLI_assert(this->size() > 0); return *(m_end - 1); } - T &last() { BLI_assert(this->size() > 0); @@ -407,9 +536,12 @@ class Vector { */ void fill(const T &value) { - std::fill(m_begin, m_end, value); + initialized_fill_n(m_begin, this->size(), value); } + /** + * Copy the value to all positions specified by the indices array. + */ void fill_indices(ArrayRef<uint> indices, const T &value) { MutableArrayRef<T>(*this).fill_indices(indices, value); @@ -426,6 +558,8 @@ class Vector { /** * Returns true when the vector contains no elements, otherwise false. + * + * This is the same as std::vector::empty. */ bool is_empty() const { @@ -433,33 +567,36 @@ class Vector { } /** - * Deconstructs the last element and decreases the size by one. - * This will assert when the vector is empty. + * Destructs the last element and decreases the size by one. This invokes undefined behavior when + * the vector is empty. */ void remove_last() { BLI_assert(!this->is_empty()); m_end--; - destruct(m_end); + m_end->~T(); UPDATE_VECTOR_SIZE(this); } /** - * Remove the last element from the vector and return it. + * Remove the last element from the vector and return it. This invokes undefined behavior when + * the vector is empty. + * + * This is similar to std::vector::pop_back. */ T pop_last() { BLI_assert(!this->is_empty()); m_end--; T value = std::move(*m_end); - destruct(m_end); + m_end->~T(); UPDATE_VECTOR_SIZE(this); return value; } /** - * Delete any element in the vector. - * The empty space will be filled by the previously last element. + * Delete any element in the vector. The empty space will be filled by the previously last + * element. This takes O(1) time. */ void remove_and_reorder(uint index) { @@ -469,37 +606,60 @@ class Vector { if (element_to_remove < m_end) { *element_to_remove = std::move(*m_end); } - destruct(m_end); + m_end->~T(); UPDATE_VECTOR_SIZE(this); } + /** + * Finds the first occurence of the value, removes it and copies the last element to the hole in + * the vector. This takes O(n) time. + */ void remove_first_occurrence_and_reorder(const T &value) { - uint index = this->index(value); + uint index = this->first_index_of(value); this->remove_and_reorder((uint)index); } /** + * Remove the element at the given index and move all values coming after it one towards the + * front. This takes O(n) time. If the order is not important, remove_and_reorder should be used + * instead. + * + * This is similar to std::vector::erase. + */ + void remove(uint index) + { + BLI_assert(index < this->size()); + uint last_index = this->size() - 1; + for (uint i = index; i < last_index; i++) { + m_begin[i] = std::move(m_begin[i + 1]); + } + m_begin[last_index].~T(); + m_end--; + UPDATE_VECTOR_SIZE(this); + } + + /** * Do a linear search to find the value in the vector. * When found, return the first index, otherwise return -1. */ - int index_try(const T &value) const + int first_index_of_try(const T &value) const { for (T *current = m_begin; current != m_end; current++) { if (*current == value) { - return current - m_begin; + return (int)(current - m_begin); } } return -1; } /** - * Do a linear search to find the value in the vector. - * When found, return the first index, otherwise fail. + * Do a linear search to find the value in the vector and return the found index. This invokes + * undefined behavior when the value is not in the vector. */ - uint index(const T &value) const + uint first_index_of(const T &value) const { - int index = this->index_try(value); + int index = this->first_index_of_try(value); BLI_assert(index >= 0); return (uint)index; } @@ -510,27 +670,13 @@ class Vector { */ bool contains(const T &value) const { - return this->index_try(value) != -1; + return this->first_index_of_try(value) != -1; } /** - * Compare vectors element-wise. - * Return true when they have the same length and all elements - * compare equal, otherwise false. + * Get the value at the given index. This invokes undefined behavior when the index is out of + * bounds. */ - static bool all_equal(const Vector &a, const Vector &b) - { - if (a.size() != b.size()) { - return false; - } - for (uint i = 0; i < a.size(); i++) { - if (a[i] != b[i]) { - return false; - } - } - return true; - } - const T &operator[](uint index) const { BLI_assert(index < this->size()); @@ -543,6 +689,22 @@ class Vector { return m_begin[index]; } + /** + * Get access to the underlying array. + */ + T *data() + { + return m_begin; + } + + /** + * Get access to the underlying array. + */ + const T *data() const + { + return m_begin; + } + T *begin() { return m_begin; @@ -562,74 +724,94 @@ class Vector { } /** - * Get the current capacity of the vector. + * Get the current capacity of the vector, i.e. the maximum number of elements the vector can + * hold, before it has to reallocate. */ uint capacity() const { return (uint)(m_capacity_end - m_begin); } + /** + * Get an index range that makes looping over all indices more convenient and less error prone. + * Obviously, this should only be used when you actually need the index in the loop. + * + * Example: + * for (uint i : myvector.index_range()) { + * do_something(i, my_vector[i]); + * } + */ IndexRange index_range() const { return IndexRange(this->size()); } - void print_stats() const + /** + * Print some debug information about the vector. + */ + void print_stats(StringRef name = "") const { - std::cout << "Small Vector at " << (void *)this << ":" << std::endl; - std::cout << " Elements: " << this->size() << std::endl; - std::cout << " Capacity: " << (m_capacity_end - m_begin) << std::endl; - std::cout << " Small Elements: " << InlineBufferCapacity - << " Size on Stack: " << sizeof(*this) << std::endl; + std::cout << "Vector Stats: " << name << "\n"; + std::cout << " Address: " << this << "\n"; + std::cout << " Elements: " << this->size() << "\n"; + std::cout << " Capacity: " << (m_capacity_end - m_begin) << "\n"; + std::cout << " Inline Capacity: " << InlineBufferCapacity << "\n"; + + char memory_size_str[15]; + BLI_str_format_byte_unit(memory_size_str, sizeof(*this), true); + std::cout << " Size on Stack: " << memory_size_str << "\n"; } private: - T *small_buffer() const + T *inline_buffer() const { - return (T *)m_small_buffer.ptr(); + return (T *)m_inline_buffer.ptr(); } - bool is_small() const + bool is_inline() const { - return m_begin == this->small_buffer(); + return m_begin == this->inline_buffer(); } void ensure_space_for_one() { if (UNLIKELY(m_end >= m_capacity_end)) { - this->grow(std::max(this->size() * 2, (uint)1)); + this->realloc_to_at_least(this->size() + 1); } + std::vector<int> a; + a.push_back(4); } - BLI_NOINLINE void grow(uint min_capacity) + BLI_NOINLINE void realloc_to_at_least(uint min_capacity) { if (this->capacity() >= min_capacity) { return; } - /* Round up to the next power of two. Otherwise consecutive calls to grow can cause a - * reallocation every time even though the min_capacity only increments. */ - min_capacity = power_of_2_max_u(min_capacity); + /* At least double the size of the previous allocation. Otherwise consecutive calls to grow can + * cause a reallocation every time even though min_capacity only increments. */ + uint min_new_capacity = this->capacity() * 2; + uint new_capacity = std::max(min_capacity, min_new_capacity); uint size = this->size(); - T *new_array = (T *)m_allocator.allocate_aligned( - min_capacity * (uint)sizeof(T), std::alignment_of<T>::value, "grow BLI::Vector"); + T *new_array = (T *)m_allocator.allocate(new_capacity * (uint)sizeof(T), alignof(T), AT); uninitialized_relocate_n(m_begin, size, new_array); - if (!this->is_small()) { + if (!this->is_inline()) { m_allocator.deallocate(m_begin); } m_begin = new_array; m_end = m_begin + size; - m_capacity_end = m_begin + min_capacity; + m_capacity_end = m_begin + new_capacity; } /** * Initialize all properties, except for m_allocator, which has to be initialized beforehand. */ - template<uint OtherN> void init_copy_from_other_vector(const Vector<T, OtherN, Allocator> &other) + template<uint OtherInlineBufferCapacity> + void init_copy_from_other_vector(const Vector<T, OtherInlineBufferCapacity, Allocator> &other) { m_allocator = other.m_allocator; @@ -637,19 +819,18 @@ class Vector { uint capacity = size; if (size <= InlineBufferCapacity) { - m_begin = this->small_buffer(); + m_begin = this->inline_buffer(); capacity = InlineBufferCapacity; } else { - m_begin = (T *)m_allocator.allocate_aligned( - sizeof(T) * size, std::alignment_of<T>::value, __func__); + m_begin = (T *)m_allocator.allocate(sizeof(T) * size, alignof(T), AT); capacity = size; } m_end = m_begin + size; m_capacity_end = m_begin + capacity; - uninitialized_copy(other.begin(), other.end(), m_begin); + uninitialized_copy_n(other.data(), size, m_begin); UPDATE_VECTOR_SIZE(this); } }; |