Merging r38694 through r38739 from trunk into vgroup_modifiers
[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         unsigned int customdata_mask;   // customdata mask
75         int lasttime;           // if lasttime != DagForest->time, this node was not evaluated yet for flushing
76         int BFS_dist;           // BFS distance
77         int DFS_dist;           // DFS distance
78         int DFS_dvtm;           // DFS discovery time
79         int DFS_fntm;           // DFS Finishing time
80         struct DagAdjList *child;
81         struct DagAdjList *parent;
82         struct DagNode *next;
83 } DagNode;
84
85 typedef struct DagNodeQueueElem {
86         struct DagNode *node;
87         struct DagNodeQueueElem *next;
88 } DagNodeQueueElem;
89
90 typedef struct DagNodeQueue
91 {
92         DagNodeQueueElem *first;
93         DagNodeQueueElem *last;
94         int count;
95         int maxlevel;
96         struct DagNodeQueue *freenodes;
97 } DagNodeQueue;
98
99 // forest as we may have more than one DAG unnconected
100 typedef struct DagForest 
101 {
102         ListBase DagNode;
103         struct GHash *nodeHash;
104         int numNodes;
105         int is_acyclic;
106         int time;               // for flushing/tagging, compare with node->lasttime
107 } DagForest;
108
109
110 // queue operations
111 DagNodeQueue * queue_create (int slots);
112 void queue_raz(DagNodeQueue *queue);
113 void push_queue(DagNodeQueue *queue, DagNode *node);
114 void push_stack(DagNodeQueue *queue, DagNode *node);
115 DagNode * pop_queue(DagNodeQueue *queue);
116 DagNode * get_top_node_queue(DagNodeQueue *queue);
117
118 // Dag management
119 DagForest *getMainDag(void);
120 void setMainDag(DagForest *dag);
121 DagForest * dag_init(void);
122 DagNode * dag_find_node (DagForest *forest,void * fob);
123 DagNode * dag_add_node (DagForest *forest,void * fob);
124 DagNode * dag_get_node (DagForest *forest,void * fob);
125 DagNode * dag_get_sub_node (DagForest *forest,void * fob);
126 void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, short rel, const char *name);
127
128 void graph_bfs(void);
129
130 DagNodeQueue * graph_dfs(void);
131
132 void set_node_xy(DagNode *node, float x, float y);
133 void graph_print_queue(DagNodeQueue *nqueue);
134 void graph_print_queue_dist(DagNodeQueue *nqueue);
135 void graph_print_adj_list(void);
136
137 int build_deps(short mask);
138
139 #endif