From cc6c52768a9e6d5c82f35e953a6e53ece76d3a78 Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Fri, 14 Aug 2020 13:16:44 +0200 Subject: BLI: add reverse iterators, iterator constructor and Vector.insert/prepend The new reverse iterators behave as the reverse iterators for contains from the standard library. Have a look at the tests to see how to use them. Using them will hopefully become easier with ranges in C++20. A Vector can now be constructed from two iterators, which is very common in the standard library. New Vector.insert methods allow adding elements in the middle of a vector. These methods should not be used often in practice, because they has a linear running time. New Vector.prepend methods allow adding elements to the beginning of a vector. These methods are O(n) as well. --- source/blender/blenlib/BLI_array.hh | 20 ++++++++++++++++++-- 1 file changed, 18 insertions(+), 2 deletions(-) (limited to 'source/blender/blenlib/BLI_array.hh') diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh index 9b307dc6a04..9d09bb3559e 100644 --- a/source/blender/blenlib/BLI_array.hh +++ b/source/blender/blenlib/BLI_array.hh @@ -288,7 +288,6 @@ class Array { { return data_; } - const T *end() const { return data_ + size_; @@ -298,12 +297,29 @@ class Array { { return data_; } - T *end() { return data_ + size_; } + std::reverse_iterator rbegin() + { + return std::reverse_iterator(this->end()); + } + std::reverse_iterator rend() + { + return std::reverse_iterator(this->begin()); + } + + std::reverse_iterator rbegin() const + { + return std::reverse_iterator(this->end()); + } + std::reverse_iterator rend() const + { + return std::reverse_iterator(this->begin()); + } + /** * Get an index range containing all valid indices for this array. */ -- cgit v1.2.3 From 2aff45146f1464ba8899368ad004522cb6a1a98c Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Wed, 19 Aug 2020 16:44:53 +0200 Subject: BLI: improve exception safety of Vector, Array and Stack Using C++ exceptions in Blender is difficult, due to the large number of C functions in the call stack. However, C++ data structures in blenlib should at least try to be exception safe, so that they can be used if someone wants to use exceptions in some isolated area. This patch improves the exception safety of the Vector, Array and Stack data structure. This is mainly achieved by reordering some lines and doing some explicit exception handling. I don't expect performance of common operations to be affected by this change. The three containers are supposed to provide at least the basic exception guarantee for most methods (except for e.g. `*_unchecked` methods). So, resources should not leak when the contained type throws an exception. I also added new unit tests that test the exception handling in various cases. --- source/blender/blenlib/BLI_array.hh | 68 +++++++++++++++++-------------------- 1 file changed, 32 insertions(+), 36 deletions(-) (limited to 'source/blender/blenlib/BLI_array.hh') diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh index 9d09bb3559e..0ffe6b9a750 100644 --- a/source/blender/blenlib/BLI_array.hh +++ b/source/blender/blenlib/BLI_array.hh @@ -77,32 +77,39 @@ class Array { /** * By default an empty array is created. */ - Array() + Array(Allocator allocator = {}) noexcept : allocator_(allocator) { data_ = inline_buffer_; size_ = 0; } + Array(NoExceptConstructor, Allocator allocator = {}) noexcept : Array(allocator) + { + } + /** * Create a new array that contains copies of all values. */ template> * = nullptr> - Array(Span values, Allocator allocator = {}) : allocator_(allocator) + Array(Span values, Allocator allocator = {}) : Array(NoExceptConstructor(), allocator) { - size_ = values.size(); - data_ = this->get_buffer_for_size(values.size()); - uninitialized_convert_n(values.data(), size_, data_); + const int64_t size = values.size(); + data_ = this->get_buffer_for_size(size); + uninitialized_convert_n(values.data(), size, data_); + size_ = size; } /** * Create a new array that contains copies of all values. */ template> * = nullptr> - Array(const std::initializer_list &values) : Array(Span(values)) + Array(const std::initializer_list &values, Allocator allocator = {}) + : Array(Span(values), allocator) { } - Array(const std::initializer_list &values) : Array(Span(values)) + Array(const std::initializer_list &values, Allocator allocator = {}) + : Array(Span(values), allocator) { } @@ -114,23 +121,24 @@ class Array { * 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(int64_t size) + explicit Array(int64_t size, Allocator allocator = {}) : Array(NoExceptConstructor(), allocator) { - size_ = size; data_ = this->get_buffer_for_size(size); default_construct_n(data_, size); + size_ = size; } /** * Create a new array with the given size. All values will be initialized by copying the given * default. */ - Array(int64_t size, const T &value) + Array(int64_t size, const T &value, Allocator allocator = {}) + : Array(NoExceptConstructor(), allocator) { BLI_assert(size >= 0); - size_ = size; data_ = this->get_buffer_for_size(size); - uninitialized_fill_n(data_, size_, value); + uninitialized_fill_n(data_, size, value); + size_ = size; } /** @@ -145,28 +153,28 @@ class Array { * Usage: * Array my_strings(10, NoInitialization()); */ - Array(int64_t size, NoInitialization) + Array(int64_t size, NoInitialization, Allocator allocator = {}) + : Array(NoExceptConstructor(), allocator) { BLI_assert(size >= 0); - size_ = size; data_ = this->get_buffer_for_size(size); + size_ = size; } Array(const Array &other) : Array(other.as_span(), other.allocator_) { } - Array(Array &&other) noexcept : allocator_(other.allocator_) + Array(Array &&other) noexcept(std::is_nothrow_move_constructible_v) + : Array(NoExceptConstructor(), other.allocator_) { - size_ = other.size_; - - if (!other.uses_inline_buffer()) { - data_ = other.data_; + if (other.uses_inline_buffer()) { + uninitialized_relocate_n(other.data_, other.size_, data_); } else { - data_ = this->get_buffer_for_size(size_); - uninitialized_relocate_n(other.data_, size_, data_); + data_ = other.data_; } + size_ = other.size_; other.data_ = other.inline_buffer_; other.size_ = 0; @@ -182,24 +190,12 @@ class Array { Array &operator=(const Array &other) { - if (this == &other) { - return *this; - } - - this->~Array(); - new (this) Array(other); - return *this; + return copy_assign_container(*this, other); } - Array &operator=(Array &&other) + Array &operator=(Array &&other) noexcept(std::is_nothrow_move_constructible_v) { - if (this == &other) { - return *this; - } - - this->~Array(); - new (this) Array(std::move(other)); - return *this; + return move_assign_container(*this, std::move(other)); } T &operator[](int64_t index) -- cgit v1.2.3 From 4883cc572888e281ee27f02b307d6fc827477686 Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Mon, 24 Aug 2020 11:51:28 +0200 Subject: BLI: add Array.last method This makes it consistent with Vector and Span. --- source/blender/blenlib/BLI_array.hh | 15 +++++++++++++++ 1 file changed, 15 insertions(+) (limited to 'source/blender/blenlib/BLI_array.hh') diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh index 0ffe6b9a750..d6b7ab03203 100644 --- a/source/blender/blenlib/BLI_array.hh +++ b/source/blender/blenlib/BLI_array.hh @@ -268,6 +268,21 @@ class Array { initialized_fill_n(data_, size_, value); } + /** + * Return a reference to the last element in the array. + * This invokes undefined behavior when the array is empty. + */ + const T &last() const + { + BLI_assert(size_ > 0); + return *(data_ + size_ - 1); + } + T &last() + { + BLI_assert(size_ > 0); + return *(data_ + size_ - 1); + } + /** * Get a pointer to the beginning of the array. */ -- cgit v1.2.3 From 8e18a9984505514a229d66b38fff31d930367968 Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Mon, 24 Aug 2020 17:24:13 +0200 Subject: BLI: improve exception safety of Set and Map For more information see rB2aff45146f1464ba8899368ad004522cb6a1a98c. --- source/blender/blenlib/BLI_array.hh | 43 +++++++++++++++++++++++++++++++------ 1 file changed, 37 insertions(+), 6 deletions(-) (limited to 'source/blender/blenlib/BLI_array.hh') diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh index d6b7ab03203..dddf4f64ff5 100644 --- a/source/blender/blenlib/BLI_array.hh +++ b/source/blender/blenlib/BLI_array.hh @@ -168,7 +168,7 @@ class Array { Array(Array &&other) noexcept(std::is_nothrow_move_constructible_v) : Array(NoExceptConstructor(), other.allocator_) { - if (other.uses_inline_buffer()) { + if (other.data_ == other.inline_buffer_) { uninitialized_relocate_n(other.data_, other.size_, data_); } else { @@ -183,9 +183,7 @@ class Array { ~Array() { destruct_n(data_, size_); - if (!this->uses_inline_buffer()) { - allocator_.deallocate(static_cast(data_)); - } + this->deallocate_if_not_inline(data_); } Array &operator=(const Array &other) @@ -365,6 +363,37 @@ class Array { return InlineBufferCapacity; } + /** + * Destruct values and create a new array of the given size. The values in the new array are + * default constructed. + */ + void reinitialize(const int64_t new_size) + { + BLI_assert(new_size >= 0); + int64_t old_size = size_; + + destruct_n(data_, size_); + size_ = 0; + + if (new_size <= old_size) { + default_construct_n(data_, new_size); + } + else { + T *new_data = this->get_buffer_for_size(new_size); + try { + default_construct_n(new_data, new_size); + } + catch (...) { + this->deallocate_if_not_inline(new_data); + throw; + } + this->deallocate_if_not_inline(data_); + data_ = new_data; + } + + size_ = new_size; + } + private: T *get_buffer_for_size(int64_t size) { @@ -382,9 +411,11 @@ class Array { allocator_.allocate(static_cast(size) * sizeof(T), alignof(T), AT)); } - bool uses_inline_buffer() const + void deallocate_if_not_inline(T *ptr) { - return data_ == inline_buffer_; + if (ptr != inline_buffer_) { + allocator_.deallocate(ptr); + } } }; -- cgit v1.2.3