From 63b4cb46d5f417798619c573be34104fea7acbae Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Tue, 5 Mar 2019 19:49:52 +0100 Subject: Saved extra code block reordering in the graph view. --- src/gtkext/graph/cluster.c | 250 ++++++++++++++++++++++++++++++++++++++++++++- 1 file 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. * -- cgit v0.11.2-87-g4458