← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/blender/gutsy-security

« back to all changes in this revision

Viewing changes to source/blender/blenkernel/intern/depsgraph.c

  • Committer: Bazaar Package Importer
  • Author(s): Florian Ernst
  • Date: 2005-11-06 12:40:03 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20051106124003-3pgs7tcg5rox96xg
Tags: 2.37a-1.1
http://bugs.debian.org/333958
* Non-maintainer upload.
* Split out parts of 01_SConstruct_debian.dpatch again: root_build_dir
  really needs to get adjusted before the clean target runs - closes: #333958,
  see #288882 for reference

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/blender/blenkernel/intern/depsgraph.c
 
1
/**
 
2
 * $Id: depsgraph.c,v 1.2 2005/05/21 21:52:58 lukep Exp $
 
3
 *
 
4
 * ***** BEGIN GPL/BL DUAL 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. The Blender
 
10
 * Foundation also sells licenses for use in proprietary software under
 
11
 * the Blender License.  See http://www.blender.org/BL/ for information
 
12
 * about this.
 
13
 *
 
14
 * This program is distributed in the hope that it will be useful,
 
15
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
16
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
17
 * GNU General Public License for more details.
 
18
 *
 
19
 * You should have received a copy of the GNU General Public License
 
20
 * along with this program; if not, write to the Free Software Foundation,
 
21
 * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 
22
 *
 
23
 * The Original Code is Copyright (C) 2004 Blender Foundation.
 
24
 * All rights reserved.
 
25
 *
 
26
 * Contributor(s): none yet.
 
27
 *
 
28
 * ***** END GPL/BL DUAL LICENSE BLOCK *****
 
29
 */
 
30
 
 
31
#include <stdio.h>
 
32
#include <string.h>
 
33
#include <math.h>
 
34
 
 
35
#ifdef _WIN32
 
36
#include "BLI_winstuff.h"
 
37
#endif
 
38
 
 
39
//#include "BMF_Api.h"
 
40
 
 
41
#include "BLI_blenlib.h"
 
42
#include "BLI_arithb.h"
 
43
 
 
44
#include "DNA_ID.h"
 
45
#include "DNA_object_types.h"
 
46
#include "DNA_oops_types.h"
 
47
#include "DNA_scene_types.h"
 
48
#include "DNA_action_types.h"
 
49
#include "DNA_screen_types.h"
 
50
#include "DNA_space_types.h"
 
51
#include "DNA_view2d_types.h"
 
52
 
 
53
#include "BKE_utildefines.h"
 
54
#include "BKE_global.h"
 
55
 
 
56
#include "MEM_guardedalloc.h"
 
57
#include "blendef.h"
 
58
 
 
59
 
 
60
 #include "depsgraph_private.h"
 
61
 
 
62
/* Queue and stack operations for dag traversal 
 
63
 *
 
64
 * the queue store a list of freenodes to avoid successives alloc/dealloc
 
65
 */
 
66
 
 
67
DagNodeQueue * queue_create (int slots) 
 
68
{
 
69
        DagNodeQueue * queue;
 
70
        DagNodeQueueElem * elem;
 
71
        int i;
 
72
        
 
73
        queue = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
 
74
        queue->freenodes = MEM_mallocN(sizeof(DagNodeQueue),"DAG queue");
 
75
        queue->count = 0;
 
76
        queue->maxlevel = 0;
 
77
        queue->first = queue->last = NULL;
 
78
        elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem3");
 
79
        elem->node = NULL;
 
80
        elem->next = NULL;
 
81
        queue->freenodes->first = queue->freenodes->last = elem;
 
82
        
 
83
        for (i = 1; i <slots;i++) {
 
84
                elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem4");
 
85
                elem->node = NULL;
 
86
                elem->next = NULL;
 
87
                queue->freenodes->last->next = elem;
 
88
                queue->freenodes->last = elem;
 
89
        }
 
90
        queue->freenodes->count = slots;
 
91
        return queue;
 
92
}
 
93
 
 
94
void queue_raz(DagNodeQueue *queue)
 
95
{
 
96
        DagNodeQueueElem * elem;
 
97
        
 
98
        elem = queue->first;
 
99
        if (queue->freenodes->last)
 
100
                queue->freenodes->last->next = elem;
 
101
        else
 
102
                queue->freenodes->first = queue->freenodes->last = elem;
 
103
        
 
104
        elem->node = NULL;
 
105
        queue->freenodes->count++;
 
106
        while (elem->next) {
 
107
                elem = elem->next;
 
108
                elem->node = NULL;
 
109
                queue->freenodes->count++;
 
110
        }
 
111
        queue->freenodes->last = elem;
 
112
        queue->count = 0;
 
113
}
 
114
 
 
115
void queue_delete(DagNodeQueue *queue)
 
116
{
 
117
        DagNodeQueueElem * elem;
 
118
        DagNodeQueueElem * temp;
 
119
        
 
120
        elem = queue->first;
 
121
        while (elem) {
 
122
                temp = elem;
 
123
                elem = elem->next;
 
124
                MEM_freeN(temp);
 
125
        }
 
126
        
 
127
        elem = queue->freenodes->first;
 
128
        while (elem) {
 
129
                temp = elem;
 
130
                elem = elem->next;
 
131
                MEM_freeN(temp);
 
132
        }
 
133
        
 
134
        MEM_freeN(queue->freenodes);                    
 
135
        MEM_freeN(queue);                       
 
136
}
 
137
 
 
138
/* insert in queue, remove in front */
 
139
void push_queue(DagNodeQueue *queue, DagNode *node)
 
