BLI: improve various C++ data structures

The changes come from the `functions` branch, where I'm using
these structures a lot.

This also includes a new `BLI::Optional<T>` type, which is similar
to `std::Optional<T>` which can be used when Blender starts using
C++17.

source/blender/blenlib/BLI_allocator.h

@@ -36,7 +36,6 @@
 
 #include "BLI_utildefines.h"
 #include "BLI_math_base.h"
-#include "BLI_temporary_allocator.h"
 
 namespace BLI {
 
@@ -53,7 +52,6 @@ class GuardedAllocator {
 
   void *allocate_aligned(uint size, uint alignment, const char *name)
   {
-    alignment = std::max<uint>(alignment, 8);
     return MEM_mallocN_aligned(size, alignment, name);
   }
 
@@ -102,29 +100,6 @@ class RawAllocator {
   }
 };
 
-/**
- * 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
 
 #endif /* __BLI_ALLOCATOR_H__ */

source/blender/blenlib/BLI_array_cxx.h

@@ -31,23 +31,24 @@
 
 namespace BLI {
 
-template<typename T, typename Allocator = GuardedAllocator> class Array {
+template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Array {
  private:
   T *m_data;
   uint m_size;
   Allocator m_allocator;
+  AlignedBuffer<sizeof(T) * N, alignof(T)> m_inline_storage;
 
  public:
   Array()
   {
-    m_data = nullptr;
+    m_data = this->inline_storage();
     m_size = 0;
   }
 
   Array(ArrayRef<T> values)
   {
     m_size = values.size();
-    m_data = this->allocate(m_size);
+    m_data = this->get_buffer_for_size(values.size());
     uninitialized_copy_n(values.begin(), m_size, m_data);
   }
 
@@ -57,8 +58,8 @@ template<typename T, typename Allocator = GuardedAllocator> class Array {
 
   explicit Array(uint size)
   {
-    m_data = this->allocate(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();
@@ -67,8 +68,8 @@ template<typename T, typename Allocator = GuardedAllocator> class Array {
 
   Array(uint size, const T &value)
   {
-    m_data = this->allocate(size);
     m_size = size;
+    m_data = this->get_buffer_for_size(size);
     uninitialized_fill_n(m_data, m_size, value);
   }
 
@@ -77,30 +78,31 @@ template<typename T, typename Allocator = GuardedAllocator> class Array {
     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);
-    }
+    m_data = this->get_buffer_for_size(other.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;
+    if (!other.uses_inline_storage()) {
+      m_data = other.m_data;
+    }
+    else {
+      m_data = this->get_buffer_for_size(m_size);
+      uninitialized_relocate_n(other.m_data, m_size, m_data);
+    }
+
+    other.m_data = other.inline_storage();
     other.m_size = 0;
   }
 
   ~Array()
   {
     destruct_n(m_data, m_size);
-    if (m_data != nullptr) {
+    if (!this->uses_inline_storage()) {
       m_allocator.deallocate((void *)m_data);
     }
   }
@@ -142,12 +144,23 @@ template<typename T, typename Allocator = GuardedAllocator> class Array {
     return *this;
   }
 
+  MutableArrayRef<T> as_mutable_ref()
+  {
+    return *this;
+  }
+
   T &operator[](uint index)
   {
     BLI_assert(index < m_size);
     return m_data[index];
   }
 
+  const T &operator[](uint index) const
+  {
+    BLI_assert(index < m_size);
+    return m_data[index];
+  }
+
   uint size() const
   {
     return m_size;
@@ -189,14 +202,32 @@ template<typename T, typename Allocator = GuardedAllocator> class Array {
   }
 
  private:
+  T *get_buffer_for_size(uint size)
+  {
+    if (size <= N) {
+      return this->inline_storage();
+    }
+    else {
+      return this->allocate(size);
+    }
+  }
+
+  T *inline_storage() const
+  {
+    return (T *)m_inline_storage.ptr();
+  }
+
   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>;
+  bool uses_inline_storage() const
+  {
+    return m_data == this->inline_storage();
+  }
+};
 
 }  // namespace BLI
 

source/blender/blenlib/BLI_array_ref.h

@@ -78,6 +78,16 @@ template<typename T> class ArrayRef {
   {
   }
 
+  /**
+   * ArrayRef<T *> -> ArrayRef<const T *>
+   * ArrayRef<Derived *> -> ArrayRef<Base *>
+   */
+  template<typename U,
+           typename std::enable_if<std::is_convertible<U *, T>::value>::type * = nullptr>
+  ArrayRef(ArrayRef<U *> array) : ArrayRef((T *)array.begin(), array.size())
+  {
+  }
+
   /**
    * Return a continuous part of the array.
    * Asserts that the slice stays within the array.
@@ -246,6 +256,73 @@ template<typename T> class ArrayRef {
     return fallback;
   }
 
+  /**
+   * Check if the array contains duplicates. Does a linear search for every element. So the total
+   * running time is O(n^2). Only use this for small arrays.
+   */
+  bool has_duplicates__linear_search() const
+  {
+    /* The size should really be smaller than that. If it is not, the calling code should be
+     * changed. */
+    BLI_assert(m_size < 1000);
+
+    for (uint i = 0; i < m_size; i++) {
+      const T &value = m_start[i];
+      for (uint j = i + 1; j < m_size; j++) {
+        if (value == m_start[j]) {
+          return true;
+        }
+      }
+    }
+    return false;
+  }
+
+  bool intersects__linear_search(ArrayRef other) const
+  {
+    /* The size should really be smaller than that. If it is not, the calling code should be
+     * changed. */
+    BLI_assert(m_size < 1000);
+
+    for (uint i = 0; i < m_size; i++) {
+      const T &value = m_start[i];
+      if (other.contains(value)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  uint first_index(const T &search_value) const
+  {
+    int index = this->first_index_try(search_value);
+    BLI_assert(index >= 0);
+    return (uint)index;
+  }
+
+  int first_index_try(const T &search_value) const
+  {
+    for (uint i = 0; i < m_size; i++) {
+      if (m_start[i] == search_value) {
+        return i;
+      }
+    }
+    return -1;
+  }
+
+  template<typename PredicateT> bool any(const PredicateT predicate)
+  {
+    for (uint i = 0; i < m_size; i++) {
+      if (predicate(m_start[i])) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  /**
+   * Utility to make it more convenient to iterate over all indices that can be used with this
+   * array.
+   */
   IndexRange index_range() const
   {
     return IndexRange(m_size);
@@ -253,13 +330,12 @@ template<typename T> class ArrayRef {
 
   /**
    * 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);
+    BLI_assert((m_size * sizeof(T)) % sizeof(NewT) == 0);
+    uint new_size = m_size * sizeof(T) / sizeof(NewT);
+    return ArrayRef<NewT>(reinterpret_cast<const NewT *>(m_start), new_size);
   }
 
   /**
@@ -275,6 +351,11 @@ template<typename T> class ArrayRef {
       std::cout << '\n';
     }
   }
+
+  void print_as_lines(std::string name) const
+  {
+    this->print_as_lines(name, [](const T &value) { std::cout << value; });
+  }
 };
 
 /**
@@ -305,7 +386,7 @@ template<typename T> class MutableArrayRef {
   {
   }
 
-  operator ArrayRef<T>()
+  operator ArrayRef<T>() const
   {
     return ArrayRef<T>(m_start, m_size);
   }
@@ -421,6 +502,12 @@ template<typename T> class MutableArrayRef {
   {
     return IndexRange(m_size);
   }
+
+  const T &last() const
+  {
+    BLI_assert(m_size > 0);
+    return m_start[m_size - 1];
+  }
 };
 
 /**
@@ -431,6 +518,28 @@ template<typename T> ArrayRef<T> ref_c_array(const T *array, uint size)
   return ArrayRef<T>(array, size);
 }
 
+template<typename T1, typename T2> void assert_same_size(const T1 &v1, const T2 &v2)
+{
+  UNUSED_VARS_NDEBUG(v1, v2);
+#ifdef DEBUG
+  uint size = v1.size();
+  BLI_assert(size == v1.size());
+  BLI_assert(size == v2.size());
+#endif
+}
+
+template<typename T1, typename T2, typename T3>
+void assert_same_size(const T1 &v1, const T2 &v2, const T3 &v3)
+{
+  UNUSED_VARS_NDEBUG(v1, v2, v3);
+#ifdef DEBUG
+  uint size = v1.size();
+  BLI_assert(size == v1.size());
+  BLI_assert(size == v2.size());
+  BLI_assert(size == v3.size());
+#endif
+}
+
 } /* namespace BLI */
 
 #endif /* __BLI_ARRAY_REF_H__ */

source/blender/blenlib/BLI_hash_cxx.h

@@ -58,6 +58,7 @@ TRIVIAL_DEFAULT_INT_HASH(uint16_t);
 TRIVIAL_DEFAULT_INT_HASH(int32_t);
 TRIVIAL_DEFAULT_INT_HASH(uint32_t);
 TRIVIAL_DEFAULT_INT_HASH(int64_t);
+TRIVIAL_DEFAULT_INT_HASH(uint64_t);
 
 template<> struct DefaultHash<float> {
   uint32_t operator()(float value) const

source/blender/blenlib/BLI_index_range.h

@@ -31,6 +31,11 @@
 
 #include "BLI_utildefines.h"
 
+/* Forward declare tbb::blocked_range for conversion operations. */
+namespace tbb {
+template<typename Value> class blocked_range;
+}
+
 namespace BLI {
 
 template<typename T> class ArrayRef;
@@ -51,6 +56,11 @@ class IndexRange {
   {
   }
 
+  template<typename T>
+  IndexRange(const tbb::blocked_range<T> &range) : m_start(range.begin()), m_size(range.size())
+  {
+  }
+
   class Iterator {
    private:
     uint m_current;
@@ -179,6 +189,11 @@ class IndexRange {
     return IndexRange(new_start, size);
   }
 
+  IndexRange slice(IndexRange range) const
+  {
+    return this->slice(range.start(), range.size());
+  }
+
   /**
    * Get read-only access to a memory buffer that contains the range as actual numbers.
    */

source/blender/blenlib/BLI_kdtree.h

@@ -17,6 +17,10 @@
 #ifndef __BLI_KDTREE_H__
 #define __BLI_KDTREE_H__
 
+#ifdef __cplusplus
+extern "C" {
+#endif
+
 /** \file
  * \ingroup bli
  * \brief A kd-tree for nearest neighbor search.
@@ -66,4 +70,8 @@
 #undef KDTreeNearest
 #undef KDTREE_PREFIX_ID
 
+#ifdef __cplusplus
+}
+#endif
+
 #endif /* __BLI_KDTREE_H__ */

source/blender/blenlib/BLI_listbase_wrapper.h

@@ -93,6 +93,19 @@ template<typename T> class IntrusiveListBaseWrapper {
     BLI_assert(ptr);
     return (T *)ptr;
   }
+
+  uint index_of(const T *value) const
+  {
+    uint index = 0;
+    for (T *ptr : *this) {
+      if (ptr == value) {
+        return index;
+      }
+      index++;
+    }
+    BLI_assert(false);
+    return 0;
+  }
 };
 
 } /* namespace BLI */

source/blender/blenlib/BLI_map.h

@@ -413,6 +413,19 @@ template<typename KeyT, typename ValueT, typename Allocator = GuardedAllocator>
     return m_array.slots_set();
   }
 
+  template<typename FuncT> void foreach_item(const FuncT &func) const
+  {
+    for (const Item &item : m_array) {
+      for (uint offset = 0; offset < 4; offset++) {
+        if (item.is_set(offset)) {
+          const KeyT &key = *item.key(offset);
+          const ValueT &value = *item.value(offset);
+          func(key, value);
+        }
+      }
+    }
+  }
+
   void print_table() const
   {
     std::cout << "Hash Table:\n";

source/blender/blenlib/BLI_memory_utils_cxx.h

@@ -33,6 +33,11 @@ using std::uninitialized_copy_n;
 using std::uninitialized_fill;
 using std::uninitialized_fill_n;
 
+template<typename T> void construct_default(T *ptr)
+{
+  new (ptr) T();
+}
+
 template<typename T> void destruct(T *ptr)
 {
   ptr->~T();
@@ -79,6 +84,38 @@ template<typename T> void relocate_n(T *src, uint n, T *dst)
   destruct_n(src, n);
 }
 
+template<typename T, typename... Args> std::unique_ptr<T> make_unique(Args &&... args)
+{
+  return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
+}
+
+template<typename T> struct DestructValueAtAddress {
+  void operator()(T *ptr)
+  {
+    ptr->~T();
+  }
+};
+
+template<typename T> using destruct_ptr = std::unique_ptr<T, DestructValueAtAddress<T>>;
+
+template<uint Size, uint Alignment> class alignas(Alignment) AlignedBuffer {
+ private:
+  /* Don't create an empty array. This causes problems with some compilers. */
+  static constexpr uint ActualSize = (Size > 0) ? Size : 1;
+  char m_buffer[ActualSize];
+
+ public:
+  void *ptr()
+  {
+    return (void *)m_buffer;
+  }
+
+  const void *ptr() const
+  {
+    return (const void *)m_buffer;
+  }
+};
+
 }  // namespace BLI
 
 #endif /* __BLI_MEMORY_UTILS_CXX_H__ */

source/blender/blenlib/BLI_open_addressing.h

@@ -70,7 +70,7 @@ class OpenAddressingArray {
   /* Can be used to map a hash value into the range of valid slot indices. */
   uint32_t m_slot_mask;
   Allocator m_allocator;
-  char m_local_storage[sizeof(Item) * ItemsInSmallStorage];
+  AlignedBuffer<sizeof(Item) * ItemsInSmallStorage, alignof(Item)> m_local_storage;
 
  public:
   explicit OpenAddressingArray(uint8_t item_exponent = 0)
@@ -291,7 +291,7 @@ class OpenAddressingArray {
  private:
   Item *small_storage() const
   {
-    return reinterpret_cast<Item *>((char *)m_local_storage);
+    return reinterpret_cast<Item *>((char *)m_local_storage.ptr());
   }
 
   bool is_in_small_storage() const

source/blender/blenlib/BLI_optional.h

@@ -0,0 +1,196 @@
+/*
+ * 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
+ *
+ * Simple version of std::optional, which is only available since C++17.
+ */
+
+#pragma once
+
+#include "BLI_utildefines.h"
+#include "BLI_memory_utils_cxx.h"
+
+#include <algorithm>
+#include <memory>
+
+namespace BLI {
+
+template<typename T> class Optional {
+ private:
+  AlignedBuffer<sizeof(T), alignof(T)> m_storage;
+  bool m_set;
+
+ public:
+  static Optional FromPointer(const T *ptr)
+  {
+    if (ptr == nullptr) {
+      return Optional();
+    }
+    else {
+      return Optional(*ptr);
+    }
+  }
+
+  Optional() : m_set(false)
+  {
+  }
+
+  ~Optional()
+  {
+    this->reset();
+  }
+
+  Optional(const T &value) : Optional()
+  {
+    this->set(value);
+  }
+
+  Optional(T &&value) : Optional()
+  {
+    this->set(std::forward<T>(value));
+  }
+
+  Optional(const Optional &other) : Optional()
+  {
+    if (other.has_value()) {
+      this->set(other.value());
+    }
+  }
+
+  Optional(Optional &&other) : Optional()
+  {
+    if (other.has_value()) {
+      this->set(std::move(other.value()));
+    }
+  }
+
+  Optional &operator=(const Optional &other)
+  {
+    if (this == &other) {
+      return *this;
+    }
+    if (other.has_value()) {
+      this->set(other.value());
+    }
+    else {
+      this->reset();
+    }
+    return *this;
+  }
+
+  Optional &operator=(Optional &&other)
+  {
+    if (this == &other) {
+      return *this;
+    }
+    if (other.has_value()) {
+      this->set(std::move(other.value()));
+    }
+    else {
+      this->reset();
+    }
+    return *this;
+  }
+
+  bool has_value() const
+  {
+    return m_set;
+  }
+
+  const T &value() const
+  {
+    BLI_assert(m_set);
+    return *this->value_ptr();
+  }
+
+  T &value()
+  {
+    BLI_assert(m_set);
+    return *this->value_ptr();
+  }
+
+  void set(const T &value)
+  {
+    if (m_set) {
+      this->value() = value;
+    }
+    else {
+      new (this->value_ptr()) T(value);
+      m_set = true;
+    }
+  }
+
+  void set(T &&value)
+  {
+    if (m_set) {
+      this->value() = std::move(value);
+    }
+    else {
+      new (this->value_ptr()) T(std::move(value));
+      m_set = true;
+    }
+  }
+
+  void set_new(const T &value)
+  {
+    BLI_assert(!m_set);
+    new (this->value_ptr()) T(value);
+    m_set = true;
+  }
+
+  void set_new(T &&value)
+  {
+    BLI_assert(!m_set);
+    new (this->value_ptr()) T(std::move(value));
+    m_set = true;
+  }
+
+  void reset()
+  {
+    if (m_set) {
+      this->value_ptr()->~T();
+      m_set = false;
+    }
+  }
+
+  T extract()
+  {
+    BLI_assert(m_set);
+    T value = std::move(this->value());
+    this->reset();
+    return value;
+  }
+
+  T *operator->()
+  {
+    return this->value_ptr();
+  }
+
+  T &operator*()
+  {
+    return *this->value_ptr();
+  }
+
+ private:
+  T *value_ptr() const
+  {
+    return (T *)m_storage.ptr();
+  }
+};
+
+} /* namespace BLI */

source/blender/blenlib/BLI_rand.h

@@ -20,6 +20,8 @@
 #ifndef __BLI_RAND_H__
 #define __BLI_RAND_H__
 
+#include "BLI_compiler_attrs.h"
+
 /** \file
  * \ingroup bli
  * \brief Random number functions.

source/blender/blenlib/BLI_stack_cxx.h

@@ -58,7 +58,7 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class St
   /**
    * Return true when the stack is empty, otherwise false.
    */
-  bool empty() const
+  bool is_empty() const
   {
     return this->size() == 0;
   }
@@ -76,6 +76,11 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class St
     m_elements.append(std::move(value));
   }
 
+  void push_multiple(ArrayRef<T> values)
+  {
+    m_elements.extend(values);
+  }
+
   /**
    * Remove the element from the top of the stack and return it.
    * This will assert when the stack is empty.
@@ -91,7 +96,7 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class St
    */
   T &peek()
   {
-    BLI_assert(!this->empty());
+    BLI_assert(!this->is_empty());
     return m_elements[this->size() - 1];
   }
 

source/blender/blenlib/BLI_string_map.h

@@ -30,6 +30,7 @@
 #include "BLI_map.h"
 #include "BLI_string_ref.h"
 #include "BLI_vector.h"
+#include "BLI_optional.h"
 
 namespace BLI {
 
@@ -189,6 +190,22 @@ template<typename T, typename Allocator = GuardedAllocator> class StringMap {
     this->add_new__impl(key, std::move(value));
   }
 
+  /**
+   * Add a new element to the map if the key does not exist yet.
+   */
+  void add(StringRef key, const T &value)
+  {
+    if (!this->contains(key)) {
+      this->add_new(key, value);
+    }
+  }
+  void add(StringRef key, T &&value)
+  {
+    if (!this->contains(key)) {
+      this->add_new(key, std::move(value));
+    }
+  }
+
   /**
    * Return true when the key exists in the map, otherwise false.
    */
@@ -263,6 +280,11 @@ template<typename T, typename Allocator = GuardedAllocator> class StringMap {
     return const_cast<T *>(const_cast<const StringMap *>(this)->lookup_ptr(key));
   }
 
+  Optional<T> try_lookup(StringRef key) const
+  {
+    return Optional<T>::FromPointer(this->lookup_ptr(key));
+  }
+
   /**
    * Get a copy of the value corresponding to the key. If the key does not exist, return the
    * default value.
@@ -326,7 +348,7 @@ template<typename T, typename Allocator = GuardedAllocator> class StringMap {
   /**
    * Run a function for every key-value-pair in the map.
    */
-  template<typename FuncT> void foreach_key_value_pair(const FuncT &func)
+  template<typename FuncT> void foreach_item(const FuncT &func)
   {
     for (Item &item : m_array) {
       for (uint offset = 0; offset < 4; offset++) {
@@ -339,6 +361,19 @@ template<typename T, typename Allocator = GuardedAllocator> class StringMap {
     }
   }
 
+  template<typename FuncT> void foreach_item(const FuncT &func) const
+  {
+    for (const Item &item : m_array) {
+      for (uint offset = 0; offset < 4; offset++) {
+        if (item.is_set(offset)) {
+          StringRefNull key = item.get_key(offset, m_chars);
+          const T &value = *item.value(offset);
+          func(key, value);
+        }
+      }
+    }
+  }
+
  private:
   uint32_t compute_string_hash(StringRef key) const
   {
@@ -415,6 +450,15 @@ template<typename T, typename Allocator = GuardedAllocator> class StringMap {
     }
     ITER_SLOTS_END(offset);
   }
+
+  template<typename ForwardT> void add__impl(StringRef key, ForwardT &&value)
+  {
+    this->ensure_can_add();
+    uint32_t hash = this->compute_string_hash(key);
+    ITER_SLOTS_BEGIN (hash, m_array, , item, offset) {
+    }
+    ITER_SLOTS_END(offset);
+  }
 };
 
 #undef ITER_SLOTS_BEGIN

source/blender/blenlib/BLI_string_ref.h

@@ -109,6 +109,8 @@ class StringRefBase {
    * Returns true when the string ends with the given suffix. Otherwise false.
    */
   bool endswith(StringRef suffix) const;
+
+  StringRef substr(uint start, uint size) const;
 };
 
 /**
@@ -242,6 +244,12 @@ inline bool StringRefBase::endswith(StringRef suffix) const
   return true;
 }
 
+inline StringRef StringRefBase::substr(uint start, uint size) const
+{
+  BLI_assert(start + size <= m_size);
+  return StringRef(m_data + start, size);
+}
+
 }  // namespace BLI
 
 #endif /* __BLI_STRING_REF_H__ */

source/blender/blenlib/BLI_temporary_allocator.h

@@ -1,64 +0,0 @@
-/*
- * 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__ */

source/blender/blenlib/BLI_temporary_allocator_cxx.h

@@ -1,38 +0,0 @@
-/*
- * 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.
- */
-
-#ifndef __BLI_TEMPORARY_ALLOCATOR_CXX_H__
-#define __BLI_TEMPORARY_ALLOCATOR_CXX_H__
-
-/** \file
- * \ingroup bli
- */
-
-#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
-
-#endif /* __BLI_TEMPORARY_ALLOCATOR_CXX_H__ */

source/blender/blenlib/BLI_vector.h

@@ -49,7 +49,7 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
   T *m_end;
   T *m_capacity_end;
   Allocator m_allocator;
-  char m_small_buffer[sizeof(T) * N];
+  AlignedBuffer<sizeof(T) * N, alignof(T)> m_small_buffer;
 
 #ifndef NDEBUG
   /* Storing size in debug builds, because it makes debugging much easier sometimes. */
@@ -216,6 +216,16 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
     return MutableArrayRef<T>(m_begin, this->size());
   }
 
+  ArrayRef<T> as_ref() const
+  {
+    return *this;
+  }
+
+  MutableArrayRef<T> as_mutable_ref()
+  {
+    return *this;
+  }
+
   Vector &operator=(const Vector &other)
   {
     if (this == &other) {
@@ -234,6 +244,8 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
       return *this;
     }
 
+    /* This can fail, when the vector is used to build a recursive data structure.
+       See https://youtu.be/7Qgd9B1KuMQ?t=840. */
     this->~Vector();
     new (this) Vector(std::move(other));
 
@@ -294,6 +306,20 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
     this->append_unchecked(std::move(value));
   }
 
+  uint append_and_get_index(const T &value)
+  {
+    uint index = this->size();
+    this->append(value);
+    return index;
+  }
+
+  void append_non_duplicates(const T &value)
+  {
+    if (!this->contains(value)) {
+      this->append(value);
+    }
+  }
+
   void append_unchecked(const T &value)
   {
     BLI_assert(m_end < m_capacity_end);
@@ -342,6 +368,13 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
     this->extend_unchecked(start, amount);
   }
 
+  void extend_non_duplicates(ArrayRef<T> array)
+  {
+    for (const T &value : array) {
+      this->append_non_duplicates(value);
+    }
+  }
+
   void extend_unchecked(ArrayRef<T> array)
   {
     this->extend_unchecked(array.begin(), array.size());
@@ -442,11 +475,17 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
     UPDATE_VECTOR_SIZE(this);
   }
 
+  void remove_first_occurrence_and_reorder(const T &value)
+  {
+    uint index = this->index(value);
+    this->remove_and_reorder((uint)index);
+  }
+
   /**
    * 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
+  int index_try(const T &value) const
   {
     for (T *current = m_begin; current != m_end; current++) {
       if (*current == value) {
@@ -456,13 +495,24 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
     return -1;
   }
 
+  /**
+   * Do a linear search to find the value in the vector.
+   * When found, return the first index, otherwise fail.
+   */
+  uint index(const T &value) const
+  {
+    int index = this->index_try(value);
+    BLI_assert(index >= 0);
+    return (uint)index;
+  }
+
   /**
    * 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;
+    return this->index_try(value) != -1;
   }
 
   /**
@@ -537,7 +587,7 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
  private:
   T *small_buffer() const
   {
-    return (T *)m_small_buffer;
+    return (T *)m_small_buffer.ptr();
   }
 
   bool is_small() const
@@ -561,10 +611,11 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
     /* 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 * (uint)sizeof(T), std::alignment_of<T>::value, __func__);
+        min_capacity * (uint)sizeof(T), std::alignment_of<T>::value, "grow BLI::Vector");
     uninitialized_relocate_n(m_begin, size, new_array);
 
     if (!this->is_small()) {
@@ -606,7 +657,11 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve
 
 #undef UPDATE_VECTOR_SIZE
 
-template<typename T, uint N = 4> using TemporaryVector = Vector<T, N, TemporaryAllocator>;
+/**
+ * Use when the vector is used in the local scope of a function. It has a larger inline storage by
+ * default to make allocations less likely.
+ */
+template<typename T, uint N = 20> using ScopedVector = Vector<T, N, GuardedAllocator>;
 
 } /* namespace BLI */
 

source/blender/blenlib/BLI_vector_set.h

@@ -292,12 +292,12 @@ template<typename T, typename Allocator = GuardedAllocator> class VectorSet {
     return m_elements[index];
   }
 
-  operator ArrayRef<T>() const
+  ArrayRef<T> as_ref() const
   {
-    return m_elements;
+    return *this;
   }
 
-  operator MutableArrayRef<T>()
+  operator ArrayRef<T>() const
   {
     return m_elements;
   }

source/blender/blenlib/CMakeLists.txt

@@ -52,7 +52,6 @@ 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
@@ -213,6 +212,7 @@ set(SRC
   BLI_mempool.h
   BLI_noise.h
   BLI_open_addressing.h
+  BLI_optional.h
   BLI_path_util.h
   BLI_polyfill_2d.h
   BLI_polyfill_2d_beautify.h
@@ -236,8 +236,6 @@ 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

source/blender/blenlib/intern/BLI_index_range.cc

@@ -24,7 +24,7 @@
 
 namespace BLI {
 
-static Vector<Array<uint, RawAllocator>, 1, RawAllocator> arrays;
+static Vector<Array<uint, 0, RawAllocator>, 1, RawAllocator> arrays;
 static uint current_array_size = 0;
 static uint *current_array = nullptr;
 static std::mutex current_array_mutex;
@@ -44,7 +44,7 @@ ArrayRef<uint> IndexRange::as_array_ref() const
   }
 
   uint new_size = std::max<uint>(1000, power_of_2_max_u(min_required_size));
-  Array<uint, RawAllocator> new_array(new_size);
+  Array<uint, 0, RawAllocator> new_array(new_size);
   for (uint i = 0; i < new_size; i++) {
     new_array[i] = i;
   }

source/blender/blenlib/intern/BLI_temporary_allocator.cc

@@ -1,115 +0,0 @@
-/*
- * 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);
-    }
-  }
-};
-
-static 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);
-  }
-}

tests/gtests/blenlib/BLI_array_ref_test.cc

@@ -2,7 +2,8 @@
 #include "BLI_array_ref.h"
 #include "BLI_vector.h"
 
-using BLI::IndexRange;
+using namespace BLI;
+
 using IntVector = BLI::Vector<int>;
 using IntArrayRef = BLI::ArrayRef<int>;
 using MutableIntArrayRef = BLI::MutableArrayRef<int>;
@@ -17,6 +18,15 @@ TEST(array_ref, FromSmallVector)
   EXPECT_EQ(a_ref[2], 3);
 }
 
+TEST(array_ref, AddConstToPointer)
+{
+  int a = 0;
+  std::vector<int *> vec = {&a};
+  ArrayRef<int *> ref = vec;
+  ArrayRef<const int *> const_ref = ref;
+  EXPECT_EQ(const_ref.size(), 1);
+}
+
 TEST(array_ref, IsReferencing)
 {
   int array[] = {3, 5, 8};
@@ -264,3 +274,47 @@ TEST(array_ref, ContainsPtr)
   EXPECT_FALSE(a_ref.contains_ptr(&a[0] - 1));
   EXPECT_FALSE(a_ref.contains_ptr(&other));
 }
+
+TEST(array_ref, FirstIndex)
+{
+  std::array<int, 5> a = {4, 5, 4, 2, 5};
+  IntArrayRef a_ref(a);
+
+  EXPECT_EQ(a_ref.first_index(4), 0);
+  EXPECT_EQ(a_ref.first_index(5), 1);
+  EXPECT_EQ(a_ref.first_index(2), 3);
+}
+
+TEST(array_ref, CastSameSize)
+{
+  int value = 0;
+  std::array<int *, 4> a = {&value, nullptr, nullptr, nullptr};
+  ArrayRef<int *> a_ref = a;
+  ArrayRef<float *> new_a_ref = a_ref.cast<float *>();
+
+  EXPECT_EQ(a_ref.size(), 4);
+  EXPECT_EQ(new_a_ref.size(), 4);
+
+  EXPECT_EQ(a_ref[0], &value);
+  EXPECT_EQ(new_a_ref[0], (float *)&value);
+}
+
+TEST(array_ref, CastSmallerSize)
+{
+  std::array<uint32_t, 4> a = {3, 4, 5, 6};
+  ArrayRef<uint32_t> a_ref = a;
+  ArrayRef<uint16_t> new_a_ref = a_ref.cast<uint16_t>();
+
+  EXPECT_EQ(a_ref.size(), 4);
+  EXPECT_EQ(new_a_ref.size(), 8);
+}
+
+TEST(array_ref, CastLargerSize)
+{
+  std::array<uint16_t, 4> a = {4, 5, 6, 7};
+  ArrayRef<uint16_t> a_ref = a;
+  ArrayRef<uint32_t> new_a_ref = a_ref.cast<uint32_t>();
+
+  EXPECT_EQ(a_ref.size(), 4);
+  EXPECT_EQ(new_a_ref.size(), 2);
+}

tests/gtests/blenlib/BLI_index_range_test.cc

@@ -119,6 +119,15 @@ TEST(index_range, Slice)
   EXPECT_EQ(slice.last(), 12);
 }
 
+TEST(index_range, SliceRange)
+{
+  IndexRange range = IndexRange(5, 15);
+  IndexRange slice = range.slice(IndexRange(3, 5));
+  EXPECT_EQ(slice.size(), 5);
+  EXPECT_EQ(slice.first(), 8);
+  EXPECT_EQ(slice.last(), 12);
+}
+
 TEST(index_range, AsArrayRef)
 {
   IndexRange range = IndexRange(4, 6);

tests/gtests/blenlib/BLI_optional_test.cc

@@ -0,0 +1,74 @@
+#include "testing/testing.h"
+#include "BLI_optional.h"
+#include <string>
+
+using namespace BLI;
+
+TEST(optional, DefaultConstructor)
+{
+  Optional<int> a;
+  EXPECT_FALSE(a.has_value());
+}
+
+TEST(optional, ValueConstructor)
+{
+  Optional<int> a(5);
+  EXPECT_TRUE(a.has_value());
+  EXPECT_EQ(a.value(), 5);
+}
+
+TEST(optional, CopyConstructor)
+{
+  Optional<std::string> a("Hello");
+  Optional<std::string> b = a;
+  EXPECT_TRUE(a.has_value());
+  EXPECT_TRUE(b.has_value());
+  b.value()[0] = 'T';
+  EXPECT_EQ(a.value(), "Hello");
+  EXPECT_EQ(b.value(), "Tello");
+}
+
+TEST(optional, Reset)
+{
+  Optional<int> a(4);
+  EXPECT_TRUE(a.has_value());
+  a.reset();
+  EXPECT_FALSE(a.has_value());
+}
+
+TEST(optional, FromNullPointer)
+{
+  Optional<int> a = Optional<int>::FromPointer(nullptr);
+  EXPECT_FALSE(a.has_value());
+}
+
+TEST(optional, FromNonNullPointer)
+{
+  int value = 42;
+  Optional<int> a = Optional<int>::FromPointer(&value);
+  EXPECT_TRUE(a.has_value());
+  EXPECT_EQ(a.value(), 42);
+}
+
+TEST(optional, Extract)
+{
+  Optional<int> a(32);
+  EXPECT_TRUE(a.has_value());
+  EXPECT_EQ(a.extract(), 32);
+  EXPECT_FALSE(a.has_value());
+}
+
+TEST(optional, ArrowOperator)
+{
+  Optional<std::string> value = std::string("Hello");
+  EXPECT_TRUE(value.has_value());
+  EXPECT_EQ(value->size(), 5);
+}
+
+TEST(optional, StarOperator)
+{
+  Optional<std::string> value = std::string("Hello");
+  EXPECT_TRUE(value.has_value());
+  std::string &s = *value;
+  EXPECT_EQ(s.size(), 5);
+}

tests/gtests/blenlib/BLI_stack_cxx_test.cc

@@ -8,7 +8,7 @@ TEST(stack, DefaultConstructor)
 {
   IntStack stack;
   EXPECT_EQ(stack.size(), 0);
-  EXPECT_TRUE(stack.empty());
+  EXPECT_TRUE(stack.is_empty());
 }
 
 TEST(stack, ArrayRefConstructor)
@@ -19,7 +19,7 @@ TEST(stack, ArrayRefConstructor)
   EXPECT_EQ(stack.pop(), 2);
   EXPECT_EQ(stack.pop(), 7);
   EXPECT_EQ(stack.pop(), 4);
-  EXPECT_TRUE(stack.empty());
+  EXPECT_TRUE(stack.is_empty());
 }
 
 TEST(stack, Push)
@@ -32,6 +32,17 @@ TEST(stack, Push)
   EXPECT_EQ(stack.size(), 2);
 }
 
+TEST(stack, PushMultiple)
+{
+  IntStack stack;
+  EXPECT_EQ(stack.size(), 0);
+  stack.push_multiple({1, 2, 3});
+  EXPECT_EQ(stack.size(), 3);
+  EXPECT_EQ(stack.pop(), 3);
+  EXPECT_EQ(stack.pop(), 2);
+  EXPECT_EQ(stack.pop(), 1);
+}
+
 TEST(stack, Pop)
 {
   IntStack stack;

tests/gtests/blenlib/BLI_string_map_test.cc

@@ -43,6 +43,21 @@ TEST(string_map, MoveConstructor)
   EXPECT_EQ(map2.lookup("B")[5], 6);
 }
 
+TEST(string_map, Add)
+{
+  StringMap<int> map;
+  EXPECT_EQ(map.size(), 0);
+
+  map.add("test", 1);
+  EXPECT_EQ(map.lookup("test"), 1);
+
+  map.add("test", 2);
+  EXPECT_EQ(map.lookup("test"), 1);
+
+  map.add("test2", 2);
+  EXPECT_EQ(map.lookup("test2"), 2);
+}
+
 TEST(string_map, AddNew)
 {
   StringMap<int> map;
@@ -128,6 +143,15 @@ TEST(string_map, LookupDefault)
   EXPECT_EQ(map.lookup_default("test", 42), 5);
 }
 
+TEST(string_map, TryLookup)
+{
+  StringMap<int> map;
+  map.add_new("test", 4);
+  EXPECT_TRUE(map.try_lookup("test").has_value());
+  EXPECT_FALSE(map.try_lookup("value").has_value());
+  EXPECT_EQ(map.try_lookup("test").value(), 4);
+}
+
 TEST(string_map, FindKeyForValue)
 {
   StringMap<int> map;
@@ -179,7 +203,7 @@ TEST(string_map, ForeachKeyValuePair)
   Vector<std::string> keys;
   Vector<int> values;
 
-  map.foreach_key_value_pair([&keys, &values](StringRefNull key, int value) {
+  map.foreach_item([&keys, &values](StringRefNull key, int value) {
     keys.append(key);
     values.append(value);
   });

tests/gtests/blenlib/BLI_string_ref_test.cc

@@ -228,3 +228,12 @@ TEST(string_ref, DropPrefix)
   EXPECT_EQ(ref2.size(), 1);
   EXPECT_EQ(ref2, "t");
 }
+
+TEST(string_ref, Substr)
+{
+  StringRef ref("hello world");
+  EXPECT_EQ(ref.substr(0, 5), "hello");
+  EXPECT_EQ(ref.substr(4, 0), "");
+  EXPECT_EQ(ref.substr(3, 4), "lo w");
+  EXPECT_EQ(ref.substr(6, 5), "world");
+}

tests/gtests/blenlib/BLI_vector_test.cc

@@ -216,6 +216,38 @@ TEST(vector, Append)
   EXPECT_EQ(vec[2], 7);
 }
 
+TEST(vector, AppendAndGetIndex)
+{
+  IntVector vec;
+  EXPECT_EQ(vec.append_and_get_index(10), 0);
+  EXPECT_EQ(vec.append_and_get_index(10), 1);
+  EXPECT_EQ(vec.append_and_get_index(10), 2);
+  vec.append(10);
+  EXPECT_EQ(vec.append_and_get_index(10), 4);
+}
+
+TEST(vector, AppendNonDuplicates)
+{
+  IntVector vec;
+  vec.append_non_duplicates(4);
+  EXPECT_EQ(vec.size(), 1);
+  vec.append_non_duplicates(5);
+  EXPECT_EQ(vec.size(), 2);
+  vec.append_non_duplicates(4);
+  EXPECT_EQ(vec.size(), 2);
+}
+
+TEST(vector, ExtendNonDuplicates)
+{
+  IntVector vec;
+  vec.extend_non_duplicates({1, 2});
+  EXPECT_EQ(vec.size(), 2);
+  vec.extend_non_duplicates({3, 4});
+  EXPECT_EQ(vec.size(), 4);
+  vec.extend_non_duplicates({0, 1, 2, 3});
+  EXPECT_EQ(vec.size(), 5);
+}
+
 TEST(vector, Fill)
 {
   IntVector vec(5);
@@ -339,6 +371,22 @@ TEST(vector, RemoveReorder)
   EXPECT_TRUE(vec.empty());
 }
 
+TEST(vector, RemoveFirstOccurrenceAndReorder)
+{
+  IntVector vec = {4, 5, 6, 7};
+  vec.remove_first_occurrence_and_reorder(5);
+  EXPECT_EQ(vec[0], 4);
+  EXPECT_EQ(vec[1], 7);
+  EXPECT_EQ(vec[2], 6);
+  vec.remove_first_occurrence_and_reorder(6);
+  EXPECT_EQ(vec[0], 4);
+  EXPECT_EQ(vec[1], 7);
+  vec.remove_first_occurrence_and_reorder(4);
+  EXPECT_EQ(vec[0], 7);
+  vec.remove_first_occurrence_and_reorder(7);
+  EXPECT_EQ(vec.size(), 0);
+}
+
 TEST(vector, AllEqual_False)
 {
   IntVector a = {1, 2, 3};

tests/gtests/blenlib/CMakeLists.txt

@@ -59,6 +59,7 @@ BLENDER_TEST(BLI_math_base "bf_blenlib")
 BLENDER_TEST(BLI_math_color "bf_blenlib")
 BLENDER_TEST(BLI_math_geom "bf_blenlib")
 BLENDER_TEST(BLI_memiter "bf_blenlib")
+BLENDER_TEST(BLI_optional "bf_blenlib")
 BLENDER_TEST(BLI_path_util "${BLI_path_util_extra_libs}")
 BLENDER_TEST(BLI_polyfill_2d "bf_blenlib")
 BLENDER_TEST(BLI_set "bf_blenlib")