Depsgraph: Add query API to traverse all dependent IDs of the given ID
authorSergey Sharybin <sergey.vfx@gmail.com>
Fri, 1 Dec 2017 10:35:36 +0000 (11:35 +0100)
committerSergey Sharybin <sergey.vfx@gmail.com>
Mon, 18 Dec 2017 15:15:47 +0000 (16:15 +0100)
source/blender/depsgraph/CMakeLists.txt
source/blender/depsgraph/DEG_depsgraph_query.h
source/blender/depsgraph/intern/depsgraph_query_foreach.cc [new file with mode: 0644]

index 9478ca306e9f37df0333001228d807a63f5ce95f..b76275566bd4fb55297784174877466105a4c984 100644 (file)
@@ -62,6 +62,7 @@ set(SRC
        intern/depsgraph_debug.cc
        intern/depsgraph_eval.cc
        intern/depsgraph_query.cc
+       intern/depsgraph_query_foreach.cc
        intern/depsgraph_tag.cc
        intern/depsgraph_type_defines.cc
 
index ccd204a20834e07211154666dd346cf839ba9211..f8cfb407831a172e4e11018c1657629e37d89b4d 100644 (file)
@@ -47,6 +47,18 @@ bool DEG_id_type_tagged(struct Main *bmain, short idtype);
 /* Get additional evaluation flags for the given ID. */
 short DEG_get_eval_flags_for_id(struct Depsgraph *graph, struct ID *id);
 
+/* ************************ 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 (file)
index 0000000..f2a121f
--- /dev/null
@@ -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, 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);
+}