140
{
 
141
        DagNodeQueueElem * elem;
 
142
        int i;
 
143
 
 
144
        if (node == NULL) {
 
145
                fprintf(stderr,"pushing null node \n");
 
146
                return;
 
147
        }
 
148
        /*fprintf(stderr,"BFS push : %s %d\n",((ID *) node->ob)->name, queue->count);*/
 
149
 
 
150
        elem = queue->freenodes->first;
 
151
        if (elem != NULL) {
 
152
                queue->freenodes->first = elem->next;
 
153
                if ( queue->freenodes->last == elem) {
 
154
                        queue->freenodes->last = NULL;
 
155
                        queue->freenodes->first = NULL;
 
156
                }
 
157
                queue->freenodes->count--;
 
158
        } else { /* alllocating more */         
 
159
                elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
 
160
                elem->node = NULL;
 
161
                elem->next = NULL;
 
162
                queue->freenodes->first = queue->freenodes->last = elem;
 
163
 
 
164
                for (i = 1; i <DAGQUEUEALLOC;i++) {
 
165
                        elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
 
166
                        elem->node = NULL;
 
167
                        elem->next = NULL;
 
168
                        queue->freenodes->last->next = elem;
 
169
                        queue->freenodes->last = elem;
 
170
                }
 
171
                queue->freenodes->count = DAGQUEUEALLOC;
 
172
                        
 
173
                elem = queue->freenodes->first; 
 
174
                queue->freenodes->first = elem->next;   
 
175
        }
 
176
        elem->next = NULL;
 
177
        elem->node = node;
 
178
        if (queue->last != NULL)
 
179
                queue->last->next = elem;
 
180
        queue->last = elem;
 
181
        if (queue->first == NULL) {
 
182
                queue->first = elem;
 
183
        }
 
184
        queue->count++;
 
185
}
 
186
 
 
187
 
 
188
/* insert in front, remove in front */
 
189
void push_stack(DagNodeQueue *queue, DagNode *node)
 
190
{
 
191
        DagNodeQueueElem * elem;
 
192
        int i;
 
193
 
 
194
        elem = queue->freenodes->first; 
 
195
        if (elem != NULL) {
 
196
                queue->freenodes->first = elem->next;
 
197
                if ( queue->freenodes->last == elem) {
 
198
                        queue->freenodes->last = NULL;
 
199
                        queue->freenodes->first = NULL;
 
200
                }
 
201
                queue->freenodes->count--;
 
202
        } else { /* alllocating more */
 
203
                elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem1");
 
204
                elem->node = NULL;
 
205
                elem->next = NULL;
 
206
                queue->freenodes->first = queue->freenodes->last = elem;
 
207
 
 
208
                for (i = 1; i <DAGQUEUEALLOC;i++) {
 
209
                        elem = MEM_mallocN(sizeof(DagNodeQueueElem),"DAG queue elem2");
 
210
                        elem->node = NULL;
 
211
                        elem->next = NULL;
 
212
                        queue->freenodes->last->next = elem;
 
213
                        queue->freenodes->last = elem;
 
214
                }
 
215
                queue->freenodes->count = DAGQUEUEALLOC;
 
216
                        
 
217
                elem = queue->freenodes->first; 
 
218
                queue->freenodes->first = elem->next;   
 
219
        }
 
220
        elem->next = queue->first;
 
221
        elem->node = node;
 
222
        queue->first = elem;
 
223
        if (queue->last == NULL)
 
224
                queue->last = elem;
 
225
        queue->count++;
 
226
}
 
227
 
 
228
 
 
229
DagNode * pop_queue(DagNodeQueue *queue)
 
230
{
 
231
        DagNodeQueueElem * elem;
 
232
        DagNode *node;
 
233
 
 
234
        elem = queue->first;
 
235
        if (elem) {
 
236
                queue->first = elem->next;
 
237
                if (queue->last == elem) {
 
238
                        queue->last=NULL;
 
239
                        queue->first=NULL;
 
240
                }
 
241
                queue->count--;
 
242
                if (queue->freenodes->last)
 
243
                        queue->freenodes->last->next=elem;
 
244
                queue->freenodes->last=elem;
 
245
                if (queue->freenodes->first == NULL)
 
246
                        queue->freenodes->first=elem;
 
247
                node = elem->node;
 
248
                elem->node = NULL;
 
249
                elem->next = NULL;
 
250
                queue->freenodes->count++;
 
251
                return node;
 
252
        } else {
 
253
                fprintf(stderr,"return null \n");
 
254
                return NULL;
 
255
        }
 
256
}
 
257
 
 
258
void    *pop_ob_queue(struct DagNodeQueue *queue) {
 
259
        return(pop_queue(queue)->ob);
 
260
}
 
261
 
 
262
DagNode * get_top_node_queue(DagNodeQueue *queue) 
 
263
{
 
264
        return queue->first->node;
 
265
}
 
266
 
 
267
int             queue_count(struct DagNodeQueue *queue){
 
268
        return queue->count;
 
269
}
 
270
 
 
271
 
 
272
DagForest * dag_init()
 
273
{
 
274
        DagForest *forest;
 
275
        
 
276
        forest = MEM_mallocN(sizeof(DagForest),"DAG root");
 
277
        forest->DagNode.first = NULL;
 
278
        forest->DagNode.last = NULL;
 
279
        forest->numNodes = 0;
 
280
        return forest;
 
281
}
 
282
 
 
283
struct DagForest        *build_dag(struct Scene *sce, short mask) 
 
