Move finding longest path to UfoGraph base class

3 files changed, 118 insertions, 82 deletions

diff --git a/ufo/ufo-graph.c b/ufo/ufo-graph.c
index aa5c2ed..faeb7e7 100644
--- a/ufo/ufo-graph.c
+++ b/ufo/ufo-graph.c
@@ -684,13 +684,14 @@ pickup_paths (UfoGraph *graph,
               UfoNode *current,
               UfoNode *last,
               GList  *current_path,
-              GList **paths)
+              GList **paths,
+              gpointer user)
 {
     GList *successors;
     GList *it;
 
-    if (pred (current, NULL)) {
-        if (!pred (last, NULL))
+    if (pred (current, user)) {
+        if (!pred (last, user))
             current_path = g_list_append (current_path, last);
 
         current_path = g_list_append (current_path, current);
@@ -707,7 +708,7 @@ pickup_paths (UfoGraph *graph,
     successors = ufo_graph_get_successors (graph, current);
 
     g_list_for (successors, it) {
-        pickup_paths (graph, pred, it->data, current, g_list_copy (current_path), paths);
+        pickup_paths (graph, pred, it->data, current, g_list_copy (current_path), paths, user);
     }
 
     g_list_free (successors);
@@ -717,6 +718,7 @@ pickup_paths (UfoGraph *graph,
  * ufo_graph_get_paths:
  * @graph: A #UfoGraph
  * @pred: (scope call): A predicate function
+ * @user_data: User-data passed to @pred
  *
  * Compute a list of lists that contain complete paths with nodes that match a
  * predicate function.
@@ -726,7 +728,8 @@ pickup_paths (UfoGraph *graph,
  */
 GList *
 ufo_graph_get_paths (UfoGraph *graph,
-                     UfoFilterPredicate pred)
+                     UfoFilterPredicate pred,
+                     gpointer user_data)
 {
     GList *roots;
     GList *it;
@@ -736,13 +739,113 @@ ufo_graph_get_paths (UfoGraph *graph,
 
     g_list_for (roots, it) {
         UfoNode *node = UFO_NODE (it->data);
-        pickup_paths (graph, pred, node, node, NULL, &paths);
+        pickup_paths (graph, pred, node, node, NULL, &paths, user_data);
     }
 
     g_list_free (roots);
     return paths;
 }
 
+static gboolean
+path_unvisited (GList *path,
+                GList **visited)
+{
+    GList *head;
+    GList *tail;
+
+    head = g_list_first (path);
+    tail = g_list_last (path);
+
+    for (GList *it = g_list_first (head); it != tail; it = g_list_next (it)) {
+        UfoNode *node = (UfoNode *) it->data;
+
+        if (g_list_find (*visited, node))
+            return FALSE;
+
+        *visited = g_list_append (*visited, node);
+    }
+
+    return TRUE;
+}
+
+static GList *
+remove_common_ancestry_paths (GList *paths)
+{
+    GList *result;
+    GList *visited;
+    GList *it;
+
+    result = NULL;
+    visited = NULL;
+
+    g_list_for (paths, it) {
+        GList *path = (GList *) it->data;
+
+        if (path_unvisited (it->data, &visited))
+            result = g_list_append (result, path);
+    }
+
+    g_list_free (visited);
+    g_list_free (paths);
+    return result;
+}
+
+static GList *
+find_longest_path (GList *paths)
+{
+    GList *longest = NULL;
+    GList *it;
+    guint max_length = 0;
+
+    g_list_for (paths, it) {
+        guint length;
+        GList *path;
+
+        path = (GList *) it->data;
+        length = g_list_length (path);
+
+        if (length > max_length) {
+            max_length = length;
+            longest = path;
+        }
+    }
+
+    return longest;
+}
+
+/**
+ * ufo_graph_find_longest_path:
+ * @graph: A #UfoGraph
+ * @pred: (scope call): Predicate function for which elements of the path must
+ *      evaluate to %TRUE.
+ * @user_data: User data passed to @pred.
+ *
+ * Find the longest path in @task_graph that fulfills @predicate.
+ *
+ * Returns: (transfer full) (element-type UfoNode): A list with nodes in
+ * subsequent order of the path. User must free it with g_list_free.
+ */
+GList *
+ufo_graph_find_longest_path (UfoGraph *graph,
+                             UfoFilterPredicate pred,
+                             gpointer user_data)
+{
+    GList *it;
+    GList *paths;
+    GList *result;
+
+    paths = ufo_graph_get_paths (graph, pred, user_data);
+    paths = remove_common_ancestry_paths (paths);
+    result = find_longest_path (paths);
+
+    g_list_for (paths, it) {
+        if (it->data != result)
+            g_list_free (it->data);
+    }
+
+    return result;
+}
+
 /**
  * ufo_graph_dump_dot:
  * @graph: A #UfoGraph
diff --git a/ufo/ufo-graph.h b/ufo/ufo-graph.h
index f1ff113..bfb91c6 100644
--- a/ufo/ufo-graph.h
+++ b/ufo/ufo-graph.h
@@ -111,7 +111,11 @@ guint       ufo_graph_get_num_successors    (UfoGraph       *graph,
 GList      *ufo_graph_get_successors        (UfoGraph       *graph,
                                              UfoNode        *node);
 GList      *ufo_graph_get_paths             (UfoGraph       *graph,
-                                             UfoFilterPredicate pred);
+                                             UfoFilterPredicate pred,
+                                             gpointer        user_data);
+GList      *ufo_graph_find_longest_path     (UfoGraph       *graph,
+                                             UfoFilterPredicate pred,
+                                             gpointer        user_data);
 GList      *ufo_graph_flatten               (UfoGraph       *graph);
 void        ufo_graph_expand                (UfoGraph       *graph,
                                              GList          *path);
diff --git a/ufo/ufo-task-graph.c b/ufo/ufo-task-graph.c
index a00c6f4..0acc88a 100644
--- a/ufo/ufo-task-graph.c
+++ b/ufo/ufo-task-graph.c
@@ -386,73 +386,6 @@ expand_remotes (UfoTaskGraph *task_graph,
     g_object_unref (remote_graph);
 }
 
-static gboolean
-path_unvisited (GList *path,
-                GList **visited)
-{
-    GList *head;
-    GList *tail;
-
-    head = g_list_first (path);
-    tail = g_list_last (path);
-
-    for (GList *it = g_list_first (head); it != tail; it = g_list_next (it)) {
-        UfoNode *node = (UfoNode *) it->data;
-
-        if (g_list_find (*visited, node))
-            return FALSE;
-
-        *visited = g_list_append (*visited, node);
-    }
-
-    return TRUE;
-}
-
-static GList *
-remove_common_ancestry_paths (GList *paths)
-{
-    GList *result;
-    GList *visited;
-    GList *it;
-
-    result = NULL;
-    visited = NULL;
-
-    g_list_for (paths, it) {
-        GList *path = (GList *) it->data;
-
-        if (path_unvisited (it->data, &visited))
-            result = g_list_append (result, path);
-    }
-
-    g_list_free (visited);
-    g_list_free (paths);
-    return result;
-}
-
-static GList *
-find_longest_path (GList *paths)
-{
-    GList *longest = NULL;
-    GList *it;
-    guint max_length = 0;
-
-    g_list_for (paths, it) {
-        guint length;
-        GList *path;
-
-        path = (GList *) it->data;
-        length = g_list_length (path);
-
-        if (length > max_length) {
-            max_length = length;
-            longest = path;
-        }
-    }
-
-    return longest;
-}
-
 /**
  * ufo_task_graph_expand:
  * @task_graph: A #UfoTaskGraph
@@ -468,16 +401,13 @@ ufo_task_graph_expand (UfoTaskGraph *task_graph,
                        UfoArchGraph *arch_graph,
                        gboolean expand_remote)
 {
-    GList *paths;
     GList *path;
 
     g_return_if_fail (UFO_IS_TASK_GRAPH (task_graph));
 
-    paths = ufo_graph_get_paths (UFO_GRAPH (task_graph), (UfoFilterPredicate) is_gpu_task);
-    g_debug ("Number of identified paths: %i", g_list_length (paths));
-    paths = remove_common_ancestry_paths (paths);
-    g_debug ("Number of cleaned paths: %i", g_list_length (paths));
-    path = find_longest_path (paths);
+    path = ufo_graph_find_longest_path (UFO_GRAPH (task_graph),
+                                        (UfoFilterPredicate) is_gpu_task,
+                                        NULL);
 
     if (path != NULL) {
         guint n_gpus;
@@ -504,8 +434,7 @@ ufo_task_graph_expand (UfoTaskGraph *task_graph,
             ufo_graph_expand (UFO_GRAPH (task_graph), path);
     }
 
-    g_list_foreach (paths, (GFunc) g_list_free, NULL);
-    g_list_free (paths);
+    g_list_free (path);
 }
 
 /**