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