From 967664d1ee2f40a85301b1a8ccdb0ba3fe811d5d Mon Sep 17 00:00:00 2001
From: Jacques Lucke <jacques@blender.org>
Date: Wed, 7 Sep 2022 13:15:34 +0200
Subject: BLI: new C++ BitVector data structure

This adds a new `blender::BitVector` data structure that was requested
a couple of times. It also replaces usages of `BLI_bitmap` in C++ code.

See the comment in `BLI_bit_vector.hh` for more details about the
advantages and disadvantages of using a bit-vector and how the new
data structure compares to `std::vector<bool>` and `BLI_bitmap`.

Differential Revision: https://developer.blender.org/D14006
---
 .../blender/blenlib/tests/BLI_bit_vector_test.cc   | 186 +++++++++++++++++++++
 1 file changed, 186 insertions(+)
 create mode 100644 source/blender/blenlib/tests/BLI_bit_vector_test.cc

(limited to 'source/blender/blenlib/tests/BLI_bit_vector_test.cc')

diff --git a/source/blender/blenlib/tests/BLI_bit_vector_test.cc b/source/blender/blenlib/tests/BLI_bit_vector_test.cc
new file mode 100644
index 00000000000..c477b464f0c
--- /dev/null
+++ b/source/blender/blenlib/tests/BLI_bit_vector_test.cc
@@ -0,0 +1,186 @@
+/* Apache License, Version 2.0 */
+
+#include "BLI_bit_vector.hh"
+#include "BLI_exception_safety_test_utils.hh"
+#include "BLI_strict_flags.h"
+
+#include "testing/testing.h"
+
+namespace blender::tests {
+
+TEST(bit_vector, DefaultConstructor)
+{
+  BitVector vec;
+  EXPECT_EQ(vec.size(), 0);
+}
+
+TEST(bit_vector, CopyConstructorInline)
+{
+  BitVector<> vec({false, false, true, true, false});
+  BitVector<> vec2 = vec;
+
+  EXPECT_EQ(vec.size(), 5);
+  EXPECT_EQ(vec2.size(), 5);
+
+  vec2[1].set();
+  EXPECT_FALSE(vec[1]);
+
+  EXPECT_FALSE(vec2[0]);
+  EXPECT_TRUE(vec2[1]);
+  EXPECT_TRUE(vec2[2]);
+  EXPECT_TRUE(vec2[3]);
+  EXPECT_FALSE(vec2[4]);
+}
+
+TEST(bit_vector, CopyConstructorLarge)
+{
+  BitVector<> vec(500, false);
+  vec[1].set();
+
+  BitVector<> vec2 = vec;
+
+  EXPECT_EQ(vec.size(), 500);
+  EXPECT_EQ(vec2.size(), 500);
+
+  vec2[2].set();
+  EXPECT_FALSE(vec[2]);
+
+  EXPECT_FALSE(vec2[0]);
+  EXPECT_TRUE(vec2[1]);
+  EXPECT_TRUE(vec2[2]);
+}
+
+TEST(bit_vector, MoveConstructorInline)
+{
+  BitVector<> vec({false, false, true, true, false});
+  BitVector<> vec2 = std::move(vec);
+
+  EXPECT_EQ(vec.size(), 0);
+  EXPECT_EQ(vec2.size(), 5);
+
+  EXPECT_FALSE(vec2[0]);
+  EXPECT_FALSE(vec2[1]);
+  EXPECT_TRUE(vec2[2]);
+  EXPECT_TRUE(vec2[3]);
+  EXPECT_FALSE(vec2[4]);
+}
+
+TEST(bit_vector, MoveConstructorLarge)
+{
+  BitVector<> vec(500, false);
+  vec[3].set();
+
+  BitVector<> vec2 = std::move(vec);
+
+  EXPECT_EQ(vec.size(), 0);
+  EXPECT_EQ(vec2.size(), 500);
+
+  EXPECT_FALSE(vec2[0]);
+  EXPECT_FALSE(vec2[1]);
+  EXPECT_FALSE(vec2[2]);
+  EXPECT_TRUE(vec2[3]);
+  EXPECT_FALSE(vec2[4]);
+}
+
+TEST(bit_vector, SizeConstructor)
+{
+  {
+    BitVector<> vec(0);
+    EXPECT_EQ(vec.size(), 0);
+  }
+  {
+    BitVector<> vec(5);
+    EXPECT_EQ(vec.size(), 5);
+    for (BitRef bit : vec) {
+      EXPECT_FALSE(bit);
+    }
+  }
+  {
+    BitVector<> vec(123);
+    EXPECT_EQ(vec.size(), 123);
+    for (BitRef bit : vec) {
+      EXPECT_FALSE(bit);
+    }
+  }
+}
+
+TEST(bit_vector, SizeFillConstructor)
+{
+  {
+    BitVector<> vec(5, false);
+    for (const int64_t i : IndexRange(5)) {
+      EXPECT_FALSE(vec[i]);
+    }
+  }
+  {
+    BitVector<> vec(123, true);
+    for (const int64_t i : IndexRange(123)) {
+      EXPECT_TRUE(vec[i]);
+    }
+  }
+}
+
+TEST(bit_vector, IndexAccess)
+{
+  BitVector<> vec(100, false);
+  vec[55].set();
+  EXPECT_FALSE(vec[50]);
+  EXPECT_FALSE(vec[51]);
+  EXPECT_FALSE(vec[52]);
+  EXPECT_FALSE(vec[53]);
+  EXPECT_FALSE(vec[54]);
+  EXPECT_TRUE(vec[55]);
+  EXPECT_FALSE(vec[56]);
+  EXPECT_FALSE(vec[57]);
+  EXPECT_FALSE(vec[58]);
+}
+
+TEST(bit_vector, Iterator)
+{
+  BitVector<> vec(100, false);
+  {
+    int64_t index = 0;
+    for (MutableBitRef bit : vec) {
+      bit.set(ELEM(index, 0, 4, 7, 10, 11));
+      index++;
+    }
+  }
+  {
+    int64_t index = 0;
+    for (BitRef bit : const_cast<const BitVector<> &>(vec)) {
+      EXPECT_EQ(bit, ELEM(index, 0, 4, 7, 10, 11));
+      index++;
+    }
+  }
+}
+
+TEST(bit_vector, Append)
+{
+  BitVector<> vec;
+  vec.append(false);
+  vec.append(true);
+  vec.append(true);
+  vec.append(false);
+
+  EXPECT_EQ(vec.size(), 4);
+  EXPECT_FALSE(vec[0]);
+  EXPECT_TRUE(vec[1]);
+  EXPECT_TRUE(vec[2]);
+  EXPECT_FALSE(vec[3]);
+}
+
+TEST(bit_vector, AppendMany)
+{
+  BitVector<> vec;
+  for (const int64_t i : IndexRange(1000)) {
+    vec.append(i % 2);
+  }
+  EXPECT_FALSE(vec[0]);
+  EXPECT_TRUE(vec[1]);
+  EXPECT_FALSE(vec[2]);
+  EXPECT_TRUE(vec[3]);
+  EXPECT_FALSE(vec[4]);
+  EXPECT_TRUE(vec[5]);
+}
+
+}  // namespace blender::tests
-- 
cgit v1.2.3