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.

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

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)
-{
-  TreeStoreElem *tselem;
-  BLI_mempool_iter iter;
-  BLI_mempool_iternew(treestore, &iter);
-
-  BLI_assert(treehash);
-
-  while ((tselem = static_cast<TreeStoreElem *>(BLI_mempool_iterstep(&iter)))) {
-    BKE_outliner_treehash_add_element(treehash, tselem);
-  }
-}
-
-GHash *BKE_outliner_treehash_create_from_treestore(BLI_mempool *treestore)
-{
-  GHash *treehash = BLI_ghash_new_ex(tse_hash, tse_cmp, "treehash", BLI_mempool_len(treestore));
-  fill_treehash(treehash, treestore);
-  return treehash;
-}
-
 static void free_treehash_group(void *key)
 {
   tse_group_free(static_cast<TseGroup *>(key));
 }
 
-void BKE_outliner_treehash_clear_used(GHash *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);
+
+  return tree_hash;
+}
+
+TreeHash::~TreeHash()
+{
+  if (treehash_) {
+    BLI_ghash_free(treehash_, nullptr, free_treehash_group);
+  }
+}
+
+void TreeHash::fill_treehash(BLI_mempool &treestore)
+{
+  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 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

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 {

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;
 

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);
   }

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;

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;