[Bf-blender-cvs] [d2255aa4ed6] master: Outliner: Refactor outliner tree-hash interfaces with C++
Julian Eisel
noreply at git.blender.org
Thu Aug 18 20:23:16 CEST 2022
Commit: d2255aa4ed6d6b3fc3a42871a649682e357a305e
Author: Julian Eisel
Date: Thu Aug 18 20:15:36 2022 +0200
Branches: master
https://developer.blender.org/rBd2255aa4ed6d6b3fc3a42871a649682e357a305e
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.
===================================================================
M source/blender/blenkernel/BKE_outliner_treehash.hh
M source/blender/blenkernel/intern/outliner_treehash.cc
M source/blender/editors/space_outliner/outliner_intern.hh
M source/blender/editors/space_outliner/outliner_tree.cc
M source/blender/editors/space_outliner/outliner_utils.cc
M source/blender/editors/space_outliner/space_outliner.cc
M source/blender/makesdna/DNA_space_types.h
===================================================================
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_fr
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list