[simdag/dot,simdag/dax] move the test for acyclic graph to the daxloader

git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/simgrid/simgrid/trunk@8872 48e7efb5-ca39-0410-a469-dd3cf9ba447f

diff --git a/src/simdag/private.h b/src/simdag/private.h
index efbabab..8c5aa0c 100644 (file)
--- a/src/simdag/private.h
+++ b/src/simdag/private.h
@@ -129,6 +129,7 @@ void __SD_task_really_run(SD_task_t task);
 int __SD_task_try_to_run(SD_task_t task);
 void __SD_task_just_done(SD_task_t task);
 bool acyclic_graph_detection(xbt_dynar_t dag);
 int __SD_task_try_to_run(SD_task_t task);
 void __SD_task_just_done(SD_task_t task);
 bool acyclic_graph_detection(xbt_dynar_t dag);

+bool acyclic_graph_detail(xbt_dynar_t dag);

 
 /* Functions to test if the task is in a given state. */
 
 
 /* Functions to test if the task is in a given state. */
 

diff --git a/src/simdag/sd_daxloader.c b/src/simdag/sd_daxloader.c
index c17e7f0..c63256f 100644 (file)
--- a/src/simdag/sd_daxloader.c
+++ b/src/simdag/sd_daxloader.c
@@ -15,6 +15,8 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_daxparse, sd, "Parsing DAX files");
 #include "dax_dtd.h"
 #include "dax_dtd.c"
 
 #include "dax_dtd.h"
 #include "dax_dtd.c"
 

+bool children_are_marked(SD_task_t task);
+bool parents_are_marked(SD_task_t task);

 
 /* Parsing helpers */
 static void dax_parse_error(char *msg)
 
 /* Parsing helpers */
 static void dax_parse_error(char *msg)


@@ -71,6 +73,238 @@ void uniq_transfer_task_name(SD_task_t task)
   free(new_name);
 }
 
   free(new_name);
 }
 

