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 | |
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')
7 files changed, 122 insertions, 118 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 diff --git a/source/blender/editors/space_outliner/outliner_intern.hh b/source/blender/editors/space_outliner/outliner_intern.hh index 5362782dd84..80254a5cb88 100644 --- a/source/blender/editors/space_outliner/outliner_intern.hh +++ b/source/blender/editors/space_outliner/outliner_intern.hh @@ -42,21 +42,25 @@ class AbstractTreeDisplay; class AbstractTreeElement; } // namespace blender::ed::outliner +namespace blender::bke::outliner::treehash { +class TreeHash; +} + namespace outliner = blender::ed::outliner; +namespace treehash = blender::bke::outliner::treehash; struct SpaceOutliner_Runtime { /** Object to create and manage the tree for a specific display type (View Layers, Scenes, * Blender File, etc.). */ std::unique_ptr<outliner::AbstractTreeDisplay> tree_display; - /** Pointers to tree-store elements, grouped by `(id, type, nr)` - * in hash-table for faster searching. */ - struct GHash *treehash; + /* Hash table for tree-store elements, using `(id, type, index)` as key. */ + std::unique_ptr<treehash::TreeHash> tree_hash; SpaceOutliner_Runtime() = default; /** Used for copying runtime data to a duplicated space. */ SpaceOutliner_Runtime(const SpaceOutliner_Runtime &); - ~SpaceOutliner_Runtime(); + ~SpaceOutliner_Runtime() = default; }; typedef enum TreeElementInsertType { diff --git a/source/blender/editors/space_outliner/outliner_tree.cc b/source/blender/editors/space_outliner/outliner_tree.cc index b3b2bb59e20..05df3f9cb8f 100644 --- a/source/blender/editors/space_outliner/outliner_tree.cc +++ b/source/blender/editors/space_outliner/outliner_tree.cc @@ -111,10 +111,7 @@ static void outliner_storage_cleanup(SpaceOutliner *space_outliner) if (BLI_mempool_len(ts) == unused) { BLI_mempool_destroy(ts); space_outliner->treestore = nullptr; - if (space_outliner->runtime->treehash) { - BKE_outliner_treehash_free(space_outliner->runtime->treehash); - space_outliner->runtime->treehash = nullptr; - } + space_outliner->runtime->tree_hash = nullptr; } else { TreeStoreElem *tsenew; @@ -129,16 +126,15 @@ static void outliner_storage_cleanup(SpaceOutliner *space_outliner) } BLI_mempool_destroy(ts); space_outliner->treestore = new_ts; - if (space_outliner->runtime->treehash) { + if (space_outliner->runtime->tree_hash) { /* update hash table to fix broken pointers */ - BKE_outliner_treehash_rebuild_from_treestore(space_outliner->runtime->treehash, - space_outliner->treestore); + space_outliner->runtime->tree_hash->rebuild_from_treestore(*space_outliner->treestore); } } } } - else if (space_outliner->runtime->treehash) { - BKE_outliner_treehash_clear_used(space_outliner->runtime->treehash); + else if (space_outliner->runtime->tree_hash) { + space_outliner->runtime->tree_hash->clear_used(); } } } @@ -151,15 +147,14 @@ static void check_persistent( space_outliner->treestore = BLI_mempool_create( sizeof(TreeStoreElem), 1, 512, BLI_MEMPOOL_ALLOW_ITER); } - if (space_outliner->runtime->treehash == nullptr) { - space_outliner->runtime->treehash = static_cast<GHash *>( - BKE_outliner_treehash_create_from_treestore(space_outliner->treestore)); + if (space_outliner->runtime->tree_hash == nullptr) { + space_outliner->runtime->tree_hash = treehash::TreeHash::create_from_treestore( + *space_outliner->treestore); } /* find any unused tree element in treestore and mark it as used * (note that there may be multiple unused elements in case of linked objects) */ - TreeStoreElem *tselem = BKE_outliner_treehash_lookup_unused( - space_outliner->runtime->treehash, type, nr, id); + TreeStoreElem *tselem = space_outliner->runtime->tree_hash->lookup_unused(type, nr, id); if (tselem) { te->store_elem = tselem; tselem->used = 1; @@ -174,7 +169,7 @@ static void check_persistent( tselem->used = 0; tselem->flag = TSE_CLOSED; te->store_elem = tselem; - BKE_outliner_treehash_add_element(space_outliner->runtime->treehash, tselem); + space_outliner->runtime->tree_hash->add_element(*tselem); } /** \} */ @@ -1685,10 +1680,9 @@ void outliner_build_tree(Main *mainvar, space_outliner->search_flags &= ~SO_SEARCH_RECURSIVE; } - if (space_outliner->runtime->treehash && (space_outliner->storeflag & SO_TREESTORE_REBUILD) && + if (space_outliner->runtime->tree_hash && (space_outliner->storeflag & SO_TREESTORE_REBUILD) && space_outliner->treestore) { - BKE_outliner_treehash_rebuild_from_treestore(space_outliner->runtime->treehash, - space_outliner->treestore); + space_outliner->runtime->tree_hash->rebuild_from_treestore(*space_outliner->treestore); } space_outliner->storeflag &= ~SO_TREESTORE_REBUILD; diff --git a/source/blender/editors/space_outliner/outliner_utils.cc b/source/blender/editors/space_outliner/outliner_utils.cc index 9c1425befdd..2ce017f4f64 100644 --- a/source/blender/editors/space_outliner/outliner_utils.cc +++ b/source/blender/editors/space_outliner/outliner_utils.cc @@ -184,8 +184,7 @@ TreeElement *outliner_find_tse(SpaceOutliner *space_outliner, const TreeStoreEle } /* Check if 'tse' is in tree-store. */ - tselem = BKE_outliner_treehash_lookup_any( - space_outliner->runtime->treehash, tse->type, tse->nr, tse->id); + tselem = space_outliner->runtime->tree_hash->lookup_any(tse->type, tse->nr, tse->id); if (tselem) { return outliner_find_tree_element(&space_outliner->tree, tselem); } diff --git a/source/blender/editors/space_outliner/space_outliner.cc b/source/blender/editors/space_outliner/space_outliner.cc index 2435e804ed5..66ee0f4f3af 100644 --- a/source/blender/editors/space_outliner/space_outliner.cc +++ b/source/blender/editors/space_outliner/space_outliner.cc @@ -38,17 +38,10 @@ #include "tree/tree_display.hh" SpaceOutliner_Runtime::SpaceOutliner_Runtime(const SpaceOutliner_Runtime & /*other*/) - : tree_display(nullptr), treehash(nullptr) + : tree_display(nullptr), tree_hash(nullptr) { } -SpaceOutliner_Runtime::~SpaceOutliner_Runtime() -{ - if (treehash) { - BKE_outliner_treehash_free(treehash); - } -} - static void outliner_main_region_init(wmWindowManager *wm, ARegion *region) { ListBase *lb; @@ -418,7 +411,7 @@ static void outliner_id_remap(ScrArea *area, SpaceLink *slink, const struct IDRe /* Note that the Outliner may not be the active editor of the area, and hence not initialized. * So runtime data might not have been created yet. */ - if (space_outliner->runtime && space_outliner->runtime->treehash && changed) { + if (space_outliner->runtime && space_outliner->runtime->tree_hash && changed) { /* rebuild hash table, because it depends on ids too */ /* postpone a full rebuild because this can be called many times on-free */ space_outliner->storeflag |= SO_TREESTORE_REBUILD; diff --git a/source/blender/makesdna/DNA_space_types.h b/source/blender/makesdna/DNA_space_types.h index 09446536657..75f2f6702e5 100644 --- a/source/blender/makesdna/DNA_space_types.h +++ b/source/blender/makesdna/DNA_space_types.h @@ -405,8 +405,8 @@ typedef enum eSpaceOutliner_StoreFlag { /* cleanup tree */ SO_TREESTORE_CLEANUP = (1 << 0), SO_TREESTORE_UNUSED_1 = (1 << 1), /* cleared */ - /* rebuild the tree, similar to cleanup, - * but defer a call to BKE_outliner_treehash_rebuild_from_treestore instead */ + /** Rebuild the tree, similar to cleanup, but defer a call to + * bke::outliner::treehash::rebuild_from_treestore instead. */ SO_TREESTORE_REBUILD = (1 << 2), } eSpaceOutliner_StoreFlag; |