[Bf-blender-cvs] [d8678e02ece] master: BLI: generally improve C++ data structures
Jacques Lucke
noreply at git.blender.org
Tue Jun 9 10:16:27 CEST 2020
Commit: d8678e02ecec9375bec1dcf1388c6fc8b4ce3ad2
Author: Jacques Lucke
Date: Tue Jun 9 10:10:56 2020 +0200
Branches: master
https://developer.blender.org/rBd8678e02ecec9375bec1dcf1388c6fc8b4ce3ad2
BLI: generally improve C++ data structures
The main focus here was to improve the docs significantly. Furthermore,
I reimplemented `Set`, `Map` and `VectorSet`. They are now (usually)
faster, simpler and more customizable. I also rewrote `Stack` to make
it more efficient by avoiding unnecessary copies.
Thanks to everyone who helped with constructive feedback.
Approved by brecht and sybren.
Differential Revision: https://developer.blender.org/D7931
===================================================================
M .clang-format
M source/blender/blenlib/BLI_allocator.hh
M source/blender/blenlib/BLI_array.hh
M source/blender/blenlib/BLI_array_ref.hh
M source/blender/blenlib/BLI_dot_export.hh
M source/blender/blenlib/BLI_hash.hh
A source/blender/blenlib/BLI_hash_tables.hh
M source/blender/blenlib/BLI_index_range.hh
M source/blender/blenlib/BLI_linear_allocator.hh
M source/blender/blenlib/BLI_listbase_wrapper.hh
M source/blender/blenlib/BLI_map.hh
A source/blender/blenlib/BLI_map_slots.hh
M source/blender/blenlib/BLI_math_bits.h
M source/blender/blenlib/BLI_memory_utils.hh
D source/blender/blenlib/BLI_open_addressing.hh
M source/blender/blenlib/BLI_optional.hh
A source/blender/blenlib/BLI_probing_strategies.hh
M source/blender/blenlib/BLI_set.hh
A source/blender/blenlib/BLI_set_slots.hh
M source/blender/blenlib/BLI_stack.hh
D source/blender/blenlib/BLI_string_map.hh
M source/blender/blenlib/BLI_string_ref.hh
M source/blender/blenlib/BLI_utility_mixins.hh
M source/blender/blenlib/BLI_vector.hh
M source/blender/blenlib/BLI_vector_set.hh
A source/blender/blenlib/BLI_vector_set_slots.hh
M source/blender/blenlib/CMakeLists.txt
M source/blender/blenlib/intern/BLI_index_range.cc
M source/blender/blenlib/intern/math_bits_inline.c
M source/blender/depsgraph/intern/node/deg_node_id.cc
M source/blender/depsgraph/intern/node/deg_node_id.h
M source/blender/functions/FN_cpp_type.hh
M tests/gtests/blenlib/BLI_array_ref_test.cc
M tests/gtests/blenlib/BLI_array_test.cc
M tests/gtests/blenlib/BLI_index_range_test.cc
M tests/gtests/blenlib/BLI_linear_allocator_test.cc
M tests/gtests/blenlib/BLI_map_test.cc
A tests/gtests/blenlib/BLI_math_bits_test.cc
M tests/gtests/blenlib/BLI_optional_test.cc
M tests/gtests/blenlib/BLI_set_test.cc
M tests/gtests/blenlib/BLI_stack_cxx_test.cc
D tests/gtests/blenlib/BLI_string_map_test.cc
M tests/gtests/blenlib/BLI_string_ref_test.cc
D tests/gtests/blenlib/BLI_type_construct_mock.hh
M tests/gtests/blenlib/BLI_vector_set_test.cc
M tests/gtests/blenlib/BLI_vector_test.cc
M tests/gtests/blenlib/CMakeLists.txt
===================================================================
diff --git a/.clang-format b/.clang-format
index 88d06a56417..cb5cdab496f 100644
--- a/.clang-format
+++ b/.clang-format
@@ -257,6 +257,10 @@ ForEachMacros:
- SURFACE_QUAD_ITER_BEGIN
- foreach
- ED_screen_areas_iter
+ - SLOT_PROBING_BEGIN
+ - SET_SLOT_PROBING_BEGIN
+ - MAP_SLOT_PROBING_BEGIN
+ - VECTOR_SET_SLOT_PROBING_BEGIN
# Use once we bump the minimum version to version 8.
# # Without this string literals that in-line 'STRINGIFY' behave strangely (a bug?).
diff --git a/source/blender/blenlib/BLI_allocator.hh b/source/blender/blenlib/BLI_allocator.hh
index c52db4aab53..cf81b024277 100644
--- a/source/blender/blenlib/BLI_allocator.hh
+++ b/source/blender/blenlib/BLI_allocator.hh
@@ -19,14 +19,23 @@
/** \file
* \ingroup bli
*
- * This file offers a couple of memory allocators that can be used with containers such as Vector
- * and Map. Note that these allocators are not designed to work with standard containers like
+ * An `Allocator` can allocate and deallocate memory. It is used by containers such as BLI::Vector.
+ * The allocators defined in this file do not work with standard library containers such as
* std::vector.
*
- * Also see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html for why the standard
- * allocators are not a good fit applications like Blender. The current implementations in this
- * file are fairly simple still, more complexity can be added when necessary. For now they do their
- * job good enough.
+ * Every allocator has to implement two methods:
+ * void *allocate(size_t size, size_t alignment, const char *name);
+ * void deallocate(void *ptr);
+ *
+ * We don't use the std::allocator interface, because it does more than is really necessary for an
+ * allocator and has some other quirks. It mixes the concepts of allocation and construction. It is
+ * essentially forced to be a template, even though the allocator should not care about the type.
+ * Also see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html#std_allocator. Some
+ * of these aspects have been improved in new versions of C++, so we might have to reevaluate the
+ * strategy later on.
+ *
+ * The allocator interface dictated by this file is very simplistic, but for now that is all we
+ * need. More complexity can be added when it seems necessary.
*/
#include <algorithm>
@@ -40,18 +49,14 @@
namespace BLI {
/**
- * Use Blenders guarded allocator (aka MEM_malloc). This should always be used except there is a
+ * Use Blender's guarded allocator (aka MEM_*). This should always be used except there is a
* good reason not to use it.
*/
class GuardedAllocator {
public:
- void *allocate(uint size, const char *name)
- {
- return MEM_mallocN(size, name);
- }
-
- void *allocate_aligned(uint size, uint alignment, const char *name)
+ void *allocate(size_t size, size_t alignment, const char *name)
{
+ /* Should we use MEM_mallocN, when alignment is small? If yes, how small must alignment be? */
return MEM_mallocN_aligned(size, alignment, name);
}
@@ -62,8 +67,9 @@ class GuardedAllocator {
};
/**
- * This is a simple wrapper around malloc/free. Only use this when the GuardedAllocator cannot be
- * used. This can be the case when the allocated element might live longer than Blenders Allocator.
+ * This is a wrapper around malloc/free. Only use this when the GuardedAllocator cannot be
+ * used. This can be the case when the allocated memory might live longer than Blender's
+ * allocator. For example, when the memory is owned by a static variable.
*/
class RawAllocator {
private:
@@ -72,14 +78,7 @@ class RawAllocator {
};
public:
- void *allocate(uint size, const char *UNUSED(name))
- {
- void *ptr = malloc(size + sizeof(MemHead));
- ((MemHead *)ptr)->offset = sizeof(MemHead);
- return POINTER_OFFSET(ptr, sizeof(MemHead));
- }
-
- void *allocate_aligned(uint size, uint alignment, const char *UNUSED(name))
+ void *allocate(size_t size, size_t alignment, const char *UNUSED(name))
{
BLI_assert(is_power_of_2_i((int)alignment));
void *ptr = malloc(size + alignment + sizeof(MemHead));
diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh
index 9dd8341aa76..09eeb321abf 100644
--- a/source/blender/blenlib/BLI_array.hh
+++ b/source/blender/blenlib/BLI_array.hh
@@ -19,8 +19,23 @@
/** \file
* \ingroup bli
*
- * This is a container that contains a fixed size array. Note however, the size of the array is not
- * a template argument. Instead it can be specified at the construction time.
+ * A `BLI::Array<T>` is a container for a fixed size array the size of which is NOT known at
+ * compile time.
+ *
+ * If the size is known at compile time, `std::array<T, N>` should be used instead.
+ *
+ * BLI::Array should usually be used instead of BLI::Vector whenever the number of elements is
+ * known at construction time. Note however, that BLI::Array will default construct all elements
+ * when initialized with the size-constructor. For trivial types, this does nothing. In all other
+ * cases, this adds overhead. If this becomes a problem, a different constructor which does not do
+ * default construction can be added.
+ *
+ * A main benefit of using Array over Vector is that it expresses the intent of the developer
+ * better. It indicates that the size of the data structure is not expected to change. Furthermore,
+ * you can be more certain that an array does not overallocate.
+ *
+ * BLI::Array supports small object optimization to improve performance when the size turns out to
+ * be small at run-time.
*/
#include "BLI_allocator.hh"
@@ -31,42 +46,83 @@
namespace BLI {
-template<typename T, uint InlineBufferCapacity = 4, typename Allocator = GuardedAllocator>
+template<
+ /**
+ * The type of the values stored in the array.
+ */
+ typename T,
+ /**
+ * The number of values that can be stored in the array, without doing a heap allocation.
+ *
+ * When T is large, the small buffer optimization is disabled by default to avoid large
+ * unexpected allocations on the stack. It can still be enabled explicitely though.
+ */
+ uint InlineBufferCapacity = (sizeof(T) < 100) ? 4 : 0,
+ /**
+ * The allocator used by this array. Should rarely be changed, except when you don't want that
+ * MEM_* functions are used internally.
+ */
+ typename Allocator = GuardedAllocator>
class Array {
private:
+ /** The beginning of the array. It might point into the inline buffer. */
T *m_data;
+
+ /** Number of elements in the array. */
uint m_size;
+
+ /** Used for allocations when the inline buffer is too small. */
Allocator m_allocator;
- AlignedBuffer<sizeof(T) * InlineBufferCapacity, alignof(T)> m_inline_storage;
+
+ /** A placeholder buffer that will remain uninitialized until it is used. */
+ AlignedBuffer<sizeof(T) * InlineBufferCapacity, alignof(T)> m_inline_buffer;
public:
+ /**
+ * By default an empty array is created.
+ */
Array()
{
- m_data = this->inline_storage();
+ m_data = this->inline_buffer();
m_size = 0;
}
+ /**
+ * Create a new array that contains copies of all values.
+ */
Array(ArrayRef<T> values)
{
m_size = values.size();
m_data = this->get_buffer_for_size(values.size());
- uninitialized_copy_n(values.begin(), m_size, m_data);
+ uninitialized_copy_n(values.data(), m_size, m_data);
}
+ /**
+ * Create a new array that contains copies of all values.
+ */
Array(const std::initializer_list<T> &values) : Array(ArrayRef<T>(values))
{
}
+ /**
+ * Create a new array with the given size. All values will be default constructed. For trivial
+ * types like int, default construction does nothing.
+ *
+ * We might want another version of this in the future, that does not do default construction
+ * even for non-trivial types. This should not be the default though, because one can easily mess
+ * up when dealing with uninitialized memory.
+ */
explicit Array(uint 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();
- }
+ default_construct_n(m_data, size);
}
+ /**
+ * Create a new array with the given size. All values will be initialized by copying the given
+ * default.
+ */
Array(uint size, const T &value)
{
m_size = size;
@@ -74,21 +130,19 @@ class Array {
uninitialized_fill_n(m_data, m_size, value);
}
- Array(const Array &other)
+ Array(const Array &other) : m_allocator(other.m_allocator)
{
m_size = other.size();
- m_allocator = other.m_allocator;
m_data = this->get_buffer_for_size(other.size());
- uninitialized_copy_n(other.begin(), m_size, m_data);
+ uninitialized_copy_n(other.data(), m_size, m_data);
}
- Array(Array &&other) noexcept
+ Array(Array &&other) noexcept : m_allocator(other.m_allocator)
{
m_size = other.m_size;
- m_allocator = other.m_allocator;
- if (!other.uses_inline_storage()) {
+ if (!other.uses_inline_buffer()) {
m_data = other.m_data;
}
else {
@@ -96,14 +150,14 @@ class Array {
uninitialized_relocate_n(other.m_data, m_size, m_data);
}
- other.m_data = other.inline_storage();
+ other.m_data = other.inline_buffer();
other.m_size = 0;
}
~Array()
{
destruct_n(m_data, m_size);
- if (!this->uses_inline_storage()) {
+ if (!this->uses_inline_buffer()) {
m_allocator.deallocate((void *)m_data);
}
}
@@ -162,21 +216,50 @@ class Array {
return m_data[index];
}
+ /**
+ * Returns the number of elements in the array.
+ */
uint size() const
{
return m_size;
}
+ /**
+ * Returns true when the number of elements in the array is zero.
+ */
+ bool is_empty() const
+ {
+ return m_size == 0;
+ }
+
+ /**
+ * Copies the value to all indices in the array.
+ */
void fill(const T &value)
{
- MutableArrayRef<T>(*this).fill(value);
+ initialized_fill_n(m_data, m_size, value);
}
+ /**
+ * Copies the value to the given indices in the array
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list