284
{
 
285
        Base *base;
 
286
        Object *ob;
 
287
        DagNode * node;
 
288
        DagNode * node2;
 
289
        DagNode * node3;
 
290
        DagNode * scenenode;
 
291
        DagForest *dag;
 
292
 
 
293
        dag = sce->theDag;
 
294
        sce->dagisvalid=1;
 
295
        if ( dag)
 
296
                free_forest( dag ); 
 
297
        else {
 
298
                dag = dag_init();
 
299
                sce->theDag = dag;
 
300
        }
 
301
        
 
302
        // add base node for scene. scene is always the first node in DAG
 
303
        scenenode = dag_add_node(dag, sce);     
 
304
        
 
305
        /* targets in object struct yet to be added. should even they ?
 
306
                struct Ipo *ipo;
 
307
        ListBase nlastrips;
 
308
        ListBase hooks;
 
309
        */
 
310
        
 
311
        
 
312
        base = sce->base.first;
 
313
        while(base) { // add all objects in any case
 
314
                int addtoroot = 1;
 
315
                ob= (Object *) base->object;
 
316
                
 
317
                node = dag_get_node(dag,ob);
 
318
                
 
319
                if ((ob->data) && (mask&DAG_RL_DATA_MASK)) {
 
320
                        node2 = dag_get_node(dag,ob->data);
 
321
                        dag_add_relation(dag,node,node2,DAG_RL_DATA);
 
322
                        node2->first_ancestor = ob;
 
323
                        node2->ancestor_count += 1;
 
324
                        
 
325
                        if ((ob->type == OB_ARMATURE) && (mask&DAG_RL_DATA_CONSTRAINT_MASK)) { // add armature constraints to datas
 
326
                                if (ob->pose){
 
327
                                        bPoseChannel *pchan;
 
328
                                        bConstraint *con;
 
329
                                        Object * target;
 
330
                                        
 
331
                                        for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){
 
332
                                                for (con = pchan->constraints.first; con; con=con->next){
 
333
                                                        if (constraint_has_target(con)) {
 
334
                                                                target = get_constraint_target(con);
 
335
                                                                if (strcmp(target->id.name, ob->id.name) != 0) {
 
336
                                                                        //fprintf(stderr,"armature target :%s \n", target->id.name);
 
337
                                                                        node3 = dag_get_node(dag,target);
 
338
                                                                        dag_add_relation(dag,node3,node2,DAG_RL_CONSTRAINT);
 
339
                                                                }
 
340
                                                        }
 
341
                                                }
 
342
                                        }
 
343
                                }
 
344
                        }
 
345
                        
 
346
                        if ((ob->hooks.first) && (mask&DAG_RL_HOOK)) {
 
347
                                ObHook *hook;
 
348
                                
 
349
                                for(hook= ob->hooks.first; hook; hook= hook->next) {
 
350
                                        if(hook->parent) {
 
351
                                                node3 = dag_get_node(dag,hook->parent);
 
352
                                                dag_add_relation(dag,node3,node2,DAG_RL_HOOK);
 
353
                                        }
 
354
                                }
 
355
                        }
 
356
                } else { // add armature constraints to object itself
 
357
                        if ((ob->type == OB_ARMATURE) && (mask&DAG_RL_DATA_CONSTRAINT_MASK)) {
 
358
                                if (ob->pose){
 
359
                                        bPoseChannel *pchan;
 
360
                                        bConstraint *con;
 
361
                                        Object * target;
 
362
                                        
 
363
                                        for (pchan = ob->pose->chanbase.first; pchan; pchan=pchan->next){
 
364
                                                for (con = pchan->constraints.first; con; con=con->next){
 
365
                                                        if (constraint_has_target(con)) {
 
366
                                                                target = get_constraint_target(con);
 
367
                                                                if (strcmp(target->id.name, ob->id.name) != 0) {
 
368
                                                                        //fprintf(stderr,"armature target :%s \n", target->id.name);
 
369
                                                                        node3 = dag_get_node(dag,target);
 
370
                                                                        dag_add_relation(dag,node3,node,DAG_RL_CONSTRAINT);
 
371
                                                                }
 
372
                                                        }
 
373
                                                }
 
374
                                        }
 
375
                                }
 
376
                        }
 
377
                        if ((ob->hooks.first)  && (mask&DAG_RL_HOOK)) {
 
378
                                ObHook *hook;
 
379
                                
 
380
                                for(hook= ob->hooks.first; hook; hook= hook->next) {
 
381
                                        if(hook->parent) {
 
382
                                                node3 = dag_get_node(dag,hook->parent);
 
383
                                                dag_add_relation(dag,node3,node,DAG_RL_HOOK);
 
384
                                        }
 
385
                                }
 
386
                        }                       
 
387
                }
 
388
                
 
389
                if ((ob->parent) && (mask&DAG_RL_PARENT_MASK)){
 
390
                        node2 = dag_get_node(dag,ob->parent);
 
391
                        dag_add_relation(dag,node2,node,DAG_RL_PARENT);
 
392
                        addtoroot = 0;
 
393
                }
 
394
                if ((ob->track) && (mask&DAG_RL_TRACK_MASK)){
 
395
                        node2 = dag_get_node(dag,ob->track);
 
396
                        dag_add_relation(dag,node2,node,DAG_RL_TRACK);
 
397
                        addtoroot = 0;
 
398
                        
 
399
                }
 
400
                if ((ob->path) && (mask&DAG_RL_PATH_MASK)){
 
401
                        node2 = dag_get_node(dag,ob->track);
 
402
                        dag_add_relation(dag,node2,node,DAG_RL_PATH);
 
403
                        addtoroot = 0;
 
404
                        
 
405
                }
 
406
                
 
407
                /* Count constraints */
 
408
                if (mask & DAG_RL_CONSTRAINT_MASK) {
 
409
                        bConstraint *con;
 
410
                        for (con = ob->constraints.first; con; con=con->next){
 
411
                                if (constraint_has_target(con)) {
 
412
                                        node2 = dag_get_node(dag,get_constraint_target(con));
 
413
                                        dag_add_relation(dag,node2,node,DAG_RL_CONSTRAINT);
 
414
                                        addtoroot = 0;
 
415
                                        
 
416
                                }
 
417
                        }
 
418
                }       
 
419
                
 
420
                
 
421
                if (addtoroot == 1 )
 
422
                        dag_add_relation(dag,scenenode,node,DAG_RL_SCENE);
 
423
                
 
424
                addtoroot = 1;
 
425
                base= base->next;
 
426
        }
 
427
        
 
428
        // cycle detection and solving
 
429
        // solve_cycles(dag);   
 
430
        
 
431
        return dag;
 
432
}
 
433
 
 
434
 
 
435
void free_forest(DagForest *Dag) 
 
