From d8678e02ecec9375bec1dcf1388c6fc8b4ce3ad2 Mon Sep 17 00:00:00 2001
From: Jacques Lucke <jacques@blender.org>
Date: Tue, 9 Jun 2020 10:10:56 +0200
Subject: BLI: generally improve C++ data structures

The main focus here was to improve the docs significantly. Furthermore,
I reimplemented `Set`, `Map` and `VectorSet`. They are now (usually)
faster, simpler and more customizable. I also rewrote `Stack` to make
it more efficient by avoiding unnecessary copies.

Thanks to everyone who helped with constructive feedback.

Approved by brecht and sybren.

Differential Revision: https://developer.blender.org/D7931
---
 tests/gtests/blenlib/BLI_array_ref_test.cc        |  40 +--
 tests/gtests/blenlib/BLI_array_test.cc            |  27 +-
 tests/gtests/blenlib/BLI_index_range_test.cc      |  17 +-
 tests/gtests/blenlib/BLI_linear_allocator_test.cc |   5 +-
 tests/gtests/blenlib/BLI_map_test.cc              | 261 ++++++++++++---
 tests/gtests/blenlib/BLI_math_bits_test.cc        |  48 +++
 tests/gtests/blenlib/BLI_optional_test.cc         |  15 +-
 tests/gtests/blenlib/BLI_set_test.cc              | 387 +++++++++++++++++++---
 tests/gtests/blenlib/BLI_stack_cxx_test.cc        | 126 ++++++-
 tests/gtests/blenlib/BLI_string_map_test.cc       | 275 ---------------
 tests/gtests/blenlib/BLI_string_ref_test.cc       |   1 +
 tests/gtests/blenlib/BLI_type_construct_mock.hh   |  63 ----
 tests/gtests/blenlib/BLI_vector_set_test.cc       |  96 ++++--
 tests/gtests/blenlib/BLI_vector_test.cc           | 155 +++++++--
 tests/gtests/blenlib/CMakeLists.txt               |   2 +-
 15 files changed, 974 insertions(+), 544 deletions(-)
 create mode 100644 tests/gtests/blenlib/BLI_math_bits_test.cc
 delete mode 100644 tests/gtests/blenlib/BLI_string_map_test.cc
 delete mode 100644 tests/gtests/blenlib/BLI_type_construct_mock.hh

(limited to 'tests')

diff --git a/tests/gtests/blenlib/BLI_array_ref_test.cc b/tests/gtests/blenlib/BLI_array_ref_test.cc
index 7a1f54e7458..48137f32197 100644
--- a/tests/gtests/blenlib/BLI_array_ref_test.cc
+++ b/tests/gtests/blenlib/BLI_array_ref_test.cc
@@ -1,4 +1,5 @@
 #include "BLI_array_ref.hh"
+#include "BLI_strict_flags.h"
 #include "BLI_vector.hh"
 #include "testing/testing.h"
 
@@ -136,14 +137,6 @@ TEST(array_ref, Count)
   EXPECT_EQ(a_ref.count(5), 0);
 }
 
-TEST(array_ref, ToSmallVector)
-{
-  IntVector a = {1, 2, 3, 4};
-  IntArrayRef a_ref = a;
-  IntVector b = a_ref;
-  IntVector::all_equal(a, b);
-}
-
 static void test_ref_from_initializer_list(IntArrayRef ref)
 {
   EXPECT_EQ(ref.size(), 4);
@@ -202,37 +195,12 @@ TEST(array_ref, FillIndices)
   EXPECT_EQ(a[4], 0);
 }
 
-TEST(array_ref, CopyFrom)
-{
-  std::array<int, 3> a = {3, 4, 5};
-  MutableIntArrayRef a_ref(a);
-  EXPECT_EQ(a[0], 3);
-  EXPECT_EQ(a[1], 4);
-  EXPECT_EQ(a[2], 5);
-  a_ref.copy_from({1, 2, 3});
-  EXPECT_EQ(a[0], 1);
-  EXPECT_EQ(a[1], 2);
-  EXPECT_EQ(a[2], 3);
-}
-
-TEST(array_ref, ByteSize)
+TEST(array_ref, SizeInBytes)
 {
   std::array<int, 10> a;
   IntArrayRef a_ref(a);
-  EXPECT_EQ(a_ref.byte_size(), sizeof(a));
-  EXPECT_EQ(a_ref.byte_size(), 40);
-}
-
-TEST(array_ref, CopyTo)
-{
-  std::array<int, 3> a = {5, 6, 7};
-  int b[3] = {0};
-  IntArrayRef a_ref(a);
-  a_ref.copy_to(b);
-
-  EXPECT_EQ(b[0], 5);
-  EXPECT_EQ(b[1], 6);
-  EXPECT_EQ(b[2], 7);
+  EXPECT_EQ(a_ref.size_in_bytes(), sizeof(a));
+  EXPECT_EQ(a_ref.size_in_bytes(), 40);
 }
 
 TEST(array_ref, FirstLast)
diff --git a/tests/gtests/blenlib/BLI_array_test.cc b/tests/gtests/blenlib/BLI_array_test.cc
index b1aa24aa808..66f69f5c309 100644
--- a/tests/gtests/blenlib/BLI_array_test.cc
+++ b/tests/gtests/blenlib/BLI_array_test.cc
@@ -1,4 +1,5 @@
 #include "BLI_array.hh"
+#include "BLI_strict_flags.h"
 #include "testing/testing.h"
 
 using namespace BLI;
@@ -7,12 +8,14 @@ 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)
@@ -55,7 +58,7 @@ TEST(array, CopyConstructor)
 
   EXPECT_EQ(array.size(), 4);
   EXPECT_EQ(new_array.size(), 4);
-  EXPECT_NE(array.begin(), new_array.begin());
+  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);
@@ -83,7 +86,7 @@ TEST(array, CopyAssignment)
   new_array = array;
   EXPECT_EQ(new_array.size(), 3);
   EXPECT_EQ(array.size(), 3);
-  EXPECT_NE(array.begin(), new_array.begin());
+  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);
@@ -101,3 +104,23 @@ TEST(array, MoveAssignment)
   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;
+}
diff --git a/tests/gtests/blenlib/BLI_index_range_test.cc b/tests/gtests/blenlib/BLI_index_range_test.cc
index b12502f0d97..8ee0f485ffe 100644
--- a/tests/gtests/blenlib/BLI_index_range_test.cc
+++ b/tests/gtests/blenlib/BLI_index_range_test.cc
@@ -1,18 +1,17 @@
 #include "BLI_index_range.hh"
+#include "BLI_strict_flags.h"
 #include "BLI_vector.hh"
 #include "testing/testing.h"
 
