BLI: new C++ ArrayRef, Vector, Stack, ... data structures

Many generic C++ data structures have been developed in the
functions branch. This commit merges a first chunk of them into
master. The following new data structures are included:

Array: Owns a memory buffer with a fixed size. It is different
  from std::array in that the size is not part of the type.

ArrayRef: References an array owned by someone else. All elements
  in the referenced array are considered to be const. This should
  be the preferred parameter type for functions that take arrays
  as input.

MutableArrayRef: References an array owned by someone else. The
  elements in the referenced array can be changed.

IndexRange: Specifies a continuous range of integers with a start
  and end index.

IntrusiveListBaseWrapper: A utility class that allows iterating
  over ListBase instances where the prev and next pointer are
  stored in the objects directly.

Stack: A stack implemented on top of a vector.

Vector: An array that can grow dynamically.

Allocators: Three allocator types are included that can be used
  by the container types to support different use cases.

The Stack and Vector support small object optimization. So when
the amount of elements in them is below a certain threshold, no
memory allocation is performed.

Additionally, most methods have unit tests.

I'm merging this without normal code review, after I checked the
code roughly with Sergey, and after we talked about it with Brecht.

19 files changed, 3104 insertions, 1 deletions

diff --git a/source/blender/blenlib/BLI_allocator.h b/source/blender/blenlib/BLI_allocator.h
new file mode 100644
index 00000000000..77506aa3dc5
--- /dev/null
+++ b/source/blender/blenlib/BLI_allocator.h
@@ -0,0 +1,127 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup bli
+ *
+ * This file offers a couple of memory allocators that can be used with containers such as Vector
+ * and Map. Note that these allocators are not designed to work with standard containers like
+ * std::vector.
+ *
+ * Also see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html for why the standard
+ * allocators are not a good fit applications like Blender. The current implementations in this
+ * file are fairly simple still, more complexity can be added when necessary. For now they do their
+ * job good enough.
+ */
+
+#pragma once
+
+#include <stdlib.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_utildefines.h"
+#include "BLI_math_base.h"
+#include "BLI_temporary_allocator.h"
+
+namespace BLI {
+
+/**
+ * Use Blenders guarded allocator (aka MEM_malloc). This should always be used except there is a
+ * good reason not to use it.
+ */
+class GuardedAllocator {
+ public:
+  void *allocate(uint size, const char *name)
+  {
+    return MEM_mallocN(size, name);
+  }
+
+  void *allocate_aligned(uint size, uint alignment, const char *name)
+  {
+    alignment = std::max<uint>(alignment, 8);
+    return MEM_mallocN_aligned(size, alignment, name);
+  }
+
+  void deallocate(void *ptr)
+  {
+    MEM_freeN(ptr);
+  }
+};
+
+/**
+ * This is a simple wrapper around malloc/free. Only use this when the GuardedAllocator cannot be
+ * used. This can be the case when the allocated element might live longer than Blenders Allocator.
+ */
+class RawAllocator {
+ private:
+  struct MemHead {
+    int offset;
+  };
+
+ public:
+  void *allocate(uint size, const char *UNUSED(name))
+  {
+    void *ptr = malloc(size + sizeof(MemHead));
+    ((MemHead *)ptr)->offset = sizeof(MemHead);
+    return POINTER_OFFSET(ptr, sizeof(MemHead));
+  }
+
+  void *allocate_aligned(uint size, uint alignment, const char *UNUSED(name))
+  {
+    BLI_assert(is_power_of_2_i(alignment));
+    void *ptr = malloc(size + alignment + sizeof(MemHead));
+    void *used_ptr = (void *)((uintptr_t)POINTER_OFFSET(ptr, alignment + sizeof(MemHead)) &
+                              ~((uintptr_t)alignment - 1));
+    uint offset = (uintptr_t)used_ptr - (uintptr_t)ptr;
+    BLI_assert(offset >= sizeof(MemHead));
+    ((MemHead *)used_ptr - 1)->offset = offset;
+    return used_ptr;
+  }
+
+  void deallocate(void *ptr)
+  {
+    MemHead *head = (MemHead *)ptr - 1;
+    int offset = -head->offset;
+    void *actual_pointer = POINTER_OFFSET(ptr, offset);
+    free(actual_pointer);
+  }
+};
+
+/**
+ * Use this only under specific circumstances as described in BLI_temporary_allocator.h.
+ */
+class TemporaryAllocator {
+ public:
+  void *allocate(uint size, const char *UNUSED(name))
+  {
+    return BLI_temporary_allocate(size);
+  }
+
+  void *allocate_aligned(uint size, uint alignment, const char *UNUSED(name))
+  {
+    BLI_assert(alignment <= 64);
+    UNUSED_VARS_NDEBUG(alignment);
+    return BLI_temporary_allocate(size);
+  }
+
+  void deallocate(void *ptr)
+  {
+    BLI_temporary_deallocate(ptr);
+  }
+};
+
+}  // namespace BLI
diff --git a/source/blender/blenlib/BLI_array_cxx.h b/source/blender/blenlib/BLI_array_cxx.h
new file mode 100644
index 00000000000..f48ba05842e
--- /dev/null
+++ b/source/blender/blenlib/BLI_array_cxx.h
@@ -0,0 +1,195 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \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.
+ */
+
+#pragma once
+
+#include "BLI_utildefines.h"
+#include "BLI_allocator.h"
+#include "BLI_array_ref.h"
+#include "BLI_memory_utils_cxx.h"
+
+namespace BLI {
+
+template<typename T, typename Allocator = GuardedAllocator> class Array {
+ private:
+  T *m_data;
+  uint m_size;
+  Allocator m_allocator;
+
+ public:
+  Array()
+  {
+    m_data = nullptr;
+    m_size = 0;
+  }
+
+  Array(ArrayRef<T> values)
+  {
+    m_size = values.size();
+    m_data = this->allocate(m_size);
+    uninitialized_copy_n(values.begin(), m_size, m_data);
+  }
+
+  Array(const std::initializer_list<T> &values) : Array(ArrayRef<T>(values))
+  {
+  }
+
+  explicit Array(uint size)
+  {
+    m_data = this->allocate(size);
+    m_size = size;
+
+    for (uint i = 0; i < m_size; i++) {
+      new (m_data + i) T();
+    }
+  }
+
+  Array(uint size, const T &value)
+  {
+    m_data = this->allocate(size);
+    m_size = size;
+    uninitialized_fill_n(m_data, m_size, value);
+  }
+
+  Array(const Array &other)
+  {
+    m_size = other.size();
+    m_allocator = other.m_allocator;
+
+    if (m_size == 0) {
+      m_data = nullptr;
+      return;
+    }
+    else {
+      m_data = this->allocate(m_size);
+      copy_n(other.begin(), m_size, m_data);
+    }
+  }
+
+  Array(Array &&other) noexcept
+  {
+    m_data = other.m_data;
+    m_size = other.m_size;
+    m_allocator = other.m_allocator;
+
+    other.m_data = nullptr;
+    other.m_size = 0;
+  }
+
+  ~Array()
+  {
+    destruct_n(m_data, m_size);
+    if (m_data != nullptr) {
+      m_allocator.deallocate((void *)m_data);
+    }
+  }
+
+  Array &operator=(const Array &other)
+  {
+    if (this == &other) {
+      return *this;
+    }
+
+    this->~Array();
+    new (this) Array(other);
+    return *this;
+  }
+
+  Array &operator=(Array &&other)
+  {
+    if (this == &other) {
+      return *this;
+    }
+
+    this->~Array();
+    new (this) Array(std::move(other));
+    return *this;
+  }
+
+  operator ArrayRef<T>() const
+  {
+    return ArrayRef<T>(m_data, m_size);
+  }
+
+  operator MutableArrayRef<T>()
+  {
+    return MutableArrayRef<T>(m_data, m_size);
+  }
+
+  ArrayRef<T> as_ref() const
+  {
+    return *this;
+  }
+
+  T &operator[](uint index)
+  {
+    BLI_assert(index < m_size);
+    return m_data[index];
+  }
+
+  uint size() const
+  {
+    return m_size;
+  }
+
+  void fill(const T &value)
+  {
+    MutableArrayRef<T>(*this).fill(value);
+  }
+
+  void fill_indices(ArrayRef<uint> indices, const T &value)
+  {
+    MutableArrayRef<T>(*this).fill_indices(indices, value);
+  }
+
+  const T *begin() const
+  {
+    return m_data;
+  }
+
+  const T *end() const
+  {
+    return m_data + m_size;
+  }
+
+  T *begin()
+  {
+    return m_data;
+  }
+
+  T *end()
+  {
+    return m_data + m_size;
+  }
+
+ private:
+  T *allocate(uint size)
+  {
+    return (T *)m_allocator.allocate_aligned(
+        size * sizeof(T), std::alignment_of<T>::value, __func__);
+  }
+};
+
+template<typename T> using TemporaryArray = Array<T, TemporaryAllocator>;
+
+}  // namespace BLI
diff --git a/source/blender/blenlib/BLI_array_ref.h b/source/blender/blenlib/BLI_array_ref.h
new file mode 100644
index 00000000000..a771d1c1329
--- /dev/null
+++ b/source/blender/blenlib/BLI_array_ref.h
@@ -0,0 +1,423 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup bli
+ *
+ * These classes offer a convenient way to work with continuous chunks of memory of a certain type.
+ * We differentiate ArrayRef and MutableArrayRef. The elements in the former are const while the
+ * elements in the other are not.
+ *
+ * Passing array references as parameters has multiple benefits:
+ *   - Less templates are used because the function does not have to work with different
+ *     container types.
+ *   - It encourages an Struct-of-Arrays data layout which is often benefitial when
+ *     writing high performance code. Also it makes it easier to reuse code.
+ *   - Array references offer convenient ways of slicing and other operations.
+ *
+ * The instances of ArrayRef and MutableArrayRef are very small and should be passed by value.
+ * Since array references do not own any memory, it is generally not save to store them.
+ */
+
+#pragma once
+
+#include <vector>
+#include <array>
+#include <algorithm>
+#include <iostream>
+#include <string>
+
+#include "BLI_utildefines.h"
+#include "BLI_memory_utils_cxx.h"
+#include "BLI_index_range.h"
+
+namespace BLI {
+
+/**
+ * References an array of data. The elements in the array should not be changed.
+ */
+template<typename T> class ArrayRef {
+ private:
+  const T *m_start = nullptr;
+  uint m_size = 0;
+
+ public:
+  /**
+   * Create a reference to an empty array.
+   * The pointer is allowed to be nullptr.
+   */
+  ArrayRef() = default;
+
+  ArrayRef(const T *start, uint size) : m_start(start), m_size(size)
+  {
+  }
+
+  ArrayRef(const std::initializer_list<T> &list) : ArrayRef(list.begin(), list.size())
+  {
+  }
+
+  ArrayRef(const std::vector<T> &vector) : ArrayRef(vector.data(), vector.size())
+  {
+  }
+
+  template<std::size_t N> ArrayRef(const std::array<T, N> &array) : ArrayRef(array.data(), N)
+  {
+  }
+
+  /**
+   * Return a continuous part of the array.
+   * Asserts that the slice stays within the array.
+   */
+  ArrayRef slice(uint start, uint size) const
+  {
+    BLI_assert(start + size <= this->size() || size == 0);
+    return ArrayRef(m_start + start, size);
+  }
+
+  ArrayRef slice(IndexRange range) const
+  {
+    return this->slice(range.start(), range.size());
+  }
+
+  /**
+   * Return a new ArrayRef with n elements removed from the beginning.
+   * Asserts that the array contains enough elements.
+   */
+  ArrayRef drop_front(uint n = 1) const
+  {
+    BLI_assert(n <= this->size());
+    return this->slice(n, this->size() - n);
+  }
+
+  /**
+   * Return a new ArrayRef with n elements removed from the beginning.
+   * Asserts that the array contains enough elements.
+   */
+  ArrayRef drop_back(uint n = 1) const
+  {
+    BLI_assert(n <= this->size());
+    return this->slice(0, this->size() - n);
+  }
+
+  /**
+   * Return a new ArrayRef that only contains the first n elements.
+   * Asserts that the array contains enough elements.
+   */
+  ArrayRef take_front(uint n) const
+  {
+    BLI_assert(n <= this->size());
+    return this->slice(0, n);
+  }
+
+  /**
+   * Return a new ArrayRef that only contains the last n elements.
+   * Asserts that the array contains enough elements.
+   */
+  ArrayRef take_back(uint n) const
+  {
+    BLI_assert(n <= this->size());
+    return this->slice(this->size() - n, n);
+  }
+
+  /**
+   * Copy the values in this array to another array.
+   */
+  void copy_to(T *ptr) const
+  {
+    BLI::copy_n(m_start, m_size, ptr);
+  }
+
+  const T *begin() const
+  {
+    return m_start;
+  }
+
+  const T *end() const
+  {
+    return m_start + m_size;
+  }
+
+  /**
+   * Access an element in the array.
+   * Asserts that the index is in the bounds of the array.
+   */
+  const T &operator[](uint index) const
+  {
+    BLI_assert(index < m_size);
+    return m_start[index];
+  }
+
+  /**
+   * Return the number of elements in the referenced array.
+   */
+  uint size() const
+  {
+    return m_size;
+  }
+
+  /**
+   * Return the number of bytes referenced by this ArrayRef.
+   */
+  uint byte_size() const
+  {
+    return sizeof(T) * m_size;
+  }
+
+  /**
+   * Does a linear search to see of the value is in the array.
+   * Return true if it is, otherwise false.
+   */
+  bool contains(const T &value) const
+  {
+    for (const T &element : *this) {
+      if (element == value) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  /**
+   * Does a constant time check to see if the pointer is within the referenced array.
+   * Return true if it is, otherwise false.
+   */
+  bool contains_ptr(const T *ptr) const
+  {
+    return (this->begin() <= ptr) && (ptr < this->end());
+  }
+
+  /**
+   * Does a linear search to count how often the value is in the array.
+   * Returns the number of occurences.
+   */
+  uint count(const T &value) const
+  {
+    uint counter = 0;
+    for (const T &element : *this) {
+      if (element == value) {
+        counter++;
+      }
+    }
+    return counter;
+  }
+
+  /**
+   * Return a reference to the first element in the array.
+   * Asserts that the array is not empty.
+   */
+  const T &first() const
+  {
+    BLI_assert(m_size > 0);
+    return m_start[0];
+  }
+
+  /**
+   * Return a reference to the last elemeent in the array.
+   * Asserts that the array is not empty.
+   */
+  const T &last() const
+  {
+    BLI_assert(m_size > 0);
+    return m_start[m_size - 1];
+  }
+
+  /**
+   * Get element at the given index. If the index is out of range, return the fallback value.
+   */
+  T get(uint index, const T &fallback) const
+  {
+    if (index < m_size) {
+      return m_start[index];
+    }
+    return fallback;
+  }
+
+  /**
+   * Get a new array ref to the same underlying memory buffer. No conversions are done.
+   * Asserts when the sizes of the types don't match.
+   */
+  template<typename NewT> ArrayRef<NewT> cast() const
+  {
+    /* Can be adjusted to allow different type sizes when necessary. */
+    BLI_STATIC_ASSERT(sizeof(T) == sizeof(NewT), "");
+    return ArrayRef<NewT>((NewT *)m_start, m_size);
+  }
+
+  /**
+   * A debug utility to print the content of the array ref. Every element will be printed on a
+   * separate line using the given callback.
+   */
+  template<typename PrintLineF> void print_as_lines(std::string name, PrintLineF print_line) const
+  {
+    std::cout << "ArrayRef: " << name << " \tSize:" << m_size << '\n';
+    for (const T &value : *this) {
+      std::cout << "  ";
+      print_line(value);
+      std::cout << '\n';
+    }
+  }
+};
+
+/**
+ * Mostly the same as ArrayRef, except that one can change the array elements via this reference.
+ */
+template<typename T> class MutableArrayRef {
+ private:
+  T *m_start;
+  uint m_size;
+
+ public:
+  MutableArrayRef() = default;
+
+  MutableArrayRef(T *start, uint size) : m_start(start), m_size(size)
+  {
+  }
+
+  MutableArrayRef(std::initializer_list<T> &list) : MutableArrayRef(list.begin(), list.size())
+  {
+  }
+
+  MutableArrayRef(std::vector<T> &vector) : MutableArrayRef(vector.data(), vector.size())
+  {
+  }
+
+  template<std::size_t N>
+  MutableArrayRef(std::array<T, N> &array) : MutableArrayRef(array.data(), N)
+  {
+  }
+
+  operator ArrayRef<T>()
+  {
+    return ArrayRef<T>(m_start, m_size);
+  }
+
+  /**
+   * Get the number of elements in the array.
+   */
+  uint size() const
+  {
+    return m_size;
+  }
+
+  /**
+   * Replace all elements in the referenced array with the given value.
+   */
+  void fill(const T &element)
+  {
+    std::fill_n(m_start, m_size, element);
+  }
+
+  /**
+   * Replace a subset of all elements with the given value.
+   */
+  void fill_indices(ArrayRef<uint> indices, const T &element)
+  {
+    for (uint i : indices) {
+      m_start[i] = element;
+    }
+  }
+
+  /**
+   * Copy the values from another array into the references array.
+   */
+  void copy_from(const T *ptr)
+  {
+    BLI::copy_n(ptr, m_size, m_start);
+  }
+
+  void copy_from(ArrayRef<T> other)
+  {
+    BLI_assert(this->size() == other.size());
+    this->copy_from(other.begin());
+  }
+
+  T *begin() const
+  {
+    return m_start;
+  }
+
+  T *end() const
+  {
+    return m_start + m_size;
+  }
+
+  T &operator[](uint index) const
+  {
+    BLI_assert(index < this->size());
+    return m_start[index];
+  }
+
+  /**
+   * Return a continuous part of the array.
+   * Aserts that the slice stays in the array bounds.
+   */
+  MutableArrayRef slice(uint start, uint length) const
+  {
+    BLI_assert(start + length <= this->size());
+    return MutableArrayRef(m_start + start, length);
+  }
+
+  /**
+   * Return a new MutableArrayRef with n elements removed from the beginning.
+   */
+  MutableArrayRef drop_front(uint n = 1) const
+  {
+    BLI_assert(n <= this->size());
+    return this->slice(n, this->size() - n);
+  }
+
+  /**
+   * Return a new MutableArrayRef with n elements removed from the beginning.
+   */
+  MutableArrayRef drop_back(uint n = 1) const
+  {
+    BLI_assert(n <= this->size());
+    return this->slice(0, this->size() - n);
+  }
+
+  /**
+   * Return a new MutableArrayRef that only contains the first n elements.
+   */
+  MutableArrayRef take_front(uint n) const
+  {
+    BLI_assert(n <= this->size());
+    return this->slice(0, n);
+  }
+
+  /**
+   * Return a new MutableArrayRef that only contains the last n elements.
+   */
+  MutableArrayRef take_back(uint n) const
+  {
+    BLI_assert(n <= this->size());
+    return this->slice(this->size() - n, n);
+  }
+
+  ArrayRef<T> as_ref() const
+  {
+    return ArrayRef<T>(m_start, m_size);
+  }
+};
+
+/**
+ * Shorthand to make use of automatic template parameter deduction.
+ */
+template<typename T> ArrayRef<T> ref_c_array(const T *array, uint size)
+{
+  return ArrayRef<T>(array, size);
+}
+
+} /* namespace BLI */
diff --git a/source/blender/blenlib/BLI_index_range.h b/source/blender/blenlib/BLI_index_range.h
new file mode 100644
index 00000000000..96c3d22c4e5
--- /dev/null
+++ b/source/blender/blenlib/BLI_index_range.h
@@ -0,0 +1,193 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup bli
+ *
+ * Allows passing iterators over ranges of integers without actually allocating an array or passing
+ * separate values. A range always has a step of one. If other step sizes are required in some
+ * cases, a separate data structure should be used.
+ */
+
+#pragma once
+
+#include <cmath>
+#include <algorithm>
+#include <iostream>
+
+#include "BLI_utildefines.h"
+
+namespace BLI {
+
+template<typename T> class ArrayRef;
+
+class IndexRange {
+ private:
+  uint m_start = 0;
+  uint m_size = 0;
+
+ public:
+  IndexRange() = default;
+
+  explicit IndexRange(uint size) : m_start(0), m_size(size)
+  {
+  }
+
+  IndexRange(uint start, uint size) : m_start(start), m_size(size)
+  {
+  }
+
+  class Iterator {
+   private:
+    uint m_current;
+
+   public:
+    Iterator(uint current) : m_current(current)
+    {
+    }
+
+    Iterator &operator++()
+    {
+      m_current++;
+      return *this;
+    }
+
+    bool operator!=(const Iterator &iterator) const
+    {
+      return m_current != iterator.m_current;
+    }
+
+    uint operator*() const
+    {
+      return m_current;
+    }
+  };
+
+  Iterator begin() const
+  {
+    return Iterator(m_start);
+  }
+
+  Iterator end() const
+  {
+    return Iterator(m_start + m_size);
+  }
+
+  /**
+   * Access an element in the range.
+   */
+  uint operator[](uint index) const
+  {
+    BLI_assert(index < this->size());
+    return m_start + index;
+  }
+
+  /**
+   * Two ranges compare equal when they contain the same numbers.
+   */
+  friend bool operator==(IndexRange a, IndexRange b)
+  {
+    return (a.m_size == b.m_size) && (a.m_start == b.m_start || a.m_size == 0);
+  }
+
+  /**
+   * Get the amount of numbers in the range.
+   */
+  uint size() const
+  {
+    return m_size;
+  }
+
+  /**
+   * Create a new range starting at the end of the current one.
+   */
+  IndexRange after(uint n) const
+  {
+    return IndexRange(m_start + m_size, n);
+  }
+
+  /**
+   * Create a new range that ends at the start of the current one.
+   */
+  IndexRange before(uint n) const
+  {
+    return IndexRange(m_start - n, n);
+  }
+
+  /**
+   * Get the first element in the range.
+   * Asserts when the range is empty.
+   */
+  uint first() const
+  {
+    BLI_assert(this->size() > 0);
+    return m_start;
+  }
+
+  /**
+   * Get the last element in the range.
+   * Asserts when the range is empty.
+   */
+  uint last() const
+  {
+    BLI_assert(this->size() > 0);
+    return m_start + m_size - 1;
+  }
+
+  /**
+   * Get the element one after the end. The returned value is undefined when the range is empty.
+   */
+  uint one_after_last() const
+  {
+    return m_start + m_size;
+  }
+
+  /**
+   * Get the first element in the range. The returned value is undefined when the range is empty.
+   */
+  uint start() const
+  {
+    return m_start;
+  }
+
+  /**
+   * Returns true when the range contains a certain number, otherwise false.
+   */
+  bool contains(uint value) const
+  {
+    return value >= m_start && value < m_start + m_size;
+  }
+
+  IndexRange slice(uint start, uint size) const
+  {
+    uint new_start = m_start + start;
+    BLI_assert(new_start + size <= m_start + m_size || size == 0);
+    return IndexRange(new_start, size);
+  }
+
+  /**
+   * Get read-only access to a memory buffer that contains the range as actual numbers.
+   */
+  ArrayRef<uint> as_array_ref() const;
+
+  friend std::ostream &operator<<(std::ostream &stream, IndexRange range)
+  {
+    stream << "[" << range.start() << ", " << range.one_after_last() << ")";
+    return stream;
+  }
+};
+
+}  // namespace BLI
diff --git a/source/blender/blenlib/BLI_listbase_wrapper.h b/source/blender/blenlib/BLI_listbase_wrapper.h
new file mode 100644
index 00000000000..90755d551b1
--- /dev/null
+++ b/source/blender/blenlib/BLI_listbase_wrapper.h
@@ -0,0 +1,97 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup bli
+ *
+ * The purpose of this wrapper is just to make it more comfortable to iterate of ListBase
+ * instances, that are used in many places in Blender.
+ */
+
+#pragma once
+
+#include "BLI_listbase.h"
+#include "DNA_listBase.h"
+
+namespace BLI {
+
+template<typename T> class IntrusiveListBaseWrapper {
+ private:
+  ListBase *m_listbase;
+
+ public:
+  IntrusiveListBaseWrapper(ListBase *listbase) : m_listbase(listbase)
+  {
+    BLI_assert(listbase);
+  }
+
+  IntrusiveListBaseWrapper(ListBase &listbase) : IntrusiveListBaseWrapper(&listbase)
+  {
+  }
+
+  class Iterator {
+   private:
+    ListBase *m_listbase;
+    T *m_current;
+
+   public:
+    Iterator(ListBase *listbase, T *current) : m_listbase(listbase), m_current(current)
+    {
+    }
+
+    Iterator &operator++()
+    {
+      m_current = m_current->next;
+      return *this;
+    }
+
+    Iterator operator++(int)
+    {
+      Iterator iterator = *this;
+      ++*this;
+      return iterator;
+    }
+
+    bool operator!=(const Iterator &iterator) const
+    {
+      return m_current != iterator.m_current;
+    }
+
+    T *operator*() const
+    {
+      return m_current;
+    }
+  };
+
+  Iterator begin() const
+  {
+    return Iterator(m_listbase, (T *)m_listbase->first);
+  }
+
+  Iterator end() const
+  {
+    return Iterator(m_listbase, nullptr);
+  }
+
+  T get(uint index) const
+  {
+    void *ptr = BLI_findlink(m_listbase, index);
+    BLI_assert(ptr);
+    return (T *)ptr;
+  }
+};
+
+} /* namespace BLI */
diff --git a/source/blender/blenlib/BLI_memory_utils_cxx.h b/source/blender/blenlib/BLI_memory_utils_cxx.h
new file mode 100644
index 00000000000..7bfc885b7f6
--- /dev/null
+++ b/source/blender/blenlib/BLI_memory_utils_cxx.h
@@ -0,0 +1,81 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup bli
+ */
+
+#pragma once
+
+#include <memory>
+#include <algorithm>
+
+namespace BLI {
+
+using std::copy;
+using std::copy_n;
+using std::uninitialized_copy;
+using std::uninitialized_copy_n;
+using std::uninitialized_fill;
+using std::uninitialized_fill_n;
+
+template<typename T> void destruct(T *ptr)
+{
+  ptr->~T();
+}
+
+template<typename T> void destruct_n(T *ptr, uint n)
+{
+  for (uint i = 0; i < n; i++) {
+    ptr[i].~T();
+  }
+}
+
+template<typename T> void uninitialized_move_n(T *src, uint n, T *dst)
+{
+  std::uninitialized_copy_n(std::make_move_iterator(src), n, dst);
+}
+
+template<typename T> void move_n(T *src, uint n, T *dst)
+{
+  std::copy_n(std::make_move_iterator(src), n, dst);
+}
+
+template<typename T> void uninitialized_relocate(T *src, T *dst)
+{
+  new (dst) T(std::move(*src));
+  destruct(src);
+}
+
+template<typename T> void uninitialized_relocate_n(T *src, uint n, T *dst)
+{
+  uninitialized_move_n(src, n, dst);
+  destruct_n(src, n);
+}
+
+template<typename T> void relocate(T *src, T *dst)
+{
+  *dst = std::move(*src);
+  destruct(src);
+}
+
+template<typename T> void relocate_n(T *src, uint n, T *dst)
+{
+  move_n(src, n, dst);
+  destruct_n(src, n);
+}
+
+}  // namespace BLI
diff --git a/source/blender/blenlib/BLI_stack_cxx.h b/source/blender/blenlib/BLI_stack_cxx.h
new file mode 100644
index 00000000000..095f98608b7
--- /dev/null
+++ b/source/blender/blenlib/BLI_stack_cxx.h
@@ -0,0 +1,142 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup bli
+ *
+ * Basic stack implementation with support for small object optimization.
+ */
+
+#pragma once
+
+#include "BLI_vector.h"
+
+namespace BLI {
+
+template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Stack {
+ private:
+  Vector<T, N, Allocator> m_elements;
+
+ public:
+  Stack() = default;
+
+  /**
+   * Construct a stack from an array ref. The elements will be pushed in the same order they are in
+   * the array.
+   */
+  Stack(ArrayRef<T> values) : m_elements(values)
+  {
+  }
+
+  operator ArrayRef<T>()
+  {
+    return m_elements;
+  }
+
+  /**
+   * Return the number of elements in the stack.
+   */
+  uint size() const
+  {
+    return m_elements.size();
+  }
+
+  /**
+   * Return true when the stack is empty, otherwise false.
+   */
+  bool empty() const
+  {
+    return this->size() == 0;
+  }
+
+  /**
+   * Add a new element to the top of the stack.
+   */
+  void push(const T &value)
+  {
+    m_elements.append(value);
+  }
+
+  void push(T &&value)
+  {
+    m_elements.append(std::forward<T>(value));
+  }
+
+  /**
+   * Remove the element from the top of the stack and return it.
+   * This will assert when the stack is empty.
+   */
+  T pop()
+  {
+    return m_elements.pop_last();
+  }
+
+  /**
+   * Return a reference to the value a the top of the stack.
+   * This will assert when the stack is empty.
+   */
+  T &peek()
+  {
+    BLI_assert(!this->empty());
+    return m_elements[this->size() - 1];
+  }
+
+  T *begin()
+  {
+    return m_elements.begin();
+  }
+
+  T *end()
+  {
+    return m_elements.end();
+  }
+
+  const T *begin() const
+  {
+    return m_elements.begin();
+  }
+
+  const T *end() const
+  {
+    return m_elements.end();
+  }
+
+  /**
+   * Remove all elements from the stack but keep the memory.
+   */
+  void clear()
+  {
+    m_elements.clear();
+  }
+
+  /**
+   * Remove all elements and free any allocated memory.
+   */
+  void clear_and_make_small()
+  {
+    m_elements.clear_and_make_small();
+  }
+
+  /**
+   * Does a linear search to check if the value is in the stack.
+   */
+  bool contains(const T &value)
+  {
+    return m_elements.contains(value);
+  }
+};
+
+} /* namespace BLI */
diff --git a/source/blender/blenlib/BLI_temporary_allocator.h b/source/blender/blenlib/BLI_temporary_allocator.h
new file mode 100644
index 00000000000..b378e5869c0
--- /dev/null
+++ b/source/blender/blenlib/BLI_temporary_allocator.h
@@ -0,0 +1,64 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup bli
+ *
+ * This allocation method assumes
+ *   1. The allocations are short-lived.
+ *   2. The total number of allocations is bound by a constant per thread.
+ *
+ * These two assumptions make it possible to cache and reuse relatively large buffers. They allow
+ * to hand out buffers that are much larger than the requested size, without the fear of running
+ * out of memory.
+ *
+ * The assumptions might feel a bit limiting at first, but hold true in many cases. For example,
+ * many algorithms need to store temporary data. With this allocator, the allocation can become
+ * very cheap for common cases.
+ *
+ * Many cpu-bound algorithms can benefit from being split up into several stages, whereby the
+ * output of one stage is written into an array that is read by the next stage. This makes them
+ * easier to debug, profile and optimize. Often a reason this is not done is that the memory
+ * allocation might be expensive. The goal of this allocator is to make this a non-issue, by
+ * reusing the same long buffers over and over again.
+ *
+ * All allocated buffers are 64 byte aligned, to make them as reusable as possible.
+ * If the requested size is too large, there is a fallback to normal allocation. The allocation
+ * overhead is probably very small in these cases anyway.
+ *
+ * The best way to use this allocator is to use one of the prepared containers like TemporaryVector
+ * and TemporaryArray.
+ */
+
+#ifndef __BLI_TEMPORARY_ALLOCATOR_H__
+#define __BLI_TEMPORARY_ALLOCATOR_H__
+
+#include "BLI_utildefines.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define BLI_TEMPORARY_BUFFER_ALIGNMENT 64
+
+void *BLI_temporary_allocate(uint size);
+void BLI_temporary_deallocate(void *buffer);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __BLI_TEMPORARY_ALLOCATOR_H__ */
diff --git a/source/blender/blenlib/BLI_temporary_allocator_cxx.h b/source/blender/blenlib/BLI_temporary_allocator_cxx.h
new file mode 100644
index 00000000000..be898f8c78d
--- /dev/null
+++ b/source/blender/blenlib/BLI_temporary_allocator_cxx.h
@@ -0,0 +1,35 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup bli
+ */
+
+#pragma once
+
+#include "BLI_temporary_allocator.h"
+
+namespace BLI {
+
+template<typename T> class MutableArrayRef;
+
+template<typename T> MutableArrayRef<T> temporary_allocate_array(uint size)
+{
+  void *ptr = BLI_temporary_allocate(sizeof(T) * size);
+  return MutableArrayRef<T>((T *)ptr, size);
+}
+
+};  // namespace BLI
diff --git a/source/blender/blenlib/BLI_vector.h b/source/blender/blenlib/BLI_vector.h
new file mode 100644
index 00000000000..167131cc99e
--- /dev/null
+++ b/source/blender/blenlib/BLI_vector.h
@@ -0,0 +1,601 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup bli
+ *
+ * This vector wraps a dynamically sized array of a specific type. It supports small object
+ * optimization. That means, when the vector only contains a few elements, no memory allocation is
+ * performed. Instead, those elements are stored directly in the vector.
+ */
+
+#pragma once
+
+#include <algorithm>
+#include <cstdlib>
+#include <cstring>
+#include <iostream>
+#include <memory>
+
+#include "BLI_utildefines.h"
+#include "BLI_memory_utils_cxx.h"
+#include "BLI_array_ref.h"
+#include "BLI_listbase_wrapper.h"
+#include "BLI_math_base.h"
+#include "BLI_allocator.h"
+
+#include "MEM_guardedalloc.h"
+
+namespace BLI {
+
+template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Vector {
+ private:
+  T *m_begin;
+  T *m_end;
+  T *m_capacity_end;
+  Allocator m_allocator;
+  char m_small_buffer[sizeof(T) * N];
+
+#ifdef DEBUG
+  /* Storing size in debug builds, because it makes debugging much easier sometimes. */
+  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
+
+  template<typename OtherT, uint OtherN, typename OtherAllocator> friend class Vector;
+
+ public:
+  /**
+   * Create an empty vector.
+   * This does not do any memory allocation.
+   */
+  Vector()
+  {
+    m_begin = this->small_buffer();
+    m_end = m_begin;
+    m_capacity_end = m_begin + N;
+    UPDATE_VECTOR_SIZE(this);
+  }
+
+  /**
+   * Create a vector with a specific size.
+   * The elements will be default initialized.
+   */
+  explicit Vector(uint size) : Vector()
+  {
+    this->reserve(size);
+    this->increase_size_unchecked(size);
+    for (T *current = m_begin; current != m_end; current++) {
+      new (current) T();
+    }
+  }
+
+  /**
+   * Create a vector filled with a specific value.
+   */
+  Vector(uint size, const T &value) : Vector()
+  {
+    this->reserve(size);
+    this->increase_size_unchecked(size);
+    BLI::uninitialized_fill_n(m_begin, size, value);
+  }
+
+  /**
+   * Create a vector from an initializer list.
+   */
+  Vector(std::initializer_list<T> values) : Vector(ArrayRef<T>(values))
+  {
+  }
+
+  /**
+   * Create a vector from an array ref.
+   */
+  Vector(ArrayRef<T> values) : Vector()
+  {
+    this->reserve(values.size());
+    this->increase_size_unchecked(values.size());
+    BLI::uninitialized_copy_n(values.begin(), values.size(), this->begin());
+  }
+
+  /**
+   * Create a vector from any container. It must be possible to use the container in a range-for
+   * loop.
+   */
+  template<typename ContainerT> static Vector FromContainer(const ContainerT &container)
+  {
+    Vector vector;
+    for (const auto &value : container) {
+      vector.append(value);
+    }
+    return vector;
+  }
+
+  /**
+   * Create a vector from a ListBase.
+   */
+  Vector(ListBase &values, bool intrusive_next_and_prev_pointers) : Vector()
+  {
+    BLI_assert(intrusive_next_and_prev_pointers);
+    if (intrusive_next_and_prev_pointers) {
+      for (T value : IntrusiveListBaseWrapper<typename std::remove_pointer<T>::type>(values)) {
+        this->append(value);
+      }
+    }
+  }
+
+  /**
+   * Create a copy of another vector.
+   * The other vector will not be changed.
+   * If the other vector has less than N elements, no allocation will be made.
+   */
+  Vector(const Vector &other) : m_allocator(other.m_allocator)
+  {
+    this->init_copy_from_other_vector(other);
+  }
+
+  template<uint OtherN>
+  Vector(const Vector<T, OtherN, Allocator> &other) : m_allocator(other.m_allocator)
+  {
+    this->init_copy_from_other_vector(other);
+  }
+
+  /**
+   * Steal the elements from another vector.
+   * This does not do an allocation.
+   * The other vector will have zero elements afterwards.
+   */
+  template<uint OtherN>
+  Vector(Vector<T, OtherN, Allocator> &&other) noexcept : m_allocator(other.m_allocator)
+  {
+    uint size = other.size();
+
+    if (other.is_small()) {
+      if (size <= N) {
+        /* Copy between inline buffers. */
+        m_begin = this->small_buffer();
+        m_end = m_begin + size;
+        m_capacity_end = m_begin + N;
+        uninitialized_relocate_n(other.m_begin, size, m_begin);
+      }
+      else {
+        /* Copy from inline buffer to newly allocated buffer. */
+        uint capacity = size;
+        m_begin = (T *)m_allocator.allocate_aligned(
+            sizeof(T) * capacity, std::alignment_of<T>::value, __func__);
+        m_end = m_begin + size;
+        m_capacity_end = m_begin + capacity;
+        uninitialized_relocate_n(other.m_begin, size, m_begin);
+      }
+    }
+    else {
+      /* Steal the pointer. */
+      m_begin = other.m_begin;
+      m_end = other.m_end;
+      m_capacity_end = other.m_capacity_end;
+    }
+
+    other.m_begin = other.small_buffer();
+    other.m_end = other.m_begin;
+    other.m_capacity_end = other.m_begin + OtherN;
+    UPDATE_VECTOR_SIZE(this);
+    UPDATE_VECTOR_SIZE(&other);
+  }
+
+  ~Vector()
+  {
+    destruct_n(m_begin, this->size());
+    if (!this->is_small()) {
+      m_allocator.deallocate(m_begin);
+    }
+  }
+
+  operator ArrayRef<T>() const
+  {
+    return ArrayRef<T>(m_begin, this->size());
+  }
+
+  operator MutableArrayRef<T>()
+  {
+    return MutableArrayRef<T>(m_begin, this->size());
+  }
+
+  Vector &operator=(const Vector &other)
+  {
+    if (this == &other) {
+      return *this;
+    }
+
+    this->~Vector();
+    new (this) Vector(other);
+
+    return *this;
+  }
+
+  Vector &operator=(Vector &&other)
+  {
+    if (this == &other) {
+      return *this;
+    }
+
+    this->~Vector();
+    new (this) Vector(std::move(other));
+
+    return *this;
+  }
+
+  /**
+   * Make sure that enough memory is allocated to hold size elements.
+   * This won't necessarily make an allocation when size is small.
+   * The actual size of the vector does not change.
+   */
+  void reserve(uint size)
+  {
+    this->grow(size);
+  }
+
+  /**
+   * Afterwards the vector has 0 elements, but will still have
+   * memory to be refilled again.
+   */
+  void clear()
+  {
+    destruct_n(m_begin, this->size());
+    m_end = m_begin;
+    UPDATE_VECTOR_SIZE(this);
+  }
+
+  /**
+   * Afterwards the vector has 0 elements and any allocated memory
+   * will be freed.
+   */
+  void clear_and_make_small()
+  {
+    destruct_n(m_begin, this->size());
+    if (!this->is_small()) {
+      m_allocator.deallocate(m_begin);
+    }
+
+    m_begin = this->small_buffer();
+    m_end = m_begin;
+    m_capacity_end = m_begin + N;
+    UPDATE_VECTOR_SIZE(this);
+  }
+
+  /**
+   * Insert a new element at the end of the vector.
+   * This might cause a reallocation with the capacity is exceeded.
+   */
+  void append(const T &value)
+  {
+    this->ensure_space_for_one();
+    this->append_unchecked(value);
+  }
+
+  void append(T &&value)
+  {
+    this->ensure_space_for_one();
+    this->append_unchecked(std::move(value));
+  }
+
+  void append_unchecked(const T &value)
+  {
+    BLI_assert(m_end < m_capacity_end);
+    new (m_end) T(value);
+    m_end++;
+    UPDATE_VECTOR_SIZE(this);
+  }
+
+  void append_unchecked(T &&value)
+  {
+    BLI_assert(m_end < m_capacity_end);
+    new (m_end) T(std::move(value));
+    m_end++;
+    UPDATE_VECTOR_SIZE(this);
+  }
+
+  /**
+   * Insert the same element n times at the end of the vector.
+   * This might result in a reallocation internally.
+   */
+  void append_n_times(const T &value, uint n)
+  {
+    this->reserve(this->size() + n);
+    BLI::uninitialized_fill_n(m_end, n, value);
+    this->increase_size_unchecked(n);
+  }
+
+  void increase_size_unchecked(uint n)
+  {
+    BLI_assert(m_end + n <= m_capacity_end);
+    m_end += n;
+    UPDATE_VECTOR_SIZE(this);
+  }
+
+  /**
+   * Copy the elements of another array to the end of this vector.
+   */
+  void extend(ArrayRef<T> array)
+  {
+    this->extend(array.begin(), array.size());
+  }
+
+  void extend(const T *start, uint amount)
+  {
+    this->reserve(this->size() + amount);
+    this->extend_unchecked(start, amount);
+  }
+
+  void extend_unchecked(ArrayRef<T> array)
+  {
+    this->extend_unchecked(array.begin(), array.size());
+  }
+
+  void extend_unchecked(const T *start, uint amount)
+  {
+    BLI_assert(m_begin + amount <= m_capacity_end);
+    BLI::uninitialized_copy_n(start, amount, m_end);
+    m_end += amount;
+    UPDATE_VECTOR_SIZE(this);
+  }
+
+  /**
+   * Return a reference to the last element in the vector.
+   * This will assert when the vector is empty.
+   */
+  const T &last() const
+  {
+    BLI_assert(this->size() > 0);
+    return *(m_end - 1);
+  }
+
+  T &last()
+  {
+    BLI_assert(this->size() > 0);
+    return *(m_end - 1);
+  }
+
+  /**
+   * Replace every element with a new value.
+   */
+  void fill(const T &value)
+  {
+    std::fill(m_begin, m_end, value);
+  }
+
+  void fill_indices(ArrayRef<uint> indices, const T &value)
+  {
+    MutableArrayRef<T>(*this).fill_indices(indices, value);
+  }
+
+  /**
+   * Return how many values are currently stored in the vector.
+   */
+  uint size() const
+  {
+    BLI_assert(m_debug_size == m_end - m_begin);
+    return m_end - m_begin;
+  }
+
+  /**
+   * Returns true when the vector contains no elements, otherwise false.
+   */
+  bool empty() const
+  {
+    return m_begin == m_end;
+  }
+
+  /**
+   * Deconstructs the last element and decreases the size by one.
+   * This will assert when the vector is empty.
+   */
+  void remove_last()
+  {
+    BLI_assert(!this->empty());
+    m_end--;
+    destruct(m_end);
+    UPDATE_VECTOR_SIZE(this);
+  }
+
+  /**
+   * Remove the last element from the vector and return it.
+   */
+  T pop_last()
+  {
+    BLI_assert(!this->empty());
+    m_end--;
+    T value = *m_end;
+    destruct(m_end);
+    UPDATE_VECTOR_SIZE(this);
+    return value;
+  }
+
+  /**
+   * Delete any element in the vector.
+   * The empty space will be filled by the previously last element.
+   */
+  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 = *m_end;
+    }
+    destruct(m_end);
+    UPDATE_VECTOR_SIZE(this);
+  }
+
+  /**
+   * Do a linear search to find the value in the vector.
+   * When found, return the first index, otherwise return -1.
+   */
+  int index(const T &value) const
+  {
+    for (T *current = m_begin; current != m_end; current++) {
+      if (*current == value) {
+        return current - m_begin;
+      }
+    }
+    return -1;
+  }
+
+  /**
+   * Do a linear search to see of the value is in the vector.
+   * Return true when it exists, otherwise false.
+   */
+  bool contains(const T &value) const
+  {
+    return this->index(value) != -1;
+  }
+
+  /**
+   * Compare vectors element-wise.
+   * Return true when they have the same length and all elements
+   * compare equal, otherwise false.
+   */
+  static bool all_equal(const Vector &a, const Vector &b)
+  {
+    if (a.size() != b.size()) {
+      return false;
+    }
+    for (uint i = 0; i < a.size(); i++) {
+      if (a[i] != b[i]) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  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];
+  }
+
+  T *begin()
+  {
+    return m_begin;
+  }
+  T *end()
+  {
+    return m_end;
+  }
+
+  const T *begin() const
+  {
+    return m_begin;
+  }
+  const T *end() const
+  {
+    return m_end;
+  }
+
+  void print_stats() const
+  {
+    std::cout << "Small Vector at " << (void *)this << ":" << std::endl;
+    std::cout << "  Elements: " << this->size() << std::endl;
+    std::cout << "  Capacity: " << (m_capacity_end - m_begin) << std::endl;
+    std::cout << "  Small Elements: " << N << "  Size on Stack: " << sizeof(*this) << std::endl;
+  }
+
+ private:
+  T *small_buffer() const
+  {
+    return (T *)m_small_buffer;
+  }
+
+  bool is_small() const
+  {
+    return m_begin == this->small_buffer();
+  }
+
+  void ensure_space_for_one()
+  {
+    if (UNLIKELY(m_end >= m_capacity_end)) {
+      this->grow(std::max(this->size() * 2, (uint)1));
+    }
+  }
+
+  uint capacity() const
+  {
+    return m_capacity_end - m_begin;
+  }
+
+  BLI_NOINLINE void grow(uint min_capacity)
+  {
+    if (this->capacity() >= min_capacity) {
+      return;
+    }
+
+    /* Round up to the next power of two. Otherwise consecutive calls to grow can cause a
+     * reallocation every time even though the min_capacity only increments. */
+    min_capacity = power_of_2_max_u(min_capacity);
+    uint size = this->size();
+
+    T *new_array = (T *)m_allocator.allocate_aligned(
+        min_capacity * sizeof(T), std::alignment_of<T>::value, __func__);
+    uninitialized_relocate_n(m_begin, size, new_array);
+
+    if (!this->is_small()) {
+      m_allocator.deallocate(m_begin);
+    }
+
+    m_begin = new_array;
+    m_end = m_begin + size;
+    m_capacity_end = m_begin + min_capacity;
+  }
+
+  /**
+   * Initialize all properties, except for m_allocator, which has to be initialized beforehand.
+   */
+  template<uint OtherN> void init_copy_from_other_vector(const Vector<T, OtherN, Allocator> &other)
+  {
+    m_allocator = other.m_allocator;
+
+    uint size = other.size();
+    uint capacity = size;
+
+    if (size <= N) {
+      m_begin = this->small_buffer();
+      capacity = N;
+    }
+    else {
+      m_begin = (T *)m_allocator.allocate_aligned(
+          sizeof(T) * size, std::alignment_of<T>::value, __func__);
+      capacity = size;
+    }
+
+    m_end = m_begin + size;
+    m_capacity_end = m_begin + capacity;
+
+    uninitialized_copy(other.begin(), other.end(), m_begin);
+    UPDATE_VECTOR_SIZE(this);
+  }
+};
+
+#undef UPDATE_VECTOR_SIZE
+
+template<typename T, uint N = 4> using TemporaryVector = Vector<T, N, TemporaryAllocator>;
+
+} /* namespace BLI */
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 73652e18a56..b4db305ccd4 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -44,6 +44,7 @@ set(SRC
   intern/BLI_ghash_utils.c
   intern/BLI_heap.c
   intern/BLI_heap_simple.c
+  intern/BLI_index_range.cc
   intern/BLI_kdopbvh.c
   intern/BLI_linklist.c
   intern/BLI_linklist_lockfree.c
@@ -51,6 +52,7 @@ set(SRC
   intern/BLI_memblock.c
   intern/BLI_memiter.c
   intern/BLI_mempool.c
+  intern/BLI_temporary_allocator.cc
   intern/BLI_timer.c
   intern/DLRB_tree.c
   intern/array_store.c
@@ -131,9 +133,14 @@ set(SRC
   intern/kdtree_impl.h
   intern/list_sort_impl.h
 
+
+
   BLI_alloca.h
+  BLI_allocator.h
   BLI_args.h
   BLI_array.h
+  BLI_array_cxx.h
+  BLI_array_ref.h
   BLI_array_store.h
   BLI_array_store_utils.h
   BLI_array_utils.h
@@ -170,6 +177,7 @@ set(SRC
   BLI_hash_mm3.h
   BLI_heap.h
   BLI_heap_simple.h
+  BLI_index_range.h
   BLI_iterator.h
   BLI_jitter_2d.h
   BLI_kdopbvh.h
@@ -181,6 +189,7 @@ set(SRC
   BLI_linklist_lockfree.h
   BLI_linklist_stack.h
   BLI_listbase.h
+  BLI_listbase_wrapper.h
   BLI_math.h
   BLI_math_base.h
   BLI_math_bits.h
@@ -198,6 +207,7 @@ set(SRC
   BLI_memblock.h
   BLI_memiter.h
   BLI_memory_utils.h
+  BLI_memory_utils_cxx.h
   BLI_mempool.h
   BLI_noise.h
   BLI_path_util.h
@@ -211,6 +221,7 @@ set(SRC
   BLI_sort.h
   BLI_sort_utils.h
   BLI_stack.h
+  BLI_stack_cxx.h
   BLI_strict_flags.h
   BLI_string.h
   BLI_string_cursor_utf8.h
@@ -219,6 +230,8 @@ set(SRC
   BLI_sys_types.h
   BLI_system.h
   BLI_task.h
+  BLI_temporary_allocator.h
+  BLI_temporary_allocator_cxx.h
   BLI_threads.h
   BLI_timecode.h
   BLI_timer.h
@@ -227,6 +240,7 @@ set(SRC
   BLI_utildefines_stack.h
   BLI_utildefines_variadic.h
   BLI_uvproject.h
+  BLI_vector.h
   BLI_vfontdata.h
   BLI_voronoi_2d.h
   BLI_voxel.h
diff --git a/source/blender/blenlib/intern/BLI_index_range.cc b/source/blender/blenlib/intern/BLI_index_range.cc
new file mode 100644
index 00000000000..7d11dd2e354
--- /dev/null
+++ b/source/blender/blenlib/intern/BLI_index_range.cc
@@ -0,0 +1,59 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include <mutex>
+
+#include "BLI_index_range.h"
+#include "BLI_array_ref.h"
+#include "BLI_array_cxx.h"
+#include "BLI_vector.h"
+
+namespace BLI {
+
+static Vector<Array<uint, RawAllocator>, 0, RawAllocator> arrays;
+static uint current_array_size = 0;
+static uint *current_array = nullptr;
+static std::mutex current_array_mutex;
+
+ArrayRef<uint> IndexRange::as_array_ref() const
+{
+  uint min_required_size = m_start + m_size;
+
+  if (min_required_size <= current_array_size) {
+    return ArrayRef<uint>(current_array + m_start, m_size);
+  }
+
+  std::lock_guard<std::mutex> lock(current_array_mutex);
+
+  if (min_required_size <= current_array_size) {
+    return ArrayRef<uint>(current_array + m_start, m_size);
+  }
+
+  uint new_size = std::max<uint>(1000, power_of_2_max_u(min_required_size));
+  Array<uint, RawAllocator> new_array(new_size);
+  for (uint i = 0; i < new_size; i++) {
+    new_array[i] = i;
+  }
+  arrays.append(std::move(new_array));
+
+  current_array = arrays.last().begin();
+  std::atomic_thread_fence(std::memory_order_seq_cst);
+  current_array_size = new_size;
+
+  return ArrayRef<uint>(current_array + m_start, m_size);
+}
+
+}  // namespace BLI
diff --git a/source/blender/blenlib/intern/BLI_temporary_allocator.cc b/source/blender/blenlib/intern/BLI_temporary_allocator.cc
new file mode 100644
index 00000000000..e41cf36f66d
--- /dev/null
+++ b/source/blender/blenlib/intern/BLI_temporary_allocator.cc
@@ -0,0 +1,115 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include <mutex>
+#include <stack>
+
+#include "BLI_temporary_allocator.h"
+#include "BLI_stack_cxx.h"
+
+using namespace BLI;
+
+constexpr uint ALIGNMENT = BLI_TEMPORARY_BUFFER_ALIGNMENT;
+constexpr uint SMALL_BUFFER_SIZE = 64 * 1024;
+constexpr uintptr_t ALIGNMENT_MASK = ~(uintptr_t)(ALIGNMENT - 1);
+
+enum TemporaryBufferType {
+  Small,
+  Large,
+};
+
+struct MemHead {
+  void *raw_ptr;
+  TemporaryBufferType type;
+};
+
+static MemHead &get_memhead(void *aligned_ptr)
+{
+  return *((MemHead *)aligned_ptr - 1);
+}
+
+static void *raw_allocate(uint size)
+{
+  uint total_allocation_size = size + ALIGNMENT + sizeof(MemHead);
+
+  uintptr_t raw_ptr = (uintptr_t)malloc(total_allocation_size);
+  uintptr_t aligned_ptr = (raw_ptr + ALIGNMENT + sizeof(MemHead)) & ALIGNMENT_MASK;
+
+  MemHead &memhead = get_memhead((void *)aligned_ptr);
+  memhead.raw_ptr = (void *)raw_ptr;
+  return (void *)aligned_ptr;
+}
+
+static void raw_deallocate(void *ptr)
+{
+  BLI_assert(((uintptr_t)ptr & ~ALIGNMENT_MASK) == 0);
+  MemHead &memhead = get_memhead(ptr);
+  void *raw_ptr = memhead.raw_ptr;
+  free(raw_ptr);
+}
+
+struct ThreadLocalBuffers {
+  uint allocated_amount = 0;
+  Stack<void *, 32, RawAllocator> buffers;
+
+  ~ThreadLocalBuffers()
+  {
+    for (void *ptr : buffers) {
+      raw_deallocate(ptr);
+    }
+  }
+};
+
+thread_local ThreadLocalBuffers local_storage;
+
+void *BLI_temporary_allocate(uint size)
+{
+  /* The total amount of allocated buffers using this allocator should be limited by a constant. If
+   * it grows unbounded, there is likely a memory leak somewhere. */
+  BLI_assert(local_storage.allocated_amount < 100);
+
+  if (size <= SMALL_BUFFER_SIZE) {
+    auto &buffers = local_storage.buffers;
+    if (buffers.empty()) {
+      void *ptr = raw_allocate(SMALL_BUFFER_SIZE);
+      MemHead &memhead = get_memhead(ptr);
+      memhead.type = TemporaryBufferType::Small;
+      local_storage.allocated_amount++;
+      return ptr;
+    }
+    else {
+      return buffers.pop();
+    }
+  }
+  else {
+    void *ptr = raw_allocate(size);
+    MemHead &memhead = get_memhead(ptr);
+    memhead.type = TemporaryBufferType::Large;
+    return ptr;
+  }
+}
+
+void BLI_temporary_deallocate(void *buffer)
+{
+  MemHead &memhead = get_memhead(buffer);
+  if (memhead.type == TemporaryBufferType::Small) {
+    auto &buffers = local_storage.buffers;
+    buffers.push(buffer);
+  }
+  else {
+    raw_deallocate(buffer);
+  }
+}
diff --git a/tests/gtests/blenlib/BLI_array_ref_test.cc b/tests/gtests/blenlib/BLI_array_ref_test.cc
new file mode 100644
index 00000000000..4507d9e6e84
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_array_ref_test.cc
@@ -0,0 +1,266 @@
+#include "testing/testing.h"
+#include "BLI_array_ref.h"
+#include "BLI_vector.h"
+
+using BLI::IndexRange;
+using IntVector = BLI::Vector<int>;
+using IntArrayRef = BLI::ArrayRef<int>;
+using MutableIntArrayRef = BLI::MutableArrayRef<int>;
+
+TEST(array_ref, FromSmallVector)
+{
+  IntVector a = {1, 2, 3};
+  IntArrayRef a_ref = a;
+  EXPECT_EQ(a_ref.size(), 3);
+  EXPECT_EQ(a_ref[0], 1);
+  EXPECT_EQ(a_ref[1], 2);
+  EXPECT_EQ(a_ref[2], 3);
+}
+
+TEST(array_ref, IsReferencing)
+{
+  int array[] = {3, 5, 8};
+  MutableIntArrayRef ref(array, ARRAY_SIZE(array));
+  EXPECT_EQ(ref.size(), 3);
+  EXPECT_EQ(ref[1], 5);
+  array[1] = 10;
+  EXPECT_EQ(ref[1], 10);
+}
+
+TEST(array_ref, DropBack)
+{
+  IntVector a = {4, 5, 6, 7};
+  auto slice = IntArrayRef(a).drop_back(2);
+  EXPECT_EQ(slice.size(), 2);
+  EXPECT_EQ(slice[0], 4);
+  EXPECT_EQ(slice[1], 5);
+}
+
+TEST(array_ref, DropBackAll)
+{
+  IntVector a = {4, 5, 6, 7};
+  auto slice = IntArrayRef(a).drop_back(a.size());
+  EXPECT_EQ(slice.size(), 0);
+}
+
+TEST(array_ref, DropFront)
+{
+  IntVector a = {4, 5, 6, 7};
+  auto slice = IntArrayRef(a).drop_front(1);
+  EXPECT_EQ(slice.size(), 3);
+  EXPECT_EQ(slice[0], 5);
+  EXPECT_EQ(slice[1], 6);
+  EXPECT_EQ(slice[2], 7);
+}
+
+TEST(array_ref, DropFrontAll)
+{
+  IntVector a = {4, 5, 6, 7};
+  auto slice = IntArrayRef(a).drop_front(a.size());
+  EXPECT_EQ(slice.size(), 0);
+}
+
+TEST(array_ref, TakeFront)
+{
+  IntVector a = {4, 5, 6, 7};
+  auto slice = IntArrayRef(a).take_front(2);
+  EXPECT_EQ(slice.size(), 2);
+  EXPECT_EQ(slice[0], 4);
+  EXPECT_EQ(slice[1], 5);
+}
+
+TEST(array_ref, TakeBack)
+{
+  IntVector a = {5, 6, 7, 8};
+  auto slice = IntArrayRef(a).take_back(2);
+  EXPECT_EQ(slice.size(), 2);
+  EXPECT_EQ(slice[0], 7);
+  EXPECT_EQ(slice[1], 8);
+}
+
+TEST(array_ref, Slice)
+{
+  IntVector a = {4, 5, 6, 7};
+  auto slice = IntArrayRef(a).slice(1, 2);
+  EXPECT_EQ(slice.size(), 2);
+  EXPECT_EQ(slice[0], 5);
+  EXPECT_EQ(slice[1], 6);
+}
+
+TEST(array_ref, SliceEmpty)
+{
+  IntVector a = {4, 5, 6, 7};
+  auto slice = IntArrayRef(a).slice(2, 0);
+  EXPECT_EQ(slice.size(), 0);
+}
+
+TEST(array_ref, SliceRange)
+{
+  IntVector a = {1, 2, 3, 4, 5};
+  auto slice = IntArrayRef(a).slice(IndexRange(2, 2));
+  EXPECT_EQ(slice.size(), 2);
+  EXPECT_EQ(slice[0], 3);
+  EXPECT_EQ(slice[1], 4);
+}
+
+TEST(array_ref, Contains)
+{
+  IntVector a = {4, 5, 6, 7};
+  IntArrayRef a_ref = a;
+  EXPECT_TRUE(a_ref.contains(4));
+  EXPECT_TRUE(a_ref.contains(5));
+  EXPECT_TRUE(a_ref.contains(6));
+  EXPECT_TRUE(a_ref.contains(7));
+  EXPECT_FALSE(a_ref.contains(3));
+  EXPECT_FALSE(a_ref.contains(8));
+}
+
+TEST(array_ref, Count)
+{
+  IntVector a = {2, 3, 4, 3, 3, 2, 2, 2, 2};
+  IntArrayRef a_ref = a;
+  EXPECT_EQ(a_ref.count(1), 0);
+  EXPECT_EQ(a_ref.count(2), 5);
+  EXPECT_EQ(a_ref.count(3), 3);
+  EXPECT_EQ(a_ref.count(4), 1);
+  EXPECT_EQ(a_ref.count(5), 0);
+}
+
+TEST(array_ref, ToSmallVector)
+{
+  IntVector a = {1, 2, 3, 4};
+  IntArrayRef a_ref = a;
+  IntVector b = a_ref;
+  IntVector::all_equal(a, b);
+}
+
+static void test_ref_from_initializer_list(IntArrayRef ref)
+{
+  EXPECT_EQ(ref.size(), 4);
+  EXPECT_EQ(ref[0], 3);
+  EXPECT_EQ(ref[1], 6);
+  EXPECT_EQ(ref[2], 8);
+  EXPECT_EQ(ref[3], 9);
+}
+
+TEST(array_ref, FromInitializerList)
+{
+  test_ref_from_initializer_list({3, 6, 8, 9});
+}
+
+TEST(array_ref, FromVector)
+{
+  std::vector<int> a = {1, 2, 3, 4};
+  IntArrayRef a_ref(a);
+  EXPECT_EQ(a_ref.size(), 4);
+  EXPECT_EQ(a_ref[0], 1);
+  EXPECT_EQ(a_ref[1], 2);
+  EXPECT_EQ(a_ref[2], 3);
+  EXPECT_EQ(a_ref[3], 4);
+}
+
+TEST(array_ref, FromArray)
+{
+  std::array<int, 2> a = {5, 6};
+  IntArrayRef a_ref(a);
+  EXPECT_EQ(a_ref.size(), 2);
+  EXPECT_EQ(a_ref[0], 5);
+  EXPECT_EQ(a_ref[1], 6);
+}
+
+TEST(array_ref, Fill)
+{
+  std::array<int, 5> a = {4, 5, 6, 7, 8};
+  MutableIntArrayRef a_ref(a);
+  a_ref.fill(1);
+  EXPECT_EQ(a[0], 1);
+  EXPECT_EQ(a[1], 1);
+  EXPECT_EQ(a[2], 1);
+  EXPECT_EQ(a[3], 1);
+  EXPECT_EQ(a[4], 1);
+}
+
+TEST(array_ref, FillIndices)
+{
+  std::array<int, 5> a = {0, 0, 0, 0, 0};
+  MutableIntArrayRef a_ref(a);
+  a_ref.fill_indices({0, 2, 3}, 1);
+  EXPECT_EQ(a[0], 1);
+  EXPECT_EQ(a[1], 0);
+  EXPECT_EQ(a[2], 1);
+  EXPECT_EQ(a[3], 1);
+  EXPECT_EQ(a[4], 0);
+}
+
+TEST(array_ref, CopyFrom)
+{
+  std::array<int, 3> a = {3, 4, 5};
+  MutableIntArrayRef a_ref(a);
+  EXPECT_EQ(a[0], 3);
+  EXPECT_EQ(a[1], 4);
+  EXPECT_EQ(a[2], 5);
+  a_ref.copy_from({1, 2, 3});
+  EXPECT_EQ(a[0], 1);
+  EXPECT_EQ(a[1], 2);
+  EXPECT_EQ(a[2], 3);
+}
+
+TEST(array_ref, ByteSize)
+{
+  std::array<int, 10> a;
+  IntArrayRef a_ref(a);
+  EXPECT_EQ(a_ref.byte_size(), sizeof(a));
+  EXPECT_EQ(a_ref.byte_size(), 40);
+}
+
+TEST(array_ref, CopyTo)
+{
+  std::array<int, 3> a = {5, 6, 7};
+  int b[3] = {0};
+  IntArrayRef a_ref(a);
+  a_ref.copy_to(b);
+
+  EXPECT_EQ(b[0], 5);
+  EXPECT_EQ(b[1], 6);
+  EXPECT_EQ(b[2], 7);
+}
+
+TEST(array_ref, FirstLast)
+{
+  std::array<int, 4> a = {6, 7, 8, 9};
+  IntArrayRef a_ref(a);
+  EXPECT_EQ(a_ref.first(), 6);
+  EXPECT_EQ(a_ref.last(), 9);
+}
+
+TEST(array_ref, FirstLast_OneElement)
+{
+  int a = 3;
+  IntArrayRef a_ref(&a, 1);
+  EXPECT_EQ(a_ref.first(), 3);
+  EXPECT_EQ(a_ref.last(), 3);
+}
+
+TEST(array_ref, Get)
+{
+  std::array<int, 3> a = {5, 6, 7};
+  IntArrayRef a_ref(a);
+  EXPECT_EQ(a_ref.get(0, 42), 5);
+  EXPECT_EQ(a_ref.get(1, 42), 6);
+  EXPECT_EQ(a_ref.get(2, 42), 7);
+  EXPECT_EQ(a_ref.get(3, 42), 42);
+  EXPECT_EQ(a_ref.get(4, 42), 42);
+}
+
+TEST(array_ref, ContainsPtr)
+{
+  std::array<int, 3> a = {5, 6, 7};
+  int other = 10;
+  IntArrayRef a_ref(a);
+  EXPECT_TRUE(a_ref.contains_ptr(&a[0] + 0));
+  EXPECT_TRUE(a_ref.contains_ptr(&a[0] + 1));
+  EXPECT_TRUE(a_ref.contains_ptr(&a[0] + 2));
+  EXPECT_FALSE(a_ref.contains_ptr(&a[0] + 3));
+  EXPECT_FALSE(a_ref.contains_ptr(&a[0] - 1));
+  EXPECT_FALSE(a_ref.contains_ptr(&other));
+}
diff --git a/tests/gtests/blenlib/BLI_array_test.cc b/tests/gtests/blenlib/BLI_array_test.cc
new file mode 100644
index 00000000000..33f84928d3d
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_array_test.cc
@@ -0,0 +1,103 @@
+#include "testing/testing.h"
+#include "BLI_array_cxx.h"
+
+using namespace BLI;
+
+TEST(array, DefaultConstructor)
+{
+  Array<int> array;
+  EXPECT_EQ(array.size(), 0);
+}
+
+TEST(array, SizeConstructor)
+{
+  Array<int> array(5);
+  EXPECT_EQ(array.size(), 5);
+}
+
+TEST(array, FillConstructor)
+{
+  Array<int> array(5, 8);
+  EXPECT_EQ(array.size(), 5);
+  EXPECT_EQ(array[0], 8);
+  EXPECT_EQ(array[1], 8);
+  EXPECT_EQ(array[2], 8);
+  EXPECT_EQ(array[3], 8);
+  EXPECT_EQ(array[4], 8);
+}
+
+TEST(array, InitializerListConstructor)
+{
+  Array<int> array = {4, 5, 6, 7};
+  EXPECT_EQ(array.size(), 4);
+  EXPECT_EQ(array[0], 4);
+  EXPECT_EQ(array[1], 5);
+  EXPECT_EQ(array[2], 6);
+  EXPECT_EQ(array[3], 7);
+}
+
+TEST(array, ArrayRefConstructor)
+{
+  int stackarray[4] = {6, 7, 8, 9};
+  ArrayRef<int> array_ref(stackarray, ARRAY_SIZE(stackarray));
+  Array<int> array(array_ref);
+  EXPECT_EQ(array.size(), 4);
+  EXPECT_EQ(array[0], 6);
+  EXPECT_EQ(array[1], 7);
+  EXPECT_EQ(array[2], 8);
+  EXPECT_EQ(array[3], 9);
+}
+
+TEST(array, CopyConstructor)
+{
+  Array<int> array = {5, 6, 7, 8};
+  Array<int> new_array(array);
+
+  EXPECT_EQ(array.size(), 4);
+  EXPECT_EQ(new_array.size(), 4);
+  EXPECT_NE(array.begin(), new_array.begin());
+  EXPECT_EQ(new_array[0], 5);
+  EXPECT_EQ(new_array[1], 6);
+  EXPECT_EQ(new_array[2], 7);
+  EXPECT_EQ(new_array[3], 8);
+}
+
+TEST(array, MoveConstructor)
+{
+  Array<int> array = {5, 6, 7, 8};
+  Array<int> new_array(std::move(array));
+
+  EXPECT_EQ(array.size(), 0);
+  EXPECT_EQ(new_array.size(), 4);
+  EXPECT_EQ(new_array[0], 5);
+  EXPECT_EQ(new_array[1], 6);
+  EXPECT_EQ(new_array[2], 7);
+  EXPECT_EQ(new_array[3], 8);
+}
+
+TEST(array, CopyAssignment)
+{
+  Array<int> array = {1, 2, 3};
+  Array<int> new_array = {4};
+  EXPECT_EQ(new_array.size(), 1);
+  new_array = array;
+  EXPECT_EQ(new_array.size(), 3);
+  EXPECT_EQ(array.size(), 3);
+  EXPECT_NE(array.begin(), new_array.begin());
+  EXPECT_EQ(new_array[0], 1);
+  EXPECT_EQ(new_array[1], 2);
+  EXPECT_EQ(new_array[2], 3);
+}
+
+TEST(array, MoveAssignment)
+{
+  Array<int> array = {1, 2, 3};
+  Array<int> new_array = {4};
+  EXPECT_EQ(new_array.size(), 1);
+  new_array = std::move(array);
+  EXPECT_EQ(new_array.size(), 3);
+  EXPECT_EQ(array.size(), 0);
+  EXPECT_EQ(new_array[0], 1);
+  EXPECT_EQ(new_array[1], 2);
+  EXPECT_EQ(new_array[2], 3);
+}
diff --git a/tests/gtests/blenlib/BLI_index_range_test.cc b/tests/gtests/blenlib/BLI_index_range_test.cc
new file mode 100644
index 00000000000..1944279999d
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_index_range_test.cc
@@ -0,0 +1,131 @@
+#include "testing/testing.h"
+#include "BLI_index_range.h"
+#include "BLI_vector.h"
+
+using BLI::ArrayRef;
+using BLI::IndexRange;
+using IntVector = BLI::Vector<int>;
+
+TEST(index_range, DefaultConstructor)
+{
+  IndexRange range;
+  EXPECT_EQ(range.size(), 0);
+
+  IntVector vector;
+  for (int value : range) {
+    vector.append(value);
+  }
+  EXPECT_EQ(vector.size(), 0);
+}
+
+TEST(index_range, SingleElementRange)
+{
+  IndexRange range(4, 1);
+  EXPECT_EQ(range.size(), 1);
+  EXPECT_EQ(*range.begin(), 4);
+
+  IntVector vector;
+  for (int value : range) {
+    vector.append(value);
+  }
+
+  EXPECT_EQ(vector.size(), 1);
+  EXPECT_EQ(vector[0], 4);
+}
+
+TEST(index_range, MultipleElementRange)
+{
+  IndexRange range(6, 4);
+  EXPECT_EQ(range.size(), 4);
+
+  IntVector vector;
+  for (int value : range) {
+    vector.append(value);
+  }
+
+  EXPECT_EQ(vector.size(), 4);
+  for (uint i = 0; i < 4; i++) {
+    EXPECT_EQ(vector[i], i + 6);
+  }
+}
+
+TEST(index_range, SubscriptOperator)
+{
+  IndexRange range(5, 5);
+  EXPECT_EQ(range[0], 5);
+  EXPECT_EQ(range[1], 6);
+  EXPECT_EQ(range[2], 7);
+}
+
+TEST(index_range, Before)
+{
+  IndexRange range = IndexRange(5, 5).before(3);
+  EXPECT_EQ(range[0], 2);
+  EXPECT_EQ(range[1], 3);
+  EXPECT_EQ(range[2], 4);
+  EXPECT_EQ(range.size(), 3);
+}
+
+TEST(index_range, After)
+{
+  IndexRange range = IndexRange(5, 5).after(4);
+  EXPECT_EQ(range[0], 10);
+  EXPECT_EQ(range[1], 11);
+  EXPECT_EQ(range[2], 12);
+  EXPECT_EQ(range[3], 13);
+  EXPECT_EQ(range.size(), 4);
+}
+
+TEST(index_range, Contains)
+{
+  IndexRange range = IndexRange(5, 3);
+  EXPECT_TRUE(range.contains(5));
+  EXPECT_TRUE(range.contains(6));
+  EXPECT_TRUE(range.contains(7));
+  EXPECT_FALSE(range.contains(4));
+  EXPECT_FALSE(range.contains(8));
+}
+
+TEST(index_range, First)
+{
+  IndexRange range = IndexRange(5, 3);
+  EXPECT_EQ(range.first(), 5);
+}
+
+TEST(index_range, Last)
+{
+  IndexRange range = IndexRange(5, 3);
+  EXPECT_EQ(range.last(), 7);
+}
+
+TEST(index_range, OneAfterEnd)
+{
+  IndexRange range = IndexRange(5, 3);
+  EXPECT_EQ(range.one_after_last(), 8);
+}
+
+TEST(index_range, Start)
+{
+  IndexRange range = IndexRange(6, 2);
+  EXPECT_EQ(range.start(), 6);
+}
+
+TEST(index_range, Slice)
+{
+  IndexRange range = IndexRange(5, 15);
+  IndexRange slice = range.slice(2, 6);
+  EXPECT_EQ(slice.size(), 6);
+  EXPECT_EQ(slice.first(), 7);
+  EXPECT_EQ(slice.last(), 12);
+}
+
+TEST(index_range, AsArrayRef)
+{
+  IndexRange range = IndexRange(4, 6);
+  ArrayRef<uint> ref = range.as_array_ref();
+  EXPECT_EQ(ref.size(), 6);
+  EXPECT_EQ(ref[0], 4);
+  EXPECT_EQ(ref[1], 5);
+  EXPECT_EQ(ref[2], 6);
+  EXPECT_EQ(ref[3], 7);
+}
diff --git a/tests/gtests/blenlib/BLI_stack_cxx_test.cc b/tests/gtests/blenlib/BLI_stack_cxx_test.cc
new file mode 100644
index 00000000000..02c5407fda3
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_stack_cxx_test.cc
@@ -0,0 +1,52 @@
+#include "testing/testing.h"
+#include "BLI_stack_cxx.h"
+
+using IntStack = BLI::Stack<int>;
+
+TEST(stack, DefaultConstructor)
+{
+  IntStack stack;
+  EXPECT_EQ(stack.size(), 0);
+  EXPECT_TRUE(stack.empty());
+}
+
+TEST(stack, ArrayRefConstructor)
+{
+  std::array<int, 3> array = {4, 7, 2};
+  IntStack stack(array);
+  EXPECT_EQ(stack.size(), 3);
+  EXPECT_EQ(stack.pop(), 2);
+  EXPECT_EQ(stack.pop(), 7);
+  EXPECT_EQ(stack.pop(), 4);
+  EXPECT_TRUE(stack.empty());
+}
+
+TEST(stack, Push)
+{
+  IntStack stack;
+  EXPECT_EQ(stack.size(), 0);
+  stack.push(3);
+  EXPECT_EQ(stack.size(), 1);
+  stack.push(5);
+  EXPECT_EQ(stack.size(), 2);
+}
+
+TEST(stack, Pop)
+{
+  IntStack stack;
+  stack.push(4);
+  stack.push(6);
+  EXPECT_EQ(stack.pop(), 6);
+  EXPECT_EQ(stack.pop(), 4);
+}
+
+TEST(stack, Peek)
+{
+  IntStack stack;
+  stack.push(3);
+  stack.push(4);
+  EXPECT_EQ(stack.peek(), 4);
+  EXPECT_EQ(stack.peek(), 4);
+  stack.pop();
+  EXPECT_EQ(stack.peek(), 3);
+}
diff --git a/tests/gtests/blenlib/BLI_vector_test.cc b/tests/gtests/blenlib/BLI_vector_test.cc
new file mode 100644
index 00000000000..60f78025269
--- /dev/null
+++ b/tests/gtests/blenlib/BLI_vector_test.cc
@@ -0,0 +1,400 @@
+#include "testing/testing.h"
+#include "BLI_vector.h"
+#include <forward_list>
+
+using BLI::Vector;
+using IntVector = Vector<int>;
+
+TEST(vector, DefaultConstructor)
+{
+  IntVector vec;
+  EXPECT_EQ(vec.size(), 0);
+}
+
+TEST(vector, SizeConstructor)
+{
+  IntVector vec(3);
+  EXPECT_EQ(vec.size(), 3);
+  EXPECT_EQ(vec[0], 0);
+  EXPECT_EQ(vec[1], 0);
+  EXPECT_EQ(vec[2], 0);
+}
+
+TEST(vector, SizeValueConstructor)
+{
+  IntVector vec(4, 10);
+  EXPECT_EQ(vec.size(), 4);
+  EXPECT_EQ(vec[0], 10);
+  EXPECT_EQ(vec[1], 10);
+  EXPECT_EQ(vec[2], 10);
+  EXPECT_EQ(vec[3], 10);
+}
+
+TEST(vector, InitializerListConstructor)
+{
+  IntVector vec = {1, 3, 4, 6};
+  EXPECT_EQ(vec.size(), 4);
+  EXPECT_EQ(vec[0], 1);
+  EXPECT_EQ(vec[1], 3);
+  EXPECT_EQ(vec[2], 4);
+  EXPECT_EQ(vec[3], 6);
+}
+
+struct TestListValue {
+  TestListValue *next, *prev;
+  int value;
+};
+
+TEST(vector, IntrusiveListBaseConstructor)
+{
+  TestListValue *value1 = new TestListValue{0, 0, 4};
+  TestListValue *value2 = new TestListValue{0, 0, 5};
+  TestListValue *value3 = new TestListValue{0, 0, 6};
+
+  ListBase list = {NULL, NULL};
+  BLI_addtail(&list, value1);
+  BLI_addtail(&list, value2);
+  BLI_addtail(&list, value3);
+  Vector<TestListValue *> vec(list, true);
+
+  EXPECT_EQ(vec.size(), 3);
+  EXPECT_EQ(vec[0]->value, 4);
+  EXPECT_EQ(vec[1]->value, 5);
+  EXPECT_EQ(vec[2]->value, 6);
+
+  delete value1;
+  delete value2;
+  delete value3;
+}
+
+TEST(vector, ContainerConstructor)
+{
+  std::forward_list<int> list;
+  list.push_front(3);
+  list.push_front(1);
+  list.push_front(5);
+
+  IntVector vec = IntVector::FromContainer(list);
+  EXPECT_EQ(vec.size(), 3);
+  EXPECT_EQ(vec[0], 5);
+  EXPECT_EQ(vec[1], 1);
+  EXPECT_EQ(vec[2], 3);
+}
+
+TEST(vector, CopyConstructor)
+{
+  IntVector vec1 = {1, 2, 3};
+  IntVector vec2(vec1);
+  EXPECT_EQ(vec2.size(), 3);
+  EXPECT_EQ(vec2[0], 1);
+  EXPECT_EQ(vec2[1], 2);
+  EXPECT_EQ(vec2[2], 3);
+
+  vec1[1] = 5;
+  EXPECT_EQ(vec1[1], 5);
+  EXPECT_EQ(vec2[1], 2);
+}
+
+TEST(vector, CopyConstructor2)
+{
+  Vector<int, 2> vec1 = {1, 2, 3, 4};
+  Vector<int, 3> vec2(vec1);
+
+  EXPECT_EQ(vec1.size(), 4);
+  EXPECT_EQ(vec2.size(), 4);
+  EXPECT_NE(vec1.begin(), vec2.begin());
+  EXPECT_EQ(vec2[0], 1);
+  EXPECT_EQ(vec2[1], 2);
+  EXPECT_EQ(vec2[2], 3);
+  EXPECT_EQ(vec2[3], 4);
+}
+
+TEST(vector, CopyConstructor3)
+{
+  Vector<int, 20> vec1 = {1, 2, 3, 4};
+  Vector<int, 1> vec2(vec1);
+
+  EXPECT_EQ(vec1.size(), 4);
+  EXPECT_EQ(vec2.size(), 4);
+  EXPECT_NE(vec1.begin(), vec2.begin());
+  EXPECT_EQ(vec2[2], 3);
+}
+
+TEST(vector, CopyConstructor4)
+{
+  Vector<int, 5> vec1 = {1, 2, 3, 4};
+  Vector<int, 6> vec2(vec1);
+
+  EXPECT_EQ(vec1.size(), 4);
+  EXPECT_EQ(vec2.size(), 4);
+  EXPECT_NE(vec1.begin(), vec2.begin());
+  EXPECT_EQ(vec2[3], 4);
+}
+
+TEST(vector, MoveConstructor)
+{
+  IntVector vec1 = {1, 2, 3, 4};
+  IntVector vec2(std::move(vec1));
+
+  EXPECT_EQ(vec1.size(), 0);
+  EXPECT_EQ(vec2.size(), 4);
+  EXPECT_EQ(vec2[0], 1);
+  EXPECT_EQ(vec2[1], 2);
+  EXPECT_EQ(vec2[2], 3);
+  EXPECT_EQ(vec2[3], 4);
+}
+
+TEST(vector, MoveConstructor2)
+{
+  Vector<int, 2> vec1 = {1, 2, 3, 4};
+  Vector<int, 3> vec2(std::move(vec1));
+
+  EXPECT_EQ(vec1.size(), 0);
+  EXPECT_EQ(vec2.size(), 4);
+  EXPECT_EQ(vec2[0], 1);
+  EXPECT_EQ(vec2[1], 2);
+  EXPECT_EQ(vec2[2], 3);
+  EXPECT_EQ(vec2[3], 4);
+}
+
+TEST(vector, MoveConstructor3)
+{
+  Vector<int, 20> vec1 = {1, 2, 3, 4};
+  Vector<int, 1> vec2(std::move(vec1));
+
+  EXPECT_EQ(vec1.size(), 0);
+  EXPECT_EQ(vec2.size(), 4);
+  EXPECT_EQ(vec2[2], 3);
+}
+
+TEST(vector, MoveConstructor4)
+{
+  Vector<int, 5> vec1 = {1, 2, 3, 4};
+  Vector<int, 6> vec2(std::move(vec1));
+
+  EXPECT_EQ(vec1.size(), 0);
+  EXPECT_EQ(vec2.size(), 4);
+  EXPECT_EQ(vec2[3], 4);
+}
+
+TEST(vector, MoveAssignment)
+{
+  IntVector vec = {1, 2};
+  EXPECT_EQ(vec.size(), 2);
+  EXPECT_EQ(vec[0], 1);
+  EXPECT_EQ(vec[1], 2);
+
+  vec = IntVector({5});
+  EXPECT_EQ(vec.size(), 1);
+  EXPECT_EQ(vec[0], 5);
+}
+
+TEST(vector, CopyAssignment)
+{
+  IntVector vec1 = {1, 2, 3};
+  IntVector vec2 = {4, 5};
+  EXPECT_EQ(vec1.size(), 3);
+  EXPECT_EQ(vec2.size(), 2);
+
+  vec2 = vec1;
+  EXPECT_EQ(vec2.size(), 3);
+
+  vec1[0] = 7;
+  EXPECT_EQ(vec1[0], 7);
+  EXPECT_EQ(vec2[0], 1);
+}
+
+TEST(vector, Append)
+{
+  IntVector vec;
+  vec.append(3);
+  vec.append(6);
+  vec.append(7);
+  EXPECT_EQ(vec.size(), 3);
+  EXPECT_EQ(vec[0], 3);
+  EXPECT_EQ(vec[1], 6);
+  EXPECT_EQ(vec[2], 7);
+}
+
+TEST(vector, Fill)
+{
+  IntVector vec(5);
+  vec.fill(3);
+  EXPECT_EQ(vec.size(), 5);
+  EXPECT_EQ(vec[0], 3);
+  EXPECT_EQ(vec[1], 3);
+  EXPECT_EQ(vec[2], 3);
+  EXPECT_EQ(vec[3], 3);
+  EXPECT_EQ(vec[4], 3);
+}
+
+TEST(vector, FillIndices)
+{
+  IntVector vec(5, 0);
+  vec.fill_indices({1, 2}, 4);
+  EXPECT_EQ(vec[0], 0);
+  EXPECT_EQ(vec[1], 4);
+  EXPECT_EQ(vec[2], 4);
+  EXPECT_EQ(vec[3], 0);
+  EXPECT_EQ(vec[4], 0);
+}
+
+TEST(vector, Iterator)
+{
+  IntVector vec({1, 4, 9, 16});
+  int i = 1;
+  for (int value : vec) {
+    EXPECT_EQ(value, i * i);
+    i++;
+  }
+}
+
+TEST(vector, BecomeLarge)
+{
+  Vector<int, 4> vec;
+  for (int i = 0; i < 100; i++) {
+    vec.append(i * 5);
+  }
+  EXPECT_EQ(vec.size(), 100);
+  for (int i = 0; i < 100; i++) {
+    EXPECT_EQ(vec[i], i * 5);
+  }
+}
+
+IntVector return_by_value_helper()
+{
+  return IntVector({3, 5, 1});
+}
+
+TEST(vector, ReturnByValue)
+{
+  IntVector vec = return_by_value_helper();
+  EXPECT_EQ(vec.size(), 3);
+  EXPECT_EQ(vec[0], 3);
+  EXPECT_EQ(vec[1], 5);
+  EXPECT_EQ(vec[2], 1);
+}
+
+TEST(vector, VectorOfVectors_Append)
+{
+  Vector<IntVector> vec;
+  EXPECT_EQ(vec.size(), 0);
+
+  IntVector v({1, 2});
+  vec.append(v);
+  vec.append({7, 8});
+  EXPECT_EQ(vec.size(), 2);
+  EXPECT_EQ(vec[0][0], 1);
+  EXPECT_EQ(vec[0][1], 2);
+  EXPECT_EQ(vec[1][0], 7);
+  EXPECT_EQ(vec[1][1], 8);
+}
+
+TEST(vector, VectorOfVectors_Fill)
+{
+  Vector<IntVector> vec(3);
+  vec.fill({4, 5});
+
+  EXPECT_EQ(vec[0][0], 4);
+  EXPECT_EQ(vec[0][1], 5);
+  EXPECT_EQ(vec[1][0], 4);
+  EXPECT_EQ(vec[1][1], 5);
+  EXPECT_EQ(vec[2][0], 4);
+  EXPECT_EQ(vec[2][1], 5);
+}
+
+TEST(vector, RemoveLast)
+{
+  IntVector vec = {5, 6};
+  EXPECT_EQ(vec.size(), 2);
+  vec.remove_last();
+  EXPECT_EQ(vec.size(), 1);
+  vec.remove_last();
+  EXPECT_EQ(vec.size(), 0);
+}
+
+TEST(vector, Empty)
+{
+  IntVector vec;
+  EXPECT_TRUE(vec.empty());
+  vec.append(1);
+  EXPECT_FALSE(vec.empty());
+  vec.remove_last();
+  EXPECT_TRUE(vec.empty());
+}
+
+TEST(vector, RemoveReorder)
+{
+  IntVector vec = {4, 5, 6, 7};
+  vec.remove_and_reorder(1);
+  EXPECT_EQ(vec[0], 4);
+  EXPECT_EQ(vec[1], 7);
+  EXPECT_EQ(vec[2], 6);
+  vec.remove_and_reorder(2);
+  EXPECT_EQ(vec[0], 4);
+  EXPECT_EQ(vec[1], 7);
+  vec.remove_and_reorder(0);
+  EXPECT_EQ(vec[0], 7);
+  vec.remove_and_reorder(0);
+  EXPECT_TRUE(vec.empty());
+}
+
+TEST(vector, AllEqual_False)
+{
+  IntVector a = {1, 2, 3};
+  IntVector b = {1, 2, 4};
+  bool result = IntVector::all_equal(a, b);
+  EXPECT_FALSE(result);
+}
+
+TEST(vector, AllEqual_True)
+{
+  IntVector a = {4, 5, 6};
+  IntVector b = {4, 5, 6};
+  bool result = IntVector::all_equal(a, b);
+  EXPECT_TRUE(result);
+}
+
+TEST(vector, ExtendSmallVector)
+{
+  IntVector a = {2, 3, 4};
+  IntVector b = {11, 12};
+  b.extend(a);
+  EXPECT_EQ(b.size(), 5);
+  EXPECT_EQ(b[0], 11);
+  EXPECT_EQ(b[1], 12);
+  EXPECT_EQ(b[2], 2);
+  EXPECT_EQ(b[3], 3);
+  EXPECT_EQ(b[4], 4);
+}
+
+TEST(vector, ExtendArray)
+{
+  int array[] = {3, 4, 5, 6};
+
+  IntVector a;
+  a.extend(array, 2);
+
+  EXPECT_EQ(a.size(), 2);
+  EXPECT_EQ(a[0], 3);
+  EXPECT_EQ(a[1], 4);
+}
+
+TEST(vector, Last)
+{
+  IntVector a{3, 5, 7};
+  EXPECT_EQ(a.last(), 7);
+}
+
+TEST(vector, AppendNTimes)
+{
+  IntVector a;
+  a.append_n_times(5, 3);
+  a.append_n_times(2, 2);
+  EXPECT_EQ(a.size(), 5);
+  EXPECT_EQ(a[0], 5);
+  EXPECT_EQ(a[1], 5);
+  EXPECT_EQ(a[2], 5);
+  EXPECT_EQ(a[3], 2);
+  EXPECT_EQ(a[4], 2);
+}
diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt
index 4e5811d140e..d2d7b76df6c 100644
--- a/tests/gtests/blenlib/CMakeLists.txt
+++ b/tests/gtests/blenlib/CMakeLists.txt
@@ -38,15 +38,18 @@ else()
   set(BLI_path_util_extra_libs "bf_blenlib;extern_wcwidth;${ZLIB_LIBRARIES}")
 endif()
 
+BLENDER_TEST(BLI_array "bf_blenlib")
+BLENDER_TEST(BLI_array_ref "bf_blenlib")
 BLENDER_TEST(BLI_array_store "bf_blenlib")
 BLENDER_TEST(BLI_array_utils "bf_blenlib")
 BLENDER_TEST(BLI_delaunay_2d "bf_blenlib")
-BLENDER_TEST(BLI_expr_pylike_eval "bf_blenlib")
 BLENDER_TEST(BLI_edgehash "bf_blenlib")
+BLENDER_TEST(BLI_expr_pylike_eval "bf_blenlib")
 BLENDER_TEST(BLI_ghash "bf_blenlib")
 BLENDER_TEST(BLI_hash_mm2a "bf_blenlib")
 BLENDER_TEST(BLI_heap "bf_blenlib")
 BLENDER_TEST(BLI_heap_simple "bf_blenlib")
+BLENDER_TEST(BLI_index_range "bf_blenlib")
 BLENDER_TEST(BLI_kdopbvh "bf_blenlib;bf_intern_numaapi")
 BLENDER_TEST(BLI_linklist_lockfree "bf_blenlib;bf_intern_numaapi")
 BLENDER_TEST(BLI_listbase "bf_blenlib")
@@ -57,9 +60,11 @@ BLENDER_TEST(BLI_memiter "bf_blenlib")
 BLENDER_TEST(BLI_path_util "${BLI_path_util_extra_libs}")
 BLENDER_TEST(BLI_polyfill_2d "bf_blenlib")
 BLENDER_TEST(BLI_stack "bf_blenlib")
+BLENDER_TEST(BLI_stack_cxx "bf_blenlib")
 BLENDER_TEST(BLI_string "bf_blenlib")
 BLENDER_TEST(BLI_string_utf8 "bf_blenlib")
 BLENDER_TEST(BLI_task "bf_blenlib;bf_intern_numaapi")
+BLENDER_TEST(BLI_vector "bf_blenlib")
 
 BLENDER_TEST_PERFORMANCE(BLI_ghash_performance "bf_blenlib")
 BLENDER_TEST_PERFORMANCE(BLI_task_performance "bf_blenlib")