diff options
author | Jacques Lucke <mail@jlucke.com> | 2020-02-10 15:54:57 +0300 |
---|---|---|
committer | Jacques Lucke <mail@jlucke.com> | 2020-02-10 16:09:01 +0300 |
commit | 68cc982dcb7c1063a96f7ec9b7ccb95da4919d6b (patch) | |
tree | 9d2076363b54cb6b6da96064453ac3499a5f65c8 | |
parent | 76208a5670bc9d70f99f22a3c49463959461b5c1 (diff) |
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.
30 files changed, 811 insertions, 288 deletions
diff --git a/source/blender/blenlib/BLI_allocator.h b/source/blender/blenlib/BLI_allocator.h index 82cf76e425c..075c181833c 100644 --- a/source/blender/blenlib/BLI_allocator.h +++ b/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__ */ diff --git a/source/blender/blenlib/BLI_array_cxx.h b/source/blender/blenlib/BLI_array_cxx.h index e987121d68c..adb00c95f28 100644 --- a/source/blender/blenlib/BLI_array_cxx.h +++ b/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 diff --git a/source/blender/blenlib/BLI_array_ref.h b/source/blender/blenlib/BLI_array_ref.h index bef7b862bf9..6cc96cedc83 100644 --- a/source/blender/blenlib/BLI_array_ref.h +++ b/source/blender/blenlib/BLI_array_ref.h @@ -79,6 +79,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__ */ diff --git a/source/blender/blenlib/BLI_hash_cxx.h b/source/blender/blenlib/BLI_hash_cxx.h index e899f27c9ee..a369774a471 100644 --- a/source/blender/blenlib/BLI_hash_cxx.h +++ b/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 diff --git a/source/blender/blenlib/BLI_index_range.h b/source/blender/blenlib/BLI_index_range.h index a1fed5bd97c..f67cc259227 100644 --- a/source/blender/blenlib/BLI_index_range.h +++ b/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. */ diff --git a/source/blender/blenlib/BLI_kdtree.h b/source/blender/blenlib/BLI_kdtree.h index 9e966ffb798..9ba045fdbf8 100644 --- a/source/blender/blenlib/BLI_kdtree.h +++ b/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__ */ diff --git a/source/blender/blenlib/BLI_listbase_wrapper.h b/source/blender/blenlib/BLI_listbase_wrapper.h index 34197fe9c45..d6832166e35 100644 --- a/source/blender/blenlib/BLI_listbase_wrapper.h +++ b/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 */ diff --git a/source/blender/blenlib/BLI_map.h b/source/blender/blenlib/BLI_map.h index 1edf7653c71..73b731252b6 100644 --- a/source/blender/blenlib/BLI_map.h +++ b/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"; diff --git a/source/blender/blenlib/BLI_memory_utils_cxx.h b/source/blender/blenlib/BLI_memory_utils_cxx.h index 22f333c6303..f15621b4e41 100644 --- a/source/blender/blenlib/BLI_memory_utils_cxx.h +++ b/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__ */ diff --git a/source/blender/blenlib/BLI_open_addressing.h b/source/blender/blenlib/BLI_open_addressing.h index 8ca5156a952..a238902c631 100644 --- a/source/blender/blenlib/BLI_open_addressing.h +++ b/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 diff --git a/source/blender/blenlib/BLI_optional.h b/source/blender/blenlib/BLI_optional.h new file mode 100644 index 00000000000..8429cddc710 --- /dev/null +++ b/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 */ diff --git a/source/blender/blenlib/BLI_rand.h b/source/blender/blenlib/BLI_rand.h index be2b18b05fd..ad8a90b3977 100644 --- a/source/blender/blenlib/BLI_rand.h +++ b/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. diff --git a/source/blender/blenlib/BLI_stack_cxx.h b/source/blender/blenlib/BLI_stack_cxx.h index 7915acadfac..a26318a3dcb 100644 --- a/source/blender/blenlib/BLI_stack_cxx.h +++ b/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]; } diff --git a/source/blender/blenlib/BLI_string_map.h b/source/blender/blenlib/BLI_string_map.h index ba870eb878a..2f09e489a7a 100644 --- a/source/blender/blenlib/BLI_string_map.h +++ b/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 { @@ -190,6 +191,22 @@ template<typename T, typename Allocator = GuardedAllocator> class StringMap { } /** + * 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. */ bool contains(StringRef key) const @@ -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 diff --git a/source/blender/blenlib/BLI_string_ref.h b/source/blender/blenlib/BLI_string_ref.h index 76163a2754c..54c2f0e7209 100644 --- a/source/blender/blenlib/BLI_string_ref.h +++ b/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__ */ diff --git a/source/blender/blenlib/BLI_temporary_allocator.h b/source/blender/blenlib/BLI_temporary_allocator.h deleted file mode 100644 index b378e5869c0..00000000000 --- a/source/blender/blenlib/BLI_temporary_allocator.h +++ /dev/null @@ -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__ */ diff --git a/source/blender/blenlib/BLI_temporary_allocator_cxx.h b/source/blender/blenlib/BLI_temporary_allocator_cxx.h deleted file mode 100644 index 06159f68059..00000000000 --- a/source/blender/blenlib/BLI_temporary_allocator_cxx.h +++ /dev/null @@ -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__ */ diff --git a/source/blender/blenlib/BLI_vector.h b/source/blender/blenlib/BLI_vector.h index 5c03a896692..60251347795 100644 --- a/source/blender/blenlib/BLI_vector.h +++ b/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) { @@ -457,12 +496,23 @@ template<typename T, uint N = 4, typename Allocator = GuardedAllocator> class Ve } /** + * 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 */ diff --git a/source/blender/blenlib/BLI_vector_set.h b/source/blender/blenlib/BLI_vector_set.h index fb21f7ed987..99d955c60d8 100644 --- a/source/blender/blenlib/BLI_vector_set.h +++ b/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; } diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index d22b1cd0ddb..2780e2becf8 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/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 diff --git a/source/blender/blenlib/intern/BLI_index_range.cc b/source/blender/blenlib/intern/BLI_index_range.cc index fde4dcf6d41..6421eb0794b 100644 --- a/source/blender/blenlib/intern/BLI_index_range.cc +++ b/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; } diff --git a/source/blender/blenlib/intern/BLI_temporary_allocator.cc b/source/blender/blenlib/intern/BLI_temporary_allocator.cc deleted file mode 100644 index b145e65530d..00000000000 --- a/source/blender/blenlib/intern/BLI_temporary_allocator.cc +++ /dev/null @@ -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); - } -} diff --git a/tests/gtests/blenlib/BLI_array_ref_test.cc b/tests/gtests/blenlib/BLI_array_ref_test.cc index 4507d9e6e84..538fadc1cf9 100644 --- a/tests/gtests/blenlib/BLI_array_ref_test.cc +++ b/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); +} diff --git a/tests/gtests/blenlib/BLI_index_range_test.cc b/tests/gtests/blenlib/BLI_index_range_test.cc index 1944279999d..c5c1f9a875b 100644 --- a/tests/gtests/blenlib/BLI_index_range_test.cc +++ b/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); diff --git a/tests/gtests/blenlib/BLI_optional_test.cc b/tests/gtests/blenlib/BLI_optional_test.cc new file mode 100644 index 00000000000..2e672967680 --- /dev/null +++ b/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); +} diff --git a/tests/gtests/blenlib/BLI_stack_cxx_test.cc b/tests/gtests/blenlib/BLI_stack_cxx_test.cc index 436f1f307b9..272bba05cb8 100644 --- a/tests/gtests/blenlib/BLI_stack_cxx_test.cc +++ b/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; diff --git a/tests/gtests/blenlib/BLI_string_map_test.cc b/tests/gtests/blenlib/BLI_string_map_test.cc index cc02a54e0c8..dfe96d63297 100644 --- a/tests/gtests/blenlib/BLI_string_map_test.cc +++ b/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); }); diff --git a/tests/gtests/blenlib/BLI_string_ref_test.cc b/tests/gtests/blenlib/BLI_string_ref_test.cc index 5605e10ac86..38a970455c0 100644 --- a/tests/gtests/blenlib/BLI_string_ref_test.cc +++ b/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"); +} diff --git a/tests/gtests/blenlib/BLI_vector_test.cc b/tests/gtests/blenlib/BLI_vector_test.cc index f258e50a60c..6cf67fb2488 100644 --- a/tests/gtests/blenlib/BLI_vector_test.cc +++ b/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}; diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt index c6b23615a5a..1a104fcb746 100644 --- a/tests/gtests/blenlib/CMakeLists.txt +++ b/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") |