diff options
-rw-r--r-- | ufo/ufo-graph.c | 115 | ||||
-rw-r--r-- | ufo/ufo-graph.h | 6 | ||||
-rw-r--r-- | ufo/ufo-task-graph.c | 79 |
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); } /** |