diff options
Diffstat (limited to 'source/blender/blenkernel/BKE_outliner_treehash.hh')
-rw-r--r-- | source/blender/blenkernel/BKE_outliner_treehash.hh | 76 |
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 |