depsgraph_private.h

Go to the documentation of this file.

/*
 * ***** BEGIN GPL 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.
 *
 * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 * The Original Code is Copyright (C) 2004 Blender Foundation.
 * All rights reserved.
 *
 * Contributor(s): none yet.
 *
 * ***** END GPL LICENSE BLOCK *****
 */

#ifndef DEPSGRAPH_PRIVATE
#define DEPSGRAPH_PRIVATE

#include "BKE_depsgraph.h"
#include "DNA_constraint_types.h"
#include "BKE_constraint.h"


#define DEPSX   5.0f
#define DEPSY   1.8f

#define DAGQUEUEALLOC 50

enum {
    DAG_WHITE = 0,
    DAG_GRAY = 1,
    DAG_BLACK = 2
};



typedef struct DagAdjList
{
    struct DagNode *node;
    short type;
    int count;          // number of identical arcs
    unsigned int lay;   // for flushing redraw/rebuild events
    const char *name;
    struct DagAdjList *next;
} DagAdjList;


typedef struct DagNode 
{
    int color;
    short type;
    float x, y, k;  
    void * ob;
    void * first_ancestor;
    int ancestor_count;
    unsigned int lay;               // accumulated layers of its relations + itself
    unsigned int scelay;            // layers due to being in scene
    uint64_t customdata_mask;   // customdata mask
    int lasttime;       // if lasttime != DagForest->time, this node was not evaluated yet for flushing
    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 DagAdjList *parent;
    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;
    struct GHash *nodeHash;
    int numNodes;
    int is_acyclic;
    int time;       // for flushing/tagging, compare with node->lasttime
} 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, short rel, const char *name);

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