diff options
Diffstat (limited to 'source/blender/blenlib/tests')
16 files changed, 3963 insertions, 0 deletions
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 |