diff options
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r-- | source/blender/blenlib/BLI_array_utils.hh | 35 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_compute_context.hh | 173 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_generic_span.hh | 57 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_multi_value_map.hh | 8 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_path_util.h | 10 | ||||
-rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 14 | ||||
-rw-r--r-- | source/blender/blenlib/intern/array_utils.cc | 18 | ||||
-rw-r--r-- | source/blender/blenlib/intern/compute_context.cc | 48 | ||||
-rw-r--r-- | source/blender/blenlib/intern/cpp_type.cc | 1 | ||||
-rw-r--r-- | source/blender/blenlib/intern/path_util.c | 4 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_path_util_test.cc | 7 |
11 files changed, 370 insertions, 5 deletions
diff --git a/source/blender/blenlib/BLI_array_utils.hh b/source/blender/blenlib/BLI_array_utils.hh new file mode 100644 index 00000000000..dd65147a926 --- /dev/null +++ b/source/blender/blenlib/BLI_array_utils.hh @@ -0,0 +1,35 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#pragma once + +#include "BLI_generic_span.hh" +#include "BLI_generic_virtual_array.hh" +#include "BLI_index_mask.hh" +#include "BLI_task.hh" + +namespace blender::array_utils { + +/** + * Fill the destination span by copying masked values from the src array. Threaded based on + * grainsize. + */ +void copy(const GVArray &src, IndexMask selection, GMutableSpan dst, int64_t grain_size = 4096); + +/** + * Fill the destination span by copying values from the src array. Threaded based on + * grainsize. + */ +template<typename T> +inline void copy(const Span<T> src, + const IndexMask selection, + MutableSpan<T> dst, + const int64_t grain_size = 4096) +{ + threading::parallel_for(selection.index_range(), grain_size, [&](const IndexRange range) { + for (const int64_t index : selection.slice(range)) { + dst[index] = src[index]; + } + }); +} + +} // namespace blender::array_utils diff --git a/source/blender/blenlib/BLI_compute_context.hh b/source/blender/blenlib/BLI_compute_context.hh new file mode 100644 index 00000000000..7422467e400 --- /dev/null +++ b/source/blender/blenlib/BLI_compute_context.hh @@ -0,0 +1,173 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#pragma once + +/** \file + * \ingroup bli + * + * When logging computed values, we generally want to know where the value was computed. For + * example, geometry nodes logs socket values so that they can be displayed in the ui. For that we + * can combine the logged value with a `ComputeContext`, which identifies the place where the value + * was computed. + * + * This is not a trivial problem because e.g. just storing storing a pointer to the socket a value + * belongs to is not enough. That's because the same socket may correspond to many different values + * when the socket is used in a node group that is used multiple times. In this case, not only does + * the socket have to be stored but also the entire nested node group path that led to the + * evaluation of the socket. + * + * Storing the entire "context path" for every logged value is not feasible, because that path can + * become quite long. So that would need much more memory, more compute overhead and makes it + * complicated to compare if two contexts are the same. If the identifier for a compute context + * would have a variable size, it would also be much harder to create a map from context to values. + * + * The solution implemented below uses the following key ideas: + * - Every compute context can be hashed to a unique fixed size value (`ComputeContextHash`). While + * technically there could be hash collisions, the hashing algorithm has to be chosen to make + * that practically impossible. This way an entire context path, possibly consisting of many + * nested contexts, is represented by a single value that can be stored easily. + * - A nested compute context is build as singly linked list, where every compute context has a + * pointer to the parent compute context. Note that a link in the other direction is not possible + * because the same parent compute context may be used by many different children which possibly + * run on different threads. + */ + +#include "BLI_array.hh" +#include "BLI_linear_allocator.hh" +#include "BLI_stack.hh" +#include "BLI_string_ref.hh" + +namespace blender { + +/** + * A hash that uniquely identifies a specific (non-fixed-size) compute context. The hash has to + * have enough bits to make collisions practically impossible. + */ +struct ComputeContextHash { + static constexpr int64_t HashSizeInBytes = 16; + uint64_t v1 = 0; + uint64_t v2 = 0; + + uint64_t hash() const + { + return v1; + } + + friend bool operator==(const ComputeContextHash &a, const ComputeContextHash &b) + { + return a.v1 == b.v1 && a.v2 == b.v2; + } + + void mix_in(const void *data, int64_t len); + + friend std::ostream &operator<<(std::ostream &stream, const ComputeContextHash &hash); +}; + +static_assert(sizeof(ComputeContextHash) == ComputeContextHash::HashSizeInBytes); + +/** + * Identifies the context in which a computation happens. This context can be used to identify + * values logged during the computation. For more details, see the comment at the top of the file. + * + * This class should be subclassed to implement specific contexts. + */ +class ComputeContext { + private: + /** + * Only used for debugging currently. + */ + const char *static_type_; + /** + * Pointer to the context that this context is child of. That allows nesting compute contexts. + */ + const ComputeContext *parent_ = nullptr; + + protected: + /** + * The hash that uniquely identifies this context. It's a combined hash of this context as well + * as all the parent contexts. + */ + ComputeContextHash hash_; + + public: + ComputeContext(const char *static_type, const ComputeContext *parent) + : static_type_(static_type), parent_(parent) + { + if (parent != nullptr) { + hash_ = parent_->hash_; + } + } + virtual ~ComputeContext() = default; + + const ComputeContextHash &hash() const + { + return hash_; + } + + const char *static_type() const + { + return static_type_; + } + + const ComputeContext *parent() const + { + return parent_; + } + + /** + * Print the entire nested context stack. + */ + void print_stack(std::ostream &stream, StringRef name) const; + + /** + * Print information about this specific context. This has to be implemented by each subclass. + */ + virtual void print_current_in_line(std::ostream &stream) const = 0; + + friend std::ostream &operator<<(std::ostream &stream, const ComputeContext &compute_context); +}; + +/** + * Utility class to build a context stack in one place. This is typically used to get the hash that + * corresponds to a specific nested compute context, in order to look up corresponding logged + * values. + */ +class ComputeContextBuilder { + private: + LinearAllocator<> allocator_; + Stack<destruct_ptr<ComputeContext>> contexts_; + + public: + bool is_empty() const + { + return contexts_.is_empty(); + } + + const ComputeContext *current() const + { + if (contexts_.is_empty()) { + return nullptr; + } + return contexts_.peek().get(); + } + + const ComputeContextHash hash() const + { + BLI_assert(!contexts_.is_empty()); + return this->current()->hash(); + } + + template<typename T, typename... Args> void push(Args &&...args) + { + const ComputeContext *current = this->current(); + destruct_ptr<T> context = allocator_.construct<T>(current, std::forward<Args>(args)...); + contexts_.push(std::move(context)); + } + + void pop() + { + contexts_.pop(); + } +}; + +} // namespace blender diff --git a/source/blender/blenlib/BLI_generic_span.hh b/source/blender/blenlib/BLI_generic_span.hh index 143ab235d2e..e7a08988c46 100644 --- a/source/blender/blenlib/BLI_generic_span.hh +++ b/source/blender/blenlib/BLI_generic_span.hh @@ -100,6 +100,34 @@ class GSpan { { return this->slice(range.start(), range.size()); } + + GSpan drop_front(const int64_t n) const + { + BLI_assert(n >= 0); + const int64_t new_size = std::max<int64_t>(0, size_ - n); + return GSpan(*type_, POINTER_OFFSET(data_, type_->size() * n), new_size); + } + + GSpan drop_back(const int64_t n) const + { + BLI_assert(n >= 0); + const int64_t new_size = std::max<int64_t>(0, size_ - n); + return GSpan(*type_, data_, new_size); + } + + GSpan take_front(const int64_t n) const + { + BLI_assert(n >= 0); + const int64_t new_size = std::min<int64_t>(size_, n); + return GSpan(*type_, data_, new_size); + } + + GSpan take_back(const int64_t n) const + { + BLI_assert(n >= 0); + const int64_t new_size = std::min<int64_t>(size_, n); + return GSpan(*type_, POINTER_OFFSET(data_, type_->size() * (size_ - new_size)), new_size); + } }; /** @@ -199,6 +227,35 @@ class GMutableSpan { return this->slice(range.start(), range.size()); } + GMutableSpan drop_front(const int64_t n) const + { + BLI_assert(n >= 0); + const int64_t new_size = std::max<int64_t>(0, size_ - n); + return GMutableSpan(*type_, POINTER_OFFSET(data_, type_->size() * n), new_size); + } + + GMutableSpan drop_back(const int64_t n) const + { + BLI_assert(n >= 0); + const int64_t new_size = std::max<int64_t>(0, size_ - n); + return GMutableSpan(*type_, data_, new_size); + } + + GMutableSpan take_front(const int64_t n) const + { + BLI_assert(n >= 0); + const int64_t new_size = std::min<int64_t>(size_, n); + return GMutableSpan(*type_, data_, new_size); + } + + GMutableSpan take_back(const int64_t n) const + { + BLI_assert(n >= 0); + const int64_t new_size = std::min<int64_t>(size_, n); + return GMutableSpan( + *type_, POINTER_OFFSET(data_, type_->size() * (size_ - new_size)), new_size); + } + /** * Copy all values from another span into this span. This invokes undefined behavior when the * destination contains uninitialized data and T is not trivially copy constructible. diff --git a/source/blender/blenlib/BLI_multi_value_map.hh b/source/blender/blenlib/BLI_multi_value_map.hh index 1fc5a797574..81b536e7d3c 100644 --- a/source/blender/blenlib/BLI_multi_value_map.hh +++ b/source/blender/blenlib/BLI_multi_value_map.hh @@ -115,6 +115,14 @@ template<typename Key, typename Value> class MultiValueMap { } /** + * Get the number of keys. + */ + int64_t size() const + { + return map_.size(); + } + + /** * NOTE: This signature will change when the implementation changes. */ typename MapType::ItemIterator items() const diff --git a/source/blender/blenlib/BLI_path_util.h b/source/blender/blenlib/BLI_path_util.h index 75002f52d94..136258e50f2 100644 --- a/source/blender/blenlib/BLI_path_util.h +++ b/source/blender/blenlib/BLI_path_util.h @@ -84,10 +84,18 @@ void BLI_join_dirfile(char *__restrict dst, * Join multiple strings into a path, ensuring only a single path separator between each, * and trailing slash is kept. * + * \param path: The first patch which has special treatment, + * allowing `//` prefix which is kept intact unlike double-slashes which are stripped + * from the bounds of all other paths passed in. + * Passing in the following paths all result in the same output (`//a/b/c`): + * - `"//", "a", "b", "c"`. + * - `"//", "/a/", "/b/", "/c"`. + * - `"//a", "b/c"`. + * * \note If you want a trailing slash, add `SEP_STR` as the last path argument, * duplicate slashes will be cleaned up. */ -size_t BLI_path_join(char *__restrict dst, size_t dst_len, const char *path_first, ...) +size_t BLI_path_join(char *__restrict dst, size_t dst_len, const char *path, ...) ATTR_NONNULL(1, 3) ATTR_SENTINEL(0); /** * Like Python's `os.path.basename()` diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index d87c60e6099..470ffebcad4 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -23,7 +23,6 @@ set(INC_SYS ) set(SRC - intern/BLI_args.c intern/BLI_array.c intern/BLI_assert.c intern/BLI_color.cc @@ -48,11 +47,13 @@ set(SRC intern/array_store.c intern/array_store_utils.c intern/array_utils.c + intern/array_utils.cc intern/astar.c intern/bitmap.c intern/bitmap_draw_2d.c intern/boxpack_2d.c intern/buffer.c + intern/compute_context.cc intern/convexhull_2d.c intern/cpp_type.cc intern/delaunay_2d.cc @@ -159,12 +160,12 @@ set(SRC BLI_alloca.h BLI_allocator.hh BLI_any.hh - BLI_args.h BLI_array.h BLI_array.hh BLI_array_store.h BLI_array_store_utils.h BLI_array_utils.h + BLI_array_utils.hh BLI_asan.h BLI_assert.h BLI_astar.h @@ -180,6 +181,7 @@ set(SRC BLI_compiler_attrs.h BLI_compiler_compat.h BLI_compiler_typecheck.h + BLI_compute_context.hh BLI_console.h BLI_convexhull_2d.h BLI_cpp_type.hh @@ -353,6 +355,14 @@ set(LIB ${ZSTD_LIBRARIES} ) +if(NOT WITH_PYTHON_MODULE) + list(APPEND SRC + intern/BLI_args.c + + BLI_args.h + ) +endif() + if(WITH_MEM_VALGRIND) add_definitions(-DWITH_MEM_VALGRIND) endif() diff --git a/source/blender/blenlib/intern/array_utils.cc b/source/blender/blenlib/intern/array_utils.cc new file mode 100644 index 00000000000..d4266295944 --- /dev/null +++ b/source/blender/blenlib/intern/array_utils.cc @@ -0,0 +1,18 @@ +#include "BLI_array_utils.hh" +#include "BLI_task.hh" + +namespace blender::array_utils { + +void copy(const GVArray &src, + const IndexMask selection, + GMutableSpan dst, + const int64_t grain_size) +{ + BLI_assert(src.type() == dst.type()); + BLI_assert(src.size() == dst.size()); + threading::parallel_for(selection.index_range(), grain_size, [&](const IndexRange range) { + src.materialize_to_uninitialized(selection.slice(range), dst.data()); + }); +} + +} // namespace blender::array_utils diff --git a/source/blender/blenlib/intern/compute_context.cc b/source/blender/blenlib/intern/compute_context.cc new file mode 100644 index 00000000000..50a4a90a4a9 --- /dev/null +++ b/source/blender/blenlib/intern/compute_context.cc @@ -0,0 +1,48 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#include "BLI_compute_context.hh" +#include "BLI_hash_md5.h" + +namespace blender { + +void ComputeContextHash::mix_in(const void *data, int64_t len) +{ + DynamicStackBuffer<> buffer_owner(HashSizeInBytes + len, 8); + char *buffer = static_cast<char *>(buffer_owner.buffer()); + memcpy(buffer, this, HashSizeInBytes); + memcpy(buffer + HashSizeInBytes, data, len); + + BLI_hash_md5_buffer(buffer, HashSizeInBytes + len, this); +} + +std::ostream &operator<<(std::ostream &stream, const ComputeContextHash &hash) +{ + std::stringstream ss; + ss << "0x" << std::hex << hash.v1 << hash.v2; + stream << ss.str(); + return stream; +} + +void ComputeContext::print_stack(std::ostream &stream, StringRef name) const +{ + Stack<const ComputeContext *> stack; + for (const ComputeContext *current = this; current; current = current->parent_) { + stack.push(current); + } + stream << "Context Stack: " << name << "\n"; + while (!stack.is_empty()) { + const ComputeContext *current = stack.pop(); + stream << "-> "; + current->print_current_in_line(stream); + const ComputeContextHash ¤t_hash = current->hash_; + stream << " \t(hash: " << current_hash << ")\n"; + } +} + +std::ostream &operator<<(std::ostream &stream, const ComputeContext &compute_context) +{ + compute_context.print_stack(stream, ""); + return stream; +} + +} // namespace blender diff --git a/source/blender/blenlib/intern/cpp_type.cc b/source/blender/blenlib/intern/cpp_type.cc index d6a087cf175..38de32d3ec8 100644 --- a/source/blender/blenlib/intern/cpp_type.cc +++ b/source/blender/blenlib/intern/cpp_type.cc @@ -26,3 +26,4 @@ BLI_CPP_TYPE_MAKE(ColorGeometry4f, blender::ColorGeometry4f, CPPTypeFlags::Basic BLI_CPP_TYPE_MAKE(ColorGeometry4b, blender::ColorGeometry4b, CPPTypeFlags::BasicType) BLI_CPP_TYPE_MAKE(string, std::string, CPPTypeFlags::BasicType) +BLI_CPP_TYPE_MAKE(StringVector, blender::Vector<std::string>, CPPTypeFlags::None) diff --git a/source/blender/blenlib/intern/path_util.c b/source/blender/blenlib/intern/path_util.c index 1e95aa3b7b0..c053c3907db 100644 --- a/source/blender/blenlib/intern/path_util.c +++ b/source/blender/blenlib/intern/path_util.c @@ -1505,8 +1505,8 @@ size_t BLI_path_join(char *__restrict dst, const size_t dst_len, const char *pat return ofs; } - /* remove trailing slashes, unless there are _only_ trailing slashes - * (allow "//" as the first argument). */ + /* Remove trailing slashes, unless there are *only* trailing slashes + * (allow `//` or `//some_path` as the first argument). */ bool has_trailing_slash = false; if (ofs != 0) { size_t len = ofs; diff --git a/source/blender/blenlib/tests/BLI_path_util_test.cc b/source/blender/blenlib/tests/BLI_path_util_test.cc index 4f6f4a5c413..54afc3d975d 100644 --- a/source/blender/blenlib/tests/BLI_path_util_test.cc +++ b/source/blender/blenlib/tests/BLI_path_util_test.cc @@ -298,6 +298,13 @@ TEST(path_util, JoinComplex) JOIN("1/2/3/", 100, "1", "////////", "", "2", "3\\"); } +TEST(path_util, JoinRelativePrefix) +{ + JOIN("//a/b/c", 100, "//a", "b", "c"); + JOIN("//a/b/c", 100, "//", "//a//", "//b//", "//c"); + JOIN("//a/b/c", 100, "//", "//", "a", "//", "b", "//", "c"); +} + #undef JOIN /* BLI_path_frame */ |