diff options
author | Hans Goudey <h.goudey@me.com> | 2021-10-14 19:06:18 +0300 |
---|---|---|
committer | Hans Goudey <h.goudey@me.com> | 2021-10-14 19:06:18 +0300 |
commit | b42ce0c54cab8ff5f85ca795cc1f0dab4308449b (patch) | |
tree | a924f6615cf2f6ae1471311bc359d57a283e33f9 /source/blender/functions | |
parent | 5e8775a8da93292a6d8ef0eed3b89dea40c94399 (diff) |
Functions: Generic array data structure
Sometimes it's useful to pass around a set of values with a generic
type. The virtual array data structures allow this, but they don't
have logical ownership. My initial use case for this is as a return
type for the functions that interpolate curve attributes to evaluated
points, but a need for this data structure has come up in a few other
places as well. It also reduced the need for templates.
Differential Revision: https://developer.blender.org/D11103
Diffstat (limited to 'source/blender/functions')
-rw-r--r-- | source/blender/functions/CMakeLists.txt | 2 | ||||
-rw-r--r-- | source/blender/functions/FN_generic_array.hh | 270 | ||||
-rw-r--r-- | source/blender/functions/FN_generic_virtual_array.hh | 11 | ||||
-rw-r--r-- | source/blender/functions/tests/FN_generic_array_test.cc | 118 |
4 files changed, 401 insertions, 0 deletions
diff --git a/source/blender/functions/CMakeLists.txt b/source/blender/functions/CMakeLists.txt index 309b92f1cb4..844e21f5e2c 100644 --- a/source/blender/functions/CMakeLists.txt +++ b/source/blender/functions/CMakeLists.txt @@ -41,6 +41,7 @@ set(SRC FN_cpp_type.hh FN_cpp_type_make.hh + FN_generic_array.hh FN_field.hh FN_field_cpp_type.hh FN_generic_pointer.hh @@ -87,6 +88,7 @@ blender_add_lib(bf_functions "${SRC}" "${INC}" "${INC_SYS}" "${LIB}") if(WITH_GTESTS) set(TEST_SRC tests/FN_cpp_type_test.cc + tests/FN_generic_array_test.cc tests/FN_field_test.cc tests/FN_generic_span_test.cc tests/FN_generic_vector_array_test.cc diff --git a/source/blender/functions/FN_generic_array.hh b/source/blender/functions/FN_generic_array.hh new file mode 100644 index 00000000000..401e496a66c --- /dev/null +++ b/source/blender/functions/FN_generic_array.hh @@ -0,0 +1,270 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#pragma once + +/** \file + * \ingroup fn + * + * This is a generic counterpart to #blender::Array, used when the type is not known at runtime. + * + * `GArray` should generally only be used for passing data around in dynamic contexts. + * It does not support a few things that #blender::Array supports: + * - Small object optimization / inline buffer. + * - Exception safety and various more specific constructors. + */ + +#include "BLI_allocator.hh" + +#include "FN_cpp_type.hh" +#include "FN_generic_span.hh" + +namespace blender::fn { + +template< + /** + * 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 GArray { + protected: + /** The type of the data in the array, will be null after the array is default constructed, + * but a value should be assigned before any other interaction with the array. */ + const CPPType *type_ = nullptr; + void *data_ = nullptr; + int64_t size_ = 0; + + Allocator allocator_; + + public: + /** + * The default constructor creates an empty array, the only situation in which the type is + * allowed to be null. This default constructor exists so `GArray` can be used in containers, + * but the type should be supplied before doing anything else to the array. + */ + GArray(Allocator allocator = {}) noexcept : allocator_(allocator) + { + } + + GArray(NoExceptConstructor, Allocator allocator = {}) noexcept : GArray(allocator) + { + } + + /** + * Create and allocate a new array, with elements default constructed + * (which does not do anything for trivial types). + */ + GArray(const CPPType &type, int64_t size, Allocator allocator = {}) : GArray(type, allocator) + { + BLI_assert(size >= 0); + size_ = size; + data_ = this->allocate(size_); + type_->default_construct_n(data_, size_); + } + + /** + * Create an empty array with just a type. + */ + GArray(const CPPType &type, Allocator allocator = {}) : GArray(allocator) + { + type_ = &type; + } + + /** + * Take ownership of a buffer with a provided size. The buffer should be + * allocated with the same allocator provided to the constructor. + */ + GArray(const CPPType &type, void *buffer, int64_t size, Allocator allocator = {}) + : GArray(type, allocator) + { + BLI_assert(size >= 0); + BLI_assert(buffer != nullptr || size == 0); + BLI_assert(type_->pointer_has_valid_alignment(buffer)); + + data_ = buffer; + size_ = size; + } + + /** + * Create an array by copying values from a generic span. + */ + GArray(const GSpan span, Allocator allocator = {}) : GArray(span.type(), span.size(), allocator) + { + if (span.data() != nullptr) { + BLI_assert(span.size() != 0); + /* Use copy assign rather than construct since the memory is already initialized. */ + type_->copy_assign_n(span.data(), data_, size_); + } + } + + /** + * Create an array by copying values from another generic array. + */ + GArray(const GArray &other) : GArray(other.as_span(), other.allocator()) + { + } + + /** + * Create an array by taking ownership of another array's data, clearing the data in the other. + */ + GArray(GArray &&other) : GArray(other.type(), other.data(), other.size(), other.allocator()) + { + other.data_ = nullptr; + other.size_ = 0; + } + + ~GArray() + { + if (data_ != nullptr) { + type_->destruct_n(data_, size_); + this->deallocate(data_); + } + } + + GArray &operator=(const GArray &other) + { + return copy_assign_container(*this, other); + } + + GArray &operator=(GArray &&other) + { + return move_assign_container(*this, std::move(other)); + } + + const CPPType &type() const + { + BLI_assert(type_ != nullptr); + return *type_; + } + + bool is_empty() const + { + return size_ == 0; + } + + /** + * Return the number of elements in the array (not the size in bytes). + */ + int64_t size() const + { + return size_; + } + + /** + * Get a pointer to the beginning of the array. + */ + const void *data() const + { + return data_; + } + void *data() + { + return data_; + } + + const void *operator[](int64_t index) const + { + BLI_assert(index < size_); + return POINTER_OFFSET(data_, type_->size() * index); + } + + void *operator[](int64_t index) + { + BLI_assert(index < size_); + return POINTER_OFFSET(data_, type_->size() * index); + } + + operator GSpan() const + { + BLI_assert(type_ != nullptr); + return GSpan(*type_, data_, size_); + } + + operator GMutableSpan() + { + BLI_assert(type_ != nullptr); + return GMutableSpan(*type_, data_, size_); + } + + GSpan as_span() const + { + return *this; + } + + GMutableSpan as_mutable_span() + { + return *this; + } + + /** + * Access the allocator used by this array. + */ + Allocator &allocator() + { + return allocator_; + } + const Allocator &allocator() const + { + return allocator_; + } + + /** + * 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_; + + type_->destruct_n(data_, size_); + size_ = 0; + + if (new_size <= old_size) { + type_->default_construct_n(data_, new_size); + } + else { + void *new_data = this->allocate(new_size); + try { + type_->default_construct_n(new_data, new_size); + } + catch (...) { + this->deallocate(new_data); + throw; + } + this->deallocate(data_); + data_ = new_data; + } + + size_ = new_size; + } + + private: + void *allocate(int64_t size) + { + const int64_t item_size = type_->size(); + const int64_t alignment = type_->alignment(); + return allocator_.allocate(static_cast<size_t>(size) * item_size, alignment, AT); + } + + void deallocate(void *ptr) + { + allocator_.deallocate(ptr); + } +}; + +} // namespace blender::fn diff --git a/source/blender/functions/FN_generic_virtual_array.hh b/source/blender/functions/FN_generic_virtual_array.hh index 703118ba23e..8aad017e68b 100644 --- a/source/blender/functions/FN_generic_virtual_array.hh +++ b/source/blender/functions/FN_generic_virtual_array.hh @@ -27,6 +27,7 @@ #include "BLI_virtual_array.hh" +#include "FN_generic_array.hh" #include "FN_generic_span.hh" namespace blender::fn { @@ -398,6 +399,16 @@ template<typename T> class GVArray_For_VArray : public GVArray { } }; +class GVArray_For_GArray : public GVArray_For_GSpan { + protected: + GArray<> array_; + + public: + GVArray_For_GArray(GArray<> array) : GVArray_For_GSpan(array.as_span()), array_(std::move(array)) + { + } +}; + /* Used to convert any generic virtual array into a typed one. */ template<typename T> class VArray_For_GVArray : public VArray<T> { protected: diff --git a/source/blender/functions/tests/FN_generic_array_test.cc b/source/blender/functions/tests/FN_generic_array_test.cc new file mode 100644 index 00000000000..417ab479cca --- /dev/null +++ b/source/blender/functions/tests/FN_generic_array_test.cc @@ -0,0 +1,118 @@ +/* Apache License, Version 2.0 */ + +#include "testing/testing.h" + +#include "MEM_guardedalloc.h" + +#include "BLI_array.hh" + +#include "FN_generic_array.hh" + +namespace blender::fn::tests { + +TEST(generic_array, TypeConstructor) +{ + GArray array(CPPType::get<float>()); + EXPECT_TRUE(array.data() == nullptr); + EXPECT_EQ(array.size(), 0); + EXPECT_EQ(array.as_span().typed<float>().size(), 0); + EXPECT_TRUE(array.is_empty()); +} + +TEST(generic_array, MoveConstructor) +{ + GArray array_a(CPPType::get<int32_t>(), (int64_t)10); + GMutableSpan span_a = array_a.as_mutable_span(); + MutableSpan<int32_t> typed_span_a = span_a.typed<int32_t>(); + typed_span_a.fill(42); + + const GArray array_b = std::move(array_a); + Span<int32_t> typed_span_b = array_b.as_span().typed<int32_t>(); + EXPECT_FALSE(array_b.data() == nullptr); + EXPECT_EQ(array_b.size(), 10); + EXPECT_EQ(typed_span_b[4], 42); + + /* Make sure the copy constructor cleaned up the original, but it shouldn't clear the type. */ + EXPECT_TRUE(array_a.data() == nullptr); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(array_a.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_TRUE(array_a.is_empty()); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(array_b.type(), array_a.type()); /* NOLINT: bugprone-use-after-move */ +} + +TEST(generic_array, CopyConstructor) +{ + GArray array_a(CPPType::get<int32_t>(), (int64_t)10); + GMutableSpan span_a = array_a.as_mutable_span(); + MutableSpan<int32_t> typed_span_a = span_a.typed<int32_t>(); + typed_span_a.fill(42); + + /* From span directly. */ + const GArray array_b = array_a.as_span(); + Span<int32_t> typed_span_b = array_b.as_span().typed<int32_t>(); + EXPECT_FALSE(array_b.data() == nullptr); + EXPECT_EQ(array_b.size(), 10); + EXPECT_EQ(typed_span_b[4], 42); + EXPECT_FALSE(array_a.is_empty()); + + /* From array. */ + const GArray array_c = array_a; + Span<int32_t> typed_span_c = array_c.as_span().typed<int32_t>(); + EXPECT_FALSE(array_c.data() == nullptr); + EXPECT_EQ(array_c.size(), 10); + EXPECT_EQ(typed_span_c[4], 42); + EXPECT_FALSE(array_a.is_empty()); +} + +TEST(generic_array, BufferAndSizeConstructor) +{ + int32_t *values = (int32_t *)MEM_malloc_arrayN(12, sizeof(int32_t), __func__); + void *buffer = (void *)values; + GArray array(CPPType::get<int32_t>(), buffer, 4); + EXPECT_FALSE(array.data() == nullptr); + EXPECT_EQ(array.size(), 4); + EXPECT_FALSE(array.is_empty()); + EXPECT_EQ(array.as_span().typed<int>().size(), 4); + EXPECT_EQ(array[0], &values[0]); + EXPECT_EQ(array[1], &values[1]); + EXPECT_EQ(array[2], &values[2]); + EXPECT_EQ(array[3], &values[3]); +} + +TEST(generic_array, Reinitialize) +{ + GArray array(CPPType::get<int32_t>(), (int64_t)5); + EXPECT_FALSE(array.data() == nullptr); + GMutableSpan span = array.as_mutable_span(); + MutableSpan<int32_t> typed_span = span.typed<int32_t>(); + typed_span.fill(77); + EXPECT_FALSE(typed_span.data() == nullptr); + typed_span[2] = 8; + EXPECT_EQ(array[2], &typed_span[2]); + EXPECT_EQ(typed_span[0], 77); + EXPECT_EQ(typed_span[1], 77); + + array.reinitialize(10); + EXPECT_EQ(array.size(), 10); + span = array.as_mutable_span(); + EXPECT_EQ(span.size(), 10); + + typed_span = span.typed<int32_t>(); + EXPECT_FALSE(typed_span.data() == nullptr); + + array.reinitialize(0); + EXPECT_EQ(array.size(), 0); +} + +TEST(generic_array, InContainer) +{ + blender::Array<GArray<>> arrays; + for (GArray<> &array : arrays) { + array = GArray(CPPType::get<int32_t>(), (int64_t)5); + array.as_mutable_span().typed<int32_t>().fill(55); + } + for (GArray<> &array : arrays) { + EXPECT_EQ(array.as_span().typed<int32_t>()[3], 55); + } +} + +} // namespace blender::fn::tests |