+bool children_are_marked(SD_task_t task){
+  SD_task_t child_task = NULL;
+  bool all_marked = true;
+  SD_dependency_t depafter = NULL;
+  unsigned int count;
+  xbt_dynar_foreach(task->tasks_after,count,depafter){
+    child_task = depafter->dst;
+    //test marked
+    if(child_task->marked == 0) {
+      all_marked = false;
+      break;
+    }
+    child_task = NULL;
+  }
+  return all_marked;
+}
+
+bool parents_are_marked(SD_task_t task){
+  SD_task_t parent_task = NULL;
+  bool all_marked = true;
+  SD_dependency_t depafter = NULL;
+  unsigned int count;
+  xbt_dynar_foreach(task->tasks_after,count,depafter){
+    parent_task = depafter->dst;
+    //test marked
+    if(parent_task->marked == 0) {
+      all_marked = false;
+      break;
+    }
+    parent_task = NULL;
+  }
+  return all_marked;
+}
+
+bool acyclic_graph_detail(xbt_dynar_t dag){
+  unsigned int count=0, count_current=0;
+  bool all_marked = true;
+  SD_task_t task = NULL, parent_task = NULL, child_task = NULL;
+  SD_dependency_t depbefore = NULL, depafter = NULL;
+  xbt_dynar_t next = NULL, current = xbt_dynar_new(sizeof(SD_task_t),NULL);
+
+  xbt_dynar_foreach(dag,count,task){
+    if(task->kind == SD_TASK_COMM_E2E) continue;
+    task->marked = 0;
+    if(xbt_dynar_length(task->tasks_after) == 0){
+      xbt_dynar_push(current, &task);
+    }
+  }
+  task = NULL;
+  count = 0;
+  //test if something has to be done for the next iteration
+  while(xbt_dynar_length(current) != 0){
+    next = xbt_dynar_new(sizeof(SD_task_t),NULL);
+    //test if the current iteration is done
+    count_current=0;
+    xbt_dynar_foreach(current,count_current,task){
+      if (task == NULL) continue;
+      count = 0;
+      //push task in next
+      task->marked = 1;
+      count = 0;
+      xbt_dynar_foreach(task->tasks_before,count,depbefore){
+        parent_task = depbefore->src;
+        if(parent_task->kind == SD_TASK_COMM_E2E){
+          unsigned int j=0;
+          parent_task->marked = 1;
+          SD_task_t parent_task_2 = NULL;
+          xbt_dynar_foreach(parent_task->tasks_before,j,depbefore){
+            parent_task_2 = depbefore->src;
+            if(children_are_marked(parent_task_2))
+              xbt_dynar_push(next, &parent_task_2);
+          }
+        } else{
+          if(children_are_marked(parent_task))
+            xbt_dynar_push(next, &parent_task);
+        }
+        parent_task = NULL;
+      }
+      task = NULL;
+      count = 0;
+    }
+    xbt_dynar_free(&current);
+    current = next;
+    next = NULL;
+  }
+  xbt_dynar_free(&current);
+  current = NULL;
+  all_marked = true;
+  xbt_dynar_foreach(dag,count,task){
+    if(task->kind == SD_TASK_COMM_E2E) continue;
+    //test if all tasks are marked
+    if(task->marked == 0){
+      WARN1("the task %s is not marked",task->name);
+      all_marked = false;
+      break;
+    }
+  }
+  task = NULL;
+  if(!all_marked){
+    VERB0("there is at least one cycle in your task graph");
+
+    count = 0;
+    task = NULL;
+    xbt_dynar_foreach(dag,count,task){
+      if(task->kind == SD_TASK_COMM_E2E) continue;
+      task->marked = 0;
+      if(xbt_dynar_length(task->tasks_before) == 0){
+        xbt_dynar_push(current, &task);
+      }
+    }
+    task = NULL;
+    count = 0;
+    //test if something has to be done for the next iteration
+    while(xbt_dynar_length(current) != 0){
+      next = xbt_dynar_new(sizeof(SD_task_t),NULL);
+      //test if the current iteration is done
+      count_current=0;
+      xbt_dynar_foreach(current,count_current,task){
+        if (task == NULL) continue;
+        count = 0;
+        //push task in next
+        task->marked = 1;
+        count = 0;
+        xbt_dynar_foreach(task->tasks_after,count,depafter){
+          child_task = depafter->dst;
+          if(child_task->kind == SD_TASK_COMM_E2E){
+            unsigned int j=0;
+            child_task->marked = 1;
+            SD_task_t child_task_2 = NULL;
+            xbt_dynar_foreach(child_task->tasks_after,j,depafter){
+              child_task_2 = depafter->src;
+              if(parents_are_marked(child_task_2))
+                xbt_dynar_push(next, &child_task_2);
+            }
+          } else{
+            if(parents_are_marked(child_task))
+              xbt_dynar_push(next, &child_task);
+          }
+          parent_task = NULL;
+        }
+        task = NULL;
+        count = 0;
+      }
+      xbt_dynar_free(&current);
+      current = next;
+      next = NULL;
+    }
+    xbt_dynar_free(&current);
+    current = NULL;
+    all_marked = true;
+    xbt_dynar_foreach(dag,count,task){
+      if(task->kind == SD_TASK_COMM_E2E) continue;
+      //test if all tasks are marked
+      if(task->marked == 0){
+        WARN1("the task %s is not marked",task->name);
+        all_marked = false;
+      }
+    }
+  }
+  return all_marked;
+}
+
+bool acyclic_graph_detection(xbt_dynar_t dag){
+  unsigned int count=0, count_current=0;
+  bool all_marked = true;
+  SD_task_t task = NULL, parent_task = NULL;
+  SD_dependency_t depbefore = NULL;
+  xbt_dynar_t next = NULL, current = xbt_dynar_new(sizeof(SD_task_t),NULL);
+
+  xbt_dynar_foreach(dag,count,task){
+    if(task->kind == SD_TASK_COMM_E2E) continue;
+    task->marked = 0;
+    if(xbt_dynar_length(task->tasks_after) == 0){
+      xbt_dynar_push(current, &task);
+    }
+  }
+  task = NULL;
+  count = 0;
+  //test if something has to be done for the next iteration
+  while(xbt_dynar_length(current) != 0){
+    next = xbt_dynar_new(sizeof(SD_task_t),NULL);
+    //test if the current iteration is done
+    count_current=0;
+    xbt_dynar_foreach(current,count_current,task){
+      if (task == NULL) continue;
+      count = 0;
+      //push task in next
+      task->marked = 1;
+      count = 0;
+      xbt_dynar_foreach(task->tasks_before,count,depbefore){
+        parent_task = depbefore->src;
+        if(parent_task->kind == SD_TASK_COMM_E2E){
+          unsigned int j=0;
+          parent_task->marked = 1;
+          SD_task_t parent_task_2 = NULL;
+          xbt_dynar_foreach(parent_task->tasks_before,j,depbefore){
+            parent_task_2 = depbefore->src;
+            if(children_are_marked(parent_task_2))
+              xbt_dynar_push(next, &parent_task_2);
+          }
+        } else{
+          if(children_are_marked(parent_task))
+            xbt_dynar_push(next, &parent_task);
+        }
+        parent_task = NULL;
+      }
+      task = NULL;
+      count = 0;
+    }
+    xbt_dynar_free(&current);
+    current = next;
+    next = NULL;
+  }
+  xbt_dynar_free(&current);
+  current = NULL;
+  all_marked = true;
+  xbt_dynar_foreach(dag,count,task){
+    if(task->kind == SD_TASK_COMM_E2E) continue;
+    //test if all tasks are marked
+    if(task->marked == 0){
+      WARN1("the task %s is not marked",task->name);
+      all_marked = false;
+      break;
+    }
+  }
+  task = NULL;
+  if(!all_marked){
+    VERB0("there is at least one cycle in your task graph");
+  }
+  return all_marked;
+}
+

 
 static YY_BUFFER_STATE input_buffer;
 
 
 static YY_BUFFER_STATE input_buffer;
 

