[Bf-blender-cvs] [0a907657d4d] master: Functions: Run-time type system and index mask
Jacques Lucke
noreply at git.blender.org
Mon Jun 8 17:38:22 CEST 2020
Commit: 0a907657d4d525d320e0c8518f583b7210736214
Author: Jacques Lucke
Date: Mon Jun 8 17:37:43 2020 +0200
Branches: master
https://developer.blender.org/rB0a907657d4d525d320e0c8518f583b7210736214
Functions: Run-time type system and index mask
This adds a new `CPPType` that encapsulates information about how to handle
instances of a specific data type. This is necessary for the function evaluation
system, which will be used to evaluate most of the particle node trees.
Furthermore, this adds an `IndexMask` class which offers a surprisingly useful
abstraction over an array containing unsigned integers. It makes two assumptions
about the underlying integer array:
* The integers are in ascending order.
* There are no duplicates.
`IndexMask` will be used to "select" certain particles that will be
processed in a data-oriented way. Sometimes, operations don't have to
be applied to all particles, but only some, those that are in the indexed by
the `IndexMask`. The two limitations imposed by an `IndexMask` allow for
better performance.
Reviewers: brecht
Differential Revision: https://developer.blender.org/D7957
===================================================================
M source/blender/CMakeLists.txt
A source/blender/blenlib/BLI_index_mask.hh
M source/blender/blenlib/CMakeLists.txt
A source/blender/functions/CMakeLists.txt
A source/blender/functions/FN_cpp_type.hh
A source/blender/functions/FN_cpp_types.hh
A source/blender/functions/intern/cpp_types.cc
M tests/gtests/CMakeLists.txt
A tests/gtests/blenlib/BLI_index_mask_test.cc
M tests/gtests/blenlib/CMakeLists.txt
A tests/gtests/functions/CMakeLists.txt
A tests/gtests/functions/FN_cpp_type_test.cc
===================================================================
diff --git a/source/blender/CMakeLists.txt b/source/blender/CMakeLists.txt
index 203b6da272f..fc1cd28312e 100644
--- a/source/blender/CMakeLists.txt
+++ b/source/blender/CMakeLists.txt
@@ -114,6 +114,7 @@ add_subdirectory(modifiers)
add_subdirectory(gpencil_modifiers)
add_subdirectory(shader_fx)
add_subdirectory(io)
+add_subdirectory(functions)
add_subdirectory(makesdna)
add_subdirectory(makesrna)
diff --git a/source/blender/blenlib/BLI_index_mask.hh b/source/blender/blenlib/BLI_index_mask.hh
new file mode 100644
index 00000000000..96ab8906bd4
--- /dev/null
+++ b/source/blender/blenlib/BLI_index_mask.hh
@@ -0,0 +1,212 @@
+/*
+ * 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_INDEX_MASK_HH__
+#define __BLI_INDEX_MASK_HH__
+
+/** \file
+ * \ingroup bli
+ *
+ * An IndexMask references an array of unsigned integers with the following property:
+ * The integers must be in ascending order and there must not be duplicates.
+ *
+ * Remember that the array is only referenced and not owned by an IndexMask instance.
+ *
+ * In most cases the integers in the array represent some indices into another array. So they
+ * "select" or "mask" a some elements in that array. Hence the name IndexMask.
+ *
+ * The invariant stated above has the nice property that it makes it easy to check if an integer
+ * array is an IndexRange, i.e. no indices are skipped. That allows functions to implement two code
+ * paths: One where it iterates over the index array and one where it iterates over the index
+ * range. The latter one is more efficient due to less memory reads and potential usage of SIMD
+ * instructions.
+ *
+ * The IndexMask.foreach_index method helps writing code that implements both code paths at the
+ * same time.
+ */
+
+#include "BLI_array_ref.hh"
+#include "BLI_index_range.hh"
+
+namespace BLI {
+
+class IndexMask {
+ private:
+ /* The underlying reference to sorted integers. */
+ ArrayRef<uint> m_indices;
+
+ public:
+ /* Creates an IndexMask that contains no indices. */
+ IndexMask() = default;
+
+ /**
+ * Create an IndexMask using the given integer array.
+ * This constructor asserts that the given integers are in ascending order and that there are no
+ * duplicates.
+ */
+ IndexMask(ArrayRef<uint> indices) : m_indices(indices)
+ {
+#ifdef DEBUG
+ for (uint i = 1; i < indices.size(); i++) {
+ BLI_assert(indices[i - 1] < indices[i]);
+ }
+#endif
+ }
+
+ /**
+ * 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())
+ {
+ }
+
+ /**
+ * Construct an IndexMask from a sorted list of indices. Note, the created IndexMask is only
+ * valid as long as the initializer_list is valid.
+ *
+ * Don't do this:
+ * IndexMask mask = {3, 4, 5};
+ *
+ * Do this:
+ * do_something_with_an_index_mask({3, 4, 5});
+ */
+ IndexMask(const std::initializer_list<uint> &indices) : IndexMask(ArrayRef<uint>(indices))
+ {
+ }
+
+ /**
+ * Creates an IndexMask that references the indices [0, n-1].
+ */
+ explicit IndexMask(uint n) : IndexMask(IndexRange(n))
+ {
+ }
+
+ operator ArrayRef<uint>() const
+ {
+ return m_indices;
+ }
+
+ const uint *begin() const
+ {
+ return m_indices.begin();
+ }
+
+ const uint *end() const
+ {
+ return m_indices.end();
+ }
+
+ /**
+ * Returns the n-th index referenced by this IndexMask. The `index_mask` method returns an
+ * IndexRange containing all indices that can be used as parameter here.
+ */
+ uint operator[](uint n) const
+ {
+ return m_indices[n];
+ }
+
+ /**
+ * Returns the minimum size an array has to have, if the integers in this IndexMask are going to
+ * be used as indices in that array.
+ */
+ uint min_array_size() const
+ {
+ if (m_indices.size() == 0) {
+ return 0;
+ }
+ else {
+ return m_indices.last() + 1;
+ }
+ }
+
+ ArrayRef<uint> indices() const
+ {
+ return m_indices;
+ }
+
+ /**
+ * Returns true if this IndexMask does not skip any indices. This check requires O(1) time.
+ */
+ bool is_range() const
+ {
+ return m_indices.size() > 0 && m_indices.last() - m_indices.first() == m_indices.size() - 1;
+ }
+
+ /**
+ * Returns the IndexRange referenced by this IndexMask. This method should only be called after
+ * the caller made sure that this IndexMask is actually a range.
+ */
+ IndexRange as_range() const
+ {
+ BLI_assert(this->is_range());
+ return IndexRange{m_indices.first(), m_indices.size()};
+ }
+
+ /**
+ * Calls the given callback for every referenced index. The callback has to take one unsigned
+ * integer as parameter.
+ *
+ * This method implements different code paths for the cases when the IndexMask represents a
+ * range or not.
+ */
+ template<typename CallbackT> void foreach_index(const CallbackT &callback) const
+ {
+ if (this->is_range()) {
+ IndexRange range = this->as_range();
+ for (uint i : range) {
+ callback(i);
+ }
+ }
+ else {
+ for (uint i : m_indices) {
+ callback(i);
+ }
+ }
+ }
+
+ /**
+ * Returns an IndexRange that can be used to index this IndexMask.
+ *
+ * The range is [0, number of indices - 1].
+ *
+ * This is not to be confused with the `as_range` method.
+ */
+ IndexRange index_range() const
+ {
+ return m_indices.index_range();
+ }
+
+ /**
+ * Returns the largest index that is referenced by this IndexMask.
+ */
+ uint last() const
+ {
+ return m_indices.last();
+ }
+
+ /**
+ * Returns the number of indices referenced by this IndexMask.
+ */
+ uint size() const
+ {
+ return m_indices.size();
+ }
+};
+
+} // namespace BLI
+
+#endif /* __BLI_INDEX_MASK_HH__ */
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 7757b838afe..73b35a17ec2 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -189,6 +189,7 @@ set(SRC
BLI_hash_mm3.h
BLI_heap.h
BLI_heap_simple.h
+ BLI_index_mask.hh
BLI_index_range.hh
BLI_iterator.h
BLI_jitter_2d.h
diff --git a/source/blender/functions/CMakeLists.txt b/source/blender/functions/CMakeLists.txt
new file mode 100644
index 00000000000..9ce1d3ac2fe
--- /dev/null
+++ b/source/blender/functions/CMakeLists.txt
@@ -0,0 +1,40 @@
+# ***** BEGIN GPL LICENSE BLOCK *****
+#
+# 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.
+#
+# ***** END GPL LICENSE BLOCK *****
+
+set(INC
+ .
+ ../blenlib
+ ../makesdna
+ ../../../intern/guardedalloc
+)
+
+set(INC_SYS
+)
+
+set(SRC
+ intern/cpp_types.cc
+
+ FN_cpp_type.hh
+ FN_cpp_types.hh
+)
+
+set(LIB
+ bf_blenlib
+)
+
+blender_add_lib(bf_functions "${SRC}" "${INC}" "${INC_SYS}" "${LIB}")
diff --git a/source/blender/functions/FN_cpp_type.hh b/source/blender/functions/FN_cpp_type.hh
new file mode 100644
index 00000000000..10e95c0341e
--- /dev/null
+++ b/source/blender/functions/FN_cpp_type.hh
@@ -0,0 +1,726 @@
+/*
+ * 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 __FN_CPP_TYPE_HH__
+#define __FN_CPP_TYPE_HH__
+
+/** \file
+ * \ingroup functions
+ *
+ * The CPPType class is the core of the runtime-type-system used by the functions system. An
+ * instance of this class can represent any C++ type, that is default-constructable, destructable,
+ * movable and copyable. Therefore it also works for all C types. This restrictions might need to
+ * be removed in the future, but for now every required type has these properties.
+ *
+ * Every type has a size and an alignment. Every function dealing with C++ types in a generic way,
+ * has to make sure that alignment rules are followed. The methods provided by a CPPType instance
+ * will check for correct alignment as well.
+ *
+ * Every type has a name that is for debugging purposes only. It should not be used as identifier.
+ *
+ * To check if two instances of CPPType represent the same type, only their pointers have to be
+ * compared. Any C++ type has at most one corresponding CPPType instance.
+ *
+ * A CPPType instance comes with many methods that all
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list