diff options
author | Hans Goudey <h.goudey@me.com> | 2020-09-01 20:35:14 +0300 |
---|---|---|
committer | Hans Goudey <h.goudey@me.com> | 2020-09-01 20:38:05 +0300 |
commit | baca8611e5fe4b3dcd6f5065fb125bc0a9d65934 (patch) | |
tree | bb1230387cd53b15f9621f10c4d0e5e2050b5580 /source/blender/blenlib/BLI_vector.hh | |
parent | 31705201dddebf7e3be5c4533b89f380aad1ede1 (diff) | |
parent | 2930d4fcea405985f2212c5f28c061af7c4849f8 (diff) |
Merge branch 'master' into active-fcurve-keyframeactive-fcurve-keyframe
Diffstat (limited to 'source/blender/blenlib/BLI_vector.hh')
-rw-r--r-- | source/blender/blenlib/BLI_vector.hh | 226 |
1 files changed, 171 insertions, 55 deletions
diff --git a/source/blender/blenlib/BLI_vector.hh b/source/blender/blenlib/BLI_vector.hh index 48110ef2814..3c90e1ab755 100644 --- a/source/blender/blenlib/BLI_vector.hh +++ b/source/blender/blenlib/BLI_vector.hh @@ -118,7 +118,7 @@ class Vector { * Create an empty vector. * This does not do any memory allocation. */ - Vector(Allocator allocator = {}) : allocator_(allocator) + Vector(Allocator allocator = {}) noexcept : allocator_(allocator) { begin_ = inline_buffer_; end_ = begin_; @@ -126,12 +126,17 @@ class Vector { UPDATE_VECTOR_SIZE(this); } + Vector(NoExceptConstructor, Allocator allocator = {}) noexcept : Vector(allocator) + { + } + /** * Create a vector with a specific size. * The elements will be default constructed. * If T is trivially constructible, the elements in the vector are not touched. */ - explicit Vector(int64_t size) : Vector() + explicit Vector(int64_t size, Allocator allocator = {}) + : Vector(NoExceptConstructor(), allocator) { this->resize(size); } @@ -139,7 +144,8 @@ class Vector { /** * Create a vector filled with a specific value. */ - Vector(int64_t size, const T &value) : Vector() + Vector(int64_t size, const T &value, Allocator allocator = {}) + : Vector(NoExceptConstructor(), allocator) { this->resize(size, value); } @@ -148,12 +154,12 @@ class Vector { * Create a vector from an array ref. The values in the vector are copy constructed. */ template<typename U, typename std::enable_if_t<std::is_convertible_v<U, T>> * = nullptr> - Vector(Span<U> values, Allocator allocator = {}) : Vector(allocator) + Vector(Span<U> values, Allocator allocator = {}) : Vector(NoExceptConstructor(), allocator) { const int64_t size = values.size(); this->reserve(size); - this->increase_size_by_unchecked(size); uninitialized_convert_n<U, T>(values.data(), size, begin_); + this->increase_size_by_unchecked(size); } /** @@ -178,17 +184,16 @@ class Vector { { } - /** - * Create a vector from any container. It must be possible to use the container in a - * range-for loop. - */ - template<typename ContainerT> static Vector FromContainer(const ContainerT &container) + template<typename InputIt, + /* This constructor should not be called with e.g. Vector(3, 10), because that is + expected to produce the vector (10, 10, 10). */ + typename std::enable_if_t<!std::is_convertible_v<InputIt, int>> * = nullptr> + Vector(InputIt first, InputIt last, Allocator allocator = {}) + : Vector(NoExceptConstructor(), allocator) { - Vector vector; - for (const auto &value : container) { - vector.append(value); + for (InputIt current = first; current != last; ++current) { + this->append(*current); } - return vector; } /** @@ -198,7 +203,7 @@ class Vector { * Example Usage: * Vector<ModifierData *> modifiers(ob->modifiers); */ - Vector(ListBase &values) : Vector() + Vector(ListBase &values, Allocator allocator = {}) : Vector(NoExceptConstructor(), allocator) { LISTBASE_FOREACH (T, value, &values) { this->append(value); @@ -228,27 +233,26 @@ class Vector { * have zero elements afterwards. */ template<int64_t OtherInlineBufferCapacity> - Vector(Vector<T, OtherInlineBufferCapacity, Allocator> &&other) noexcept - : allocator_(other.allocator_) + Vector(Vector<T, OtherInlineBufferCapacity, Allocator> &&other) noexcept( + std::is_nothrow_move_constructible_v<T>) + : Vector(NoExceptConstructor(), other.allocator_) { const int64_t size = other.size(); if (other.is_inline()) { if (size <= InlineBufferCapacity) { /* Copy between inline buffers. */ - begin_ = inline_buffer_; - end_ = begin_ + size; - capacity_end_ = begin_ + InlineBufferCapacity; uninitialized_relocate_n(other.begin_, size, begin_); + end_ = begin_ + size; } else { /* Copy from inline buffer to newly allocated buffer. */ const int64_t capacity = size; begin_ = static_cast<T *>( allocator_.allocate(sizeof(T) * static_cast<size_t>(capacity), alignof(T), AT)); - end_ = begin_ + size; capacity_end_ = begin_ + capacity; uninitialized_relocate_n(other.begin_, size, begin_); + end_ = begin_ + size; } } else { @@ -275,28 +279,12 @@ class Vector { Vector &operator=(const Vector &other) { - if (this == &other) { - return *this; - } - - this->~Vector(); - new (this) Vector(other); - - return *this; + return copy_assign_container(*this, other); } Vector &operator=(Vector &&other) { - if (this == &other) { - return *this; - } - - /* 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)); - - return *this; + return move_assign_container(*this, std::move(other)); } /** @@ -476,17 +464,10 @@ class Vector { * behavior when not enough capacity has been reserved beforehand. Only use this in performance * critical code. */ - void append_unchecked(const T &value) + template<typename ForwardT> void append_unchecked(ForwardT &&value) { BLI_assert(end_ < capacity_end_); - new (end_) T(value); - end_++; - UPDATE_VECTOR_SIZE(this); - } - void append_unchecked(T &&value) - { - BLI_assert(end_ < capacity_end_); - new (end_) T(std::move(value)); + new (end_) T(std::forward<ForwardT>(value)); end_++; UPDATE_VECTOR_SIZE(this); } @@ -499,7 +480,7 @@ class Vector { { BLI_assert(n >= 0); this->reserve(this->size() + n); - blender::uninitialized_fill_n(end_, n, value); + uninitialized_fill_n(end_, n, value); this->increase_size_by_unchecked(n); } @@ -509,7 +490,7 @@ class Vector { * 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(const int64_t n) + void increase_size_by_unchecked(const int64_t n) noexcept { BLI_assert(end_ + n <= capacity_end_); end_ += n; @@ -555,11 +536,101 @@ class Vector { { BLI_assert(amount >= 0); BLI_assert(begin_ + amount <= capacity_end_); - blender::uninitialized_copy_n(start, amount, end_); + uninitialized_copy_n(start, amount, end_); end_ += amount; UPDATE_VECTOR_SIZE(this); } + template<typename InputIt> void extend(InputIt first, InputIt last) + { + this->insert(this->end(), first, last); + } + + /** + * Insert elements into the vector at the specified position. This has a running time of O(n) + * where n is the number of values that have to be moved. Undefined behavior is invoked when the + * insert position is out of bounds. + */ + void insert(const int64_t insert_index, const T &value) + { + this->insert(insert_index, Span<T>(&value, 1)); + } + void insert(const int64_t insert_index, T &&value) + { + this->insert( + insert_index, std::make_move_iterator(&value), std::make_move_iterator(&value + 1)); + } + void insert(const int64_t insert_index, Span<T> array) + { + this->insert(begin_ + insert_index, array.begin(), array.end()); + } + template<typename InputIt> void insert(const T *insert_position, InputIt first, InputIt last) + { + const int64_t insert_index = insert_position - begin_; + this->insert(insert_index, first, last); + } + template<typename InputIt> void insert(const int64_t insert_index, InputIt first, InputIt last) + { + BLI_assert(insert_index >= 0); + BLI_assert(insert_index <= this->size()); + + const int64_t insert_amount = std::distance(first, last); + const int64_t old_size = this->size(); + const int64_t new_size = old_size + insert_amount; + const int64_t move_amount = old_size - insert_index; + + this->reserve(new_size); + for (int64_t i = 0; i < move_amount; i++) { + const int64_t src_index = insert_index + move_amount - i - 1; + const int64_t dst_index = new_size - i - 1; + try { + new (static_cast<void *>(begin_ + dst_index)) T(std::move(begin_[src_index])); + } + catch (...) { + /* Destruct all values that have been moved already. */ + destruct_n(begin_ + dst_index + 1, i); + end_ = begin_ + src_index + 1; + UPDATE_VECTOR_SIZE(this); + throw; + } + begin_[src_index].~T(); + } + + try { + std::uninitialized_copy_n(first, insert_amount, begin_ + insert_index); + } + catch (...) { + /* Destruct all values that have been moved. */ + destruct_n(begin_ + new_size - move_amount, move_amount); + end_ = begin_ + insert_index; + UPDATE_VECTOR_SIZE(this); + throw; + } + end_ = begin_ + new_size; + UPDATE_VECTOR_SIZE(this); + } + + /** + * Insert values at the beginning of the vector. The has to move all the other elements, so it + * has a linear running time. + */ + void prepend(const T &&value) + { + this->insert(0, value); + } + void prepend(T &&value) + { + this->insert(0, std::move(value)); + } + void prepend(Span<T> values) + { + this->insert(0, values); + } + template<typename InputIt> void prepend(InputIt first, InputIt last) + { + this->insert(0, first, last); + } + /** * Return a reference to the last element in the vector. * This invokes undefined behavior when the vector is empty. @@ -616,8 +687,8 @@ class Vector { T pop_last() { BLI_assert(!this->is_empty()); + T value = std::move(*(end_ - 1)); end_--; - T value = std::move(*end_); end_->~T(); UPDATE_VECTOR_SIZE(this); return value; @@ -632,10 +703,10 @@ class Vector { BLI_assert(index >= 0); BLI_assert(index < this->size()); T *element_to_remove = begin_ + index; - end_--; if (element_to_remove < end_) { - *element_to_remove = std::move(*end_); + *element_to_remove = std::move(*(end_ - 1)); } + end_--; end_->~T(); UPDATE_VECTOR_SIZE(this); } @@ -671,6 +742,27 @@ class Vector { } /** + * Remove a contiguous chunk of elements and move all values coming after it towards the front. + * This takes O(n) time. + * + * This is similar to std::vector::erase. + */ + void remove(const int64_t start_index, const int64_t amount) + { + const int64_t old_size = this->size(); + BLI_assert(start_index >= 0); + BLI_assert(amount >= 0); + BLI_assert(start_index + amount <= old_size); + const int64_t move_amount = old_size - start_index - amount; + for (int64_t i = 0; i < move_amount; i++) { + begin_[start_index + i] = std::move(begin_[start_index + amount + i]); + } + destruct_n(end_ - amount, amount); + end_ -= amount; + UPDATE_VECTOR_SIZE(this); + } + + /** * Do a linear search to find the value in the vector. * When found, return the first index, otherwise return -1. */ @@ -746,6 +838,24 @@ class Vector { return end_; } + std::reverse_iterator<T *> rbegin() + { + return std::reverse_iterator<T *>(this->end()); + } + std::reverse_iterator<T *> rend() + { + return std::reverse_iterator<T *>(this->begin()); + } + + std::reverse_iterator<const T *> rbegin() const + { + return std::reverse_iterator<T *>(this->end()); + } + std::reverse_iterator<const T *> rend() const + { + return std::reverse_iterator<T *>(this->begin()); + } + /** * Get the current capacity of the vector, i.e. the maximum number of elements the vector can * hold, before it has to reallocate. @@ -813,7 +923,13 @@ class Vector { T *new_array = static_cast<T *>( allocator_.allocate(static_cast<size_t>(new_capacity) * sizeof(T), alignof(T), AT)); - uninitialized_relocate_n(begin_, size, new_array); + try { + uninitialized_relocate_n(begin_, size, new_array); + } + catch (...) { + allocator_.deallocate(new_array); + throw; + } if (!this->is_inline()) { allocator_.deallocate(begin_); |