blender
/
blender
129
398
Fork 572
Code Issues 6.2k Pull Requests 749 Projects 19 Wiki Activity

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).
This commit is contained in:
Julian Eisel 2020-11-07 00:15:09 +01:00
parent c9cc03b688
commit 6b18e13c5b
1 changed files with 22 additions and 42 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

64
source/blender/editors/space_outliner/tree/tree_view_view_layer.cc
View File

@ -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,24 +189,10 @@ 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(SpaceOutliner &outliner) : _outliner(outliner)
{
}
ObjectsChildrenBuilder::~ObjectsChildrenBuilder()
{
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)
{
object_tree_elements_lookup_create_recursive(&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) {
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));
/* Lookup children or add new, empty children vector. */
Vector<TreeElement *> &tree_elements = _object_tree_elements_map.lookup_or_add(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);
}
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);
}
}
}