BLI: Add new `blender::Pool` container

A `blender::Pool` can construct and destruct elements without reordering. Freed items memory
will be reused by next allocations.

Elements are allocated in chunks to reduce memory fragmentation and avoid reallocation.

Reviewed By: JacquesLucke

Differential Revision: https://developer.blender.org/D15894

3 files changed, 137 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_pool.hh b/source/blender/blenlib/BLI_pool.hh
new file mode 100644
index 00000000000..7ed39fea195
--- /dev/null
+++ b/source/blender/blenlib/BLI_pool.hh
@@ -0,0 +1,84 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+/** \file
+ * \ingroup bli
+ *
+ * A `blender::Pool` allows fast allocation and deallocation of many elements of the same type.
+ *
+ * It is compatible with types that are not moveable.
+ *
+ * Freed elements memory will be reused by next allocations.
+ * Elements are allocated in chunks to reduce memory fragmentation and avoid reallocation.
+ */
+
+#pragma once
+
+#include "BLI_stack.hh"
+#include "BLI_utility_mixins.hh"
+#include "BLI_vector.hh"
+
+namespace blender {
+
+template<typename T, int64_t ChunkLen = 64> class Pool : NonCopyable {
+ private:
+  using Chunk = TypedBuffer<T, ChunkLen>;
+
+  /** Allocated item buffer. */
+  Vector<std::unique_ptr<Chunk>> values_;
+  /** List of freed elements to be use for the next allocations. A Stack is best here to avoid
+   * overhead when growing the free list. It also offers better cache performance than a queue
+   * since last added entries will be reused first. */
+  Stack<T *, 0> free_list_;
+
+ public:
+  ~Pool()
+  {
+    /* All elements need to be freed before freeing the pool. */
+    BLI_assert(this->size() == 0);
+  }
+
+  /**
+   * Construct an object inside this pool's memory.
+   */
+  template<typename... ForwardT> T &construct(ForwardT &&...value)
+  {
+    if (free_list_.is_empty()) {
+      values_.append(std::make_unique<Chunk>());
+      T *chunk_start = values_.last()->ptr();
+      for (auto i : IndexRange(ChunkLen)) {
+        free_list_.push(chunk_start + i);
+      }
+    }
+    T *ptr = free_list_.pop();
+    new (ptr) T(std::forward<ForwardT>(value)...);
+    return *ptr;
+  }
+
+  /**
+   * Destroy the given element inside this memory pool. Memory will be reused by next element
+   * construction. This invokes undefined behavior if the item is not from this pool.
+   */
+  void destruct(T &value)
+  {
+    value.~T();
+    free_list_.push(&value);
+  }
+
+  /**
+   * Return the number of constructed elements in this pool.
+   */
+  int64_t size() const
+  {
+    return values_.size() * ChunkLen - free_list_.size();
+  }
+
+  /**
+   * Returns true when the pool contains no elements, otherwise false.
+   */
+  bool is_empty() const
+  {
+    return this->size() == 0;
+  }
+};
+
+}  // namespace blender
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 78455c44fe1..ded4127a0d8 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -283,6 +283,7 @@ set(SRC
   BLI_path_util.h
   BLI_polyfill_2d.h
   BLI_polyfill_2d_beautify.h
+  BLI_pool.hh
   BLI_probing_strategies.hh
   BLI_quadric.h
   BLI_rand.h
@@ -474,6 +475,7 @@ if(WITH_GTESTS)
     tests/BLI_multi_value_map_test.cc
     tests/BLI_path_util_test.cc
     tests/BLI_polyfill_2d_test.cc
+    tests/BLI_pool_test.cc
     tests/BLI_ressource_strings.h
     tests/BLI_serialize_test.cc
     tests/BLI_session_uuid_test.cc
diff --git a/source/blender/blenlib/tests/BLI_pool_test.cc b/source/blender/blenlib/tests/BLI_pool_test.cc
new file mode 100644
index 00000000000..31cb255d997
--- /dev/null
+++ b/source/blender/blenlib/tests/BLI_pool_test.cc
@@ -0,0 +1,51 @@
+/* SPDX-License-Identifier: Apache-2.0 */
+
+#include "BLI_exception_safety_test_utils.hh"
+#include "BLI_pool.hh"
+#include "BLI_strict_flags.h"
+#include "testing/testing.h"
+
+namespace blender::tests {
+
+TEST(pool, DefaultConstructor)
+{
+  Pool<int> pool;
+  EXPECT_EQ(pool.size(), 0);
+}
+
+TEST(pool, Allocation)
+{
+  Vector<int *> ptrs;
+  Pool<int> pool;
+  for (int i = 0; i < 100; i++) {
+    ptrs.append(&pool.construct(i));
+  }
+  EXPECT_EQ(pool.size(), 100);
+
+  for (int *ptr : ptrs) {
+    pool.destruct(*ptr);
+  }
+  EXPECT_EQ(pool.size(), 0);
+}
+
+TEST(pool, Reuse)
+{
+  Vector<int *> ptrs;
+  Pool<int> pool;
+  for (int i = 0; i < 32; i++) {
+    ptrs.append(&pool.construct(i));
+  }
+
+  int *freed_ptr = ptrs[6];
+  pool.destruct(*freed_ptr);
+
+  ptrs[6] = &pool.construct(0);
+
+  EXPECT_EQ(ptrs[6], freed_ptr);
+
+  for (int *ptr : ptrs) {
+    pool.destruct(*ptr);
+  }
+}
+
+}  // namespace blender::tests