436
{  /* remove all nodes and deps */
 
437
        DagNode *tempN;
 
438
        DagAdjList *tempA;      
 
439
        DagAdjList *itA;
 
440
        DagNode *itN = Dag->DagNode.first;
 
441
        
 
442
        while (itN) {
 
443
                itA = itN->child;       
 
444
                while (itA) {
 
445
                        tempA = itA;
 
446
                        itA = itA->next;
 
447
                        MEM_freeN(tempA);                       
 
448
                }
 
449
                tempN = itN;
 
450
                itN = itN->next;
 
451
                MEM_freeN(tempN);
 
452
        }
 
453
        Dag->DagNode.first = NULL;
 
454
        Dag->DagNode.last = NULL;
 
455
        Dag->numNodes = 0;
 
456
 
 
457
}
 
458
 
 
459
DagNode * dag_find_node (DagForest *forest,void * fob)
 
460
{
 
461
                DagNode *node = forest->DagNode.first;
 
462
                
 
463
                while (node) {
 
464
                        if (node->ob == fob)
 
465
                                return node;
 
466
                        node = node->next;
 
467
                }
 
468
                return NULL;
 
469
}
 
470
 
 
471
/* no checking of existance, use dag_find_node first or dag_get_node */
 
472
DagNode * dag_add_node (DagForest *forest,void * fob)
 
473
{
 
474
        DagNode *node;
 
475
                
 
476
        node = MEM_mallocN(sizeof(DagNode),"DAG node");
 
477
        if (node) {
 
478
                node->ob = fob;
 
479
                node->color = DAG_WHITE;
 
480
                node->BFS_dist = 0;             
 
481
                node->DFS_dist = 0;             
 
482
                node->DFS_dvtm = 0;             
 
483
                node->DFS_fntm = 0;
 
484
                node->child = NULL;
 
485
                node->next = NULL;
 
486
                node->first_ancestor = NULL;
 
487
                node->ancestor_count = 0;
 
488
 
 
489
                node->type = GS(((ID *) fob)->name);
 
490
                if (forest->numNodes) {
 
491
                        ((DagNode *) forest->DagNode.last)->next = node;
 
492
                        forest->DagNode.last = node;
 
493
                        forest->numNodes++;
 
494
                } else {
 
495
                        forest->DagNode.last = node;
 
496
                        forest->DagNode.first = node;
 
497
                        forest->numNodes = 1;
 
498
                }
 
499
        }
 
500
        return node;
 
501
}
 
502
 
 
503
DagNode * dag_get_node (DagForest *forest,void * fob)
 
504
{
 
505
        DagNode *node;
 
506
        
 
507
        node = dag_find_node (forest, fob);     
 
508
        if (!node) 
 
509
                node = dag_add_node(forest, fob);
 
510
        return node;
 
511
}
 
512
 
 
513
 
 
514
 
 
515
DagNode * dag_get_sub_node (DagForest *forest,void * fob)
 
516
{
 
517
        DagNode *node;
 
518
        DagAdjList *mainchild, *prev=NULL;
 
519
        
 
520
        mainchild = ((DagNode *) forest->DagNode.first)->child;
 
521
        /* remove from first node (scene) adj list if present */
 
522
        while (mainchild) {
 
523
                if (mainchild->node == fob) {
 
524
                        if (prev) {
 
525
                                prev->next = mainchild->next;
 
526
                                MEM_freeN(mainchild);
 
527
                                break;
 
528
                        } else {
 
529
                                ((DagNode *) forest->DagNode.first)->child = mainchild->next;
 
530
                                MEM_freeN(mainchild);
 
531
                                break;
 
532
                        }
 
533
                }
 
534
                prev = mainchild;
 
535
                mainchild = mainchild->next;
 
536
        }
 
537
        node = dag_find_node (forest, fob);     
 
538
        if (!node) 
 
539
                node = dag_add_node(forest, fob);
 
540
        return node;
 
541
}
 
542
 
 
543
void dag_add_relation(DagForest *forest, DagNode *fob1, DagNode *fob2, dag_rel_type rel) 
 
544
{
 
545
        DagAdjList *itA = fob1->child;
 
546
        
 
547
        while (itA) { /* search if relation exist already */
 
548
                if (itA->node == fob2) {
 
549
                        if (itA->type == rel) { 
 
550
                                itA->count += 1;
 
551
                                return;
 
552
                        }
 
553
                }
 
554
                itA = itA->next;
 
555
        }
 
556
        /* create new relation and insert at head */
 
557
        itA = MEM_mallocN(sizeof(DagAdjList),"DAG adj list");
 
558
        itA->node = fob2;
 
559
        itA->type = rel;
 
560
        itA->count = 1;
 
561
        itA->next = fob1->child;
 
562
        fob1->child = itA;
 
563
}
 
564
 
 
565
 
 
566
/*
 
567
 * MainDAG is the DAG of all objects in current scene
 
568
 * used only for drawing there is one also in each scene
 
569
 */
 
570
static DagForest * MainDag = NULL;
 
571
 
 
572
DagForest *getMainDag(void)
 
573
{
 
574
        return MainDag;
 
575
}
 
576
 
 
577
 
 
578
void setMainDag(DagForest *dag)
 
579
{
 
580
        MainDag = dag;
 
581
}
 
582
 
 
583
 
 
584
/*
 
585
 * note for BFS/DFS
 
586
 * in theory we should sweep the whole array
 
587
 * but in our case the first node is the scene
 
588
 * and is linked to every other object
 
589
 *
 
590
 * for general case we will need to add outer loop
 
591
 */
 
592
 
 
593
/*
 
594
 * ToDo : change pos kludge
 
595
 */
 
596
 
 
597
/* adjust levels for drawing in oops space */
 
598
void graph_bfs(void)
 
