diff options
author | Jacques Lucke <jacques@blender.org> | 2022-09-17 15:12:25 +0300 |
---|---|---|
committer | Jacques Lucke <jacques@blender.org> | 2022-09-17 15:12:25 +0300 |
commit | 06d85ad64ba30d734fee0cb0a9db8f9492b41c52 (patch) | |
tree | d2555ba7643fac1f87ed414137e9c732ca8aaafa /source/blender/blenlib | |
parent | 453b664b077cae2e38ef0ef221d8888c106ef902 (diff) | |
parent | 7549e0c5ae36be739f0e0a38e87eb85428808e89 (diff) |
Merge branch 'master' into temp-chunk-list
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 | 22 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_utildefines.h | 2 | ||||
-rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 14 | ||||
-rw-r--r-- | source/blender/blenlib/intern/array_utils.cc | 20 | ||||
-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 | 8 | ||||
-rw-r--r-- | source/blender/blenlib/intern/system.c | 4 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_path_util_test.cc | 7 |
13 files changed, 383 insertions, 16 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..cf2f948b0b4 --- /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 + * grain-size. + */ +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 + * grain-size. + */ +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..e3e5b6f9e85 --- /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 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..1e45e76afe1 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()` @@ -98,10 +106,10 @@ size_t BLI_path_join(char *__restrict dst, size_t dst_len, const char *path_firs const char *BLI_path_basename(const char *path) ATTR_NONNULL() ATTR_WARN_UNUSED_RESULT; /** * Get an element of the path at an index, eg: - * "/some/path/file.txt" where an index of: - * - 0 or -3: "some" - * - 1 or -2: "path" - * - 2 or -1: "file.txt" + * `/some/path/file.txt` where an index of: + * - 0 or -3: `some` + * - 1 or -2: `path` + * - 2 or -1: `file.txt` * * Ignores multiple slashes at any point in the path (including start/end). */ @@ -357,8 +365,8 @@ void BLI_path_normalize_unc(char *path_16, int maxlen); /** * Appends a suffix to the string, fitting it before the extension * - * string = Foo.png, suffix = 123, separator = _ - * Foo.png -> Foo_123.png + * string = `Foo.png`, suffix = `123`, separator = `_`. + * `Foo.png` -> `Foo_123.png`. * * \param string: original (and final) string * \param maxlen: Maximum length of string diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h index 7f9470a9111..9f68795a4a2 100644 --- a/source/blender/blenlib/BLI_utildefines.h +++ b/source/blender/blenlib/BLI_utildefines.h @@ -589,7 +589,7 @@ extern "C" { /** Performs `offsetof(typeof(data), member) + sizeof((data)->member)` for non-gcc compilers. */ #define OFFSETOF_STRUCT_AFTER(_struct, _member) \ - ((((const char *)&((_struct)->_member)) - ((const char *)(_struct))) + \ + ((size_t)(((const char *)&((_struct)->_member)) - ((const char *)(_struct))) + \ sizeof((_struct)->_member)) /** diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 9e5ad4d9efe..a82a86183d0 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 @@ -354,6 +356,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..a0fc8810199 --- /dev/null +++ b/source/blender/blenlib/intern/array_utils.cc @@ -0,0 +1,20 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#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..9b91636b055 100644 --- a/source/blender/blenlib/intern/path_util.c +++ b/source/blender/blenlib/intern/path_util.c @@ -466,8 +466,8 @@ void BLI_path_rel(char *file, const char *relfile) #ifdef WIN32 if (BLI_strnlen(relfile, 3) > 2 && !BLI_path_is_abs(relfile)) { char *ptemp; - /* fix missing volume name in relative base, - * can happen with old recent-files.txt files */ + /* Fix missing volume name in relative base, + * can happen with old `recent-files.txt` files. */ BLI_windows_get_default_root_dir(temp); ptemp = &temp[2]; if (!ELEM(relfile[0], '\\', '/')) { @@ -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/intern/system.c b/source/blender/blenlib/intern/system.c index 781b38f713a..f7249e491d7 100644 --- a/source/blender/blenlib/intern/system.c +++ b/source/blender/blenlib/intern/system.c @@ -154,12 +154,12 @@ void BLI_hostname_get(char *buffer, size_t bufsize) if (gethostname(buffer, bufsize - 1) < 0) { BLI_strncpy(buffer, "-unknown-", bufsize); } - /* When gethostname() truncates, it doesn't guarantee the trailing \0. */ + /* When `gethostname()` truncates, it doesn't guarantee the trailing `\0`. */ buffer[bufsize - 1] = '\0'; #else DWORD bufsize_inout = bufsize; if (!GetComputerName(buffer, &bufsize_inout)) { - strncpy(buffer, "-unknown-", bufsize); + BLI_strncpy(buffer, "-unknown-", bufsize); } #endif } 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 */ |