progress

5 files changed, 406 insertions, 242 deletions

diff --git a/source/blender/blenlib/BLI_chunk_list.hh b/source/blender/blenlib/BLI_chunk_list.hh
new file mode 100644
index 00000000000..e401e4ae942
--- /dev/null
+++ b/source/blender/blenlib/BLI_chunk_list.hh
@@ -0,0 +1,351 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#pragma once
+
+/** \file
+ * \ingroup bli
+ *
+ * A `blender::ChunkList` 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`:
+ * - `ChunkList` has better performance when appending many elements, because it does not have to
+ *   move existing values.
+ * - This also means that `ChunkList` can be used with types that cannot be moved.
+ * - A `ChunkList` 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 `ChunkList` is a little bit slower, because it may have to iterate over
+ *   multiple arrays. That is likely negligible in most cases.
+ *
+ * `ChunkList` 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>> chunks;
+};
+}  // namespace detail
+
+template<typename T,
+         int64_t InlineBufferCapacity = default_inline_buffer_capacity(sizeof(T)),
+         typename Allocator = GuardedAllocator>
+class ChunkList {
+ 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:
+  ChunkList(Allocator allocator = {}) noexcept : allocator_(allocator)
+  {
+    end_ = inline_buffer_;
+    capacity_end_ = end_ + InlineBufferCapacity;
+  }
+
+  ChunkList(NoExceptConstructor, Allocator allocator = {}) noexcept : ChunkList(allocator)
+  {
+  }
+
+  ChunkList(const ChunkList &other)
+  {
+    this->extend(other);
+  }
+
+  template<int64_t OtherInlineBufferCapacity>
+  ChunkList(const ChunkList<T, OtherInlineBufferCapacity, Allocator> &other)
+      : ChunkList(other.allocator())
+  {
+    this->extend(other);
+  }
+
+  ~ChunkList()
+  {
+    if (InlineBufferCapacity > 0) {
+      if (alloc_info_ == nullptr) {
+        destruct_n<T>(inline_buffer_, end_ - inline_buffer_);
+      }
+      else {
+        for (const int64_t i : IndexRange(this->get_chunk_num()).drop_front(2)) {
+          MutableSpan<T> chunk = this->get_chunk(i);
+          destruct_n(chunk.data(), chunk.size());
+          allocator_.deallocate(chunk.data());
+        }
+        const MutableSpan<T> inline_chunk = alloc_info_->chunks[0];
+        const MutableSpan<T> alloc_chunk = alloc_info_->chunks[1];
+        destruct_n(inline_chunk.data(), inline_chunk.size());
+        destruct_n(alloc_chunk.data(), alloc_chunk.size());
+        alloc_info_->~AllocInfo();
+        allocator_.deallocate(alloc_info_);
+      }
+    }
+    else {
+      if (alloc_info_ != nullptr) {
+        for (const int64_t i : IndexRange(this->get_chunk_num()).drop_front(1)) {
+          MutableSpan<T> chunk = this->get_chunk(i);
+          destruct_n(chunk.data(), chunk.size());
+          allocator_.deallocate(chunk.data());
+        }
+        const MutableSpan<T> alloc_chunk = alloc_info_->chunks[1];
+        destruct_n(alloc_chunk.data(), alloc_chunk.size());
+        alloc_info_->~AllocInfo();
+        allocator_.deallocate(alloc_info_);
+      }
+    }
+  }
+
+  const Allocator &allocator() const
+  {
+    return allocator_;
+  }
+
+  template<typename Fn> void foreach_chunk(Fn &&fn) const
+  {
+    for (const int64_t i : IndexRange(this->get_chunk_num())) {
+      const Span<T> chunk = this->get_chunk(i);
+      fn(chunk);
+    }
+  }
+
+  template<typename Fn> void foreach_chunk(Fn &&fn)
+  {
+    const_cast<const ChunkList *>(this)->foreach_chunk([&](const Span<T> chunk) {
+      fn(MutableSpan(const_cast<T *>(chunk.data()), chunk.size()));
+    });
+  }
+
+  template<typename Fn> void foreach_elem(Fn &&fn) const
+  {
+    for (const int64_t i : IndexRange(this->get_chunk_num())) {
+      const Span<T> chunk = this->get_chunk(i);
+      for (const T &value : chunk) {
+        fn(value);
+      }
+    }
+  }
+
+  int64_t get_chunk_num() const
+  {
+    if constexpr (InlineBufferCapacity > 0) {
+      if (alloc_info_ == nullptr) {
+        return 1;
+      }
+      return alloc_info_->chunks.size();
+    }
+    else {
+      if (alloc_info_ == nullptr) {
+        return 0;
+      }
+      return alloc_info_->chunks.size();
+    }
+  }
+
+  BLI_NOINLINE Span<T> get_chunk(const int64_t index) const
+  {
+    BLI_assert(index >= 0);
+    if constexpr (InlineBufferCapacity > 0) {
+      if (alloc_info_ == nullptr) {
+        BLI_assert(index == 0);
+        return {inline_buffer_, end_ - inline_buffer_};
+      }
+      BLI_assert(index < alloc_info_->chunks.size());
+      if (index == alloc_info_->chunks.size() - 1) {
+        const T *span_begin = alloc_info_->chunks.last().data();
+        return {span_begin, end_ - span_begin};
+      }
+      return alloc_info_->chunks[index];
+    }
+    else {
+      BLI_assert(alloc_info_ != nullptr);
+      return alloc_info_->chunks[index];
+    }
+  }
+
+  MutableSpan<T> get_chunk(const int64_t index)
+  {
+    const Span<T> chunk = const_cast<const ChunkList *>(this)->get_chunk(index);
+    return {const_cast<T *>(chunk.data()), chunk.size()};
+  }
+
+  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 ChunkList<T, OtherInlineBufferCapacity, Allocator> &list)
+  {
+    list.foreach_chunk([&](const Span<T> chunk) { this->extend(chunk); });
+  }
+
+  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 chunk_index_;
+    int64_t chunk_num_;
+    const ChunkList *chunk_list_;
+
+    friend ChunkList;
+
+   public:
+    constexpr Iterator &operator++()
+    {
+      BLI_assert(chunk_index_ < chunk_num_);
+      current_++;
+      if (current_ == end_) {
+        chunk_index_++;
+        if (chunk_index_ < chunk_num_) {
+          const Span<T> next_chunk = chunk_list_->get_chunk(chunk_index_);
+          begin_ = next_chunk.data();
+          current_ = begin_;
+          end_ = begin_ + next_chunk.size();
+        }
+      }
+      return *this;
+    }
+
+    constexpr friend bool operator!=(const Iterator &a, const Iterator &b)
+    {
+      BLI_assert(a.chunk_list_ == b.chunk_list_);
+      return a.current_ != b.current_;
+    }
+
+    constexpr const T &operator*() const
+    {
+      return *current_;
+    }
+  };
+
+  Iterator begin() const
+  {
+    const int64_t span_num = this->get_chunk_num();
+    Iterator it;
+    it.chunk_list_ = this;
+    it.chunk_index_ = 0;
+    it.chunk_num_ = span_num;
+    if (span_num == 0) {
+      it.begin_ = nullptr;
+      it.end_ = nullptr;
+    }
+    else {
+      const Span<T> span = this->get_chunk(0);
+      it.begin_ = span.data();
+      it.end_ = it.begin_ + span.size();
+    }
+    it.current_ = it.begin_;
+    return it;
+  }
+
+  Iterator end() const
+  {
+    const int64_t span_num = this->get_chunk_num();
+    Iterator it;
+    it.chunk_list_ = this;
+    it.chunk_index_ = span_num;
+    it.chunk_num_ = span_num;
+    if (span_num == 0) {
+      it.begin_ = nullptr;
+      it.end_ = nullptr;
+    }
+    else {
+      const Span<T> last_span = this->get_chunk(span_num - 1);
+      it.begin_ = last_span.data();
+      it.end_ = it.begin_ + last_span.size();
+    }
+    it.current_ = it.end_;
+    return it;
+  }
+
+ 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();
+      alloc_info_->chunks.append({inline_buffer_, end_ - inline_buffer_});
+      new_chunk_begin = static_cast<T *>(POINTER_OFFSET(buffer, sizeof(AllocInfo)));
+    }
+    else {
+      math::max_inplace(new_chunk_size,
+                        std::min<int64_t>(alloc_info_->chunks.last().size() * 2, 4096 * 1000));
+      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_->chunks.append(new_chunk);
+    end_ = new_chunk.data();
+    capacity_end_ = new_chunk.data() + new_chunk_size;
+  }
+};
+
+}  // namespace blender
diff --git a/source/blender/blenlib/BLI_chunked_list.hh b/source/blender/blenlib/BLI_chunked_list.hh
deleted file mode 100644
index e0702e55bc9..00000000000
--- a/source/blender/blenlib/BLI_chunked_list.hh
+++ /dev/null
@@ -1,233 +0,0 @@
-/* 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/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index a3ec0603257..9e5ad4d9efe 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_chunked_list.hh
+  BLI_chunk_list.hh
   BLI_vector_set.hh
   BLI_vector_set_slots.hh
   BLI_virtual_array.hh
@@ -434,7 +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_chunk_list_test.cc
     tests/BLI_color_test.cc
     tests/BLI_cpp_type_test.cc
     tests/BLI_delaunay_2d_test.cc
diff --git a/source/blender/blenlib/tests/BLI_chunk_list_test.cc b/source/blender/blenlib/tests/BLI_chunk_list_test.cc
new file mode 100644
index 00000000000..f40d31b9c07
--- /dev/null
+++ b/source/blender/blenlib/tests/BLI_chunk_list_test.cc
@@ -0,0 +1,53 @@
+/* SPDX-License-Identifier: Apache-2.0 */
+
+#include "BLI_chunk_list.hh"
+#include "BLI_timeit.hh"
+
+#include "testing/testing.h"
+
+namespace blender::tests {
+
+TEST(chunk_list, Test)
+{
+  const int64_t amount = 1e3;
+  for ([[maybe_unused]] const int64_t iter : IndexRange(5)) {
+    {
+      ChunkList<int> list;
+      {
+        SCOPED_TIMER("chunk list: create");
+        for (const int64_t i : IndexRange(amount)) {
+          list.append(i);
+        }
+      }
+      int sum = 0;
+      {
+        SCOPED_TIMER("chunk list: sum");
+        // list.foreach_elem([&](const int v) { sum += v; });
+        for (const int v : list) {
+          sum += v;
+        }
+      }
+      std::cout << "Sum: " << sum << "\n";
+    }
+    {
+      Vector<int> vec;
+      {
+
+        SCOPED_TIMER("vector: create");
+        for (const int64_t i : IndexRange(amount)) {
+          vec.append(i);
+        }
+      }
+      int sum = 0;
+      {
+        SCOPED_TIMER("vector: sum");
+        for (const int v : vec) {
+          sum += v;
+        }
+      }
+      std::cout << "Sum: " << sum << "\n";
+    }
+  }
+}
+
+}  // namespace blender::tests
diff --git a/source/blender/blenlib/tests/BLI_chunked_list_test.cc b/source/blender/blenlib/tests/BLI_chunked_list_test.cc
deleted file mode 100644
index 30425855b24..00000000000
--- a/source/blender/blenlib/tests/BLI_chunked_list_test.cc
+++ /dev/null
@@ -1,7 +0,0 @@
-/* SPDX-License-Identifier: Apache-2.0 */
-
-#include "BLI_chunked_list.hh"
-#include "testing/testing.h"
-
-namespace blender::tests {
-}