599
{
 
600
        DagNode *node;
 
601
        DagNodeQueue *nqueue;
 
602
        int pos[50];
 
603
        int i;
 
604
        DagAdjList *itA;
 
605
        int minheight;
 
606
        
 
607
        /* fprintf(stderr,"starting BFS \n ------------\n"); */ 
 
608
        nqueue = queue_create(DAGQUEUEALLOC);
 
609
        for ( i=0; i<50; i++)
 
610
                pos[i] = 0;
 
611
        
 
612
        /* Init
 
613
         * dagnode.first is alway the root (scene) 
 
614
         */
 
615
        node = MainDag->DagNode.first;
 
616
        while(node) {
 
617
                node->color = DAG_WHITE;
 
618
                node->BFS_dist = 9999;
 
619
                node->k = 0;
 
620
                node = node->next;
 
621
        }
 
622
        
 
623
        node = MainDag->DagNode.first;
 
624
        if (node->color == DAG_WHITE) {
 
625
                node->color = DAG_GRAY;
 
626
                node->BFS_dist = 1;
 
627
                push_queue(nqueue,node);  
 
628
                while(nqueue->count) {
 
629
                        node = pop_queue(nqueue);
 
630
                        
 
631
                        minheight = pos[node->BFS_dist];
 
632
                        itA = node->child;
 
633
                        while(itA != NULL) {
 
634
                                if((itA->node->color == DAG_WHITE) ) {
 
635
                                        itA->node->color = DAG_GRAY;
 
636
                                        itA->node->BFS_dist = node->BFS_dist + 1;
 
637
                                        itA->node->k = minheight;
 
638
                                        push_queue(nqueue,itA->node);
 
639
                                }
 
640
                                
 
641
                                 else {
 
642
                                        fprintf(stderr,"bfs not dag tree edge color :%i \n",itA->node->color);
 
643
                                }
 
644
                                 
 
645
                                
 
646
                                itA = itA->next;
 
647
                        }
 
648
                        if (pos[node->BFS_dist] > node->k ) {
 
649
                                pos[node->BFS_dist] += 1;                               
 
650
                                node->k = pos[node->BFS_dist];
 
651
                        } else {
 
652
                                pos[node->BFS_dist] = node->k +1;
 
653
                        }
 
654
                        set_node_xy(node, DEPSX*2*node->BFS_dist, pos[node->BFS_dist]*DEPSY*2);
 
655
                        node->color = DAG_BLACK;
 
656
                        /*
 
657
                         fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);   
 
658
                         */
 
659
                }
 
660
        }
 
661
        queue_delete(nqueue);
 
662
}
 
663
 
 
664
int pre_and_post_BFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
 
665
        DagNode *node;
 
666
        
 
667
        node = dag->DagNode.first;
 
668
        return pre_and_post_source_BFS(dag, mask,  node,  pre_func,  post_func, data);
 
669
}
 
670
 
 
671
 
 
672
int pre_and_post_source_BFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
 
673
{
 
674
        DagNode *node;
 
675
        DagNodeQueue *nqueue;
 
676
        DagAdjList *itA;
 
677
        int     retval = 0;
 
678
        /* fprintf(stderr,"starting BFS \n ------------\n"); */ 
 
679
        
 
680
        /* Init
 
681
                * dagnode.first is alway the root (scene) 
 
682
                */
 
683
        node = dag->DagNode.first;
 
684
        nqueue = queue_create(DAGQUEUEALLOC);
 
685
        while(node) {
 
686
                node->color = DAG_WHITE;
 
687
                node->BFS_dist = 9999;
 
688
                node = node->next;
 
689
        }
 
690
        
 
691
        node = source;
 
692
        if (node->color == DAG_WHITE) {
 
693
                node->color = DAG_GRAY;
 
694
                node->BFS_dist = 1;
 
695
                pre_func(node->ob,data);
 
696
                
 
697
                while(nqueue->count) {
 
698
                        node = pop_queue(nqueue);
 
699
                        
 
700
                        itA = node->child;
 
701
                        while(itA != NULL) {
 
702
                                if((itA->node->color == DAG_WHITE) && (itA->type & mask)) {
 
703
                                        itA->node->color = DAG_GRAY;
 
704
                                        itA->node->BFS_dist = node->BFS_dist + 1;
 
705
                                        push_queue(nqueue,itA->node);
 
706
                                        pre_func(node->ob,data);
 
707
                                }
 
708
                                
 
709
                                else { // back or cross edge
 
710
                                        retval = 1;
 
711
                                }
 
712
                                itA = itA->next;
 
713
                        }
 
714
                        post_func(node->ob,data);
 
715
                        node->color = DAG_BLACK;
 
716
                        /*
 
717
                         fprintf(stderr,"BFS node : %20s %i %5.0f %5.0f\n",((ID *) node->ob)->name,node->BFS_dist, node->x, node->y);   
 
718
                         */
 
719
                }
 
720
        }
 
721
        queue_delete(nqueue);
 
722
        return retval;
 
723
}
 
724
 
 
725
/* non recursive version of DFS, return queue -- outer loop present to catch odd cases (first level cycles)*/
 
726
DagNodeQueue * graph_dfs(void)
 
