diff options
author | Ton Roosendaal <ton@blender.org> | 2005-05-01 01:27:05 +0400 |
---|---|---|
committer | Ton Roosendaal <ton@blender.org> | 2005-05-01 01:27:05 +0400 |
commit | 79e333343b2aacd17126a4b2d7415ecda0977b05 (patch) | |
tree | 69d7f15aec8fb9744aa5c749518148b4a9c7e2ba /source/blender/blenkernel/depsgraph_private.h | |
parent | 42ae9128fab8e6ec294c16cb2ce4eedcde9c4aed (diff) |
Dependency graph patch, provided by Jean-Luc Peuriere.
Works like a charm... well it now replaces the old base-sorting hack. :)
Next stage will be to define how to further integrate it. Plus some
minor code cleanups... static/internal functions versus external, etc.
Diffstat (limited to 'source/blender/blenkernel/depsgraph_private.h')
-rw-r--r-- | source/blender/blenkernel/depsgraph_private.h | 129 |
1 files changed, 129 insertions, 0 deletions
diff --git a/source/blender/blenkernel/depsgraph_private.h b/source/blender/blenkernel/depsgraph_private.h new file mode 100644 index 00000000000..7b3da76c652 --- /dev/null +++ b/source/blender/blenkernel/depsgraph_private.h @@ -0,0 +1,129 @@ +/** + * $Id$ + * + * ***** BEGIN GPL/BL DUAL 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. The Blender + * Foundation also sells licenses for use in proprietary software under + * the Blender License. See http://www.blender.org/BL/ for information + * about this. + * + * 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + * + * The Original Code is Copyright (C) 2004 Blender Foundation. + * All rights reserved. + * + * Contributor(s): none yet. + * + * ***** END GPL/BL DUAL LICENSE BLOCK ***** + */ +#ifndef DEPSGRAPH_PRIVATE +#define DEPSGRAPH_PRIVATE + +#include "BKE_depsgraph.h" +#include "DNA_constraint_types.h" +#include "BKE_constraint.h" + + +#define DEPSX 5.0 +#define DEPSY 1.8 + +#define DAGQUEUEALLOC 50 + +enum { + DAG_WHITE = 0, + DAG_GRAY = 1, + DAG_BLACK = 2 +}; + + + +typedef struct DagAdjList +{ + struct DagNode *node; + dag_rel_type type; + int count; // number of identical arcs + struct DagAdjList *next; +} DagAdjList; + + +typedef struct DagNode +{ + int color; + short type; + float x, y, k; + void * ob; + void * first_ancestor; + int ancestor_count; + 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 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; + int numNodes; + int is_acyclic; +} 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, dag_rel_type rel); + +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 +
\ No newline at end of file |