1 #ifndef FILE_NODE_H 2 #define FILE_NODE_H 3 4 5 /* **** dependency graph ****** */ 6 7 #include <time.h> 8 #include "tree.h" 9 10 /* */ 11 struct NODELINK 12 { 13 struct NODE *node; 14 struct NODELINK *next; 15 }; 16 17 struct NODETREELINK 18 { 19 struct NODETREELINK *parent; 20 struct NODETREELINK *leafs[2]; 21 struct NODE *node; 22 int depth; 23 }; 24 25 struct SCANNER 26 { 27 struct SCANNER *next; 28 int (*scannerfunc)(struct NODE *, struct SCANNER *info); 29 }; 30 31 #if 0 32 struct JOB 33 { 34 struct GRAPH *graph; /* graph that the job belongs to */ 35 36 char *cmdline; 37 char *label; 38 char *filter; 39 40 unsigned cmdhash; /* hash of the command line for detecting changes */ 41 unsigned cachehash; /* hash that should be written to the cache */ 42 43 struct NODELINK *firstoutput; 44 45 struct NODELINK *constraint_exclusive; /* list of exclusive constraints */ 46 struct NODELINK *constraint_shared; /* list of shared constraints */ 47 48 }; 49 #endif 50 51 /* 52 a node in the dependency graph 53 NOTE: when adding variables to this structure, they will all be set 54 to zero when created by node_create(). 55 TODO: these should be allocated cache aligned, and padded to 128 byte? 56 */ 57 struct NODE 58 { 59 /* *** */ 60 struct GRAPH *graph; /* graph that the node belongs to */ 61 struct NODE *next; /* next node in the graph */ 62 struct NODELINK *firstparent; /* list of parents */ 63 64 struct NODELINK *firstdep; /* list of dependencies */ 65 struct NODETREELINK *deproot; /* tree of dependencies */ 66 67 struct NODELINK *firstjobdep; /* list of job dependencies */ 68 struct NODETREELINK *jobdeproot; /* tree of job dependencies */ 69 70 struct NODELINK *constraint_exclusive; /* list of exclusive constraints */ 71 struct NODELINK *constraint_shared; /* list of shared constraints */ 72 73 char *filename; /* this contains the filename with the FULLPATH */ 74 75 /* either none of these are set or both of em are */ 76 char *cmdline; /* command line that should be executed to build this node */ 77 char *label; /* what to print when we build this node */ 78 79 char *filter; /* filter string, first character sets the type of filter */ 80 81 /* filename and the tool to build the resource */ 82 unsigned cmdhash; /* hash of the command line for detecting changes */ 83 unsigned cachehash; /* hash that should be written to the cache */ 84 85 unsigned constraint_exclusive_count; /* */ 86 unsigned constraint_shared_count; /* */ 87 88 unsigned hashid; /* hash of the filename/nodename */ 89 90 /* time stamps, 0 == does not exist. */ 91 time_t timestamp; /* timestamp. this will be updated from the deps of the node */ 92 time_t timestamp_raw; /* raw timestamp. contains the timestamp on the disc */ 93 94 unsigned id; /* used when doing traversal with marking (bitarray) */ 95 96 unsigned short filename_len; /* length of filename including zero term */ 97 unsigned short depth; /* depth in the graph. used for priority when buliding */ 98 99 /* various flags (4 bytes in the end) */ 100 unsigned dirty:8; /* non-zero if the node has to be rebuilt */ 101 unsigned depchecked:1; /* set if a dependency checker have processed the file */ 102 unsigned counted:1; /* set if we have counted this node towards the number of targets to build */ 103 unsigned targeted:1; /* set if this node is targeted for a build */ 104 unsigned touch:1; /* when built, touch the output file as well */ 105 unsigned cached:1; /* set if the node should be considered as cached */ 106 107 volatile unsigned workstatus:2; /* build status of the node, NODESTATUS_* flags */ 108 }; 109 110 /* cache node */ 111 struct CACHENODE 112 { 113 RB_ENTRY(CACHENODE) rbentry; 114 115 unsigned hashid; 116 time_t timestamp_raw; 117 char *filename; 118 unsigned cmdhash; 119 120 unsigned cached:1; 121 122 unsigned deps_num; 123 unsigned *deps; /* index id, not hashid */ 124 }; 125 126 /* */ 127 struct GRAPH 128 { 129 struct NODETREELINK *nodehash[0x10000]; 130 struct NODE *first; 131 struct NODE *last; 132 struct HEAP *heap; 133 134 /* needed when saving the cache */ 135 int num_nodes; 136 int num_deps; 137 }; 138 139 struct HEAP; 140 struct CONTEXT; 141 142 /* node status */ 143 #define NODESTATUS_UNDONE 0 /* node needs build */ 144 #define NODESTATUS_WORKING 1 /* a thread is working on this node */ 145 #define NODESTATUS_DONE 2 /* node built successfully */ 146 #define NODESTATUS_BROKEN 3 /* node tool reported an error or a dependency is broken */ 147 148 /* node creation error codes */ 149 #define NODECREATE_OK 0 150 #define NODECREATE_EXISTS 1 /* the node already exists */ 151 #define NODECREATE_NOTNICE 2 /* the path is not normalized */ 152 #define NODECREATE_INVALID_ARG 3 /* invalid arguments */ 153 154 /* node walk flags */ 155 #define NODEWALK_FORCE 1 /* skips dirty checks and*/ 156 #define NODEWALK_TOPDOWN 2 /* callbacks are done top down */ 157 #define NODEWALK_BOTTOMUP 4 /* callbacks are done bottom up */ 158 #define NODEWALK_UNDONE 8 /* causes checking of the undone flag, does not decend if it's set */ 159 #define NODEWALK_QUICK 16 /* never visit the same node twice */ 160 #define NODEWALK_JOBS 32 /* walk the jobtree instead of the complete tree */ 161 #define NODEWALK_REVISIT (64|NODEWALK_QUICK) /* will do a quick pass and revisits all nodes thats 162 have been marked by node_walk_revisit(). path info won't be available when revisiting nodes */ 163 164 /* node dirty status */ 165 /* make sure to update node_debug_dump_jobs() when changing these */ 166 #define NODEDIRTY_NOT 0 167 #define NODEDIRTY_MISSING 1 /* the output file is missing */ 168 #define NODEDIRTY_CMDHASH 2 /* the command doesn't match the one in the cache */ 169 #define NODEDIRTY_DEPDIRTY 3 /* one of the dependencies is dirty */ 170 #define NODEDIRTY_DEPNEWER 4 /* one of the dependencies is newer */ 171 #define NODEDIRTY_GLOBALSTAMP 5 /* the globaltimestamp is newer */ 172 173 /* you destroy graphs by destroying the heap */ 174 struct GRAPH *node_create_graph(struct HEAP *heap); 175 176 /* */ 177 int node_create(struct NODE **node, struct GRAPH *graph, const char *filename, const char *label, const char *cmdline); 178 struct NODE *node_find(struct GRAPH *graph, const char *filename); 179 struct NODE *node_find_byhash(struct GRAPH *graph, unsigned int hashid); 180 struct NODE *node_get(struct GRAPH *graph, const char *filename); 181 struct NODE *node_add_dependency(struct NODE *node, const char *filename); 182 struct NODE *node_add_dependency_withnode(struct NODE *node, struct NODE *depnode); 183 struct NODE *node_add_job_dependency_withnode(struct NODE *node, struct NODE *depnode); 184 void node_set_pseudo(struct NODE *node); 185 void node_cached(struct NODE *node); 186 187 struct NODE *node_add_constraint_shared(struct NODE *node, const char *filename); 188 struct NODE *node_add_constraint_exclusive(struct NODE *node, const char *filename); 189 190 struct NODEWALKPATH 191 { 192 struct NODEWALKPATH *parent; 193 struct NODE *node; 194 }; 195 196 struct NODEWALKREVISIT 197 { 198 struct NODE *node; 199 struct NODEWALKREVISIT *next; 200 }; 201 202 struct NODEWALK 203 { 204 int flags; /* flags for this node walk */ 205 struct NODE *node; /* current visiting node */ 206 207 /* path that we reached this node by (not available during revisit due to activation) */ 208 struct NODEWALKPATH *parent; 209 unsigned depth; 210 211 void *user; 212 int (*callback)(struct NODEWALK *); /* function that is called for each visited node */ 213 214 unsigned char *mark; /* bits for mark and sweep */ 215 216 int revisiting; /* set to 1 if we are doing revisits */ 217 struct NODEWALKREVISIT *firstrevisit; 218 struct NODEWALKREVISIT *revisits; 219 }; 220 221 /* walks though the dependency tree with the set options and calling callback() 222 on each node it visites */ 223 int node_walk( 224 struct NODE *node, 225 int flags, 226 int (*callback)(struct NODEWALK *info), 227 void *u); 228 229 /* marks a node for revisit, only works if NODEWALK_REVISIT flags 230 was specified to node_walk */ 231 void node_walk_revisit(struct NODEWALK *walk, struct NODE *node); 232 233 /* node debug dump functions */ 234 void node_debug_dump(struct GRAPH *graph); 235 void node_debug_dump_detailed(struct GRAPH *graph); 236 void node_debug_dump_jobs(struct GRAPH *graph); 237 void node_debug_dump_dot(struct GRAPH *graph, struct NODE *top); 238 void node_debug_dump_jobs_dot(struct GRAPH *graph, struct NODE *top); 239 240 #endif /* FILE_NODE_H */ 241