synched with trunk at revision 36569
[blender.git] / source / blender / blenkernel / depsgraph_private.h
1 /*
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2004 Blender Foundation.
21  * All rights reserved.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/depsgraph_private.h
29  *  \ingroup bke
30  */
31
32 #ifndef DEPSGRAPH_PRIVATE
33 #define DEPSGRAPH_PRIVATE
34
35 #include "BKE_depsgraph.h"
36 #include "DNA_constraint_types.h"
37 #include "BKE_constraint.h"
38
39
40 #define DEPSX   5.0f
41 #define DEPSY   1.8f
42
43 #define DAGQUEUEALLOC 50
44
45 enum {
46         DAG_WHITE = 0,
47         DAG_GRAY = 1,
48         DAG_BLACK = 2
49 };
50
51
52
53 typedef struct DagAdjList
54 {
55         struct DagNode *node;
56         short type;
57         int count;                      // number of identical arcs
58         unsigned int lay;   // for flushing redraw/rebuild events
59         const char *name;
60         struct DagAdjList *next;
61 } DagAdjList;
62
63
64 typedef struct DagNode 
65 {
66         int color;
67         short type;
68         float x, y, k;  
69         void * ob;
70         void * first_ancestor;
71         int ancestor_count;
72         unsigned int lay;                       // accumulated layers of its relations + itself
73         unsigned int scelay;                    // layers due to being in scene
74         int lasttime;           // if lasttime != DagForest->time, this node was not evaluated yet for flushing
75         int BFS_dist;           // BFS distance
76         int DFS_dist;           // DFS distance
77         int DFS_dvtm;           // DFS discovery time
78         int DFS_fntm;           // DFS Finishing time
79         struct DagAdjList *child;
80         struct DagAdjList *parent;
81         struct DagNode *next;
82 } DagNode;
83
84 typedef struct DagNodeQueueElem {
85         struct DagNode *node;
86         struct DagNodeQueueElem *next;
87 } DagNodeQueueElem;
88
89 typedef struct DagNodeQueue
90 {
91         DagNodeQueueElem *first;
92         DagNodeQueueElem *last;
93         int count;
94         int maxlevel;
95         struct DagNodeQueue *freenodes;
96 } DagNodeQueue;
97
98 // forest as we may have more than one DAG unnconected
99 typedef struct DagForest 
100 {
101         ListBase DagNode;
102         struct GHash *nodeHash;
103         int numNodes;
104         int is_acyclic;
105         int time;               // for flushing/tagging, compare with node->lasttime
106 } DagForest;
107
108
109 // queue operations
110 DagNodeQueue * queue_create (int slots);
111 void queue_raz(DagNodeQueue *queue);
112 void push_queue(DagNodeQueue *queue, DagNode *node);
113 void push_stack(DagNodeQueue *queue, DagNode *node);
114 DagNode * pop_queue(DagNodeQueue *queue);
115 DagNode * get_top_node_queue(DagNodeQueue *queue);
116
117 // Dag management
118 DagForest *getMainDag(void);
119 void setMainDag(DagForest *dag);
120 DagForest * dag_init(void);
121 DagNode * dag_find_node (DagForest *forest,void * fob);
122 DagNode * dag_add_node (DagForest *forest,void * fob);
123 DagNode * dag_get_node (DagForest *forest,void * fob);
124 DagNode * dag_get_sub_node (DagForest *forest,void * fob);
125 void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, short rel, const char *name);
126
127 void graph_bfs(void);
128
129 DagNodeQueue * graph_dfs(void);
130
131 void set_node_xy(DagNode *node, float x, float y);
132 void graph_print_queue(DagNodeQueue *nqueue);
133 void graph_print_queue_dist(DagNodeQueue *nqueue);
134 void graph_print_adj_list(void);
135
136 int build_deps(short mask);
137
138 #endif