diff options
Diffstat (limited to 'source/blender/blenlib')
| -rw-r--r-- | source/blender/blenlib/BLI_compiler_attrs.h | 7 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_map.hh | 80 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_map_slots.hh | 12 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_span.hh | 14 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_stack.hh | 5 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_vector.hh | 37 | ||||
| -rw-r--r-- | source/blender/blenlib/BLI_virtual_array.hh | 384 | ||||
| -rw-r--r-- | source/blender/blenlib/tests/BLI_map_test.cc | 9 | ||||
| -rw-r--r-- | source/blender/blenlib/tests/BLI_stack_cxx_test.cc | 9 | ||||
| -rw-r--r-- | source/blender/blenlib/tests/BLI_vector_test.cc | 9 | ||||
| -rw-r--r-- | source/blender/blenlib/tests/BLI_virtual_array_test.cc | 133 |
11 files changed, 610 insertions, 89 deletions
diff --git a/source/blender/blenlib/BLI_compiler_attrs.h b/source/blender/blenlib/BLI_compiler_attrs.h index 680c4bc78da..4b5a7d671f2 100644 --- a/source/blender/blenlib/BLI_compiler_attrs.h +++ b/source/blender/blenlib/BLI_compiler_attrs.h @@ -98,3 +98,10 @@ #else # define ATTR_ALIGN(x) __attribute__((aligned(x))) #endif + +/* Alignment directive */ +#ifdef _WIN64 +# define ALIGN_STRUCT __declspec(align(64)) +#else +# define ALIGN_STRUCT +#endif diff --git a/source/blender/blenlib/BLI_map.hh b/source/blender/blenlib/BLI_map.hh index 9fa69853e44..376bf5df06f 100644 --- a/source/blender/blenlib/BLI_map.hh +++ b/source/blender/blenlib/BLI_map.hh @@ -247,11 +247,11 @@ class Map { { this->add_new_as(std::move(key), std::move(value)); } - template<typename ForwardKey, typename ForwardValue> - void add_new_as(ForwardKey &&key, ForwardValue &&value) + template<typename ForwardKey, typename... ForwardValue> + void add_new_as(ForwardKey &&key, ForwardValue &&... value) { this->add_new__impl( - std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash_(key)); + std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...); } /** @@ -277,11 +277,11 @@ class Map { { return this->add_as(std::move(key), std::move(value)); } - template<typename ForwardKey, typename ForwardValue> - bool add_as(ForwardKey &&key, ForwardValue &&value) + template<typename ForwardKey, typename... ForwardValue> + bool add_as(ForwardKey &&key, ForwardValue &&... value) { return this->add__impl( - std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash_(key)); + std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...); } /** @@ -307,11 +307,11 @@ class Map { { return this->add_overwrite_as(std::move(key), std::move(value)); } - template<typename ForwardKey, typename ForwardValue> - bool add_overwrite_as(ForwardKey &&key, ForwardValue &&value) + template<typename ForwardKey, typename... ForwardValue> + bool add_overwrite_as(ForwardKey &&key, ForwardValue &&... value) { return this->add_overwrite__impl( - std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash_(key)); + std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...); } /** @@ -413,12 +413,12 @@ class Map { { return this->pop_default_as(key, std::move(default_value)); } - template<typename ForwardKey, typename ForwardValue> - Value pop_default_as(const ForwardKey &key, ForwardValue &&default_value) + template<typename ForwardKey, typename... ForwardValue> + Value pop_default_as(const ForwardKey &key, ForwardValue &&... default_value) { Slot *slot = this->lookup_slot_ptr(key, hash_(key)); if (slot == nullptr) { - return std::forward<ForwardValue>(default_value); + return Value(std::forward<ForwardValue>(default_value)...); } Value value = std::move(*slot->value()); slot->remove(); @@ -525,15 +525,15 @@ class Map { { return this->lookup_default_as(key, default_value); } - template<typename ForwardKey, typename ForwardValue> - Value lookup_default_as(const ForwardKey &key, ForwardValue &&default_value) const + template<typename ForwardKey, typename... ForwardValue> + Value lookup_default_as(const ForwardKey &key, ForwardValue &&... default_value) const { const Value *ptr = this->lookup_ptr_as(key); if (ptr != nullptr) { return *ptr; } else { - return std::forward<ForwardValue>(default_value); + return Value(std::forward<ForwardValue>(default_value)...); } } @@ -557,11 +557,11 @@ class Map { { return this->lookup_or_add_as(std::move(key), std::move(value)); } - template<typename ForwardKey, typename ForwardValue> - Value &lookup_or_add_as(ForwardKey &&key, ForwardValue &&value) + template<typename ForwardKey, typename... ForwardValue> + Value &lookup_or_add_as(ForwardKey &&key, ForwardValue &&... value) { return this->lookup_or_add__impl( - std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash_(key)); + std::forward<ForwardKey>(key), hash_(key), std::forward<ForwardValue>(value)...); } /** @@ -982,7 +982,7 @@ class Map { SLOT_PROBING_BEGIN (ProbingStrategy, hash, new_slot_mask, slot_index) { Slot &slot = new_slots[slot_index]; if (slot.is_empty()) { - slot.occupy(std::move(*old_slot.key()), std::move(*old_slot.value()), hash); + slot.occupy(std::move(*old_slot.key()), hash, std::move(*old_slot.value())); return; } } @@ -996,8 +996,8 @@ class Map { new (this) Map(NoExceptConstructor(), allocator); } - template<typename ForwardKey, typename ForwardValue> - void add_new__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash) + template<typename ForwardKey, typename... ForwardValue> + void add_new__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&... value) { BLI_assert(!this->contains_as(key)); @@ -1005,7 +1005,7 @@ class Map { MAP_SLOT_PROBING_BEGIN (hash, slot) { if (slot.is_empty()) { - slot.occupy(std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash); + slot.occupy(std::forward<ForwardKey>(key), hash, std::forward<ForwardValue>(value)...); occupied_and_removed_slots_++; return; } @@ -1013,14 +1013,14 @@ class Map { MAP_SLOT_PROBING_END(); } - template<typename ForwardKey, typename ForwardValue> - bool add__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash) + template<typename ForwardKey, typename... ForwardValue> + bool add__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&... value) { this->ensure_can_add(); MAP_SLOT_PROBING_BEGIN (hash, slot) { if (slot.is_empty()) { - slot.occupy(std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash); + slot.occupy(std::forward<ForwardKey>(key), hash, std::forward<ForwardValue>(value)...); occupied_and_removed_slots_++; return true; } @@ -1075,7 +1075,7 @@ class Map { MAP_SLOT_PROBING_BEGIN (hash, slot) { if (slot.is_empty()) { - slot.occupy(std::forward<ForwardKey>(key), create_value(), hash); + slot.occupy(std::forward<ForwardKey>(key), hash, create_value()); occupied_and_removed_slots_++; return *slot.value(); } @@ -1086,14 +1086,14 @@ class Map { MAP_SLOT_PROBING_END(); } - template<typename ForwardKey, typename ForwardValue> - Value &lookup_or_add__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash) + template<typename ForwardKey, typename... ForwardValue> + Value &lookup_or_add__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&... value) { this->ensure_can_add(); MAP_SLOT_PROBING_BEGIN (hash, slot) { if (slot.is_empty()) { - slot.occupy(std::forward<ForwardKey>(key), std::forward<ForwardValue>(value), hash); + slot.occupy(std::forward<ForwardKey>(key), hash, std::forward<ForwardValue>(value)...); occupied_and_removed_slots_++; return *slot.value(); } @@ -1104,15 +1104,15 @@ class Map { MAP_SLOT_PROBING_END(); } - template<typename ForwardKey, typename ForwardValue> - bool add_overwrite__impl(ForwardKey &&key, ForwardValue &&value, uint64_t hash) + template<typename ForwardKey, typename... ForwardValue> + bool add_overwrite__impl(ForwardKey &&key, uint64_t hash, ForwardValue &&... value) { auto create_func = [&](Value *ptr) { - new (static_cast<void *>(ptr)) Value(std::forward<ForwardValue>(value)); + new (static_cast<void *>(ptr)) Value(std::forward<ForwardValue>(value)...); return true; }; auto modify_func = [&](Value *ptr) { - *ptr = std::forward<ForwardValue>(value); + *ptr = Value(std::forward<ForwardValue>(value)...); return false; }; return this->add_or_modify__impl( @@ -1221,16 +1221,18 @@ template<typename Key, typename Value> class StdUnorderedMapWrapper { map_.reserve(n); } - template<typename ForwardKey, typename ForwardValue> - void add_new(ForwardKey &&key, ForwardValue &&value) + template<typename ForwardKey, typename... ForwardValue> + void add_new(ForwardKey &&key, ForwardValue &&... value) { - map_.insert({std::forward<ForwardKey>(key), std::forward<ForwardValue>(value)}); + map_.insert({std::forward<ForwardKey>(key), Value(std::forward<ForwardValue>(value)...)}); } - template<typename ForwardKey, typename ForwardValue> - bool add(ForwardKey &&key, ForwardValue &&value) + template<typename ForwardKey, typename... ForwardValue> + bool add(ForwardKey &&key, ForwardValue &&... value) { - return map_.insert({std::forward<ForwardKey>(key), std::forward<ForwardValue>(value)}).second; + return map_ + .insert({std::forward<ForwardKey>(key), Value(std::forward<ForwardValue>(value)...)}) + .second; } bool contains(const Key &key) const diff --git a/source/blender/blenlib/BLI_map_slots.hh b/source/blender/blenlib/BLI_map_slots.hh index c0cb3091a8e..1b4ca11af41 100644 --- a/source/blender/blenlib/BLI_map_slots.hh +++ b/source/blender/blenlib/BLI_map_slots.hh @@ -195,11 +195,11 @@ template<typename Key, typename Value> class SimpleMapSlot { * Change the state of this slot from empty/removed to occupied. The key/value has to be * constructed by calling the constructor with the given key/value as parameter. */ - template<typename ForwardKey, typename ForwardValue> - void occupy(ForwardKey &&key, ForwardValue &&value, uint64_t hash) + template<typename ForwardKey, typename... ForwardValue> + void occupy(ForwardKey &&key, uint64_t hash, ForwardValue &&... value) { BLI_assert(!this->is_occupied()); - new (&value_buffer_) Value(std::forward<ForwardValue>(value)); + new (&value_buffer_) Value(std::forward<ForwardValue>(value)...); this->occupy_no_value(std::forward<ForwardKey>(key), hash); state_ = Occupied; } @@ -315,12 +315,12 @@ template<typename Key, typename Value, typename KeyInfo> class IntrusiveMapSlot return is_equal(key, key_); } - template<typename ForwardKey, typename ForwardValue> - void occupy(ForwardKey &&key, ForwardValue &&value, uint64_t hash) + template<typename ForwardKey, typename... ForwardValue> + void occupy(ForwardKey &&key, uint64_t hash, ForwardValue &&... value) { BLI_assert(!this->is_occupied()); BLI_assert(KeyInfo::is_not_empty_or_removed(key)); - new (&value_buffer_) Value(std::forward<ForwardValue>(value)); + new (&value_buffer_) Value(std::forward<ForwardValue>(value)...); this->occupy_no_value(std::forward<ForwardKey>(key), hash); } diff --git a/source/blender/blenlib/BLI_span.hh b/source/blender/blenlib/BLI_span.hh index fe511793c46..c3876d4eaf8 100644 --- a/source/blender/blenlib/BLI_span.hh +++ b/source/blender/blenlib/BLI_span.hh @@ -94,7 +94,7 @@ template<typename T> class Span { using iterator = const T *; using size_type = int64_t; - private: + protected: const T *data_ = nullptr; int64_t size_ = 0; @@ -477,7 +477,7 @@ template<typename T> class MutableSpan { using iterator = T *; using size_type = int64_t; - private: + protected: T *data_; int64_t size_; @@ -662,6 +662,16 @@ template<typename T> class MutableSpan { } /** + * Return a reference to the first element in the array. This invokes undefined behavior when the + * array is empty. + */ + constexpr T &first() const + { + BLI_assert(size_ > 0); + return data_[0]; + } + + /** * Returns a reference to the last element. This invokes undefined behavior when the array is * empty. */ diff --git a/source/blender/blenlib/BLI_stack.hh b/source/blender/blenlib/BLI_stack.hh index 19f77078c5b..d66316a95d9 100644 --- a/source/blender/blenlib/BLI_stack.hh +++ b/source/blender/blenlib/BLI_stack.hh @@ -232,13 +232,14 @@ class Stack { { this->push_as(std::move(value)); } - template<typename ForwardT> void push_as(ForwardT &&value) + /* This is similar to `std::stack::emplace`. */ + template<typename... ForwardT> void push_as(ForwardT &&... value) { if (top_ == top_chunk_->capacity_end) { this->activate_next_chunk(1); } try { - new (top_) T(std::forward<ForwardT>(value)); + new (top_) T(std::forward<ForwardT>(value)...); top_++; size_++; } diff --git a/source/blender/blenlib/BLI_vector.hh b/source/blender/blenlib/BLI_vector.hh index 328d623787b..3ffd5309a04 100644 --- a/source/blender/blenlib/BLI_vector.hh +++ b/source/blender/blenlib/BLI_vector.hh @@ -437,13 +437,17 @@ class Vector { */ void append(const T &value) { - this->ensure_space_for_one(); - this->append_unchecked(value); + this->append_as(value); } void append(T &&value) { + this->append_as(std::move(value)); + } + /* This is similar to `std::vector::emplace_back`. */ + template<typename... ForwardValue> void append_as(ForwardValue &&...value) + { this->ensure_space_for_one(); - this->append_unchecked(std::move(value)); + this->append_unchecked_as(std::forward<ForwardValue>(value)...); } /** @@ -474,10 +478,18 @@ class Vector { * behavior when not enough capacity has been reserved beforehand. Only use this in performance * critical code. */ - template<typename ForwardT> void append_unchecked(ForwardT &&value) + void append_unchecked(const T &value) + { + this->append_unchecked_as(value); + } + void append_unchecked(T &&value) + { + this->append_unchecked_as(std::move(value)); + } + template<typename... ForwardT> void append_unchecked_as(ForwardT &&...value) { BLI_assert(end_ < capacity_end_); - new (end_) T(std::forward<ForwardT>(value)); + new (end_) T(std::forward<ForwardT>(value)...); end_++; UPDATE_VECTOR_SIZE(this); } @@ -657,6 +669,21 @@ class Vector { } /** + * Return a reference to the first element in the vector. + * This invokes undefined behavior when the vector is empty. + */ + const T &first() const + { + BLI_assert(this->size() > 0); + return *begin_; + } + T &first() + { + BLI_assert(this->size() > 0); + return *begin_; + } + + /** * Return how many values are currently stored in the vector. */ int64_t size() const diff --git a/source/blender/blenlib/BLI_virtual_array.hh b/source/blender/blenlib/BLI_virtual_array.hh index f9b0aaa7de6..eae15f0300c 100644 --- a/source/blender/blenlib/BLI_virtual_array.hh +++ b/source/blender/blenlib/BLI_virtual_array.hh @@ -37,6 +37,7 @@ * see of the increased compile time and binary size is worth it. */ +#include "BLI_array.hh" #include "BLI_span.hh" namespace blender { @@ -71,6 +72,11 @@ template<typename T> class VArray { return size_ == 0; } + IndexRange index_range() const + { + return IndexRange(size_); + } + /* Returns true when the virtual array is stored as a span internally. */ bool is_span() const { @@ -82,13 +88,13 @@ template<typename T> class VArray { /* Returns the internally used span of the virtual array. This invokes undefined behavior is the * virtual array is not stored as a span internally. */ - Span<T> get_span() const + Span<T> get_internal_span() const { BLI_assert(this->is_span()); if (size_ == 0) { return {}; } - return this->get_span_impl(); + return this->get_internal_span_impl(); } /* Returns true when the virtual array returns the same value for every index. */ @@ -102,20 +108,35 @@ template<typename T> class VArray { /* Returns the value that is returned for every index. This invokes undefined behavior if the * virtual array would not return the same value for every index. */ - T get_single() const + T get_internal_single() const { BLI_assert(this->is_single()); if (size_ == 1) { return this->get(0); } - return this->get_single_impl(); + return this->get_internal_single_impl(); } + /* Get the element at a specific index. Note that this operator cannot be used to assign values + * to an index, because the return value is not a reference. */ T operator[](const int64_t index) const { return this->get(index); } + /* Copy the entire virtual array into a span. */ + void materialize(MutableSpan<T> r_span) const + { + BLI_assert(size_ == r_span.size()); + this->materialize_impl(r_span); + } + + void materialize_to_uninitialized(MutableSpan<T> r_span) const + { + BLI_assert(size_ == r_span.size()); + this->materialize_to_uninitialized_impl(r_span); + } + protected: virtual T get_impl(const int64_t index) const = 0; @@ -124,7 +145,7 @@ template<typename T> class VArray { return false; } - virtual Span<T> get_span_impl() const + virtual Span<T> get_internal_span_impl() const { BLI_assert_unreachable(); return {}; @@ -135,56 +156,201 @@ template<typename T> class VArray { return false; } - virtual T get_single_impl() const + virtual T get_internal_single_impl() const { /* Provide a default implementation, so that subclasses don't have to provide it. This method * should never be called because `is_single_impl` returns false by default. */ BLI_assert_unreachable(); return T(); } + + virtual void materialize_impl(MutableSpan<T> r_span) const + { + if (this->is_span()) { + const Span<T> span = this->get_internal_span(); + initialized_copy_n(span.data(), size_, r_span.data()); + } + else if (this->is_single()) { + const T single = this->get_internal_single(); + initialized_fill_n(r_span.data(), size_, single); + } + else { + const int64_t size = size_; + for (int64_t i = 0; i < size; i++) { + r_span[i] = this->get(i); + } + } + } + + virtual void materialize_to_uninitialized_impl(MutableSpan<T> r_span) const + { + if (this->is_span()) { + const Span<T> span = this->get_internal_span(); + uninitialized_copy_n(span.data(), size_, r_span.data()); + } + else if (this->is_single()) { + const T single = this->get_internal_single(); + uninitialized_fill_n(r_span.data(), size_, single); + } + else { + const int64_t size = size_; + T *dst = r_span.data(); + for (int64_t i = 0; i < size; i++) { + new (dst + i) T(this->get(i)); + } + } + } +}; + +/* Similar to VArray, but the elements are mutable. */ +template<typename T> class VMutableArray : public VArray<T> { + public: + VMutableArray(const int64_t size) : VArray<T>(size) + { + } + + void set(const int64_t index, T value) + { + BLI_assert(index >= 0); + BLI_assert(index < this->size_); + this->set_impl(index, std::move(value)); + } + + /* Copy the values from the source span to all elements in the virtual array. */ + void set_all(Span<T> src) + { + BLI_assert(src.size() == this->size_); + this->set_all_impl(src); + } + + MutableSpan<T> get_internal_span() + { + BLI_assert(this->is_span()); + Span<T> span = static_cast<const VArray<T> *>(this)->get_internal_span(); + return MutableSpan<T>(const_cast<T *>(span.data()), span.size()); + } + + protected: + virtual void set_impl(const int64_t index, T value) = 0; + + virtual void set_all_impl(Span<T> src) + { + if (this->is_span()) { + const MutableSpan<T> span = this->get_internal_span(); + initialized_copy_n(src.data(), this->size_, span.data()); + } + else { + const int64_t size = this->size_; + for (int64_t i = 0; i < size; i++) { + this->set(i, src[i]); + } + } + } }; +template<typename T> using VArrayPtr = std::unique_ptr<VArray<T>>; +template<typename T> using VMutableArrayPtr = std::unique_ptr<VMutableArray<T>>; + /** - * A virtual array implementation for a span. This class is final so that it can be devirtualized - * by the compiler in some cases (e.g. when #devirtualize_varray is used). + * A virtual array implementation for a span. Methods in this class are final so that it can be + * devirtualized by the compiler in some cases (e.g. when #devirtualize_varray is used). */ -template<typename T> class VArrayForSpan final : public VArray<T> { - private: - const T *data_; +template<typename T> class VArray_For_Span : public VArray<T> { + protected: + const T *data_ = nullptr; public: - VArrayForSpan(const Span<T> data) : VArray<T>(data.size()), data_(data.data()) + VArray_For_Span(const Span<T> data) : VArray<T>(data.size()), data_(data.data()) { } protected: - T get_impl(const int64_t index) const override + VArray_For_Span(const int64_t size) : VArray<T>(size) + { + } + + T get_impl(const int64_t index) const final + { + return data_[index]; + } + + bool is_span_impl() const final + { + return true; + } + + Span<T> get_internal_span_impl() const final + { + return Span<T>(data_, this->size_); + } +}; + +template<typename T> class VMutableArray_For_MutableSpan : public VMutableArray<T> { + protected: + T *data_ = nullptr; + + public: + VMutableArray_For_MutableSpan(const MutableSpan<T> data) + : VMutableArray<T>(data.size()), data_(data.data()) + { + } + + protected: + VMutableArray_For_MutableSpan(const int64_t size) : VMutableArray<T>(size) + { + } + + T get_impl(const int64_t index) const final { return data_[index]; } + void set_impl(const int64_t index, T value) final + { + data_[index] = value; + } + bool is_span_impl() const override { return true; } - Span<T> get_span_impl() const override + Span<T> get_internal_span_impl() const override { return Span<T>(data_, this->size_); } }; /** + * A variant of `VArray_For_Span` that owns the underlying data. + * The `Container` type has to implement a `size()` and `data()` method. + * The `data()` method has to return a pointer to the first element in the continuous array of + * elements. + */ +template<typename Container, typename T = typename Container::value_type> +class VArray_For_ArrayContainer : public VArray_For_Span<T> { + private: + Container container_; + + public: + VArray_For_ArrayContainer(Container container) + : VArray_For_Span<T>((int64_t)container.size()), container_(std::move(container)) + { + this->data_ = container_.data(); + } +}; + +/** * A virtual array implementation that returns the same value for every index. This class is final * so that it can be devirtualized by the compiler in some cases (e.g. when #devirtualize_varray is * used). */ -template<typename T> class VArrayForSingle final : public VArray<T> { +template<typename T> class VArray_For_Single final : public VArray<T> { private: T value_; public: - VArrayForSingle(T value, const int64_t size) : VArray<T>(size), value_(std::move(value)) + VArray_For_Single(T value, const int64_t size) : VArray<T>(size), value_(std::move(value)) { } @@ -199,7 +365,7 @@ template<typename T> class VArrayForSingle final : public VArray<T> { return this->size_ == 1; } - Span<T> get_span_impl() const override + Span<T> get_internal_span_impl() const override { return Span<T>(&value_, 1); } @@ -209,13 +375,171 @@ template<typename T> class VArrayForSingle final : public VArray<T> { return true; } - T get_single_impl() const override + T get_internal_single_impl() const override { return value_; } }; /** + * In many cases a virtual array is a span internally. In those cases, access to individual could + * be much more efficient than calling a virtual method. When the underlying virtual array is not a + * span, this class allocates a new array and copies the values over. + * + * This should be used in those cases: + * - All elements in the virtual array are accessed multiple times. + * - In most cases, the underlying virtual array is a span, so no copy is necessary to benefit + * from faster access. + * - An API is called, that does not accept virtual arrays, but only spans. + */ +template<typename T> class VArray_Span final : public Span<T> { + private: + const VArray<T> &varray_; + Array<T> owned_data_; + + public: + VArray_Span(const VArray<T> &varray) : Span<T>(), varray_(varray) + { + this->size_ = varray_.size(); + if (varray_.is_span()) { + this->data_ = varray_.get_internal_span().data(); + } + else { + owned_data_.~Array(); + new (&owned_data_) Array<T>(varray_.size(), NoInitialization{}); + varray_.materialize_to_uninitialized(owned_data_); + this->data_ = owned_data_.data(); + } + } +}; + +/** + * Same as VArray_Span, but for a mutable span. + * The important thing to note is that when changing this span, the results might not be + * immediately reflected in the underlying virtual array (only when the virtual array is a span + * internally). The #save method can be used to write all changes to the underlying virtual array, + * if necessary. + */ +template<typename T> class VMutableArray_Span final : public MutableSpan<T> { + private: + VMutableArray<T> &varray_; + Array<T> owned_data_; + bool save_has_been_called_ = false; + bool show_not_saved_warning_ = true; + + public: + /* Create a span for any virtual array. This is cheap when the virtual array is a span itself. If + * not, a new array has to be allocated as a wrapper for the underlying virtual array. */ + VMutableArray_Span(VMutableArray<T> &varray, const bool copy_values_to_span = true) + : MutableSpan<T>(), varray_(varray) + { + this->size_ = varray_.size(); + if (varray_.is_span()) { + this->data_ = varray_.get_internal_span().data(); + } + else { + if (copy_values_to_span) { + owned_data_.~Array(); + new (&owned_data_) Array<T>(varray_.size(), NoInitialization{}); + varray_.materialize_to_uninitialized(owned_data_); + } + else { + owned_data_.reinitialize(varray_.size()); + } + this->data_ = owned_data_.data(); + } + } + + ~VMutableArray_Span() + { + if (show_not_saved_warning_) { + if (!save_has_been_called_) { + std::cout << "Warning: Call `save()` to make sure that changes persist in all cases.\n"; + } + } + } + + /* Write back all values from a temporary allocated array to the underlying virtual array. */ + void save() + { + save_has_been_called_ = true; + if (this->data_ != owned_data_.data()) { + return; + } + varray_.set_all(owned_data_); + } + + void disable_not_applied_warning() + { + show_not_saved_warning_ = false; + } +}; + +/** + * This class makes it easy to create a virtual array for an existing function or lambda. The + * `GetFunc` should take a single `index` argument and return the value at that index. + */ +template<typename T, typename GetFunc> class VArray_For_Func final : public VArray<T> { + private: + GetFunc get_func_; + + public: + VArray_For_Func(const int64_t size, GetFunc get_func) + : VArray<T>(size), get_func_(std::move(get_func)) + { + } + + private: + T get_impl(const int64_t index) const override + { + return get_func_(index); + } +}; + +template<typename StructT, typename ElemT, ElemT (*GetFunc)(const StructT &)> +class VArray_For_DerivedSpan : public VArray<ElemT> { + private: + const StructT *data_; + + public: + VArray_For_DerivedSpan(const Span<StructT> data) : VArray<ElemT>(data.size()), data_(data.data()) + { + } + + private: + ElemT get_impl(const int64_t index) const override + { + return GetFunc(data_[index]); + } +}; + +template<typename StructT, + typename ElemT, + ElemT (*GetFunc)(const StructT &), + void (*SetFunc)(StructT &, ElemT)> +class VMutableArray_For_DerivedSpan : public VMutableArray<ElemT> { + private: + StructT *data_; + + public: + VMutableArray_For_DerivedSpan(const MutableSpan<StructT> data) + : VMutableArray<ElemT>(data.size()), data_(data.data()) + { + } + + private: + ElemT get_impl(const int64_t index) const override + { + return GetFunc(data_[index]); + } + + void set_impl(const int64_t index, ElemT value) override + { + SetFunc(data_[index], std::move(value)); + } +}; + +/** * Generate multiple versions of the given function optimized for different virtual arrays. * One has to be careful with nesting multiple devirtualizations, because that results in an * exponential number of function instantiations (increasing compile time and binary size). @@ -229,14 +553,14 @@ inline void devirtualize_varray(const VArray<T> &varray, const Func &func, bool /* Support disabling the devirtualization to simplify benchmarking. */ if (enable) { if (varray.is_single()) { - /* `VArrayForSingle` can be used for devirtualization, because it is declared `final`. */ - const VArrayForSingle<T> varray_single{varray.get_single(), varray.size()}; + /* `VArray_For_Single` can be used for devirtualization, because it is declared `final`. */ + const VArray_For_Single<T> varray_single{varray.get_internal_single(), varray.size()}; func(varray_single); return; } if (varray.is_span()) { - /* `VArrayForSpan` can be used for devirtualization, because it is declared `final`. */ - const VArrayForSpan<T> varray_span{varray.get_span()}; + /* `VArray_For_Span` can be used for devirtualization, because it is declared `final`. */ + const VArray_For_Span<T> varray_span{varray.get_internal_span()}; func(varray_span); return; } @@ -262,26 +586,26 @@ inline void devirtualize_varray2(const VArray<T1> &varray1, const bool is_single1 = varray1.is_single(); const bool is_single2 = varray2.is_single(); if (is_span1 && is_span2) { - const VArrayForSpan<T1> varray1_span{varray1.get_span()}; - const VArrayForSpan<T2> varray2_span{varray2.get_span()}; + const VArray_For_Span<T1> varray1_span{varray1.get_internal_span()}; + const VArray_For_Span<T2> varray2_span{varray2.get_internal_span()}; func(varray1_span, varray2_span); return; } if (is_span1 && is_single2) { - const VArrayForSpan<T1> varray1_span{varray1.get_span()}; - const VArrayForSingle<T2> varray2_single{varray2.get_single(), varray2.size()}; + const VArray_For_Span<T1> varray1_span{varray1.get_internal_span()}; + const VArray_For_Single<T2> varray2_single{varray2.get_internal_single(), varray2.size()}; func(varray1_span, varray2_single); return; } if (is_single1 && is_span2) { - const VArrayForSingle<T1> varray1_single{varray1.get_single(), varray1.size()}; - const VArrayForSpan<T2> varray2_span{varray2.get_span()}; + const VArray_For_Single<T1> varray1_single{varray1.get_internal_single(), varray1.size()}; + const VArray_For_Span<T2> varray2_span{varray2.get_internal_span()}; func(varray1_single, varray2_span); return; } if (is_single1 && is_single2) { - const VArrayForSingle<T1> varray1_single{varray1.get_single(), varray1.size()}; - const VArrayForSingle<T2> varray2_single{varray2.get_single(), varray2.size()}; + const VArray_For_Single<T1> varray1_single{varray1.get_internal_single(), varray1.size()}; + const VArray_For_Single<T2> varray2_single{varray2.get_internal_single(), varray2.size()}; func(varray1_single, varray2_single); return; } diff --git a/source/blender/blenlib/tests/BLI_map_test.cc b/source/blender/blenlib/tests/BLI_map_test.cc index f1ae8fb3921..bb15f7f0d8d 100644 --- a/source/blender/blenlib/tests/BLI_map_test.cc +++ b/source/blender/blenlib/tests/BLI_map_test.cc @@ -604,6 +604,15 @@ TEST(map, GenericAlgorithms) EXPECT_EQ(std::count(map.keys().begin(), map.keys().end(), 7), 1); } +TEST(map, AddAsVariadic) +{ + Map<int, StringRef> map; + map.add_as(3, "hello", 2); + map.add_as(2, "test", 1); + EXPECT_EQ(map.lookup(3), "he"); + EXPECT_EQ(map.lookup(2), "t"); +} + /** * Set this to 1 to activate the benchmark. It is disabled by default, because it prints a lot. */ diff --git a/source/blender/blenlib/tests/BLI_stack_cxx_test.cc b/source/blender/blenlib/tests/BLI_stack_cxx_test.cc index f1fcdae3a52..b3108381d78 100644 --- a/source/blender/blenlib/tests/BLI_stack_cxx_test.cc +++ b/source/blender/blenlib/tests/BLI_stack_cxx_test.cc @@ -93,6 +93,15 @@ TEST(stack, Push) EXPECT_EQ(stack.size(), 2); } +TEST(stack, PushAs) +{ + Stack<StringRef> stack; + stack.push_as("hello", 3); + stack.push_as("world", 1); + EXPECT_EQ(stack.pop(), "w"); + EXPECT_EQ(stack.pop(), "hel"); +} + TEST(stack, PushMultiple) { Stack<int> stack; diff --git a/source/blender/blenlib/tests/BLI_vector_test.cc b/source/blender/blenlib/tests/BLI_vector_test.cc index 462f13c15ab..e8636168308 100644 --- a/source/blender/blenlib/tests/BLI_vector_test.cc +++ b/source/blender/blenlib/tests/BLI_vector_test.cc @@ -248,6 +248,15 @@ TEST(vector, Append) EXPECT_EQ(vec[2], 7); } +TEST(vector, AppendAs) +{ + Vector<StringRef> vec; + vec.append_as("hello", 2); + vec.append_as("world", 3); + EXPECT_EQ(vec[0], "he"); + EXPECT_EQ(vec[1], "wor"); +} + TEST(vector, AppendAndGetIndex) { Vector<int> vec; diff --git a/source/blender/blenlib/tests/BLI_virtual_array_test.cc b/source/blender/blenlib/tests/BLI_virtual_array_test.cc index ac25229cd69..a6d2ca10315 100644 --- a/source/blender/blenlib/tests/BLI_virtual_array_test.cc +++ b/source/blender/blenlib/tests/BLI_virtual_array_test.cc @@ -1,26 +1,29 @@ /* Apache License, Version 2.0 */ +#include "BLI_array.hh" #include "BLI_strict_flags.h" +#include "BLI_vector.hh" +#include "BLI_vector_set.hh" #include "BLI_virtual_array.hh" #include "testing/testing.h" namespace blender::tests { -TEST(virtual_array, ForSpan) +TEST(virtual_array, Span) { std::array<int, 5> data = {3, 4, 5, 6, 7}; - VArrayForSpan<int> varray{data}; + VArray_For_Span<int> varray{data}; EXPECT_EQ(varray.size(), 5); EXPECT_EQ(varray.get(0), 3); EXPECT_EQ(varray.get(4), 7); EXPECT_TRUE(varray.is_span()); EXPECT_FALSE(varray.is_single()); - EXPECT_EQ(varray.get_span().data(), data.data()); + EXPECT_EQ(varray.get_internal_span().data(), data.data()); } -TEST(virtual_array, ForSingle) +TEST(virtual_array, Single) { - VArrayForSingle<int> varray{10, 4}; + VArray_For_Single<int> varray{10, 4}; EXPECT_EQ(varray.size(), 4); EXPECT_EQ(varray.get(0), 10); EXPECT_EQ(varray.get(3), 10); @@ -28,4 +31,124 @@ TEST(virtual_array, ForSingle) EXPECT_TRUE(varray.is_single()); } +TEST(virtual_array, Array) +{ + Array<int> array = {1, 2, 3, 5, 8}; + { + VArray_For_ArrayContainer varray{array}; + EXPECT_EQ(varray.size(), 5); + EXPECT_EQ(varray[0], 1); + EXPECT_EQ(varray[2], 3); + EXPECT_EQ(varray[3], 5); + EXPECT_TRUE(varray.is_span()); + } + { + VArray_For_ArrayContainer varray{std::move(array)}; + EXPECT_EQ(varray.size(), 5); + EXPECT_EQ(varray[0], 1); + EXPECT_EQ(varray[2], 3); + EXPECT_EQ(varray[3], 5); + EXPECT_TRUE(varray.is_span()); + } + { + VArray_For_ArrayContainer varray{array}; /* NOLINT: bugprone-use-after-move */ + EXPECT_TRUE(varray.is_empty()); + } +} + +TEST(virtual_array, Vector) +{ + Vector<int> vector = {9, 8, 7, 6}; + VArray_For_ArrayContainer varray{std::move(vector)}; + EXPECT_EQ(varray.size(), 4); + EXPECT_EQ(varray[0], 9); + EXPECT_EQ(varray[3], 6); +} + +TEST(virtual_array, StdVector) +{ + std::vector<int> vector = {5, 6, 7, 8}; + VArray_For_ArrayContainer varray{std::move(vector)}; + EXPECT_EQ(varray.size(), 4); + EXPECT_EQ(varray[0], 5); + EXPECT_EQ(varray[1], 6); +} + +TEST(virtual_array, StdArray) +{ + std::array<int, 4> array = {2, 3, 4, 5}; + VArray_For_ArrayContainer varray{array}; + EXPECT_EQ(varray.size(), 4); + EXPECT_EQ(varray[0], 2); + EXPECT_EQ(varray[1], 3); +} + +TEST(virtual_array, VectorSet) +{ + VectorSet<int> vector_set = {5, 3, 7, 3, 3, 5, 1}; + VArray_For_ArrayContainer varray{std::move(vector_set)}; + EXPECT_TRUE(vector_set.is_empty()); /* NOLINT: bugprone-use-after-move. */ + EXPECT_EQ(varray.size(), 4); + EXPECT_EQ(varray[0], 5); + EXPECT_EQ(varray[1], 3); + EXPECT_EQ(varray[2], 7); + EXPECT_EQ(varray[3], 1); +} + +TEST(virtual_array, Func) +{ + auto func = [](int64_t index) { return (int)(index * index); }; + VArray_For_Func<int, decltype(func)> varray{10, func}; + EXPECT_EQ(varray.size(), 10); + EXPECT_EQ(varray[0], 0); + EXPECT_EQ(varray[3], 9); + EXPECT_EQ(varray[9], 81); +} + +TEST(virtual_array, AsSpan) +{ + auto func = [](int64_t index) { return (int)(10 * index); }; + VArray_For_Func<int, decltype(func)> func_varray{10, func}; + VArray_Span span_varray{func_varray}; + EXPECT_EQ(span_varray.size(), 10); + Span<int> span = span_varray; + EXPECT_EQ(span.size(), 10); + EXPECT_EQ(span[0], 0); + EXPECT_EQ(span[3], 30); + EXPECT_EQ(span[6], 60); +} + +static int get_x(const std::array<int, 3> &item) +{ + return item[0]; +} + +static void set_x(std::array<int, 3> &item, int value) +{ + item[0] = value; +} + +TEST(virtual_array, DerivedSpan) +{ + Vector<std::array<int, 3>> vector; + vector.append({3, 4, 5}); + vector.append({1, 1, 1}); + { + VArray_For_DerivedSpan<std::array<int, 3>, int, get_x> varray{vector}; + EXPECT_EQ(varray.size(), 2); + EXPECT_EQ(varray[0], 3); + EXPECT_EQ(varray[1], 1); + } + { + VMutableArray_For_DerivedSpan<std::array<int, 3>, int, get_x, set_x> varray{vector}; + EXPECT_EQ(varray.size(), 2); + EXPECT_EQ(varray[0], 3); + EXPECT_EQ(varray[1], 1); + varray.set(0, 10); + varray.set(1, 20); + EXPECT_EQ(vector[0][0], 10); + EXPECT_EQ(vector[1][0], 20); + } +} + } // namespace blender::tests |