diff options
author | Julian Eisel <julian@blender.org> | 2020-11-07 02:15:09 +0300 |
---|---|---|
committer | Julian Eisel <julian@blender.org> | 2020-11-11 21:08:13 +0300 |
commit | 6b18e13c5b2fecd6485eaf44a58de5375f175ce9 (patch) | |
tree | 47903fbb52eec8eab03bdd23f57581b6c829325f /source/blender/editors/space_outliner | |
parent | c9cc03b688230d0b898467135e75e2cbac8a3226 (diff) |
UI Code Quality: Use C++ data-structures for Outliner object hierarchy building
See https://developer.blender.org/D9499.
* Use `blender::Map` over `GHash`
* Use `blender::Vector` over allocated `ListBase *`
Benefits:
* Significantly reduces the amount of heap allocations in large trees (e.g.
from O(n) to O(log(n)), where n is number of objects).
* Higher type safety (no `void *`, virtually no casts).
* More optimized (e.g. small buffer optimization).
* More practicable, const-correct APIs with well-defined exception behavior.
Code generally becomes more readable (less lines of code, less boilerplate,
more logic-focused APIs because of greater language flexibility).
Diffstat (limited to 'source/blender/editors/space_outliner')
-rw-r--r-- | source/blender/editors/space_outliner/tree/tree_view_view_layer.cc | 64 |
1 files changed, 22 insertions, 42 deletions
diff --git a/source/blender/editors/space_outliner/tree/tree_view_view_layer.cc b/source/blender/editors/space_outliner/tree/tree_view_view_layer.cc index 0d35db36e5b..e8afff12991 100644 --- a/source/blender/editors/space_outliner/tree/tree_view_view_layer.cc +++ b/source/blender/editors/space_outliner/tree/tree_view_view_layer.cc @@ -24,14 +24,13 @@ #include "BKE_layer.h" -#include "BLI_ghash.h" #include "BLI_listbase.h" #include "BLI_listbase_wrapper.hh" +#include "BLI_map.hh" +#include "BLI_vector.hh" #include "BLT_translation.h" -#include "MEM_guardedalloc.h" - #include "../outliner_intern.h" #include "tree_view.hh" @@ -44,13 +43,16 @@ template<typename T> using List = ListBaseWrapper<T>; class ObjectsChildrenBuilder { public: ObjectsChildrenBuilder(SpaceOutliner &outliner); - ~ObjectsChildrenBuilder(); + ~ObjectsChildrenBuilder() = default; void operator()(TreeElement &collection_tree_elem); private: + using TreeChildren = Vector<TreeElement *>; + using ObjectTreeElementsMap = Map<Object *, TreeChildren>; + SpaceOutliner &_outliner; - GHash &_object_tree_elements_hash; + ObjectTreeElementsMap _object_tree_elements_map; void object_tree_elements_lookup_create_recursive(TreeElement *te_parent); void make_object_parent_hierarchy_collections(); @@ -187,22 +189,8 @@ void TreeViewViewLayer::add_layer_collection_objects_children(TreeElement &colle * * \{ */ -ObjectsChildrenBuilder::ObjectsChildrenBuilder(SpaceOutliner &outliner) - : _outliner(outliner), - _object_tree_elements_hash( - *BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, __func__)) -{ -} - -ObjectsChildrenBuilder::~ObjectsChildrenBuilder() +ObjectsChildrenBuilder::ObjectsChildrenBuilder(SpaceOutliner &outliner) : _outliner(outliner) { - GHASH_FOREACH_BEGIN (ListBase *, tree_elements, &_object_tree_elements_hash) { - BLI_freelistN(tree_elements); - MEM_freeN(tree_elements); - } - GHASH_FOREACH_END(); - - BLI_ghash_free(&_object_tree_elements_hash, nullptr, nullptr); } void ObjectsChildrenBuilder::operator()(TreeElement &collection_tree_elem) @@ -221,18 +209,15 @@ void ObjectsChildrenBuilder::object_tree_elements_lookup_create_recursive(TreeEl if (tselem->type == TSE_LAYER_COLLECTION) { object_tree_elements_lookup_create_recursive(te); + continue; } - else if (tselem->type == 0 && te->idcode == ID_OB) { - Object *ob = (Object *)tselem->id; - ListBase *tree_elements = static_cast<ListBase *>( - BLI_ghash_lookup(&_object_tree_elements_hash, ob)); - if (tree_elements == nullptr) { - tree_elements = static_cast<ListBase *>(MEM_callocN(sizeof(ListBase), __func__)); - BLI_ghash_insert(&_object_tree_elements_hash, ob, tree_elements); - } + if (tselem->type == 0 && te->idcode == ID_OB) { + Object *ob = (Object *)tselem->id; + /* Lookup children or add new, empty children vector. */ + Vector<TreeElement *> &tree_elements = _object_tree_elements_map.lookup_or_add(ob, {}); - BLI_addtail(tree_elements, BLI_genericNodeN(te)); + tree_elements.append(te); object_tree_elements_lookup_create_recursive(te); } } @@ -244,24 +229,21 @@ void ObjectsChildrenBuilder::object_tree_elements_lookup_create_recursive(TreeEl */ void ObjectsChildrenBuilder::make_object_parent_hierarchy_collections() { - GHashIterator gh_iter; - GHASH_ITER (gh_iter, &_object_tree_elements_hash) { - Object *child = static_cast<Object *>(BLI_ghashIterator_getKey(&gh_iter)); + for (ObjectTreeElementsMap::MutableItem item : _object_tree_elements_map.items()) { + Object *child = item.key; if (child->parent == nullptr) { continue; } - ListBase *child_ob_tree_elements = static_cast<ListBase *>( - BLI_ghashIterator_getValue(&gh_iter)); - ListBase *parent_ob_tree_elements = static_cast<ListBase *>( - BLI_ghash_lookup(&_object_tree_elements_hash, child->parent)); + Vector<TreeElement *> &child_ob_tree_elements = item.value; + Vector<TreeElement *> *parent_ob_tree_elements = _object_tree_elements_map.lookup_ptr( + child->parent); if (parent_ob_tree_elements == nullptr) { continue; } - for (LinkData *link : List<LinkData>(parent_ob_tree_elements)) { - TreeElement *parent_ob_tree_element = static_cast<TreeElement *>(link->data); + for (TreeElement *parent_ob_tree_element : *parent_ob_tree_elements) { TreeElement *parent_ob_collection_tree_element = nullptr; bool found = false; @@ -274,9 +256,7 @@ void ObjectsChildrenBuilder::make_object_parent_hierarchy_collections() parent_ob_collection_tree_element = parent_ob_collection_tree_element->parent; } - for (LinkData *link_iter : List<LinkData>(child_ob_tree_elements)) { - TreeElement *child_ob_tree_element = static_cast<TreeElement *>(link_iter->data); - + for (TreeElement *child_ob_tree_element : child_ob_tree_elements) { if (child_ob_tree_element->parent == parent_ob_collection_tree_element) { /* Move from the collection subtree into the parent object subtree. */ BLI_remlink(&parent_ob_collection_tree_element->subtree, child_ob_tree_element); @@ -294,7 +274,7 @@ void ObjectsChildrenBuilder::make_object_parent_hierarchy_collections() &_outliner, &parent_ob_tree_element->subtree, child, parent_ob_tree_element, 0, 0); outliner_free_tree(&child_ob_tree_element->subtree); child_ob_tree_element->flag |= TE_CHILD_NOT_IN_COLLECTION; - BLI_addtail(child_ob_tree_elements, BLI_genericNodeN(child_ob_tree_element)); + child_ob_tree_elements.append(child_ob_tree_element); } } } |