From bf53af268d38ebb3224886e6d916e6148e78778b Mon Sep 17 00:00:00 2001
From: Cyrille Bagard <nocbos@gmail.com>
Date: Fri, 8 Mar 2019 20:00:28 +0100
Subject: Saved a first round to book extra space for straight edges if needed.
---
src/gtkext/graph/cluster-int.h | 6 ++
src/gtkext/graph/cluster.c | 176 ++++++++++++++++++++++++++++++++++++++++-
2 files changed, 180 insertions(+), 2 deletions(-)
diff --git a/src/gtkext/graph/cluster-int.h b/src/gtkext/graph/cluster-int.h
index 3121d64..9da1af2 100644
--- a/src/gtkext/graph/cluster-int.h
+++ b/src/gtkext/graph/cluster-int.h
@@ -64,6 +64,12 @@ const leaving_link_t *g_graph_cluster_has_origin(const GGraphCluster *, const GG
/* Compare deux clusters selon un de leurs liens d'origine. */
int g_graph_cluster_compare_by_origin(const GGraphCluster **, const GGraphCluster **, const GGraphCluster *);
+/* Calcule les abscisses extrèmes atteintes horizontalement. */
+void g_graph_cluster_compute_min_max_horizontal(const GGraphCluster *, const GGraphCluster *, gint [2]);
+
+/* S'assure que les liens verticaux ne traversent pas de bloc. */
+void g_graph_cluster_ensure_space_for_straight(GGraphCluster *);
+
/* Réorganise au besoin les liens entrants d'un bloc. */
void g_graph_cluster_sort_incoming_links(GGraphCluster *);
diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c
index 801929e..48ad9ca 100644
--- a/src/gtkext/graph/cluster.c
+++ b/src/gtkext/graph/cluster.c
@@ -65,6 +65,9 @@ struct _GGraphCluster
GtkWidget *display; /* Vue graphique associée */
GtkAllocation alloc; /* Emplacement final du bloc */
+ gint left_offset; /* Besoin d'espace à gauche */
+ gint right_offset; /* Besoin d'espace à droite */
+
leaving_link_t **bottom_anchors; /* Accroches inférieures */
size_t ba_count; /* Quantité de ces accroches */
@@ -189,6 +192,9 @@ static void g_graph_cluster_init(GGraphCluster *cluster)
{
cluster->container = cluster;
+ cluster->left_offset = 0;
+ cluster->right_offset = 0;
+
init_vspace_manager(&cluster->self);
}
@@ -816,7 +822,7 @@ void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
if (*rank->clusters[j - 1]->parent_index < straight_index)
break;
- start -= HORIZONTAL_MARGIN / 2;
+ start -= LINK_MARGIN;
_place_graph_rank_clusters(rank->clusters, j, start, -1);
@@ -826,7 +832,7 @@ void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
if (*rank->clusters[j]->parent_index > straight_index)
break;
- start += HORIZONTAL_MARGIN;
+ start += 2 * LINK_MARGIN;
_place_graph_rank_clusters(rank->clusters + j, rank->count - j, start, 1);
@@ -1250,6 +1256,148 @@ int g_graph_cluster_compare_by_origin(const GGraphCluster **cluster, const GGrap
/******************************************************************************
* *
+* Paramètres : cluster = graphique de blocs à consulter. *
+* stop = chef de file marquant l'arrêt des consultations. *
+* pos = ordonnées minimale et maximale en bout. [OUT] *
+* *
+* Description : Calcule les abscisses extrèmes atteintes horizontalement. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void g_graph_cluster_compute_min_max_horizontal(const GGraphCluster *cluster, const GGraphCluster *stop, gint pos[2])
+{
+ size_t i; /* Boucle de parcours */
+ const leaving_link_t *leaving; /* Lien sortant du bloc */
+
+ if (cluster->alloc.y < stop->alloc.y)
+ {
+ if (cluster->alloc.x < pos[0])
+ pos[0] = cluster->alloc.x;
+
+ if ((cluster->alloc.x + cluster->alloc.width) > pos[1])
+ pos[1] = cluster->alloc.x + cluster->alloc.width;
+
+ for (i = 0; i < cluster->ba_count; i++)
+ {
+ leaving = cluster->bottom_anchors[i];
+
+ if (leaving->other->type == ILT_LOOP)
+ continue;
+
+ g_graph_cluster_compute_min_max_horizontal(leaving->other->owner, stop, pos);
+
+ }
+
+ }
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : cluster = graphique de blocs à manipuler. *
+* *
+* Description : S'assure que les liens verticaux ne traversent pas de bloc. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void g_graph_cluster_ensure_space_for_straight(GGraphCluster *cluster)
+{
+ size_t i; /* Boucle de parcours */
+ size_t first; /* Premier lien vertical */
+ size_t last; /* Dernier lien vertical */
+ size_t straight_level; /* Rang atteint en ligne droite*/
+ GGraphCluster *stop; /* Borne d'arrêt correspondante*/
+ const leaving_link_t *leaving; /* Lien sortant du bloc */
+ gint pos[2]; /* Bornes horizontales */
+ gint max; /* Borne horizontale */
+
+ for (i = 0; i < cluster->ranks_count; i++)
+ visit_graph_rank(&cluster->ranks[i], g_graph_cluster_ensure_space_for_straight);
+
+ first = cluster->ba_count;
+ last = 0;
+
+ straight_level = 0;
+ stop = NULL;
+
+ for (i = 0; i < cluster->ba_count; i++)
+ {
+ leaving = cluster->bottom_anchors[i];
+
+ if (leaving->straight)
+ {
+ if (first == cluster->ba_count)
+ first = i;
+
+ last = i;
+
+ if (straight_level < leaving->straight_level)
+ {
+ straight_level = leaving->straight_level;
+ stop = leaving->other->owner;
+ }
+
+ }
+
+ }
+
+ if (stop != NULL)
+ {
+ if (first > 0)
+ {
+ pos[0] = G_MAXINT;
+ pos[1] = 0;
+
+ for (i = 0; i < first; i++)
+ {
+ leaving = cluster->bottom_anchors[i];
+ g_graph_cluster_compute_min_max_horizontal(leaving->other->owner, stop, pos);
+ }
+
+ max = compute_leaving_link_position(cluster->bottom_anchors[first]);
+
+ if ((pos[1] + LINK_MARGIN) > max)
+ {
+ cluster->right_offset = (pos[0] + LINK_MARGIN) - max;
+ assert(false);
+ }
+
+ }
+
+ if ((last + 1) < cluster->ba_count)
+ {
+ pos[0] = G_MAXINT;
+ pos[1] = 0;
+
+ for (i = last + 1; i < cluster->ba_count; i++)
+ {
+ leaving = cluster->bottom_anchors[i];
+ g_graph_cluster_compute_min_max_horizontal(leaving->other->owner, stop, pos);
+ }
+
+ max = compute_leaving_link_position(cluster->bottom_anchors[last]);
+
+ if ((max + LINK_MARGIN) > pos[0])
+ cluster->right_offset = (max + LINK_MARGIN) - pos[0];
+
+ }
+
+ }
+
+}
+
+
+/******************************************************************************
+* *
* Paramètres : cluster = graphique de blocs à manipuler. *
* *
* Description : Réorganise au besoin les liens entrants d'un bloc. *
@@ -1546,6 +1694,8 @@ void g_graph_cluster_compute_needed_alloc(const GGraphCluster *cluster, GtkAlloc
}
+ alloc->width += cluster->right_offset;
+
}
@@ -2473,6 +2623,28 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
g_graph_cluster_sort_leaving_links(result);
/**
+ * On vérifie maintenant que les liens bien verticaux ne rencontrent pas
+ * de bloc de code.
+ *
+ * Pour celà, il faut disposer d'une cartographie complète :
+ *
+ * - sur l'axe des abscisses pour les positions à compenser.
+ * - sur l'axe des ordonnées pour borner les suivis de liens en profondeur.
+ */
+
+ g_graph_cluster_reset_allocation(result);
+
+ g_graph_cluster_dispatch_x(result);
+
+ g_graph_cluster_compute_needed_alloc(result, &needed);
+
+ g_graph_cluster_offset_x(result, -needed.x);
+
+ g_graph_cluster_set_y(result, 0);
+
+ g_graph_cluster_ensure_space_for_straight(result);
+
+ /**
* A ce point, tous les blocs sont placés.
* On est donc en mesure de réorganiser les points d'arrivée
* des liens afin d'éviter les croisements : un lien qui vient
--
cgit v0.11.2-87-g4458