[Bf-blender-cvs] [5e3d519] depsgraph_refactor: Basic Scheduler class for the depsgraph.

[Lukas Tönne]

Commit: 5e3d519657daff815f2186d6b2402d8dffe31ff3
Author: Lukas Tönne
Date:   Wed May 21 23:04:37 2014 +0200
https://developer.blender.org/rB5e3d519657daff815f2186d6b2402d8dffe31ff3

Basic Scheduler class for the depsgraph.

===================================================================

M	source/blender/depsgraph/intern/depsgraph_debug.cpp
M	source/blender/depsgraph/intern/depsgraph_eval.cpp
M	source/blender/depsgraph/intern/depsgraph_eval.h
M	source/blender/depsgraph/util/depsgraph_util_priority_queue.h

===================================================================

diff --git a/source/blender/depsgraph/intern/depsgraph_debug.cpp b/source/blender/depsgraph/intern/depsgraph_debug.cpp
index 465f759..57a5fe9 100644
--- a/source/blender/depsgraph/intern/depsgraph_debug.cpp
+++ b/source/blender/depsgraph/intern/depsgraph_debug.cpp
@@ -315,7 +315,7 @@ static void deg_debug_graphviz_node_single(const DebugContext &ctx, const DepsNo
 	deg_debug_printf(ctx, "[");
 //	deg_debug_printf(ctx, "label=<<B>%s</B>>", name);
 	if (priority >= 0.0f)
-		deg_debug_printf(ctx, "label=<%s (<I>%f</I>)>", name, priority);
+		deg_debug_printf(ctx, "label=<%s<BR/>(<I>%.2f</I>)>", name, priority);
 	else
 		deg_debug_printf(ctx, "label=<%s>", name);
 	deg_debug_printf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname);
diff --git a/source/blender/depsgraph/intern/depsgraph_eval.cpp b/source/blender/depsgraph/intern/depsgraph_eval.cpp
index 4fb4afb..5353d9f 100644
--- a/source/blender/depsgraph/intern/depsgraph_eval.cpp
+++ b/source/blender/depsgraph/intern/depsgraph_eval.cpp
@@ -58,6 +58,7 @@ extern "C" {
 #include "RNA_types.h"
 } /* extern "C" */
 
+#include "depsgraph.h"
 #include "depsnode.h"
 #include "depsnode_component.h"
 #include "depsnode_operation.h"
@@ -65,7 +66,6 @@ extern "C" {
 #include "depsgraph_eval.h"
 #include "depsgraph_queue.h"
 #include "depsgraph_intern.h"
-#include "depsgraph_util_priority_queue.h"
 
 /* *************************************************** */
 /* Multi-Threaded Evaluation Internals */
@@ -124,17 +124,50 @@ static void deg_exec_node(Depsgraph *graph, DepsNode *node, eEvaluationContextTy
 	/* NOTE: "generic" nodes cannot be executed, but will still end up calling this */
 }
 
-/* *************************************************** */
-/* Evaluation Entrypoints */
+Scheduler::Scheduler()
+{
+}
 
-struct CompareOperationNode {
-	bool operator() (OperationDepsNode *a, OperationDepsNode *b)
-	{
-		return a->eval_priority < b->eval_priority;
+Scheduler::~Scheduler()
+{
+}
+
+static bool is_node_ready(OperationDepsNode *node)
+{
+	return (node->flag & DEPSOP_FLAG_NEEDS_UPDATE) && node->num_links_pending == 0;
+}
+
+void Scheduler::schedule_graph(Depsgraph *graph)
+{
+	for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin(); it != graph->operations.end(); ++it) {
+		OperationDepsNode *node = *it;
+		
+		if (is_node_ready(node))
+			queue.push(node);
 	}
-};
+}
 
-typedef priority_queue<OperationDepsNode *, vector<OperationDepsNode *>, CompareOperationNode> EvalQueue;
+OperationDepsNode *Scheduler::retrieve_node()
+{
+	OperationDepsNode *node = queue.top();
+	queue.pop();
+	return node;
+}
+
+void Scheduler::finish_node(OperationDepsNode *node)
+{
+	for (OperationDepsNode::Relations::const_iterator it = node->outlinks.begin(); it != node->outlinks.end(); ++it) {
+		DepsRelation *rel = *it;
+		
+		BLI_assert(rel->to->num_links_pending > 0);
+		--rel->to->num_links_pending;
+		if (rel->to->num_links_pending == 0)
+			queue.push(node);
+	}
+}
+
+/* *************************************************** */
+/* Evaluation Entrypoints */
 
 static void calculate_eval_priority(OperationDepsNode *node)
 {
@@ -156,6 +189,8 @@ static void calculate_eval_priority(OperationDepsNode *node)
 		node->eval_priority = 0.0f;
 }
 
+
+
 /* Evaluate all nodes tagged for updating 
  * ! This is usually done as part of main loop, but may also be 
  *   called from frame-change update
@@ -179,6 +214,9 @@ void DEG_evaluate_on_refresh(Depsgraph *graph, eEvaluationContextType context_ty
 	
 	DEG_debug_eval_step("Eval Priority Calculation");
 	
+	EvalQueue queue;
+	
+	
 	/* from the root node, start queuing up nodes to evaluate */
 	// ... start scheduler, etc.
 	// ...
diff --git a/source/blender/depsgraph/intern/depsgraph_eval.h b/source/blender/depsgraph/intern/depsgraph_eval.h
index 72afad2..5523d53 100644
--- a/source/blender/depsgraph/intern/depsgraph_eval.h
+++ b/source/blender/depsgraph/intern/depsgraph_eval.h
@@ -33,8 +33,10 @@
 #ifndef __DEPSGRAPH_EVAL_TYPES_H__
 #define __DEPSGRAPH_EVAL_TYPES_H__
 
+#include "depsgraph_util_priority_queue.h"
+
 struct Depsgraph;
-struct DepsNode;
+struct OperationDepsNode;
 
 /* ****************************************** */
 /* Operation Contexts */
@@ -124,4 +126,29 @@ typedef struct DEG_PoseContext {
 
 /* ****************************************** */
 
+
+struct CompareOperationNode {
+	bool operator() (OperationDepsNode *a, OperationDepsNode *b)
+	{
+		return a->eval_priority < b->eval_priority;
+	}
+};
+
+typedef priority_queue<OperationDepsNode *, vector<OperationDepsNode *>, CompareOperationNode> EvalQueue;
+
+class Scheduler {
+public:
+	Scheduler();
+	~Scheduler();
+	
+	void schedule_graph(Depsgraph *graph);
+	OperationDepsNode *retrieve_node();
+	void finish_node(OperationDepsNode *node);
+	
+private:
+	EvalQueue queue;
+};
+
+/* ****************************************** */
+
 #endif // __DEPSGRAPH_EVAL_TYPES_H__
diff --git a/source/blender/depsgraph/util/depsgraph_util_priority_queue.h b/source/blender/depsgraph/util/depsgraph_util_priority_queue.h
index 6425271..3c50a14 100644
--- a/source/blender/depsgraph/util/depsgraph_util_priority_queue.h
+++ b/source/blender/depsgraph/util/depsgraph_util_priority_queue.h
@@ -26,7 +26,9 @@
 #define __DEPSGRAPH_UTIL_PRIORITY_QUEUE_H__
 
 #include <queue>
+#include <vector>
 
 using std::priority_queue;
+using std::vector;
 
 #endif /* __DEPSGRAPH_UTIL_PRIORITY_QUEUE_H__ */