[Bf-blender-cvs] [7e767d08583] functions: initial experimental vector adaptor data structure

[Jacques Lucke]

Commit: 7e767d08583496d7eef4fd531e0583291f79b736
Author: Jacques Lucke
Date:   Fri Jun 28 17:41:15 2019 +0200
Branches: functions
https://developer.blender.org/rB7e767d08583496d7eef4fd531e0583291f79b736

initial experimental vector adaptor data structure

===================================================================

A	source/blender/blenlib/BLI_vector_adaptor.hpp
M	source/blender/blenlib/CMakeLists.txt
A	tests/gtests/blenlib/BLI_vector_adaptor_test.cc
M	tests/gtests/blenlib/CMakeLists.txt

===================================================================

diff --git a/source/blender/blenlib/BLI_vector_adaptor.hpp b/source/blender/blenlib/BLI_vector_adaptor.hpp
new file mode 100644
index 00000000000..65691b74818
--- /dev/null
+++ b/source/blender/blenlib/BLI_vector_adaptor.hpp
@@ -0,0 +1,141 @@
+/*
+ * 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.
+ */
+
+/** \file
+ * \ingroup bli
+ *
+ * This vector wraps an externally provided memory buffer.
+ * At allows using any buffer as if it were an array.
+ * It does not grow the array dynamically. If the number of
+ * elements is about to exceed the capacity, it asserts false.
+ *
+ * This constraint allows a very efficient append operation,
+ * since no boundary checks have to be performed in release builds.
+ */
+
+#pragma once
+
+#include "BLI_array_ref.hpp"
+
+namespace BLI {
+
+template<typename T> class VectorAdaptor {
+ private:
+  T *m_start;
+  T *m_end;
+  uint m_capacity;
+
+ public:
+  /**
+   * Construct an empty vector adaptor.
+   */
+  VectorAdaptor() : m_start(nullptr), m_end(nullptr), m_capacity(0)
+  {
+  }
+
+  /**
+   * Disable creating copies of the vector, because it would not be
+   * clear, where the new adaptor should take the memory from.
+   */
+  VectorAdaptor(VectorAdaptor &other) = delete;
+
+  /**
+   * Construct using any pointer and a capacity.
+   * The initial size is set to zero.
+   */
+  VectorAdaptor(T *ptr, uint capacity) : m_start(ptr), m_end(ptr), m_capacity(capacity)
+  {
+  }
+
+  /**
+   * Construct from an array. The capacity is automatically determined
+   * from the length of the array.
+   * The initial size is set to zero.
+   */
+  template<uint N> VectorAdaptor(T (&array)[N]) : m_start(array), m_end(array), m_capacity(N)
+  {
+  }
+
+  ~VectorAdaptor()
+  {
+    for (T &value : *this) {
+      value.~T();
+    }
+  }
+
+  /**
+   * Insert one element at the end of the vector.
+   * Asserts, when the capacity is exceeded.
+   */
+  void append(const T &value)
+  {
+    BLI_assert(this->size() < m_capacity);
+    std::uninitialized_copy_n(&value, 1, m_end);
+    m_end += 1;
+  }
+
+  void append(T &&value)
+  {
+    BLI_assert(this->size() < m_capacity);
+    std::uninitialized_copy_n(std::make_move_iterator(&value), 1, m_end);
+    m_end += 1;
+  }
+
+  /**
+   * Insert multiple elements at the end of the vector.
+   * Asserts, when the capacity is exceeded.
+   */
+  void extend(ArrayRef<T> values)
+  {
+    BLI_assert(this->size() + values.size() < m_capacity);
+    std::uninitialized_copy_n(values.begin(), values.size(), m_end);
+    m_end += values.size();
+  }
+
+  /**
+   * Return the maximum size of the vector.
+   */
+  uint capacity() const
+  {
+    return m_capacity;
+  }
+
+  /**
+   * Return the current size of the vector.
+   */
+  uint size() const
+  {
+    return m_end - m_start;
+  }
+
+  T &operator[](uint index)
+  {
+    BLI_assert(index < this->size());
+    return this->begin()[index];
+  }
+
+  T *begin() const
+  {
+    return m_start;
+  }
+
+  T *end() const
+  {
+    return m_end;
+  }
+};
+
+}  // namespace BLI
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 6ee3877d97a..95f703357b0 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -257,6 +257,7 @@ set(SRC
   BLI_small_stack.hpp
   BLI_string_ref.hpp
   BLI_timeit.hpp
+  BLI_vector_adaptor.hpp
 )
 
 set(LIB
diff --git a/tests/gtests/blenlib/BLI_vector_adaptor_test.cc b/tests/gtests/blenlib/BLI_vector_adaptor_test.cc
new file mode 100644
index 00000000000..b100b5a5d97
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_vector_adaptor_test.cc
@@ -0,0 +1,87 @@
+#include "testing/testing.h"
+#include "BLI_vector_adaptor.hpp"
+#include <vector>
+
+using IntVectorAdaptor = BLI::VectorAdaptor<int>;
+
+TEST(vector_adaptor, DefaultConstructor)
+{
+  IntVectorAdaptor vec;
+  EXPECT_EQ(vec.size(), 0);
+  EXPECT_EQ(vec.capacity(), 0);
+}
+
+TEST(vector_adaptor, PointerConstructor)
+{
+  int *array = new int[3];
+  IntVectorAdaptor vec(array, 3);
+  EXPECT_EQ(vec.size(), 0);
+  EXPECT_EQ(vec.capacity(), 3);
+  delete[] array;
+}
+
+TEST(vector_adaptor, ArrayConstructor)
+{
+  int array[5];
+  IntVectorAdaptor vec(array);
+  EXPECT_EQ(vec.size(), 0);
+  EXPECT_EQ(vec.capacity(), 5);
+}
+
+TEST(vector_adaptor, AppendOnce)
+{
+  int array[5];
+  IntVectorAdaptor vec(array);
+  vec.append(42);
+  EXPECT_EQ(vec.size(), 1);
+  EXPECT_EQ(vec[0], 42);
+}
+
+TEST(vector_adaptor, AppendFull)
+{
+  int array[5];
+  IntVectorAdaptor vec(array);
+  vec.append(3);
+  vec.append(4);
+  vec.append(5);
+  vec.append(6);
+  vec.append(7);
+  EXPECT_EQ(vec.size(), 5);
+  EXPECT_EQ(vec[0], 3);
+  EXPECT_EQ(vec[1], 4);
+  EXPECT_EQ(vec[2], 5);
+  EXPECT_EQ(vec[3], 6);
+  EXPECT_EQ(vec[4], 7);
+}
+
+TEST(vector_adaptor, Iterate)
+{
+  int array[4];
+  IntVectorAdaptor vec(array);
+  vec.append(10);
+  vec.append(11);
+  vec.append(12);
+
+  std::vector<int> std_vector;
+  for (int value : vec) {
+    std_vector.push_back(value);
+  }
+
+  EXPECT_EQ(std_vector.size(), 3);
+  EXPECT_EQ(std_vector[0], 10);
+  EXPECT_EQ(std_vector[1], 11);
+  EXPECT_EQ(std_vector[2], 12);
+}
+
+TEST(vector_adaptor, Extend)
+{
+  int array[6];
+  IntVectorAdaptor vec(array);
+  vec.extend({1, 3});
+  vec.extend({2, 5});
+  EXPECT_EQ(vec.size(), 4);
+  EXPECT_EQ(vec[0], 1);
+  EXPECT_EQ(vec[1], 3);
+  EXPECT_EQ(vec[2], 2);
+  EXPECT_EQ(vec[3], 5);
+}
diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt
index c342483aad0..a97efa81805 100644
--- a/tests/gtests/blenlib/CMakeLists.txt
+++ b/tests/gtests/blenlib/CMakeLists.txt
@@ -74,6 +74,7 @@ BLENDER_TEST(BLI_string "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")
+BLENDER_TEST(BLI_vector_adaptor "bf_blenlib")
 
 BLENDER_TEST_PERFORMANCE(BLI_ghash_performance "bf_blenlib")
 BLENDER_TEST_PERFORMANCE(BLI_task_performance "bf_blenlib")