From 3cf2601f5d652037b79ca0cdaee051e4d9679c74 Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Fri, 21 Oct 2016 01:39:14 +0200 Subject: Extended the number of cases where beautiful graphs are produced. --- ChangeLog | 7 + src/gtkext/graph/cluster.c | 714 +++++++++++++++++++++++++++++++++++++-------- src/gtkext/graph/edge.c | 21 ++ src/gtkext/graph/edge.h | 3 + 4 files changed, 631 insertions(+), 114 deletions(-) diff --git a/ChangeLog b/ChangeLog index 1f6cfbf..62a1bc6 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,10 @@ +16-10-21 Cyrille Bagard + + * src/gtkext/graph/cluster.c: + * src/gtkext/graph/edge.c: + * src/gtkext/graph/edge.h: + Extend the number of cases where beautiful graphs are produced. + 16-10-18 Cyrille Bagard * src/gtkext/gtkgraphview.c: diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c index 4c92718..3e18f5f 100644 --- a/src/gtkext/graph/cluster.c +++ b/src/gtkext/graph/cluster.c @@ -26,6 +26,7 @@ #include #include +#include #include @@ -37,23 +38,49 @@ /* Définition du tracé d'un lien */ -typedef struct _link_def +typedef struct _incoming_edge { InstructionLinkType type; /* Complexité du tracé */ + const size_t *hslot; /* Couche horizontale réservée */ GdkPoint y; /* Position des décrochages */ - GdkPoint end; /* Point d'arrivée final */ GGraphEdge *edge; /* Lien complet en préparation */ -} link_def; + GGraphCluster *origin; /* Bloc de départ du lien */ + const size_t *leaving_index; /* Indice du point de départ */ + +} incoming_edge; + + +/* Détails sur le départ d'un lien */ +typedef struct _leaving_edge +{ + GdkPoint start; /* Point de départ d'un lien */ + size_t index; /* Indice sur ligne de départ */ + +} leaving_edge; + +/* Réservation pour les lignes horizontales */ +typedef struct _hspace_booking +{ + gint start; /* Abscisse de départ de ligne */ + size_t index; /* Indice de rangée verticale */ + +} hspace_booking; /* Découpage vertical */ typedef struct _graph_rank { unsigned int level; /* Niveau des blocs */ + hspace_booking **right2left; /* Réservations de D -> G */ + size_t r2l_count; /* Quantité de ces réservations*/ + + hspace_booking **left2right; /* Réservations de G -> D */ + size_t l2r_count; /* Quantité de ces réservations*/ + GGraphCluster **clusters; /* Ensembles de blocs */ size_t count; /* Nombre de ces ensembles */ @@ -64,6 +91,7 @@ struct _GGraphCluster { GObject parent; /* A laisser en premier */ + size_t *parent_index; /* Indice du lien au départ */ //////////////////////////////////////// gint top_margin[2]; /* Espaces gauches et droites */ @@ -72,16 +100,20 @@ struct _GGraphCluster //////////////////////////////////////// - link_def **top_anchors; /* Accroches supérieures */ + incoming_edge **top_anchors; /* Accroches supérieures */ size_t ta_count; /* Quantité de ces accroches */ GBasicBlock *block; /* Bloc d'origine représenté */ GtkWidget *view; /* Vue graphique associée */ GtkAllocation alloc; /* Emplacement final du bloc */ - GdkPoint **bottom_anchors; /* Accroches inférieures */ + leaving_edge **bottom_anchors; /* Accroches inférieures */ size_t ba_count; /* Quantité de ces accroches */ + bool has_straight; /* Présence d'une ligne droite */ + unsigned int straight_level; /* Rang atteint en ligne droite*/ + size_t straight_index; /* Indice du lien vertical */ + graph_rank *ranks; /* Répartition verticale */ size_t ranks_count; /* Nombre de divisions */ @@ -99,7 +131,7 @@ struct _GGraphClusterClass #define HORIZONTAL_MARGIN 20 /* Espace minimal vertical entre les blocs */ -#define VERTICAL_MARGIN 30 +#define VERTICAL_MARGIN 15 /* Espace minimal entre les liens */ #define LINK_MARGIN 10 @@ -142,8 +174,17 @@ static void g_graph_cluster_set_y(GGraphCluster *, gint); /* Met en place les embryons de liens nécessaires. */ static void g_graph_cluster_define_links(GGraphCluster *, GHashTable *); -/* Détermine les positions de tous les liens en place. */ -static void g_graph_cluster_compute_link_positions(GGraphCluster *); +/* Calcule l'abscisse d'un lien à son départ d'un bloc. */ +static gint g_graph_cluster_compute_leaving_link_position(const GGraphCluster *, size_t); + +/* Détermine les abscisses de tous les liens en place. */ +static void g_graph_cluster_compute_link_x_positions(GGraphCluster *); + +/* Réserve de l'espace vertical pour les lignes horizontales. */ +static void g_graph_cluster_book_hspace_for_links(GGraphCluster *); + +/* Détermine les ordonnées de tous les liens en place. */ +static void g_graph_cluster_compute_link_y_positions(GGraphCluster *); /* Applique les positions calculées pour chaque lien graphique. */ static void g_graph_cluster_resolve_links(const GGraphCluster *); @@ -324,7 +365,7 @@ static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub, unsigned int level; /* Niveau du nouvel ensemble */ size_t i; /* Boucle de parcours */ graph_rank new; /* Nouvel étage à insérer */ - graph_rank *rank; /* Nouvel étage à compléter */ + graph_rank *rank; /* Nouvel étage à compléter */ level = g_basic_block_get_rank(block); @@ -336,6 +377,12 @@ static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub, { new.level = level; + new.right2left = NULL; + new.r2l_count = 0; + + new.left2right = NULL; + new.l2r_count = 0; + new.clusters = (GGraphCluster **)calloc(1, sizeof(GGraphCluster *)); new.count = 1; @@ -389,9 +436,47 @@ static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub, static void g_graph_cluster_dispatch_x(GGraphCluster *cluster) { size_t k; /* Boucle de parcours #1 */ + const graph_rank *rank; /* Accès confortable au rang */ + size_t j; /* Boucle de parcours #2 */ + gint start; /* Position initiale de départ */ size_t rcount; /* Nombre d'ensembles présents */ size_t mid; /* Position centrale de départ */ - gint start; /* Position initiale de départ */ + + /** + * A ce point, tous les blocs parents 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 + * de la gauche ne doit pas arriver tout à droite ! + */ + + int compare_incoming_edges(const incoming_edge **a, const incoming_edge **b) + { + int result; /* Bilan à retourner */ + gint pos_a; /* Point de départ pour A */ + gint pos_b; /* Point de départ pour B */ + + pos_a = g_graph_cluster_compute_leaving_link_position((*a)->origin, *(*a)->leaving_index); + + pos_b = g_graph_cluster_compute_leaving_link_position((*b)->origin, *(*b)->leaving_index); + + if (pos_a < pos_b) + result = -1; + + else if (pos_a > pos_b) + result = 1; + + else + result = 0; + + return result; + + } + + qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_edge *), (__compar_fn_t)compare_incoming_edges); + + /** + * Il est désormais temps de placer tous les blocs de code inférieurs. + */ void place_sub(GGraphCluster **iter, size_t loop, gint base, int dir) { @@ -418,41 +503,80 @@ static void g_graph_cluster_dispatch_x(GGraphCluster *cluster) } - - for (k = 0; k < cluster->ranks_count; k++) { - rcount = cluster->ranks[k].count; + rank = &cluster->ranks[k]; - if (rcount % 2 == 1) + /* Répartition autour d'une ligne verticale */ + if (cluster->has_straight) { - if (rcount > 1) + start = g_graph_cluster_compute_leaving_link_position(cluster, cluster->straight_index); + + if (rank->level < cluster->straight_level) { - mid = rcount / 2; + /* Répartition à gauche du lien */ - start = cluster->ranks[k].clusters[mid]->alloc.x - HORIZONTAL_MARGIN; + for (j = rank->count; j > 0; j--) + if (*rank->clusters[j - 1]->parent_index < cluster->straight_index) + break; - place_sub(cluster->ranks[k].clusters + mid - 1, mid, start, -1); + start -= HORIZONTAL_MARGIN / 2; - start *= -1; + place_sub(rank->clusters, j, start, -1); + + /* Répartition à droite du lien */ + + for (j = 0; j < rank->count; j++) + if (*rank->clusters[j]->parent_index > cluster->straight_index) + break; - place_sub(cluster->ranks[k].clusters + mid + 1, mid, start, 1); + start += HORIZONTAL_MARGIN; + + place_sub(rank->clusters + j, rank->count - j, start, 1); } } + /* Répartition homogène */ else { - mid = rcount / 2 - 1; + rcount = rank->count; + + if (rcount % 2 == 1) + { + if (rcount > 1) + { + mid = rcount / 2; + + start = rank->clusters[mid]->alloc.x - HORIZONTAL_MARGIN; + + place_sub(rank->clusters + mid - 1, mid, start, -1); + + start *= -1; + + place_sub(rank->clusters + mid + 1, mid, start, 1); + + } - start = - HORIZONTAL_MARGIN / 2; + else + g_graph_cluster_dispatch_x(rank->clusters[0]); + + } + + else + { + mid = rcount / 2 - 1; + + start = - HORIZONTAL_MARGIN / 2; - place_sub(cluster->ranks[k].clusters + mid, mid + 1, start, -1); + place_sub(rank->clusters + mid, mid + 1, start, -1); - start *= -1; + start *= -1; - place_sub(cluster->ranks[k].clusters + mid + 1, mid + 1, start, 1); + place_sub(rank->clusters + mid + 1, mid + 1, start, 1); + + } } @@ -527,6 +651,7 @@ static void g_graph_cluster_offset_x(GGraphCluster *cluster, gint offset) static void g_graph_cluster_set_y(GGraphCluster *cluster, gint base) { size_t i; /* Boucle de parcours #1 */ + const graph_rank *rank; /* Accès simplifié à la rangée */ gint max; /* Hauteur maximale rencontrée */ size_t j; /* Boucle de parcours #2 */ GGraphCluster *sub; /* Sous-ensemble traité */ @@ -538,13 +663,34 @@ static void g_graph_cluster_set_y(GGraphCluster *cluster, gint base) for (i = 0; i < cluster->ranks_count; i++) { + rank = &cluster->ranks[i]; + + /* On ajoute l'espace vertical pour les lignes horizontales */ + + if (rank->r2l_count > rank->l2r_count) + max = rank->r2l_count; + else + max = rank->l2r_count; + + base += VERTICAL_MARGIN; + + /** + * Comme les liens purement verticaux n'entrainent pas de réservation, + * il n'y a potentiellement pas toujours d'espace à ajouter. + */ + + if (max > 0) + base += ((max - 1) * LINK_MARGIN); + + /* On ajoute l'espace requis pour l'affichage des blocs */ + base += VERTICAL_MARGIN; max = 0; - for (j = 0; j < cluster->ranks[i].count; j++) + for (j = 0; j < rank->count; j++) { - sub = cluster->ranks[i].clusters[j]; + sub = rank->clusters[j]; g_graph_cluster_set_y(sub, base); @@ -756,18 +902,23 @@ static GGraphCluster *g_graph_cluster_find_lower_dest_cluster(const GGraphCluste static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all) { + unsigned int level; /* Niveau du nouvel ensemble */ GArchInstruction *last; /* Dernière instruction du bloc*/ GArchInstruction **dests; /* Instr. visée par une autre */ InstructionLinkType *types; /* Type de lien entre lignes */ size_t dcount; /* Nombre de liens de dest. */ size_t i; /* Boucle de parcours #1 */ GGraphCluster *target; /* Bloc ciblé par un lien */ - GdkPoint *start; /* Point de départ d'un lien */ - link_def *end; /* Définitions d'arrivée */ + leaving_edge *leaving; /* Point de départ d'un lien */ + unsigned int target_level; /* Rang du bloc ciblé */ size_t j; /* Boucle de parcours #2 */ + size_t k; /* Boucle de parcours #3 */ + incoming_edge *incoming; /* Définitions d'arrivée */ /* Au niveau du bloc courant */ + level = g_basic_block_get_rank(cluster->block); + g_basic_block_get_boundary(cluster->block, NULL, &last); g_arch_instruction_rlock_dest(last); @@ -787,32 +938,80 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all /* Point de départ */ - start = (GdkPoint *)calloc(1, sizeof(GdkPoint)); + leaving = (leaving_edge *)calloc(1, sizeof(leaving_edge)); + + cluster->bottom_anchors = (leaving_edge **)realloc(cluster->bottom_anchors, + ++cluster->ba_count * sizeof(leaving_edge *)); + cluster->bottom_anchors[cluster->ba_count - 1] = leaving; + + /* Est-ce un lien qui doit être vertical ? */ + + + /* FIXME : trop de boucles ! */ + + target_level = -1; + + for (j = 0; j < cluster->ranks_count && target_level == -1; j++) + for (k = 0; k < cluster->ranks[j].count && target_level == -1; k++) + if (cluster->ranks[j].clusters[k] == target) + { + target_level = cluster->ranks[j].level; + + if (target_level > (level + 1) && target_level > cluster->straight_level) + { + cluster->has_straight = true; + cluster->straight_level = target_level; + cluster->straight_index = cluster->ba_count - 1; + } + + } + + + + - cluster->bottom_anchors = (GdkPoint **)realloc(cluster->bottom_anchors, - ++cluster->ba_count * sizeof(GdkPoint *)); - cluster->bottom_anchors[cluster->ba_count - 1] = start; /* Point d'arrivée */ - end = (link_def *)calloc(1, sizeof(link_def)); + incoming = (incoming_edge *)calloc(1, sizeof(incoming_edge)); - target->top_anchors = (link_def **)realloc(target->top_anchors, - ++target->ta_count * sizeof(link_def *)); - target->top_anchors[target->ta_count - 1] = end; + target->top_anchors = (incoming_edge **)realloc(target->top_anchors, + ++target->ta_count * sizeof(incoming_edge *)); + target->top_anchors[target->ta_count - 1] = incoming; /* Etablissement d'un embryon de lien */ - end->type = types[i]; + leaving->index = cluster->ba_count - 1; + + incoming->type = types[i]; if (types[i] == ILT_JUMP_IF_TRUE) - end->edge = g_graph_edge_new_true(start, &end->y, &end->end); + incoming->edge = g_graph_edge_new_true(&leaving->start, &incoming->y, &incoming->end); else if (types[i] == ILT_JUMP_IF_FALSE) - end->edge = g_graph_edge_new_false(start, &end->y, &end->end); + incoming->edge = g_graph_edge_new_false(&leaving->start, &incoming->y, &incoming->end); else - end->edge = g_graph_edge_new(start, &end->y, &end->end); + incoming->edge = g_graph_edge_new(&leaving->start, &incoming->y, &incoming->end); + + incoming->origin = cluster; + incoming->leaving_index = &leaving->index; + + + /* FIXME : trop de boucles ! */ + + target_level = -1; + + for (j = 0; j < cluster->ranks_count && target_level == -1; j++) + for (k = 0; k < cluster->ranks[j].count && target_level == -1; k++) + if (cluster->ranks[j].clusters[k] == target) + { + target_level = 0; + target->parent_index = &leaving->index; + } + + + break; @@ -820,7 +1019,7 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all case ILT_LOOP: /* TODO */ - assert(false); + //assert(false); break; @@ -831,6 +1030,57 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all g_arch_instruction_runlock_dest(last); + + + + /* Déplacement d'un éventuel lien central */ + + if (cluster->has_straight) + { + size_t center; + leaving_edge *tmp; + + if (cluster->ba_count % 2 == 0) + center = cluster->ba_count / 2 - 1; + else + center = cluster->ba_count / 2; + + if (cluster->straight_index < center) + { + tmp = cluster->bottom_anchors[cluster->straight_index]; + + memmove(cluster->bottom_anchors + cluster->straight_index, + cluster->bottom_anchors + cluster->straight_index + 1, + (center - cluster->straight_index) * sizeof(leaving_edge *)); + + cluster->bottom_anchors[center] = tmp; + + for (i = cluster->straight_index; i <= center; i++) + cluster->bottom_anchors[i]->index = i; + + cluster->straight_index = center; + + } + + else if (cluster->straight_index > center) + { + tmp = cluster->bottom_anchors[cluster->straight_index]; + + memmove(cluster->bottom_anchors + center + 1, + cluster->bottom_anchors + center, + (cluster->straight_index - center) * sizeof(leaving_edge *)); + + cluster->bottom_anchors[center] = tmp; + + for (i = center; i <= cluster->straight_index ; i++) + cluster->bottom_anchors[i]->index = i; + + cluster->straight_index = center; + + } + + } + /* Propagation de la mise en place */ for (i = 0; i < cluster->ranks_count; i++) @@ -842,60 +1092,113 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all /****************************************************************************** * * -* Paramètres : cluster = graphique de blocs à actualiser. * +* Paramètres : cluster = graphique de blocs à consulter. * +* index = indice du lien à considérer. * * * -* Description : Détermine les positions de tous les liens en place. * +* Description : Calcule l'abscisse d'un lien à son départ d'un bloc. * * * -* Retour : - * +* Retour : Abscisse à attribuer à un départ de lien. * * * * Remarques : - * * * ******************************************************************************/ -static void g_graph_cluster_compute_link_positions(GGraphCluster *cluster) +static gint g_graph_cluster_compute_leaving_link_position(const GGraphCluster *cluster, size_t index) { + gint result; /* Position à retourner */ gint mid_x; /* Abscisse centrale */ size_t half; /* Indice de répartition égale */ - gint y; /* Ordonnée d'application */ + assert(index < cluster->ba_count); + + mid_x = cluster->alloc.x + (cluster->alloc.width / 2); + + half = cluster->ba_count / 2; + + if (cluster->ba_count % 2 == 1) + { + if (index < half) + result = mid_x - (half - index) * LINK_MARGIN; + + else if (index == half) + result = mid_x; + + else + result = mid_x + (index - half) * LINK_MARGIN; + + } + + else + { + if (index < half) + result = mid_x - LINK_MARGIN / 2 - (half - index - 1) * LINK_MARGIN; + + else + result = mid_x + LINK_MARGIN / 2 + (index - half) * LINK_MARGIN; + + } + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à actualiser. * +* * +* Description : Détermine les abscisses de tous les liens en place. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_compute_link_x_positions(GGraphCluster *cluster) +{ + gint mid_x; /* Abscisse centrale */ size_t i; /* Boucle de parcours #1 */ + size_t half; /* Indice de répartition égale */ GdkPoint *pt; /* Point à actualiser */ size_t j; /* Boucle de parcours #2 */ - - mid_x = cluster->alloc.x + (cluster->alloc.width / 2); /* Du côté des départs... */ if (cluster->ba_count > 0) - { - half = cluster->ba_count / 2; + for (i = 0; i < cluster->ba_count; i++) + { + pt = &cluster->bottom_anchors[i]->start; - y = cluster->alloc.y + cluster->alloc.height; + pt->x = g_graph_cluster_compute_leaving_link_position(cluster, i); + + } + + /* Du côté des arrivées... */ + + if (cluster->ta_count > 0) + { + half = cluster->ta_count / 2; - if (cluster->ba_count % 2 == 1) + if (cluster->ta_count % 2 == 1) { for (i = half; i > 0; i--) { - pt = cluster->bottom_anchors[i - 1]; + pt = &cluster->top_anchors[i - 1]->end; pt->x = mid_x - (half - i + 1) * LINK_MARGIN; - pt->y = y; } - pt = cluster->bottom_anchors[half]; - - pt->x = mid_x; - pt->y = y; + cluster->top_anchors[half]->end.x = mid_x; - for (i = half + 1; i < cluster->ba_count; i++) + for (i = half + 1; i < cluster->ta_count; i++) { - pt = cluster->bottom_anchors[i]; + pt = &cluster->top_anchors[i]->end; pt->x = mid_x + (i - half) * LINK_MARGIN; - pt->y = y; } @@ -905,19 +1208,17 @@ static void g_graph_cluster_compute_link_positions(GGraphCluster *cluster) { for (i = half; i > 0; i--) { - pt = cluster->bottom_anchors[i - 1]; + pt = &cluster->top_anchors[i - 1]->end; pt->x = mid_x - LINK_MARGIN / 2 - (half - i) * LINK_MARGIN; - pt->y = y; } - for (i = half; i < cluster->ba_count; i++) + for (i = half; i < cluster->ta_count; i++) { - pt = cluster->bottom_anchors[i]; + pt = &cluster->top_anchors[i]->end; pt->x = mid_x + LINK_MARGIN / 2 + (half - i) * LINK_MARGIN; - pt->y = y; } @@ -925,78 +1226,191 @@ static void g_graph_cluster_compute_link_positions(GGraphCluster *cluster) } - /* Du côté des arrivées... */ + /* Propagation des déterminations */ - if (cluster->ta_count > 0) + for (i = 0; i < cluster->ranks_count; i++) + for (j = 0; j < cluster->ranks[i].count; j++) + g_graph_cluster_compute_link_x_positions(cluster->ranks[i].clusters[j]); + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à traiter. * +* * +* Description : Réserve de l'espace vertical pour les lignes horizontales. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_book_hspace_for_links(GGraphCluster *cluster) +{ + size_t i; /* Boucle de parcours #1 */ + graph_rank *rank; /* Rangée à manipuler */ + size_t j; /* Boucle de parcours #2 */ + GGraphCluster *sub; /* Bloc inférieur à manipuler */ + size_t k; /* Boucle de parcours #3 */ + gint x1; /* Abscisse de départ de lien */ + gint x2; /* Abscisse d'arrivée de lien */ + hspace_booking *new; /* Nouvelle réservation */ + + for (i = 0; i < cluster->ranks_count; i++) { - half = cluster->ta_count / 2; + rank = &cluster->ranks[i]; - y = cluster->alloc.y; + /* Enregistrement des besoins */ - if (cluster->ta_count % 2 == 1) + for (j = 0; j < rank->count; j++) { - for (i = half; i > 0; i--) + sub = rank->clusters[j]; + + for (k = 0; k < sub->ta_count; k++) { - pt = &cluster->top_anchors[i - 1]->end; + g_graph_edge_get_x_borders(sub->top_anchors[k]->edge, &x1, &x2); - pt->x = mid_x - (half - i + 1) * LINK_MARGIN; - pt->y = y; + if (x1 > x2) + { + new = (hspace_booking *)calloc(1, sizeof(hspace_booking)); - } + new->start = x1; + sub->top_anchors[k]->hslot = &new->index; - pt = &cluster->top_anchors[half]->end; + int compare_right_to_left(const hspace_booking **a, const hspace_booking **b) + { + int result; /* Bilan à retourner */ - pt->x = mid_x; - pt->y = y; + if ((*a)->start > (*b)->start) + result = -1; - for (i = half + 1; i < cluster->ta_count; i++) - { - pt = &cluster->top_anchors[i]->end; + else if ((*a)->start < (*b)->start) + result = 1; - pt->x = mid_x + (i - half) * LINK_MARGIN; - pt->y = y; + else + { + assert(false); + result = 0; + } - } + return result; - } + } - else - { - for (i = half; i > 0; i--) - { - pt = &cluster->top_anchors[i - 1]->end; + rank->right2left = qinsert(rank->right2left, &rank->r2l_count, + sizeof(hspace_booking *), + (__compar_fn_t)compare_right_to_left, &new); - pt->x = mid_x - LINK_MARGIN / 2 - (half - i) * LINK_MARGIN; - pt->y = y; + } - } + else if (x1 < x2) + { + new = (hspace_booking *)calloc(1, sizeof(hspace_booking)); - for (i = half; i < cluster->ta_count; i++) - { - pt = &cluster->top_anchors[i]->end; + new->start = x1; + sub->top_anchors[k]->hslot = &new->index; - pt->x = mid_x + LINK_MARGIN / 2 + (half - i) * LINK_MARGIN; - pt->y = y; + int compare_left_to_right(const hspace_booking **a, const hspace_booking **b) + { + int result; /* Bilan à retourner */ + + if ((*a)->start < (*b)->start) + result = -1; + + else if ((*a)->start > (*b)->start) + result = 1; + + else + { + assert(false); + result = 0; + } + + return result; + + } + + rank->left2right = qinsert(rank->left2right, &rank->l2r_count, + sizeof(hspace_booking *), + (__compar_fn_t)compare_left_to_right, &new); + + } + + else + sub->top_anchors[k]->hslot = NULL; } } + /* Définition des couches */ + for (j = 0; j < rank->r2l_count; j++) + rank->right2left[j]->index = j; + for (j = 0; j < rank->l2r_count; j++) + rank->left2right[j]->index = j; + /* Propagation des déterminations */ + for (j = 0; j < rank->count; j++) + g_graph_cluster_book_hspace_for_links(rank->clusters[j]); + } +} - for (i = 0; i < cluster->ta_count; i++) - cluster->top_anchors[i]->y.y = cluster->top_anchors[i]->end.y - 18; +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à actualiser. * +* * +* Description : Détermine les ordonnées de tous les liens en place. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_compute_link_y_positions(GGraphCluster *cluster) +{ + gint y; /* Ordonnée d'application */ + size_t i; /* Boucle de parcours #1 */ + incoming_edge *incoming; /* Raccourci pour le confort */ + size_t j; /* Boucle de parcours #2 */ + + /* Du côté des départs... */ + if (cluster->ba_count > 0) + { + y = cluster->alloc.y + cluster->alloc.height; + for (i = 0; i < cluster->ba_count; i++) + cluster->bottom_anchors[i]->start.y = y; + } + /* Du côté des arrivées... */ + if (cluster->ta_count > 0) + { + y = cluster->alloc.y; + + for (i = 0; i < cluster->ta_count; i++) + { + incoming = cluster->top_anchors[i]; + + incoming->end.y = y; + + incoming->y.y = incoming->end.y - VERTICAL_MARGIN; + + if (incoming->hslot != NULL) + incoming->y.y -= *incoming->hslot * LINK_MARGIN; + + } } @@ -1004,7 +1418,7 @@ static void g_graph_cluster_compute_link_positions(GGraphCluster *cluster) for (i = 0; i < cluster->ranks_count; i++) for (j = 0; j < cluster->ranks[i].count; j++) - g_graph_cluster_compute_link_positions(cluster->ranks[i].clusters[j]); + g_graph_cluster_compute_link_y_positions(cluster->ranks[i].clusters[j]); } @@ -1124,8 +1538,6 @@ static GGraphCluster *setup_graph_clusters(GLoadedBinary *binary, const GBlockLi g_arch_instruction_rlock_dest(last); dcount = g_arch_instruction_get_destinations(last, &dests, &types, NULL); - printf(" ... block=%p dest=%zu\n", block, dcount); - for (i = 0; i < dcount; i++) switch (types[i]) { @@ -1158,9 +1570,33 @@ static GGraphCluster *setup_graph_clusters(GLoadedBinary *binary, const GBlockLi if (j == pending->count) { - assert((pending->count + 1) < g_block_list_count_blocks(list)); - pending->list[pending->count++] = target; - printf(" --push-- %d -> %p\n", types[i], target); + /** + * Il faut vérifier ici si la destination n'a pas déjà été + * empruntée, sauf peine de faire réagir l'assertion plus + * haut au moment de l'insertion. + * + * Le type de code à problème est le suivant : + * + * ... + * if (...) + * ... + * ... + * + * Le code suivant le bloc conditionnel a deux origines, + * qui vont chacune poursuivre le traitement vers ce code + * commun. + * + * Et comme les origines ne sont pas dominantes, on utilise + * la table globale. + */ + + if (!g_hash_table_contains(all, dests[i])) + { + assert((pending->count + 1) < g_block_list_count_blocks(list)); + pending->list[pending->count++] = target; + printf(" --push-- %d -> %p\n", types[i], target); + } + } do @@ -1266,12 +1702,15 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList * - +#if 0 do { size_t i; GBasicBlock *block; const bitfield_t *domination; + GArchInstruction *first; /* Première instruction du bloc*/ + GArchInstruction *last; /* Dernière instruction du bloc*/ + printf("DBG // count : %zu\n", count); @@ -1280,8 +1719,12 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList * block = g_block_list_get_block(list, i); domination = g_basic_block_get_domination(block); - printf("DBG // block [%zu] : 0x%08lx -- rank = %u\n", - i, gfw(domination), g_basic_block_get_rank(block)); + g_basic_block_get_boundary(block, &first, &last); + + printf("DBG // block [%zu] @ 0x%08x : 0x%08lx -- rank = %u\n", + i, + (unsigned int)first->range.addr.virtual, + gfw(domination), g_basic_block_get_rank(block)); } @@ -1292,6 +1735,39 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList * + void show_tree(GGraphCluster *cluster, int depth) + { + int i; + GArchInstruction *first; + size_t j; + size_t k; + + printf("TREE | "); + + for (i = 0; i < depth; i++) + printf(" "); + + g_basic_block_get_boundary(cluster->block, &first, NULL); + + printf("cluster @ 0x%08x\n", (unsigned int)first->range.addr.virtual); + + for (j = 0; j < cluster->ranks_count; j++) + { + printf("TREE | "); + + for (i = 0; i < depth; i++) + printf(" "); + + printf(" + rank %u +\n", cluster->ranks[j].level); + + for (k = 0; k < cluster->ranks[j].count; k++) + show_tree(cluster->ranks[j].clusters[k], depth + 1); + + } + + + } +#endif result = setup_graph_clusters(binary, list, 0, highlighted, pending, all); @@ -1300,12 +1776,16 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList * g_graph_cluster_define_links(result, all); + + //show_tree(result, 0); + //printf("--------------\n"); + + + /* Positionnements dans l'espace */ g_graph_cluster_dispatch_x(result); - g_graph_cluster_set_y(result, 0); - /* Réajustement vers la droite */ g_graph_cluster_compute_needed_alloc(result, &needed); @@ -1314,7 +1794,13 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList * /* Application finale sur les liens */ - g_graph_cluster_compute_link_positions(result); + g_graph_cluster_compute_link_x_positions(result); + + g_graph_cluster_book_hspace_for_links(result); + + g_graph_cluster_set_y(result, 0); + + g_graph_cluster_compute_link_y_positions(result); g_graph_cluster_resolve_links(result); diff --git a/src/gtkext/graph/edge.c b/src/gtkext/graph/edge.c index a917cc3..ab3a666 100644 --- a/src/gtkext/graph/edge.c +++ b/src/gtkext/graph/edge.c @@ -205,6 +205,27 @@ GGraphEdge *_g_graph_edge_new(const GdkPoint *start, const GdkPoint **mid, size_ /****************************************************************************** * * +* Paramètres : edge = ligne de rendu à consulter. * +* x1 = abscisse du point de départ de la ligne. [OUT] * +* x2 = abscisse du point d'arrivée de la ligne. [OUT] * +* * +* Description : Fournit les abscisses des points extrèmes de la ligne. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void g_graph_edge_get_x_borders(const GGraphEdge *edge, gint *x1, gint *x2) +{ + *x1 = edge->start->x; + *x2 = edge->end->x; +} + + +/****************************************************************************** +* * * Paramètres : edge = ligne de rendu à définir dans les détails. * * * * Description : Détermine les positions finales d'un lien graphique. * diff --git a/src/gtkext/graph/edge.h b/src/gtkext/graph/edge.h index 602c559..e2237c3 100644 --- a/src/gtkext/graph/edge.h +++ b/src/gtkext/graph/edge.h @@ -75,6 +75,9 @@ GGraphEdge *_g_graph_edge_new(const GdkPoint *, const GdkPoint **, size_t, const #define g_graph_edge_new_false(start, y, end) \ _g_graph_edge_new(start, (const GdkPoint *[]) { y }, 1, end, EGC_RED) +/* Fournit les abscisses des points extrèmes de la ligne. */ +void g_graph_edge_get_x_borders(const GGraphEdge *, gint *, gint *); + /* Détermine les positions finales d'un lien graphique. */ void g_graph_edge_resolve(GGraphEdge *); -- cgit v0.11.2-87-g4458