727
{
 
728
        DagNode *node;
 
729
        DagNodeQueue *nqueue;
 
730
        DagNodeQueue *retqueue;
 
731
        int pos[50];
 
732
        int i;
 
733
        DagAdjList *itA;
 
734
        int time;
 
735
        int skip = 0;
 
736
        int minheight;
 
737
        int maxpos=0;
 
738
        int     is_cycle = 0;
 
739
        /*
 
740
         *fprintf(stderr,"starting DFS \n ------------\n");
 
741
         */     
 
742
        nqueue = queue_create(DAGQUEUEALLOC);
 
743
        retqueue = queue_create(MainDag->numNodes);
 
744
        for ( i=0; i<50; i++)
 
745
                pos[i] = 0;
 
746
        
 
747
        /* Init
 
748
         * dagnode.first is alway the root (scene) 
 
749
         */
 
750
        node = MainDag->DagNode.first;
 
751
        while(node) {
 
752
                node->color = DAG_WHITE;
 
753
                node->DFS_dist = 9999;
 
754
                node->DFS_dvtm = node->DFS_fntm = 9999;
 
755
                node->k = 0;
 
756
                node =  node->next;
 
757
        }
 
758
        
 
759
        time = 1;
 
760
        
 
761
        node = MainDag->DagNode.first;
 
762
 
 
763
        do {
 
764
        if (node->color == DAG_WHITE) {
 
765
                node->color = DAG_GRAY;
 
766
                node->DFS_dist = 1;
 
767
                node->DFS_dvtm = time;
 
768
                time++;
 
769
                push_stack(nqueue,node);  
 
770
                        
 
771
                while(nqueue->count) {
 
772
                        //graph_print_queue(nqueue);
 
773
 
 
774
                         skip = 0;
 
775
                        node = get_top_node_queue(nqueue);
 
776
                        
 
777
                        minheight = pos[node->DFS_dist];
 
778
 
 
779
                        itA = node->child;
 
780
                        while(itA != NULL) {
 
781
                                if((itA->node->color == DAG_WHITE) ) {
 
782
                                        itA->node->DFS_dvtm = time;
 
783
                                        itA->node->color = DAG_GRAY;
 
784
 
 
785
                                        time++;
 
786
                                        itA->node->DFS_dist = node->DFS_dist + 1;
 
787
                                        itA->node->k = minheight;
 
788
                                        push_stack(nqueue,itA->node);
 
789
                                        skip = 1;
 
790
                                        break;
 
791
                                } else { 
 
792
                                        if (itA->node->color == DAG_GRAY) { // back edge
 
793
                                                fprintf(stderr,"dfs back edge :%15s %15s \n",((ID *) node->ob)->name, ((ID *) itA->node->ob)->name);
 
794
                                                is_cycle = 1;
 
795
                                        } else if (itA->node->color == DAG_BLACK) {
 
796
                                                ;
 
797
                                                /* already processed node but we may want later to change distance either to shorter to longer.
 
798
                                                 * DFS_dist is the first encounter  
 
799
                                                */
 
800
                                                /*if (node->DFS_dist >= itA->node->DFS_dist)
 
801
                                                        itA->node->DFS_dist = node->DFS_dist + 1;
 
802
                                                        
 
803
                                                        fprintf(stderr,"dfs forward or cross edge :%15s %i-%i %15s %i-%i \n",
 
804
                                                                ((ID *) node->ob)->name,
 
805
                                                                node->DFS_dvtm, 
 
806
                                                                node->DFS_fntm, 
 
807
                                                                ((ID *) itA->node->ob)->name, 
 
808
                                                                itA->node->DFS_dvtm,
 
809
                                                                itA->node->DFS_fntm);
 
810
                                        */
 
811
                                        } else 
 
812
                                                fprintf(stderr,"dfs unknown edge \n");
 
813
                                }
 
814
                                itA = itA->next;
 
815
                        }                       
 
816
 
 
817
                        if (!skip) {
 
818
                                node = pop_queue(nqueue);
 
819
                                node->color = DAG_BLACK;
 
820
 
 
821
                                node->DFS_fntm = time;
 
822
                                time++;
 
823
                                if (node->DFS_dist > maxpos)
 
824
                                        maxpos = node->DFS_dist;
 
825
                                if (pos[node->DFS_dist] > node->k ) {
 
826
                                        pos[node->DFS_dist] += 1;                               
 
827
                                        node->k = pos[node->DFS_dist];
 
828
                                } else {
 
829
                                        pos[node->DFS_dist] = node->k +1;
 
830
                                }
 
831
                                set_node_xy(node, DEPSX*2*node->DFS_dist, pos[node->DFS_dist]*DEPSY*2);
 
832
                                
 
833
                                /*
 
834
                                 fprintf(stderr,"DFS node : %20s %i %i %i %i\n",((ID *) node->ob)->name,node->BFS_dist, node->DFS_dist, node->DFS_dvtm, node->DFS_fntm );       
 
835
                                */
 
836
                                 push_stack(retqueue,node);
 
837
                                
 
838
                        }
 
839
                }
 
840
        }
 
841
                node = node->next;
 
842
        } while (node);
 
843
//        fprintf(stderr,"i size : %i \n", maxpos);
 
844
          
 
845
        queue_delete(nqueue);
 
846
          return(retqueue);
 
847
}
 
848
 
 
849
int pre_and_post_DFS(DagForest *dag, short mask, graph_action_func pre_func, graph_action_func post_func, void **data) {
 
850
        DagNode *node;
 
851
 
 
852
        node = dag->DagNode.first;
 
853
        return pre_and_post_source_DFS(dag, mask,  node,  pre_func,  post_func, data);
 
854
}
 
855
 
 
856
int pre_and_post_source_DFS(DagForest *dag, short mask, DagNode *source, graph_action_func pre_func, graph_action_func post_func, void **data)
 
857
{
 
858
        DagNode *node;
 
859
        DagNodeQueue *nqueue;
 
860
        DagAdjList *itA;
 
861
        int time;
 
862
        int skip = 0;
 
863
        int retval = 0;
 
864
        /*
 
865
         *fprintf(stderr,"starting DFS \n ------------\n");
 
866
         */     
 
867
        nqueue = queue_create(DAGQUEUEALLOC);
 
868
        
 
869
        /* Init
 
870
                * dagnode.first is alway the root (scene) 
 
871
                */
 
872
        node = dag->DagNode.first;
 
873
        while(node) {
 
874
                node->color = DAG_WHITE;
 
875
                node->DFS_dist = 9999;
 
876
                node->DFS_dvtm = node->DFS_fntm = 9999;
 
877
                node->k = 0;
 
878
                node =  node->next;
 
879
        }
 
880
        
 
881
        time = 1;
 
882
        
 
883
        node = source;
 
884
        do {
 
885
                if (node->color == DAG_WHITE) {
 
886
                        node->color = DAG_GRAY;
 
887
                        node->DFS_dist = 1;
 
888
                        node->DFS_dvtm = time;
 
889
                        time++;
 
890
                        push_stack(nqueue,node);  
 
891
                        pre_func(node->ob,data);
 
892
 
 
893
                        while(nqueue->count) {
 
894
                                skip = 0;
 
895
                                node = get_top_node_queue(nqueue);
 
896
                                                                
 
897
                                itA = node->child;
 
898
                                while(itA != NULL) {
 
899
                                        if((itA->node->color == DAG_WHITE) && (itA->type & mask) ) {
 
900
                                                itA->node->DFS_dvtm = time;
 
901
                                                itA->node->color = DAG_GRAY;
 
902
                                                
 
903
                                                time++;
 
904
                                                itA->node->DFS_dist = node->DFS_dist + 1;
 
905
                                                push_stack(nqueue,itA->node);
 
906
                                                pre_func(node->ob,data);
 
907
 
 
908
                                                skip = 1;
 
909
                                                break;
 
910
                                        } else {
 
911
                                                if (itA->node->color == DAG_GRAY) {// back edge
 
912
                                                        retval = 1;
 
913
                                                }
 
914
//                                              else if (itA->node->color == DAG_BLACK) { // cross or forward
 
915
//                                                      ;
 
916
                                        }
 
917
                                        itA = itA->next;
 
918
                                }                       
 
919
                                
 
920
                                if (!skip) {
 
921
                                        node = pop_queue(nqueue);
 
922
                                        node->color = DAG_BLACK;
 
923
                                        
 
924
                                        node->DFS_fntm = time;
 
925
                                        time++;
 
926
                                        post_func(node->ob,data);
 
927
                                }
 
928
                        }
 
929
                }
 
930
                node = node->next;
 
931
        } while (node);
 
932
        queue_delete(nqueue);
 
933
        return(retval);
 
934
}
 
