1 files changed, 132 insertions, 26 deletions

diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh
index 9dd8341aa76..09eeb321abf 100644
--- a/source/blender/blenlib/BLI_array.hh
+++ b/source/blender/blenlib/BLI_array.hh
@@ -19,8 +19,23 @@
 /** \file
  * \ingroup bli
  *
- * This is a container that contains a fixed size array. Note however, the size of the array is not
- * a template argument. Instead it can be specified at the construction time.
+ * A `BLI::Array<T>` is a container for a fixed size array the size of which is NOT known at
+ * compile time.
+ *
+ * If the size is known at compile time, `std::array<T, N>` should be used instead.
+ *
+ * BLI::Array should usually be used instead of BLI::Vector whenever the number of elements is
+ * known at construction time. Note however, that BLI::Array will default construct all elements
+ * when initialized with the size-constructor. For trivial types, this does nothing. In all other
+ * cases, this adds overhead. If this becomes a problem, a different constructor which does not do
+ * default construction can be added.
+ *
+ * A main benefit of using Array over Vector is that it expresses the intent of the developer
+ * better. It indicates that the size of the data structure is not expected to change. Furthermore,
+ * you can be more certain that an array does not overallocate.
+ *
+ * BLI::Array supports small object optimization to improve performance when the size turns out to
+ * be small at run-time.
  */
 
 #include "BLI_allocator.hh"
