progresstemp-chunked-list

4 files changed, 236 insertions, 49 deletions

diff --git a/source/blender/blenlib/BLI_chunked_list.hh b/source/blender/blenlib/BLI_chunked_list.hh
new file mode 100644
index 00000000000..e0702e55bc9
--- /dev/null
+++ b/source/blender/blenlib/BLI_chunked_list.hh
@@ -0,0 +1,233 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#pragma once
+
+/** \file
+ * \ingroup bli
+ *
+ * A `blender::ChunkedList` is a dynamically growing ordered container for values of type T.
+ * It is *not* guaranteed that all values will be stored in one contiguous array. Instead, multiple
+ * arrays may be used.
+ *
+ * Comparison to `blender::Vector`:
+ * - `ChunkedList` has better performance when appending many elements, because it does not have to
+ *   move existing values.
+ * - This also means that `ChunkedList` can be used with types that cannot be moved.
+ * - A `ChunkedList` can not be indexed efficiently. So while the container is ordered, one can not
+ *   efficiently get the value at a specific index.
+ * - Iterating over a `ChunkedList` is a little bit slower, because it may have to iterate over
+ *   multiple arrays. That is likely negligible in most cases.
+ *
+ * `ChunkedList` should be used instead of `Vector` when the following two statements are true:
+ * - The elements do not have to be in a contiguous array.
+ * - The elements do not have to be accessed with an index.
+ */
+
+#include "BLI_allocator.hh"
+#include "BLI_math_base.hh"
+#include "BLI_memory_utils.hh"
+#include "BLI_vector.hh"
+
+namespace blender {
+
+namespace detail {
+template<typename T> struct alignas(std::max<size_t>(alignof(T), 8)) ChunkListAllocInfo {
+  Vector<MutableSpan<T>> spans;
+};
+}  // namespace detail
+
+template<typename T,
+         int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(T)),
+         typename Allocator = GuardedAllocator>
+class ChunkedList {
+ private:
+  using AllocInfo = detail::ChunkListAllocInfo<T>;
+
+  T *end_;
+  T *capacity_end_;
+  AllocInfo *alloc_info_ = nullptr;
+  BLI_NO_UNIQUE_ADDRESS TypedBuffer<T, InlineBufferCapacity> inline_buffer_;
+  BLI_NO_UNIQUE_ADDRESS Allocator allocator_;
+
+ public:
+  ChunkedList(Allocator allocator = {}) noexcept : allocator_(allocator)
+  {
+    end_ = inline_buffer_;
+    capacity_end_ = end_ + InlineBufferCapacity;
+  }
+
+  ChunkedList(NoExceptConstructor, Allocator allocator = {}) noexcept : ChunkedList(allocator)
+  {
+  }
+
+  ChunkedList(const ChunkedList &other)
+  {
+    this->extend(other);
+  }
+
+  template<int64_t OtherInlineBufferCapacity>
+  ChunkedList(const ChunkedList<T, OtherInlineBufferCapacity, Allocator> &other)
+      : ChunkedList(other.allocator())
+  {
+    this->extend(other);
+  }
+
+  const Allocator &allocator() const
+  {
+    return allocator_;
+  }
+
+  template<typename Fn> void foreach_span(Fn &&fn) const
+  {
+    const T *inline_begin = inline_buffer_;
+    if (alloc_info_ == nullptr) {
+      if (end_ > inline_begin) {
+        fn(Span<T>(inline_begin, end_ - inline_begin));
+      }
+    }
+    else {
+      if (InlineBufferCapacity > 0) {
+        fn(Span<T>(inline_begin, InlineBufferCapacity));
+      }
+      for (const Span<T> span : alloc_info_->spans) {
+        fn(span);
+      }
+    }
+  }
+
+  template<typename Fn> void foreach_span(Fn &&fn)
+  {
+    const_cast<const ChunkedList *>(this)->foreach_span(
+        [&](const Span<T> span) { fn(MutableSpan(const_cast<T *>(span.data()), span.size())); });
+  }
+
+  std::optional<Span<T>> get_span(const int64_t index) const
+  {
+    /* TODO: Define the indices of individual spans. */
+    return {};
+  }
+
+  void append(const T &value)
+  {
+    this->append_as(value);
+  }
+  void append(T &&value)
+  {
+    this->append_as(std::move(value));
+  }
+  template<typename... Args> void append_as(Args &&...args)
+  {
+    this->ensure_space_for_one();
+    BLI_assert(end_ < capacity_end_);
+    new (end_) T(std::forward<Args>(args)...);
+    end_++;
+  }
+
+  template<int64_t OtherInlineBufferCapacity>
+  void extend(const ChunkedList<T, OtherInlineBufferCapacity, Allocator> &list)
+  {
+    list.foreach_span([&](const Span<T> span) { this->extend(span); });
+  }
+
+  void extend(const Span<T> values)
+  {
+    const T *src_data = values.data();
+    const int64_t remaining_capacity = capacity_end_ - end_;
+    const int64_t copy_to_current_chunk = std::min(values.size(), remaining_capacity);
+    const int64_t copy_to_next_chunk = values.size() - copy_to_current_chunk;
+
+    uninitialized_copy_n(src_data, copy_to_current_chunk, end_);
+    end_ += copy_to_current_chunk;
+    if (copy_to_next_chunk == 0) {
+      return;
+    }
+    this->add_chunk(copy_to_next_chunk);
+    try {
+      uninitialized_copy_n(src_data + copy_to_current_chunk, copy_to_next_chunk, end_);
+    }
+    catch (...) {
+      /* TODO:
+       * - Destruct data in previous chunk.
+       * - Free newly allocated chunk.
+       * - Reset `end_`. */
+      throw;
+    }
+    end_ += copy_to_next_chunk;
+  }
+
+  class Iterator {
+   private:
+    using iterator_category = std::forward_iterator_tag;
+    using value_type = T;
+    using pointer = const T *;
+    using reference = const T &;
+
+    const T *begin_;
+    const T *current_;
+    const T *end_;
+    int64_t span_index_;
+    const ChunkedList *chunked_list_;
+
+    friend ChunkedList;
+
+   public:
+    constexpr Iterator &operator++()
+    {
+      current_++;
+      if (current_ == end_) {
+        span_index_++;
+        if (const std::optional<Span<T>> span = chunked_list_->get_span(span_index_)) {
+          begin_ = span.data();
+          current_ = begin_;
+          end_ = begin_ + span.size();
+        }
+      }
+    }
+
+    constexpr friend bool operator!=(const Iterator &a, const Iterator &b)
+    {
+      BLI_assert(a.chunked_list_ == b.chunked_list_);
+      return a.current_ == b.current_;
+    }
+
+    constexpr const T &operator*() const
+    {
+      return *current_;
+    }
+  };
+
+ private:
+  void ensure_space_for_one()
+  {
+    if (UNLIKELY(end_ >= capacity_end_)) {
+      this->add_chunk(1);
+    }
+  }
+
+  BLI_NOINLINE void add_chunk(const int64_t min_chunk_size)
+  {
+    int64_t new_chunk_size = min_chunk_size;
+    T *new_chunk_begin;
+    if (alloc_info_ == nullptr) {
+      math::max_inplace(new_chunk_size, std::max<int64_t>(InlineBufferCapacity * 2, 8));
+      const size_t allocation_size = sizeof(AllocInfo) +
+                                     sizeof(T) * static_cast<size_t>(new_chunk_size);
+      void *buffer = allocator_.allocate(allocation_size, alignof(AllocInfo), __func__);
+      alloc_info_ = new (buffer) AllocInfo();
+      new_chunk_begin = static_cast<T *>(POINTER_OFFSET(buffer, sizeof(AllocInfo)));
+    }
+    else {
+      math::max_inplace(new_chunk_size,
+                        std::min<int64_t>(alloc_info_->spans.last().size() * 2, 4096));
+      const size_t allocation_size = sizeof(T) * static_cast<size_t>(new_chunk_size);
+      new_chunk_begin = static_cast<T *>(
+          allocator_.allocate(allocation_size, alignof(T), __func__));
+    }
+    MutableSpan<T> new_chunk{new_chunk_begin, new_chunk_size};
+    alloc_info_->spans.append(new_chunk);
+    end_ = new_chunk.data();
+    capacity_end_ = new_chunk.data() + new_chunk_size;
+  }
+};
+
+}  // namespace blender
diff --git a/source/blender/blenlib/BLI_vector_list.hh b/source/blender/blenlib/BLI_vector_list.hh
deleted file mode 100644
index 34dac27e053..00000000000
--- a/source/blender/blenlib/BLI_vector_list.hh
+++ /dev/null
@@ -1,46 +0,0 @@
-/* SPDX-License-Identifier: GPL-2.0-or-later */
-
-#pragma once
-
-/** \file
- * \ingroup bli
- *
- * A `blender::VectorList` is a dynamically growing ordered container for values of type T.
- * It is *not* guaranteed that all values will be stored in one contiguous array. Instead, multiple
- * arrays may be used.
- *
- * Comparison to `blender::Vector`:
- * - `VectorList` has better performance when appending many elements, because it does not have to
- *   move existing values.
- * - This also means that `VectorList` can be used with types that cannot be moved.
- * - A `VectorList` can not be indexed efficiently. So while the container is ordered, one can not
- *   efficiently get the value at a specific index.
- * - Iterating over a `VectorList` is a little bit slower, because it may have to iterate over
- *   multiple arrays. That is likely negligible in most cases.
- *
- * `VectorList` should be used instead of `Vector` when the following two statements are true:
- * - The elements do not have to be in a contiguous array.
- * - The elements do not have to be accessed with an index.
- */
-
-#include "BLI_allocator.hh"
-#include "BLI_memory_utils.hh"
-
-namespace blender {
-
-template<typename T> struct VectorListChunk {
-  /** Start of this chunk. */
-  T *begin;
-  /** End of this chunk. */
-  T *capacity_end;
-};
-template<typename T,
-         int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(T)),
-         typename Allocator = GuardedAllocator>
-class VectorList {
-  T *current_end_;
-  T *current_capacity_end_;
-  VectorListChunk *current_chunk_;
-};
-
-}  // namespace blender
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index dddb073fe76..a3ec0603257 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -330,7 +330,7 @@ set(SRC
   BLI_uvproject.h
   BLI_vector.hh
   BLI_vector_adaptor.hh
-  BLI_vector_list.hh
+  BLI_chunked_list.hh
   BLI_vector_set.hh
   BLI_vector_set_slots.hh
   BLI_virtual_array.hh
@@ -434,6 +434,7 @@ if(WITH_GTESTS)
     tests/BLI_bit_vector_test.cc
     tests/BLI_bitmap_test.cc
     tests/BLI_bounds_test.cc
+    tests/BLI_chunked_list_test.cc
     tests/BLI_color_test.cc
     tests/BLI_cpp_type_test.cc
     tests/BLI_delaunay_2d_test.cc
@@ -495,7 +496,6 @@ if(WITH_GTESTS)
     tests/BLI_uuid_test.cc
     tests/BLI_vector_set_test.cc
     tests/BLI_vector_test.cc
-    tests/BLI_vector_list_test.cc
     tests/BLI_virtual_array_test.cc
 
     tests/BLI_exception_safety_test_utils.hh
diff --git a/source/blender/blenlib/tests/BLI_vector_list_test.cc b/source/blender/blenlib/tests/BLI_chunked_list_test.cc
index 3219c573956..30425855b24 100644
--- a/source/blender/blenlib/tests/BLI_vector_list_test.cc
+++ b/source/blender/blenlib/tests/BLI_chunked_list_test.cc
@@ -1,6 +1,6 @@
 /* SPDX-License-Identifier: Apache-2.0 */
 
-#include "BLI_vector_list.hh"
+#include "BLI_chunked_list.hh"
 #include "testing/testing.h"
 
 namespace blender::tests {