935
 
 
936
// sort the base list on place
 
937
void topo_sort_baselist(struct Scene *sce){
 
938
        DagNode *node;
 
939
        DagNodeQueue *nqueue;
 
940
        DagAdjList *itA;
 
941
        int time;
 
942
        int skip = 0;
 
943
        ListBase tempbase;
 
944
        Base *base;
 
945
        
 
946
        tempbase.first= tempbase.last= 0;
 
947
        
 
948
        build_dag(sce,DAG_RL_ALL_BUT_DATA_MASK);
 
949
        
 
950
        nqueue = queue_create(DAGQUEUEALLOC);
 
951
        
 
952
        node = sce->theDag->DagNode.first;
 
953
        while(node) {
 
954
                node->color = DAG_WHITE;
 
955
                node =  node->next;
 
956
        }
 
957
        
 
958
        time = 1;
 
959
        
 
960
        node = sce->theDag->DagNode.first;
 
961
        
 
962
        node->color = DAG_GRAY;
 
963
        time++;
 
964
        push_stack(nqueue,node);  
 
965
        
 
966
        while(nqueue->count) {
 
967
                
 
968
                skip = 0;
 
969
                node = get_top_node_queue(nqueue);
 
970
                
 
971
                itA = node->child;
 
972
                while(itA != NULL) {
 
973
                        if((itA->node->color == DAG_WHITE) ) {
 
974
                                itA->node->DFS_dvtm = time;
 
975
                                itA->node->color = DAG_GRAY;
 
976
                                
 
977
                                time++;
 
978
                                push_stack(nqueue,itA->node);
 
979
                                skip = 1;
 
980
                                break;
 
981
                        } 
 
982
                        itA = itA->next;
 
983
                }                       
 
984
                
 
985
                if (!skip) {
 
986
                        if (node) {
 
987
                                node = pop_queue(nqueue);
 
988
                                if (node->ob == sce)    // we are done
 
989
                                        break ;
 
990
                                node->color = DAG_BLACK;
 
991
                                
 
992
                                time++;
 
993
                                base = sce->base.first;
 
994
                                while (base->object != node->ob)
 
995
                                        base = base->next;
 
996
                                BLI_remlink(&sce->base,base);
 
997
                                BLI_addhead(&tempbase,base);
 
998
                        }       
 
999
                }
 
1000
        }
 
1001
        
 
1002
        // temporal correction for circular dependancies
 
1003
        base = sce->base.first;
 
1004
        while (base) {
 
1005
                BLI_remlink(&sce->base,base);
 
1006
                BLI_addhead(&tempbase,base);
 
1007
                base = sce->base.first;
 
1008
        }
 
1009
        
 
1010
        sce->base = tempbase;
 
1011
        queue_delete(nqueue);
 
1012
}
 
1013
 
 
1014
 
 
1015
// used to get the obs owning a datablock
 
1016
struct DagNodeQueue *get_obparents(struct DagForest     *dag, void *ob) 
 
1017
{
 
1018
        DagNode * node, *node1;
 
1019
        DagNodeQueue *nqueue;
 
1020
        DagAdjList *itA;
 
1021
 
 
1022
        node = dag_find_node(dag,ob);
 
1023
        if (node->ancestor_count == 1) { // simple case
 
1024
                nqueue = queue_create(1);
 
1025
                push_queue(nqueue,node);
 
1026
        } else {        // need to go over the whole dag for adj list
 
1027
                nqueue = queue_create(node->ancestor_count);
 
1028
                
 
1029
                node1 = dag->DagNode.first;
 
1030
                do {
 
1031
                        if (node1->DFS_fntm > node->DFS_fntm) { // a parent is finished after child. must check adj list
 
1032
                                itA = node->child;
 
1033
                                while(itA != NULL) {
 
1034
                                        if ((itA->node == node) && (itA->type == DAG_RL_DATA)) {
 
1035
                                                push_queue(nqueue,node);
 
1036
                                        }
 
1037
                                        itA = itA->next;
 
1038
                                }
 
1039
                        }
 
1040
                        node1 = node1->next;
 
1041
                } while (node1);
 
1042
        }
 
1043
        return nqueue;
 
1044
}
 
1045
 
 
1046
struct DagNodeQueue *get_first_ancestors(struct DagForest       *dag, void *ob)
 
1047
{
 
1048
        DagNode * node, *node1;
 
1049
        DagNodeQueue *nqueue;
 
1050
        DagAdjList *itA;
 
1051
        
 
1052
        node = dag_find_node(dag,ob);
 
1053
        
 
1054
        // need to go over the whole dag for adj list
 
1055
        nqueue = queue_create(node->ancestor_count);
 
1056
        
 
1057
        node1 = dag->DagNode.first;
 
1058
        do {
 
1059
                if (node1->DFS_fntm > node->DFS_fntm) { 
 
1060
                        itA = node->child;
 
1061
                        while(itA != NULL) {
 
1062
                                if (itA->node == node) {
 
1063
                                        push_queue(nqueue,node);
 
1064
                                }
 
1065
                                itA = itA->next;
 
1066
                        }
 
1067
                }
 
1068
                node1 = node1->next;
 
1069
        } while (node1);
 
1070
        
 
1071
        return nqueue;  
 
1072
}
 
