diff options
author | Julian Eisel <julian@blender.org> | 2022-08-18 21:15:36 +0300 |
---|---|---|
committer | Julian Eisel <julian@blender.org> | 2022-08-18 21:22:55 +0300 |
commit | d2255aa4ed6d6b3fc3a42871a649682e357a305e (patch) | |
tree | b9f26ef1bf0548fb29b91431e9423f55db37a7fd /source/blender/blenkernel | |
parent | 75cca8360f611f6b79b65228d18fd6597267417f (diff) |
Outliner: Refactor outliner tree-hash interfaces with C++
- Turn storage into an object with "automatic" memory management (RAII)
so freeing is implicit and reliable.
- Turn functions into member functions, to have the data and its
functions close together with controlled access that increases
encapsulation and hiding implementation details.
- Use references to indicate null is not an expected value.
- Related minor cleanup (comments, use const etc.)
Couldn't spot any changes in performance.
Diffstat (limited to 'source/blender/blenkernel')
-rw-r--r-- | source/blender/blenkernel/BKE_outliner_treehash.hh | 61 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/outliner_treehash.cc | 119 |
2 files changed, 97 insertions, 83 deletions
diff --git a/source/blender/blenkernel/BKE_outliner_treehash.hh b/source/blender/blenkernel/BKE_outliner_treehash.hh index fc0ab35cf38..f72cec21dbc 100644 --- a/source/blender/blenkernel/BKE_outliner_treehash.hh +++ b/source/blender/blenkernel/BKE_outliner_treehash.hh @@ -3,45 +3,52 @@ /** \file * \ingroup bke + * + * Hash table of tree-store elements (#TreeStoreElem) for fast lookups via a (id, type, index) + * tuple as key. + * + * The Outliner may have to perform many lookups for rebuilding complex trees, so this should be + * treated as performance sensitive. */ -#ifdef __cplusplus -extern "C" { -#endif +#include <memory> struct BLI_mempool; struct ID; struct GHash; struct TreeStoreElem; -/* create and fill hashtable with treestore elements */ -GHash *BKE_outliner_treehash_create_from_treestore(BLI_mempool *treestore); +namespace blender::bke::outliner::treehash { -/* full rebuild for already allocated hashtable */ -GHash *BKE_outliner_treehash_rebuild_from_treestore(GHash *treehash, BLI_mempool *treestore); +class TreeHash { + GHash *treehash_ = nullptr; -/* clear element usage flags */ -void BKE_outliner_treehash_clear_used(GHash *treehash); + public: + ~TreeHash(); -/* Add/remove hashtable elements */ -void BKE_outliner_treehash_add_element(GHash *treehash, TreeStoreElem *elem); -void BKE_outliner_treehash_remove_element(GHash *treehash, TreeStoreElem *elem); + /* create and fill hashtable with treestore elements */ + static std::unique_ptr<TreeHash> create_from_treestore(BLI_mempool &treestore); -/* find first unused element with specific type, nr and id */ -struct TreeStoreElem *BKE_outliner_treehash_lookup_unused(GHash *treehash, - short type, - short nr, - ID *id); + /* full rebuild for already allocated hashtable */ + void rebuild_from_treestore(BLI_mempool &treestore); -/* find user or unused element with specific type, nr and id */ -struct TreeStoreElem *BKE_outliner_treehash_lookup_any(GHash *treehash, - short type, - short nr, - ID *id); + /* clear element usage flags */ + void clear_used(); -/* free treehash structure */ -void BKE_outliner_treehash_free(GHash *treehash); + /* Add/remove hashtable elements */ + void add_element(TreeStoreElem &elem); + void remove_element(TreeStoreElem &elem); -#ifdef __cplusplus -} -#endif + /* find first unused element with specific type, nr and id */ + TreeStoreElem *lookup_unused(short type, short nr, ID *id) const; + + /* find user or unused element with specific type, nr and id */ + TreeStoreElem *lookup_any(short type, short nr, ID *id) const; + + private: + TreeHash() = default; + + void fill_treehash(BLI_mempool &treestore); +}; + +} // namespace blender::bke::outliner::treehash diff --git a/source/blender/blenkernel/intern/outliner_treehash.cc b/source/blender/blenkernel/intern/outliner_treehash.cc index b43fbd7a4ac..5d13894c265 100644 --- a/source/blender/blenkernel/intern/outliner_treehash.cc +++ b/source/blender/blenkernel/intern/outliner_treehash.cc @@ -20,13 +20,20 @@ #include "MEM_guardedalloc.h" -struct TseGroup { +namespace blender::bke::outliner::treehash { + +class TseGroup { + public: blender::Vector<TreeStoreElem *> elems; /* Index of last used #TreeStoreElem item, to speed up search for another one. */ - int lastused; + int lastused = 0; /* Counter used to reduce the amount of 'rests' of `lastused` index, otherwise search for unused * item is exponential and becomes critically slow when there are a lot of items in the group. */ - int lastused_reset_count; + int lastused_reset_count = -1; + + public: + void add_element(TreeStoreElem &elem); + void remove_element(TreeStoreElem &elem); }; /* Only allow reset of #TseGroup.lastused counter to 0 once every 1k search. */ @@ -42,16 +49,16 @@ static TseGroup *tse_group_create(void) return tse_group; } -static void tse_group_add_element(TseGroup *tse_group, TreeStoreElem *elem) +void TseGroup::add_element(TreeStoreElem &elem) { - const int64_t idx = tse_group->elems.append_and_get_index(elem); - tse_group->lastused = idx; + const int64_t idx = elems.append_and_get_index(&elem); + lastused = idx; } -static void tse_group_remove_element(TseGroup &group, TreeStoreElem &elem) +void TseGroup::remove_element(TreeStoreElem &elem) { - const int64_t idx = group.elems.first_index_of(&elem); - group.elems.remove(idx); + const int64_t idx = elems.first_index_of(&elem); + elems.remove(idx); } static void tse_group_free(TseGroup *tse_group) @@ -84,78 +91,87 @@ static bool tse_cmp(const void *a, const void *b) return tse_a->type != tse_b->type || tse_a->nr != tse_b->nr || tse_a->id != tse_b->id; } -static void fill_treehash(GHash *treehash, BLI_mempool *treestore) +static void free_treehash_group(void *key) { - TreeStoreElem *tselem; - BLI_mempool_iter iter; - BLI_mempool_iternew(treestore, &iter); + tse_group_free(static_cast<TseGroup *>(key)); +} - BLI_assert(treehash); +std::unique_ptr<TreeHash> TreeHash::create_from_treestore(BLI_mempool &treestore) +{ + /* Can't use `make_unique()` here because of private constructor. */ + std::unique_ptr<TreeHash> tree_hash{new TreeHash()}; + tree_hash->treehash_ = BLI_ghash_new_ex( + tse_hash, tse_cmp, "treehash", BLI_mempool_len(&treestore)); + tree_hash->fill_treehash(treestore); - while ((tselem = static_cast<TreeStoreElem *>(BLI_mempool_iterstep(&iter)))) { - BKE_outliner_treehash_add_element(treehash, tselem); - } + return tree_hash; } -GHash *BKE_outliner_treehash_create_from_treestore(BLI_mempool *treestore) +TreeHash::~TreeHash() { - GHash *treehash = BLI_ghash_new_ex(tse_hash, tse_cmp, "treehash", BLI_mempool_len(treestore)); - fill_treehash(treehash, treestore); - return treehash; + if (treehash_) { + BLI_ghash_free(treehash_, nullptr, free_treehash_group); + } } -static void free_treehash_group(void *key) +void TreeHash::fill_treehash(BLI_mempool &treestore) { - tse_group_free(static_cast<TseGroup *>(key)); + BLI_assert(treehash_); + + TreeStoreElem *tselem; + BLI_mempool_iter iter; + BLI_mempool_iternew(&treestore, &iter); + + while ((tselem = static_cast<TreeStoreElem *>(BLI_mempool_iterstep(&iter)))) { + add_element(*tselem); + } } -void BKE_outliner_treehash_clear_used(GHash *treehash) +void TreeHash::clear_used() { GHashIterator gh_iter; - GHASH_ITER (gh_iter, treehash) { + GHASH_ITER (gh_iter, treehash_) { TseGroup *group = static_cast<TseGroup *>(BLI_ghashIterator_getValue(&gh_iter)); group->lastused = 0; group->lastused_reset_count = 0; } } -GHash *BKE_outliner_treehash_rebuild_from_treestore(GHash *treehash, BLI_mempool *treestore) +void TreeHash::rebuild_from_treestore(BLI_mempool &treestore) { - BLI_assert(treehash); + BLI_assert(treehash_); - BLI_ghash_clear_ex(treehash, nullptr, free_treehash_group, BLI_mempool_len(treestore)); - fill_treehash(treehash, treestore); - return treehash; + BLI_ghash_clear_ex(treehash_, nullptr, free_treehash_group, BLI_mempool_len(&treestore)); + fill_treehash(treestore); } -void BKE_outliner_treehash_add_element(GHash *treehash, TreeStoreElem *elem) +void TreeHash::add_element(TreeStoreElem &elem) { - TseGroup *group; void **val_p; - if (!BLI_ghash_ensure_p(treehash, elem, &val_p)) { + if (!BLI_ghash_ensure_p(treehash_, &elem, &val_p)) { *val_p = tse_group_create(); } - group = static_cast<TseGroup *>(*val_p); - tse_group_add_element(group, elem); + TseGroup &group = *static_cast<TseGroup *>(*val_p); + group.add_element(elem); } -void BKE_outliner_treehash_remove_element(GHash *treehash, TreeStoreElem *elem) +void TreeHash::remove_element(TreeStoreElem &elem) { - TseGroup *group = static_cast<TseGroup *>(BLI_ghash_lookup(treehash, elem)); + TseGroup *group = static_cast<TseGroup *>(BLI_ghash_lookup(treehash_, &elem)); BLI_assert(group != nullptr); if (group->elems.size() <= 1) { /* one element -> remove group completely */ - BLI_ghash_remove(treehash, elem, nullptr, free_treehash_group); + BLI_ghash_remove(treehash_, &elem, nullptr, free_treehash_group); } else { - tse_group_remove_element(*group, *elem); + group->remove_element(elem); } } -static TseGroup *BKE_outliner_treehash_lookup_group(GHash *th, short type, short nr, struct ID *id) +static TseGroup *lookup_group(GHash *th, const short type, const short nr, ID *id) { TreeStoreElem tse_template; tse_template.type = type; @@ -167,16 +183,13 @@ static TseGroup *BKE_outliner_treehash_lookup_group(GHash *th, short type, short return static_cast<TseGroup *>(BLI_ghash_lookup(th, &tse_template)); } -TreeStoreElem *BKE_outliner_treehash_lookup_unused(GHash *treehash, - short type, - short nr, - struct ID *id) +TreeStoreElem *TreeHash::lookup_unused(const short type, const short nr, ID *id) const { TseGroup *group; - BLI_assert(treehash); + BLI_assert(treehash_); - group = BKE_outliner_treehash_lookup_group(treehash, type, nr, id); + group = lookup_group(treehash_, type, nr, id); if (!group) { return nullptr; } @@ -206,19 +219,13 @@ TreeStoreElem *BKE_outliner_treehash_lookup_unused(GHash *treehash, return nullptr; } -TreeStoreElem *BKE_outliner_treehash_lookup_any(GHash *treehash, short type, short nr, ID *id) +TreeStoreElem *TreeHash::lookup_any(const short type, const short nr, ID *id) const { TseGroup *group; - BLI_assert(treehash); + BLI_assert(treehash_); - group = BKE_outliner_treehash_lookup_group(treehash, type, nr, id); + group = lookup_group(treehash_, type, nr, id); return group ? group->elems[0] : nullptr; } - -void BKE_outliner_treehash_free(GHash *treehash) -{ - BLI_assert(treehash); - - BLI_ghash_free(treehash, nullptr, free_treehash_group); -} +} // namespace blender::bke::outliner::treehash |