[Bf-blender-cvs] [006dccd] depsgraph_refactor: Depsgraph: Code cleanup, move transitive reduction to own file
Sergey Sharybin
noreply at git.blender.org
Mon Mar 16 14:34:58 CET 2015
Commit: 006dccd87b7ab72e680553f8133e9a60282f5285
Author: Sergey Sharybin
Date: Mon Mar 16 18:25:02 2015 +0500
Branches: depsgraph_refactor
https://developer.blender.org/rB006dccd87b7ab72e680553f8133e9a60282f5285
Depsgraph: Code cleanup, move transitive reduction to own file
It might actually be gone in the future since it causes issues
with threaded evaluation order.
===================================================================
M source/blender/depsgraph/CMakeLists.txt
M source/blender/depsgraph/intern/depsgraph_build.cpp
A source/blender/depsgraph/util/depsgraph_util_transitive.cpp
A source/blender/depsgraph/util/depsgraph_util_transitive.h
===================================================================
diff --git a/source/blender/depsgraph/CMakeLists.txt b/source/blender/depsgraph/CMakeLists.txt
index f842a61..eb25e49 100644
--- a/source/blender/depsgraph/CMakeLists.txt
+++ b/source/blender/depsgraph/CMakeLists.txt
@@ -59,6 +59,7 @@ set(SRC
intern/depsgraph_type_defines.cpp
util/depsgraph_util_cycle.cpp
util/depsgraph_util_pchanmap.cpp
+ util/depsgraph_util_transitive.cpp
DEG_depsgraph.h
DEG_depsgraph_build.h
@@ -76,11 +77,13 @@ set(SRC
intern/depsgraph_queue.h
intern/depsgraph_types.h
+ util/depsgraph_util_cycle.h
util/depsgraph_util_function.h
util/depsgraph_util_hash.h
util/depsgraph_util_map.h
util/depsgraph_util_pchanmap.h
util/depsgraph_util_set.h
+ util/depsgraph_util_transitive.h
)
TEST_UNORDERED_MAP_SUPPORT()
diff --git a/source/blender/depsgraph/intern/depsgraph_build.cpp b/source/blender/depsgraph/intern/depsgraph_build.cpp
index 1cb53b8..a0bb272 100644
--- a/source/blender/depsgraph/intern/depsgraph_build.cpp
+++ b/source/blender/depsgraph/intern/depsgraph_build.cpp
@@ -97,6 +97,7 @@ extern "C" {
#include "depsgraph_intern.h"
#include "depsgraph_util_cycle.h"
+#include "depsgraph_util_transitive.h"
/* ****************** */
/* External Build API */
@@ -176,77 +177,6 @@ string deg_fcurve_id_name(const FCurve *fcu)
return string(fcu->rna_path) + index_buf;
}
-/* -------------------------------------------------- */
-
-/* performs a transitive reduction to remove redundant relations
- * http://en.wikipedia.org/wiki/Transitive_reduction
- *
- * XXX The current implementation is somewhat naive and has O(V*E) worst case runtime.
- * A more optimized algorithm can be implemented later, e.g.
- *
- * http://www.sciencedirect.com/science/article/pii/0304397588900321/pdf?md5=3391e309b708b6f9cdedcd08f84f4afc&pid=1-s2.0-0304397588900321-main.pdf
- *
- * Care has to be taken to make sure the algorithm can handle the cyclic case too!
- * (unless we can to prevent this case early on)
- */
-
-enum {
- OP_VISITED = 1,
- OP_REACHABLE = 2,
-};
-
-static void deg_graph_tag_paths_recursive(DepsNode *node)
-{
- if (node->done & OP_VISITED)
- return;
- node->done |= OP_VISITED;
-
- for (OperationDepsNode::Relations::const_iterator it = node->inlinks.begin(); it != node->inlinks.end(); ++it) {
- DepsRelation *rel = *it;
-
- deg_graph_tag_paths_recursive(rel->from);
- /* do this only in inlinks loop, so the target node does not get flagged! */
- rel->from->done |= OP_REACHABLE;
- }
-}
-
-static void deg_graph_transitive_reduction(Depsgraph *graph)
-{
- for (Depsgraph::OperationNodes::const_iterator it_target = graph->operations.begin(); it_target != graph->operations.end(); ++it_target) {
- OperationDepsNode *target = *it_target;
-
- /* clear tags */
- for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin(); it != graph->operations.end(); ++it) {
- OperationDepsNode *node = *it;
- node->done = 0;
- }
-
- /* mark nodes from which we can reach the target
- * start with children, so the target node and direct children are not flagged
- */
- target->done |= OP_VISITED;
- for (OperationDepsNode::Relations::const_iterator it = target->inlinks.begin(); it != target->inlinks.end(); ++it) {
- DepsRelation *rel = *it;
-
- deg_graph_tag_paths_recursive(rel->from);
- }
-
- /* remove redundant paths to the target */
- for (DepsNode::Relations::const_iterator it_rel = target->inlinks.begin(); it_rel != target->inlinks.end();) {
- DepsRelation *rel = *it_rel;
- ++it_rel; /* increment in advance, so we can safely remove the relation */
-
- if (rel->from->type == DEPSNODE_TYPE_TIMESOURCE) {
- /* HACK: time source nodes don't get "done" flag set/cleared */
- // TODO: there will be other types in future, so iterators above need modifying
- }
- else if (rel->from->done & OP_REACHABLE) {
- OBJECT_GUARDED_DELETE(rel, DepsRelation);
- }
- }
- }
-}
-
static void deg_graph_build_finalize(Depsgraph *graph)
{
std::stack<OperationDepsNode*> stack;
diff --git a/source/blender/depsgraph/util/depsgraph_util_transitive.cpp b/source/blender/depsgraph/util/depsgraph_util_transitive.cpp
new file mode 100644
index 0000000..e115259
--- /dev/null
+++ b/source/blender/depsgraph/util/depsgraph_util_transitive.cpp
@@ -0,0 +1,129 @@
+/*
+ * ***** 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) 2015 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): Lukas Toenne
+ * Sergey Sharybin,
+ */
+
+extern "C" {
+#include "MEM_guardedalloc.h"
+
+#include "BLI_utildefines.h"
+
+#include "DNA_ID.h"
+
+#include "RNA_access.h"
+#include "RNA_types.h"
+}
+
+#include "depsgraph_util_transitive.h"
+#include "depsgraph.h"
+#include "depsnode.h"
+#include "depsnode_component.h"
+#include "depsnode_operation.h"
+
+/* -------------------------------------------------- */
+
+/* Performs a transitive reduction to remove redundant relations.
+ * http://en.wikipedia.org/wiki/Transitive_reduction
+ *
+ * XXX The current implementation is somewhat naive and has O(V*E) worst case
+ * runtime.
+ * A more optimized algorithm can be implemented later, e.g.
+ *
+ * http://www.sciencedirect.com/science/article/pii/0304397588900321/pdf?md5=3391e309b708b6f9cdedcd08f84f4afc&pid=1-s2.0-0304397588900321-main.pdf
+ *
+ * Care has to be taken to make sure the algorithm can handle the cyclic case
+ * too! (unless we can to prevent this case early on).
+ */
+
+enum {
+ OP_VISITED = 1,
+ OP_REACHABLE = 2,
+};
+
+static void deg_graph_tag_paths_recursive(DepsNode *node)
+{
+ if (node->done & OP_VISITED)
+ return;
+ node->done |= OP_VISITED;
+
+ for (OperationDepsNode::Relations::const_iterator it = node->inlinks.begin();
+ it != node->inlinks.end();
+ ++it)
+ {
+ DepsRelation *rel = *it;
+
+ deg_graph_tag_paths_recursive(rel->from);
+ /* Do this only in inlinks loop, so the target node does not get
+ * flagged.
+ */
+ rel->from->done |= OP_REACHABLE;
+ }
+}
+
+void deg_graph_transitive_reduction(Depsgraph *graph)
+{
+ for (Depsgraph::OperationNodes::const_iterator it_target = graph->operations.begin();
+ it_target != graph->operations.end();
+ ++it_target)
+ {
+ OperationDepsNode *target = *it_target;
+
+ /* clear tags */
+ for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin();
+ it != graph->operations.end();
+ ++it)
+ {
+ OperationDepsNode *node = *it;
+ node->done = 0;
+ }
+
+ /* mark nodes from which we can reach the target
+ * start with children, so the target node and direct children are not flagged
+ */
+ target->done |= OP_VISITED;
+ for (OperationDepsNode::Relations::const_iterator it = target->inlinks.begin();
+ it != target->inlinks.end();
+ ++it)
+ {
+ DepsRelation *rel = *it;
+
+ deg_graph_tag_paths_recursive(rel->from);
+ }
+
+ /* remove redundant paths to the target */
+ for (DepsNode::Relations::const_iterator it_rel = target->inlinks.begin();
+ it_rel != target->inlinks.end();
+ )
+ {
+ DepsRelation *rel = *it_rel;
+ ++it_rel; /* increment in advance, so we can safely remove the relation */
+
+ if (rel->from->type == DEPSNODE_TYPE_TIMESOURCE) {
+ /* HACK: time source nodes don't get "done" flag set/cleared */
+ // TODO: there will be other types in future, so iterators above need modifying
+ }
+ else if (rel->from->done & OP_REACHABLE) {
+ OBJECT_GUARDED_DELETE(rel, DepsRelation);
+ }
+ }
+ }
+}
diff --git a/source/blender/depsgraph/util/depsgraph_util_transitive.h b/source/blender/depsgraph/util/depsgraph_util_transitive.h
new file mode 100644
index 0000000..8995c18
--- /dev/null
+++ b/source/blender/depsgraph/util/depsgraph_util_transitive.h
@@ -0,0 +1,32 @@
+/*
+ * ***** 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) 2015 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): Lukas Toenne
+ * Sergey Sharybin,
+ */
+
+#ifndef __DEPSGRAPH_UTIL_TRANSITIVE_H__
+#define __DEPSGRAPH_UTIL_TRANSITIVE_H__
+
+struct Depsgraph;
+
+void deg_graph_transitive_reduction(Depsgraph *graph);
+
+#endif /* __DEPSGRAPH_UTIL_TRANSITIVE_H__ */
More information about the Bf-blender-cvs
mailing list