diff --git a/src/simdag/sd_dotloader.c b/src/simdag/sd_dotloader.c
index 6bd182c..2d675aa 100644 (file)
--- a/src/simdag/sd_dotloader.c
+++ b/src/simdag/sd_dotloader.c
@@ -23,7 +23,6 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(sd_dotparse, sd, "Parsing DOT files");
 void dot_add_task(Agnode_t * dag_node);
 void dot_add_input_dependencies(SD_task_t current_job, Agedge_t * edge);
 void dot_add_output_dependencies(SD_task_t current_job, Agedge_t * edge);
 void dot_add_task(Agnode_t * dag_node);
 void dot_add_input_dependencies(SD_task_t current_job, Agedge_t * edge);
 void dot_add_output_dependencies(SD_task_t current_job, Agedge_t * edge);

-bool child_are_marked(SD_task_t task);

 xbt_dynar_t SD_dotload_FILE(FILE * in_file);
 
 static double dot_parse_double(const char *string)
 xbt_dynar_t SD_dotload_FILE(FILE * in_file);
 
 static double dot_parse_double(const char *string)


@@ -70,91 +69,6 @@ static void dump_res()
   }
 }
 
   }
 }
 

-bool child_are_marked(SD_task_t task){
-  SD_task_t child_task = NULL;
-  bool all_marked = true;
-  SD_dependency_t depafter = NULL;
-  unsigned int count;
-  xbt_dynar_foreach(task->tasks_after,count,depafter){
-    child_task = depafter->dst;
-    //test marked
-    if(child_task->marked == 0) {
-      all_marked = false;
-      break;
-    }
-    child_task = NULL;
-  }
-  return all_marked;
-}
-
-bool acyclic_graph_detection(xbt_dynar_t dag){
-  unsigned int count=0, count_current=0;
-  bool all_marked = true;
-  SD_task_t task = NULL, parent_task = NULL;
-  SD_dependency_t depbefore = NULL;
-  xbt_dynar_t next = NULL, current = xbt_dynar_new(sizeof(SD_task_t),NULL);
-
-  xbt_dynar_foreach(dag,count,task){
-    if(task->kind == SD_TASK_COMM_E2E) continue;
-    task->marked = 0;
-    if(xbt_dynar_length(task->tasks_after) == 0){
-      xbt_dynar_push(current, &task);
-    }
-  }
-  task = NULL;
-  count = 0;
-  //test if something has to be done for the next iteration
-  while(xbt_dynar_length(current) != 0){
-    next = xbt_dynar_new(sizeof(SD_task_t),NULL);
-    //test if the current iteration is done
-    count_current=0;
-    xbt_dynar_foreach(current,count_current,task){
-      if (task == NULL) continue;
-      count = 0;
-      //push task in next
-      task->marked = 1;
-      count = 0;
-      xbt_dynar_foreach(task->tasks_before,count,depbefore){
-        parent_task = depbefore->src;
-        if(parent_task->kind == SD_TASK_COMM_E2E){
-          unsigned int j=0;
-          parent_task->marked = 1;
-          xbt_dynar_foreach(parent_task->tasks_before,j,depbefore){
-            parent_task = depbefore->src;
-            if(child_are_marked(parent_task))
-              xbt_dynar_push(next, &parent_task);
-          }
-        } else{
-          if(child_are_marked(parent_task))
-            xbt_dynar_push(next, &parent_task);
-        }
-        parent_task = NULL;
-      }
-      task = NULL;
-      count = 0;
-    }
-    xbt_dynar_free(&current);
-    current = next;
-    next = NULL;
-  }
-  xbt_dynar_free(&current);
-  current = NULL;
-  all_marked = true;
-  xbt_dynar_foreach(dag,count,task){
-    if(task->kind == SD_TASK_COMM_E2E) continue;
-    //test if all tasks are marked
-    if(task->marked == 0){
-      WARN1("the task %s is not marked",task->name);
-      all_marked = false;
-      break;
-    }
-  }
-  task = NULL;
-  if(!all_marked){
-    VERB0("there is at least one cycle in your task graph");
-  }
-  return all_marked;
-}

 
 static void dot_task_free(void *task)
 {
 
 static void dot_task_free(void *task)
 {


@@ -322,6 +236,7 @@ xbt_dynar_t SD_dotload_FILE(FILE * in_file)
   xbt_dict_free(&files);
   if(acyclic_graph_detection(result))
     return result;
   xbt_dict_free(&files);
   if(acyclic_graph_detection(result))
     return result;

+  acyclic_graph_detail(result);

   return NULL;
 }
 
   return NULL;
 }