-using BLI::ArrayRef;
-using BLI::IndexRange;
-using IntVector = BLI::Vector<int>;
+using namespace BLI;
 
 TEST(index_range, DefaultConstructor)
 {
   IndexRange range;
   EXPECT_EQ(range.size(), 0);
 
-  IntVector vector;
-  for (int value : range) {
+  Vector<uint> vector;
+  for (uint value : range) {
     vector.append(value);
   }
   EXPECT_EQ(vector.size(), 0);
@@ -24,8 +23,8 @@ TEST(index_range, SingleElementRange)
   EXPECT_EQ(range.size(), 1);
   EXPECT_EQ(*range.begin(), 4);
 
-  IntVector vector;
-  for (int value : range) {
+  Vector<uint> vector;
+  for (uint value : range) {
     vector.append(value);
   }
 
@@ -38,8 +37,8 @@ TEST(index_range, MultipleElementRange)
   IndexRange range(6, 4);
   EXPECT_EQ(range.size(), 4);
 
-  IntVector vector;
-  for (int value : range) {
+  Vector<uint> vector;
+  for (uint value : range) {
     vector.append(value);
   }
 
diff --git a/tests/gtests/blenlib/BLI_linear_allocator_test.cc b/tests/gtests/blenlib/BLI_linear_allocator_test.cc
index 0c67d1e76c9..6cac60dea3b 100644
--- a/tests/gtests/blenlib/BLI_linear_allocator_test.cc
+++ b/tests/gtests/blenlib/BLI_linear_allocator_test.cc
@@ -1,11 +1,12 @@
 #include "BLI_linear_allocator.hh"
+#include "BLI_strict_flags.h"
 #include "testing/testing.h"
 
 using namespace BLI;
 
 static bool is_aligned(void *ptr, uint alignment)
 {
-  BLI_assert(is_power_of_2_i(alignment));
+  BLI_assert(is_power_of_2_i((int)alignment));
   return (POINTER_AS_UINT(ptr) & (alignment - 1)) == 0;
 }
 
@@ -105,7 +106,7 @@ TEST(linear_allocator, ConstructArrayCopy)
   Vector<int> values = {1, 2, 3};
   MutableArrayRef<int> array1 = allocator.construct_array_copy(values.as_ref());
   MutableArrayRef<int> array2 = allocator.construct_array_copy(values.as_ref());
-  EXPECT_NE(array1.begin(), array2.begin());
+  EXPECT_NE(array1.data(), array2.data());
   EXPECT_EQ(array1.size(), 3);
   EXPECT_EQ(array2.size(), 3);
   EXPECT_EQ(array1[1], 2);
diff --git a/tests/gtests/blenlib/BLI_map_test.cc b/tests/gtests/blenlib/BLI_map_test.cc
index 5a19216fa7c..990683dcfc5 100644
--- a/tests/gtests/blenlib/BLI_map_test.cc
+++ b/tests/gtests/blenlib/BLI_map_test.cc
@@ -1,20 +1,23 @@
 #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"
 
-using BLI::Map;
-using IntFloatMap = Map<int, float>;
+using namespace BLI;
 
 TEST(map, DefaultConstructor)
 {
-  IntFloatMap map;
+  Map<int, float> map;
   EXPECT_EQ(map.size(), 0);
   EXPECT_TRUE(map.is_empty());
 }
 
 TEST(map, AddIncreasesSize)
 {
-  IntFloatMap map;
+  Map<int, float> map;
   EXPECT_EQ(map.size(), 0);
   EXPECT_TRUE(map.is_empty());
   map.add(2, 5.0f);
@@ -27,7 +30,7 @@ TEST(map, AddIncreasesSize)
 
 TEST(map, Contains)
 {
-  IntFloatMap map;
+  Map<int, float> map;
   EXPECT_FALSE(map.contains(4));
   map.add(5, 6.0f);
   EXPECT_FALSE(map.contains(4));
@@ -37,7 +40,7 @@ TEST(map, Contains)
 
 TEST(map, LookupExisting)
 {
-  IntFloatMap map;
+  Map<int, float> map;
   map.add(2, 6.0f);
   map.add(4, 1.0f);
   EXPECT_EQ(map.lookup(2), 6.0f);
@@ -46,7 +49,7 @@ TEST(map, LookupExisting)
 
 TEST(map, LookupNotExisting)
 {
-  IntFloatMap map;
+  Map<int, float> map;
   map.add(2, 4.0f);
   map.add(1, 1.0f);
   EXPECT_EQ(map.lookup_ptr(0), nullptr);
@@ -55,15 +58,16 @@ TEST(map, LookupNotExisting)
 
 TEST(map, AddMany)
 {
-  IntFloatMap map;
+  Map<int, int> map;
   for (int i = 0; i < 100; i++) {
-    map.add(i, i);
+    map.add(i * 30, i);
+    map.add(i * 31, i);
   }
 }
 
 TEST(map, PopItem)
 {
-  IntFloatMap map;
+  Map<int, float> map;
   map.add(2, 3.0f);
   map.add(1, 9.0f);
   EXPECT_TRUE(map.contains(2));
@@ -80,21 +84,21 @@ TEST(map, PopItem)
 
 TEST(map, PopItemMany)
 {
-  IntFloatMap map;
-  for (uint i = 0; i < 100; i++) {
+  Map<int, int> map;
+  for (int i = 0; i < 100; i++) {
     map.add_new(i, i);
   }
-  for (uint i = 25; i < 80; i++) {
+  for (int i = 25; i < 80; i++) {
     EXPECT_EQ(map.pop(i), i);
   }
-  for (uint i = 0; i < 100; i++) {
+  for (int i = 0; i < 100; i++) {
     EXPECT_EQ(map.contains(i), i < 25 || i >= 80);
   }
 }
 
 TEST(map, ValueIterator)
 {
-  IntFloatMap map;
+  Map<int, float> map;
   map.add(3, 5.0f);
   map.add(1, 2.0f);
   map.add(7, -2.0f);
@@ -115,7 +119,7 @@ TEST(map, ValueIterator)
 
 TEST(map, KeyIterator)
 {
-  IntFloatMap map;
+  Map<int, float> map;
   map.add(6, 3.0f);
   map.add(2, 4.0f);
   map.add(1, 3.0f);
@@ -136,7 +140,7 @@ TEST(map, KeyIterator)
 
 TEST(map, ItemIterator)
 {
-  IntFloatMap map;
+  Map<int, float> map;
   map.add(5, 3.0f);
   map.add(2, 9.0f);
   map.add(1, 0.0f);
@@ -160,6 +164,34 @@ TEST(map, ItemIterator)
   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);
+}
+
 static float return_42()
 {
   return 42.0f;
@@ -167,14 +199,16 @@ static float return_42()
 
 TEST(map, LookupOrAdd_SeparateFunction)
 {
-  IntFloatMap map;
+  Map<int, float> map;
   EXPECT_EQ(map.lookup_or_add(0, return_42), 42.0f);
   EXPECT_EQ(map.lookup(0), 42);
+
+  map.keys();
 }
 
 TEST(map, LookupOrAdd_Lambdas)
 {
-  IntFloatMap map;
+  Map<int, float> map;
   auto lambda1 = []() { return 11.0f; };
   EXPECT_EQ(map.lookup_or_add(0, lambda1), 11.0f);
   auto lambda2 = []() { return 20.0f; };
@@ -186,7 +220,7 @@ TEST(map, LookupOrAdd_Lambdas)
 
 TEST(map, AddOrModify)
 {
-  IntFloatMap map;
+  Map<int, float> map;
   auto create_func = [](float *value) {
     *value = 10.0f;
     return true;
@@ -201,13 +235,13 @@ TEST(map, AddOrModify)
   EXPECT_EQ(map.lookup(1), 15.0f);
 }
 
-TEST(map, AddOverride)
+TEST(map, AddOverwrite)
 {
-  IntFloatMap map;
+  Map<int, float> map;
   EXPECT_FALSE(map.contains(3));
-  EXPECT_TRUE(map.add_override(3, 6.0f));
+  EXPECT_TRUE(map.add_overwrite(3, 6.0f));
   EXPECT_EQ(map.lookup(3), 6.0f);
-  EXPECT_FALSE(map.add_override(3, 7.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);
@@ -215,7 +249,7 @@ TEST(map, AddOverride)
 
 TEST(map, LookupOrAddDefault)
 {
-  IntFloatMap map;
+  Map<int, float> map;
   map.lookup_or_add_default(3) = 6;
   EXPECT_EQ(map.lookup(3), 6);
   map.lookup_or_add_default(5) = 2;
@@ -226,10 +260,10 @@ TEST(map, LookupOrAddDefault)
 
 TEST(map, MoveConstructorSmall)
 {
-  IntFloatMap map1;
+  Map<int, float> map1;
   map1.add(1, 2.0f);
   map1.add(4, 1.0f);
-  IntFloatMap map2(std::move(map1));
+  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);
@@ -239,24 +273,25 @@ TEST(map, MoveConstructorSmall)
 
 TEST(map, MoveConstructorLarge)
 {
-  IntFloatMap map1;
-  for (uint i = 0; i < 100; i++) {
+  Map<int, int> map1;
+  for (int i = 0; i < 100; i++) {
     map1.add_new(i, i);
   }
-  IntFloatMap map2(std::move(map1));
+  Map<int, int> map2(std::move(map1));
   EXPECT_EQ(map2.size(), 100);
-  EXPECT_EQ(map2.lookup(1), 1.0f);
-  EXPECT_EQ(map2.lookup(4), 4.0f);
+  EXPECT_EQ(map2.lookup(1), 1);
+  EXPECT_EQ(map2.lookup(4), 4);
   EXPECT_EQ(map1.size(), 0);
   EXPECT_EQ(map1.lookup_ptr(4), nullptr);
 }
 
 TEST(map, MoveAssignment)
 {
-  IntFloatMap map1;
+  Map<int, float> map1;
   map1.add(1, 2.0f);
   map1.add(4, 1.0f);
-  IntFloatMap map2 = std::move(map1);
+  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);
@@ -264,9 +299,23 @@ TEST(map, MoveAssignment)
   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)
 {
-  IntFloatMap map;
+  Map<int, float> map;
   map.add(1, 1.0f);
   map.add(2, 5.0f);
 
@@ -292,12 +341,150 @@ TEST(map, UniquePtrValue)
   Map<int, std::unique_ptr<int>> map;
   map.add_new(1, std::move(value1));
   map.add(2, std::move(value2));
-  map.add_override(3, std::move(value3));
+  map.add_overwrite(3, std::move(value3));
   map.lookup_or_add(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_override(7, std::unique_ptr<int>(new int()));
+  map.add_overwrite(7, 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());
+}
+
+/**
+ * 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, uint amount, uint factor)
+{
+  RNG *rng = BLI_rng_new(0);
+  Vector<int> values;
+  for (uint 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 (uint i = 0; i < 3; i++) {
+    benchmark_random_ints<BLI::Map<int, int>>("BLI::Map          ", 1000000, 1);
+    benchmark_random_ints<BLI::StdUnorderedMapWrapper<int, int>>("std::unordered_map", 1000000, 1);
+  }
+  std::cout << "\n";
+  for (uint i = 0; i < 3; i++) {
+    uint32_t factor = (3 << 10);
+    benchmark_random_ints<BLI::Map<int, int>>("BLI::Map          ", 1000000, factor);
+    benchmark_random_ints<BLI::StdUnorderedMapWrapper<int, int>>(
+        "std::unordered_map", 1000000, factor);
+  }
+}
+
+/**
+ * Timer 'BLI::Map           Add' took 61.7616 ms
+ * Timer 'BLI::Map           Contains' took 18.4989 ms
+ * Timer 'BLI::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 'BLI::Map           Add' took 37.9196 ms
+ * Timer 'BLI::Map           Contains' took 16.7361 ms
+ * Timer 'BLI::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 'BLI::Map           Add' took 37.3053 ms
+ * Timer 'BLI::Map           Contains' took 16.6731 ms
+ * Timer 'BLI::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 'BLI::Map           Add' took 50.1131 ms
+ * Timer 'BLI::Map           Contains' took 25.0491 ms
+ * Timer 'BLI::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 'BLI::Map           Add' took 50.4438 ms
+ * Timer 'BLI::Map           Contains' took 25.2677 ms
+ * Timer 'BLI::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 'BLI::Map           Add' took 48.6995 ms
+ * Timer 'BLI::Map           Contains' took 25.1846 ms
+ * Timer 'BLI::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 */
diff --git a/tests/gtests/blenlib/BLI_math_bits_test.cc b/tests/gtests/blenlib/BLI_math_bits_test.cc
new file mode 100644
index 00000000000..9baa471cf48
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_math_bits_test.cc
@@ -0,0 +1,48 @@
+#include "BLI_math_bits.h"
+#include "testing/testing.h"
+#include <iostream>
+
+TEST(math_bits, BitscanReverseClearUint)
+{
+  uint a = 1234;
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 21);
+  EXPECT_EQ(a, 210);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 24);
+  EXPECT_EQ(a, 82);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 25);
+  EXPECT_EQ(a, 18);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 27);
+  EXPECT_EQ(a, 2);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 30);
+  EXPECT_EQ(a, 0);
+
+  a = 3563987529;
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 0);
+  EXPECT_EQ(a, 1416503881);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 1);
+  EXPECT_EQ(a, 342762057);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 3);
+  EXPECT_EQ(a, 74326601);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 5);
+  EXPECT_EQ(a, 7217737);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 9);
+  EXPECT_EQ(a, 3023433);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 10);
+  EXPECT_EQ(a, 926281);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 12);
+  EXPECT_EQ(a, 401993);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 13);
+  EXPECT_EQ(a, 139849);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 14);
+  EXPECT_EQ(a, 8777);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 18);
+  EXPECT_EQ(a, 585);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 22);
+  EXPECT_EQ(a, 73);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 25);
+  EXPECT_EQ(a, 9);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 28);
+  EXPECT_EQ(a, 1);
+  EXPECT_EQ(bitscan_reverse_clear_uint(&a), 31);
+  EXPECT_EQ(a, 0);
+}
diff --git a/tests/gtests/blenlib/BLI_optional_test.cc b/tests/gtests/blenlib/BLI_optional_test.cc
index e0dec5681fe..8d8be9a3a31 100644
--- a/tests/gtests/blenlib/BLI_optional_test.cc
+++ b/tests/gtests/blenlib/BLI_optional_test.cc
@@ -1,4 +1,5 @@
 #include "BLI_optional.hh"
+#include "BLI_strict_flags.h"
 #include "testing/testing.h"
 #include <string>
 
@@ -36,20 +37,6 @@ TEST(optional, Reset)
   EXPECT_FALSE(a.has_value());
 }
 
-TEST(optional, FromNullPointer)
-{
-  Optional<int> a = Optional<int>::FromPointer(nullptr);
-  EXPECT_FALSE(a.has_value());
-}
-
-TEST(optional, FromNonNullPointer)
-{
-  int value = 42;
-  Optional<int> a = Optional<int>::FromPointer(&value);
-  EXPECT_TRUE(a.has_value());
-  EXPECT_EQ(a.value(), 42);
-}
-
 TEST(optional, Extract)
 {
   Optional<int> a(32);
diff --git a/tests/gtests/blenlib/BLI_set_test.cc b/tests/gtests/blenlib/BLI_set_test.cc
index 90c052d7d2b..1f480f1d3b8 100644
--- a/tests/gtests/blenlib/BLI_set_test.cc
+++ b/tests/gtests/blenlib/BLI_set_test.cc
@@ -1,27 +1,32 @@
+#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"
 
-using BLI::Set;
-using BLI::Vector;
-using IntSet = Set<int>;
+using namespace BLI;
 
-TEST(set, Defaultconstructor)
+TEST(set, DefaultConstructor)
 {
-  IntSet set;
+  Set<int> set;
   EXPECT_EQ(set.size(), 0);
   EXPECT_TRUE(set.is_empty());
 }
 
 TEST(set, ContainsNotExistant)
 {
-  IntSet set;
+  Set<int> set;
   EXPECT_FALSE(set.contains(3));
 }
 
 TEST(set, ContainsExistant)
 {
-  IntSet set;
+  Set<int> set;
   EXPECT_FALSE(set.contains(5));
   EXPECT_TRUE(set.is_empty());
   set.add(5);
@@ -31,7 +36,7 @@ TEST(set, ContainsExistant)
 
 TEST(set, AddMany)
 {
-  IntSet set;
+  Set<int> set;
   for (int i = 0; i < 100; i++) {
     set.add(i);
   }
@@ -46,7 +51,7 @@ TEST(set, AddMany)
 
 TEST(set, InitializerListConstructor)
 {
-  IntSet set = {4, 5, 6};
+  Set<int> set = {4, 5, 6};
   EXPECT_EQ(set.size(), 3);
   EXPECT_TRUE(set.contains(4));
   EXPECT_TRUE(set.contains(5));
@@ -57,11 +62,11 @@ TEST(set, InitializerListConstructor)
 
 TEST(set, CopyConstructor)
 {
-  IntSet set = {3};
+  Set<int> set = {3};
   EXPECT_TRUE(set.contains(3));
   EXPECT_FALSE(set.contains(4));
 
-  IntSet set2 = set;
+  Set<int> set2(set);
   set2.add(4);
   EXPECT_TRUE(set2.contains(3));
   EXPECT_TRUE(set2.contains(4));
@@ -71,47 +76,72 @@ TEST(set, CopyConstructor)
 
 TEST(set, MoveConstructor)
 {
-  IntSet set = {1, 2, 3};
+  Set<int> set = {1, 2, 3};
   EXPECT_EQ(set.size(), 3);
-  IntSet set2 = std::move(set);
+  Set<int> set2(std::move(set));
   EXPECT_EQ(set.size(), 0);
   EXPECT_EQ(set2.size(), 3);
 }
 
-TEST(set, Remove)
+TEST(set, CopyAssignment)
 {
-  IntSet set = {3, 4, 5};
+  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);
+  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(4);
+  set.remove_contained(4);
   EXPECT_TRUE(set.contains(3));
   EXPECT_FALSE(set.contains(4));
   EXPECT_TRUE(set.contains(5));
-  set.remove(3);
+  set.remove_contained(3);
   EXPECT_FALSE(set.contains(3));
   EXPECT_FALSE(set.contains(4));
   EXPECT_TRUE(set.contains(5));
-  set.remove(5);
+  set.remove_contained(5);
   EXPECT_FALSE(set.contains(3));
   EXPECT_FALSE(set.contains(4));
   EXPECT_FALSE(set.contains(5));
 }
 
-TEST(set, RemoveMany)
+TEST(set, RemoveContainedMany)
 {
-  IntSet set;
-  for (uint i = 0; i < 1000; i++) {
+  Set<int> set;
+  for (int i = 0; i < 1000; i++) {
     set.add(i);
   }
-  for (uint i = 100; i < 1000; i++) {
-    set.remove(i);
+  for (int i = 100; i < 1000; i++) {
+    set.remove_contained(i);
   }
-  for (uint i = 900; i < 1000; i++) {
+  for (int i = 900; i < 1000; i++) {
     set.add(i);
   }
 
-  for (uint i = 0; i < 1000; i++) {
+  for (int i = 0; i < 1000; i++) {
     if (i < 100 || i >= 900) {
       EXPECT_TRUE(set.contains(i));
     }
@@ -123,23 +153,23 @@ TEST(set, RemoveMany)
 
 TEST(set, Intersects)
 {
-  IntSet a = {3, 4, 5, 6};
-  IntSet b = {1, 2, 5};
-  EXPECT_TRUE(IntSet::Intersects(a, b));
-  EXPECT_FALSE(IntSet::Disjoint(a, b));
+  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)
 {
-  IntSet a = {5, 6, 7, 8};
-  IntSet b = {2, 3, 4, 9};
-  EXPECT_FALSE(IntSet::Intersects(a, b));
-  EXPECT_TRUE(IntSet::Disjoint(a, b));
+  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)
 {
-  IntSet a;
+  Set<int> a;
   a.add_multiple({5, 7});
   EXPECT_TRUE(a.contains(5));
   EXPECT_TRUE(a.contains(7));
@@ -152,7 +182,7 @@ TEST(set, AddMultiple)
 
 TEST(set, AddMultipleNew)
 {
-  IntSet a;
+  Set<int> a;
   a.add_multiple_new({5, 6});
   EXPECT_TRUE(a.contains(5));
   EXPECT_TRUE(a.contains(6));
@@ -160,7 +190,7 @@ TEST(set, AddMultipleNew)
 
 TEST(set, Iterator)
 {
-  IntSet set = {1, 3, 2, 5, 4};
+  Set<int> set = {1, 3, 2, 5, 4};
   BLI::Vector<int> vec;
   for (int value : set) {
     vec.append(value);
@@ -173,13 +203,13 @@ TEST(set, Iterator)
   EXPECT_TRUE(vec.contains(4));
 }
 
-TEST(set, OftenAddRemove)
+TEST(set, OftenAddRemoveContained)
 {
-  IntSet set;
+  Set<int> set;
   for (int i = 0; i < 100; i++) {
     set.add(42);
     EXPECT_EQ(set.size(), 1);
-    set.remove(42);
+    set.remove_contained(42);
     EXPECT_EQ(set.size(), 0);
   }
 }
@@ -202,3 +232,282 @@ TEST(set, Clear)
   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;
+};
+
+bool operator==(const Type1 &a, const Type1 &b)
+{
+  return a.value == b.value;
+}
+bool operator==(const Type1 &a, const Type2 &b)
+{
+  return a.value == b.value;
+}
+bool operator==(const Type2 &a, const Type1 &b)
+{
+  return a.value == b.value;
+}
+
+template<> struct BLI::DefaultHash<Type1> {
+  uint32_t operator()(const Type1 &value) const
+  {
+    return value.value;
+  }
+
+  uint32_t operator()(const Type2 &value) const
+  {
+    return value.value;
+  }
+};
+
+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 {
+  uint32_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));
+}
+
+/**
+ * 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, uint amount, uint factor)
+{
+  RNG *rng = BLI_rng_new(0);
+  Vector<int> values;
+  for (uint 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 (uint i = 0; i < 3; i++) {
+    benchmark_random_ints<BLI::Set<int>>("BLI::Set          ", 100000, 1);
+    benchmark_random_ints<BLI::StdUnorderedSetWrapper<int>>("std::unordered_set", 100000, 1);
+  }
+  std::cout << "\n";
+  for (uint i = 0; i < 3; i++) {
+    uint32_t factor = (3 << 10);
+    benchmark_random_ints<BLI::Set<int>>("BLI::Set          ", 100000, factor);
+    benchmark_random_ints<BLI::StdUnorderedSetWrapper<int>>("std::unordered_set", 100000, factor);
+  }
+}
+
+/**
+ * Output of the rudimentary benchmark above on my hardware.
+ *
+ * Timer 'BLI::Set           Add' took 5.5573 ms
+ * Timer 'BLI::Set           Contains' took 0.807384 ms
+ * Timer 'BLI::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 'BLI::Set           Add' took 2.62526 ms
+ * Timer 'BLI::Set           Contains' took 0.407499 ms
+ * Timer 'BLI::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 'BLI::Set           Add' took 2.59152 ms
+ * Timer 'BLI::Set           Contains' took 0.415254 ms
+ * Timer 'BLI::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 'BLI::Set           Add' took 3.16514 ms
+ * Timer 'BLI::Set           Contains' took 0.732895 ms
+ * Timer 'BLI::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 'BLI::Set           Add' took 3.11439 ms
+ * Timer 'BLI::Set           Contains' took 0.740159 ms
+ * Timer 'BLI::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 'BLI::Set           Add' took 3.09876 ms
+ * Timer 'BLI::Set           Contains' took 0.742072 ms
+ * Timer 'BLI::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 */
diff --git a/tests/gtests/blenlib/BLI_stack_cxx_test.cc b/tests/gtests/blenlib/BLI_stack_cxx_test.cc
index e49872f8643..28d30f0ecfb 100644
--- a/tests/gtests/blenlib/BLI_stack_cxx_test.cc
+++ b/tests/gtests/blenlib/BLI_stack_cxx_test.cc
@@ -1,12 +1,13 @@
 #include "BLI_stack.hh"
+#include "BLI_strict_flags.h"
+#include "BLI_vector.hh"
 #include "testing/testing.h"
 
-using BLI::Stack;
-using IntStack = Stack<int>;
+using namespace BLI;
 
 TEST(stack, DefaultConstructor)
 {
-  IntStack stack;
+  Stack<int> stack;
   EXPECT_EQ(stack.size(), 0);
   EXPECT_TRUE(stack.is_empty());
 }
@@ -14,7 +15,7 @@ TEST(stack, DefaultConstructor)
 TEST(stack, ArrayRefConstructor)
 {
   std::array<int, 3> array = {4, 7, 2};
-  IntStack stack(array);
+  Stack<int> stack(array);
   EXPECT_EQ(stack.size(), 3);
   EXPECT_EQ(stack.pop(), 2);
   EXPECT_EQ(stack.pop(), 7);
@@ -22,9 +23,66 @@ TEST(stack, ArrayRefConstructor)
   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);
+  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);
+  EXPECT_EQ(stack2.size(), 7);
+  for (int i = 7; i >= 1; i--) {
+    EXPECT_EQ(stack2.pop(), i);
+  }
+}
+
 TEST(stack, Push)
 {
-  IntStack stack;
+  Stack<int> stack;
   EXPECT_EQ(stack.size(), 0);
   stack.push(3);
   EXPECT_EQ(stack.size(), 1);
@@ -34,7 +92,7 @@ TEST(stack, Push)
 
 TEST(stack, PushMultiple)
 {
-  IntStack stack;
+  Stack<int> stack;
   EXPECT_EQ(stack.size(), 0);
   stack.push_multiple({1, 2, 3});
   EXPECT_EQ(stack.size(), 3);
@@ -43,9 +101,52 @@ TEST(stack, PushMultiple)
   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(), i + 1);
+  }
+  for (int i = 999; i > 50; i--) {
+    EXPECT_EQ(stack.pop(), i);
+    EXPECT_EQ(stack.size(), i);
+  }
+  for (int i = 51; i < 5000; i++) {
+    stack.push(i);
+    EXPECT_EQ(stack.size(), i + 1);
+  }
+  for (int i = 4999; i >= 0; i--) {
+    EXPECT_EQ(stack.pop(), i);
+    EXPECT_EQ(stack.size(), 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)
 {
-  IntStack stack;
+  Stack<int> stack;
   stack.push(4);
   stack.push(6);
   EXPECT_EQ(stack.pop(), 6);
@@ -54,7 +155,7 @@ TEST(stack, Pop)
 
 TEST(stack, Peek)
 {
-  IntStack stack;
+  Stack<int> stack;
   stack.push(3);
   stack.push(4);
   EXPECT_EQ(stack.peek(), 4);
@@ -72,3 +173,12 @@ TEST(stack, UniquePtrValues)
   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);
+  }
+}
diff --git a/tests/gtests/blenlib/BLI_string_map_test.cc b/tests/gtests/blenlib/BLI_string_map_test.cc
deleted file mode 100644
index 6acad0ce581..00000000000
--- a/tests/gtests/blenlib/BLI_string_map_test.cc
+++ /dev/null
@@ -1,275 +0,0 @@
-#include "BLI_string_map.hh"
-#include "BLI_vector.hh"
-#include "testing/testing.h"
-
-using namespace BLI;
-
-TEST(string_map, DefaultConstructor)
-{
-  StringMap<int> map;
-  EXPECT_EQ(map.size(), 0);
-}
-
-TEST(string_map, CopyConstructor)
-{
-  StringMap<Vector<int, 4>> map1;
-  map1.add_new("A", {1, 2, 3});
-  map1.add_new("B", {1, 2, 3, 4, 5, 6});
-
-  StringMap<Vector<int>> map2(map1);
-
-  EXPECT_EQ(map1.size(), 2);
-  EXPECT_EQ(map2.size(), 2);
-  EXPECT_EQ(map1.lookup("A")[1], 2);
-  EXPECT_EQ(map2.lookup("A")[1], 2);
-  EXPECT_EQ(map1.lookup("B")[5], 6);
-  EXPECT_EQ(map2.lookup("B")[5], 6);
-}
-
-TEST(string_map, MoveConstructor)
-{
-  StringMap<Vector<int, 4>> map1;
-  map1.add_new("A", {1, 2, 3});
-  map1.add_new("B", {1, 2, 3, 4, 5, 6});
-
-  StringMap<Vector<int>> map2(std::move(map1));
-
-  EXPECT_EQ(map1.size(), 0);
-  EXPECT_FALSE(map1.contains("A"));
-  EXPECT_FALSE(map1.contains("B"));
-
-  EXPECT_EQ(map2.size(), 2);
-  EXPECT_EQ(map2.lookup("A")[1], 2);
-  EXPECT_EQ(map2.lookup("B")[5], 6);
-}
-
-TEST(string_map, Add)
-{
-  StringMap<int> map;
-  EXPECT_EQ(map.size(), 0);
-
-  map.add("test", 1);
-  EXPECT_EQ(map.lookup("test"), 1);
-
-  map.add("test", 2);
-  EXPECT_EQ(map.lookup("test"), 1);
-
-  map.add("test2", 2);
-  EXPECT_EQ(map.lookup("test2"), 2);
-}
-
-TEST(string_map, AddNew)
-{
-  StringMap<int> map;
-  EXPECT_EQ(map.size(), 0);
-
-  map.add_new("Why", 5);
-  EXPECT_EQ(map.size(), 1);
-  EXPECT_EQ(map.lookup("Why"), 5);
-
-  map.add_new("Where", 6);
-  EXPECT_EQ(map.size(), 2);
-  EXPECT_EQ(map.lookup("Where"), 6);
-}
-
-TEST(string_map, AddNew_Many)
-{
-  StringMap<int> map;
-
-  for (uint i = 0; i < 100; i++) {
-    map.add_new(std::to_string(i), i);
-  }
-  EXPECT_EQ(map.size(), 100);
-}
-
-TEST(string_map, Contains)
-{
-  StringMap<int> map;
-  map.add_new("A", 0);
-  map.add_new("B", 0);
-  EXPECT_TRUE(map.contains("A"));
-  EXPECT_TRUE(map.contains("B"));
-  EXPECT_FALSE(map.contains("C"));
-}
-
-TEST(string_map, Contains_Many)
-{
-  StringMap<int> map;
-  for (uint i = 0; i < 50; i++) {
-    map.add_new(std::to_string(i), i);
-  }
-  for (uint i = 100; i < 200; i++) {
-    map.add_new(std::to_string(i), i);
-  }
-  EXPECT_EQ(map.size(), 150);
-  for (uint i = 0; i < 200; i++) {
-    if (i < 50 || i >= 100) {
-      EXPECT_TRUE(map.contains(std::to_string(i)));
-    }
-    else {
-      EXPECT_FALSE(map.contains(std::to_string(i)));
-    }
-  }
-}
-
-TEST(string_map, Lookup)
-{
-  StringMap<int> map;
-  map.add_new("A", 5);
-  map.add_new("B", 8);
-  map.add_new("C", 10);
-  EXPECT_EQ(map.lookup("A"), 5);
-  EXPECT_EQ(map.lookup("B"), 8);
-  EXPECT_EQ(map.lookup("C"), 10);
-}
-
-TEST(string_map, LookupPtr)
-{
-  StringMap<int> map;
-  map.add_new("test1", 13);
-  map.add_new("test2", 14);
-  map.add_new("test3", 15);
-  EXPECT_EQ(*map.lookup_ptr("test1"), 13);
-  EXPECT_EQ(*map.lookup_ptr("test2"), 14);
-  EXPECT_EQ(*map.lookup_ptr("test3"), 15);
-  EXPECT_EQ(map.lookup_ptr("test4"), nullptr);
-}
-
-TEST(string_map, LookupDefault)
-{
-  StringMap<int> map;
-  EXPECT_EQ(map.lookup_default("test", 42), 42);
-  map.add_new("test", 5);
-  EXPECT_EQ(map.lookup_default("test", 42), 5);
-}
-
-TEST(string_map, TryLookup)
-{
-  StringMap<int> map;
-  map.add_new("test", 4);
-  EXPECT_TRUE(map.try_lookup("test").has_value());
-  EXPECT_FALSE(map.try_lookup("value").has_value());
-  EXPECT_EQ(map.try_lookup("test").value(), 4);
-}
-
-TEST(string_map, FindKeyForValue)
-{
-  StringMap<int> map;
-  map.add_new("A", 1);
-  map.add_new("B", 2);
-  map.add_new("C", 3);
-  EXPECT_EQ(map.find_key_for_value(1), "A");
-  EXPECT_EQ(map.find_key_for_value(2), "B");
-  EXPECT_EQ(map.find_key_for_value(3), "C");
-}
-
-TEST(string_map, ForeachValue)
-{
-  StringMap<int> map;
-  map.add_new("A", 4);
-  map.add_new("B", 5);
-  map.add_new("C", 1);
-
-  Vector<int> values;
-  map.foreach_value([&values](int &value) { values.append(value); });
-  EXPECT_EQ(values.size(), 3);
-  EXPECT_TRUE(values.contains(1));
-  EXPECT_TRUE(values.contains(4));
-  EXPECT_TRUE(values.contains(5));
-}
-
-TEST(string_map, ForeachKey)
-{
-  StringMap<int> map;
-  map.add_new("A", 4);
-  map.add_new("B", 5);
-  map.add_new("C", 1);
-
-  Vector<std::string> keys;
-  map.foreach_key([&keys](StringRefNull key) { keys.append(key); });
-  EXPECT_EQ(keys.size(), 3);
-  EXPECT_TRUE(keys.contains("A"));
-  EXPECT_TRUE(keys.contains("B"));
-  EXPECT_TRUE(keys.contains("C"));
-}
-
-TEST(string_map, ForeachKeyValuePair)
-{
-  StringMap<int> map;
-  map.add_new("A", 4);
-  map.add_new("B", 5);
-  map.add_new("C", 1);
-
-  Vector<std::string> keys;
-  Vector<int> values;
-
-  map.foreach_item([&keys, &values](StringRefNull key, int value) {
-    keys.append(key);
-    values.append(value);
-  });
-
-  EXPECT_EQ(keys.size(), 3);
-  EXPECT_EQ(values[keys.index("A")], 4);
-  EXPECT_EQ(values[keys.index("B")], 5);
-  EXPECT_EQ(values[keys.index("C")], 1);
-}
-
-TEST(string_map, WithVectors)
-{
-  StringMap<Vector<int>> map;
-  map.add_new("A", {1, 2, 3});
-  map.add_new("B", {1, 2, 3, 4, 5, 6, 7});
-  EXPECT_EQ(map.size(), 2);
-  EXPECT_EQ(map.lookup("A").size(), 3);
-  EXPECT_EQ(map.lookup("B").size(), 7);
-}
-
-TEST(string_map, UniquePtrValues)
-{
-  StringMap<std::unique_ptr<int>> map;
-  map.add_new("A", std::unique_ptr<int>(new int()));
-  std::unique_ptr<int> &a = map.lookup("A");
-  std::unique_ptr<int> *b = map.lookup_ptr("A");
-  EXPECT_EQ(a.get(), b->get());
-}
-
-TEST(string_map, AddOrModify)
-{
-  StringMap<int> map;
-  auto create_func = [](int *value) {
-    *value = 10;
-    return true;
-  };
-  auto modify_func = [](int *value) {
-    *value += 5;
-    return false;
-  };
-  EXPECT_TRUE(map.add_or_modify("Hello", create_func, modify_func));
-  EXPECT_EQ(map.lookup("Hello"), 10);
-  EXPECT_FALSE(map.add_or_modify("Hello", create_func, modify_func));
-  EXPECT_EQ(map.lookup("Hello"), 15);
-}
-
-TEST(string_map, LookupOrAdd)
-{
-  StringMap<int> map;
-  auto return_5 = []() { return 5; };
-  auto return_8 = []() { return 8; };
-
-  int &a = map.lookup_or_add("A", return_5);
-  EXPECT_EQ(a, 5);
-  EXPECT_EQ(map.lookup_or_add("A", return_8), 5);
-  EXPECT_EQ(map.lookup_or_add("B", return_8), 8);
-}
-
-TEST(string_map, LookupOrAddDefault)
-{
-  StringMap<std::string> map;
-
-  std::string &a = map.lookup_or_add_default("A");
-  EXPECT_EQ(a.size(), 0);
-  a += "Test";
-  EXPECT_EQ(a.size(), 4);
-  std::string &b = map.lookup_or_add_default("A");
-  EXPECT_EQ(b, "Test");
-}
diff --git a/tests/gtests/blenlib/BLI_string_ref_test.cc b/tests/gtests/blenlib/BLI_string_ref_test.cc
index 393f28d4fc1..6f15de282f6 100644
--- a/tests/gtests/blenlib/BLI_string_ref_test.cc
+++ b/tests/gtests/blenlib/BLI_string_ref_test.cc
@@ -1,3 +1,4 @@
+#include "BLI_strict_flags.h"
 #include "BLI_string_ref.hh"
 #include "BLI_vector.hh"
 #include "testing/testing.h"
diff --git a/tests/gtests/blenlib/BLI_type_construct_mock.hh b/tests/gtests/blenlib/BLI_type_construct_mock.hh
deleted file mode 100644
index 72767631608..00000000000
--- a/tests/gtests/blenlib/BLI_type_construct_mock.hh
+++ /dev/null
@@ -1,63 +0,0 @@
-/*
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- */
-
-#ifndef __ANY_TYPE_MOCK_TEST_H__
-#define __ANY_TYPE_MOCK_TEST_H__
-
-#include "BLI_sys_types.h"
-
-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 &other) : copy_constructed(true)
-  {
-  }
-
-  TypeConstructMock(TypeConstructMock &&other) : move_constructed(true)
-  {
-  }
-
-  TypeConstructMock &operator=(const TypeConstructMock &other)
-  {
-    if (this == &other) {
-      return *this;
-    }
-
-    copy_assigned = true;
-    return *this;
-  }
-
-  TypeConstructMock &operator=(TypeConstructMock &&other)
-  {
-    if (this == &other) {
-      return *this;
-    }
-
-    move_assigned = true;
-    return *this;
-  }
-};
-
-#endif /* __ANY_TYPE_MOCK_TEST_H__ */
diff --git a/tests/gtests/blenlib/BLI_vector_set_test.cc b/tests/gtests/blenlib/BLI_vector_set_test.cc
index bfdd47ccb13..87162c9920a 100644
--- a/tests/gtests/blenlib/BLI_vector_set_test.cc
+++ b/tests/gtests/blenlib/BLI_vector_set_test.cc
@@ -1,19 +1,19 @@
+#include "BLI_strict_flags.h"
 #include "BLI_vector_set.hh"
 #include "testing/testing.h"
 
 using BLI::VectorSet;
-using IntVectorSet = VectorSet<int>;
 
 TEST(vector_set, DefaultConstructor)
 {
-  IntVectorSet set;
+  VectorSet<int> set;
   EXPECT_EQ(set.size(), 0);
   EXPECT_TRUE(set.is_empty());
 }
 
 TEST(vector_set, InitializerListConstructor_WithoutDuplicates)
 {
-  IntVectorSet set = {1, 4, 5};
+  VectorSet<int> set = {1, 4, 5};
   EXPECT_EQ(set.size(), 3);
   EXPECT_EQ(set[0], 1);
   EXPECT_EQ(set[1], 4);
@@ -22,7 +22,7 @@ TEST(vector_set, InitializerListConstructor_WithoutDuplicates)
 
 TEST(vector_set, InitializerListConstructor_WithDuplicates)
 {
-  IntVectorSet set = {1, 3, 3, 2, 1, 5};
+  VectorSet<int> set = {1, 3, 3, 2, 1, 5};
   EXPECT_EQ(set.size(), 4);
   EXPECT_EQ(set[0], 1);
   EXPECT_EQ(set[1], 3);
@@ -32,37 +32,37 @@ TEST(vector_set, InitializerListConstructor_WithDuplicates)
 
 TEST(vector_set, Copy)
 {
-  IntVectorSet set1 = {1, 2, 3};
-  IntVectorSet set2 = set1;
+  VectorSet<int> set1 = {1, 2, 3};
+  VectorSet<int> set2 = set1;
   EXPECT_EQ(set1.size(), 3);
   EXPECT_EQ(set2.size(), 3);
-  EXPECT_EQ(set1.index(2), 1);
-  EXPECT_EQ(set2.index(2), 1);
+  EXPECT_EQ(set1.index_of(2), 1);
+  EXPECT_EQ(set2.index_of(2), 1);
 }
 
 TEST(vector_set, CopyAssignment)
 {
-  IntVectorSet set1 = {1, 2, 3};
-  IntVectorSet set2 = {};
+  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(2), 1);
-  EXPECT_EQ(set2.index(2), 1);
+  EXPECT_EQ(set1.index_of(2), 1);
+  EXPECT_EQ(set2.index_of(2), 1);
 }
 
 TEST(vector_set, Move)
 {
-  IntVectorSet set1 = {1, 2, 3};
-  IntVectorSet set2 = std::move(set1);
+  VectorSet<int> set1 = {1, 2, 3};
+  VectorSet<int> set2 = std::move(set1);
   EXPECT_EQ(set1.size(), 0);
   EXPECT_EQ(set2.size(), 3);
 }
 
 TEST(vector_set, MoveAssignment)
 {
-  IntVectorSet set1 = {1, 2, 3};
-  IntVectorSet set2 = {};
+  VectorSet<int> set1 = {1, 2, 3};
+  VectorSet<int> set2 = {};
   set2 = std::move(set1);
   EXPECT_EQ(set1.size(), 0);
   EXPECT_EQ(set2.size(), 3);
@@ -70,7 +70,7 @@ TEST(vector_set, MoveAssignment)
 
 TEST(vector_set, AddNewIncreasesSize)
 {
-  IntVectorSet set;
+  VectorSet<int> set;
   EXPECT_TRUE(set.is_empty());
   EXPECT_EQ(set.size(), 0);
   set.add(5);
@@ -80,57 +80,81 @@ TEST(vector_set, AddNewIncreasesSize)
 
 TEST(vector_set, AddExistingDoesNotIncreaseSize)
 {
-  IntVectorSet set;
+  VectorSet<int> set;
   EXPECT_EQ(set.size(), 0);
-  set.add(5);
+  EXPECT_TRUE(set.add(5));
   EXPECT_EQ(set.size(), 1);
-  set.add(5);
+  EXPECT_FALSE(set.add(5));
   EXPECT_EQ(set.size(), 1);
 }
 
 TEST(vector_set, Index)
 {
-  IntVectorSet set = {3, 6, 4};
-  EXPECT_EQ(set.index(6), 1);
-  EXPECT_EQ(set.index(3), 0);
-  EXPECT_EQ(set.index(4), 2);
+  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)
 {
-  IntVectorSet set = {3, 6, 4};
-  EXPECT_EQ(set.index_try(5), -1);
-  EXPECT_EQ(set.index_try(3), 0);
-  EXPECT_EQ(set.index_try(6), 1);
-  EXPECT_EQ(set.index_try(2), -1);
+  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, Remove)
+TEST(vector_set, RemoveContained)
 {
-  IntVectorSet set = {4, 5, 6, 7};
+  VectorSet<int> set = {4, 5, 6, 7};
   EXPECT_EQ(set.size(), 4);
-  set.remove(5);
+  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(6);
+  set.remove_contained(6);
   EXPECT_EQ(set.size(), 2);
   EXPECT_EQ(set[0], 4);
   EXPECT_EQ(set[1], 7);
-  set.remove(4);
+  set.remove_contained(4);
   EXPECT_EQ(set.size(), 1);
   EXPECT_EQ(set[0], 7);
-  set.remove(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_try(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));
+}
diff --git a/tests/gtests/blenlib/BLI_vector_test.cc b/tests/gtests/blenlib/BLI_vector_test.cc
index 90180feba1f..7d16ef9e54d 100644
--- a/tests/gtests/blenlib/BLI_vector_test.cc
+++ b/tests/gtests/blenlib/BLI_vector_test.cc
@@ -1,9 +1,9 @@
-#include "BLI_type_construct_mock.hh"
+#include "BLI_strict_flags.h"
 #include "BLI_vector.hh"
 #include "testing/testing.h"
 #include <forward_list>
 
-using BLI::Vector;
+using namespace BLI;
 
 TEST(vector, DefaultConstructor)
 {
@@ -15,9 +15,26 @@ TEST(vector, SizeConstructor)
 {
   Vector<int> vec(3);
   EXPECT_EQ(vec.size(), 3);
-  EXPECT_EQ(vec[0], 0);
-  EXPECT_EQ(vec[1], 0);
-  EXPECT_EQ(vec[2], 0);
+}
+
+/**
+ * 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)
@@ -102,7 +119,7 @@ TEST(vector, CopyConstructor2)
 
   EXPECT_EQ(vec1.size(), 4);
   EXPECT_EQ(vec2.size(), 4);
-  EXPECT_NE(vec1.begin(), vec2.begin());
+  EXPECT_NE(vec1.data(), vec2.data());
   EXPECT_EQ(vec2[0], 1);
   EXPECT_EQ(vec2[1], 2);
   EXPECT_EQ(vec2[2], 3);
@@ -116,7 +133,7 @@ TEST(vector, CopyConstructor3)
 
   EXPECT_EQ(vec1.size(), 4);
   EXPECT_EQ(vec2.size(), 4);
-  EXPECT_NE(vec1.begin(), vec2.begin());
+  EXPECT_NE(vec1.data(), vec2.data());
   EXPECT_EQ(vec2[2], 3);
 }
 
@@ -127,7 +144,7 @@ TEST(vector, CopyConstructor4)
 
   EXPECT_EQ(vec1.size(), 4);
   EXPECT_EQ(vec2.size(), 4);
-  EXPECT_NE(vec1.begin(), vec2.begin());
+  EXPECT_NE(vec1.data(), vec2.data());
   EXPECT_EQ(vec2[3], 4);
 }
 
@@ -288,7 +305,7 @@ TEST(vector, BecomeLarge)
     vec.append(i * 5);
   }
   EXPECT_EQ(vec.size(), 100);
-  for (int i = 0; i < 100; i++) {
+  for (uint i = 0; i < 100; i++) {
     EXPECT_EQ(vec[i], i * 5);
   }
 }
@@ -387,20 +404,21 @@ TEST(vector, RemoveFirstOccurrenceAndReorder)
   EXPECT_EQ(vec.size(), 0);
 }
 
-TEST(vector, AllEqual_False)
-{
-  Vector<int> a = {1, 2, 3};
-  Vector<int> b = {1, 2, 4};
-  bool result = Vector<int>::all_equal(a, b);
-  EXPECT_FALSE(result);
-}
-
-TEST(vector, AllEqual_True)
+TEST(vector, Remove)
 {
-  Vector<int> a = {4, 5, 6};
-  Vector<int> b = {4, 5, 6};
-  bool result = Vector<int>::all_equal(a, b);
-  EXPECT_TRUE(result);
+  Vector<int> vec = {1, 2, 3, 4, 5, 6};
+  vec.remove(3);
+  EXPECT_TRUE(std::equal(vec.begin(), vec.end(), ArrayRef<int>({1, 2, 3, 5, 6}).begin()));
+  vec.remove(0);
+  EXPECT_TRUE(std::equal(vec.begin(), vec.end(), ArrayRef<int>({2, 3, 5, 6}).begin()));
+  vec.remove(3);
+  EXPECT_TRUE(std::equal(vec.begin(), vec.end(), ArrayRef<int>({2, 3, 5}).begin()));
+  vec.remove(1);
+  EXPECT_TRUE(std::equal(vec.begin(), vec.end(), ArrayRef<int>({2, 5}).begin()));
+  vec.remove(1);
+  EXPECT_TRUE(std::equal(vec.begin(), vec.end(), ArrayRef<int>({2}).begin()));
+  vec.remove(0);
+  EXPECT_TRUE(std::equal(vec.begin(), vec.end(), ArrayRef<int>({}).begin()));
 }
 
 TEST(vector, ExtendSmallVector)
@@ -453,14 +471,59 @@ TEST(vector, UniquePtrValue)
   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 &other) : copy_constructed(true)
+  {
+  }
+
+  TypeConstructMock(TypeConstructMock &&other) : move_constructed(true)
+  {
+  }
+
+  TypeConstructMock &operator=(const TypeConstructMock &other)
+  {
+    if (this == &other) {
+      return *this;
+    }
+
+    copy_assigned = true;
+    return *this;
+  }
+
+  TypeConstructMock &operator=(TypeConstructMock &&other)
+  {
+    if (this == &other) {
+      return *this;
+    }
+
+    move_assigned = true;
+    return *this;
+  }
+};
+
 TEST(vector, SizeConstructorCallsDefaultConstructor)
 {
   Vector<TypeConstructMock> vec(3);
@@ -525,3 +588,51 @@ TEST(vector, LargeVectorMoveCallsNoConstructor)
   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);
+  }
+}
diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt
index fd0dca37bf6..b76050531da 100644
--- a/tests/gtests/blenlib/CMakeLists.txt
+++ b/tests/gtests/blenlib/CMakeLists.txt
@@ -58,6 +58,7 @@ BLENDER_TEST(BLI_linklist_lockfree "bf_blenlib;bf_intern_numaapi")
 BLENDER_TEST(BLI_listbase "bf_blenlib")
 BLENDER_TEST(BLI_map "bf_blenlib")
 BLENDER_TEST(BLI_math_base "bf_blenlib")
+BLENDER_TEST(BLI_math_bits "bf_blenlib")
 BLENDER_TEST(BLI_math_color "bf_blenlib")
 BLENDER_TEST(BLI_math_geom "bf_blenlib")
 BLENDER_TEST(BLI_math_vector "bf_blenlib")
@@ -69,7 +70,6 @@ BLENDER_TEST(BLI_set "bf_blenlib")
 BLENDER_TEST(BLI_stack "bf_blenlib")
 BLENDER_TEST(BLI_stack_cxx "bf_blenlib")
 BLENDER_TEST(BLI_string "bf_blenlib")
-BLENDER_TEST(BLI_string_map "bf_blenlib")
 BLENDER_TEST(BLI_string_ref "bf_blenlib")
 BLENDER_TEST(BLI_string_utf8 "bf_blenlib")
 BLENDER_TEST(BLI_task "bf_blenlib;bf_intern_numaapi")
-- 
cgit v1.2.3