diff options
author | Sergey Sharybin <sergey.vfx@gmail.com> | 2017-12-01 13:35:36 +0300 |
---|---|---|
committer | Sergey Sharybin <sergey.vfx@gmail.com> | 2017-12-01 13:40:50 +0300 |
commit | 0591fb17e93517d849ab6cb13f2028cff0c5a540 (patch) | |
tree | ec16e67756a21795ed9104d8231ddd7c8c3ea767 | |
parent | 7270e8cc8f8fa3ec619c980b5d4967712ade0a43 (diff) |
Depsgraph: Add query API to traverse all dependent IDs of the given ID
-rw-r--r-- | source/blender/depsgraph/CMakeLists.txt | 1 | ||||
-rw-r--r-- | source/blender/depsgraph/DEG_depsgraph_query.h | 14 | ||||
-rw-r--r-- | source/blender/depsgraph/intern/depsgraph_query_foreach.cc | 147 |
3 files changed, 161 insertions, 1 deletions
diff --git a/source/blender/depsgraph/CMakeLists.txt b/source/blender/depsgraph/CMakeLists.txt index c4cd861739e..89ba6e27aed 100644 --- a/source/blender/depsgraph/CMakeLists.txt +++ b/source/blender/depsgraph/CMakeLists.txt @@ -65,6 +65,7 @@ set(SRC intern/depsgraph_debug.cc intern/depsgraph_eval.cc intern/depsgraph_query.cc + intern/depsgraph_query_foreach.cc intern/depsgraph_query_iter.cc intern/depsgraph_tag.cc intern/depsgraph_type_defines.cc diff --git a/source/blender/depsgraph/DEG_depsgraph_query.h b/source/blender/depsgraph/DEG_depsgraph_query.h index 0c374668845..7771d35d581 100644 --- a/source/blender/depsgraph/DEG_depsgraph_query.h +++ b/source/blender/depsgraph/DEG_depsgraph_query.h @@ -67,7 +67,7 @@ struct Object *DEG_get_evaluated_object(struct Depsgraph *depsgraph, struct Obje /* Get evaluated version of given ID datablock. */ struct ID *DEG_get_evaluated_id(struct Depsgraph *depsgraph, struct ID *id); -/* ************************ DAG iterators ********************* */ +/* ************************ DEG iterators ********************* */ enum { DEG_ITER_OBJECT_FLAG_SET = (1 << 0), @@ -125,6 +125,18 @@ void DEG_iterator_objects_end(struct BLI_Iterator *iter); ITER_END \ } +/* ************************ DEG traversal ********************* */ + +typedef void (*DEGForeachIDCallback)(ID *id, void *user_data); + +/* NOTE: Modifies runtime flags in depsgraph nodes, so can not be used in + * parallel. Keep an eye on that! + */ +void DEG_foreach_dependent_ID(const Depsgraph *depsgraph, + const ID *id, + DEGForeachIDCallback callback, void *user_data); + + #ifdef __cplusplus } /* extern "C" */ #endif diff --git a/source/blender/depsgraph/intern/depsgraph_query_foreach.cc b/source/blender/depsgraph/intern/depsgraph_query_foreach.cc new file mode 100644 index 00000000000..b1353f528bc --- /dev/null +++ b/source/blender/depsgraph/intern/depsgraph_query_foreach.cc @@ -0,0 +1,147 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2017 Blender Foundation. + * All rights reserved. + * + * Original Author: Sergey Sharybin + * Contributor(s): None Yet + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/depsgraph/intern/depsgraph_query_foreach.cc + * \ingroup depsgraph + * + * Implementation of Querying and Filtering API's + */ + +// TODO(sergey): Use some sort of wrapper. +#include <deque> + +#include "MEM_guardedalloc.h" + +extern "C" { +#include "BLI_utildefines.h" +#include "BLI_ghash.h" +} /* extern "C" */ + +#include "DNA_object_types.h" +#include "DNA_scene_types.h" + +#include "DEG_depsgraph.h" +#include "DEG_depsgraph_query.h" + +#include "intern/depsgraph_intern.h" + +#include "intern/nodes/deg_node.h" +#include "intern/nodes/deg_node_component.h" +#include "intern/nodes/deg_node_operation.h" + +#include "util/deg_util_foreach.h" + +/* ************************ DEG TRAVERSAL ********************* */ + +namespace DEG { + +typedef std::deque<OperationDepsNode *> TraversalQueue; + +static void deg_foreach_clear_flags(const Depsgraph *graph) +{ + foreach (OperationDepsNode *op_node, graph->operations) { + op_node->scheduled = false; + } + foreach (IDDepsNode *id_node, graph->id_nodes) { + id_node->done = false; + } +} + +static void deg_foreach_dependent_ID(const Depsgraph *graph, + const ID *id, + DEGForeachIDCallback callback, + void *user_data) +{ + /* Start with getting ID node from the graph. */ + IDDepsNode *id_node = graph->find_id_node(id); + if (id_node == NULL) { + /* TODO(sergey): Shall we inform or assert here about attempt to start + * iterating over non-existing ID? + */ + return; + } + /* Make sure all runtime flags are ready and clear. */ + deg_foreach_clear_flags(graph); + /* Start with scheduling all operations from ID node. */ + TraversalQueue queue; + GHASH_FOREACH_BEGIN(ComponentDepsNode *, comp_node, id_node->components) + { + foreach (OperationDepsNode *op_node, comp_node->operations) { + queue.push_back(op_node); + op_node->scheduled = true; + } + } + GHASH_FOREACH_END(); + id_node->done = true; + /* Process the queue. */ + while (!queue.empty()) { + /* get next operation node to process. */ + OperationDepsNode *op_node = queue.front(); + queue.pop_front(); + for (;;) { + /* Check whether we need to inform callee about corresponding ID node. */ + ComponentDepsNode *comp_node = op_node->owner; + IDDepsNode *id_node = comp_node->owner; + if (!id_node->done) { + /* TODO(sergey): Is it orig or CoW? */ + callback(id_node->id_orig, user_data); + id_node->done = true; + } + /* Schedule outgoing operation nodes. */ + if (op_node->outlinks.size() == 1) { + OperationDepsNode *to_node = (OperationDepsNode *)op_node->outlinks[0]->to; + if (to_node->scheduled == false) { + to_node->scheduled = true; + op_node = to_node; + } + else { + break; + } + } + else { + foreach (DepsRelation *rel, op_node->outlinks) { + OperationDepsNode *to_node = (OperationDepsNode *)rel->to; + if (to_node->scheduled == false) { + queue.push_front(to_node); + to_node->scheduled = true; + } + } + break; + } + } + } +} + +} // namespace DEG + +void DEG_foreach_dependent_ID(const Depsgraph *depsgraph, + const ID *id, + DEGForeachIDCallback callback, void *user_data) +{ + DEG::deg_foreach_dependent_ID((const DEG::Depsgraph *)depsgraph, + id, + callback, user_data); +} |