Dependency graph patch, provided by Jean-Luc Peuriere.

Works like a charm... well it now replaces the old base-sorting hack. :)
Next stage will be to define how to further integrate it. Plus some
minor code cleanups... static/internal functions versus external, etc.

1 files changed, 129 insertions, 0 deletions

diff --git a/source/blender/blenkernel/depsgraph_private.h b/source/blender/blenkernel/depsgraph_private.h
new file mode 100644
index 00000000000..7b3da76c652
--- /dev/null
+++ b/source/blender/blenkernel/depsgraph_private.h
@@ -0,0 +1,129 @@
+/**
+ * $Id$
+ *
+ * ***** BEGIN GPL/BL DUAL 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. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this.
+ *
+ * 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2004 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+#ifndef DEPSGRAPH_PRIVATE
+#define DEPSGRAPH_PRIVATE
+
+#include "BKE_depsgraph.h"
+#include "DNA_constraint_types.h"
+#include "BKE_constraint.h"
+
+
+#define DEPSX	5.0
+#define DEPSY	1.8
+
+#define DAGQUEUEALLOC 50
+
+enum {
+	DAG_WHITE = 0,
+	DAG_GRAY = 1,
+	DAG_BLACK = 2
+};
+
+
+
+typedef struct DagAdjList
+{
+	struct DagNode *node;
+	dag_rel_type type;
+	int count; // number of identical arcs
+	struct DagAdjList *next;
+} DagAdjList;
+
+
+typedef struct DagNode 
+{
+	int color;
+	short type;
+	float x, y, k;	
+	void * ob;
+	void * first_ancestor;
+	int		ancestor_count;
+	int BFS_dist;		// BFS distance
+	int DFS_dist;		// DFS distance
+	int DFS_dvtm;		// DFS discovery time
+	int DFS_fntm;		// DFS Finishing time
+	struct DagAdjList *child;
+	struct DagNode *next;
+} DagNode;
+
+typedef struct DagNodeQueueElem {
+	struct DagNode *node;
+	struct DagNodeQueueElem *next;
+} DagNodeQueueElem;
+
+typedef struct DagNodeQueue
+{
+	DagNodeQueueElem *first;
+	DagNodeQueueElem *last;
+	int count;
+	int maxlevel;
+	struct DagNodeQueue *freenodes;
+} DagNodeQueue;
+
+// forest as we may have more than one DAG unnconected
+typedef struct DagForest 
+{
+	ListBase DagNode;
+	int numNodes;
+	int is_acyclic;
+} DagForest;
+
+
+// queue operations
+DagNodeQueue * queue_create (int slots);
+void queue_raz(DagNodeQueue *queue);
+void push_queue(DagNodeQueue *queue, DagNode *node);
+void push_stack(DagNodeQueue *queue, DagNode *node);
+DagNode * pop_queue(DagNodeQueue *queue);
+DagNode * get_top_node_queue(DagNodeQueue *queue);
+
+// Dag management
+DagForest *getMainDag(void);
+void setMainDag(DagForest *dag);
+DagForest * dag_init(void);
+DagNode * dag_find_node (DagForest *forest,void * fob);
+DagNode * dag_add_node (DagForest *forest,void * fob);
+DagNode * dag_get_node (DagForest *forest,void * fob);
+DagNode * dag_get_sub_node (DagForest *forest,void * fob);
+void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, dag_rel_type rel);
+
+void graph_bfs(void);
+
+DagNodeQueue * graph_dfs(void);
+
+void set_node_xy(DagNode *node, float x, float y);
+void graph_print_queue(DagNodeQueue *nqueue);
+void graph_print_queue_dist(DagNodeQueue *nqueue);
+void graph_print_adj_list(void);
+
+int build_deps(short mask);
+
+#endif
+ 
\ No newline at end of file