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.
This commit is contained in:
parent
75cca8360f
commit
d2255aa4ed
|
@ -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
|
||||
|
|
|
@ -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
|
||||
|
|
|
@ -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 {
|
||||
|
|
|
@ -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;
|
||||
|
||||
|
|
|
@ -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);
|
||||
}
|
||||
|
|
|
@ -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;
|
||||
|
|
|
@ -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;
|
||||
|
||||
|
|
Loading…
Reference in New Issue