Merge branch 'master' into xr-devxr-dev

1 files changed, 76 insertions, 0 deletions

diff --git a/source/blender/blenkernel/BKE_outliner_treehash.hh b/source/blender/blenkernel/BKE_outliner_treehash.hh
new file mode 100644
index 00000000000..7f1dad5fd68
--- /dev/null
+++ b/source/blender/blenkernel/BKE_outliner_treehash.hh
@@ -0,0 +1,76 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+#pragma once
+
+/** \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.
+ */
+
+#include <memory>
+
+#include "BLI_map.hh"
+
+struct BLI_mempool;
+struct ID;
+struct TreeStoreElem;
+
+namespace blender::bke::outliner::treehash {
+
+/* -------------------------------------------------------------------- */
+
+class TreeStoreElemKey {
+ public:
+  ID *id = nullptr;
+  short type = 0;
+  short nr = 0;
+
+  explicit TreeStoreElemKey(const TreeStoreElem &elem);
+  TreeStoreElemKey(ID *id, short type, short nr);
+
+  uint64_t hash() const;
+  friend bool operator==(const TreeStoreElemKey &a, const TreeStoreElemKey &b);
+};
+
+/* -------------------------------------------------------------------- */
+
+class TreeHash {
+  Map<TreeStoreElemKey, std::unique_ptr<class TseGroup>> elem_groups_;
+
+ public:
+  ~TreeHash();
+
+  /** Create and fill hash-table with treestore elements */
+  static std::unique_ptr<TreeHash> create_from_treestore(BLI_mempool &treestore);
+
+  /** Full rebuild for already allocated hash-table. */
+  void rebuild_from_treestore(BLI_mempool &treestore);
+
+  /** Clear element usage flags. */
+  void clear_used();
+
+  /** Add hash-table element. */
+  void add_element(TreeStoreElem &elem);
+  /** Remove hash-table element. */
+  void remove_element(TreeStoreElem &elem);
+
+  /** 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;
+
+  TseGroup *lookup_group(const TreeStoreElemKey &key) const;
+  TseGroup *lookup_group(const TreeStoreElem &elem) const;
+  TseGroup *lookup_group(short type, short nr, ID *id) const;
+  void fill_treehash(BLI_mempool &treestore);
+};
+
+}  // namespace blender::bke::outliner::treehash