1073
 
 
1074
// standard DFS list
 
1075
struct DagNodeQueue *get_all_childs(struct DagForest    *dag, void *ob)
 
1076
{
 
1077
        DagNode *node;
 
1078
        DagNodeQueue *nqueue;
 
1079
        DagNodeQueue *retqueue;
 
1080
        DagAdjList *itA;
 
1081
        int time;
 
1082
        int skip = 0;
 
1083
 
 
1084
        nqueue = queue_create(DAGQUEUEALLOC);
 
1085
        retqueue = queue_create(MainDag->numNodes);
 
1086
        
 
1087
        node = dag->DagNode.first;
 
1088
        while(node) {
 
1089
                node->color = DAG_WHITE;
 
1090
                node =  node->next;
 
1091
        }
 
1092
        
 
1093
        time = 1;
 
1094
        
 
1095
        node = dag_find_node(dag,ob);
 
1096
        
 
1097
        node->color = DAG_GRAY;
 
1098
        time++;
 
1099
        push_stack(nqueue,node);  
 
1100
        
 
1101
        while(nqueue->count) {
 
1102
                
 
1103
                skip = 0;
 
1104
                node = get_top_node_queue(nqueue);
 
1105
                                
 
1106
                itA = node->child;
 
1107
                while(itA != NULL) {
 
1108
                        if((itA->node->color == DAG_WHITE) ) {
 
1109
                                itA->node->DFS_dvtm = time;
 
1110
                                itA->node->color = DAG_GRAY;
 
1111
                                
 
1112
                                time++;
 
1113
                                push_stack(nqueue,itA->node);
 
1114
                                skip = 1;
 
1115
                                break;
 
1116
                        } 
 
1117
                        itA = itA->next;
 
1118
                }                       
 
1119
                
 
1120
                if (!skip) {
 
1121
                        node = pop_queue(nqueue);
 
1122
                        node->color = DAG_BLACK;
 
1123
                        
 
1124
                        time++;
 
1125
                        push_stack(retqueue,node);                      
 
1126
                }
 
1127
        }
 
1128
                
 
1129
        queue_delete(nqueue);
 
1130
        return(retqueue);
 
1131
}
 
1132
 
 
1133
dag_rel_type    are_obs_related(struct DagForest        *dag, void *ob1, void *ob2) {
 
1134
        DagNode * node;
 
1135
        DagAdjList *itA;
 
1136
        
 
1137
        node = dag_find_node(dag,ob1);
 
1138
        
 
1139
        itA = node->child;
 
1140
        while(itA != NULL) {
 
1141
                if((itA->node->ob == ob2) ) {
 
1142
                        return itA->node->type;
 
1143
                } 
 
1144
                itA = itA->next;
 
1145
        }
 
1146
        return DAG_NO_RELATION;
 
1147
}
 
1148
 
 
1149
int     is_acyclic( DagForest   *dag) {
 
1150
        return dag->is_acyclic;
 
1151
}
 
1152
 
 
1153
void set_node_xy(DagNode *node, float x, float y)
 
1154
{
 
1155
        node->x = x;
 
1156
        node->y = y;
 
1157
}
 
1158
 
 
1159
 
 
1160
/* debug test functions */
 
1161
 
 
1162
void graph_print_queue(DagNodeQueue *nqueue)
 
1163
{       
 
1164
        DagNodeQueueElem *queueElem;
 
1165
        
 
1166
        queueElem = nqueue->first;
 
1167
        while(queueElem) {
 
1168
                fprintf(stderr,"** %s %i %i-%i ",((ID *) queueElem->node->ob)->name,queueElem->node->color,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
 
1169
                queueElem = queueElem->next;            
 
1170
        }
 
1171
        fprintf(stderr,"\n");
 
1172
}
 
1173
 
 
1174
void graph_print_queue_dist(DagNodeQueue *nqueue)
 
1175
{       
 
1176
        DagNodeQueueElem *queueElem;
 
1177
        int max, count;
 
1178
        
 
1179
        queueElem = nqueue->first;
 
1180
        max = queueElem->node->DFS_fntm;
 
1181
        count = 0;
 
1182
        while(queueElem) {
 
1183
                fprintf(stderr,"** %25s %2.2i-%2.2i ",((ID *) queueElem->node->ob)->name,queueElem->node->DFS_dvtm,queueElem->node->DFS_fntm);
 
1184
                while (count < queueElem->node->DFS_dvtm-1) { fputc(' ',stderr); count++;}
 
1185
                fputc('|',stderr); 
 
1186
                while (count < queueElem->node->DFS_fntm-2) { fputc('-',stderr); count++;}
 
1187
                fputc('|',stderr);
 
1188
                fputc('\n',stderr);
 
1189
                count = 0;
 
1190
                queueElem = queueElem->next;            
 
1191
        }
 
1192
        fprintf(stderr,"\n");
 
1193
}
 
1194
 
 
1195
void graph_print_adj_list(void)
 
1196
{
 
1197
        DagNode *node;
 
1198
        DagAdjList *itA;
 
1199
        
 
1200
        node = (getMainDag())->DagNode.first;
 
1201
        while(node) {
 
1202
                fprintf(stderr,"node : %s col: %i",((ID *) node->ob)->name, node->color);               
 
1203
                itA = node->child;
 
1204
                while (itA) {
 
1205
                        fprintf(stderr,"-- %s ",((ID *) itA->node->ob)->name);
 
1206
                        
 
1207
                        itA = itA->next;
 
1208
                }
 
1209
                fprintf(stderr,"\n");
 
1210
                node = node->next;
 
1211
        }
 
1212
}
 
1213
 
 
1214