examples/simdag/mixtesim/src/dag.c

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <stdlib.h>
   4
   5 #include "mixtesim_prototypes.h"
   6
   7 /**           **
   8  ** STRUCTURE **
   9  **           **/
  10
  11 /*
  12  * newDAG()
  13  */
  14 DAG newDAG()
  15 {
  16   return (DAG)calloc(1,sizeof(struct _DAG));
  17 }
  18
  19 /*
  20  * freeDAG()
  21  */
  22 void freeDAG(DAG dag)
  23 {
  24   int i;
  25
  26   for (i=0;i<dag->nb_nodes;i++) {
  27     freeNode(dag->nodes[i]);
  28   }
  29   if (dag->nodes)
  30     free(dag->nodes);
  31   free(dag);
  32   return;
  33 }
  34
  35 /*
  36  * newNode()
  37  */
  38 Node newNode()
  39 {
  40   return (Node)calloc(1,sizeof(struct _Node));
  41 }
  42
  43 /*
  44  * freeNode()
  45  */
  46 void freeNode(Node n)
  47 {
  48   if (n->parents)
  49     free(n->parents);
  50   if (n->children)
  51     free(n->children);
  52   free(n);
  53   return;
  54 }
  55
  56 /*
  57  * printDAG()
  58  */
  59 void printDAG(DAG dag)
  60 {
  61   fprintf(stderr,"%d nodes: # (children) [parents]\n",dag->nb_nodes);
  62   printNode(dag,dag->root);
  63 }
  64
  65 /*
  66  * printNode()
  67  */
  68 void printNode(DAG dag, Node node)
  69 {
  70   int i;
  71   fprintf(stderr,"%d (",node->global_index);
  72
  73   /* print children info */
  74   for (i=0;i<node->nb_children-1;i++) {
  75     fprintf(stderr,"%d,",node->children[i]->global_index);
  76   }
  77   if (node->nb_children> 0)
  78     fprintf(stderr,"%d",node->children[node->nb_children-1]->global_index);
  79   fprintf(stderr,") ");
  80
  81   /* print parent info */
  82   fprintf(stderr,"[");
  83   for (i=0;i<node->nb_parents-1;i++) {
  84     fprintf(stderr,"%d,",node->parents[i]->global_index);
  85   }
  86   if (node->nb_parents > 0)
  87     fprintf(stderr,"%d",node->parents[node->nb_parents-1]->global_index);
  88   fprintf(stderr,"] ");
  89
  90   /* print special inf */
  91   if (dag->root == node) {
  92     fprintf(stderr,"ROOT\n");
  93   } else if (dag->end == node) {
  94     fprintf(stderr,"END\n");
  95   } else {
  96     fprintf(stderr,"\n");
  97   }
  98
  99   for (i=0;i<node->nb_children;i++) {
 100     printNode(dag, node->children[i]);
 101   }
 102   return;
 103 }
 104
 105 /**         **
 106  ** PARSING **
 107  **         **/
 108
 109 static int parseLine(DAG,char*);
 110 static int parseNodeLine(DAG,char*);
 111 static int parseNodeCountLine(DAG,char*);
 112 static node_t string2NodeType(const char*);
 113 static int string2NodeList(const char*,int**,int*);
 114 static int finalizeDAG(DAG);
 115
 116 /* temporary array in which children lists are stored. Once all nodes
 117  * have been parsed, one can go through these lists and assign actual
 118  * Node pointers to real children lists
 119  */
 120 char **tmp_childrens;
 121
 122 /*
 123  * parseDAGFile()
 124  */
 125 DAG parseDAGFile(char *filename)
 126 {
 127   FILE *f;
 128   char line[4024];
 129   int i,count=0;
 130   char *tmp;
 131   DAG new;
 132
 133   /* initialize the global children list array */
 134   tmp_childrens=NULL;
 135
 136   /* opening the DAG description file */
 137   if (!(f=fopen(filename,"r"))) {
 138     fprintf(stderr,"Impossible to open file '%s'\n",filename);
 139     return NULL;
 140   }
 141
 142   /* allocate memory for the DAG */
 143   new = newDAG();
 144
 145   /* Go through the lines of the file */
 146   while(fgets(line,4024,f)) {
 147     count++;
 148     if (line[0]=='#') /* comment lines */
 149       continue;
 150     if (line[0]=='\n') /* empty lines */
 151       continue;
 152     tmp=strdup(line); /* somehow, strduping makes it work ? */
 153     if (parseLine(new,tmp) == -1) {
 154       fprintf(stderr,"Error in DAG description file at line %d\n",count);
 155       fclose(f);
 156       return NULL;
 157     }
 158     free(tmp);
 159   }
 160   fclose(f);
 161
 162   /* fill in child lists, parent lists, and perform a few
 163    * reality checks
 164    */
 165   if (finalizeDAG(new) == -1) {
 166     freeDAG(new);
 167     return NULL;
 168   }
 169
 170   /* free the temporary global child list array */
 171   for (i=0;i<new->nb_nodes;i++) {
 172     if (tmp_childrens[i])
 173       free(tmp_childrens[i]);
 174   }
 175   free(tmp_childrens);
 176
 177   return new;
 178 }
 179
 180 /*
 181  * finalizeDAG(): fills in the child lists with actual pointers,
 182  * creates the parent lists, checks some things about the Root
 183  * and the End node.
 184  */
 185 static int finalizeDAG(DAG dag)
 186 {
 187   int i,j;
 188   int *childrenlist,nb_children;
 189
 190   /* Set the children pointers */
 191   for (i=0;i<dag->nb_nodes;i++) {
 192     Node node=dag->nodes[i];
 193
 194     /* convert the textual list to an integer list */
 195     if (string2NodeList(tmp_childrens[i],&childrenlist,&nb_children) == -1) {
 196       fprintf(stderr,"Error: invalid child list '%s'\n",
 197                       tmp_childrens[i]);
 198       return -1;
 199     }
 200     /* set the number of children */
 201     node->nb_children=nb_children;
 202
 203     /* create the child list with pointers to nodes */
 204     if (nb_children) {
 205       node->children=(Node*)calloc(nb_children,sizeof(Node));
 206       for (j=0;j<nb_children;j++) {
 207         node->children[j]=dag->nodes[childrenlist[j]];
 208       }
 209       free(childrenlist);
 210     }
 211   }
 212
 213   /* Set the parent pointers */
 214   for (i=0;i<dag->nb_nodes;i++) {
 215     for (j=0;j<dag->nodes[i]->nb_children;j++) {
 216       Node node=dag->nodes[i]->children[j];
 217       node->parents=(Node*)realloc(node->parents,
 218                       (node->nb_parents+1)*sizeof(Node));
 219       node->parents[node->nb_parents]=dag->nodes[i];
 220       (node->nb_parents)++;
 221     }
 222   }
 223
 224   /* A few sanity checks */
 225   if (!(dag->root) || !(dag->end)) {
 226     fprintf(stderr,"Error: Graph has missing end points\n");
 227     return -1;
 228   }
 229
 230   if (dag->root->nb_parents != 0) {
 231     fprintf(stderr,"Error: The Root should have no parents\n");
 232     return -1;
 233   }
 234   if (dag->end->nb_children != 0) {
 235     fprintf(stderr,"Error: The End should have no children\n");
 236     return -1;
 237   }
 238   return 0;
 239 }
 240
 241 /*
 242  * parseLine()
 243  */
 244 static int parseLine(DAG dag, char *line)
 245 {
 246   char *ptr;
 247
 248   /* If the line does not start with a keyword, then bail */
 249   ptr=strchr(line,' ');
 250   if (ptr==NULL) {
 251     fprintf(stderr,"Syntax error\n");
 252     return -1;
 253   } else{
 254     *ptr='\0';
 255   }
 256
 257   /* deal with the two possible keywords */
 258   if (!strncmp(line,"NODE_COUNT",strlen("NODE_COUNT")))
 259     return parseNodeCountLine(dag,ptr+1);
 260   if (!strncmp(line,"NODE",strlen("NODE")))
 261     return parseNodeLine(dag,ptr+1);
 262
 263   fprintf(stderr,"Unknown keyword %s\n",line);
 264   return -1;
 265 }
 266
 267 /*
 268  * parseNodeCountLine()
 269  *
 270  * NODE_COUNT <number>
 271  */
 272 int parseNodeCountLine(DAG dag, char *line)
 273 {
 274   int count;
 275
 276   /* more than one NODE_COUNT statements ? */
 277   if (dag->nb_nodes != 0) {
 278     fprintf(stderr,"Error: Only one Node Count specification allowed\n");
 279     return -1;
 280   }
 281
 282   /* get the count and checks that it's >0 */
 283   count=atoi(line);
 284   if (count == 0) {
 285     fprintf(stderr,"Error: invalid Node count\n");
 286     return -1;
 287   }
 288
 289   /* allocate the node array within the dag */
 290   dag->nb_nodes=count;
 291   dag->nodes=(Node *)calloc(dag->nb_nodes,sizeof(Node));
 292   /* allocate space in the temporary gobal childlist array */
 293   tmp_childrens=(char **)calloc(dag->nb_nodes,sizeof(char*));
 294   return 0;
 295 }
 296
 297 /*
 298  * parseNodeLine()
 299  *
 300  * NODE <index> <childlist> <type> <cost>
 301  */
 302 int parseNodeLine(DAG dag, char *line)
 303 {
 304   char *ptr;
 305   Node node;
 306
 307   char *s_index,*s_childlist,*s_type,*s_cost;
 308   int index;
 309   node_t type;
 310   double cost;
 311
 312   /* NODE_COUNT should be called before NODE */
 313   if (dag->nb_nodes == 0) {
 314     fprintf(stderr,"Error: Node Count must be specified before Nodes\n");
 315     return -1;
 316   }
 317
 318   /* Get index */
 319   ptr=strchr(line,' ');
 320   if (!ptr) {
 321     fprintf(stderr,"Syntax error\n");
 322     return -1;
 323   }
 324   s_index=line;
 325   *ptr='\0';
 326   line=ptr+1;
 327
 328
 329   /* Get childlist */
 330   ptr=strchr(line,' ');
 331   if (!ptr) {
 332     fprintf(stderr,"Syntax error\n");
 333     return -1;
 334   }
 335   s_childlist=line;
 336   *ptr='\0';
 337   line=ptr+1;
 338
 339   /* get node type */
 340   ptr=strchr(line,' ');
 341   if (!ptr) {
 342     fprintf(stderr,"Syntax error\n");
 343     return -1;
 344   }
 345   s_type=line;
 346   *ptr='\0';
 347   line=ptr+1;
 348
 349   /* get cost */
 350   ptr=strchr(line,'\n');
 351   if (!ptr) {
 352     fprintf(stderr,"Syntax error\n");
 353     return -1;
 354   }
 355   s_cost=line;
 356   *ptr='\0';
 357
 358   /* Process strings, but store childlist for later */
 359   index=atoi(s_index);
 360   if ((type=string2NodeType(s_type)) ==-1)
 361     return -1;
 362   cost=atof(s_cost);
 363   tmp_childrens[index]=strdup(s_childlist);
 364
 365   /* Creating the node */
 366   node = newNode();
 367   node->global_index = index;
 368   node->cost=cost;
 369   node->type=type;
 370
 371   /* Is this the root ? */
 372   if (node->type == NODE_ROOT) {
 373     if (dag->root) {
 374       fprintf(stderr,"Error: only one Root node allowed\n");
 375       return -1;
 376     } else {
 377       dag->root = node;
 378
 379     }
 380   }
 381   /* Is this the end ? */
 382   if (node->type == NODE_END) {
 383     if (dag->end) {
 384       fprintf(stderr,"Error: only one End node allowed\n");
 385       return -1;
 386     } else {
 387       dag->end = node;
 388     }
 389   }
 390
 391   /* Is the node beyond the total number of nodes ? */
 392   if (node->global_index >= dag->nb_nodes) {
 393     fprintf(stderr,"Error: More nodes than the node count\n");
 394     return -1;
 395   }
 396
 397   /* Have we seen that node before ? */
 398   if (dag->nodes[node->global_index] != NULL) {
 399     fprintf(stderr,"Error: Two nodes share index %d\n",
 400                     node->global_index);
 401     return -1;
 402   }
 403   /* add the node to the global array */
 404   dag->nodes[node->global_index]=node;
 405   return 1;
 406 }
 407
 408 /*
 409  * string2NodeList()
 410  * parser x,y,z and returns {x,y,z} and 3
 411  * Does not really do good error checking
 412  */
 413 static int string2NodeList(const char *string, int **list, int *nb_nodes)
 414 {
 415   char *start,*ptr;
 416   int count=0;
 417
 418   *list=NULL;
 419
 420   /* no children "-" */
 421   if (!strcmp(string,"-")) {
 422     *nb_nodes=0;
 423     *list=NULL;
 424     return 0;
 425   }
 426
 427   /* Get all indexes in the list */
 428   start = (char*)string;
 429   while((ptr = strchr(start,','))) {
 430     *ptr='\0';
 431     *list=(int*)realloc(*list,(count+1)*sizeof(int));
 432     (*list)[count]=atoi(start);
 433     count++;
 434     start = ptr+1;
 435   }
 436   *list=(int*)realloc(*list,(count+1)*sizeof(int));
 437   (*list)[count]=atoi(start);
 438   count++;
 439
 440   *nb_nodes=count;
 441   return 0;
 442 }
 443
 444 /*
 445  * string2NodeType()
 446  */
 447 static node_t string2NodeType(const char *string) {
 448   if (!strcmp(string,"ROOT")) {
 449     return NODE_ROOT;
 450   } else if (!strcmp(string,"END")) {
 451     return NODE_END;
 452   } else if (!strcmp(string,"COMPUTATION")) {
 453     return NODE_COMPUTATION;
 454   } else if (!strcmp(string,"TRANSFER")) {
 455     return NODE_TRANSFER;
 456   }
 457   fprintf(stderr,"Error: Unknown Node Type '%s'\n",string);
 458   return -1;
 459 }
 460