[Bf-blender-cvs] [096856a700b] functions: new LinearAllocatedVector<T>

[Jacques Lucke]

Commit: 096856a700b795ac3ffb0a6d86317fd0c57b2a11
Author: Jacques Lucke
Date:   Sun Feb 23 17:35:47 2020 +0100
Branches: functions
https://developer.blender.org/rB096856a700b795ac3ffb0a6d86317fd0c57b2a11

new LinearAllocatedVector<T>

This is a vector that does not own the memory its elements are stored in.
Instead, a linear allocator is passed to every call to `append`, that will
be used if the vector has to grow. Since a linear allocator does not support
deallocation, no memory is dealloced until the linear allocator is destructed.

This structure can be used when many small vectors of initially unknown
size are required.

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

A	source/blender/blenlib/BLI_linear_allocated_vector.h
M	source/blender/blenlib/CMakeLists.txt

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

diff --git a/source/blender/blenlib/BLI_linear_allocated_vector.h b/source/blender/blenlib/BLI_linear_allocated_vector.h
new file mode 100644
index 00000000000..a70f83c98fb
--- /dev/null
+++ b/source/blender/blenlib/BLI_linear_allocated_vector.h
@@ -0,0 +1,230 @@
+#pragma once
+
+#include "BLI_linear_allocator.h"
+#include "BLI_memory_utils_cxx.h"
+#include "BLI_index_range.h"
+
+namespace BLI {
+
+template<typename T> class LinearAllocatedVector : BLI::NonCopyable {
+ private:
+  T *m_begin;
+  T *m_end;
+  T *m_capacity_end;
+
+#ifdef DEBUG
+  uint m_debug_size;
+#  define UPDATE_VECTOR_SIZE(ptr) (ptr)->m_debug_size = (ptr)->m_end - (ptr)->m_begin
+#else
+#  define UPDATE_VECTOR_SIZE(ptr) ((void)0)
+#endif
+
+ public:
+  LinearAllocatedVector() : m_begin(nullptr), m_end(nullptr), m_capacity_end(nullptr)
+  {
+    UPDATE_VECTOR_SIZE(this);
+  }
+
+  ~LinearAllocatedVector()
+  {
+    destruct_n(m_begin, this->size());
+  }
+
+  LinearAllocatedVector(LinearAllocatedVector &&other)
+  {
+    m_begin = other.m_begin;
+    m_end = other.m_end;
+    m_capacity_end = other.m_capacity_end;
+
+    other.m_begin = nullptr;
+    other.m_end = nullptr;
+    other.m_capacity_end = nullptr;
+
+    UPDATE_VECTOR_SIZE(this);
+    UPDATE_VECTOR_SIZE(&other);
+  }
+
+  LinearAllocatedVector &operator=(LinearAllocatedVector &&other)
+  {
+    if (this == &other) {
+      return *this;
+    }
+
+    m_begin = other.m_begin;
+    m_end = other.m_end;
+    m_capacity_end = other.m_capacity_end;
+
+    other.m_begin = nullptr;
+    other.m_end = nullptr;
+    other.m_capacity_end = nullptr;
+
+    UPDATE_VECTOR_SIZE(this);
+    UPDATE_VECTOR_SIZE(&other);
+
+    return *this;
+  }
+
+  operator ArrayRef<T>() const
+  {
+    return ArrayRef<T>(m_begin, this->size());
+  }
+
+  operator MutableArrayRef<T>()
+  {
+    return MutableArrayRef<T>(m_begin, this->size());
+  }
+
+  ArrayRef<T> as_ref() const
+  {
+    return *this;
+  }
+
+  MutableArrayRef<T> as_mutable_ref() const
+  {
+    return *this;
+  }
+
+  IndexRange index_range() const
+  {
+    return IndexRange(this->size());
+  }
+
+  uint size() const
+  {
+    return m_end - m_begin;
+  }
+
+  uint capacity() const
+  {
+    return m_capacity_end - m_begin;
+  }
+
+  void clear()
+  {
+    destruct_n(m_begin, this->size());
+    m_end = m_begin;
+    UPDATE_VECTOR_SIZE(this);
+  }
+
+  void append_unchecked(const T &value)
+  {
+    BLI_assert(m_end < m_capacity_end);
+    new (m_end) T(value);
+    m_end++;
+    UPDATE_VECTOR_SIZE(this);
+  }
+
+  template<typename AllocT> void append(const T &value, LinearAllocator<AllocT> &allocator)
+  {
+    if (m_end == m_capacity_end) {
+      this->grow(this->size() + 1, allocator);
+    }
+    this->append_unchecked(value);
+  }
+
+  template<typename AllocT>
+  uint append_and_get_index(const T &value, LinearAllocator<AllocT> &allocator)
+  {
+    uint index = this->size();
+    this->append(value, allocator);
+    return index;
+  }
+
+  bool contains(const T &value) const
+  {
+    for (const T &current : *this) {
+      if (current == value) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  const T &operator[](uint index) const
+  {
+    BLI_assert(index < this->size());
+    return m_begin[index];
+  }
+
+  T &operator[](uint index)
+  {
+    BLI_assert(index < this->size());
+    return m_begin[index];
+  }
+
+  const T *begin() const
+  {
+    return m_begin;
+  }
+
+  const T *end() const
+  {
+    return m_end;
+  }
+
+  T *begin()
+  {
+    return m_begin;
+  }
+
+  T *end()
+  {
+    return m_end;
+  }
+
+  void remove_and_reorder(uint index)
+  {
+    BLI_assert(index < this->size());
+    T *element_to_remove = m_begin + index;
+    m_end--;
+    if (element_to_remove < m_end) {
+      *element_to_remove = std::move(*m_end);
+    }
+    destruct(m_end);
+    UPDATE_VECTOR_SIZE(this);
+  }
+
+  int index_try(const T &value) const
+  {
+    for (T *current = m_begin; current != m_end; current++) {
+      if (*current == value) {
+        return current - m_begin;
+      }
+    }
+    return -1;
+  }
+
+  uint index(const T &value) const
+  {
+    int index = this->index_try(value);
+    BLI_assert(index >= 0);
+    return (uint)index;
+  }
+
+  void remove_first_occurrence_and_reorder(const T &value)
+  {
+    uint index = this->index(value);
+    this->remove_and_reorder((uint)index);
+  }
+
+ private:
+  template<typename AllocT>
+  BLI_NOINLINE void grow(uint min_capacity, LinearAllocator<AllocT> &allocator)
+  {
+    if (min_capacity <= this->capacity()) {
+      return;
+    }
+
+    uint size = this->size();
+    min_capacity = power_of_2_max_u(min_capacity);
+
+    T *new_begin = (T *)allocator.allocate(sizeof(T) * min_capacity, alignof(T));
+    uninitialized_relocate_n(m_begin, size, new_begin);
+
+    m_begin = new_begin;
+    m_end = new_begin + size;
+    m_capacity_end = new_begin + min_capacity;
+  }
+};
+
+}  // namespace BLI
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 5dd0419d7bc..2a5334beff0 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -272,6 +272,7 @@ set(SRC
   BLI_float2.h
   BLI_float4x4.h
   BLI_color.h
+  BLI_linear_allocated_vector.h
 )
 
 set(LIB