From 2007956107e6dad867d28b4043cd97b81df96800 Mon Sep 17 00:00:00 2001
From: Cyrille Bagard <nocbos@gmail.com>
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