[Bf-blender-cvs] [68cc982dcb7] master: BLI: improve various C++ data structures
Jacques Lucke
noreply at git.blender.org
Mon Feb 10 14:09:56 CET 2020
Commit: 68cc982dcb7c1063a96f7ec9b7ccb95da4919d6b
Author: Jacques Lucke
Date: Mon Feb 10 13:54:57 2020 +0100
Branches: master
https://developer.blender.org/rB68cc982dcb7c1063a96f7ec9b7ccb95da4919d6b
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.
===================================================================
M source/blender/blenlib/BLI_allocator.h
M source/blender/blenlib/BLI_array_cxx.h
M source/blender/blenlib/BLI_array_ref.h
M source/blender/blenlib/BLI_hash_cxx.h
M source/blender/blenlib/BLI_index_range.h
M source/blender/blenlib/BLI_kdtree.h
M source/blender/blenlib/BLI_listbase_wrapper.h
M source/blender/blenlib/BLI_map.h
M source/blender/blenlib/BLI_memory_utils_cxx.h
M source/blender/blenlib/BLI_open_addressing.h
A source/blender/blenlib/BLI_optional.h
M source/blender/blenlib/BLI_rand.h
M source/blender/blenlib/BLI_stack_cxx.h
M source/blender/blenlib/BLI_string_map.h
M source/blender/blenlib/BLI_string_ref.h
D source/blender/blenlib/BLI_temporary_allocator.h
D source/blender/blenlib/BLI_temporary_allocator_cxx.h
M source/blender/blenlib/BLI_vector.h
M source/blender/blenlib/BLI_vector_set.h
M source/blender/blenlib/CMakeLists.txt
M source/blender/blenlib/intern/BLI_index_range.cc
D source/blender/blenlib/intern/BLI_temporary_allocator.cc
M tests/gtests/blenlib/BLI_array_ref_test.cc
M tests/gtests/blenlib/BLI_index_range_test.cc
A tests/gtests/blenlib/BLI_optional_test.cc
M tests/gtests/blenlib/BLI_stack_cxx_test.cc
M tests/gtests/blenlib/BLI_string_map_test.cc
M tests/gtests/blenlib/BLI_string_ref_test.cc
M tests/gtests/blenlib/BLI_vector_test.cc
M tests/gtests/blenlib/CMakeLists.txt
===================================================================
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
@@ -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__ */
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/blend
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list