From f7c0f1b8b83ac475755b633abf59cf9f447b2d49 Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Tue, 9 Jun 2020 11:58:47 +0200 Subject: BLI: rename ArrayRef to Span This also renames `MutableArrayRef` to `MutableSpan`. The name "Span" works better, because `std::span` will provide similar functionality in C++20. Furthermore, a shorter, more concise name for a common data structure is nice. --- source/blender/blenkernel/intern/simulation.cc | 14 +- source/blender/blenlib/BLI_array.hh | 22 +- source/blender/blenlib/BLI_array_ref.hh | 630 -------------------- source/blender/blenlib/BLI_dot_export.hh | 4 +- source/blender/blenlib/BLI_index_mask.hh | 14 +- source/blender/blenlib/BLI_index_range.hh | 6 +- source/blender/blenlib/BLI_linear_allocator.hh | 28 +- source/blender/blenlib/BLI_set.hh | 6 +- source/blender/blenlib/BLI_span.hh | 644 +++++++++++++++++++++ source/blender/blenlib/BLI_stack.hh | 12 +- source/blender/blenlib/BLI_string_ref.hh | 6 +- source/blender/blenlib/BLI_vector.hh | 28 +- source/blender/blenlib/BLI_vector_set.hh | 14 +- source/blender/blenlib/CMakeLists.txt | 2 +- source/blender/blenlib/intern/BLI_index_range.cc | 10 +- source/blender/blenlib/intern/dot_export.cc | 4 +- .../blender/depsgraph/intern/depsgraph_registry.cc | 2 +- .../blender/depsgraph/intern/depsgraph_registry.h | 2 +- source/blender/depsgraph/intern/depsgraph_type.h | 2 +- source/blender/modifiers/intern/MOD_mask.cc | 40 +- 20 files changed, 752 insertions(+), 738 deletions(-) delete mode 100644 source/blender/blenlib/BLI_array_ref.hh create mode 100644 source/blender/blenlib/BLI_span.hh (limited to 'source') diff --git a/source/blender/blenkernel/intern/simulation.cc b/source/blender/blenkernel/intern/simulation.cc index 8f08665ab8a..20a23ab8b38 100644 --- a/source/blender/blenkernel/intern/simulation.cc +++ b/source/blender/blenkernel/intern/simulation.cc @@ -27,11 +27,11 @@ #include "DNA_scene_types.h" #include "DNA_simulation_types.h" -#include "BLI_array_ref.hh" #include "BLI_compiler_compat.h" #include "BLI_float3.hh" #include "BLI_listbase.h" #include "BLI_math.h" +#include "BLI_span.hh" #include "BLI_string.h" #include "BLI_utildefines.h" @@ -54,9 +54,9 @@ #include "DEG_depsgraph.h" #include "DEG_depsgraph_query.h" -using blender::ArrayRef; using blender::float3; -using blender::MutableArrayRef; +using blender::MutableSpan; +using blender::Span; static void simulation_init_data(ID *id) { @@ -168,9 +168,9 @@ void *BKE_simulation_add(Main *bmain, const char *name) return simulation; } -static MutableArrayRef get_particle_positions(ParticleSimulationState *state) +static MutableSpan get_particle_positions(ParticleSimulationState *state) { - return MutableArrayRef( + return MutableSpan( (float3 *)CustomData_get_layer_named(&state->attributes, CD_LOCATION, "Position"), state->tot_particles); } @@ -239,7 +239,7 @@ void BKE_simulation_data_update(Depsgraph *depsgraph, Scene *scene, Simulation * CustomData_realloc(&state_orig->attributes, state_orig->tot_particles); ensure_attributes_exist(state_orig); - MutableArrayRef positions = get_particle_positions(state_orig); + MutableSpan positions = get_particle_positions(state_orig); for (uint i : positions.index_range()) { positions[i] = {i / 10.0f, 0, 0}; } @@ -250,7 +250,7 @@ void BKE_simulation_data_update(Depsgraph *depsgraph, Scene *scene, Simulation * else if (current_frame == state_orig->current_frame + 1) { state_orig->current_frame = current_frame; ensure_attributes_exist(state_orig); - MutableArrayRef positions = get_particle_positions(state_orig); + MutableSpan positions = get_particle_positions(state_orig); for (float3 &position : positions) { position.z += 0.1f; } diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh index 874cd6b215a..b929d1220da 100644 --- a/source/blender/blenlib/BLI_array.hh +++ b/source/blender/blenlib/BLI_array.hh @@ -39,9 +39,9 @@ */ #include "BLI_allocator.hh" -#include "BLI_array_ref.hh" #include "BLI_index_range.hh" #include "BLI_memory_utils.hh" +#include "BLI_span.hh" #include "BLI_utildefines.h" namespace blender { @@ -90,7 +90,7 @@ class Array { /** * Create a new array that contains copies of all values. */ - Array(ArrayRef values) + Array(Span values) { m_size = values.size(); m_data = this->get_buffer_for_size(values.size()); @@ -100,7 +100,7 @@ class Array { /** * Create a new array that contains copies of all values. */ - Array(const std::initializer_list &values) : Array(ArrayRef(values)) + Array(const std::initializer_list &values) : Array(Span(values)) { } @@ -184,22 +184,22 @@ class Array { return *this; } - operator ArrayRef() const + operator Span() const { - return ArrayRef(m_data, m_size); + return Span(m_data, m_size); } - operator MutableArrayRef() + operator MutableSpan() { - return MutableArrayRef(m_data, m_size); + return MutableSpan(m_data, m_size); } - ArrayRef as_ref() const + Span as_span() const { return *this; } - MutableArrayRef as_mutable_ref() + MutableSpan as_mutable_span() { return *this; } @@ -243,9 +243,9 @@ class Array { /** * Copies the value to the given indices in the array. */ - void fill_indices(ArrayRef indices, const T &value) + void fill_indices(Span indices, const T &value) { - MutableArrayRef(*this).fill_indices(indices, value); + MutableSpan(*this).fill_indices(indices, value); } /** diff --git a/source/blender/blenlib/BLI_array_ref.hh b/source/blender/blenlib/BLI_array_ref.hh deleted file mode 100644 index 2a4d0b6e0df..00000000000 --- a/source/blender/blenlib/BLI_array_ref.hh +++ /dev/null @@ -1,630 +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_ARRAY_REF_HH__ -#define __BLI_ARRAY_REF_HH__ - -/** \file - * \ingroup bli - * - * An `blender::ArrayRef` references an array that is owned by someone else. It is just a - * pointer and a size. Since the memory is not owned, ArrayRef should not be used to transfer - * ownership. The array cannot be modified through the ArrayRef. However, if T is a non-const - * pointer, the pointed-to elements can be modified. - * - * There is also `blender::MutableArrayRef`. It is mostly the same as ArrayRef, but allows the - * array to be modified. - * - * An (Mutable)ArrayRef can refer to data owned by many different data structures including - * blender::Vector, blender::Array, blender::VectorSet, std::vector, std::array, std::string, - * std::initializer_list and c-style array. - * - * `blender::ArrayRef` should be your default choice when you have to pass a read-only array - * into a function. It is better than passing a `const Vector &`, because then the function only - * works for vectors and not for e.g. arrays. Using ArrayRef as function parameter makes it usable - * in more contexts, better expresses the intent and does not sacrifice performance. It is also - * better than passing a raw pointer and size separately, because it is more convenient and safe. - * - * `blender::MutableArrayRef` can be used when a function is supposed to return an array, the - * size of which is known before the function is called. One advantage of this approach is that the - * caller is responsible for allocation and deallocation. Furthermore, the function can focus on - * its task, without having to worry about memory allocation. Alternatively, a function could - * return an Array or Vector. - * - * Note: When a function has a MutableArrayRef output parameter and T is not a trivial type, - * then the function has to specify whether the referenced array is expected to be initialized or - * not. - * - * Since the arrays are only referenced, it is generally unsafe to store an ArrayRef. When you - * store one, you should know who owns the memory. - * - * Instances of ArrayRef and MutableArrayRef are small and should be passed by value. - */ - -#include -#include -#include -#include -#include - -#include "BLI_index_range.hh" -#include "BLI_memory_utils.hh" -#include "BLI_utildefines.h" - -namespace blender { - -/** - * References an array of type T that is owned by someone else. The data in the array cannot be - * modified. - */ -template class ArrayRef { - private: - const T *m_start = nullptr; - uint m_size = 0; - - public: - /** - * Create a reference to an empty array. - */ - ArrayRef() = default; - - ArrayRef(const T *start, uint size) : m_start(start), m_size(size) - { - } - - /** - * Reference an initializer_list. Note that the data in the initializer_list is only valid until - * the expression containing it is fully computed. - * - * Do: - * call_function_with_array({1, 2, 3, 4}); - * - * Don't: - * ArrayRef ref = {1, 2, 3, 4}; - * call_function_with_array(ref); - */ - ArrayRef(const std::initializer_list &list) : ArrayRef(list.begin(), (uint)list.size()) - { - } - - ArrayRef(const std::vector &vector) : ArrayRef(vector.data(), (uint)vector.size()) - { - } - - template ArrayRef(const std::array &array) : ArrayRef(array.data(), N) - { - } - - /** - * Support implicit conversions like the ones below: - * ArrayRef -> ArrayRef - * ArrayRef -> ArrayRef - */ - template::value>::type * = nullptr> - ArrayRef(ArrayRef array) : ArrayRef((T *)array.data(), array.size()) - { - } - - /** - * Returns a contiguous part of the array. This invokes undefined behavior when the slice does - * not stay within the bounds of the array. - */ - ArrayRef slice(uint start, uint size) const - { - BLI_assert(start + size <= this->size() || size == 0); - return ArrayRef(m_start + start, size); - } - - ArrayRef slice(IndexRange range) const - { - return this->slice(range.start(), range.size()); - } - - /** - * Returns a new ArrayRef with n elements removed from the beginning. This invokes undefined - * behavior when the array is too small. - */ - ArrayRef drop_front(uint n) const - { - BLI_assert(n <= this->size()); - return this->slice(n, this->size() - n); - } - - /** - * Returns a new ArrayRef with n elements removed from the beginning. This invokes undefined - * behavior when the array is too small. - */ - ArrayRef drop_back(uint n) const - { - BLI_assert(n <= this->size()); - return this->slice(0, this->size() - n); - } - - /** - * Returns a new ArrayRef that only contains the first n elements. This invokes undefined - * behavior when the array is too small. - */ - ArrayRef take_front(uint n) const - { - BLI_assert(n <= this->size()); - return this->slice(0, n); - } - - /** - * Returns a new ArrayRef that only contains the last n elements. This invokes undefined - * behavior when the array is too small. - */ - ArrayRef take_back(uint n) const - { - BLI_assert(n <= this->size()); - return this->slice(this->size() - n, n); - } - - /** - * Returns the pointer to the beginning of the referenced array. This may be nullptr when the - * size is zero. - */ - const T *data() const - { - return m_start; - } - - const T *begin() const - { - return m_start; - } - - const T *end() const - { - return m_start + m_size; - } - - /** - * Access an element in the array. This invokes undefined behavior when the index is out of - * bounds. - */ - const T &operator[](uint index) const - { - BLI_assert(index < m_size); - return m_start[index]; - } - - /** - * Returns the number of elements in the referenced array. - */ - uint size() const - { - return m_size; - } - - /** - * Returns true if the size is zero. - */ - bool is_empty() const - { - return m_size == 0; - } - - /** - * Returns the number of bytes referenced by this ArrayRef. - */ - uint size_in_bytes() const - { - return sizeof(T) * m_size; - } - - /** - * Does a linear search to see of the value is in the array. - * Returns true if it is, otherwise false. - */ - bool contains(const T &value) const - { - for (const T &element : *this) { - if (element == value) { - return true; - } - } - return false; - } - - /** - * Does a constant time check to see if the pointer points to a value in the referenced array. - * Return true if it is, otherwise false. - */ - bool contains_ptr(const T *ptr) const - { - return (this->begin() <= ptr) && (ptr < this->end()); - } - - /** - * Does a linear search to count how often the value is in the array. - * Returns the number of occurrences. - */ - uint count(const T &value) const - { - uint counter = 0; - for (const T &element : *this) { - if (element == value) { - counter++; - } - } - return counter; - } - - /** - * Return a reference to the first element in the array. This invokes undefined behavior when the - * array is empty. - */ - const T &first() const - { - BLI_assert(m_size > 0); - return m_start[0]; - } - - /** - * Returns a reference to the last element in the array. This invokes undefined behavior when the - * array is empty. - */ - const T &last() const - { - BLI_assert(m_size > 0); - return m_start[m_size - 1]; - } - - /** - * Returns the element at the given index. If the index is out of range, return the fallback - * value. - */ - T get(uint index, const T &fallback) const - { - if (index < m_size) { - return m_start[index]; - } - return fallback; - } - - /** - * 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; - } - - /** - * Returns true when this and the other array have an element in common. This should only be - * called on small arrays, because it has a running time of O(n*m) where n and m are the sizes of - * the arrays. - */ - 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; - } - - /** - * Returns the index of the first occurrence of the given value. This invokes undefined behavior - * when the value is not in the array. - */ - uint first_index(const T &search_value) const - { - int index = this->first_index_try(search_value); - BLI_assert(index >= 0); - return (uint)index; - } - - /** - * Returns the index of the first occurrence of the given value or -1 if it does not exist. - */ - 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; - } - - /** - * 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); - } - - /** - * Returns a new ArrayRef to the same underlying memory buffer. No conversions are done. - */ - template ArrayRef cast() const - { - BLI_assert((m_size * sizeof(T)) % sizeof(NewT) == 0); - uint new_size = m_size * sizeof(T) / sizeof(NewT); - return ArrayRef(reinterpret_cast(m_start), new_size); - } - - /** - * A debug utility to print the content of the ArrayRef. Every element will be printed on a - * separate line using the given callback. - */ - template void print_as_lines(std::string name, PrintLineF print_line) const - { - std::cout << "ArrayRef: " << name << " \tSize:" << m_size << '\n'; - for (const T &value : *this) { - std::cout << " "; - print_line(value); - std::cout << '\n'; - } - } - - /** - * A debug utility to print the content of the array ref. Every element be printed on a separate - * line. - */ - void print_as_lines(std::string name) const - { - this->print_as_lines(name, [](const T &value) { std::cout << value; }); - } -}; - -/** - * Mostly the same as ArrayRef, except that one can change the array elements through a - * MutableArrayRef. - */ -template class MutableArrayRef { - private: - T *m_start; - uint m_size; - - public: - MutableArrayRef() = default; - - MutableArrayRef(T *start, uint size) : m_start(start), m_size(size) - { - } - - /** - * Reference an initializer_list. Note that the data in the initializer_list is only valid until - * the expression containing it is fully computed. - * - * Do: - * call_function_with_array({1, 2, 3, 4}); - * - * Don't: - * MutableArrayRef ref = {1, 2, 3, 4}; - * call_function_with_array(ref); - */ - MutableArrayRef(std::initializer_list &list) : MutableArrayRef(list.begin(), list.size()) - { - } - - MutableArrayRef(std::vector &vector) : MutableArrayRef(vector.data(), vector.size()) - { - } - - template - MutableArrayRef(std::array &array) : MutableArrayRef(array.data(), N) - { - } - - operator ArrayRef() const - { - return ArrayRef(m_start, m_size); - } - - /** - * Returns the number of elements in the array. - */ - uint size() const - { - return m_size; - } - - /** - * Replace all elements in the referenced array with the given value. - */ - void fill(const T &value) - { - initialized_fill_n(m_start, m_size, value); - } - - /** - * Replace a subset of all elements with the given value. This invokes undefined behavior when - * one of the indices is out of bounds. - */ - void fill_indices(ArrayRef indices, const T &value) - { - for (uint i : indices) { - BLI_assert(i < m_size); - m_start[i] = value; - } - } - - /** - * Returns a pointer to the beginning of the referenced array. This may be nullptr, when the size - * is zero. - */ - T *data() const - { - return m_start; - } - - T *begin() const - { - return m_start; - } - - T *end() const - { - return m_start + m_size; - } - - T &operator[](uint index) const - { - BLI_assert(index < this->size()); - return m_start[index]; - } - - /** - * Returns a contiguous part of the array. This invokes undefined behavior when the slice would - * go out of bounds. - */ - MutableArrayRef slice(uint start, uint length) const - { - BLI_assert(start + length <= this->size()); - return MutableArrayRef(m_start + start, length); - } - - /** - * Returns a new MutableArrayRef with n elements removed from the beginning. This invokes - * undefined behavior when the array is too small. - */ - MutableArrayRef drop_front(uint n) const - { - BLI_assert(n <= this->size()); - return this->slice(n, this->size() - n); - } - - /** - * Returns a new MutableArrayRef with n elements removed from the end. This invokes undefined - * behavior when the array is too small. - */ - MutableArrayRef drop_back(uint n) const - { - BLI_assert(n <= this->size()); - return this->slice(0, this->size() - n); - } - - /** - * Returns a new MutableArrayRef that only contains the first n elements. This invokes undefined - * behavior when the array is too small. - */ - MutableArrayRef take_front(uint n) const - { - BLI_assert(n <= this->size()); - return this->slice(0, n); - } - - /** - * Return a new MutableArrayRef that only contains the last n elements. This invokes undefined - * behavior when the array is too small. - */ - MutableArrayRef take_back(uint n) const - { - BLI_assert(n <= this->size()); - return this->slice(this->size() - n, n); - } - - /** - * Returns an (immutable) ArrayRef that references the same array. This is usually not needed, - * due to implicit conversions. However, sometimes automatic type deduction needs some help. - */ - ArrayRef as_ref() const - { - return ArrayRef(m_start, m_size); - } - - /** - * 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); - } - - /** - * Returns a reference to the last element. This invokes undefined behavior when the array is - * empty. - */ - const T &last() const - { - BLI_assert(m_size > 0); - return m_start[m_size - 1]; - } - - /** - * Returns a new array ref to the same underlying memory buffer. No conversions are done. - */ - template MutableArrayRef cast() const - { - BLI_assert((m_size * sizeof(T)) % sizeof(NewT) == 0); - uint new_size = m_size * sizeof(T) / sizeof(NewT); - return MutableArrayRef(reinterpret_cast(m_start), new_size); - } -}; - -/** - * Shorthand to make use of automatic template parameter deduction. - */ -template ArrayRef ref_c_array(const T *array, uint size) -{ - return ArrayRef(array, size); -} - -/** - * Utilities to check that arrays have the same size in debug builds. - */ -template 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 -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 blender */ - -#endif /* __BLI_ARRAY_REF_HH__ */ diff --git a/source/blender/blenlib/BLI_dot_export.hh b/source/blender/blenlib/BLI_dot_export.hh index 60353d7913f..67af4391a55 100644 --- a/source/blender/blenlib/BLI_dot_export.hh +++ b/source/blender/blenlib/BLI_dot_export.hh @@ -267,8 +267,8 @@ class NodeWithSocketsRef { public: NodeWithSocketsRef(Node &node, StringRef name, - ArrayRef input_names, - ArrayRef output_names); + Span input_names, + Span output_names); NodePort input(uint index) const { diff --git a/source/blender/blenlib/BLI_index_mask.hh b/source/blender/blenlib/BLI_index_mask.hh index 4cd348215fe..cc1bf05f936 100644 --- a/source/blender/blenlib/BLI_index_mask.hh +++ b/source/blender/blenlib/BLI_index_mask.hh @@ -38,15 +38,15 @@ * same time. */ -#include "BLI_array_ref.hh" #include "BLI_index_range.hh" +#include "BLI_span.hh" namespace blender { class IndexMask { private: /* The underlying reference to sorted integers. */ - ArrayRef m_indices; + Span m_indices; public: /* Creates an IndexMask that contains no indices. */ @@ -57,7 +57,7 @@ class IndexMask { * This constructor asserts that the given integers are in ascending order and that there are no * duplicates. */ - IndexMask(ArrayRef indices) : m_indices(indices) + IndexMask(Span indices) : m_indices(indices) { #ifdef DEBUG for (uint i = 1; i < indices.size(); i++) { @@ -70,7 +70,7 @@ class IndexMask { * Use this method when you know that no indices are skipped. It is more efficient than preparing * an integer array all the time. */ - IndexMask(IndexRange range) : m_indices(range.as_array_ref()) + IndexMask(IndexRange range) : m_indices(range.as_span()) { } @@ -84,7 +84,7 @@ class IndexMask { * Do this: * do_something_with_an_index_mask({3, 4, 5}); */ - IndexMask(const std::initializer_list &indices) : IndexMask(ArrayRef(indices)) + IndexMask(const std::initializer_list &indices) : IndexMask(Span(indices)) { } @@ -95,7 +95,7 @@ class IndexMask { { } - operator ArrayRef() const + operator Span() const { return m_indices; } @@ -133,7 +133,7 @@ class IndexMask { } } - ArrayRef indices() const + Span indices() const { return m_indices; } diff --git a/source/blender/blenlib/BLI_index_range.hh b/source/blender/blenlib/BLI_index_range.hh index 8a97facd9c0..25192429a5d 100644 --- a/source/blender/blenlib/BLI_index_range.hh +++ b/source/blender/blenlib/BLI_index_range.hh @@ -49,7 +49,7 @@ * Ideally this could be could be even closer to Python's enumerate(). We might get that in the * future with newer C++ versions. * - * One other important feature is the as_array_ref method. This method returns an ArrayRef + * One other important feature is the as_span method. This method returns an Span * that contains the interval as individual numbers. */ @@ -66,7 +66,7 @@ template class blocked_range; namespace blender { -template class ArrayRef; +template class Span; class IndexRange { private: @@ -227,7 +227,7 @@ class IndexRange { /** * Get read-only access to a memory buffer that contains the range as actual numbers. */ - ArrayRef as_array_ref() const; + Span as_span() const; friend std::ostream &operator<<(std::ostream &stream, IndexRange range) { diff --git a/source/blender/blenlib/BLI_linear_allocator.hh b/source/blender/blenlib/BLI_linear_allocator.hh index e2bb3ce02cb..f968f9f15ce 100644 --- a/source/blender/blenlib/BLI_linear_allocator.hh +++ b/source/blender/blenlib/BLI_linear_allocator.hh @@ -35,7 +35,7 @@ template class LinearAllocator : NonCopya private: Allocator m_allocator; Vector m_owned_buffers; - Vector> m_unused_borrowed_buffers; + Vector> m_unused_borrowed_buffers; uintptr_t m_current_begin; uintptr_t m_current_end; @@ -104,9 +104,9 @@ template class LinearAllocator : NonCopya * * This method only allocates memory and does not construct the instance. */ - template MutableArrayRef allocate_array(uint size) + template MutableSpan allocate_array(uint size) { - return MutableArrayRef((T *)this->allocate(sizeof(T) * size, alignof(T)), size); + return MutableSpan((T *)this->allocate(sizeof(T) * size, alignof(T)), size); } /** @@ -127,9 +127,9 @@ template class LinearAllocator : NonCopya /** * Copy the given array into a memory buffer provided by this allocator. */ - template MutableArrayRef construct_array_copy(ArrayRef src) + template MutableSpan construct_array_copy(Span src) { - MutableArrayRef dst = this->allocate_array(src.size()); + MutableSpan dst = this->allocate_array(src.size()); uninitialized_copy_n(src.data(), src.size(), dst.data()); return dst; } @@ -146,14 +146,14 @@ template class LinearAllocator : NonCopya return StringRefNull((const char *)buffer); } - MutableArrayRef allocate_elements_and_pointer_array(uint element_amount, - uint element_size, - uint element_alignment) + MutableSpan allocate_elements_and_pointer_array(uint element_amount, + uint element_size, + uint element_alignment) { void *pointer_buffer = this->allocate(element_amount * sizeof(void *), alignof(void *)); void *elements_buffer = this->allocate(element_amount * element_size, element_alignment); - MutableArrayRef pointers((void **)pointer_buffer, element_amount); + MutableSpan pointers((void **)pointer_buffer, element_amount); void *next_element_buffer = elements_buffer; for (uint i : IndexRange(element_amount)) { pointers[i] = next_element_buffer; @@ -164,11 +164,11 @@ template class LinearAllocator : NonCopya } template - ArrayRef construct_elements_and_pointer_array(uint n, Args &&... args) + Span construct_elements_and_pointer_array(uint n, Args &&... args) { - MutableArrayRef void_pointers = this->allocate_elements_and_pointer_array( + MutableSpan void_pointers = this->allocate_elements_and_pointer_array( n, sizeof(T), alignof(T)); - MutableArrayRef pointers = void_pointers.cast(); + MutableSpan pointers = void_pointers.cast(); for (uint i : IndexRange(n)) { new (pointers[i]) T(std::forward(args)...); @@ -183,7 +183,7 @@ template class LinearAllocator : NonCopya */ void provide_buffer(void *buffer, uint size) { - m_unused_borrowed_buffers.append(ArrayRef((char *)buffer, size)); + m_unused_borrowed_buffers.append(Span((char *)buffer, size)); } template @@ -196,7 +196,7 @@ template class LinearAllocator : NonCopya void allocate_new_buffer(uint min_allocation_size) { for (uint i : m_unused_borrowed_buffers.index_range()) { - ArrayRef buffer = m_unused_borrowed_buffers[i]; + Span buffer = m_unused_borrowed_buffers[i]; if (buffer.size() >= min_allocation_size) { m_unused_borrowed_buffers.remove_and_reorder(i); m_current_begin = (uintptr_t)buffer.begin(); diff --git a/source/blender/blenlib/BLI_set.hh b/source/blender/blenlib/BLI_set.hh index 5bdf99360cb..ece9fb05d8c 100644 --- a/source/blender/blenlib/BLI_set.hh +++ b/source/blender/blenlib/BLI_set.hh @@ -276,7 +276,7 @@ class Set { * We might be able to make this faster than sequentially adding all keys, but that is not * implemented yet. */ - void add_multiple(ArrayRef keys) + void add_multiple(Span keys) { for (const Key &key : keys) { this->add(key); @@ -287,7 +287,7 @@ class Set { * Convenience function to add many new keys to the set at once. The keys must not exist in the * set before and there must not be duplicates in the array. */ - void add_multiple_new(ArrayRef keys) + void add_multiple_new(Span keys) { for (const Key &key : keys) { this->add_new(key); @@ -726,7 +726,7 @@ template class StdUnorderedSetWrapper { return m_set.insert(std::move(key)).second; } - void add_multiple(ArrayRef keys) + void add_multiple(Span keys) { for (const Key &key : keys) { m_set.insert(key); diff --git a/source/blender/blenlib/BLI_span.hh b/source/blender/blenlib/BLI_span.hh new file mode 100644 index 00000000000..23f0f161e01 --- /dev/null +++ b/source/blender/blenlib/BLI_span.hh @@ -0,0 +1,644 @@ +/* + * 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_SPAN_HH__ +#define __BLI_SPAN_HH__ + +/** \file + * \ingroup bli + * + * An `blender::Span` references an array that is owned by someone else. It is just a + * pointer and a size. Since the memory is not owned, Span should not be used to transfer + * ownership. The array cannot be modified through the Span. However, if T is a non-const + * pointer, the pointed-to elements can be modified. + * + * There is also `blender::MutableSpan`. It is mostly the same as Span, but allows the + * array to be modified. + * + * A (Mutable)Span can refer to data owned by many different data structures including + * blender::Vector, blender::Array, blender::VectorSet, std::vector, std::array, std::string, + * std::initializer_list and c-style array. + * + * `blender::Span` is very similar to `std::span` (C++20). However, there are a few differences: + * - `blender::Span` is const by default. This is to avoid making things mutable when they don't + * have to be. To get a non-const span, you need to use `blender::MutableSpan`. Below is a list + * of const-behavior-equivalent pairs of data structures: + * - std::span <==> blender::MutableSpan + * - std::span <==> blender::Span + * - std::span <==> blender::MutableSpan + * - std::span <==> blender::MutableSpan + * - std::span <==> blender::Span + * - std::span <==> blender::Span + * - `blender::Span` always has a dynamic extent, while `std::span` can have a size that is + * determined at compile time. I did not have a use case for that yet. If we need it, we can + * decide to add this functionality to `blender::Span` or introduce a new type like + * `blender::FixedSpan`. + * + * `blender::Span` should be your default choice when you have to pass a read-only array + * into a function. It is better than passing a `const Vector &`, because then the function only + * works for vectors and not for e.g. arrays. Using Span as function parameter makes it usable + * in more contexts, better expresses the intent and does not sacrifice performance. It is also + * better than passing a raw pointer and size separately, because it is more convenient and safe. + * + * `blender::MutableSpan` can be used when a function is supposed to return an array, the + * size of which is known before the function is called. One advantage of this approach is that the + * caller is responsible for allocation and deallocation. Furthermore, the function can focus on + * its task, without having to worry about memory allocation. Alternatively, a function could + * return an Array or Vector. + * + * Note: When a function has a MutableSpan output parameter and T is not a trivial type, + * then the function has to specify whether the referenced array is expected to be initialized or + * not. + * + * Since the arrays are only referenced, it is generally unsafe to store an Span. When you + * store one, you should know who owns the memory. + * + * Instances of Span and MutableSpan are small and should be passed by value. + */ + +#include +#include +#include +#include +#include + +#include "BLI_index_range.hh" +#include "BLI_memory_utils.hh" +#include "BLI_utildefines.h" + +namespace blender { + +/** + * References an array of type T that is owned by someone else. The data in the array cannot be + * modified. + */ +template class Span { + private: + const T *m_start = nullptr; + uint m_size = 0; + + public: + /** + * Create a reference to an empty array. + */ + Span() = default; + + Span(const T *start, uint size) : m_start(start), m_size(size) + { + } + + /** + * Reference an initializer_list. Note that the data in the initializer_list is only valid until + * the expression containing it is fully computed. + * + * Do: + * call_function_with_array({1, 2, 3, 4}); + * + * Don't: + * Span span = {1, 2, 3, 4}; + * call_function_with_array(span); + */ + Span(const std::initializer_list &list) : Span(list.begin(), (uint)list.size()) + { + } + + Span(const std::vector &vector) : Span(vector.data(), (uint)vector.size()) + { + } + + template Span(const std::array &array) : Span(array.data(), N) + { + } + + /** + * Support implicit conversions like the ones below: + * Span -> Span + * Span -> Span + */ + template::value>::type * = nullptr> + Span(Span array) : Span((T *)array.data(), array.size()) + { + } + + /** + * Returns a contiguous part of the array. This invokes undefined behavior when the slice does + * not stay within the bounds of the array. + */ + Span slice(uint start, uint size) const + { + BLI_assert(start + size <= this->size() || size == 0); + return Span(m_start + start, size); + } + + Span slice(IndexRange range) const + { + return this->slice(range.start(), range.size()); + } + + /** + * Returns a new Span with n elements removed from the beginning. This invokes undefined + * behavior when the array is too small. + */ + Span drop_front(uint n) const + { + BLI_assert(n <= this->size()); + return this->slice(n, this->size() - n); + } + + /** + * Returns a new Span with n elements removed from the beginning. This invokes undefined + * behavior when the array is too small. + */ + Span drop_back(uint n) const + { + BLI_assert(n <= this->size()); + return this->slice(0, this->size() - n); + } + + /** + * Returns a new Span that only contains the first n elements. This invokes undefined + * behavior when the array is too small. + */ + Span take_front(uint n) const + { + BLI_assert(n <= this->size()); + return this->slice(0, n); + } + + /** + * Returns a new Span that only contains the last n elements. This invokes undefined + * behavior when the array is too small. + */ + Span take_back(uint n) const + { + BLI_assert(n <= this->size()); + return this->slice(this->size() - n, n); + } + + /** + * Returns the pointer to the beginning of the referenced array. This may be nullptr when the + * size is zero. + */ + const T *data() const + { + return m_start; + } + + const T *begin() const + { + return m_start; + } + + const T *end() const + { + return m_start + m_size; + } + + /** + * Access an element in the array. This invokes undefined behavior when the index is out of + * bounds. + */ + const T &operator[](uint index) const + { + BLI_assert(index < m_size); + return m_start[index]; + } + + /** + * Returns the number of elements in the referenced array. + */ + uint size() const + { + return m_size; + } + + /** + * Returns true if the size is zero. + */ + bool is_empty() const + { + return m_size == 0; + } + + /** + * Returns the number of bytes referenced by this Span. + */ + uint size_in_bytes() const + { + return sizeof(T) * m_size; + } + + /** + * Does a linear search to see of the value is in the array. + * Returns true if it is, otherwise false. + */ + bool contains(const T &value) const + { + for (const T &element : *this) { + if (element == value) { + return true; + } + } + return false; + } + + /** + * Does a constant time check to see if the pointer points to a value in the referenced array. + * Return true if it is, otherwise false. + */ + bool contains_ptr(const T *ptr) const + { + return (this->begin() <= ptr) && (ptr < this->end()); + } + + /** + * Does a linear search to count how often the value is in the array. + * Returns the number of occurrences. + */ + uint count(const T &value) const + { + uint counter = 0; + for (const T &element : *this) { + if (element == value) { + counter++; + } + } + return counter; + } + + /** + * Return a reference to the first element in the array. This invokes undefined behavior when the + * array is empty. + */ + const T &first() const + { + BLI_assert(m_size > 0); + return m_start[0]; + } + + /** + * Returns a reference to the last element in the array. This invokes undefined behavior when the + * array is empty. + */ + const T &last() const + { + BLI_assert(m_size > 0); + return m_start[m_size - 1]; + } + + /** + * Returns the element at the given index. If the index is out of range, return the fallback + * value. + */ + T get(uint index, const T &fallback) const + { + if (index < m_size) { + return m_start[index]; + } + return fallback; + } + + /** + * 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; + } + + /** + * Returns true when this and the other array have an element in common. This should only be + * called on small arrays, because it has a running time of O(n*m) where n and m are the sizes of + * the arrays. + */ + bool intersects__linear_search(Span 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; + } + + /** + * Returns the index of the first occurrence of the given value. This invokes undefined behavior + * when the value is not in the array. + */ + uint first_index(const T &search_value) const + { + int index = this->first_index_try(search_value); + BLI_assert(index >= 0); + return (uint)index; + } + + /** + * Returns the index of the first occurrence of the given value or -1 if it does not exist. + */ + 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; + } + + /** + * 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); + } + + /** + * Returns a new Span to the same underlying memory buffer. No conversions are done. + */ + template Span cast() const + { + BLI_assert((m_size * sizeof(T)) % sizeof(NewT) == 0); + uint new_size = m_size * sizeof(T) / sizeof(NewT); + return Span(reinterpret_cast(m_start), new_size); + } + + /** + * A debug utility to print the content of the Span. Every element will be printed on a + * separate line using the given callback. + */ + template void print_as_lines(std::string name, PrintLineF print_line) const + { + std::cout << "Span: " << name << " \tSize:" << m_size << '\n'; + for (const T &value : *this) { + std::cout << " "; + print_line(value); + std::cout << '\n'; + } + } + + /** + * A debug utility to print the content of the span. Every element be printed on a separate + * line. + */ + void print_as_lines(std::string name) const + { + this->print_as_lines(name, [](const T &value) { std::cout << value; }); + } +}; + +/** + * Mostly the same as Span, except that one can change the array elements through a + * MutableSpan. + */ +template class MutableSpan { + private: + T *m_start; + uint m_size; + + public: + MutableSpan() = default; + + MutableSpan(T *start, uint size) : m_start(start), m_size(size) + { + } + + /** + * Reference an initializer_list. Note that the data in the initializer_list is only valid until + * the expression containing it is fully computed. + * + * Do: + * call_function_with_array({1, 2, 3, 4}); + * + * Don't: + * MutableSpan span = {1, 2, 3, 4}; + * call_function_with_array(span); + */ + MutableSpan(std::initializer_list &list) : MutableSpan(list.begin(), list.size()) + { + } + + MutableSpan(std::vector &vector) : MutableSpan(vector.data(), vector.size()) + { + } + + template MutableSpan(std::array &array) : MutableSpan(array.data(), N) + { + } + + operator Span() const + { + return Span(m_start, m_size); + } + + /** + * Returns the number of elements in the array. + */ + uint size() const + { + return m_size; + } + + /** + * Replace all elements in the referenced array with the given value. + */ + void fill(const T &value) + { + initialized_fill_n(m_start, m_size, value); + } + + /** + * Replace a subset of all elements with the given value. This invokes undefined behavior when + * one of the indices is out of bounds. + */ + void fill_indices(Span indices, const T &value) + { + for (uint i : indices) { + BLI_assert(i < m_size); + m_start[i] = value; + } + } + + /** + * Returns a pointer to the beginning of the referenced array. This may be nullptr, when the size + * is zero. + */ + T *data() const + { + return m_start; + } + + T *begin() const + { + return m_start; + } + + T *end() const + { + return m_start + m_size; + } + + T &operator[](uint index) const + { + BLI_assert(index < this->size()); + return m_start[index]; + } + + /** + * Returns a contiguous part of the array. This invokes undefined behavior when the slice would + * go out of bounds. + */ + MutableSpan slice(uint start, uint length) const + { + BLI_assert(start + length <= this->size()); + return MutableSpan(m_start + start, length); + } + + /** + * Returns a new MutableSpan with n elements removed from the beginning. This invokes + * undefined behavior when the array is too small. + */ + MutableSpan drop_front(uint n) const + { + BLI_assert(n <= this->size()); + return this->slice(n, this->size() - n); + } + + /** + * Returns a new MutableSpan with n elements removed from the end. This invokes undefined + * behavior when the array is too small. + */ + MutableSpan drop_back(uint n) const + { + BLI_assert(n <= this->size()); + return this->slice(0, this->size() - n); + } + + /** + * Returns a new MutableSpan that only contains the first n elements. This invokes undefined + * behavior when the array is too small. + */ + MutableSpan take_front(uint n) const + { + BLI_assert(n <= this->size()); + return this->slice(0, n); + } + + /** + * Return a new MutableSpan that only contains the last n elements. This invokes undefined + * behavior when the array is too small. + */ + MutableSpan take_back(uint n) const + { + BLI_assert(n <= this->size()); + return this->slice(this->size() - n, n); + } + + /** + * Returns an (immutable) Span that references the same array. This is usually not needed, + * due to implicit conversions. However, sometimes automatic type deduction needs some help. + */ + Span as_span() const + { + return Span(m_start, m_size); + } + + /** + * 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); + } + + /** + * Returns a reference to the last element. This invokes undefined behavior when the array is + * empty. + */ + const T &last() const + { + BLI_assert(m_size > 0); + return m_start[m_size - 1]; + } + + /** + * Returns a new span to the same underlying memory buffer. No conversions are done. + */ + template MutableSpan cast() const + { + BLI_assert((m_size * sizeof(T)) % sizeof(NewT) == 0); + uint new_size = m_size * sizeof(T) / sizeof(NewT); + return MutableSpan(reinterpret_cast(m_start), new_size); + } +}; + +/** + * Shorthand to make use of automatic template parameter deduction. + */ +template Span ref_c_array(const T *array, uint size) +{ + return Span(array, size); +} + +/** + * Utilities to check that arrays have the same size in debug builds. + */ +template 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 +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 blender */ + +#endif /* __BLI_SPAN_HH__ */ diff --git a/source/blender/blenlib/BLI_stack.hh b/source/blender/blenlib/BLI_stack.hh index 81b8b192efd..030d9c84c8e 100644 --- a/source/blender/blenlib/BLI_stack.hh +++ b/source/blender/blenlib/BLI_stack.hh @@ -41,8 +41,8 @@ */ #include "BLI_allocator.hh" -#include "BLI_array_ref.hh" #include "BLI_memory_utils.hh" +#include "BLI_span.hh" namespace blender { @@ -139,7 +139,7 @@ class Stack { * Create a new stack that contains the given elements. The values are pushed to the stack in * the order they are in the array. */ - Stack(ArrayRef values) : Stack() + Stack(Span values) : Stack() { this->push_multiple(values); } @@ -153,7 +153,7 @@ class Stack { * assert(stack.pop() == 6); * assert(stack.pop() == 5); */ - Stack(const std::initializer_list &values) : Stack(ArrayRef(values)) + Stack(const std::initializer_list &values) : Stack(Span(values)) { } @@ -162,7 +162,7 @@ class Stack { for (const Chunk *chunk = &other.m_inline_chunk; chunk; chunk = chunk->above) { const T *begin = chunk->begin; const T *end = (chunk == other.m_top_chunk) ? other.m_top : chunk->capacity_end; - this->push_multiple(ArrayRef(begin, end - begin)); + this->push_multiple(Span(begin, end - begin)); } } @@ -289,9 +289,9 @@ class Stack { * This method is more efficient than pushing multiple elements individually and might cause less * heap allocations. */ - void push_multiple(ArrayRef values) + void push_multiple(Span values) { - ArrayRef remaining_values = values; + Span remaining_values = values; while (!remaining_values.is_empty()) { if (m_top == m_top_chunk->capacity_end) { this->activate_next_chunk(remaining_values.size()); diff --git a/source/blender/blenlib/BLI_string_ref.hh b/source/blender/blenlib/BLI_string_ref.hh index 3c670c4f2b8..8ed923068a8 100644 --- a/source/blender/blenlib/BLI_string_ref.hh +++ b/source/blender/blenlib/BLI_string_ref.hh @@ -46,7 +46,7 @@ #include #include -#include "BLI_array_ref.hh" +#include "BLI_span.hh" #include "BLI_utildefines.h" namespace blender { @@ -83,9 +83,9 @@ class StringRefBase { return m_data; } - operator ArrayRef() const + operator Span() const { - return ArrayRef(m_data, m_size); + return Span(m_data, m_size); } /** diff --git a/source/blender/blenlib/BLI_vector.hh b/source/blender/blenlib/BLI_vector.hh index 8042a2a554e..b2b2da0a4b0 100644 --- a/source/blender/blenlib/BLI_vector.hh +++ b/source/blender/blenlib/BLI_vector.hh @@ -44,11 +44,11 @@ #include #include "BLI_allocator.hh" -#include "BLI_array_ref.hh" #include "BLI_index_range.hh" #include "BLI_listbase_wrapper.hh" #include "BLI_math_base.h" #include "BLI_memory_utils.hh" +#include "BLI_span.hh" #include "BLI_string.h" #include "BLI_string_ref.hh" #include "BLI_utildefines.h" @@ -152,14 +152,14 @@ class Vector { * This allows you to write code like: * Vector vec = {3, 4, 5}; */ - Vector(const std::initializer_list &values) : Vector(ArrayRef(values)) + Vector(const std::initializer_list &values) : Vector(Span(values)) { } /** * Create a vector from an array ref. The values in the vector are copy constructed. */ - Vector(ArrayRef values) : Vector() + Vector(Span values) : Vector() { uint size = values.size(); this->reserve(size); @@ -263,22 +263,22 @@ class Vector { } } - operator ArrayRef() const + operator Span() const { - return ArrayRef(m_begin, this->size()); + return Span(m_begin, this->size()); } - operator MutableArrayRef() + operator MutableSpan() { - return MutableArrayRef(m_begin, this->size()); + return MutableSpan(m_begin, this->size()); } - ArrayRef as_ref() const + Span as_span() const { return *this; } - MutableArrayRef as_mutable_ref() + MutableSpan as_mutable_span() { return *this; } @@ -478,7 +478,7 @@ class Vector { * * This can be used to emulate parts of std::vector::insert. */ - void extend(ArrayRef array) + void extend(Span array) { this->extend(array.data(), array.size()); } @@ -493,7 +493,7 @@ class Vector { * operation when the vector is large, but can be very cheap when it is known that the vector is * small. */ - void extend_non_duplicates(ArrayRef array) + void extend_non_duplicates(Span array) { for (const T &value : array) { this->append_non_duplicates(value); @@ -504,7 +504,7 @@ class Vector { * Extend the vector without bounds checking. It is assumed that enough memory has been reserved * beforehand. Only use this in performance critical code. */ - void extend_unchecked(ArrayRef array) + void extend_unchecked(Span array) { this->extend_unchecked(array.data(), array.size()); } @@ -542,9 +542,9 @@ class Vector { /** * Copy the value to all positions specified by the indices array. */ - void fill_indices(ArrayRef indices, const T &value) + void fill_indices(Span indices, const T &value) { - MutableArrayRef(*this).fill_indices(indices, value); + MutableSpan(*this).fill_indices(indices, value); } /** diff --git a/source/blender/blenlib/BLI_vector_set.hh b/source/blender/blenlib/BLI_vector_set.hh index a3155a3a9fd..d330d3c3247 100644 --- a/source/blender/blenlib/BLI_vector_set.hh +++ b/source/blender/blenlib/BLI_vector_set.hh @@ -32,7 +32,7 @@ * - The insertion order is important. * - Iteration over all keys has to be fast. * - The keys in the set are supposed to be passed to a function that does not have to know that - * the keys are stored in a set. With a VectorSet, one can get an ArrayRef containing all keys + * the keys are stored in a set. With a VectorSet, one can get a Span containing all keys * without additional copies. * * blender::VectorSet is implemented using open addressing in a slot array with a power-of-two @@ -279,7 +279,7 @@ class VectorSet { * We might be able to make this faster than sequentially adding all keys, but that is not * implemented yet. */ - void add_multiple(ArrayRef keys) + void add_multiple(Span keys) { for (const Key &key : keys) { this->add(key); @@ -411,18 +411,18 @@ class VectorSet { return m_keys[index]; } - operator ArrayRef() const + operator Span() const { - return ArrayRef(m_keys, this->size()); + return Span(m_keys, this->size()); } /** - * Get an ArrayRef referencing the keys vector. The referenced memory buffer is only valid as + * Get an Span referencing the keys vector. The referenced memory buffer is only valid as * long as the vector set is not changed. * * The keys must not be changed, because this would change their hash value. */ - ArrayRef as_ref() const + Span as_span() const { return *this; } @@ -432,7 +432,7 @@ class VectorSet { */ void print_stats(StringRef name = "") const { - HashTableStats stats(*this, this->as_ref()); + HashTableStats stats(*this, this->as_span()); stats.print(); } diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 79a65bbb98d..69df0505dfe 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -144,7 +144,6 @@ set(SRC BLI_args.h BLI_array.h BLI_array.hh - BLI_array_ref.hh BLI_array_store.h BLI_array_store_utils.h BLI_array_utils.h @@ -240,6 +239,7 @@ set(SRC BLI_smallhash.h BLI_sort.h BLI_sort_utils.h + BLI_span.hh BLI_stack.h BLI_stack.hh BLI_strict_flags.h diff --git a/source/blender/blenlib/intern/BLI_index_range.cc b/source/blender/blenlib/intern/BLI_index_range.cc index 31b969ec0b3..910e418a29b 100644 --- a/source/blender/blenlib/intern/BLI_index_range.cc +++ b/source/blender/blenlib/intern/BLI_index_range.cc @@ -18,8 +18,8 @@ #include #include "BLI_array.hh" -#include "BLI_array_ref.hh" #include "BLI_index_range.hh" +#include "BLI_span.hh" #include "BLI_vector.hh" namespace blender { @@ -29,18 +29,18 @@ static uint current_array_size = 0; static uint *current_array = nullptr; static std::mutex current_array_mutex; -ArrayRef IndexRange::as_array_ref() const +Span IndexRange::as_span() const { uint min_required_size = m_start + m_size; if (min_required_size <= current_array_size) { - return ArrayRef(current_array + m_start, m_size); + return Span(current_array + m_start, m_size); } std::lock_guard lock(current_array_mutex); if (min_required_size <= current_array_size) { - return ArrayRef(current_array + m_start, m_size); + return Span(current_array + m_start, m_size); } uint new_size = std::max(1000, power_of_2_max_u(min_required_size)); @@ -54,7 +54,7 @@ ArrayRef IndexRange::as_array_ref() const std::atomic_thread_fence(std::memory_order_seq_cst); current_array_size = new_size; - return ArrayRef(current_array + m_start, m_size); + return Span(current_array + m_start, m_size); } } // namespace blender diff --git a/source/blender/blenlib/intern/dot_export.cc b/source/blender/blenlib/intern/dot_export.cc index f08fb02ec21..a2cf843c473 100644 --- a/source/blender/blenlib/intern/dot_export.cc +++ b/source/blender/blenlib/intern/dot_export.cc @@ -250,8 +250,8 @@ std::string color_attr_from_hsv(float h, float s, float v) NodeWithSocketsRef::NodeWithSocketsRef(Node &node, StringRef name, - ArrayRef input_names, - ArrayRef output_names) + Span input_names, + Span output_names) : m_node(&node) { std::stringstream ss; diff --git a/source/blender/depsgraph/intern/depsgraph_registry.cc b/source/blender/depsgraph/intern/depsgraph_registry.cc index 3b0a0b3ea19..7eac7b45069 100644 --- a/source/blender/depsgraph/intern/depsgraph_registry.cc +++ b/source/blender/depsgraph/intern/depsgraph_registry.cc @@ -49,7 +49,7 @@ void unregister_graph(Depsgraph *depsgraph) } } -ArrayRef get_all_registered_graphs(Main *bmain) +Span get_all_registered_graphs(Main *bmain) { VectorSet *graphs = g_graph_registry.lookup_ptr(bmain); if (graphs != nullptr) { diff --git a/source/blender/depsgraph/intern/depsgraph_registry.h b/source/blender/depsgraph/intern/depsgraph_registry.h index f8e5b9543f2..967791d2fbf 100644 --- a/source/blender/depsgraph/intern/depsgraph_registry.h +++ b/source/blender/depsgraph/intern/depsgraph_registry.h @@ -33,6 +33,6 @@ struct Depsgraph; void register_graph(Depsgraph *depsgraph); void unregister_graph(Depsgraph *depsgraph); -ArrayRef get_all_registered_graphs(Main *bmain); +Span get_all_registered_graphs(Main *bmain); } // namespace DEG diff --git a/source/blender/depsgraph/intern/depsgraph_type.h b/source/blender/depsgraph/intern/depsgraph_type.h index f6901395897..43b1ecb774a 100644 --- a/source/blender/depsgraph/intern/depsgraph_type.h +++ b/source/blender/depsgraph/intern/depsgraph_type.h @@ -53,9 +53,9 @@ struct CustomData_MeshMasks; namespace DEG { /* Commonly used types. */ -using blender::ArrayRef; using blender::Map; using blender::Set; +using blender::Span; using blender::StringRef; using blender::StringRefNull; using blender::Vector; diff --git a/source/blender/modifiers/intern/MOD_mask.cc b/source/blender/modifiers/intern/MOD_mask.cc index 2fe3195583a..46b88142223 100644 --- a/source/blender/modifiers/intern/MOD_mask.cc +++ b/source/blender/modifiers/intern/MOD_mask.cc @@ -67,10 +67,10 @@ #include "BLI_vector.hh" using blender::Array; -using blender::ArrayRef; using blender::IndexRange; using blender::ListBaseWrapper; -using blender::MutableArrayRef; +using blender::MutableSpan; +using blender::Span; using blender::Vector; static void requiredDataMask(Object *UNUSED(ob), @@ -104,7 +104,7 @@ static void compute_vertex_mask__armature_mode(MDeformVert *dvert, Object *ob, Object *armature_ob, float threshold, - MutableArrayRef r_vertex_mask) + MutableSpan r_vertex_mask) { /* Element i is true if there is a selected bone that uses vertex group i. */ Vector selected_bone_uses_group; @@ -115,10 +115,10 @@ static void compute_vertex_mask__armature_mode(MDeformVert *dvert, selected_bone_uses_group.append(bone_for_group_exists); } - ArrayRef use_vertex_group = selected_bone_uses_group; + Span use_vertex_group = selected_bone_uses_group; for (int i : r_vertex_mask.index_range()) { - ArrayRef weights(dvert[i].dw, dvert[i].totweight); + Span weights(dvert[i].dw, dvert[i].totweight); r_vertex_mask[i] = false; /* check the groups that vertex is assigned to, and see if it was any use */ @@ -137,7 +137,7 @@ static void compute_vertex_mask__armature_mode(MDeformVert *dvert, static void compute_vertex_mask__vertex_group_mode(MDeformVert *dvert, int defgrp_index, float threshold, - MutableArrayRef r_vertex_mask) + MutableSpan r_vertex_mask) { for (int i : r_vertex_mask.index_range()) { const bool found = BKE_defvert_find_weight(&dvert[i], defgrp_index) > threshold; @@ -145,15 +145,15 @@ static void compute_vertex_mask__vertex_group_mode(MDeformVert *dvert, } } -static void invert_boolean_array(MutableArrayRef array) +static void invert_boolean_array(MutableSpan array) { for (bool &value : array) { value = !value; } } -static void compute_masked_vertices(ArrayRef vertex_mask, - MutableArrayRef r_vertex_map, +static void compute_masked_vertices(Span vertex_mask, + MutableSpan r_vertex_map, uint *r_num_masked_vertices) { BLI_assert(vertex_mask.size() == r_vertex_map.size()); @@ -173,8 +173,8 @@ static void compute_masked_vertices(ArrayRef vertex_mask, } static void computed_masked_edges(const Mesh *mesh, - ArrayRef vertex_mask, - MutableArrayRef r_edge_map, + Span vertex_mask, + MutableSpan r_edge_map, uint *r_num_masked_edges) { BLI_assert(mesh->totedge == r_edge_map.size()); @@ -197,7 +197,7 @@ static void computed_masked_edges(const Mesh *mesh, } static void computed_masked_polygons(const Mesh *mesh, - ArrayRef vertex_mask, + Span vertex_mask, Vector &r_masked_poly_indices, Vector &r_loop_starts, uint *r_num_masked_polys, @@ -213,7 +213,7 @@ static void computed_masked_polygons(const Mesh *mesh, const MPoly &poly_src = mesh->mpoly[i]; bool all_verts_in_mask = true; - ArrayRef loops_src(&mesh->mloop[poly_src.loopstart], poly_src.totloop); + Span loops_src(&mesh->mloop[poly_src.loopstart], poly_src.totloop); for (const MLoop &loop : loops_src) { if (!vertex_mask[loop.v]) { all_verts_in_mask = false; @@ -234,7 +234,7 @@ static void computed_masked_polygons(const Mesh *mesh, static void copy_masked_vertices_to_new_mesh(const Mesh &src_mesh, Mesh &dst_mesh, - ArrayRef vertex_map) + Span vertex_map) { BLI_assert(src_mesh.totvert == vertex_map.size()); for (const int i_src : vertex_map.index_range()) { @@ -253,8 +253,8 @@ static void copy_masked_vertices_to_new_mesh(const Mesh &src_mesh, static void copy_masked_edges_to_new_mesh(const Mesh &src_mesh, Mesh &dst_mesh, - ArrayRef vertex_map, - ArrayRef edge_map) + Span vertex_map, + Span edge_map) { BLI_assert(src_mesh.totvert == vertex_map.size()); BLI_assert(src_mesh.totedge == edge_map.size()); @@ -276,10 +276,10 @@ static void copy_masked_edges_to_new_mesh(const Mesh &src_mesh, static void copy_masked_polys_to_new_mesh(const Mesh &src_mesh, Mesh &dst_mesh, - ArrayRef vertex_map, - ArrayRef edge_map, - ArrayRef masked_poly_indices, - ArrayRef new_loop_starts) + Span vertex_map, + Span edge_map, + Span masked_poly_indices, + Span new_loop_starts) { for (const int i_dst : masked_poly_indices.index_range()) { const int i_src = masked_poly_indices[i_dst]; -- cgit v1.2.3