From 2007956107e6dad867d28b4043cd97b81df96800 Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Sat, 23 Feb 2019 11:33:45 +0100 Subject: Optimized the graph view by reordering loop blocks. --- src/gtkext/graph/cluster.c | 118 +++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 115 insertions(+), 3 deletions(-) diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c index 4f39b28..8f584b9 100644 --- a/src/gtkext/graph/cluster.c +++ b/src/gtkext/graph/cluster.c @@ -231,6 +231,9 @@ static void dispatch_x_graph_rank(const graph_rank_t *); /* Réorganise au besoin les liens entrants un ensemble de blocs. */ static void sort_graph_rank_incoming_links(graph_rank_t *); +/* Réordonne les blocs de départ de boucle d'un ensemble. */ +static void reorder_graph_rank_loop_blocks(graph_rank_t *); + /* Décale vers la droite un ensemble de blocs basiques. */ static void offset_x_graph_rank(graph_rank_t *, gint); @@ -335,6 +338,9 @@ static void g_graph_cluster_sort_incoming_links(GGraphCluster *); /* Retrouve l'indice d'un lien entrant donné pour un bloc. */ static size_t g_graph_cluster_find_incoming_link(const GGraphCluster *, const leaving_link_t *); +/* Réordonne les blocs de départ de boucle au mieux. */ +static void g_graph_cluster_reorder_loop_blocks(GGraphCluster *); + /* Décale vers la droite un ensemble de blocs basiques. */ static void g_graph_cluster_offset_x(GGraphCluster *, gint); @@ -1491,6 +1497,70 @@ static void sort_graph_rank_incoming_links(graph_rank_t *grank) /****************************************************************************** * * * Paramètres : grank = ensemble de blocs de même rang à actualiser. * +* * +* Description : Réordonne les blocs de départ de boucle d'un ensemble. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void reorder_graph_rank_loop_blocks(graph_rank_t *grank) +{ + size_t i; /* Boucle de parcours #1 */ + size_t k; /* Boucle de parcours #2 */ + GGraphCluster *tmp; /* Stockage temporaire */ + + for (i = 0; i < grank->count; i++) + g_graph_cluster_reorder_loop_blocks(grank->clusters[i]); + + if (grank->count > 1) + { + /* Placement des départs de boucle à gauche ! */ + + for (i = 0; i < grank->vspaces.left_count; i++) + { + tmp = grank->vspaces.left[i]->from->owner; + + for (k = 0; k < grank->count; k++) + if (grank->clusters[k] == tmp) + break; + + assert(k < grank->count); + + memmove(&grank->clusters[1], &grank->clusters[0], k * sizeof(GGraphCluster *)); + + grank->clusters[0] = tmp; + + } + + /* Placement des départs de boucle à droite ! */ + + for (i = 0; i < grank->vspaces.right_count; i++) + { + tmp = grank->vspaces.right[i]->from->owner; + + for (k = 0; k < grank->count; k++) + if (grank->clusters[k] == tmp) + break; + + assert(k < grank->count); + + memmove(&grank->clusters[k], &grank->clusters[k + 1], (grank->count - k - 1) * sizeof(GGraphCluster *)); + + grank->clusters[grank->count - 1] = tmp; + + } + + } + +} + + +/****************************************************************************** +* * +* Paramètres : grank = ensemble de blocs de même rang à actualiser. * * offset = décalage à appliquer. * * * * Description : Décale vers la droite un ensemble de blocs basiques. * @@ -2297,6 +2367,28 @@ static size_t g_graph_cluster_find_incoming_link(const GGraphCluster *cluster, c /****************************************************************************** * * * Paramètres : cluster = graphique de blocs à actualiser. * +* * +* Description : Réordonne les blocs de départ de boucle au mieux. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_reorder_loop_blocks(GGraphCluster *cluster) +{ + size_t i; /* Boucle de parcours */ + + for (i = 0; i < cluster->ranks_count; i++) + reorder_graph_rank_loop_blocks(&cluster->ranks[i]); + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à actualiser. * * offset = décalage à appliquer. * * * * Description : Décale vers la droite un ensemble de blocs basiques. * @@ -3174,17 +3266,37 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList * * Cette consigne est valable pour les liens de boucle également, dont * l'origine est toujours dans un bloc inférieur au bloc de destination. * Le premier étant traité après le second, cela oblige à appeler - * g_graph_cluster_dispatch_x() deux fois donc, car on ne peut effectuer - * le tri des liens au début de cette fonction comme c'était fait - * dans les premières versions du code. + * g_graph_cluster_dispatch_x() au moins deux fois donc, car on ne peut + * effectuer le tri des liens au début de cette fonction comme c'était + * fait dans les premières versions du code. */ g_graph_cluster_sort_incoming_links(result); + /** + * Même s'ils ne sont pas encore entièrement tracés, les liens de boucle + * voient désormais leurs positions d'arrivée et de départ définies. + * + * On sait si lesdits liens partent vers la gauche ou la droite. + * + * On est donc en mesure de réorganiser latéralement les blocs + * pour tirer les traits horizontaux au plus court ! + */ + + g_graph_cluster_reset_allocation(result); + + g_graph_cluster_reorder_loop_blocks(result); + + /** + * Placement horizontal définitif. + */ + g_graph_cluster_reset_allocation(result); g_graph_cluster_dispatch_x(result); + g_graph_cluster_sort_incoming_links(result); + /* Réajustement vers la droite */ g_graph_cluster_compute_needed_alloc(result, &needed); -- cgit v0.11.2-87-g4458