@@ -31,42 +46,83 @@
 
 namespace BLI {
 
-template<typename T, uint InlineBufferCapacity = 4, typename Allocator = GuardedAllocator>
+template<
+    /**
+     * The type of the values stored in the array.
+     */
+    typename T,
+    /**
+     * The number of values that can be stored in the array, without doing a heap allocation.
+     *
+     * When T is large, the small buffer optimization is disabled by default to avoid large
+     * unexpected allocations on the stack. It can still be enabled explicitely though.
+     */
+    uint InlineBufferCapacity = (sizeof(T) < 100) ? 4 : 0,
+    /**
+     * The allocator used by this array. Should rarely be changed, except when you don't want that
+     * MEM_* functions are used internally.
+     */
+    typename Allocator = GuardedAllocator>
 class Array {
  private:
+  /** The beginning of the array. It might point into the inline buffer. */
   T *m_data;
+
+  /** Number of elements in the array. */
   uint m_size;
+
+  /** Used for allocations when the inline buffer is too small. */
   Allocator m_allocator;
-  AlignedBuffer<sizeof(T) * InlineBufferCapacity, alignof(T)> m_inline_storage;
+
+  /** A placeholder buffer that will remain uninitialized until it is used. */
+  AlignedBuffer<sizeof(T) * InlineBufferCapacity, alignof(T)> m_inline_buffer;
 
  public:
+  /**
+   * By default an empty array is created.
+   */
   Array()
   {
-    m_data = this->inline_storage();
+    m_data = this->inline_buffer();
     m_size = 0;
   }
 
+  /**
+   * Create a new array that contains copies of all values.
+   */
   Array(ArrayRef<T> values)
   {
     m_size = values.size();
     m_data = this->get_buffer_for_size(values.size());
-    uninitialized_copy_n(values.begin(), m_size, m_data);
+    uninitialized_copy_n(values.data(), m_size, m_data);
   }
 
+  /**
+   * Create a new array that contains copies of all values.
+   */
   Array(const std::initializer_list<T> &values) : Array(ArrayRef<T>(values))
   {
   }
 
+  /**
+   * Create a new array with the given size. All values will be default constructed. For trivial
+   * types like int, default construction does nothing.
+   *
+   * We might want another version of this in the future, that does not do default construction
+   * even for non-trivial types. This should not be the default though, because one can easily mess
+   * up when dealing with uninitialized memory.
+   */
   explicit Array(uint size)
   {
     m_size = size;
     m_data = this->get_buffer_for_size(size);
-
-    for (uint i = 0; i < m_size; i++) {
-      new (m_data + i) T();
-    }
+    default_construct_n(m_data, size);
   }
 
+  /**
+   * Create a new array with the given size. All values will be initialized by copying the given
+   * default.
+   */
   Array(uint size, const T &value)
   {
     m_size = size;
@@ -74,21 +130,19 @@ class Array {
     uninitialized_fill_n(m_data, m_size, value);
   }
 
-  Array(const Array &other)
+  Array(const Array &other) : m_allocator(other.m_allocator)
   {
     m_size = other.size();
-    m_allocator = other.m_allocator;
 
     m_data = this->get_buffer_for_size(other.size());
-    uninitialized_copy_n(other.begin(), m_size, m_data);
+    uninitialized_copy_n(other.data(), m_size, m_data);
   }
 
-  Array(Array &&other) noexcept
+  Array(Array &&other) noexcept : m_allocator(other.m_allocator)
   {
     m_size = other.m_size;
-    m_allocator = other.m_allocator;
 
-    if (!other.uses_inline_storage()) {
+    if (!other.uses_inline_buffer()) {
       m_data = other.m_data;
     }
     else {
@@ -96,14 +150,14 @@ class Array {
       uninitialized_relocate_n(other.m_data, m_size, m_data);
     }
 
-    other.m_data = other.inline_storage();
+    other.m_data = other.inline_buffer();
     other.m_size = 0;
   }
 
   ~Array()
   {
     destruct_n(m_data, m_size);
-    if (!this->uses_inline_storage()) {
+    if (!this->uses_inline_buffer()) {
       m_allocator.deallocate((void *)m_data);
     }
   }
@@ -162,21 +216,50 @@ class Array {
     return m_data[index];
   }
 
+  /**
+   * Returns the number of elements in the array.
+   */
   uint size() const
   {
     return m_size;
   }
 
+  /**
+   * Returns true when the number of elements in the array is zero.
+   */
+  bool is_empty() const
+  {
+    return m_size == 0;
+  }
+
+  /**
+   * Copies the value to all indices in the array.
+   */
   void fill(const T &value)
   {
-    MutableArrayRef<T>(*this).fill(value);
+    initialized_fill_n(m_data, m_size, value);
   }
 
+  /**
+   * Copies the value to the given indices in the array.
+   */
   void fill_indices(ArrayRef<uint> indices, const T &value)
   {
     MutableArrayRef<T>(*this).fill_indices(indices, value);
   }
 
+  /**
+   * Get a pointer to the beginning of the array.
+   */
+  const T *data() const
+  {
+    return m_data;
+  }
+  T *data()
+  {
+    return m_data;
+  }
+
   const T *begin() const
   {
     return m_data;
@@ -197,41 +280,64 @@ class Array {
     return m_data + m_size;
   }
 
+  /**
+   * Get an index range containing all valid indices for this array.
+   */
   IndexRange index_range() const
   {
     return IndexRange(m_size);
   }
 
+  /**
+   * Sets the size to zero. This should only be used when you have manually destructed all elements
+   * in the array beforehand. Use with care.
+   */
+  void clear_without_destruct()
+  {
+    m_size = 0;
+  }
+
+  /**
+   * Access the allocator used by this array.
+   */
   Allocator &allocator()
   {
     return m_allocator;
   }
 
+  /**
+   * Get the value of the InlineBufferCapacity template argument. This is the number of elements
+   * that can be stored without doing an allocation.
+   */
+  static uint inline_buffer_capacity()
+  {
+    return InlineBufferCapacity;
+  }
+
  private:
   T *get_buffer_for_size(uint size)
   {
     if (size <= InlineBufferCapacity) {
-      return this->inline_storage();
+      return this->inline_buffer();
     }
     else {
       return this->allocate(size);
     }
   }
 
-  T *inline_storage() const
+  T *inline_buffer() const
   {
-    return (T *)m_inline_storage.ptr();
+    return (T *)m_inline_buffer.ptr();
   }
 
   T *allocate(uint size)
   {
-    return (T *)m_allocator.allocate_aligned(
-        size * sizeof(T), std::alignment_of<T>::value, __func__);
+    return (T *)m_allocator.allocate(size * sizeof(T), alignof(T), AT);
   }
 
-  bool uses_inline_storage() const
+  bool uses_inline_buffer() const
   {
-    return m_data == this->inline_storage();
+    return m_data == this->inline_buffer();
   }
 };