summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/gtkext/graph/cluster.c250
1 files changed, 246 insertions, 4 deletions
diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c
index 84f3b38..6284029 100644
--- a/src/gtkext/graph/cluster.c
+++ b/src/gtkext/graph/cluster.c
@@ -55,16 +55,16 @@ typedef struct _leaving_link_t
size_t index; /* Indice sur ligne de départ */
bool straight; /* Présence d'une ligne droite */
+ bool forced_straight; /* Forçage de verticalité */
size_t straight_level; /* Rang atteint en ligne droite*/
bool cluster_exit; /* Sortie du cluster d'origine */
- bool forced_straight; /* Forçage de verticalité */
incoming_link_t *other; /* Autre extrémité du lien */
} leaving_link_t;
-#define SHOULD_BE_VERTICAL(l) ((l)->straight || (l)->cluster_exit || (l)->forced_straight)
+#define SHOULD_BE_VERTICAL(l) ((l)->straight || (l)->forced_straight || (l)->cluster_exit)
/* Crée un point d'attache pour un lien sortant. */
@@ -249,6 +249,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 sortant d'un ensemble. */
+static void reorder_graph_rank_exit_blocks(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 *);
@@ -373,6 +376,15 @@ 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 *);
+/* Détermine si un cluster possède un lien sortant. */
+static bool g_graph_cluster_has_exit_link(GGraphCluster *, bool *);
+
+/* Compare deux clusters avec lien sortant. */
+static int g_graph_cluster_compare_by_exit(const GGraphCluster **, const GGraphCluster **, const bool *);
+
+/* Réordonne les blocs sortant du cluster au mieux. */
+static void g_graph_cluster_reorder_exit_blocks(GGraphCluster *);
+
/* Réordonne les blocs de départ de boucle au mieux. */
static void g_graph_cluster_reorder_loop_blocks(GGraphCluster *);
@@ -466,9 +478,9 @@ static leaving_link_t *create_leaving_link(GGraphCluster *owner, size_t index)
result->index = index;
result->straight = false;
+ result->forced_straight = false;
result->straight_level = SIZE_MAX;
result->cluster_exit = false;
- result->forced_straight = false;
return result;
@@ -1596,7 +1608,81 @@ static void sort_graph_rank_incoming_links(graph_rank_t *grank)
/******************************************************************************
* *
-* Paramètres : grank = ensemble de blocs de même rang à actualiser. *
+* Paramètres : grank = ensemble de blocs de même rang à actualiser. *
+* *
+* Description : Réordonne les blocs sortant d'un ensemble. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void reorder_graph_rank_exit_blocks(graph_rank_t *grank)
+{
+ GGraphCluster **exit_2_left; /* Liste avec sortie à gauche */
+ GGraphCluster **exit_2_right; /* Liste avec sortie à droite */
+ GGraphCluster **no_exit; /* Liste sans sortie */
+ size_t count_2_left; /* Quantité de présents */
+ size_t count_2_right; /* Quantité de présents */
+ size_t count_no; /* Quantité de présents */
+ size_t i; /* Boucle de parcours */
+ bool l2r; /* Détermination de catégorie */
+
+ if (grank->count > 1)
+ {
+ exit_2_left = malloc(grank->count * sizeof(GGraphCluster *));
+ exit_2_right = malloc(grank->count * sizeof(GGraphCluster *));
+ no_exit = malloc(grank->count * sizeof(GGraphCluster *));
+
+ count_2_left = 0;
+ count_2_right = 0;
+ count_no = 0;
+
+ for (i = 0; i < grank->count; i++)
+ {
+ if (g_graph_cluster_has_exit_link(grank->clusters[i], &l2r))
+ {
+ if (l2r)
+ exit_2_right[count_2_right++] = grank->clusters[i];
+ else
+ exit_2_left[count_2_left++] = grank->clusters[i];
+ }
+ else
+ no_exit[count_no++] = grank->clusters[i];
+
+ }
+
+ assert((count_2_left + count_2_right + count_no) == grank->count);
+
+ qsort_r(exit_2_left, count_2_left, sizeof(GGraphCluster *),
+ (__compar_d_fn_t)g_graph_cluster_compare_by_exit, (bool []){ false });
+
+ qsort_r(exit_2_right, count_2_right, sizeof(GGraphCluster *),
+ (__compar_d_fn_t)g_graph_cluster_compare_by_exit, (bool []){ true });
+
+ grank->count = 0;
+
+ for (i = 0; i < count_2_left; i++)
+ grank->clusters[grank->count++] = exit_2_left[i];
+
+ for (i = 0; i < count_no; i++)
+ grank->clusters[grank->count++] = no_exit[i];
+
+ for (i = 0; i < count_2_right; i++)
+ grank->clusters[grank->count++] = exit_2_right[i];
+
+ }
+
+ for (i = 0; i < grank->count; i++)
+ g_graph_cluster_reorder_exit_blocks(grank->clusters[i]);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : grank = ensemble de blocs de même rang à actualiser. *
* *
* Description : Réordonne les blocs de départ de boucle d'un ensemble. *
* *
@@ -2744,6 +2830,147 @@ static size_t g_graph_cluster_find_incoming_link(const GGraphCluster *cluster, c
/******************************************************************************
* *
+* Paramètres : cluster = graphique de blocs à analyser. *
+* l2r = indique si le lien trouvé part vers à droite. [OUT]*
+* *
+* Description : Détermine si un cluster possède un lien sortant. *
+* *
+* Retour : true si le chef de file à un lien qui sort de l'ensemble. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static bool g_graph_cluster_has_exit_link(GGraphCluster *cluster, bool *l2r)
+{
+ bool result; /* Bilan à retourner */
+ size_t i; /* Boucle de parcours */
+ leaving_link_t *leaving; /* Lien manipulé */
+ gint x1; /* Abscisse de départ de lien */
+ size_t idx; /* Indice du lien entrant */
+ gint x2; /* Abscisse d'arrivée de lien */
+
+ result = false;
+
+ for (i = 0; i < cluster->ba_count && !result; i++)
+ {
+ leaving = cluster->bottom_anchors[i];
+
+ if (leaving->cluster_exit)
+ {
+ result = true;
+
+ x1 = compute_leaving_link_position(leaving);
+
+ idx = g_graph_cluster_find_incoming_link(leaving->other->owner, leaving);
+
+ x2 = g_graph_cluster_compute_incoming_link_position(leaving->other->owner, idx);
+
+ *l2r = (x1 < x2);
+
+ }
+
+ }
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : cluster = premier graphique de blocs à analyser. *
+* other = second graphique de blocs à analyser. *
+* l2r = indique si le lien trouvé part vers à droite. *
+* *
+* Description : Compare deux clusters avec lien sortant. *
+* *
+* Retour : Bilan de la comparaison. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static int g_graph_cluster_compare_by_exit(const GGraphCluster **cluster, const GGraphCluster **other, const bool *l2r)
+{
+ int result; /* Bilan à renvoyer */
+ size_t i; /* Boucle de parcours */
+ gint cluster_y; /* Position de la sortie #0 */
+ gint other_y; /* Position de la sortie #1 */
+ leaving_link_t *leaving; /* Lien manipulé */
+
+ cluster_y = 0;
+ other_y = 0;
+
+ for (i = 0; i < (*cluster)->ba_count; i++)
+ {
+ leaving = (*cluster)->bottom_anchors[i];
+
+ if (leaving->cluster_exit)
+ {
+ cluster_y = leaving->other->owner->alloc.y;
+ break;
+ }
+
+ }
+
+ assert(i < (*cluster)->ba_count);
+
+ for (i = 0; i < (*other)->ba_count; i++)
+ {
+ leaving = (*other)->bottom_anchors[i];
+
+ if (leaving->cluster_exit)
+ {
+ other_y = leaving->other->owner->alloc.y;
+ break;
+ }
+
+ }
+
+ assert(i < (*other)->ba_count);
+
+ if (cluster_y < other_y)
+ result = -1;
+
+ else if (cluster_y > other_y)
+ result = 1;
+
+ else
+ result = 0;
+
+ if (*l2r)
+ result *= -1;
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : cluster = graphique de blocs à actualiser. *
+* *
+* Description : Réordonne les blocs sortant du cluster au mieux. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_graph_cluster_reorder_exit_blocks(GGraphCluster *cluster)
+{
+ size_t i; /* Boucle de parcours */
+
+ for (i = 0; i < cluster->ranks_count; i++)
+ reorder_graph_rank_exit_blocks(&cluster->ranks[i]);
+
+}
+
+
+/******************************************************************************
+* *
* Paramètres : cluster = graphique de blocs à actualiser. *
* *
* Description : Réordonne les blocs de départ de boucle au mieux. *
@@ -3910,6 +4137,21 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
g_graph_cluster_sort_incoming_links(result);
/**
+ * Comme des profondeurs de rang identiques peuvent renvoyer à des
+ * positions verticales différentes selon les chemins présents,
+ * on lance ici une réorganisation des blocs qui ont une sortie fuyante
+ * de leur ensemble parent en plaçant, même de façon parcellaire, l'ensemble
+ * des blocs.
+ *
+ * Une illustration concrête de cette nécessité est la fonction test_ite_2()
+ * de la suite de tests.
+ */
+
+ g_graph_cluster_set_y(result, 0);
+
+ g_graph_cluster_reorder_exit_blocks(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.
*
generated by cgit v0.11.2-87-g4458 at 2024-12-24 03:32:36 (GMT)