From bf53af268d38ebb3224886e6d916e6148e78778b Mon Sep 17 00:00:00 2001 From: Cyrille Bagard 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