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.

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