diff options
Diffstat (limited to 'source/blender/blenlib')
26 files changed, 4377 insertions, 33 deletions
diff --git a/source/blender/blenlib/BLI_float3.hh b/source/blender/blenlib/BLI_float3.hh index b2633985ac7..a0979bc75bd 100644 --- a/source/blender/blenlib/BLI_float3.hh +++ b/source/blender/blenlib/BLI_float3.hh @@ -143,6 +143,17 @@ struct float3 { return normalize_v3(*this); } + /** + * Normalizes the vector in place. + */ + void normalize() + { + normalize_v3(*this); + } + + /** + * Returns a normalized vector. The original vector is not changed. + */ float3 normalized() const { float3 result; diff --git a/source/blender/blenlib/BLI_float4x4.hh b/source/blender/blenlib/BLI_float4x4.hh index 185cffd13ac..b4f12f17cc2 100644 --- a/source/blender/blenlib/BLI_float4x4.hh +++ b/source/blender/blenlib/BLI_float4x4.hh @@ -71,8 +71,8 @@ struct float4x4 { float4x4 inverted() const { - float result[4][4]; - invert_m4_m4(result, values); + float4x4 result; + invert_m4_m4(result.values, values); return result; } @@ -86,6 +86,18 @@ struct float4x4 { return this->inverted(); } + float4x4 transposed() const + { + float4x4 result; + transpose_m4_m4(result.values, values); + return result; + } + + float4x4 inverted_transposed_affine() const + { + return this->inverted_affine().transposed(); + } + struct float3x3_ref { const float4x4 &data; diff --git a/source/blender/blenlib/BLI_multi_value_map.hh b/source/blender/blenlib/BLI_multi_value_map.hh new file mode 100644 index 00000000000..c20c4ef9677 --- /dev/null +++ b/source/blender/blenlib/BLI_multi_value_map.hh @@ -0,0 +1,134 @@ +/* + * 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. + */ + +#ifndef __BLI_MULTI_VALUE_MAP_HH__ +#define __BLI_MULTI_VALUE_MAP_HH__ + +/** \file + * \ingroup bli + * + * A `blender::MultiValueMap<Key, Value>` is an unordered associative container that stores + * key-value pairs. It is different from `blender::Map` in that it can store multiple values for + * the same key. The list of values that corresponds to a specific key can contain duplicates + * and their order is maintained. + * + * This data structure is different from a `std::multi_map`, because multi_map can store the same + * key more than once and MultiValueMap can't. + * + * Currently, this class exists mainly for convenience. There are no performance benefits over + * using Map<Key, Vector<Value>>. In the future, a better implementation for this data structure + * can be developed. + */ + +#include "BLI_map.hh" +#include "BLI_vector.hh" + +namespace blender { + +template<typename Key, typename Value> class MultiValueMap { + private: + using MapType = Map<Key, Vector<Value>>; + MapType map_; + + public: + /** + * Add a new value for the given key. If the map contains the key already, the value will be + * appended to the list of corresponding values. + */ + void add(const Key &key, const Value &value) + { + this->add_as(key, value); + } + void add(const Key &key, Value &&value) + { + this->add_as(key, std::move(value)); + } + void add(Key &&key, const Value &value) + { + this->add_as(std::move(key), value); + } + void add(Key &&key, Value &&value) + { + this->add_as(std::move(key), std::move(value)); + } + template<typename ForwardKey, typename ForwardValue> + void add_as(ForwardKey &&key, ForwardValue &&value) + { + Vector<Value> &vector = map_.lookup_or_add_default_as(std::forward<ForwardKey>(key)); + vector.append(std::forward<ForwardValue>(value)); + } + + /** + * Add all given values to the key. + */ + void add_multiple(const Key &key, Span<Value> values) + { + this->add_multiple_as(key, values); + } + void add_multiple(Key &&key, Span<Value> values) + { + this->add_multiple_as(std::move(key), values); + } + template<typename ForwardKey> void add_multiple_as(ForwardKey &&key, Span<Value> values) + { + Vector<Value> &vector = map_.lookup_or_add_default_as(std::forward<ForwardKey>(key)); + vector.extend(values); + } + + /** + * Get a span to all the values that are stored for the given key. + */ + Span<Value> lookup(const Key &key) const + { + return this->lookup_as(key); + } + template<typename ForwardKey> Span<Value> lookup_as(const ForwardKey &key) const + { + const Vector<Value> *vector = map_.lookup_ptr_as(key); + if (vector != nullptr) { + return vector->as_span(); + } + return {}; + } + + /** + * Note: This signature will change when the implementation changes. + */ + typename MapType::ItemIterator items() const + { + return map_.items(); + } + + /** + * Note: This signature will change when the implementation changes. + */ + typename MapType::KeyIterator keys() const + { + return map_.keys(); + } + + /** + * Note: This signature will change when the implementation changes. + */ + typename MapType::ValueIterator values() const + { + return map_.values(); + } +}; + +} // namespace blender + +#endif /* __BLI_MULTI_VALUE_MAP_HH__ */ diff --git a/source/blender/blenlib/BLI_rand.hh b/source/blender/blenlib/BLI_rand.hh index 612ac0bbe19..7a98ee0f2bb 100644 --- a/source/blender/blenlib/BLI_rand.hh +++ b/source/blender/blenlib/BLI_rand.hh @@ -63,6 +63,15 @@ class RandomNumberGenerator { } /** + * \return Random value (0..N), but never N. + */ + int32_t get_int32(int32_t max_exclusive) + { + BLI_assert(max_exclusive > 0); + return this->get_int32() % max_exclusive; + } + + /** * \return Random value (0..1), but never 1.0. */ double get_double() @@ -78,6 +87,35 @@ class RandomNumberGenerator { return (float)this->get_int32() / 0x80000000; } + template<typename T> void shuffle(MutableSpan<T> values) + { + /* Cannot shuffle arrays of this size yet. */ + BLI_assert(values.size() <= INT32_MAX); + + for (int i = values.size() - 1; i >= 2; i--) { + int j = this->get_int32(i); + if (i != j) { + std::swap(values[i], values[j]); + } + } + } + + /** + * Compute uniformly distributed barycentric coordinates. + */ + float3 get_barycentric_coordinates() + { + float rand1 = this->get_float(); + float rand2 = this->get_float(); + + if (rand1 + rand2 > 1.0f) { + rand1 = 1.0f - rand1; + rand2 = 1.0f - rand2; + } + + return float3(rand1, rand2, 1.0f - rand1 - rand2); + } + float2 get_unit_float2(); float3 get_unit_float3(); float2 get_triangle_sample(float2 v1, float2 v2, float2 v3); diff --git a/source/blender/blenlib/BLI_resource_collector.hh b/source/blender/blenlib/BLI_resource_collector.hh index 10d610da618..e1be87d8af2 100644 --- a/source/blender/blenlib/BLI_resource_collector.hh +++ b/source/blender/blenlib/BLI_resource_collector.hh @@ -79,6 +79,12 @@ class ResourceCollector : NonCopyable, NonMovable { */ template<typename T> void add(destruct_ptr<T> resource, const char *name) { + /* There is no need to keep track of such types. */ + if (std::is_trivially_destructible_v<T>) { + resource.release(); + return; + } + BLI_assert(resource.get() != nullptr); this->add( resource.release(), diff --git a/source/blender/blenlib/BLI_span.hh b/source/blender/blenlib/BLI_span.hh index 2d875fe73be..81b86f647f6 100644 --- a/source/blender/blenlib/BLI_span.hh +++ b/source/blender/blenlib/BLI_span.hh @@ -87,7 +87,7 @@ namespace blender { */ template<typename T> class Span { private: - const T *start_ = nullptr; + const T *data_ = nullptr; int64_t size_ = 0; public: @@ -96,13 +96,13 @@ template<typename T> class Span { */ Span() = default; - Span(const T *start, int64_t size) : start_(start), size_(size) + Span(const T *start, int64_t size) : data_(start), size_(size) { BLI_assert(size >= 0); } template<typename U, typename std::enable_if_t<is_convertible_pointer_v<U, T>> * = nullptr> - Span(const U *start, int64_t size) : start_((const T *)start), size_(size) + Span(const U *start, int64_t size) : data_((const T *)start), size_(size) { BLI_assert(size >= 0); } @@ -136,7 +136,7 @@ template<typename T> class Span { * Span<Derived *> -> Span<Base *> */ template<typename U, typename std::enable_if_t<is_convertible_pointer_v<U, T>> * = nullptr> - Span(Span<U> array) : start_((T *)array.data()), size_(array.size()) + Span(Span<U> array) : data_((T *)array.data()), size_(array.size()) { } @@ -149,7 +149,7 @@ template<typename T> class Span { BLI_assert(start >= 0); BLI_assert(size >= 0); BLI_assert(start + size <= this->size() || size == 0); - return Span(start_ + start, size); + return Span(data_ + start, size); } Span slice(IndexRange range) const @@ -207,17 +207,17 @@ template<typename T> class Span { */ const T *data() const { - return start_; + return data_; } const T *begin() const { - return start_; + return data_; } const T *end() const { - return start_ + size_; + return data_ + size_; } /** @@ -228,7 +228,7 @@ template<typename T> class Span { { BLI_assert(index >= 0); BLI_assert(index < size_); - return start_[index]; + return data_[index]; } /** @@ -300,7 +300,7 @@ template<typename T> class Span { const T &first() const { BLI_assert(size_ > 0); - return start_[0]; + return data_[0]; } /** @@ -310,7 +310,7 @@ template<typename T> class Span { const T &last() const { BLI_assert(size_ > 0); - return start_[size_ - 1]; + return data_[size_ - 1]; } /** @@ -320,7 +320,7 @@ template<typename T> class Span { T get(int64_t index, const T &fallback) const { if (index < size_ && index >= 0) { - return start_[index]; + return data_[index]; } return fallback; } @@ -336,9 +336,9 @@ template<typename T> class Span { BLI_assert(size_ < 1000); for (int64_t i = 0; i < size_; i++) { - const T &value = start_[i]; + const T &value = data_[i]; for (int64_t j = i + 1; j < size_; j++) { - if (value == start_[j]) { + if (value == data_[j]) { return true; } } @@ -358,7 +358,7 @@ template<typename T> class Span { BLI_assert(size_ < 1000); for (int64_t i = 0; i < size_; i++) { - const T &value = start_[i]; + const T &value = data_[i]; if (other.contains(value)) { return true; } @@ -383,7 +383,7 @@ template<typename T> class Span { int64_t first_index_try(const T &search_value) const { for (int64_t i = 0; i < size_; i++) { - if (start_[i] == search_value) { + if (data_[i] == search_value) { return i; } } @@ -406,7 +406,7 @@ template<typename T> class Span { { BLI_assert((size_ * sizeof(T)) % sizeof(NewT) == 0); int64_t new_size = size_ * sizeof(T) / sizeof(NewT); - return Span<NewT>(reinterpret_cast<const NewT *>(start_), new_size); + return Span<NewT>(reinterpret_cast<const NewT *>(data_), new_size); } /** @@ -439,13 +439,13 @@ template<typename T> class Span { */ template<typename T> class MutableSpan { private: - T *start_; + T *data_; int64_t size_; public: MutableSpan() = default; - MutableSpan(T *start, const int64_t size) : start_(start), size_(size) + MutableSpan(T *start, const int64_t size) : data_(start), size_(size) { } @@ -459,7 +459,7 @@ template<typename T> class MutableSpan { operator Span<T>() const { - return Span<T>(start_, size_); + return Span<T>(data_, size_); } /** @@ -475,7 +475,7 @@ template<typename T> class MutableSpan { */ void fill(const T &value) { - initialized_fill_n(start_, size_, value); + initialized_fill_n(data_, size_, value); } /** @@ -486,7 +486,7 @@ template<typename T> class MutableSpan { { for (int64_t i : indices) { BLI_assert(i < size_); - start_[i] = value; + data_[i] = value; } } @@ -496,23 +496,23 @@ template<typename T> class MutableSpan { */ T *data() const { - return start_; + return data_; } T *begin() const { - return start_; + return data_; } T *end() const { - return start_ + size_; + return data_ + size_; } T &operator[](const int64_t index) const { BLI_assert(index < this->size()); - return start_[index]; + return data_[index]; } /** @@ -522,7 +522,7 @@ template<typename T> class MutableSpan { MutableSpan slice(const int64_t start, const int64_t length) const { BLI_assert(start + length <= this->size()); - return MutableSpan(start_ + start, length); + return MutableSpan(data_ + start, length); } /** @@ -571,7 +571,7 @@ template<typename T> class MutableSpan { */ Span<T> as_span() const { - return Span<T>(start_, size_); + return Span<T>(data_, size_); } /** @@ -590,7 +590,7 @@ template<typename T> class MutableSpan { T &last() const { BLI_assert(size_ > 0); - return start_[size_ - 1]; + return data_[size_ - 1]; } /** @@ -609,13 +609,24 @@ template<typename T> class MutableSpan { } /** + * Copy all values from another span into this span. This invokes undefined behavior when the + * destination contains uninitialized data and T is not trivially copy constructible. + * The size of both spans is expected to be the same. + */ + void copy_from(Span<T> values) + { + BLI_assert(size_ == values.size()); + initialized_copy_n(values.data(), size_, data_); + } + + /** * Returns a new span to the same underlying memory buffer. No conversions are done. */ template<typename NewT> MutableSpan<NewT> cast() const { BLI_assert((size_ * sizeof(T)) % sizeof(NewT) == 0); int64_t new_size = size_ * sizeof(T) / sizeof(NewT); - return MutableSpan<NewT>(reinterpret_cast<NewT *>(start_), new_size); + return MutableSpan<NewT>(reinterpret_cast<NewT *>(data_), new_size); } }; diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h index bc35e969e6a..2699f2498ac 100644 --- a/source/blender/blenlib/BLI_utildefines.h +++ b/source/blender/blenlib/BLI_utildefines.h @@ -755,6 +755,43 @@ extern bool BLI_memory_is_zero(const void *arr, const size_t arr_size); /** \} */ /* -------------------------------------------------------------------- */ +/** \name C++ Macros + * \{ */ + +#ifdef __cplusplus + +/* Useful to port C code using enums to C++ where enums are strongly typed. + * To use after the enum declaration. */ +# define ENUM_OPERATORS(_enum_type) \ + inline constexpr _enum_type operator|(_enum_type a, _enum_type b) \ + { \ + return a = static_cast<_enum_type>(static_cast<int>(a) | b); \ + } \ + inline constexpr _enum_type operator&(_enum_type a, _enum_type b) \ + { \ + return a = static_cast<_enum_type>(static_cast<int>(a) & b); \ + } \ + inline constexpr _enum_type operator~(_enum_type a) \ + { \ + return a = static_cast<_enum_type>(~static_cast<int>(a)); \ + } \ + inline _enum_type &operator|=(_enum_type &a, _enum_type b) \ + { \ + return a = static_cast<_enum_type>(static_cast<int>(a) | b); \ + } \ + inline _enum_type &operator&=(_enum_type &a, _enum_type b) \ + { \ + return a = static_cast<_enum_type>(static_cast<int>(a) & b); \ + } + +#else +/* Output nothing. */ +# define ENUM_OPERATORS(_type) +#endif + +/** \} */ + +/* -------------------------------------------------------------------- */ /** \name Misc Macros * \{ */ diff --git a/source/blender/blenlib/BLI_vector.hh b/source/blender/blenlib/BLI_vector.hh index 1bb674093bb..7eac511bf4a 100644 --- a/source/blender/blenlib/BLI_vector.hh +++ b/source/blender/blenlib/BLI_vector.hh @@ -561,7 +561,7 @@ class Vector { /** * Return a reference to the last element in the vector. - * This will assert when the vector is empty. + * This invokes undefined behavior when the vector is empty. */ const T &last() const { diff --git a/source/blender/blenlib/BLI_vector_adaptor.hh b/source/blender/blenlib/BLI_vector_adaptor.hh new file mode 100644 index 00000000000..cadffc0b445 --- /dev/null +++ b/source/blender/blenlib/BLI_vector_adaptor.hh @@ -0,0 +1,105 @@ +/* + * 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. + */ + +#ifndef __BLI_VECTOR_ADAPTOR_HH__ +#define __BLI_VECTOR_ADAPTOR_HH__ + +/** \file + * \ingroup bli + * + * A `blender::VectorAdaptor` is a container with a fixed maximum size and does not own the + * underlying memory. When an adaptor is constructed, you have to provide it with an uninitialized + * array that will be filled when elements are added to the vector. The vector adaptor is not able + * to grow. Therefore, it is undefined behavior to add more elements than fit into the provided + * buffer. + */ + +#include "BLI_span.hh" + +namespace blender { + +template<typename T> class VectorAdaptor { + private: + T *begin_; + T *end_; + T *capacity_end_; + + public: + VectorAdaptor() : begin_(nullptr), end_(nullptr), capacity_end_(nullptr) + { + } + + VectorAdaptor(T *data, int64_t capacity, int64_t size = 0) + : begin_(data), end_(data + size), capacity_end_(data + capacity) + { + } + + VectorAdaptor(MutableSpan<T> span) : VectorAdaptor(span.data(), span.size(), 0) + { + } + + void append(const T &value) + { + BLI_assert(end_ < capacity_end_); + new (end_) T(value); + end_++; + } + + void append(T &&value) + { + BLI_assert(end_ < capacity_end_); + new (end_) T(std::move(value)); + end_++; + } + + void append_n_times(const T &value, int64_t n) + { + BLI_assert(end_ + n <= capacity_end_); + uninitialized_fill_n(end_, n, value); + end_ += n; + } + + void extend(Span<T> values) + { + BLI_assert(end_ + values.size() <= capacity_end_); + uninitialized_copy_n(values.data(), values.size(), end_); + end_ += values.size(); + } + + int64_t capacity() const + { + return capacity_end_ - begin_; + } + + int64_t size() const + { + return end_ - begin_; + } + + bool is_empty() const + { + return begin_ == end_; + } + + bool is_full() const + { + return end_ == capacity_end_; + } +}; + +} // namespace blender + +#endif /* __BLI_VECTOR_ADAPTOR_HH__ */ diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index c6e04d4147a..4997917a93f 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -267,6 +267,7 @@ set(SRC BLI_utility_mixins.hh BLI_uvproject.h BLI_vector.hh + BLI_vector_adaptor.hh BLI_vector_set.hh BLI_vector_set_slots.hh BLI_vfontdata.h @@ -340,3 +341,29 @@ set_source_files_properties( ) blender_add_lib(bf_blenlib "${SRC}" "${INC}" "${INC_SYS}" "${LIB}") + +if(WITH_GTESTS) + set(TEST_SRC + tests/BLI_array_test.cc + tests/BLI_disjoint_set_test.cc + tests/BLI_edgehash_test.cc + tests/BLI_index_mask_test.cc + tests/BLI_index_range_test.cc + tests/BLI_linear_allocator_test.cc + tests/BLI_map_test.cc + tests/BLI_math_base_safe_test.cc + tests/BLI_memory_utils_test.cc + tests/BLI_multi_value_map_test.cc + tests/BLI_set_test.cc + tests/BLI_span_test.cc + tests/BLI_stack_cxx_test.cc + tests/BLI_string_ref_test.cc + tests/BLI_vector_set_test.cc + tests/BLI_vector_test.cc + ) + set(TEST_LIB + bf_blenlib + ) + include(GTestTesting) + blender_add_test_lib(bf_bli_tests "${TEST_SRC}" "${INC};${TEST_INC}" "${INC_SYS}" "${LIB};${TEST_LIB}") +endif() diff --git a/source/blender/blenlib/tests/BLI_array_test.cc b/source/blender/blenlib/tests/BLI_array_test.cc new file mode 100644 index 00000000000..7348a6f93f3 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_array_test.cc @@ -0,0 +1,176 @@ +/* Apache License, Version 2.0 */ + +#include "BLI_array.hh" +#include "BLI_strict_flags.h" +#include "testing/testing.h" + +namespace blender::tests { + +TEST(array, DefaultConstructor) +{ + Array<int> array; + EXPECT_EQ(array.size(), 0); + EXPECT_TRUE(array.is_empty()); +} + +TEST(array, SizeConstructor) +{ + Array<int> array(5); + EXPECT_EQ(array.size(), 5); + EXPECT_FALSE(array.is_empty()); +} + +TEST(array, FillConstructor) +{ + Array<int> array(5, 8); + EXPECT_EQ(array.size(), 5); + EXPECT_EQ(array[0], 8); + EXPECT_EQ(array[1], 8); + EXPECT_EQ(array[2], 8); + EXPECT_EQ(array[3], 8); + EXPECT_EQ(array[4], 8); +} + +TEST(array, InitializerListConstructor) +{ + Array<int> array = {4, 5, 6, 7}; + EXPECT_EQ(array.size(), 4); + EXPECT_EQ(array[0], 4); + EXPECT_EQ(array[1], 5); + EXPECT_EQ(array[2], 6); + EXPECT_EQ(array[3], 7); +} + +TEST(array, SpanConstructor) +{ + int stackarray[4] = {6, 7, 8, 9}; + Span<int> span(stackarray, ARRAY_SIZE(stackarray)); + Array<int> array(span); + EXPECT_EQ(array.size(), 4); + EXPECT_EQ(array[0], 6); + EXPECT_EQ(array[1], 7); + EXPECT_EQ(array[2], 8); + EXPECT_EQ(array[3], 9); +} + +TEST(array, CopyConstructor) +{ + Array<int> array = {5, 6, 7, 8}; + Array<int> new_array(array); + + EXPECT_EQ(array.size(), 4); + EXPECT_EQ(new_array.size(), 4); + EXPECT_NE(array.data(), new_array.data()); + EXPECT_EQ(new_array[0], 5); + EXPECT_EQ(new_array[1], 6); + EXPECT_EQ(new_array[2], 7); + EXPECT_EQ(new_array[3], 8); +} + +TEST(array, MoveConstructor) +{ + Array<int> array = {5, 6, 7, 8}; + Array<int> new_array(std::move(array)); + + EXPECT_EQ(array.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(new_array.size(), 4); + EXPECT_EQ(new_array[0], 5); + EXPECT_EQ(new_array[1], 6); + EXPECT_EQ(new_array[2], 7); + EXPECT_EQ(new_array[3], 8); +} + +TEST(array, CopyAssignment) +{ + Array<int> array = {1, 2, 3}; + Array<int> new_array = {4}; + EXPECT_EQ(new_array.size(), 1); + new_array = array; + EXPECT_EQ(new_array.size(), 3); + EXPECT_EQ(array.size(), 3); + EXPECT_NE(array.data(), new_array.data()); + EXPECT_EQ(new_array[0], 1); + EXPECT_EQ(new_array[1], 2); + EXPECT_EQ(new_array[2], 3); +} + +TEST(array, MoveAssignment) +{ + Array<int> array = {1, 2, 3}; + Array<int> new_array = {4}; + EXPECT_EQ(new_array.size(), 1); + new_array = std::move(array); + EXPECT_EQ(new_array.size(), 3); + EXPECT_EQ(array.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(new_array[0], 1); + EXPECT_EQ(new_array[1], 2); + EXPECT_EQ(new_array[2], 3); +} + +/** + * Tests that the trivially constructible types are not zero-initialized. We do not want that for + * performance reasons. + */ +TEST(array, TrivialTypeSizeConstructor) +{ + Array<char, 1> *array = new Array<char, 1>(1); + char *ptr = &(*array)[0]; + array->~Array(); + + const char magic = 42; + *ptr = magic; + EXPECT_EQ(*ptr, magic); + + new (array) Array<char, 1>(1); + EXPECT_EQ((*array)[0], magic); + EXPECT_EQ(*ptr, magic); + delete array; +} + +struct ConstructibleType { + char value; + + ConstructibleType() + { + value = 42; + } +}; + +TEST(array, NoInitializationSizeConstructor) +{ + using MyArray = Array<ConstructibleType>; + + TypedBuffer<MyArray> buffer; + memset((void *)&buffer, 100, sizeof(MyArray)); + + /* Doing this to avoid some compiler optimization. */ + for (int64_t i : IndexRange(sizeof(MyArray))) { + EXPECT_EQ(((char *)buffer.ptr())[i], 100); + } + + { + MyArray &array = *new (buffer) MyArray(1, NoInitialization()); + EXPECT_EQ(array[0].value, 100); + array.clear_without_destruct(); + array.~Array(); + } + { + MyArray &array = *new (buffer) MyArray(1); + EXPECT_EQ(array[0].value, 42); + array.~Array(); + } +} + +TEST(array, Fill) +{ + Array<int> array(5); + array.fill(3); + EXPECT_EQ(array.size(), 5u); + EXPECT_EQ(array[0], 3); + EXPECT_EQ(array[1], 3); + EXPECT_EQ(array[2], 3); + EXPECT_EQ(array[3], 3); + EXPECT_EQ(array[4], 3); +} + +} // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_disjoint_set_test.cc b/source/blender/blenlib/tests/BLI_disjoint_set_test.cc new file mode 100644 index 00000000000..f30ee610b2a --- /dev/null +++ b/source/blender/blenlib/tests/BLI_disjoint_set_test.cc @@ -0,0 +1,36 @@ +/* Apache License, Version 2.0 */ + +#include "BLI_disjoint_set.hh" +#include "BLI_strict_flags.h" + +#include "testing/testing.h" + +namespace blender::tests { + +TEST(disjoint_set, Test) +{ + DisjointSet disjoint_set(6); + EXPECT_FALSE(disjoint_set.in_same_set(1, 2)); + EXPECT_FALSE(disjoint_set.in_same_set(5, 3)); + EXPECT_TRUE(disjoint_set.in_same_set(2, 2)); + EXPECT_EQ(disjoint_set.find_root(3), 3); + + disjoint_set.join(1, 2); + + EXPECT_TRUE(disjoint_set.in_same_set(1, 2)); + EXPECT_FALSE(disjoint_set.in_same_set(0, 1)); + + disjoint_set.join(3, 4); + + EXPECT_FALSE(disjoint_set.in_same_set(2, 3)); + EXPECT_TRUE(disjoint_set.in_same_set(3, 4)); + + disjoint_set.join(1, 4); + + EXPECT_TRUE(disjoint_set.in_same_set(1, 4)); + EXPECT_TRUE(disjoint_set.in_same_set(1, 3)); + EXPECT_TRUE(disjoint_set.in_same_set(2, 4)); + EXPECT_FALSE(disjoint_set.in_same_set(0, 4)); +} + +} // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_edgehash_test.cc b/source/blender/blenlib/tests/BLI_edgehash_test.cc new file mode 100644 index 00000000000..7106033df36 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_edgehash_test.cc @@ -0,0 +1,408 @@ +/* Apache License, Version 2.0 */ + +#include "testing/testing.h" +#include <algorithm> +#include <random> +#include <vector> + +#include "BLI_edgehash.h" +#include "BLI_utildefines.h" + +#define VALUE_1 POINTER_FROM_INT(1) +#define VALUE_2 POINTER_FROM_INT(2) +#define VALUE_3 POINTER_FROM_INT(3) + +TEST(edgehash, InsertIncreasesLength) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + ASSERT_EQ(BLI_edgehash_len(eh), 0); + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, ReinsertNewIncreasesLength) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + ASSERT_EQ(BLI_edgehash_len(eh), 0); + BLI_edgehash_reinsert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, ReinsertExistingDoesNotIncreaseLength) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + ASSERT_EQ(BLI_edgehash_len(eh), 0); + BLI_edgehash_reinsert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + BLI_edgehash_reinsert(eh, 1, 2, VALUE_2); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + BLI_edgehash_reinsert(eh, 2, 1, VALUE_2); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, ReinsertCanChangeValue) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_1); + BLI_edgehash_reinsert(eh, 2, 1, VALUE_2); + ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_2); + BLI_edgehash_reinsert(eh, 1, 2, VALUE_3); + ASSERT_EQ(BLI_edgehash_lookup(eh, 2, 1), VALUE_3); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, LookupExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_1); + ASSERT_EQ(BLI_edgehash_lookup(eh, 2, 1), VALUE_1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, LookupNonExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), nullptr); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, LookupNonExistingWithDefault) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + ASSERT_EQ(BLI_edgehash_lookup_default(eh, 1, 2, VALUE_1), VALUE_1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, LookupExistingWithDefault) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_lookup_default(eh, 1, 2, VALUE_2), VALUE_1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, LookupPExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + void *value = VALUE_1; + BLI_edgehash_insert(eh, 1, 2, value); + void **value_p = BLI_edgehash_lookup_p(eh, 1, 2); + ASSERT_EQ(*value_p, VALUE_1); + *value_p = VALUE_2; + ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_2); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, LookupPNonExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + ASSERT_EQ(BLI_edgehash_lookup_p(eh, 1, 2), nullptr); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, EnsurePNonExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + void **value_p; + bool existed = BLI_edgehash_ensure_p(eh, 1, 2, &value_p); + ASSERT_FALSE(existed); + *value_p = VALUE_1; + ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, EnsurePExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + void **value_p; + bool existed = BLI_edgehash_ensure_p(eh, 1, 2, &value_p); + ASSERT_TRUE(existed); + ASSERT_EQ(*value_p, VALUE_1); + *value_p = VALUE_2; + ASSERT_EQ(BLI_edgehash_lookup(eh, 1, 2), VALUE_2); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, RemoveExistingDecreasesLength) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + bool has_been_removed = BLI_edgehash_remove(eh, 1, 2, nullptr); + ASSERT_EQ(BLI_edgehash_len(eh), 0); + ASSERT_TRUE(has_been_removed); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, RemoveNonExistingDoesNotDecreaseLength) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + bool has_been_removed = BLI_edgehash_remove(eh, 4, 5, nullptr); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + ASSERT_FALSE(has_been_removed); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, PopKeyTwice) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_popkey(eh, 1, 2), VALUE_1); + ASSERT_EQ(BLI_edgehash_popkey(eh, 1, 2), nullptr); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, LookupInvertedIndices) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_EQ(BLI_edgehash_lookup(eh, 2, 1), VALUE_1); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, HasKeyExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + ASSERT_TRUE(BLI_edgehash_haskey(eh, 1, 2)); + ASSERT_TRUE(BLI_edgehash_haskey(eh, 2, 1)); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, HasKeyNonExisting) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + ASSERT_FALSE(BLI_edgehash_haskey(eh, 1, 2)); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, ClearSetsLengthToZero) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + BLI_edgehash_insert(eh, 1, 2, VALUE_2); + ASSERT_EQ(BLI_edgehash_len(eh), 2); + BLI_edgehash_clear(eh, nullptr); + ASSERT_EQ(BLI_edgehash_len(eh), 0); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, IteratorFindsAllValues) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + BLI_edgehash_insert(eh, 1, 3, VALUE_2); + BLI_edgehash_insert(eh, 1, 4, VALUE_3); + + EdgeHashIterator *ehi = BLI_edgehashIterator_new(eh); + auto a = BLI_edgehashIterator_getValue(ehi); + BLI_edgehashIterator_step(ehi); + auto b = BLI_edgehashIterator_getValue(ehi); + BLI_edgehashIterator_step(ehi); + auto c = BLI_edgehashIterator_getValue(ehi); + BLI_edgehashIterator_step(ehi); + + ASSERT_NE(a, b); + ASSERT_NE(b, c); + ASSERT_NE(a, c); + ASSERT_TRUE(ELEM(a, VALUE_1, VALUE_2, VALUE_3)); + ASSERT_TRUE(ELEM(b, VALUE_1, VALUE_2, VALUE_3)); + ASSERT_TRUE(ELEM(c, VALUE_1, VALUE_2, VALUE_3)); + + BLI_edgehashIterator_free(ehi); + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, IterateIsDone) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + BLI_edgehash_insert(eh, 1, 3, VALUE_2); + BLI_edgehash_insert(eh, 1, 4, VALUE_3); + + EdgeHashIterator *ehi = BLI_edgehashIterator_new(eh); + ASSERT_FALSE(BLI_edgehashIterator_isDone(ehi)); + BLI_edgehashIterator_step(ehi); + ASSERT_FALSE(BLI_edgehashIterator_isDone(ehi)); + BLI_edgehashIterator_step(ehi); + ASSERT_FALSE(BLI_edgehashIterator_isDone(ehi)); + BLI_edgehashIterator_step(ehi); + ASSERT_TRUE(BLI_edgehashIterator_isDone(ehi)); + + BLI_edgehashIterator_free(ehi); + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgehash, DoubleRemove) +{ + EdgeHash *eh = BLI_edgehash_new(__func__); + + BLI_edgehash_insert(eh, 1, 2, VALUE_1); + BLI_edgehash_insert(eh, 1, 3, VALUE_2); + BLI_edgehash_insert(eh, 1, 4, VALUE_3); + ASSERT_EQ(BLI_edgehash_len(eh), 3); + + BLI_edgehash_remove(eh, 1, 2, nullptr); + BLI_edgehash_remove(eh, 1, 3, nullptr); + ASSERT_EQ(BLI_edgehash_len(eh), 1); + + BLI_edgehash_free(eh, nullptr); +} + +struct Edge { + uint v1, v2; +}; + +TEST(edgehash, StressTest) +{ + std::srand(0); + int amount = 10000; + + std::vector<Edge> edges; + for (int i = 0; i < amount; i++) { + edges.push_back({(uint)i, amount + (uint)std::rand() % 12345}); + } + + EdgeHash *eh = BLI_edgehash_new(__func__); + + /* first insert all the edges */ + for (int i = 0; i < edges.size(); i++) { + BLI_edgehash_insert(eh, edges[i].v1, edges[i].v2, POINTER_FROM_INT(i)); + } + + std::vector<Edge> shuffled = edges; + std::shuffle(shuffled.begin(), shuffled.end(), std::default_random_engine()); + + /* then remove half of them */ + int remove_until = shuffled.size() / 2; + for (int i = 0; i < remove_until; i++) { + BLI_edgehash_remove(eh, shuffled[i].v2, shuffled[i].v1, nullptr); + } + + ASSERT_EQ(BLI_edgehash_len(eh), edges.size() - remove_until); + + /* check if the right ones have been removed */ + for (int i = 0; i < shuffled.size(); i++) { + bool haskey = BLI_edgehash_haskey(eh, shuffled[i].v1, shuffled[i].v2); + if (i < remove_until) { + ASSERT_FALSE(haskey); + } + else { + ASSERT_TRUE(haskey); + } + } + + /* reinsert all edges */ + for (int i = 0; i < edges.size(); i++) { + BLI_edgehash_reinsert(eh, edges[i].v1, edges[i].v2, POINTER_FROM_INT(i)); + } + + ASSERT_EQ(BLI_edgehash_len(eh), edges.size()); + + /* pop all edges */ + for (int i = 0; i < edges.size(); i++) { + int value = POINTER_AS_INT(BLI_edgehash_popkey(eh, edges[i].v1, edges[i].v2)); + ASSERT_EQ(i, value); + } + + ASSERT_EQ(BLI_edgehash_len(eh), 0); + + BLI_edgehash_free(eh, nullptr); +} + +TEST(edgeset, AddNonExistingIncreasesLength) +{ + EdgeSet *es = BLI_edgeset_new(__func__); + + ASSERT_EQ(BLI_edgeset_len(es), 0); + BLI_edgeset_add(es, 1, 2); + ASSERT_EQ(BLI_edgeset_len(es), 1); + BLI_edgeset_add(es, 1, 3); + ASSERT_EQ(BLI_edgeset_len(es), 2); + BLI_edgeset_add(es, 1, 4); + ASSERT_EQ(BLI_edgeset_len(es), 3); + + BLI_edgeset_free(es); +} + +TEST(edgeset, AddExistingDoesNotIncreaseLength) +{ + EdgeSet *es = BLI_edgeset_new(__func__); + + ASSERT_EQ(BLI_edgeset_len(es), 0); + BLI_edgeset_add(es, 1, 2); + ASSERT_EQ(BLI_edgeset_len(es), 1); + BLI_edgeset_add(es, 2, 1); + ASSERT_EQ(BLI_edgeset_len(es), 1); + BLI_edgeset_add(es, 1, 2); + ASSERT_EQ(BLI_edgeset_len(es), 1); + + BLI_edgeset_free(es); +} + +TEST(edgeset, HasKeyNonExisting) +{ + EdgeSet *es = BLI_edgeset_new(__func__); + + ASSERT_FALSE(BLI_edgeset_haskey(es, 1, 2)); + + BLI_edgeset_free(es); +} + +TEST(edgeset, HasKeyExisting) +{ + EdgeSet *es = BLI_edgeset_new(__func__); + + BLI_edgeset_insert(es, 1, 2); + ASSERT_TRUE(BLI_edgeset_haskey(es, 1, 2)); + + BLI_edgeset_free(es); +} diff --git a/source/blender/blenlib/tests/BLI_index_mask_test.cc b/source/blender/blenlib/tests/BLI_index_mask_test.cc new file mode 100644 index 00000000000..4d6060e51c9 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_index_mask_test.cc @@ -0,0 +1,43 @@ +/* Apache License, Version 2.0 */ + +#include "BLI_index_mask.hh" +#include "testing/testing.h" + +namespace blender::tests { + +TEST(index_mask, DefaultConstructor) +{ + IndexMask mask; + EXPECT_EQ(mask.min_array_size(), 0); + EXPECT_EQ(mask.size(), 0); +} + +TEST(index_mask, ArrayConstructor) +{ + [](IndexMask mask) { + EXPECT_EQ(mask.size(), 4); + EXPECT_EQ(mask.min_array_size(), 8); + EXPECT_FALSE(mask.is_range()); + EXPECT_EQ(mask[0], 3); + EXPECT_EQ(mask[1], 5); + EXPECT_EQ(mask[2], 6); + EXPECT_EQ(mask[3], 7); + }({3, 5, 6, 7}); +} + +TEST(index_mask, RangeConstructor) +{ + IndexMask mask = IndexRange(3, 5); + EXPECT_EQ(mask.size(), 5); + EXPECT_EQ(mask.min_array_size(), 8); + EXPECT_EQ(mask.last(), 7); + EXPECT_TRUE(mask.is_range()); + EXPECT_EQ(mask.as_range().first(), 3); + EXPECT_EQ(mask.as_range().last(), 7); + Span<int64_t> indices = mask.indices(); + EXPECT_EQ(indices[0], 3); + EXPECT_EQ(indices[1], 4); + EXPECT_EQ(indices[2], 5); +} + +} // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_index_range_test.cc b/source/blender/blenlib/tests/BLI_index_range_test.cc new file mode 100644 index 00000000000..d472ded0f18 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_index_range_test.cc @@ -0,0 +1,143 @@ +/* Apache License, Version 2.0 */ + +#include "BLI_index_range.hh" +#include "BLI_strict_flags.h" +#include "BLI_vector.hh" +#include "testing/testing.h" + +namespace blender::tests { + +TEST(index_range, DefaultConstructor) +{ + IndexRange range; + EXPECT_EQ(range.size(), 0); + + Vector<int64_t> vector; + for (int64_t value : range) { + vector.append(value); + } + EXPECT_EQ(vector.size(), 0); +} + +TEST(index_range, SingleElementRange) +{ + IndexRange range(4, 1); + EXPECT_EQ(range.size(), 1); + EXPECT_EQ(*range.begin(), 4); + + Vector<int64_t> vector; + for (int64_t value : range) { + vector.append(value); + } + + EXPECT_EQ(vector.size(), 1); + EXPECT_EQ(vector[0], 4); +} + +TEST(index_range, MultipleElementRange) +{ + IndexRange range(6, 4); + EXPECT_EQ(range.size(), 4); + + Vector<int64_t> vector; + for (int64_t value : range) { + vector.append(value); + } + + EXPECT_EQ(vector.size(), 4); + for (int i = 0; i < 4; i++) { + EXPECT_EQ(vector[i], i + 6); + } +} + +TEST(index_range, SubscriptOperator) +{ + IndexRange range(5, 5); + EXPECT_EQ(range[0], 5); + EXPECT_EQ(range[1], 6); + EXPECT_EQ(range[2], 7); +} + +TEST(index_range, Before) +{ + IndexRange range = IndexRange(5, 5).before(3); + EXPECT_EQ(range[0], 2); + EXPECT_EQ(range[1], 3); + EXPECT_EQ(range[2], 4); + EXPECT_EQ(range.size(), 3); +} + +TEST(index_range, After) +{ + IndexRange range = IndexRange(5, 5).after(4); + EXPECT_EQ(range[0], 10); + EXPECT_EQ(range[1], 11); + EXPECT_EQ(range[2], 12); + EXPECT_EQ(range[3], 13); + EXPECT_EQ(range.size(), 4); +} + +TEST(index_range, Contains) +{ + IndexRange range = IndexRange(5, 3); + EXPECT_TRUE(range.contains(5)); + EXPECT_TRUE(range.contains(6)); + EXPECT_TRUE(range.contains(7)); + EXPECT_FALSE(range.contains(4)); + EXPECT_FALSE(range.contains(8)); +} + +TEST(index_range, First) +{ + IndexRange range = IndexRange(5, 3); + EXPECT_EQ(range.first(), 5); +} + +TEST(index_range, Last) +{ + IndexRange range = IndexRange(5, 3); + EXPECT_EQ(range.last(), 7); +} + +TEST(index_range, OneAfterEnd) +{ + IndexRange range = IndexRange(5, 3); + EXPECT_EQ(range.one_after_last(), 8); +} + +TEST(index_range, Start) +{ + IndexRange range = IndexRange(6, 2); + EXPECT_EQ(range.start(), 6); +} + +TEST(index_range, Slice) +{ + IndexRange range = IndexRange(5, 15); + IndexRange slice = range.slice(2, 6); + EXPECT_EQ(slice.size(), 6); + EXPECT_EQ(slice.first(), 7); + EXPECT_EQ(slice.last(), 12); +} + +TEST(index_range, SliceRange) +{ + IndexRange range = IndexRange(5, 15); + IndexRange slice = range.slice(IndexRange(3, 5)); + EXPECT_EQ(slice.size(), 5); + EXPECT_EQ(slice.first(), 8); + EXPECT_EQ(slice.last(), 12); +} + +TEST(index_range, AsSpan) +{ + IndexRange range = IndexRange(4, 6); + Span<int64_t> span = range.as_span(); + EXPECT_EQ(span.size(), 6); + EXPECT_EQ(span[0], 4); + EXPECT_EQ(span[1], 5); + EXPECT_EQ(span[2], 6); + EXPECT_EQ(span[3], 7); +} + +} // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_linear_allocator_test.cc b/source/blender/blenlib/tests/BLI_linear_allocator_test.cc new file mode 100644 index 00000000000..44b70d1f55d --- /dev/null +++ b/source/blender/blenlib/tests/BLI_linear_allocator_test.cc @@ -0,0 +1,118 @@ +/* Apache License, Version 2.0 */ + +#include "BLI_linear_allocator.hh" +#include "BLI_strict_flags.h" +#include "testing/testing.h" + +namespace blender::tests { + +static bool is_aligned(void *ptr, uint alignment) +{ + BLI_assert(is_power_of_2_i((int)alignment)); + return (POINTER_AS_UINT(ptr) & (alignment - 1)) == 0; +} + +TEST(linear_allocator, AllocationAlignment) +{ + LinearAllocator<> allocator; + + EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 8), 8)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 16), 16)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 4), 4)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 64), 64)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 64), 64)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 8), 8)); + EXPECT_TRUE(is_aligned(allocator.allocate(10, 128), 128)); +} + +TEST(linear_allocator, PackedAllocation) +{ + LinearAllocator<> allocator; + blender::AlignedBuffer<256, 32> buffer; + allocator.provide_buffer(buffer); + + uintptr_t ptr1 = (uintptr_t)allocator.allocate(10, 4); /* 0 - 10 */ + uintptr_t ptr2 = (uintptr_t)allocator.allocate(10, 4); /* 12 - 22 */ + uintptr_t ptr3 = (uintptr_t)allocator.allocate(8, 32); /* 32 - 40 */ + uintptr_t ptr4 = (uintptr_t)allocator.allocate(16, 8); /* 40 - 56 */ + uintptr_t ptr5 = (uintptr_t)allocator.allocate(1, 8); /* 56 - 57 */ + uintptr_t ptr6 = (uintptr_t)allocator.allocate(1, 4); /* 60 - 61 */ + uintptr_t ptr7 = (uintptr_t)allocator.allocate(1, 1); /* 61 - 62 */ + + EXPECT_EQ(ptr2 - ptr1, 12); /* 12 - 0 = 12 */ + EXPECT_EQ(ptr3 - ptr2, 20); /* 32 - 12 = 20 */ + EXPECT_EQ(ptr4 - ptr3, 8); /* 40 - 32 = 8 */ + EXPECT_EQ(ptr5 - ptr4, 16); /* 56 - 40 = 16 */ + EXPECT_EQ(ptr6 - ptr5, 4); /* 60 - 56 = 4 */ + EXPECT_EQ(ptr7 - ptr6, 1); /* 61 - 60 = 1 */ +} + +TEST(linear_allocator, CopyString) +{ + LinearAllocator<> allocator; + blender::AlignedBuffer<256, 1> buffer; + allocator.provide_buffer(buffer); + + StringRefNull ref1 = allocator.copy_string("Hello"); + StringRefNull ref2 = allocator.copy_string("World"); + + EXPECT_EQ(ref1, "Hello"); + EXPECT_EQ(ref2, "World"); + EXPECT_EQ(ref2.data() - ref1.data(), 6); +} + +TEST(linear_allocator, AllocateArray) +{ + LinearAllocator<> allocator; + + MutableSpan<int> span = allocator.allocate_array<int>(5); + EXPECT_EQ(span.size(), 5); +} + +TEST(linear_allocator, Construct) +{ + LinearAllocator<> allocator; + + std::array<int, 5> values = {1, 2, 3, 4, 5}; + Vector<int> *vector = allocator.construct<Vector<int>>(values); + EXPECT_EQ(vector->size(), 5); + EXPECT_EQ((*vector)[3], 4); + vector->~Vector(); +} + +TEST(linear_allocator, ConstructElementsAndPointerArray) +{ + LinearAllocator<> allocator; + + std::array<int, 7> values = {1, 2, 3, 4, 5, 6, 7}; + Span<Vector<int> *> vectors = allocator.construct_elements_and_pointer_array<Vector<int>>( + 5, values); + + EXPECT_EQ(vectors.size(), 5); + EXPECT_EQ(vectors[3]->size(), 7); + EXPECT_EQ((*vectors[2])[5], 6); + + for (Vector<int> *vector : vectors) { + vector->~Vector(); + } +} + +TEST(linear_allocator, ConstructArrayCopy) +{ + LinearAllocator<> allocator; + + Vector<int> values = {1, 2, 3}; + MutableSpan<int> span1 = allocator.construct_array_copy(values.as_span()); + MutableSpan<int> span2 = allocator.construct_array_copy(values.as_span()); + EXPECT_NE(span1.data(), span2.data()); + EXPECT_EQ(span1.size(), 3); + EXPECT_EQ(span2.size(), 3); + EXPECT_EQ(span1[1], 2); + EXPECT_EQ(span2[2], 3); +} + +} // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_map_test.cc b/source/blender/blenlib/tests/BLI_map_test.cc new file mode 100644 index 00000000000..fe7b0f01279 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_map_test.cc @@ -0,0 +1,590 @@ +/* Apache License, Version 2.0 */ + +#include "BLI_map.hh" +#include "BLI_rand.h" +#include "BLI_set.hh" +#include "BLI_strict_flags.h" +#include "BLI_timeit.hh" +#include "BLI_vector.hh" +#include "testing/testing.h" + +namespace blender::tests { + +TEST(map, DefaultConstructor) +{ + Map<int, float> map; + EXPECT_EQ(map.size(), 0); + EXPECT_TRUE(map.is_empty()); +} + +TEST(map, AddIncreasesSize) +{ + Map<int, float> map; + EXPECT_EQ(map.size(), 0); + EXPECT_TRUE(map.is_empty()); + map.add(2, 5.0f); + EXPECT_EQ(map.size(), 1); + EXPECT_FALSE(map.is_empty()); + map.add(6, 2.0f); + EXPECT_EQ(map.size(), 2); + EXPECT_FALSE(map.is_empty()); +} + +TEST(map, Contains) +{ + Map<int, float> map; + EXPECT_FALSE(map.contains(4)); + map.add(5, 6.0f); + EXPECT_FALSE(map.contains(4)); + map.add(4, 2.0f); + EXPECT_TRUE(map.contains(4)); +} + +TEST(map, LookupExisting) +{ + Map<int, float> map; + map.add(2, 6.0f); + map.add(4, 1.0f); + EXPECT_EQ(map.lookup(2), 6.0f); + EXPECT_EQ(map.lookup(4), 1.0f); +} + +TEST(map, LookupNotExisting) +{ + Map<int, float> map; + map.add(2, 4.0f); + map.add(1, 1.0f); + EXPECT_EQ(map.lookup_ptr(0), nullptr); + EXPECT_EQ(map.lookup_ptr(5), nullptr); +} + +TEST(map, AddMany) +{ + Map<int, int> map; + for (int i = 0; i < 100; i++) { + map.add(i * 30, i); + map.add(i * 31, i); + } +} + +TEST(map, PopItem) +{ + Map<int, float> map; + map.add(2, 3.0f); + map.add(1, 9.0f); + EXPECT_TRUE(map.contains(2)); + EXPECT_TRUE(map.contains(1)); + + EXPECT_EQ(map.pop(1), 9.0f); + EXPECT_TRUE(map.contains(2)); + EXPECT_FALSE(map.contains(1)); + + EXPECT_EQ(map.pop(2), 3.0f); + EXPECT_FALSE(map.contains(2)); + EXPECT_FALSE(map.contains(1)); +} + +TEST(map, PopTry) +{ + Map<int, int> map; + map.add(1, 5); + map.add(2, 7); + EXPECT_EQ(map.size(), 2); + std::optional<int> value = map.pop_try(4); + EXPECT_EQ(map.size(), 2); + EXPECT_FALSE(value.has_value()); + value = map.pop_try(2); + EXPECT_EQ(map.size(), 1); + EXPECT_TRUE(value.has_value()); + EXPECT_EQ(*value, 7); + EXPECT_EQ(*map.pop_try(1), 5); + EXPECT_EQ(map.size(), 0); +} + +TEST(map, PopDefault) +{ + Map<int, int> map; + map.add(1, 4); + map.add(2, 7); + map.add(3, 8); + EXPECT_EQ(map.size(), 3); + EXPECT_EQ(map.pop_default(4, 10), 10); + EXPECT_EQ(map.size(), 3); + EXPECT_EQ(map.pop_default(1, 10), 4); + EXPECT_EQ(map.size(), 2); + EXPECT_EQ(map.pop_default(2, 20), 7); + EXPECT_EQ(map.size(), 1); + EXPECT_EQ(map.pop_default(2, 20), 20); + EXPECT_EQ(map.size(), 1); + EXPECT_EQ(map.pop_default(3, 0), 8); + EXPECT_EQ(map.size(), 0); +} + +TEST(map, PopItemMany) +{ + Map<int, int> map; + for (int i = 0; i < 100; i++) { + map.add_new(i, i); + } + for (int i = 25; i < 80; i++) { + EXPECT_EQ(map.pop(i), i); + } + for (int i = 0; i < 100; i++) { + EXPECT_EQ(map.contains(i), i < 25 || i >= 80); + } +} + +TEST(map, ValueIterator) +{ + Map<int, float> map; + map.add(3, 5.0f); + map.add(1, 2.0f); + map.add(7, -2.0f); + + blender::Set<float> values; + + int iterations = 0; + for (float value : map.values()) { + values.add(value); + iterations++; + } + + EXPECT_EQ(iterations, 3); + EXPECT_TRUE(values.contains(5.0f)); + EXPECT_TRUE(values.contains(-2.0f)); + EXPECT_TRUE(values.contains(2.0f)); +} + +TEST(map, KeyIterator) +{ + Map<int, float> map; + map.add(6, 3.0f); + map.add(2, 4.0f); + map.add(1, 3.0f); + + blender::Set<int> keys; + + int iterations = 0; + for (int key : map.keys()) { + keys.add(key); + iterations++; + } + + EXPECT_EQ(iterations, 3); + EXPECT_TRUE(keys.contains(1)); + EXPECT_TRUE(keys.contains(2)); + EXPECT_TRUE(keys.contains(6)); +} + +TEST(map, ItemIterator) +{ + Map<int, float> map; + map.add(5, 3.0f); + map.add(2, 9.0f); + map.add(1, 0.0f); + + blender::Set<int> keys; + blender::Set<float> values; + + int iterations = 0; + const Map<int, float> &const_map = map; + for (auto item : const_map.items()) { + keys.add(item.key); + values.add(item.value); + iterations++; + } + + EXPECT_EQ(iterations, 3); + EXPECT_TRUE(keys.contains(5)); + EXPECT_TRUE(keys.contains(2)); + EXPECT_TRUE(keys.contains(1)); + EXPECT_TRUE(values.contains(3.0f)); + EXPECT_TRUE(values.contains(9.0f)); + EXPECT_TRUE(values.contains(0.0f)); +} + +TEST(map, MutableValueIterator) +{ + Map<int, int> map; + map.add(3, 6); + map.add(2, 1); + + for (int &value : map.values()) { + value += 10; + } + + EXPECT_EQ(map.lookup(3), 16); + EXPECT_EQ(map.lookup(2), 11); +} + +TEST(map, MutableItemIterator) +{ + Map<int, int> map; + map.add(3, 6); + map.add(2, 1); + + for (auto item : map.items()) { + item.value += item.key; + } + + EXPECT_EQ(map.lookup(3), 9.0f); + EXPECT_EQ(map.lookup(2), 3.0f); +} + +TEST(map, MutableItemToItemConversion) +{ + Map<int, int> map; + map.add(3, 6); + map.add(2, 1); + + Vector<int> keys, values; + for (Map<int, int>::Item item : map.items()) { + keys.append(item.key); + values.append(item.value); + } + + EXPECT_EQ(keys.size(), 2); + EXPECT_EQ(values.size(), 2); + EXPECT_TRUE(keys.contains(3)); + EXPECT_TRUE(keys.contains(2)); + EXPECT_TRUE(values.contains(6)); + EXPECT_TRUE(values.contains(1)); +} + +static float return_42() +{ + return 42.0f; +} + +TEST(map, LookupOrAddCB_SeparateFunction) +{ + Map<int, float> map; + EXPECT_EQ(map.lookup_or_add_cb(0, return_42), 42.0f); + EXPECT_EQ(map.lookup(0), 42); + + map.keys(); +} + +TEST(map, LookupOrAddCB_Lambdas) +{ + Map<int, float> map; + auto lambda1 = []() { return 11.0f; }; + EXPECT_EQ(map.lookup_or_add_cb(0, lambda1), 11.0f); + auto lambda2 = []() { return 20.0f; }; + EXPECT_EQ(map.lookup_or_add_cb(1, lambda2), 20.0f); + + EXPECT_EQ(map.lookup_or_add_cb(0, lambda2), 11.0f); + EXPECT_EQ(map.lookup_or_add_cb(1, lambda1), 20.0f); +} + +TEST(map, AddOrModify) +{ + Map<int, float> map; + auto create_func = [](float *value) { + *value = 10.0f; + return true; + }; + auto modify_func = [](float *value) { + *value += 5; + return false; + }; + EXPECT_TRUE(map.add_or_modify(1, create_func, modify_func)); + EXPECT_EQ(map.lookup(1), 10.0f); + EXPECT_FALSE(map.add_or_modify(1, create_func, modify_func)); + EXPECT_EQ(map.lookup(1), 15.0f); +} + +TEST(map, AddOverwrite) +{ + Map<int, float> map; + EXPECT_FALSE(map.contains(3)); + EXPECT_TRUE(map.add_overwrite(3, 6.0f)); + EXPECT_EQ(map.lookup(3), 6.0f); + EXPECT_FALSE(map.add_overwrite(3, 7.0f)); + EXPECT_EQ(map.lookup(3), 7.0f); + EXPECT_FALSE(map.add(3, 8.0f)); + EXPECT_EQ(map.lookup(3), 7.0f); +} + +TEST(map, LookupOrAddDefault) +{ + Map<int, float> map; + map.lookup_or_add_default(3) = 6; + EXPECT_EQ(map.lookup(3), 6); + map.lookup_or_add_default(5) = 2; + EXPECT_EQ(map.lookup(5), 2); + map.lookup_or_add_default(3) += 4; + EXPECT_EQ(map.lookup(3), 10); +} + +TEST(map, LookupOrAdd) +{ + Map<int, int> map; + EXPECT_EQ(map.lookup_or_add(6, 4), 4); + EXPECT_EQ(map.lookup_or_add(6, 5), 4); + map.lookup_or_add(6, 4) += 10; + EXPECT_EQ(map.lookup(6), 14); +} + +TEST(map, MoveConstructorSmall) +{ + Map<int, float> map1; + map1.add(1, 2.0f); + map1.add(4, 1.0f); + Map<int, float> map2(std::move(map1)); + EXPECT_EQ(map2.size(), 2); + EXPECT_EQ(map2.lookup(1), 2.0f); + EXPECT_EQ(map2.lookup(4), 1.0f); + EXPECT_EQ(map1.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(map1.lookup_ptr(4), nullptr); +} + +TEST(map, MoveConstructorLarge) +{ + Map<int, int> map1; + for (int i = 0; i < 100; i++) { + map1.add_new(i, i); + } + Map<int, int> map2(std::move(map1)); + EXPECT_EQ(map2.size(), 100); + EXPECT_EQ(map2.lookup(1), 1); + EXPECT_EQ(map2.lookup(4), 4); + EXPECT_EQ(map1.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(map1.lookup_ptr(4), nullptr); +} + +TEST(map, MoveAssignment) +{ + Map<int, float> map1; + map1.add(1, 2.0f); + map1.add(4, 1.0f); + Map<int, float> map2; + map2 = std::move(map1); + EXPECT_EQ(map2.size(), 2); + EXPECT_EQ(map2.lookup(1), 2.0f); + EXPECT_EQ(map2.lookup(4), 1.0f); + EXPECT_EQ(map1.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(map1.lookup_ptr(4), nullptr); +} + +TEST(map, CopyAssignment) +{ + Map<int, float> map1; + map1.add(1, 2.0f); + map1.add(4, 1.0f); + Map<int, float> map2; + map2 = map1; + EXPECT_EQ(map2.size(), 2); + EXPECT_EQ(map2.lookup(1), 2.0f); + EXPECT_EQ(map2.lookup(4), 1.0f); + EXPECT_EQ(map1.size(), 2); + EXPECT_EQ(*map1.lookup_ptr(4), 1.0f); +} + +TEST(map, Clear) +{ + Map<int, float> map; + map.add(1, 1.0f); + map.add(2, 5.0f); + + EXPECT_EQ(map.size(), 2); + EXPECT_TRUE(map.contains(1)); + EXPECT_TRUE(map.contains(2)); + + map.clear(); + + EXPECT_EQ(map.size(), 0); + EXPECT_FALSE(map.contains(1)); + EXPECT_FALSE(map.contains(2)); +} + +TEST(map, UniquePtrValue) +{ + auto value1 = std::unique_ptr<int>(new int()); + auto value2 = std::unique_ptr<int>(new int()); + auto value3 = std::unique_ptr<int>(new int()); + + int *value1_ptr = value1.get(); + + Map<int, std::unique_ptr<int>> map; + map.add_new(1, std::move(value1)); + map.add(2, std::move(value2)); + map.add_overwrite(3, std::move(value3)); + map.lookup_or_add_cb(4, []() { return std::unique_ptr<int>(new int()); }); + map.add_new(5, std::unique_ptr<int>(new int())); + map.add(6, std::unique_ptr<int>(new int())); + map.add_overwrite(7, std::unique_ptr<int>(new int())); + map.lookup_or_add(8, std::unique_ptr<int>(new int())); + map.pop_default(9, std::unique_ptr<int>(new int())); + + EXPECT_EQ(map.lookup(1).get(), value1_ptr); + EXPECT_EQ(map.lookup_ptr(100), nullptr); +} + +TEST(map, Remove) +{ + Map<int, int> map; + map.add(2, 4); + EXPECT_EQ(map.size(), 1); + EXPECT_FALSE(map.remove(3)); + EXPECT_EQ(map.size(), 1); + EXPECT_TRUE(map.remove(2)); + EXPECT_EQ(map.size(), 0); +} + +TEST(map, PointerKeys) +{ + char a, b, c, d; + + Map<char *, int> map; + EXPECT_TRUE(map.add(&a, 5)); + EXPECT_FALSE(map.add(&a, 4)); + map.add_new(&b, 1); + map.add_new(&c, 1); + EXPECT_EQ(map.size(), 3); + EXPECT_TRUE(map.remove(&b)); + EXPECT_TRUE(map.add(&b, 8)); + EXPECT_FALSE(map.remove(&d)); + EXPECT_TRUE(map.remove(&a)); + EXPECT_TRUE(map.remove(&b)); + EXPECT_TRUE(map.remove(&c)); + EXPECT_TRUE(map.is_empty()); +} + +TEST(map, ConstKeysAndValues) +{ + Map<const std::string, const std::string> map; + map.reserve(10); + map.add("45", "643"); + EXPECT_TRUE(map.contains("45")); + EXPECT_FALSE(map.contains("54")); +} + +TEST(map, ForeachItem) +{ + Map<int, int> map; + map.add(3, 4); + map.add(1, 8); + + Vector<int> keys; + Vector<int> values; + map.foreach_item([&](int key, int value) { + keys.append(key); + values.append(value); + }); + + EXPECT_EQ(keys.size(), 2); + EXPECT_EQ(values.size(), 2); + EXPECT_EQ(keys.first_index_of(3), values.first_index_of(4)); + EXPECT_EQ(keys.first_index_of(1), values.first_index_of(8)); +} + +/** + * Set this to 1 to activate the benchmark. It is disabled by default, because it prints a lot. + */ +#if 0 +template<typename MapT> +BLI_NOINLINE void benchmark_random_ints(StringRef name, int amount, int factor) +{ + RNG *rng = BLI_rng_new(0); + Vector<int> values; + for (int i = 0; i < amount; i++) { + values.append(BLI_rng_get_int(rng) * factor); + } + BLI_rng_free(rng); + + MapT map; + { + SCOPED_TIMER(name + " Add"); + for (int value : values) { + map.add(value, value); + } + } + int count = 0; + { + SCOPED_TIMER(name + " Contains"); + for (int value : values) { + count += map.contains(value); + } + } + { + SCOPED_TIMER(name + " Remove"); + for (int value : values) { + count += map.remove(value); + } + } + + /* Print the value for simple error checking and to avoid some compiler optimizations. */ + std::cout << "Count: " << count << "\n"; +} + +TEST(map, Benchmark) +{ + for (int i = 0; i < 3; i++) { + benchmark_random_ints<blender::Map<int, int>>("blender::Map ", 1000000, 1); + benchmark_random_ints<blender::StdUnorderedMapWrapper<int, int>>("std::unordered_map", 1000000, 1); + } + std::cout << "\n"; + for (int i = 0; i < 3; i++) { + uint32_t factor = (3 << 10); + benchmark_random_ints<blender::Map<int, int>>("blender::Map ", 1000000, factor); + benchmark_random_ints<blender::StdUnorderedMapWrapper<int, int>>( + "std::unordered_map", 1000000, factor); + } +} + +/** + * Timer 'blender::Map Add' took 61.7616 ms + * Timer 'blender::Map Contains' took 18.4989 ms + * Timer 'blender::Map Remove' took 20.5864 ms + * Count: 1999755 + * Timer 'std::unordered_map Add' took 188.674 ms + * Timer 'std::unordered_map Contains' took 44.3741 ms + * Timer 'std::unordered_map Remove' took 169.52 ms + * Count: 1999755 + * Timer 'blender::Map Add' took 37.9196 ms + * Timer 'blender::Map Contains' took 16.7361 ms + * Timer 'blender::Map Remove' took 20.9568 ms + * Count: 1999755 + * Timer 'std::unordered_map Add' took 166.09 ms + * Timer 'std::unordered_map Contains' took 40.6133 ms + * Timer 'std::unordered_map Remove' took 142.85 ms + * Count: 1999755 + * Timer 'blender::Map Add' took 37.3053 ms + * Timer 'blender::Map Contains' took 16.6731 ms + * Timer 'blender::Map Remove' took 18.8304 ms + * Count: 1999755 + * Timer 'std::unordered_map Add' took 170.964 ms + * Timer 'std::unordered_map Contains' took 38.1824 ms + * Timer 'std::unordered_map Remove' took 140.263 ms + * Count: 1999755 + * + * Timer 'blender::Map Add' took 50.1131 ms + * Timer 'blender::Map Contains' took 25.0491 ms + * Timer 'blender::Map Remove' took 32.4225 ms + * Count: 1889920 + * Timer 'std::unordered_map Add' took 150.129 ms + * Timer 'std::unordered_map Contains' took 34.6999 ms + * Timer 'std::unordered_map Remove' took 120.907 ms + * Count: 1889920 + * Timer 'blender::Map Add' took 50.4438 ms + * Timer 'blender::Map Contains' took 25.2677 ms + * Timer 'blender::Map Remove' took 32.3047 ms + * Count: 1889920 + * Timer 'std::unordered_map Add' took 144.015 ms + * Timer 'std::unordered_map Contains' took 36.3387 ms + * Timer 'std::unordered_map Remove' took 119.109 ms + * Count: 1889920 + * Timer 'blender::Map Add' took 48.6995 ms + * Timer 'blender::Map Contains' took 25.1846 ms + * Timer 'blender::Map Remove' took 33.0283 ms + * Count: 1889920 + * Timer 'std::unordered_map Add' took 143.494 ms + * Timer 'std::unordered_map Contains' took 34.8905 ms + * Timer 'std::unordered_map Remove' took 122.739 ms + * Count: 1889920 + */ + +#endif /* Benchmark */ + +} // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_math_base_safe_test.cc b/source/blender/blenlib/tests/BLI_math_base_safe_test.cc new file mode 100644 index 00000000000..2e3e083cf92 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_math_base_safe_test.cc @@ -0,0 +1,37 @@ +/* Apache License, Version 2.0 */ + +#include "testing/testing.h" + +#include "BLI_math_base_safe.h" + +TEST(math_base, SafePowf) +{ + EXPECT_FLOAT_EQ(safe_powf(4.0f, 3.0f), 64.0f); + EXPECT_FLOAT_EQ(safe_powf(3.2f, 5.6f), 674.2793796f); + EXPECT_FLOAT_EQ(safe_powf(4.0f, -2.0f), 0.0625f); + EXPECT_FLOAT_EQ(safe_powf(6.0f, -3.2f), 0.003235311f); + EXPECT_FLOAT_EQ(safe_powf(-4.0f, 6), 4096.0f); + EXPECT_FLOAT_EQ(safe_powf(-3.0f, 5.5), 0.0f); + EXPECT_FLOAT_EQ(safe_powf(-2.5f, -4.0f), 0.0256f); + EXPECT_FLOAT_EQ(safe_powf(-3.7f, -4.5f), 0.0f); +} + +TEST(math_base, SafeModf) +{ + EXPECT_FLOAT_EQ(safe_modf(3.4, 2.2f), 1.2f); + EXPECT_FLOAT_EQ(safe_modf(3.4, -2.2f), 1.2f); + EXPECT_FLOAT_EQ(safe_modf(-3.4, -2.2f), -1.2f); + EXPECT_FLOAT_EQ(safe_modf(-3.4, 0.0f), 0.0f); + EXPECT_FLOAT_EQ(safe_modf(0.0f, 3.0f), 0.0f); + EXPECT_FLOAT_EQ(safe_modf(55.0f, 10.0f), 5.0f); +} + +TEST(math_base, SafeLogf) +{ + EXPECT_FLOAT_EQ(safe_logf(3.3f, 2.5f), 1.302995247f); + EXPECT_FLOAT_EQ(safe_logf(0.0f, 3.0f), 0.0f); + EXPECT_FLOAT_EQ(safe_logf(3.0f, 0.0f), 0.0f); + EXPECT_FLOAT_EQ(safe_logf(-2.0f, 4.3f), 0.0f); + EXPECT_FLOAT_EQ(safe_logf(2.0f, -4.3f), 0.0f); + EXPECT_FLOAT_EQ(safe_logf(-2.0f, -4.3f), 0.0f); +} diff --git a/source/blender/blenlib/tests/BLI_memory_utils_test.cc b/source/blender/blenlib/tests/BLI_memory_utils_test.cc new file mode 100644 index 00000000000..f3cb02b63d7 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_memory_utils_test.cc @@ -0,0 +1,159 @@ +/* Apache License, Version 2.0 */ + +#include "BLI_float3.hh" +#include "BLI_memory_utils.hh" +#include "BLI_strict_flags.h" +#include "testing/testing.h" + +namespace blender::tests { + +struct MyValue { + static inline int alive = 0; + + MyValue() + { + if (alive == 15) { + throw std::exception(); + } + + alive++; + } + + MyValue(const MyValue &UNUSED(other)) + { + if (alive == 15) { + throw std::exception(); + } + + alive++; + } + + ~MyValue() + { + alive--; + } +}; + +TEST(memory_utils, DefaultConstructN_ActuallyCallsConstructor) +{ + constexpr int amount = 10; + TypedBuffer<MyValue, amount> buffer; + + EXPECT_EQ(MyValue::alive, 0); + default_construct_n(buffer.ptr(), amount); + EXPECT_EQ(MyValue::alive, amount); + destruct_n(buffer.ptr(), amount); + EXPECT_EQ(MyValue::alive, 0); +} + +TEST(memory_utils, DefaultConstructN_StrongExceptionSafety) +{ + constexpr int amount = 20; + TypedBuffer<MyValue, amount> buffer; + + EXPECT_EQ(MyValue::alive, 0); + EXPECT_THROW(default_construct_n(buffer.ptr(), amount), std::exception); + EXPECT_EQ(MyValue::alive, 0); +} + +TEST(memory_utils, UninitializedCopyN_ActuallyCopies) +{ + constexpr int amount = 5; + TypedBuffer<MyValue, amount> buffer1; + TypedBuffer<MyValue, amount> buffer2; + + EXPECT_EQ(MyValue::alive, 0); + default_construct_n(buffer1.ptr(), amount); + EXPECT_EQ(MyValue::alive, amount); + uninitialized_copy_n(buffer1.ptr(), amount, buffer2.ptr()); + EXPECT_EQ(MyValue::alive, 2 * amount); + destruct_n(buffer1.ptr(), amount); + EXPECT_EQ(MyValue::alive, amount); + destruct_n(buffer2.ptr(), amount); + EXPECT_EQ(MyValue::alive, 0); +} + +TEST(memory_utils, UninitializedCopyN_StrongExceptionSafety) +{ + constexpr int amount = 10; + TypedBuffer<MyValue, amount> buffer1; + TypedBuffer<MyValue, amount> buffer2; + + EXPECT_EQ(MyValue::alive, 0); + default_construct_n(buffer1.ptr(), amount); + EXPECT_EQ(MyValue::alive, amount); + EXPECT_THROW(uninitialized_copy_n(buffer1.ptr(), amount, buffer2.ptr()), std::exception); + EXPECT_EQ(MyValue::alive, amount); + destruct_n(buffer1.ptr(), amount); + EXPECT_EQ(MyValue::alive, 0); +} + +TEST(memory_utils, UninitializedFillN_ActuallyCopies) +{ + constexpr int amount = 10; + TypedBuffer<MyValue, amount> buffer; + + EXPECT_EQ(MyValue::alive, 0); + { + MyValue value; + EXPECT_EQ(MyValue::alive, 1); + uninitialized_fill_n(buffer.ptr(), amount, value); + EXPECT_EQ(MyValue::alive, 1 + amount); + destruct_n(buffer.ptr(), amount); + EXPECT_EQ(MyValue::alive, 1); + } + EXPECT_EQ(MyValue::alive, 0); +} + +TEST(memory_utils, UninitializedFillN_StrongExceptionSafety) +{ + constexpr int amount = 20; + TypedBuffer<MyValue, amount> buffer; + + EXPECT_EQ(MyValue::alive, 0); + { + MyValue value; + EXPECT_EQ(MyValue::alive, 1); + EXPECT_THROW(uninitialized_fill_n(buffer.ptr(), amount, value), std::exception); + EXPECT_EQ(MyValue::alive, 1); + } + EXPECT_EQ(MyValue::alive, 0); +} + +class TestBaseClass { + virtual void mymethod(){}; +}; + +class TestChildClass : public TestBaseClass { + void mymethod() override + { + } +}; + +static_assert(is_convertible_pointer_v<int *, int *>); +static_assert(is_convertible_pointer_v<int *, const int *>); +static_assert(is_convertible_pointer_v<int *, int *const>); +static_assert(is_convertible_pointer_v<int *, const int *const>); +static_assert(!is_convertible_pointer_v<const int *, int *>); +static_assert(!is_convertible_pointer_v<int, int *>); +static_assert(!is_convertible_pointer_v<int *, int>); +static_assert(is_convertible_pointer_v<TestBaseClass *, const TestBaseClass *>); +static_assert(!is_convertible_pointer_v<const TestBaseClass *, TestBaseClass *>); +static_assert(is_convertible_pointer_v<TestChildClass *, TestBaseClass *>); +static_assert(!is_convertible_pointer_v<TestBaseClass *, TestChildClass *>); +static_assert(is_convertible_pointer_v<const TestChildClass *, const TestBaseClass *>); +static_assert(!is_convertible_pointer_v<TestBaseClass, const TestChildClass *>); +static_assert(!is_convertible_pointer_v<float3, float *>); +static_assert(!is_convertible_pointer_v<float *, float3>); +static_assert(!is_convertible_pointer_v<int **, int *>); +static_assert(!is_convertible_pointer_v<int *, int **>); +static_assert(is_convertible_pointer_v<int **, int **>); +static_assert(is_convertible_pointer_v<const int **, const int **>); +static_assert(!is_convertible_pointer_v<const int **, int **>); +static_assert(!is_convertible_pointer_v<int *const *, int **>); +static_assert(!is_convertible_pointer_v<int *const *const, int **>); +static_assert(is_convertible_pointer_v<int **, int **const>); +static_assert(is_convertible_pointer_v<int **, int *const *>); +static_assert(is_convertible_pointer_v<int **, int const *const *>); + +} // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_multi_value_map_test.cc b/source/blender/blenlib/tests/BLI_multi_value_map_test.cc new file mode 100644 index 00000000000..7501fbe0d87 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_multi_value_map_test.cc @@ -0,0 +1,109 @@ +/* Apache License, Version 2.0 */ + +#include "BLI_multi_value_map.hh" +#include "BLI_vector.hh" +#include "testing/testing.h" + +namespace blender::tests { + +TEST(multi_value_map, LookupNotExistant) +{ + MultiValueMap<int, int> map; + EXPECT_EQ(map.lookup(5).size(), 0); + map.add(2, 5); + EXPECT_EQ(map.lookup(5).size(), 0); +} + +TEST(multi_value_map, LookupExistant) +{ + MultiValueMap<int, int> map; + map.add(2, 4); + map.add(2, 5); + map.add(3, 6); + + EXPECT_EQ(map.lookup(2).size(), 2); + EXPECT_EQ(map.lookup(2)[0], 4); + EXPECT_EQ(map.lookup(2)[1], 5); + + EXPECT_EQ(map.lookup(3).size(), 1); + EXPECT_EQ(map.lookup(3)[0], 6); +} + +TEST(multi_value_map, AddMultiple) +{ + MultiValueMap<int, int> map; + map.add_multiple(2, {4, 5, 6}); + map.add_multiple(2, {1, 2}); + map.add_multiple(5, {7, 5, 3}); + + EXPECT_EQ(map.lookup(2).size(), 5); + EXPECT_EQ(map.lookup(2)[0], 4); + EXPECT_EQ(map.lookup(2)[1], 5); + EXPECT_EQ(map.lookup(2)[2], 6); + EXPECT_EQ(map.lookup(2)[3], 1); + EXPECT_EQ(map.lookup(2)[4], 2); + + EXPECT_EQ(map.lookup(5).size(), 3); + EXPECT_EQ(map.lookup(5)[0], 7); + EXPECT_EQ(map.lookup(5)[1], 5); + EXPECT_EQ(map.lookup(5)[2], 3); +} + +TEST(multi_value_map, Keys) +{ + MultiValueMap<int, int> map; + map.add(5, 7); + map.add(5, 7); + map.add_multiple(2, {6, 7, 8}); + + Vector<int> keys; + for (int key : map.keys()) { + keys.append(key); + } + + EXPECT_EQ(keys.size(), 2); + EXPECT_TRUE(keys.contains(5)); + EXPECT_TRUE(keys.contains(2)); +} + +TEST(multi_value_map, Values) +{ + MultiValueMap<int, int> map; + map.add(3, 5); + map.add_multiple(3, {1, 2}); + map.add(6, 1); + + Vector<Span<int>> values; + for (Span<int> value_span : map.values()) { + values.append(value_span); + } + + EXPECT_EQ(values.size(), 2); +} + +TEST(multi_value_map, Items) +{ + MultiValueMap<int, int> map; + map.add_multiple(4, {1, 2, 3}); + + for (auto &&item : map.items()) { + int key = item.key; + Span<int> values = item.value; + EXPECT_EQ(key, 4); + EXPECT_EQ(values.size(), 3); + EXPECT_EQ(values[0], 1); + EXPECT_EQ(values[1], 2); + EXPECT_EQ(values[2], 3); + } +} + +TEST(multi_value_map, UniquePtr) +{ + /* Mostly testing if it compiles here. */ + MultiValueMap<std::unique_ptr<int>, std::unique_ptr<int>> map; + map.add(std::make_unique<int>(4), std::make_unique<int>(6)); + map.add(std::make_unique<int>(4), std::make_unique<int>(7)); + EXPECT_EQ(map.lookup(std::make_unique<int>(10)).size(), 0); +} + +} // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_set_test.cc b/source/blender/blenlib/tests/BLI_set_test.cc new file mode 100644 index 00000000000..7bd0b258df8 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_set_test.cc @@ -0,0 +1,565 @@ +/* Apache License, Version 2.0 */ + +#include <set> +#include <unordered_set> + +#include "BLI_ghash.h" +#include "BLI_rand.h" +#include "BLI_set.hh" +#include "BLI_strict_flags.h" +#include "BLI_timeit.hh" +#include "BLI_vector.hh" +#include "testing/testing.h" + +namespace blender { +namespace tests { + +TEST(set, DefaultConstructor) +{ + Set<int> set; + EXPECT_EQ(set.size(), 0); + EXPECT_TRUE(set.is_empty()); +} + +TEST(set, ContainsNotExistant) +{ + Set<int> set; + EXPECT_FALSE(set.contains(3)); +} + +TEST(set, ContainsExistant) +{ + Set<int> set; + EXPECT_FALSE(set.contains(5)); + EXPECT_TRUE(set.is_empty()); + set.add(5); + EXPECT_TRUE(set.contains(5)); + EXPECT_FALSE(set.is_empty()); +} + +TEST(set, AddMany) +{ + Set<int> set; + for (int i = 0; i < 100; i++) { + set.add(i); + } + + for (int i = 50; i < 100; i++) { + EXPECT_TRUE(set.contains(i)); + } + for (int i = 100; i < 150; i++) { + EXPECT_FALSE(set.contains(i)); + } +} + +TEST(set, InitializerListConstructor) +{ + Set<int> set = {4, 5, 6}; + EXPECT_EQ(set.size(), 3); + EXPECT_TRUE(set.contains(4)); + EXPECT_TRUE(set.contains(5)); + EXPECT_TRUE(set.contains(6)); + EXPECT_FALSE(set.contains(2)); + EXPECT_FALSE(set.contains(3)); +} + +TEST(set, CopyConstructor) +{ + Set<int> set = {3}; + EXPECT_TRUE(set.contains(3)); + EXPECT_FALSE(set.contains(4)); + + Set<int> set2(set); + set2.add(4); + EXPECT_TRUE(set2.contains(3)); + EXPECT_TRUE(set2.contains(4)); + + EXPECT_FALSE(set.contains(4)); +} + +TEST(set, MoveConstructor) +{ + Set<int> set = {1, 2, 3}; + EXPECT_EQ(set.size(), 3); + Set<int> set2(std::move(set)); + EXPECT_EQ(set.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(set2.size(), 3); +} + +TEST(set, CopyAssignment) +{ + Set<int> set = {3}; + EXPECT_TRUE(set.contains(3)); + EXPECT_FALSE(set.contains(4)); + + Set<int> set2; + set2 = set; + set2.add(4); + EXPECT_TRUE(set2.contains(3)); + EXPECT_TRUE(set2.contains(4)); + + EXPECT_FALSE(set.contains(4)); +} + +TEST(set, MoveAssignment) +{ + Set<int> set = {1, 2, 3}; + EXPECT_EQ(set.size(), 3); + Set<int> set2; + set2 = std::move(set); + EXPECT_EQ(set.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(set2.size(), 3); +} + +TEST(set, RemoveContained) +{ + Set<int> set = {3, 4, 5}; + EXPECT_TRUE(set.contains(3)); + EXPECT_TRUE(set.contains(4)); + EXPECT_TRUE(set.contains(5)); + set.remove_contained(4); + EXPECT_TRUE(set.contains(3)); + EXPECT_FALSE(set.contains(4)); + EXPECT_TRUE(set.contains(5)); + set.remove_contained(3); + EXPECT_FALSE(set.contains(3)); + EXPECT_FALSE(set.contains(4)); + EXPECT_TRUE(set.contains(5)); + set.remove_contained(5); + EXPECT_FALSE(set.contains(3)); + EXPECT_FALSE(set.contains(4)); + EXPECT_FALSE(set.contains(5)); +} + +TEST(set, RemoveContainedMany) +{ + Set<int> set; + for (int i = 0; i < 1000; i++) { + set.add(i); + } + for (int i = 100; i < 1000; i++) { + set.remove_contained(i); + } + for (int i = 900; i < 1000; i++) { + set.add(i); + } + + for (int i = 0; i < 1000; i++) { + if (i < 100 || i >= 900) { + EXPECT_TRUE(set.contains(i)); + } + else { + EXPECT_FALSE(set.contains(i)); + } + } +} + +TEST(set, Intersects) +{ + Set<int> a = {3, 4, 5, 6}; + Set<int> b = {1, 2, 5}; + EXPECT_TRUE(Set<int>::Intersects(a, b)); + EXPECT_FALSE(Set<int>::Disjoint(a, b)); +} + +TEST(set, Disjoint) +{ + Set<int> a = {5, 6, 7, 8}; + Set<int> b = {2, 3, 4, 9}; + EXPECT_FALSE(Set<int>::Intersects(a, b)); + EXPECT_TRUE(Set<int>::Disjoint(a, b)); +} + +TEST(set, AddMultiple) +{ + Set<int> a; + a.add_multiple({5, 7}); + EXPECT_TRUE(a.contains(5)); + EXPECT_TRUE(a.contains(7)); + EXPECT_FALSE(a.contains(4)); + a.add_multiple({2, 4, 7}); + EXPECT_TRUE(a.contains(4)); + EXPECT_TRUE(a.contains(2)); + EXPECT_EQ(a.size(), 4); +} + +TEST(set, AddMultipleNew) +{ + Set<int> a; + a.add_multiple_new({5, 6}); + EXPECT_TRUE(a.contains(5)); + EXPECT_TRUE(a.contains(6)); +} + +TEST(set, Iterator) +{ + Set<int> set = {1, 3, 2, 5, 4}; + blender::Vector<int> vec; + for (int value : set) { + vec.append(value); + } + EXPECT_EQ(vec.size(), 5); + EXPECT_TRUE(vec.contains(1)); + EXPECT_TRUE(vec.contains(3)); + EXPECT_TRUE(vec.contains(2)); + EXPECT_TRUE(vec.contains(5)); + EXPECT_TRUE(vec.contains(4)); +} + +TEST(set, OftenAddRemoveContained) +{ + Set<int> set; + for (int i = 0; i < 100; i++) { + set.add(42); + EXPECT_EQ(set.size(), 1); + set.remove_contained(42); + EXPECT_EQ(set.size(), 0); + } +} + +TEST(set, UniquePtrValues) +{ + Set<std::unique_ptr<int>> set; + set.add_new(std::unique_ptr<int>(new int())); + auto value1 = std::unique_ptr<int>(new int()); + set.add_new(std::move(value1)); + set.add(std::unique_ptr<int>(new int())); + + EXPECT_EQ(set.size(), 3); +} + +TEST(set, Clear) +{ + Set<int> set = {3, 4, 6, 7}; + EXPECT_EQ(set.size(), 4); + set.clear(); + EXPECT_EQ(set.size(), 0); +} + +TEST(set, StringSet) +{ + Set<std::string> set; + set.add("hello"); + set.add("world"); + EXPECT_EQ(set.size(), 2); + EXPECT_TRUE(set.contains("hello")); + EXPECT_TRUE(set.contains("world")); + EXPECT_FALSE(set.contains("world2")); +} + +TEST(set, PointerSet) +{ + int a, b, c; + Set<int *> set; + set.add(&a); + set.add(&b); + EXPECT_EQ(set.size(), 2); + EXPECT_TRUE(set.contains(&a)); + EXPECT_TRUE(set.contains(&b)); + EXPECT_FALSE(set.contains(&c)); +} + +TEST(set, Remove) +{ + Set<int> set = {1, 2, 3, 4, 5, 6}; + EXPECT_EQ(set.size(), 6); + EXPECT_TRUE(set.remove(2)); + EXPECT_EQ(set.size(), 5); + EXPECT_FALSE(set.contains(2)); + EXPECT_FALSE(set.remove(2)); + EXPECT_EQ(set.size(), 5); + EXPECT_TRUE(set.remove(5)); + EXPECT_EQ(set.size(), 4); +} + +struct Type1 { + uint32_t value; +}; + +struct Type2 { + uint32_t value; +}; + +static bool operator==(const Type1 &a, const Type1 &b) +{ + return a.value == b.value; +} +static bool operator==(const Type2 &a, const Type1 &b) +{ + return a.value == b.value; +} + +} // namespace tests + +/* This has to be defined in ::blender namespace. */ +template<> struct DefaultHash<tests::Type1> { + uint32_t operator()(const tests::Type1 &value) const + { + return value.value; + } + + uint32_t operator()(const tests::Type2 &value) const + { + return value.value; + } +}; + +namespace tests { + +TEST(set, ContainsAs) +{ + Set<Type1> set; + set.add(Type1{5}); + EXPECT_TRUE(set.contains_as(Type1{5})); + EXPECT_TRUE(set.contains_as(Type2{5})); + EXPECT_FALSE(set.contains_as(Type1{6})); + EXPECT_FALSE(set.contains_as(Type2{6})); +} + +TEST(set, ContainsAsString) +{ + Set<std::string> set; + set.add("test"); + EXPECT_TRUE(set.contains_as("test")); + EXPECT_TRUE(set.contains_as(StringRef("test"))); + EXPECT_FALSE(set.contains_as("string")); + EXPECT_FALSE(set.contains_as(StringRef("string"))); +} + +TEST(set, RemoveContainedAs) +{ + Set<Type1> set; + set.add(Type1{5}); + EXPECT_TRUE(set.contains_as(Type2{5})); + set.remove_contained_as(Type2{5}); + EXPECT_FALSE(set.contains_as(Type2{5})); +} + +TEST(set, RemoveAs) +{ + Set<Type1> set; + set.add(Type1{5}); + EXPECT_TRUE(set.contains_as(Type2{5})); + set.remove_as(Type2{6}); + EXPECT_TRUE(set.contains_as(Type2{5})); + set.remove_as(Type2{5}); + EXPECT_FALSE(set.contains_as(Type2{5})); + set.remove_as(Type2{5}); + EXPECT_FALSE(set.contains_as(Type2{5})); +} + +TEST(set, AddAs) +{ + Set<std::string> set; + EXPECT_TRUE(set.add_as("test")); + EXPECT_TRUE(set.add_as(StringRef("qwe"))); + EXPECT_FALSE(set.add_as(StringRef("test"))); + EXPECT_FALSE(set.add_as("qwe")); +} + +template<uint N> struct EqualityIntModN { + bool operator()(uint a, uint b) const + { + return (a % N) == (b % N); + } +}; + +template<uint N> struct HashIntModN { + uint64_t operator()(uint value) const + { + return value % N; + } +}; + +TEST(set, CustomizeHashAndEquality) +{ + Set<uint, 0, DefaultProbingStrategy, HashIntModN<10>, EqualityIntModN<10>> set; + set.add(4); + EXPECT_TRUE(set.contains(4)); + EXPECT_TRUE(set.contains(14)); + EXPECT_TRUE(set.contains(104)); + EXPECT_FALSE(set.contains(5)); + set.add(55); + EXPECT_TRUE(set.contains(5)); + EXPECT_TRUE(set.contains(14)); + set.remove(1004); + EXPECT_FALSE(set.contains(14)); +} + +TEST(set, IntrusiveIntKey) +{ + Set<int, + 2, + DefaultProbingStrategy, + DefaultHash<int>, + DefaultEquality, + IntegerSetSlot<int, 100, 200>> + set; + EXPECT_TRUE(set.add(4)); + EXPECT_TRUE(set.add(3)); + EXPECT_TRUE(set.add(11)); + EXPECT_TRUE(set.add(8)); + EXPECT_FALSE(set.add(3)); + EXPECT_FALSE(set.add(4)); + EXPECT_TRUE(set.remove(4)); + EXPECT_FALSE(set.remove(7)); + EXPECT_TRUE(set.add(4)); + EXPECT_TRUE(set.remove(4)); +} + +struct MyKeyType { + uint32_t key; + int32_t attached_data; + + uint64_t hash() const + { + return key; + } + + friend bool operator==(const MyKeyType &a, const MyKeyType &b) + { + return a.key == b.key; + } +}; + +TEST(set, LookupKey) +{ + Set<MyKeyType> set; + set.add({1, 10}); + set.add({2, 20}); + EXPECT_EQ(set.lookup_key({1, 30}).attached_data, 10); + EXPECT_EQ(set.lookup_key({2, 0}).attached_data, 20); +} + +TEST(set, LookupKeyDefault) +{ + Set<MyKeyType> set; + set.add({1, 10}); + set.add({2, 20}); + + MyKeyType fallback{5, 50}; + EXPECT_EQ(set.lookup_key_default({1, 66}, fallback).attached_data, 10); + EXPECT_EQ(set.lookup_key_default({4, 40}, fallback).attached_data, 50); +} + +TEST(set, LookupKeyPtr) +{ + Set<MyKeyType> set; + set.add({1, 10}); + set.add({2, 20}); + EXPECT_EQ(set.lookup_key_ptr({1, 50})->attached_data, 10); + EXPECT_EQ(set.lookup_key_ptr({2, 50})->attached_data, 20); + EXPECT_EQ(set.lookup_key_ptr({3, 50}), nullptr); +} + +/** + * Set this to 1 to activate the benchmark. It is disabled by default, because it prints a lot. + */ +#if 0 +template<typename SetT> +BLI_NOINLINE void benchmark_random_ints(StringRef name, int amount, int factor) +{ + RNG *rng = BLI_rng_new(0); + Vector<int> values; + for (int i = 0; i < amount; i++) { + values.append(BLI_rng_get_int(rng) * factor); + } + BLI_rng_free(rng); + + SetT set; + { + SCOPED_TIMER(name + " Add"); + for (int value : values) { + set.add(value); + } + } + int count = 0; + { + SCOPED_TIMER(name + " Contains"); + for (int value : values) { + count += set.contains(value); + } + } + { + SCOPED_TIMER(name + " Remove"); + for (int value : values) { + count += set.remove(value); + } + } + + /* Print the value for simple error checking and to avoid some compiler optimizations. */ + std::cout << "Count: " << count << "\n"; +} + +TEST(set, Benchmark) +{ + for (int i = 0; i < 3; i++) { + benchmark_random_ints<blender::Set<int>>("blender::Set ", 100000, 1); + benchmark_random_ints<blender::StdUnorderedSetWrapper<int>>("std::unordered_set", 100000, 1); + } + std::cout << "\n"; + for (int i = 0; i < 3; i++) { + uint32_t factor = (3 << 10); + benchmark_random_ints<blender::Set<int>>("blender::Set ", 100000, factor); + benchmark_random_ints<blender::StdUnorderedSetWrapper<int>>("std::unordered_set", 100000, factor); + } +} + +/** + * Output of the rudimentary benchmark above on my hardware. + * + * Timer 'blender::Set Add' took 5.5573 ms + * Timer 'blender::Set Contains' took 0.807384 ms + * Timer 'blender::Set Remove' took 0.953436 ms + * Count: 199998 + * Timer 'std::unordered_set Add' took 12.551 ms + * Timer 'std::unordered_set Contains' took 2.3323 ms + * Timer 'std::unordered_set Remove' took 5.07082 ms + * Count: 199998 + * Timer 'blender::Set Add' took 2.62526 ms + * Timer 'blender::Set Contains' took 0.407499 ms + * Timer 'blender::Set Remove' took 0.472981 ms + * Count: 199998 + * Timer 'std::unordered_set Add' took 6.26945 ms + * Timer 'std::unordered_set Contains' took 1.17236 ms + * Timer 'std::unordered_set Remove' took 3.77402 ms + * Count: 199998 + * Timer 'blender::Set Add' took 2.59152 ms + * Timer 'blender::Set Contains' took 0.415254 ms + * Timer 'blender::Set Remove' took 0.477559 ms + * Count: 199998 + * Timer 'std::unordered_set Add' took 6.28129 ms + * Timer 'std::unordered_set Contains' took 1.17562 ms + * Timer 'std::unordered_set Remove' took 3.77811 ms + * Count: 199998 + * + * Timer 'blender::Set Add' took 3.16514 ms + * Timer 'blender::Set Contains' took 0.732895 ms + * Timer 'blender::Set Remove' took 1.08171 ms + * Count: 198790 + * Timer 'std::unordered_set Add' took 6.57377 ms + * Timer 'std::unordered_set Contains' took 1.17008 ms + * Timer 'std::unordered_set Remove' took 3.7946 ms + * Count: 198790 + * Timer 'blender::Set Add' took 3.11439 ms + * Timer 'blender::Set Contains' took 0.740159 ms + * Timer 'blender::Set Remove' took 1.06749 ms + * Count: 198790 + * Timer 'std::unordered_set Add' took 6.35597 ms + * Timer 'std::unordered_set Contains' took 1.17713 ms + * Timer 'std::unordered_set Remove' took 3.77826 ms + * Count: 198790 + * Timer 'blender::Set Add' took 3.09876 ms + * Timer 'blender::Set Contains' took 0.742072 ms + * Timer 'blender::Set Remove' took 1.06622 ms + * Count: 198790 + * Timer 'std::unordered_set Add' took 6.4469 ms + * Timer 'std::unordered_set Contains' took 1.16515 ms + * Timer 'std::unordered_set Remove' took 3.80639 ms + * Count: 198790 + */ + +#endif /* Benchmark */ + +} // namespace tests +} // namespace blender diff --git a/source/blender/blenlib/tests/BLI_span_test.cc b/source/blender/blenlib/tests/BLI_span_test.cc new file mode 100644 index 00000000000..587497624f4 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_span_test.cc @@ -0,0 +1,311 @@ +/* Apache License, Version 2.0 */ + +#include "BLI_span.hh" +#include "BLI_strict_flags.h" +#include "BLI_vector.hh" +#include "testing/testing.h" + +namespace blender::tests { + +TEST(span, FromSmallVector) +{ + Vector<int> a = {1, 2, 3}; + Span<int> a_span = a; + EXPECT_EQ(a_span.size(), 3); + EXPECT_EQ(a_span[0], 1); + EXPECT_EQ(a_span[1], 2); + EXPECT_EQ(a_span[2], 3); +} + +TEST(span, AddConstToPointer) +{ + int a = 0; + std::vector<int *> vec = {&a}; + Span<int *> span = vec; + Span<const int *> const_span = span; + EXPECT_EQ(const_span.size(), 1); +} + +TEST(span, IsReferencing) +{ + int array[] = {3, 5, 8}; + MutableSpan<int> span(array, ARRAY_SIZE(array)); + EXPECT_EQ(span.size(), 3); + EXPECT_EQ(span[1], 5); + array[1] = 10; + EXPECT_EQ(span[1], 10); +} + +TEST(span, DropBack) +{ + Vector<int> a = {4, 5, 6, 7}; + auto slice = Span<int>(a).drop_back(2); + EXPECT_EQ(slice.size(), 2); + EXPECT_EQ(slice[0], 4); + EXPECT_EQ(slice[1], 5); +} + +TEST(span, DropBackAll) +{ + Vector<int> a = {4, 5, 6, 7}; + auto slice = Span<int>(a).drop_back(a.size()); + EXPECT_EQ(slice.size(), 0); +} + +TEST(span, DropFront) +{ + Vector<int> a = {4, 5, 6, 7}; + auto slice = Span<int>(a).drop_front(1); + EXPECT_EQ(slice.size(), 3); + EXPECT_EQ(slice[0], 5); + EXPECT_EQ(slice[1], 6); + EXPECT_EQ(slice[2], 7); +} + +TEST(span, DropFrontAll) +{ + Vector<int> a = {4, 5, 6, 7}; + auto slice = Span<int>(a).drop_front(a.size()); + EXPECT_EQ(slice.size(), 0); +} + +TEST(span, TakeFront) +{ + Vector<int> a = {4, 5, 6, 7}; + auto slice = Span<int>(a).take_front(2); + EXPECT_EQ(slice.size(), 2); + EXPECT_EQ(slice[0], 4); + EXPECT_EQ(slice[1], 5); +} + +TEST(span, TakeBack) +{ + Vector<int> a = {5, 6, 7, 8}; + auto slice = Span<int>(a).take_back(2); + EXPECT_EQ(slice.size(), 2); + EXPECT_EQ(slice[0], 7); + EXPECT_EQ(slice[1], 8); +} + +TEST(span, Slice) +{ + Vector<int> a = {4, 5, 6, 7}; + auto slice = Span<int>(a).slice(1, 2); + EXPECT_EQ(slice.size(), 2); + EXPECT_EQ(slice[0], 5); + EXPECT_EQ(slice[1], 6); +} + +TEST(span, SliceEmpty) +{ + Vector<int> a = {4, 5, 6, 7}; + auto slice = Span<int>(a).slice(2, 0); + EXPECT_EQ(slice.size(), 0); +} + +TEST(span, SliceRange) +{ + Vector<int> a = {1, 2, 3, 4, 5}; + auto slice = Span<int>(a).slice(IndexRange(2, 2)); + EXPECT_EQ(slice.size(), 2); + EXPECT_EQ(slice[0], 3); + EXPECT_EQ(slice[1], 4); +} + +TEST(span, Contains) +{ + Vector<int> a = {4, 5, 6, 7}; + Span<int> a_span = a; + EXPECT_TRUE(a_span.contains(4)); + EXPECT_TRUE(a_span.contains(5)); + EXPECT_TRUE(a_span.contains(6)); + EXPECT_TRUE(a_span.contains(7)); + EXPECT_FALSE(a_span.contains(3)); + EXPECT_FALSE(a_span.contains(8)); +} + +TEST(span, Count) +{ + Vector<int> a = {2, 3, 4, 3, 3, 2, 2, 2, 2}; + Span<int> a_span = a; + EXPECT_EQ(a_span.count(1), 0); + EXPECT_EQ(a_span.count(2), 5); + EXPECT_EQ(a_span.count(3), 3); + EXPECT_EQ(a_span.count(4), 1); + EXPECT_EQ(a_span.count(5), 0); +} + +static void test_ref_from_initializer_list(Span<int> span) +{ + EXPECT_EQ(span.size(), 4); + EXPECT_EQ(span[0], 3); + EXPECT_EQ(span[1], 6); + EXPECT_EQ(span[2], 8); + EXPECT_EQ(span[3], 9); +} + +TEST(span, FromInitializerList) +{ + test_ref_from_initializer_list({3, 6, 8, 9}); +} + +TEST(span, FromVector) +{ + std::vector<int> a = {1, 2, 3, 4}; + Span<int> a_span(a); + EXPECT_EQ(a_span.size(), 4); + EXPECT_EQ(a_span[0], 1); + EXPECT_EQ(a_span[1], 2); + EXPECT_EQ(a_span[2], 3); + EXPECT_EQ(a_span[3], 4); +} + +TEST(span, FromArray) +{ + std::array<int, 2> a = {5, 6}; + Span<int> a_span(a); + EXPECT_EQ(a_span.size(), 2); + EXPECT_EQ(a_span[0], 5); + EXPECT_EQ(a_span[1], 6); +} + +TEST(span, Fill) +{ + std::array<int, 5> a = {4, 5, 6, 7, 8}; + MutableSpan<int> a_span(a); + a_span.fill(1); + EXPECT_EQ(a[0], 1); + EXPECT_EQ(a[1], 1); + EXPECT_EQ(a[2], 1); + EXPECT_EQ(a[3], 1); + EXPECT_EQ(a[4], 1); +} + +TEST(span, FillIndices) +{ + std::array<int, 5> a = {0, 0, 0, 0, 0}; + MutableSpan<int> a_span(a); + a_span.fill_indices({0, 2, 3}, 1); + EXPECT_EQ(a[0], 1); + EXPECT_EQ(a[1], 0); + EXPECT_EQ(a[2], 1); + EXPECT_EQ(a[3], 1); + EXPECT_EQ(a[4], 0); +} + +TEST(span, SizeInBytes) +{ + std::array<int, 10> a; + Span<int> a_span(a); + EXPECT_EQ(a_span.size_in_bytes(), (int64_t)sizeof(a)); + EXPECT_EQ(a_span.size_in_bytes(), 40); +} + +TEST(span, FirstLast) +{ + std::array<int, 4> a = {6, 7, 8, 9}; + Span<int> a_span(a); + EXPECT_EQ(a_span.first(), 6); + EXPECT_EQ(a_span.last(), 9); +} + +TEST(span, FirstLast_OneElement) +{ + int a = 3; + Span<int> a_span(&a, 1); + EXPECT_EQ(a_span.first(), 3); + EXPECT_EQ(a_span.last(), 3); +} + +TEST(span, Get) +{ + std::array<int, 3> a = {5, 6, 7}; + Span<int> a_span(a); + EXPECT_EQ(a_span.get(0, 42), 5); + EXPECT_EQ(a_span.get(1, 42), 6); + EXPECT_EQ(a_span.get(2, 42), 7); + EXPECT_EQ(a_span.get(3, 42), 42); + EXPECT_EQ(a_span.get(4, 42), 42); +} + +TEST(span, ContainsPtr) +{ + std::array<int, 3> a = {5, 6, 7}; + int other = 10; + Span<int> a_span(a); + EXPECT_TRUE(a_span.contains_ptr(&a[0] + 0)); + EXPECT_TRUE(a_span.contains_ptr(&a[0] + 1)); + EXPECT_TRUE(a_span.contains_ptr(&a[0] + 2)); + EXPECT_FALSE(a_span.contains_ptr(&a[0] + 3)); + EXPECT_FALSE(a_span.contains_ptr(&a[0] - 1)); + EXPECT_FALSE(a_span.contains_ptr(&other)); +} + +TEST(span, FirstIndex) +{ + std::array<int, 5> a = {4, 5, 4, 2, 5}; + Span<int> a_span(a); + + EXPECT_EQ(a_span.first_index(4), 0); + EXPECT_EQ(a_span.first_index(5), 1); + EXPECT_EQ(a_span.first_index(2), 3); +} + +TEST(span, CastSameSize) +{ + int value = 0; + std::array<int *, 4> a = {&value, nullptr, nullptr, nullptr}; + Span<int *> a_span = a; + Span<float *> new_a_span = a_span.cast<float *>(); + + EXPECT_EQ(a_span.size(), 4); + EXPECT_EQ(new_a_span.size(), 4); + + EXPECT_EQ(a_span[0], &value); + EXPECT_EQ(new_a_span[0], (float *)&value); +} + +TEST(span, CastSmallerSize) +{ + std::array<uint32_t, 4> a = {3, 4, 5, 6}; + Span<uint32_t> a_span = a; + Span<uint16_t> new_a_span = a_span.cast<uint16_t>(); + + EXPECT_EQ(a_span.size(), 4); + EXPECT_EQ(new_a_span.size(), 8); +} + +TEST(span, CastLargerSize) +{ + std::array<uint16_t, 4> a = {4, 5, 6, 7}; + Span<uint16_t> a_span = a; + Span<uint32_t> new_a_span = a_span.cast<uint32_t>(); + + EXPECT_EQ(a_span.size(), 4); + EXPECT_EQ(new_a_span.size(), 2); +} + +TEST(span, VoidPointerSpan) +{ + int a; + float b; + double c; + + auto func1 = [](Span<void *> span) { EXPECT_EQ(span.size(), 3); }; + func1({&a, &b, &c}); +} + +TEST(span, CopyFrom) +{ + std::array<int, 4> src = {5, 6, 7, 8}; + std::array<int, 4> dst = {1, 2, 3, 4}; + + EXPECT_EQ(dst[2], 3); + MutableSpan(dst).copy_from(src); + EXPECT_EQ(dst[0], 5); + EXPECT_EQ(dst[1], 6); + EXPECT_EQ(dst[2], 7); + EXPECT_EQ(dst[3], 8); +} + +} // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_stack_cxx_test.cc b/source/blender/blenlib/tests/BLI_stack_cxx_test.cc new file mode 100644 index 00000000000..3572e751b88 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_stack_cxx_test.cc @@ -0,0 +1,188 @@ +/* Apache License, Version 2.0 */ + +#include "BLI_stack.hh" +#include "BLI_strict_flags.h" +#include "BLI_vector.hh" +#include "testing/testing.h" + +namespace blender::tests { + +TEST(stack, DefaultConstructor) +{ + Stack<int> stack; + EXPECT_EQ(stack.size(), 0); + EXPECT_TRUE(stack.is_empty()); +} + +TEST(stack, SpanConstructor) +{ + std::array<int, 3> array = {4, 7, 2}; + Stack<int> stack(array); + EXPECT_EQ(stack.size(), 3); + EXPECT_EQ(stack.pop(), 2); + EXPECT_EQ(stack.pop(), 7); + EXPECT_EQ(stack.pop(), 4); + EXPECT_TRUE(stack.is_empty()); +} + +TEST(stack, CopyConstructor) +{ + Stack<int> stack1 = {1, 2, 3, 4, 5, 6, 7}; + Stack<int> stack2 = stack1; + EXPECT_EQ(stack1.size(), 7); + EXPECT_EQ(stack2.size(), 7); + for (int i = 7; i >= 1; i--) { + EXPECT_FALSE(stack1.is_empty()); + EXPECT_FALSE(stack2.is_empty()); + EXPECT_EQ(stack1.pop(), i); + EXPECT_EQ(stack2.pop(), i); + } + EXPECT_TRUE(stack1.is_empty()); + EXPECT_TRUE(stack2.is_empty()); +} + +TEST(stack, MoveConstructor) +{ + Stack<int> stack1 = {1, 2, 3, 4, 5, 6, 7}; + Stack<int> stack2 = std::move(stack1); + EXPECT_EQ(stack1.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(stack2.size(), 7); + for (int i = 7; i >= 1; i--) { + EXPECT_EQ(stack2.pop(), i); + } +} + +TEST(stack, CopyAssignment) +{ + Stack<int> stack1 = {1, 2, 3, 4, 5, 6, 7}; + Stack<int> stack2 = {2, 3, 4, 5, 6, 7}; + stack2 = stack1; + + EXPECT_EQ(stack1.size(), 7); + EXPECT_EQ(stack2.size(), 7); + for (int i = 7; i >= 1; i--) { + EXPECT_FALSE(stack1.is_empty()); + EXPECT_FALSE(stack2.is_empty()); + EXPECT_EQ(stack1.pop(), i); + EXPECT_EQ(stack2.pop(), i); + } + EXPECT_TRUE(stack1.is_empty()); + EXPECT_TRUE(stack2.is_empty()); +} + +TEST(stack, MoveAssignment) +{ + Stack<int> stack1 = {1, 2, 3, 4, 5, 6, 7}; + Stack<int> stack2 = {5, 3, 7, 2, 2}; + stack2 = std::move(stack1); + EXPECT_EQ(stack1.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(stack2.size(), 7); + for (int i = 7; i >= 1; i--) { + EXPECT_EQ(stack2.pop(), i); + } +} + +TEST(stack, Push) +{ + Stack<int> stack; + EXPECT_EQ(stack.size(), 0); + stack.push(3); + EXPECT_EQ(stack.size(), 1); + stack.push(5); + EXPECT_EQ(stack.size(), 2); +} + +TEST(stack, PushMultiple) +{ + Stack<int> stack; + EXPECT_EQ(stack.size(), 0); + stack.push_multiple({1, 2, 3}); + EXPECT_EQ(stack.size(), 3); + EXPECT_EQ(stack.pop(), 3); + EXPECT_EQ(stack.pop(), 2); + EXPECT_EQ(stack.pop(), 1); +} + +TEST(stack, PushPopMany) +{ + Stack<int> stack; + for (int i = 0; i < 1000; i++) { + stack.push(i); + EXPECT_EQ(stack.size(), static_cast<unsigned int>(i + 1)); + } + for (int i = 999; i > 50; i--) { + EXPECT_EQ(stack.pop(), i); + EXPECT_EQ(stack.size(), static_cast<unsigned int>(i)); + } + for (int i = 51; i < 5000; i++) { + stack.push(i); + EXPECT_EQ(stack.size(), static_cast<unsigned int>(i + 1)); + } + for (int i = 4999; i >= 0; i--) { + EXPECT_EQ(stack.pop(), i); + EXPECT_EQ(stack.size(), static_cast<unsigned int>(i)); + } +} + +TEST(stack, PushMultipleAfterPop) +{ + Stack<int> stack; + for (int i = 0; i < 1000; i++) { + stack.push(i); + } + for (int i = 999; i >= 0; i--) { + EXPECT_EQ(stack.pop(), i); + } + + Vector<int> values; + for (int i = 0; i < 5000; i++) { + values.append(i); + } + stack.push_multiple(values); + EXPECT_EQ(stack.size(), 5000); + + for (int i = 4999; i >= 0; i--) { + EXPECT_EQ(stack.pop(), i); + } +} + +TEST(stack, Pop) +{ + Stack<int> stack; + stack.push(4); + stack.push(6); + EXPECT_EQ(stack.pop(), 6); + EXPECT_EQ(stack.pop(), 4); +} + +TEST(stack, Peek) +{ + Stack<int> stack; + stack.push(3); + stack.push(4); + EXPECT_EQ(stack.peek(), 4); + EXPECT_EQ(stack.peek(), 4); + stack.pop(); + EXPECT_EQ(stack.peek(), 3); +} + +TEST(stack, UniquePtrValues) +{ + Stack<std::unique_ptr<int>> stack; + stack.push(std::unique_ptr<int>(new int())); + stack.push(std::unique_ptr<int>(new int())); + std::unique_ptr<int> a = stack.pop(); + std::unique_ptr<int> &b = stack.peek(); + UNUSED_VARS(a, b); +} + +TEST(stack, OveralignedValues) +{ + Stack<AlignedBuffer<1, 512>, 2> stack; + for (int i = 0; i < 100; i++) { + stack.push({}); + EXPECT_EQ((uintptr_t)&stack.peek() % 512, 0); + } +} + +} // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_string_ref_test.cc b/source/blender/blenlib/tests/BLI_string_ref_test.cc new file mode 100644 index 00000000000..d08c8a77455 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_string_ref_test.cc @@ -0,0 +1,277 @@ +/* Apache License, Version 2.0 */ + +#include "BLI_strict_flags.h" +#include "BLI_string_ref.hh" +#include "BLI_vector.hh" +#include "testing/testing.h" + +namespace blender::tests { + +TEST(string_ref_null, DefaultConstructor) +{ + StringRefNull ref; + EXPECT_EQ(ref.size(), 0); + EXPECT_EQ(ref[0], '\0'); +} + +TEST(string_ref_null, CStringConstructor) +{ + const char *str = "Hello"; + StringRefNull ref(str); + EXPECT_EQ(ref.size(), 5); + EXPECT_EQ(ref.data(), str); +} + +TEST(string_ref_null, CStringLengthConstructor) +{ + const char *str = "Hello"; + StringRefNull ref(str, 5); + EXPECT_EQ(ref.size(), 5); + EXPECT_EQ(ref.data(), str); +} + +TEST(string_ref, DefaultConstructor) +{ + StringRef ref; + EXPECT_EQ(ref.size(), 0); +} + +TEST(string_ref, StartEndConstructor) +{ + const char *text = "hello world"; + StringRef ref(text, text + 5); + EXPECT_EQ(ref.size(), 5); + EXPECT_TRUE(ref == "hello"); + EXPECT_FALSE(ref == "hello "); +} + +TEST(string_ref, StartEndConstructorNullptr) +{ + StringRef ref(nullptr, nullptr); + EXPECT_EQ(ref.size(), 0); + EXPECT_TRUE(ref == ""); +} + +TEST(string_ref, StartEndConstructorSame) +{ + const char *text = "hello world"; + StringRef ref(text, text); + EXPECT_EQ(ref.size(), 0); + EXPECT_TRUE(ref == ""); +} + +TEST(string_ref, CStringConstructor) +{ + const char *str = "Test"; + StringRef ref(str); + EXPECT_EQ(ref.size(), 4); + EXPECT_EQ(ref.data(), str); +} + +TEST(string_ref, PointerWithLengthConstructor) +{ + const char *str = "Test"; + StringRef ref(str, 2); + EXPECT_EQ(ref.size(), 2); + EXPECT_EQ(ref.data(), str); +} + +TEST(string_ref, StdStringConstructor) +{ + std::string str = "Test"; + StringRef ref(str); + EXPECT_EQ(ref.size(), 4); + EXPECT_EQ(ref.data(), str.data()); +} + +TEST(string_ref, SubscriptOperator) +{ + StringRef ref("hello"); + EXPECT_EQ(ref.size(), 5); + EXPECT_EQ(ref[0], 'h'); + EXPECT_EQ(ref[1], 'e'); + EXPECT_EQ(ref[2], 'l'); + EXPECT_EQ(ref[3], 'l'); + EXPECT_EQ(ref[4], 'o'); +} + +TEST(string_ref, ToStdString) +{ + StringRef ref("test"); + std::string str = ref; + EXPECT_EQ(str.size(), 4); + EXPECT_EQ(str, "test"); +} + +TEST(string_ref, Print) +{ + StringRef ref("test"); + std::stringstream ss; + ss << ref; + ss << ref; + std::string str = ss.str(); + EXPECT_EQ(str.size(), 8); + EXPECT_EQ(str, "testtest"); +} + +TEST(string_ref, Add) +{ + StringRef a("qwe"); + StringRef b("asd"); + std::string result = a + b; + EXPECT_EQ(result, "qweasd"); +} + +TEST(string_ref, AddCharPtr1) +{ + StringRef ref("test"); + std::string result = ref + "qwe"; + EXPECT_EQ(result, "testqwe"); +} + +TEST(string_ref, AddCharPtr2) +{ + StringRef ref("test"); + std::string result = "qwe" + ref; + EXPECT_EQ(result, "qwetest"); +} + +TEST(string_ref, AddString1) +{ + StringRef ref("test"); + std::string result = ref + std::string("asd"); + EXPECT_EQ(result, "testasd"); +} + +TEST(string_ref, AddString2) +{ + StringRef ref("test"); + std::string result = std::string("asd") + ref; + EXPECT_EQ(result, "asdtest"); +} + +TEST(string_ref, CompareEqual) +{ + StringRef ref1("test"); + StringRef ref2("test"); + StringRef ref3("other"); + EXPECT_TRUE(ref1 == ref2); + EXPECT_FALSE(ref1 == ref3); + EXPECT_TRUE(ref1 != ref3); + EXPECT_FALSE(ref1 != ref2); +} + +TEST(string_ref, CompareEqualCharPtr1) +{ + StringRef ref("test"); + EXPECT_TRUE(ref == "test"); + EXPECT_FALSE(ref == "other"); + EXPECT_TRUE(ref != "other"); + EXPECT_FALSE(ref != "test"); +} + +TEST(string_ref, CompareEqualCharPtr2) +{ + StringRef ref("test"); + EXPECT_TRUE("test" == ref); + EXPECT_FALSE("other" == ref); + EXPECT_TRUE(ref != "other"); + EXPECT_FALSE(ref != "test"); +} + +TEST(string_ref, CompareEqualString1) +{ + StringRef ref("test"); + EXPECT_TRUE(ref == std::string("test")); + EXPECT_FALSE(ref == std::string("other")); + EXPECT_TRUE(ref != std::string("other")); + EXPECT_FALSE(ref != std::string("test")); +} + +TEST(string_ref, CompareEqualString2) +{ + StringRef ref("test"); + EXPECT_TRUE(std::string("test") == ref); + EXPECT_FALSE(std::string("other") == ref); + EXPECT_TRUE(std::string("other") != ref); + EXPECT_FALSE(std::string("test") != ref); +} + +TEST(string_ref, Iterate) +{ + StringRef ref("test"); + Vector<char> chars; + for (char c : ref) { + chars.append(c); + } + EXPECT_EQ(chars.size(), 4); + EXPECT_EQ(chars[0], 't'); + EXPECT_EQ(chars[1], 'e'); + EXPECT_EQ(chars[2], 's'); + EXPECT_EQ(chars[3], 't'); +} + +TEST(string_ref, StartsWith) +{ + StringRef ref("test"); + EXPECT_TRUE(ref.startswith("")); + EXPECT_TRUE(ref.startswith("t")); + EXPECT_TRUE(ref.startswith("te")); + EXPECT_TRUE(ref.startswith("tes")); + EXPECT_TRUE(ref.startswith("test")); + EXPECT_FALSE(ref.startswith("test ")); + EXPECT_FALSE(ref.startswith("a")); +} + +TEST(string_ref, EndsWith) +{ + StringRef ref("test"); + EXPECT_TRUE(ref.endswith("")); + EXPECT_TRUE(ref.endswith("t")); + EXPECT_TRUE(ref.endswith("st")); + EXPECT_TRUE(ref.endswith("est")); + EXPECT_TRUE(ref.endswith("test")); + EXPECT_FALSE(ref.endswith(" test")); + EXPECT_FALSE(ref.endswith("a")); +} + +TEST(string_ref, DropPrefixN) +{ + StringRef ref("test"); + StringRef ref2 = ref.drop_prefix(2); + StringRef ref3 = ref2.drop_prefix(2); + EXPECT_EQ(ref2.size(), 2); + EXPECT_EQ(ref3.size(), 0); + EXPECT_EQ(ref2, "st"); + EXPECT_EQ(ref3, ""); +} + +TEST(string_ref, DropPrefix) +{ + StringRef ref("test"); + StringRef ref2 = ref.drop_prefix("tes"); + EXPECT_EQ(ref2.size(), 1); + EXPECT_EQ(ref2, "t"); +} + +TEST(string_ref, Substr) +{ + StringRef ref("hello world"); + EXPECT_EQ(ref.substr(0, 5), "hello"); + EXPECT_EQ(ref.substr(4, 0), ""); + EXPECT_EQ(ref.substr(3, 4), "lo w"); + EXPECT_EQ(ref.substr(6, 5), "world"); +} + +TEST(string_ref, Copy) +{ + StringRef ref("hello"); + char dst[10]; + memset(dst, 0xFF, 10); + ref.copy(dst); + EXPECT_EQ(dst[5], '\0'); + EXPECT_EQ(dst[6], 0xFF); + EXPECT_EQ(ref, dst); +} + +} // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_vector_set_test.cc b/source/blender/blenlib/tests/BLI_vector_set_test.cc new file mode 100644 index 00000000000..8f3db8d8403 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_vector_set_test.cc @@ -0,0 +1,164 @@ +/* Apache License, Version 2.0 */ + +#include "BLI_strict_flags.h" +#include "BLI_vector_set.hh" +#include "testing/testing.h" + +namespace blender::tests { + +TEST(vector_set, DefaultConstructor) +{ + VectorSet<int> set; + EXPECT_EQ(set.size(), 0); + EXPECT_TRUE(set.is_empty()); +} + +TEST(vector_set, InitializerListConstructor_WithoutDuplicates) +{ + VectorSet<int> set = {1, 4, 5}; + EXPECT_EQ(set.size(), 3); + EXPECT_EQ(set[0], 1); + EXPECT_EQ(set[1], 4); + EXPECT_EQ(set[2], 5); +} + +TEST(vector_set, InitializerListConstructor_WithDuplicates) +{ + VectorSet<int> set = {1, 3, 3, 2, 1, 5}; + EXPECT_EQ(set.size(), 4); + EXPECT_EQ(set[0], 1); + EXPECT_EQ(set[1], 3); + EXPECT_EQ(set[2], 2); + EXPECT_EQ(set[3], 5); +} + +TEST(vector_set, Copy) +{ + VectorSet<int> set1 = {1, 2, 3}; + VectorSet<int> set2 = set1; + EXPECT_EQ(set1.size(), 3); + EXPECT_EQ(set2.size(), 3); + EXPECT_EQ(set1.index_of(2), 1); + EXPECT_EQ(set2.index_of(2), 1); +} + +TEST(vector_set, CopyAssignment) +{ + VectorSet<int> set1 = {1, 2, 3}; + VectorSet<int> set2 = {}; + set2 = set1; + EXPECT_EQ(set1.size(), 3); + EXPECT_EQ(set2.size(), 3); + EXPECT_EQ(set1.index_of(2), 1); + EXPECT_EQ(set2.index_of(2), 1); +} + +TEST(vector_set, Move) +{ + VectorSet<int> set1 = {1, 2, 3}; + VectorSet<int> set2 = std::move(set1); + EXPECT_EQ(set1.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(set2.size(), 3); +} + +TEST(vector_set, MoveAssignment) +{ + VectorSet<int> set1 = {1, 2, 3}; + VectorSet<int> set2 = {}; + set2 = std::move(set1); + EXPECT_EQ(set1.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(set2.size(), 3); +} + +TEST(vector_set, AddNewIncreasesSize) +{ + VectorSet<int> set; + EXPECT_TRUE(set.is_empty()); + EXPECT_EQ(set.size(), 0); + set.add(5); + EXPECT_FALSE(set.is_empty()); + EXPECT_EQ(set.size(), 1); +} + +TEST(vector_set, AddExistingDoesNotIncreaseSize) +{ + VectorSet<int> set; + EXPECT_EQ(set.size(), 0); + EXPECT_TRUE(set.add(5)); + EXPECT_EQ(set.size(), 1); + EXPECT_FALSE(set.add(5)); + EXPECT_EQ(set.size(), 1); +} + +TEST(vector_set, Index) +{ + VectorSet<int> set = {3, 6, 4}; + EXPECT_EQ(set.index_of(6), 1); + EXPECT_EQ(set.index_of(3), 0); + EXPECT_EQ(set.index_of(4), 2); +} + +TEST(vector_set, IndexTry) +{ + VectorSet<int> set = {3, 6, 4}; + EXPECT_EQ(set.index_of_try(5), -1); + EXPECT_EQ(set.index_of_try(3), 0); + EXPECT_EQ(set.index_of_try(6), 1); + EXPECT_EQ(set.index_of_try(2), -1); +} + +TEST(vector_set, RemoveContained) +{ + VectorSet<int> set = {4, 5, 6, 7}; + EXPECT_EQ(set.size(), 4); + set.remove_contained(5); + EXPECT_EQ(set.size(), 3); + EXPECT_EQ(set[0], 4); + EXPECT_EQ(set[1], 7); + EXPECT_EQ(set[2], 6); + set.remove_contained(6); + EXPECT_EQ(set.size(), 2); + EXPECT_EQ(set[0], 4); + EXPECT_EQ(set[1], 7); + set.remove_contained(4); + EXPECT_EQ(set.size(), 1); + EXPECT_EQ(set[0], 7); + set.remove_contained(7); + EXPECT_EQ(set.size(), 0); +} + +TEST(vector_set, AddMultipleTimes) +{ + VectorSet<int> set; + for (int i = 0; i < 100; i++) { + EXPECT_FALSE(set.contains(i * 13)); + set.add(i * 12); + set.add(i * 13); + EXPECT_TRUE(set.contains(i * 13)); + } +} + +TEST(vector_set, UniquePtrValue) +{ + VectorSet<std::unique_ptr<int>> set; + set.add_new(std::unique_ptr<int>(new int())); + set.add(std::unique_ptr<int>(new int())); + set.index_of_try(std::unique_ptr<int>(new int())); + std::unique_ptr<int> value = set.pop(); + UNUSED_VARS(value); +} + +TEST(vector_set, Remove) +{ + VectorSet<int> set; + EXPECT_TRUE(set.add(5)); + EXPECT_TRUE(set.contains(5)); + EXPECT_FALSE(set.remove(6)); + EXPECT_TRUE(set.contains(5)); + EXPECT_TRUE(set.remove(5)); + EXPECT_FALSE(set.contains(5)); + EXPECT_FALSE(set.remove(5)); + EXPECT_FALSE(set.contains(5)); +} + +} // namespace blender::tests diff --git a/source/blender/blenlib/tests/BLI_vector_test.cc b/source/blender/blenlib/tests/BLI_vector_test.cc new file mode 100644 index 00000000000..f72dfc5deb8 --- /dev/null +++ b/source/blender/blenlib/tests/BLI_vector_test.cc @@ -0,0 +1,639 @@ +/* Apache License, Version 2.0 */ + +#include "BLI_strict_flags.h" +#include "BLI_vector.hh" +#include "testing/testing.h" +#include <forward_list> + +namespace blender::tests { + +TEST(vector, DefaultConstructor) +{ + Vector<int> vec; + EXPECT_EQ(vec.size(), 0); +} + +TEST(vector, SizeConstructor) +{ + Vector<int> vec(3); + EXPECT_EQ(vec.size(), 3); +} + +/** + * Tests that the trivially constructible types are not zero-initialized. We do not want that for + * performance reasons. + */ +TEST(vector, TrivialTypeSizeConstructor) +{ + Vector<char, 1> *vec = new Vector<char, 1>(1); + char *ptr = &(*vec)[0]; + vec->~Vector(); + + const char magic = 42; + *ptr = magic; + EXPECT_EQ(*ptr, magic); + + new (vec) Vector<char, 1>(1); + EXPECT_EQ((*vec)[0], magic); + EXPECT_EQ(*ptr, magic); + delete vec; +} + +TEST(vector, SizeValueConstructor) +{ + Vector<int> vec(4, 10); + EXPECT_EQ(vec.size(), 4); + EXPECT_EQ(vec[0], 10); + EXPECT_EQ(vec[1], 10); + EXPECT_EQ(vec[2], 10); + EXPECT_EQ(vec[3], 10); +} + +TEST(vector, InitializerListConstructor) +{ + Vector<int> vec = {1, 3, 4, 6}; + EXPECT_EQ(vec.size(), 4); + EXPECT_EQ(vec[0], 1); + EXPECT_EQ(vec[1], 3); + EXPECT_EQ(vec[2], 4); + EXPECT_EQ(vec[3], 6); +} + +TEST(vector, ConvertingConstructor) +{ + std::array<float, 5> values = {5.4f, 7.3f, -8.1f, 5.0f, 0.0f}; + Vector<int> vec = values; + EXPECT_EQ(vec.size(), 5); + EXPECT_EQ(vec[0], 5); + EXPECT_EQ(vec[1], 7); + EXPECT_EQ(vec[2], -8); + EXPECT_EQ(vec[3], 5); + EXPECT_EQ(vec[4], 0); +} + +struct TestListValue { + TestListValue *next, *prev; + int value; +}; + +TEST(vector, ListBaseConstructor) +{ + TestListValue *value1 = new TestListValue{0, 0, 4}; + TestListValue *value2 = new TestListValue{0, 0, 5}; + TestListValue *value3 = new TestListValue{0, 0, 6}; + + ListBase list = {NULL, NULL}; + BLI_addtail(&list, value1); + BLI_addtail(&list, value2); + BLI_addtail(&list, value3); + Vector<TestListValue *> vec(list); + + EXPECT_EQ(vec.size(), 3); + EXPECT_EQ(vec[0]->value, 4); + EXPECT_EQ(vec[1]->value, 5); + EXPECT_EQ(vec[2]->value, 6); + + delete value1; + delete value2; + delete value3; +} + +TEST(vector, ContainerConstructor) +{ + std::forward_list<int> list; + list.push_front(3); + list.push_front(1); + list.push_front(5); + + Vector<int> vec = Vector<int>::FromContainer(list); + EXPECT_EQ(vec.size(), 3); + EXPECT_EQ(vec[0], 5); + EXPECT_EQ(vec[1], 1); + EXPECT_EQ(vec[2], 3); +} + +TEST(vector, CopyConstructor) +{ + Vector<int> vec1 = {1, 2, 3}; + Vector<int> vec2(vec1); + EXPECT_EQ(vec2.size(), 3); + EXPECT_EQ(vec2[0], 1); + EXPECT_EQ(vec2[1], 2); + EXPECT_EQ(vec2[2], 3); + + vec1[1] = 5; + EXPECT_EQ(vec1[1], 5); + EXPECT_EQ(vec2[1], 2); +} + +TEST(vector, CopyConstructor2) +{ + Vector<int, 2> vec1 = {1, 2, 3, 4}; + Vector<int, 3> vec2(vec1); + + EXPECT_EQ(vec1.size(), 4); + EXPECT_EQ(vec2.size(), 4); + EXPECT_NE(vec1.data(), vec2.data()); + EXPECT_EQ(vec2[0], 1); + EXPECT_EQ(vec2[1], 2); + EXPECT_EQ(vec2[2], 3); + EXPECT_EQ(vec2[3], 4); +} + +TEST(vector, CopyConstructor3) +{ + Vector<int, 20> vec1 = {1, 2, 3, 4}; + Vector<int, 1> vec2(vec1); + + EXPECT_EQ(vec1.size(), 4); + EXPECT_EQ(vec2.size(), 4); + EXPECT_NE(vec1.data(), vec2.data()); + EXPECT_EQ(vec2[2], 3); +} + +TEST(vector, CopyConstructor4) +{ + Vector<int, 5> vec1 = {1, 2, 3, 4}; + Vector<int, 6> vec2(vec1); + + EXPECT_EQ(vec1.size(), 4); + EXPECT_EQ(vec2.size(), 4); + EXPECT_NE(vec1.data(), vec2.data()); + EXPECT_EQ(vec2[3], 4); +} + +TEST(vector, MoveConstructor) +{ + Vector<int> vec1 = {1, 2, 3, 4}; + Vector<int> vec2(std::move(vec1)); + + EXPECT_EQ(vec1.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(vec2.size(), 4); + EXPECT_EQ(vec2[0], 1); + EXPECT_EQ(vec2[1], 2); + EXPECT_EQ(vec2[2], 3); + EXPECT_EQ(vec2[3], 4); +} + +TEST(vector, MoveConstructor2) +{ + Vector<int, 2> vec1 = {1, 2, 3, 4}; + Vector<int, 3> vec2(std::move(vec1)); + + EXPECT_EQ(vec1.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(vec2.size(), 4); + EXPECT_EQ(vec2[0], 1); + EXPECT_EQ(vec2[1], 2); + EXPECT_EQ(vec2[2], 3); + EXPECT_EQ(vec2[3], 4); +} + +TEST(vector, MoveConstructor3) +{ + Vector<int, 20> vec1 = {1, 2, 3, 4}; + Vector<int, 1> vec2(std::move(vec1)); + + EXPECT_EQ(vec1.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(vec2.size(), 4); + EXPECT_EQ(vec2[2], 3); +} + +TEST(vector, MoveConstructor4) +{ + Vector<int, 5> vec1 = {1, 2, 3, 4}; + Vector<int, 6> vec2(std::move(vec1)); + + EXPECT_EQ(vec1.size(), 0); /* NOLINT: bugprone-use-after-move */ + EXPECT_EQ(vec2.size(), 4); + EXPECT_EQ(vec2[3], 4); +} + +TEST(vector, MoveAssignment) +{ + Vector<int> vec = {1, 2}; + EXPECT_EQ(vec.size(), 2); + EXPECT_EQ(vec[0], 1); + EXPECT_EQ(vec[1], 2); + + vec = Vector<int>({5}); + EXPECT_EQ(vec.size(), 1); + EXPECT_EQ(vec[0], 5); +} + +TEST(vector, CopyAssignment) +{ + Vector<int> vec1 = {1, 2, 3}; + Vector<int> vec2 = {4, 5}; + EXPECT_EQ(vec1.size(), 3); + EXPECT_EQ(vec2.size(), 2); + + vec2 = vec1; + EXPECT_EQ(vec2.size(), 3); + + vec1[0] = 7; + EXPECT_EQ(vec1[0], 7); + EXPECT_EQ(vec2[0], 1); +} + +TEST(vector, Append) +{ + Vector<int> vec; + vec.append(3); + vec.append(6); + vec.append(7); + EXPECT_EQ(vec.size(), 3); + EXPECT_EQ(vec[0], 3); + EXPECT_EQ(vec[1], 6); + EXPECT_EQ(vec[2], 7); +} + +TEST(vector, AppendAndGetIndex) +{ + Vector<int> vec; + EXPECT_EQ(vec.append_and_get_index(10), 0); + EXPECT_EQ(vec.append_and_get_index(10), 1); + EXPECT_EQ(vec.append_and_get_index(10), 2); + vec.append(10); + EXPECT_EQ(vec.append_and_get_index(10), 4); +} + +TEST(vector, AppendNonDuplicates) +{ + Vector<int> vec; + vec.append_non_duplicates(4); + EXPECT_EQ(vec.size(), 1); + vec.append_non_duplicates(5); + EXPECT_EQ(vec.size(), 2); + vec.append_non_duplicates(4); + EXPECT_EQ(vec.size(), 2); +} + +TEST(vector, ExtendNonDuplicates) +{ + Vector<int> vec; + vec.extend_non_duplicates({1, 2}); + EXPECT_EQ(vec.size(), 2); + vec.extend_non_duplicates({3, 4}); + EXPECT_EQ(vec.size(), 4); + vec.extend_non_duplicates({0, 1, 2, 3}); + EXPECT_EQ(vec.size(), 5); +} + +TEST(vector, Iterator) +{ + Vector<int> vec({1, 4, 9, 16}); + int i = 1; + for (int value : vec) { + EXPECT_EQ(value, i * i); + i++; + } +} + +TEST(vector, BecomeLarge) +{ + Vector<int, 4> vec; + for (int i = 0; i < 100; i++) { + vec.append(i * 5); + } + EXPECT_EQ(vec.size(), 100); + for (int i = 0; i < 100; i++) { + EXPECT_EQ(vec[i], static_cast<int>(i * 5)); + } +} + +static Vector<int> return_by_value_helper() +{ + return Vector<int>({3, 5, 1}); +} + +TEST(vector, ReturnByValue) +{ + Vector<int> vec = return_by_value_helper(); + EXPECT_EQ(vec.size(), 3); + EXPECT_EQ(vec[0], 3); + EXPECT_EQ(vec[1], 5); + EXPECT_EQ(vec[2], 1); +} + +TEST(vector, VectorOfVectors_Append) +{ + Vector<Vector<int>> vec; + EXPECT_EQ(vec.size(), 0); + + Vector<int> v({1, 2}); + vec.append(v); + vec.append({7, 8}); + EXPECT_EQ(vec.size(), 2); + EXPECT_EQ(vec[0][0], 1); + EXPECT_EQ(vec[0][1], 2); + EXPECT_EQ(vec[1][0], 7); + EXPECT_EQ(vec[1][1], 8); +} + +TEST(vector, RemoveLast) +{ + Vector<int> vec = {5, 6}; + EXPECT_EQ(vec.size(), 2); + vec.remove_last(); + EXPECT_EQ(vec.size(), 1); + vec.remove_last(); + EXPECT_EQ(vec.size(), 0); +} + +TEST(vector, IsEmpty) +{ + Vector<int> vec; + EXPECT_TRUE(vec.is_empty()); + vec.append(1); + EXPECT_FALSE(vec.is_empty()); + vec.remove_last(); + EXPECT_TRUE(vec.is_empty()); +} + +TEST(vector, RemoveReorder) +{ + Vector<int> vec = {4, 5, 6, 7}; + vec.remove_and_reorder(1); + EXPECT_EQ(vec[0], 4); + EXPECT_EQ(vec[1], 7); + EXPECT_EQ(vec[2], 6); + vec.remove_and_reorder(2); + EXPECT_EQ(vec[0], 4); + EXPECT_EQ(vec[1], 7); + vec.remove_and_reorder(0); + EXPECT_EQ(vec[0], 7); + vec.remove_and_reorder(0); + EXPECT_TRUE(vec.is_empty()); +} + +TEST(vector, RemoveFirstOccurrenceAndReorder) +{ + Vector<int> vec = {4, 5, 6, 7}; + vec.remove_first_occurrence_and_reorder(5); + EXPECT_EQ(vec[0], 4); + EXPECT_EQ(vec[1], 7); + EXPECT_EQ(vec[2], 6); + vec.remove_first_occurrence_and_reorder(6); + EXPECT_EQ(vec[0], 4); + EXPECT_EQ(vec[1], 7); + vec.remove_first_occurrence_and_reorder(4); + EXPECT_EQ(vec[0], 7); + vec.remove_first_occurrence_and_reorder(7); + EXPECT_EQ(vec.size(), 0); +} + +TEST(vector, Remove) +{ + Vector<int> vec = {1, 2, 3, 4, 5, 6}; + vec.remove(3); + EXPECT_TRUE(std::equal(vec.begin(), vec.end(), Span<int>({1, 2, 3, 5, 6}).begin())); + vec.remove(0); + EXPECT_TRUE(std::equal(vec.begin(), vec.end(), Span<int>({2, 3, 5, 6}).begin())); + vec.remove(3); + EXPECT_TRUE(std::equal(vec.begin(), vec.end(), Span<int>({2, 3, 5}).begin())); + vec.remove(1); + EXPECT_TRUE(std::equal(vec.begin(), vec.end(), Span<int>({2, 5}).begin())); + vec.remove(1); + EXPECT_TRUE(std::equal(vec.begin(), vec.end(), Span<int>({2}).begin())); + vec.remove(0); + EXPECT_TRUE(std::equal(vec.begin(), vec.end(), Span<int>({}).begin())); +} + +TEST(vector, ExtendSmallVector) +{ + Vector<int> a = {2, 3, 4}; + Vector<int> b = {11, 12}; + b.extend(a); + EXPECT_EQ(b.size(), 5); + EXPECT_EQ(b[0], 11); + EXPECT_EQ(b[1], 12); + EXPECT_EQ(b[2], 2); + EXPECT_EQ(b[3], 3); + EXPECT_EQ(b[4], 4); +} + +TEST(vector, ExtendArray) +{ + int array[] = {3, 4, 5, 6}; + + Vector<int> a; + a.extend(array, 2); + + EXPECT_EQ(a.size(), 2); + EXPECT_EQ(a[0], 3); + EXPECT_EQ(a[1], 4); +} + +TEST(vector, Last) +{ + Vector<int> a{3, 5, 7}; + EXPECT_EQ(a.last(), 7); +} + +TEST(vector, AppendNTimes) +{ + Vector<int> a; + a.append_n_times(5, 3); + a.append_n_times(2, 2); + EXPECT_EQ(a.size(), 5); + EXPECT_EQ(a[0], 5); + EXPECT_EQ(a[1], 5); + EXPECT_EQ(a[2], 5); + EXPECT_EQ(a[3], 2); + EXPECT_EQ(a[4], 2); +} + +TEST(vector, UniquePtrValue) +{ + Vector<std::unique_ptr<int>> vec; + vec.append(std::unique_ptr<int>(new int())); + vec.append(std::unique_ptr<int>(new int())); + vec.append(std::unique_ptr<int>(new int())); + vec.append(std::unique_ptr<int>(new int())); + EXPECT_EQ(vec.size(), 4); + + std::unique_ptr<int> &a = vec.last(); + std::unique_ptr<int> b = vec.pop_last(); + vec.remove_and_reorder(0); + vec.remove(0); + EXPECT_EQ(vec.size(), 1); + + UNUSED_VARS(a, b); +} + +class TypeConstructMock { + public: + bool default_constructed = false; + bool copy_constructed = false; + bool move_constructed = false; + bool copy_assigned = false; + bool move_assigned = false; + + TypeConstructMock() : default_constructed(true) + { + } + + TypeConstructMock(const TypeConstructMock &UNUSED(other)) : copy_constructed(true) + { + } + + TypeConstructMock(TypeConstructMock &&UNUSED(other)) noexcept : move_constructed(true) + { + } + + TypeConstructMock &operator=(const TypeConstructMock &other) + { + if (this == &other) { + return *this; + } + + copy_assigned = true; + return *this; + } + + TypeConstructMock &operator=(TypeConstructMock &&other) noexcept + { + if (this == &other) { + return *this; + } + + move_assigned = true; + return *this; + } +}; + +TEST(vector, SizeConstructorCallsDefaultConstructor) +{ + Vector<TypeConstructMock> vec(3); + EXPECT_TRUE(vec[0].default_constructed); + EXPECT_TRUE(vec[1].default_constructed); + EXPECT_TRUE(vec[2].default_constructed); +} + +TEST(vector, SizeValueConstructorCallsCopyConstructor) +{ + Vector<TypeConstructMock> vec(3, TypeConstructMock()); + EXPECT_TRUE(vec[0].copy_constructed); + EXPECT_TRUE(vec[1].copy_constructed); + EXPECT_TRUE(vec[2].copy_constructed); +} + +TEST(vector, AppendCallsCopyConstructor) +{ + Vector<TypeConstructMock> vec; + TypeConstructMock value; + vec.append(value); + EXPECT_TRUE(vec[0].copy_constructed); +} + +TEST(vector, AppendCallsMoveConstructor) +{ + Vector<TypeConstructMock> vec; + vec.append(TypeConstructMock()); + EXPECT_TRUE(vec[0].move_constructed); +} + +TEST(vector, SmallVectorCopyCallsCopyConstructor) +{ + Vector<TypeConstructMock, 2> src(2); + Vector<TypeConstructMock, 2> dst(src); + EXPECT_TRUE(dst[0].copy_constructed); + EXPECT_TRUE(dst[1].copy_constructed); +} + +TEST(vector, LargeVectorCopyCallsCopyConstructor) +{ + Vector<TypeConstructMock, 2> src(5); + Vector<TypeConstructMock, 2> dst(src); + EXPECT_TRUE(dst[0].copy_constructed); + EXPECT_TRUE(dst[1].copy_constructed); +} + +TEST(vector, SmallVectorMoveCallsMoveConstructor) +{ + Vector<TypeConstructMock, 2> src(2); + Vector<TypeConstructMock, 2> dst(std::move(src)); + EXPECT_TRUE(dst[0].move_constructed); + EXPECT_TRUE(dst[1].move_constructed); +} + +TEST(vector, LargeVectorMoveCallsNoConstructor) +{ + Vector<TypeConstructMock, 2> src(5); + Vector<TypeConstructMock, 2> dst(std::move(src)); + + EXPECT_TRUE(dst[0].default_constructed); + EXPECT_FALSE(dst[0].move_constructed); + EXPECT_FALSE(dst[0].copy_constructed); +} + +TEST(vector, Resize) +{ + std::string long_string = "012345678901234567890123456789"; + Vector<std::string> vec; + EXPECT_EQ(vec.size(), 0); + vec.resize(2); + EXPECT_EQ(vec.size(), 2); + EXPECT_EQ(vec[0], ""); + EXPECT_EQ(vec[1], ""); + vec.resize(5, long_string); + EXPECT_EQ(vec.size(), 5); + EXPECT_EQ(vec[0], ""); + EXPECT_EQ(vec[1], ""); + EXPECT_EQ(vec[2], long_string); + EXPECT_EQ(vec[3], long_string); + EXPECT_EQ(vec[4], long_string); + vec.resize(1); + EXPECT_EQ(vec.size(), 1); + EXPECT_EQ(vec[0], ""); +} + +TEST(vector, FirstIndexOf) +{ + Vector<int> vec = {2, 3, 5, 7, 5, 9}; + EXPECT_EQ(vec.first_index_of(2), 0); + EXPECT_EQ(vec.first_index_of(5), 2); + EXPECT_EQ(vec.first_index_of(9), 5); +} + +TEST(vector, FirstIndexTryOf) +{ + Vector<int> vec = {2, 3, 5, 7, 5, 9}; + EXPECT_EQ(vec.first_index_of_try(2), 0); + EXPECT_EQ(vec.first_index_of_try(4), -1); + EXPECT_EQ(vec.first_index_of_try(5), 2); + EXPECT_EQ(vec.first_index_of_try(9), 5); + EXPECT_EQ(vec.first_index_of_try(1), -1); +} + +TEST(vector, OveralignedValues) +{ + Vector<AlignedBuffer<1, 512>, 2> vec; + for (int i = 0; i < 100; i++) { + vec.append({}); + EXPECT_EQ((uintptr_t)&vec.last() % 512, 0); + } +} + +TEST(vector, ConstructVoidPointerVector) +{ + int a; + float b; + double c; + Vector<void *> vec = {&a, &b, &c}; + EXPECT_EQ(vec.size(), 3); +} + +TEST(vector, Fill) +{ + Vector<int> vec(5); + vec.fill(3); + EXPECT_EQ(vec.size(), 5u); + EXPECT_EQ(vec[0], 3); + EXPECT_EQ(vec[1], 3); + EXPECT_EQ(vec[2], 3); + EXPECT_EQ(vec[3], 3); + EXPECT_EQ(vec[4], 3); +} + +} // namespace blender::tests |