From e363028265c5d1ab9905dee4128b8d998dad06b1 Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Mon, 7 Jan 2019 08:52:28 +0100 Subject: Improved links computation and handled loops in the graph layout. --- src/gtkext/graph/cluster.c | 783 ++++++++++++++++++++++++++++++++++++++----- src/gtkext/graph/edge.c | 71 ++-- src/gtkext/graph/edge.h | 18 +- src/gtkext/gtkgraphdisplay.c | 2 +- 4 files changed, 733 insertions(+), 141 deletions(-) diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c index d21818a..8053e54 100644 --- a/src/gtkext/graph/cluster.c +++ b/src/gtkext/graph/cluster.c @@ -46,7 +46,7 @@ typedef struct _leaving_link_t { GGraphCluster *owner; /* Propriétés du lien */ - GdkPoint start; /* Point de départ d'un lien */ + GdkPoint start[2]; /* Point de départ d'un lien */ size_t index; /* Indice sur ligne de départ */ } leaving_link_t; @@ -74,21 +74,20 @@ typedef struct _incoming_link_t 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 */ + GdkPoint end[2]; /* Point d'arrivée final */ GGraphEdge *edge; /* Lien complet en préparation */ - const leaving_link_t *other; /* Autre extrémité du lien */ + leaving_link_t *other; /* Autre extrémité du lien */ } incoming_link_t; /* Crée un point d'attache pour un lien entrant simple. */ -static incoming_link_t *create_incoming_link(GGraphCluster *, InstructionLinkType, const leaving_link_t *); +static incoming_link_t *create_incoming_link(GGraphCluster *, InstructionLinkType, leaving_link_t *); /* Crée un point d'attache pour un lien entrant de boucle. */ -static incoming_link_t *create_incoming_loop_link(GGraphCluster *, const leaving_link_t *); +static incoming_link_t *create_incoming_loop_link(GGraphCluster *, const GdkPoint *, leaving_link_t *); /* Détruit un point d'attache pour un lien entrant. */ static void delete_incoming_link(incoming_link_t *); @@ -141,6 +140,9 @@ static void init_graph_rank(graph_rank_t *, GGraphCluster *); /* Termine la gestion d'un ensemble de blocs de même rang. */ static void exit_graph_rank(graph_rank_t *); +/* Assigne à un ensemble de blocs un emplacement initial. */ +static void reset_graph_rank_allocation(const graph_rank_t *); + /* Fournit le rang d'un ensemble de blocs. */ static size_t get_graph_rank(const graph_rank_t *); @@ -165,6 +167,9 @@ static void _place_graph_rank_clusters(GGraphCluster **, size_t, gint, int); /* Organise la disposition d'un ensemble de blocs basiques. */ 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(const graph_rank_t *); + /* Décale vers la droite un ensemble de blocs basiques. */ static void offset_x_graph_rank(const graph_rank_t *, gint); @@ -182,7 +187,7 @@ typedef struct _vspace_booking_t leaving_link_t *from; /* Bloc de départ du lien */ incoming_link_t *to; /* Bloc d'arrivée du lien */ - GdkPoint pts[2]; /* Coordonnées des points */ + GdkPoint *pts; /* Coordonnées des points */ } vspace_booking_t; @@ -207,6 +212,21 @@ static void init_vspace_manager(vspace_manager_t *); /* Termine les réservations liens verticaux. */ static void exit_vspace_manager(vspace_manager_t *); +/* Inscrit une nouvelle réservation d'espace latéral. */ +static void extend_vspace_manager(vspace_manager_t *, leaving_link_t *, incoming_link_t *, GdkPoint *); + +/* Détermine l'emplacement requis pour les espaces latéraux. */ +static void compute_vspace_manager_needed_alloc(const vspace_manager_t *, bool, bool, GtkAllocation *); + +/* Réorganise au besoin les liens de boucle entre blocs. */ +static void sort_incoming_links_for_vspace_manager(vspace_manager_t *); + +/* Détermine les abscisses de tous les liens en place. */ +static void compute_loop_link_x_with_vspace_manager(vspace_manager_t *, bool, GGraphCluster *); + +/* Détermine les ordonnées de tous les liens en place. */ +static void compute_loop_link_y_with_vspace_manager(vspace_manager_t *, GGraphCluster *); + /* -------------------------- DEFINITION D'UN CHEF DE FILE -------------------------- */ @@ -217,6 +237,7 @@ struct _GGraphCluster { GObject parent; /* A laisser en premier */ + GGraphCluster *owner; /* Ensemble lié parent */ size_t *parent_index; /* Indice du lien au départ */ //////////////////////////////////////// @@ -277,6 +298,9 @@ static void g_graph_cluster_dispose(GGraphCluster *); /* Procède à la libération totale de la mémoire. */ static void g_graph_cluster_finalize(GGraphCluster *); +/* Assigne à un bloc et son ensemble un emplacement initial. */ +static void g_graph_cluster_reset_allocation(GGraphCluster *); + /* Complète un graphique avec un sous-ensemble de blocs. */ static void g_graph_cluster_add_sub(GGraphCluster *, GGraphCluster *); @@ -286,22 +310,30 @@ static void g_graph_cluster_define_links(GGraphCluster *, GHashTable *); /* Organise la disposition d'un ensemble de blocs basiques. */ static void g_graph_cluster_dispatch_x(GGraphCluster *); +/* Réorganise au besoin les liens entrants d'un bloc. */ +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écale vers la droite un ensemble de blocs basiques. */ static void g_graph_cluster_offset_x(GGraphCluster *, gint); /* Décale vers le bas un ensemble de blocs basiques. */ static void g_graph_cluster_set_y(GGraphCluster *, gint); - - - - -/* Recherche le bloc basique à l'extrémité d'un lien. */ -//static GGraphCluster *g_graph_cluster_find_lower_dest_cluster(const GGraphCluster *, const GArchInstruction *); +/* Calcule l'abscisse d'un lien pour un bloc. */ +static gint _g_graph_cluster_compute_link_position(const GGraphCluster *, size_t, size_t, bool); /* 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); +/* Calcule l'abscisse d'un lien à son arrivée à un bloc. */ +static gint g_graph_cluster_compute_incoming_link_position(const GGraphCluster *, size_t); + +/* Détermine les abscisses des liens de boucle en place. */ +static void g_graph_cluster_compute_loop_link_x_positions(GGraphCluster *); + /* Détermine les abscisses de tous les liens en place. */ static void g_graph_cluster_compute_link_x_positions(GGraphCluster *); @@ -428,7 +460,7 @@ static gint compute_leaving_link_position(const leaving_link_t *link) * * ******************************************************************************/ -static incoming_link_t *create_incoming_link(GGraphCluster *owner, InstructionLinkType type, const leaving_link_t *other) +static incoming_link_t *create_incoming_link(GGraphCluster *owner, InstructionLinkType type, leaving_link_t *other) { incoming_link_t *result; /* Structure à retourner */ @@ -439,13 +471,13 @@ static incoming_link_t *create_incoming_link(GGraphCluster *owner, InstructionLi result->type = type; if (type == ILT_JUMP_IF_TRUE) - result->edge = g_graph_edge_new_true(&other->start, &result->y, &result->end); + result->edge = g_graph_edge_new_true(&other->start[0], &other->start[1], &result->end[0], &result->end[1]); else if (type == ILT_JUMP_IF_FALSE) - result->edge = g_graph_edge_new_false(&other->start, &result->y, &result->end); + result->edge = g_graph_edge_new_false(&other->start[0], &other->start[1], &result->end[0], &result->end[1]); else - result->edge = g_graph_edge_new(&other->start, &result->y, &result->end); + result->edge = g_graph_edge_new(&other->start[0], &other->start[1], &result->end[0], &result->end[1]); result->other = other; @@ -467,7 +499,7 @@ static incoming_link_t *create_incoming_link(GGraphCluster *owner, InstructionLi * * ******************************************************************************/ -static incoming_link_t *create_incoming_loop_link(GGraphCluster *owner, const leaving_link_t *other) +static incoming_link_t *create_incoming_loop_link(GGraphCluster *owner, const GdkPoint *midpts, leaving_link_t *other) { incoming_link_t *result; /* Structure à retourner */ @@ -477,7 +509,9 @@ static incoming_link_t *create_incoming_loop_link(GGraphCluster *owner, const le result->type = ILT_LOOP; - result->edge = g_graph_edge_new_loop(&other->start, &other->start, &result->y, &result->end); + result->edge = g_graph_edge_new_loop(&other->start[0], &other->start[1], + &midpts[0], &midpts[1], + &result->end[0], &result->end[1]); result->other = other; @@ -709,6 +743,28 @@ static void exit_graph_rank(graph_rank_t *grank) * * * Paramètres : grank = ensemble de même rang à consulter. * * * +* Description : Assigne à un ensemble de blocs un emplacement initial. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void reset_graph_rank_allocation(const graph_rank_t *grank) +{ + size_t i; /* Boucle de parcours */ + + for (i = 0; i < grank->count; i++) + g_graph_cluster_reset_allocation(grank->clusters[i]); + +} + + +/****************************************************************************** +* * +* Paramètres : grank = ensemble de même rang à consulter. * +* * * Description : Fournit le rang d'un ensemble de blocs. * * * * Retour : Rang d'un ensemble de blocs de même rang. * @@ -925,6 +981,39 @@ static void compute_graph_rank_needed_alloc(const graph_rank_t *grank, bool last /****************************************************************************** * * +* Paramètres : grank = ensemble de descendants d'un même rang. * +* * +* Description : Indique si un espace horizontal final est prévu en bas. * +* * +* Retour : true si l'étage comporte une zone pour liens de boucle. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static bool has_graph_rank_ending_vspace(const graph_rank_t *grank) +{ + bool result; /* Bilan à retourner */ + size_t i; /* Boucle de parcours */ + GGraphCluster *cluster; /* Bloc à analyser */ + + result = false; + + for (i = 0; i < grank->count && !result; i++) + { + cluster = grank->clusters[i]; + + result = (cluster->vspaces.pending_count > 0); + + } + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : iter = début de la boucle de parcours. * * loop = nombre d'itérations à mener. * * base = position de base sur l'axe des abscisses. * @@ -1021,6 +1110,28 @@ static void dispatch_x_graph_rank(const graph_rank_t *grank) /****************************************************************************** * * * Paramètres : grank = ensemble de blocs de même rang à actualiser. * +* * +* Description : Réorganise au besoin les liens entrants un ensemble de blocs.* +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void sort_graph_rank_incoming_links(const graph_rank_t *grank) +{ + size_t i; /* Boucle de parcours */ + + for (i = 0; i < grank->count; i++) + g_graph_cluster_sort_incoming_links(grank->clusters[i]); + +} + + +/****************************************************************************** +* * +* Paramètres : grank = ensemble de blocs de même rang à actualiser. * * offset = décalage à appliquer. * * * * Description : Décale vers la droite un ensemble de blocs basiques. * @@ -1149,6 +1260,11 @@ static void init_vspace_manager(vspace_manager_t *manager) static void exit_vspace_manager(vspace_manager_t *manager) { + size_t i; /* Boucle de parcours */ + + for (i = 0; i < manager->pending_count; i++) + free(manager->pending[i].pts); + if (manager->pending != NULL) free(manager->pending); @@ -1161,6 +1277,261 @@ static void exit_vspace_manager(vspace_manager_t *manager) } +/****************************************************************************** +* * +* Paramètres : manager = structure à compléter. * +* from = point de départ du lien concerné. * +* to = point d'arrivée du lien concerné. * +* pts = points intermédiaires du tracé complet final. * +* * +* Description : Inscrit une nouvelle réservation d'espace latéral. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void extend_vspace_manager(vspace_manager_t *manager, leaving_link_t *from, incoming_link_t *to, GdkPoint *pts) +{ + vspace_booking_t *new; /* Réservation à constituer */ + + manager->pending = realloc(manager->pending, ++manager->pending_count * sizeof(vspace_booking_t)); + + new = &manager->pending[manager->pending_count - 1]; + + new->from = from; + new->to = to; + + new->pts = pts; + +} + + +/****************************************************************************** +* * +* Paramètres : manager = gestion des espaces latéraux à consulter. * +* top = le bloc courant est-il le principal ? * +* concat = la zone inférieuse s'ajoute à une similaire ? * +* alloc = emplacement idéal pour l'affichage. [OUT] * +* * +* Description : Détermine l'emplacement requis pour les espaces latéraux. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void compute_vspace_manager_needed_alloc(const vspace_manager_t *manager, bool top, bool concat, GtkAllocation *alloc) +{ + gint width; /* Largeur supplémentaire */ + + /* Extension de la largeur */ + + width = 0; + + if (manager->left_count > 0) + { + if (!top) + width += HORIZONTAL_MARGIN; + + width += (manager->left_count - 1) * LINK_MARGIN; + + width += HORIZONTAL_MARGIN; + + } + + if (manager->right_count > 0) + { + width += HORIZONTAL_MARGIN; + + width += (manager->right_count - 1) * LINK_MARGIN; + + if (!top) + width += HORIZONTAL_MARGIN; + + } + + alloc->x -= width / 2; + alloc->width += width; + + /* Extension de la hauteur */ + + if (manager->pending_count > 0) + { + if (!concat) + alloc->height += VERTICAL_MARGIN; + + alloc->height += (manager->pending_count - 1) * LINK_MARGIN; + + alloc->height += VERTICAL_MARGIN; + + } + +} + + +/****************************************************************************** +* * +* Paramètres : manager = gestion d'espaces latéraux à manipuler. * +* * +* Description : Réorganise au besoin les liens de boucle entre blocs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void sort_incoming_links_for_vspace_manager(vspace_manager_t *manager) +{ + size_t i; /* Boucle de parcours */ + vspace_booking_t *pending; /* Elément traité */ + gint x1; /* Abscisse de départ de lien */ + size_t idx; /* Indice du lien entrant */ + gint x2; /* Abscisse d'arrivée de lien */ + + for (i = 0; i < manager->pending_count; i++) + { + pending = &manager->pending[i]; + + x1 = g_graph_cluster_compute_leaving_link_position(pending->from->owner, pending->from->index); + + idx = g_graph_cluster_find_incoming_link(pending->to->owner, pending->from); + + x2 = g_graph_cluster_compute_incoming_link_position(pending->to->owner, idx); + + if (x1 < x2) + { + manager->left = realloc(manager->left, ++manager->left_count * sizeof(vspace_booking_t *)); + manager->left[manager->left_count - 1] = pending; + } + else + { + manager->right = realloc(manager->right, ++manager->right_count * sizeof(vspace_booking_t *)); + manager->right[manager->right_count - 1] = pending; + } + + } + +} + + +/****************************************************************************** +* * +* Paramètres : manager = structure à consulter. * +* top = le bloc courant est-il le principal ? * +* cluster = graphique de blocs sur lequel s'appuyer. * +* * +* Description : Détermine les abscisses de tous les liens en place. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void compute_loop_link_x_with_vspace_manager(vspace_manager_t *manager, bool top, GGraphCluster *cluster) +{ + GtkAllocation needed; /* Espace nécessaire et alloué */ + size_t i; /* Boucle de parcours */ + vspace_booking_t *booking; /* Réservation à traiter */ + gint x; /* Position à appliquer */ + + g_graph_cluster_compute_needed_alloc(cluster, &needed); + + for (i = 0; i < manager->left_count; i++) + { + booking = manager->left[i]; + + x = i * LINK_MARGIN; + + if (!top) + x += HORIZONTAL_MARGIN; + + booking->pts[0].x = needed.x + x; + booking->pts[1].x = needed.x + x; + + } + + if (manager->left_count > 0) + { + if (!top) + x = HORIZONTAL_MARGIN; + else + x = 0; + + x += (manager->left_count - 1) * LINK_MARGIN; + + x += HORIZONTAL_MARGIN; + + /** + * Si la routine est une boucle sans fin, + * alors la boucle peut renvoyer vers le premier bloc. + */ + if (cluster->owner != NULL) + g_graph_cluster_offset_x(cluster->owner, x); + + } + + for (i = 0; i < manager->right_count; i++) + { + booking = manager->right[i]; + + x = HORIZONTAL_MARGIN + i * LINK_MARGIN; + + booking->pts[0].x = x; + booking->pts[1].x = x; + + } + +} + + +/****************************************************************************** +* * +* Paramètres : manager = structure à consulter. * +* cluster = graphique de blocs sur lequel s'appuyer. * +* * +* Description : Détermine les ordonnées de tous les liens en place. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void compute_loop_link_y_with_vspace_manager(vspace_manager_t *manager, GGraphCluster *cluster) +{ + GtkAllocation needed; /* Espace nécessaire et alloué */ + size_t i; /* Boucle de parcours */ + vspace_booking_t *booking; /* Réservation à traiter */ + + g_graph_cluster_compute_needed_alloc(cluster, &needed); + + for (i = 0; i < manager->pending_count; i++) + { + booking = &manager->pending[i]; + + /** + * On corrige le raccourci pris sans distinction de type de lien dans + * la fonction g_graph_cluster_compute_link_y_positions(). + */ + + booking->from->start[1].y = needed.y + needed.height - VERTICAL_MARGIN; + + /* Définition de l'ordonnée des points du lien */ + + booking->pts[0].y = booking->from->start[1].y; + + booking->pts[1].y = booking->to->end[0].y; + + } + +} + + /* ---------------------------------------------------------------------------------- */ /* DEFINITION D'UN CHEF DE FILE */ @@ -1295,7 +1666,6 @@ GGraphCluster *g_graph_cluster_new(GCodeBlock *block, segcnt_list *highlighted, { GGraphCluster *result; /* Structure à retourner */ GBufferView *view; /* Partie affichée du tampon */ - GtkRequisition requisition; /* Taille à l'écran actuelle */ result = g_object_new(G_TYPE_GRAPH_CLUSTER, NULL); @@ -1315,17 +1685,44 @@ GGraphCluster *g_graph_cluster_new(GCodeBlock *block, segcnt_list *highlighted, gtk_display_panel_show_border(GTK_DISPLAY_PANEL(result->display), true); + g_graph_cluster_reset_allocation(result); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à compléter. * +* * +* Description : Assigne à un bloc et son ensemble un emplacement initial. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_reset_allocation(GGraphCluster *cluster) +{ + GtkRequisition requisition; /* Taille à l'écran actuelle */ + size_t i; /* Boucle de parcours */ + /* Détermination d'une position initiale centrée */ - gtk_widget_get_preferred_size(result->display, NULL, &requisition); + gtk_widget_get_preferred_size(cluster->display, NULL, &requisition); - result->alloc.x = -requisition.width / 2; - result->alloc.y = 0; + cluster->alloc.x = -requisition.width / 2; + cluster->alloc.y = 0; - result->alloc.width = requisition.width; - result->alloc.height = requisition.height; + cluster->alloc.width = requisition.width; + cluster->alloc.height = requisition.height; - return result; + /* Propagation aux sous-blocs */ + + for (i = 0; i < cluster->ranks_count; i++) + reset_graph_rank_allocation(&cluster->ranks[i]); } @@ -1367,6 +1764,8 @@ static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub) else extend_graph_rank(&cluster->ranks[i], sub); + sub->owner = cluster; + } @@ -1391,6 +1790,7 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all GGraphCluster *target; /* Bloc ciblé par un lien */ leaving_link_t *leaving; /* Point de départ d'un lien */ incoming_link_t *incoming; /* Définitions d'arrivée */ + GdkPoint *midpts; /* Points intermédiaires */ size_t j; /* Boucle de parcours #2 */ /* Au niveau du bloc courant */ @@ -1455,13 +1855,20 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all /* Point d'arrivée */ - incoming = create_incoming_loop_link(target, leaving); + midpts = malloc(2 * sizeof(GdkPoint)); + midpts = calloc(2, sizeof(GdkPoint));//////////////// REMME + + incoming = create_incoming_loop_link(target, midpts, leaving); target->top_anchors = realloc(target->top_anchors, ++target->ta_count * sizeof(incoming_link_t *)); target->top_anchors[target->ta_count - 1] = incoming; + /* Réservation d'un espace latéral */ + + extend_vspace_manager(&target->vspaces, leaving, incoming, midpts); + /* Etablissement d'un embryon de lien */ for (j = 0; j < cluster->ranks_count; j++) @@ -1483,8 +1890,30 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all + /* Doit-on forcer un lien strictement vertical ? */ + + if (cluster->ba_count == 1) + { + assert(!cluster->has_straight); + + /** + * Attention : les boucles aussi ont un seul lien sortant ! + * + * S'il n'y a qu'un seul lien, on peut s'appuyer sur la variable 'incoming' + * manipulée dans la boucle : c'est forcément elle qui a été mise en place. + * + * Même chose pour 'target'. + */ + if (incoming->type != ILT_LOOP) + { + cluster->has_straight = true; + cluster->straight_level = g_code_block_get_rank(target->block); + cluster->straight_index = 0; + } + + } - /* Déplacement d'un éventuel lien central */ + /* Déplacement d'un éventuel lien central en position centrale */ if (cluster->has_straight) { @@ -1559,6 +1988,9 @@ static void g_graph_cluster_dispatch_x(GGraphCluster *cluster) const graph_rank_t *rank; /* Accès confortable au rang */ size_t j; /* Boucle de parcours #2 */ gint start; /* Position initiale de départ */ + GGraphCluster *target; /* Unique sous-bloc visé */ + size_t idx; /* Indice du lien entrant */ + gint end; /* Position initiale d'arrivée */ /** * A ce point, tous les blocs parents sont placés. @@ -1567,13 +1999,12 @@ static void g_graph_cluster_dispatch_x(GGraphCluster *cluster) * de la gauche ne doit pas arriver tout à droite ! */ - qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_link_t *), (__compar_fn_t)cmp_incoming_links); + //qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_link_t *), (__compar_fn_t)cmp_incoming_links); /** * Il est désormais temps de placer tous les blocs de code inférieurs. */ - for (k = 0; k < cluster->ranks_count; k++) { rank = &cluster->ranks[k]; @@ -1607,6 +2038,32 @@ static void g_graph_cluster_dispatch_x(GGraphCluster *cluster) } + else if (get_graph_rank(rank) == cluster->straight_level) + { + /** + * Si le bloc pointé en direct a plus d'un lien en entrée (comme + * dans le cas d'un bloc qui assure un début de boucle par exemple), + * le lien direct n'est pas centré sur le milieu de ce bloc pointé. + * + * On corrige ici le léger décalage. + */ + assert(rank->count == 1); + + target = rank->clusters[0]; + + idx = g_graph_cluster_find_incoming_link(target, cluster->bottom_anchors[cluster->straight_index]); + + end = g_graph_cluster_compute_incoming_link_position(target, idx); + + g_graph_cluster_offset_x(target, start - end); + + dispatch_x_graph_rank(rank); + + } + + else + dispatch_x_graph_rank(rank); + } /* Répartition homogène */ @@ -1620,6 +2077,60 @@ static void g_graph_cluster_dispatch_x(GGraphCluster *cluster) /****************************************************************************** * * +* Paramètres : cluster = graphique de blocs à manipuler. * +* * +* Description : Réorganise au besoin les liens entrants d'un bloc. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_sort_incoming_links(GGraphCluster *cluster) +{ + size_t i; /* Boucle de parcours */ + + qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_link_t *), (__compar_fn_t)cmp_incoming_links); + + for (i = 0; i < cluster->ranks_count; i++) + sort_graph_rank_incoming_links(&cluster->ranks[i]); + + sort_incoming_links_for_vspace_manager(&cluster->vspaces); + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à consulter. * +* incoming = adresse de l'autre bout du lien concerné. * +* * +* Description : Retrouve l'indice d'un lien entrant donné pour un bloc. * +* * +* Retour : Indice à priori toujours valide. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static size_t g_graph_cluster_find_incoming_link(const GGraphCluster *cluster, const leaving_link_t *leaving) +{ + size_t result; /* Indice à retourner */ + + for (result = 0; result < cluster->ta_count; result++) + if (cluster->top_anchors[result]->other == leaving) + break; + + assert(cluster->ta_count); + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : cluster = graphique de blocs à actualiser. * * offset = décalage à appliquer. * * * @@ -1686,12 +2197,23 @@ static void g_graph_cluster_set_y(GGraphCluster *cluster, gint base) void g_graph_cluster_compute_needed_alloc(const GGraphCluster *cluster, GtkAllocation *alloc) { size_t i; /* Boucle de parcours */ + size_t level; /* Niveau du nouvel ensemble */ + bool concat; /* Redondance des espaces ? */ *alloc = cluster->alloc; for (i = 0; i < cluster->ranks_count; i++) compute_graph_rank_needed_alloc(&cluster->ranks[i], (i + 1) == cluster->ranks_count, alloc); + level = g_code_block_get_rank(cluster->block); + + if (cluster->ranks_count == 0) + concat = false; + else + concat = has_graph_rank_ending_vspace(&cluster->ranks[cluster->ranks_count - 1]); + + compute_vspace_manager_needed_alloc(&cluster->vspaces, level == 0, concat, alloc); + } @@ -1754,62 +2276,86 @@ void g_graph_cluster_place(GGraphCluster *cluster, GtkGraphDisplay *display) } +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à consulter. * +* index = indice du lien à considérer. * +* half = moitié du nombre de liens en présence. * +* odd = le nombre de liens considérés est-il impair ? * +* * +* Description : Calcule l'abscisse d'un lien pour un bloc. * +* * +* Retour : Abscisse à attribuer au lien. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static gint _g_graph_cluster_compute_link_position(const GGraphCluster *cluster, size_t index, size_t half, bool odd) +{ + gint result; /* Position à retourner */ + gint mid_x; /* Abscisse centrale */ + mid_x = cluster->alloc.x + (cluster->alloc.width / 2); + if (odd) + { + 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 à consulter ou remonter. * -* first = première instruction du bloc basique recherché. * +* Paramètres : cluster = graphique de blocs à consulter. * +* index = indice du lien à considérer. * * * -* Description : Recherche le bloc basique à l'extrémité d'un lien. * +* Description : Calcule l'abscisse d'un lien à son départ d'un bloc. * * * -* Retour : Bloc graphique de destination pour un lien ou NULL si échec. * +* Retour : Abscisse à attribuer à un départ de lien. * * * * Remarques : - * * * ******************************************************************************/ -#if 0 -static GGraphCluster *g_graph_cluster_find_lower_dest_cluster(const GGraphCluster *cluster, const GArchInstruction *first) -{ - GGraphCluster *result; /* Trouvaille à retourner */ - size_t i; /* Boucle de parcours #1 */ - const graph_rank_t *rank; /* Confort d'accès */ - size_t j; /* Boucle de parcours #2 */ - GArchInstruction *instr; /* Instruction à comparer */ - result = NULL; - - for (i = 0; i < cluster->ranks_count && result == NULL; i++) - { - rank = &cluster->ranks[i]; +static gint g_graph_cluster_compute_leaving_link_position(const GGraphCluster *cluster, size_t index) +{ + gint result; /* Position à retourner */ + size_t half; /* Indice de répartition égale */ + bool odd; /* Partité du nombre de liens */ - for (j = 0; j < rank->count && result == NULL; j++) - { - g_basic_block_get_boundaries(rank->clusters[j]->block, &instr, NULL); + assert(index < cluster->ba_count); - if (instr == first) - result = rank->clusters[j]; + half = cluster->ba_count / 2; - } + odd = (cluster->ba_count % 2 == 1); - } + result = _g_graph_cluster_compute_link_position(cluster, index, half, odd); return result; } -#endif - /****************************************************************************** @@ -1817,50 +2363,59 @@ static GGraphCluster *g_graph_cluster_find_lower_dest_cluster(const GGraphCluste * Paramètres : cluster = graphique de blocs à consulter. * * index = indice du lien à considérer. * * * -* Description : Calcule l'abscisse d'un lien à son départ d'un bloc. * +* Description : Calcule l'abscisse d'un lien à son arrivée à un bloc. * * * -* Retour : Abscisse à attribuer à un départ de lien. * +* Retour : Abscisse à attribuer à une arrivée de lien. * * * * Remarques : - * * * ******************************************************************************/ -static gint g_graph_cluster_compute_leaving_link_position(const GGraphCluster *cluster, size_t index) +static gint g_graph_cluster_compute_incoming_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 */ + bool odd; /* Partité du nombre de liens */ - assert(index < cluster->ba_count); + assert(index < cluster->ta_count); - mid_x = cluster->alloc.x + (cluster->alloc.width / 2); + half = cluster->ta_count / 2; - half = cluster->ba_count / 2; + odd = (cluster->ta_count % 2 == 1); - if (cluster->ba_count % 2 == 1) - { - if (index < half) - result = mid_x - (half - index) * LINK_MARGIN; + result = _g_graph_cluster_compute_link_position(cluster, index, half, odd); - else if (index == half) - result = mid_x; + return result; - else - result = mid_x + (index - half) * LINK_MARGIN; +} - } - else - { - if (index < half) - result = mid_x - LINK_MARGIN / 2 - (half - index - 1) * LINK_MARGIN; +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à actualiser. * +* * +* Description : Détermine les abscisses des liens de boucle en place. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ - else - result = mid_x + LINK_MARGIN / 2 + (index - half) * LINK_MARGIN; +static void g_graph_cluster_compute_loop_link_x_positions(GGraphCluster *cluster) +{ + size_t i; /* Boucle de parcours #1 */ + size_t j; /* Boucle de parcours #2 */ - } + /* Liens de boucle */ - return result; + compute_loop_link_x_with_vspace_manager(&cluster->vspaces, false /* FIXME */, cluster); + + /* Propagation des déterminations */ + + for (i = 0; i < cluster->ranks_count; i++) + for (j = 0; j < cluster->ranks[i].count; j++) + g_graph_cluster_compute_loop_link_x_positions(cluster->ranks[i].clusters[j]); } @@ -1892,10 +2447,12 @@ static void g_graph_cluster_compute_link_x_positions(GGraphCluster *cluster) if (cluster->ba_count > 0) for (i = 0; i < cluster->ba_count; i++) { - pt = &cluster->bottom_anchors[i]->start; + pt = &cluster->bottom_anchors[i]->start[0]; pt->x = g_graph_cluster_compute_leaving_link_position(cluster, i); + cluster->bottom_anchors[i]->start[1].x = pt->x; + } /* Du côté des arrivées... */ @@ -1908,17 +2465,17 @@ static void g_graph_cluster_compute_link_x_positions(GGraphCluster *cluster) { for (i = half; i > 0; i--) { - pt = &cluster->top_anchors[i - 1]->end; + pt = &cluster->top_anchors[i - 1]->end[1]; pt->x = mid_x - (half - i + 1) * LINK_MARGIN; } - cluster->top_anchors[half]->end.x = mid_x; + cluster->top_anchors[half]->end[1].x = mid_x; for (i = half + 1; i < cluster->ta_count; i++) { - pt = &cluster->top_anchors[i]->end; + pt = &cluster->top_anchors[i]->end[1]; pt->x = mid_x + (i - half) * LINK_MARGIN; @@ -1930,7 +2487,7 @@ static void g_graph_cluster_compute_link_x_positions(GGraphCluster *cluster) { for (i = half; i > 0; i--) { - pt = &cluster->top_anchors[i - 1]->end; + pt = &cluster->top_anchors[i - 1]->end[1]; pt->x = mid_x - LINK_MARGIN / 2 - (half - i) * LINK_MARGIN; @@ -1938,7 +2495,7 @@ static void g_graph_cluster_compute_link_x_positions(GGraphCluster *cluster) for (i = half; i < cluster->ta_count; i++) { - pt = &cluster->top_anchors[i]->end; + pt = &cluster->top_anchors[i]->end[1]; pt->x = mid_x + LINK_MARGIN / 2 + (half - i) * LINK_MARGIN; @@ -1948,6 +2505,9 @@ static void g_graph_cluster_compute_link_x_positions(GGraphCluster *cluster) } + for (i = 0; i < cluster->ta_count; i++) + cluster->top_anchors[i]->end[0].x = cluster->top_anchors[i]->end[1].x; + /* Propagation des déterminations */ for (i = 0; i < cluster->ranks_count; i++) @@ -2058,7 +2618,7 @@ static void g_graph_cluster_compute_link_y_positions(GGraphCluster *cluster) y = cluster->alloc.y + cluster->alloc.height; for (i = 0; i < cluster->ba_count; i++) - cluster->bottom_anchors[i]->start.y = y; + cluster->bottom_anchors[i]->start[0].y = y; } @@ -2072,17 +2632,23 @@ static void g_graph_cluster_compute_link_y_positions(GGraphCluster *cluster) { incoming = cluster->top_anchors[i]; - incoming->end.y = y; + incoming->end[1].y = y; - incoming->y.y = incoming->end.y - VERTICAL_MARGIN; + incoming->end[0].y = incoming->end[1].y - VERTICAL_MARGIN; if (incoming->hslot != NULL) - incoming->y.y -= *incoming->hslot * LINK_MARGIN; + incoming->end[0].y -= *incoming->hslot * LINK_MARGIN; + + incoming->other->start[1].y = incoming->end[0].y; } } + /* Définition des liens de boucle */ + + compute_loop_link_y_with_vspace_manager(&cluster->vspaces, cluster); + /* Propagation des déterminations */ for (i = 0; i < cluster->ranks_count; i++) @@ -2326,6 +2892,26 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList * g_graph_cluster_dispatch_x(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 + * de la gauche ne doit pas arriver tout à droite ! + * + * Cette consigne est valable pour les liens de boucle également, dont + * l'origine est toujours dans un bloc inférieur au bloc de destination. + * Le premier étant traité après le second, cela oblige à appeler + * g_graph_cluster_dispatch_x() deux fois donc, car on ne peut effectuer + * le tri des liens au début de cette fonction comme c'était fait + * dans les premières versions du code. + */ + + g_graph_cluster_sort_incoming_links(result); + + g_graph_cluster_reset_allocation(result); + + g_graph_cluster_dispatch_x(result); + /* Réajustement vers la droite */ g_graph_cluster_compute_needed_alloc(result, &needed); @@ -2334,6 +2920,21 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList * /* Application finale sur les liens */ + /** + * Comme g_graph_cluster_offset_x() n'agit que sur les abscisses et non sur + * les largeurs, on ne peut pas définir les positions pour les liens de boucle + * en amont et les décaler ensuite. + * + * Et comme la mise en place de ce type de lien peut déplacer le bloc parent, + * ses repères pour ses propres liens peuvent être décaler. Il faut ainsi + * une procédure distincte de g_graph_cluster_compute_link_x_positions(). + * + * On définit donc l'abscisse de ces liens ici, en redécalant encore un peu + * les blocs au besoin. + */ + + g_graph_cluster_compute_loop_link_x_positions(result); + g_graph_cluster_compute_link_x_positions(result); g_graph_cluster_book_hspace_for_links(result); diff --git a/src/gtkext/graph/edge.c b/src/gtkext/graph/edge.c index c07c6c5..e3844f3 100644 --- a/src/gtkext/graph/edge.c +++ b/src/gtkext/graph/edge.c @@ -38,12 +38,11 @@ struct _GGraphEdge EdgeColor color; /* Couleur du rendu */ - const GdkPoint *start; /* Point de départ du lien */ - GdkPoint *mid[2]; /* Etapes intermédiaires */ - size_t m_count; /* Quantité de ces étapes */ - const GdkPoint *end; /* Point d'arrivée du lien */ - - GdkPoint *points; /* Points de la ligne dessinée */ + union + { + const GdkPoint **templates; /* Inspirations de coordonnées */ + GdkPoint *points; /* Points de la ligne dessinée */ + }; size_t count; /* Quantité de ces points */ }; @@ -157,8 +156,7 @@ static void g_graph_edge_dispose(GGraphEdge *edge) static void g_graph_edge_finalize(GGraphEdge *edge) { - if (edge->points != NULL) - free(edge->points); + free(edge->points); G_OBJECT_CLASS(g_graph_edge_parent_class)->finalize(G_OBJECT(edge)); @@ -167,11 +165,9 @@ static void g_graph_edge_finalize(GGraphEdge *edge) /****************************************************************************** * * -* Paramètres : start = point de départ de la flêche. * -* mid = points intermédiares variables. * -* count = nombre de ces points fournis. * -* end = point d'arrivée de la flêche. * -* color = couleur de rendu à l'écran. * +* Paramètres : templates = coordonnées des futurs points. * +* count = nombre de ces points fournis. * +* color = couleur de rendu à l'écran. * * * * Description : Etablit un lien graphique entre deux noeuds graphiques. * * * @@ -181,7 +177,7 @@ static void g_graph_edge_finalize(GGraphEdge *edge) * * ******************************************************************************/ -GGraphEdge *_g_graph_edge_new(const GdkPoint *start, const GdkPoint **mid, size_t count, const GdkPoint *end, EdgeColor color) +GGraphEdge *_g_graph_edge_new(const GdkPoint **templates, size_t count, EdgeColor color) { GGraphEdge *result; /* Structure à retourner */ @@ -189,16 +185,14 @@ GGraphEdge *_g_graph_edge_new(const GdkPoint *start, const GdkPoint **mid, size_ result->color = color; - assert(count == 1 || count == 2); + assert(count == 4 || count == 6); - result->start = start; + result->templates = malloc(count * sizeof(GdkPoint *)); + memcpy(result->templates, templates, count * sizeof(GdkPoint *)); - memcpy(result->mid, mid, count * sizeof(GdkPoint)); - result->m_count = count; + result->count = count; - result->end = end; - - return G_GRAPH_EDGE(result); + return result; } @@ -219,8 +213,14 @@ GGraphEdge *_g_graph_edge_new(const GdkPoint *start, const GdkPoint **mid, size_ void g_graph_edge_get_x_borders(const GGraphEdge *edge, gint *x1, gint *x2) { - *x1 = edge->start->x; - *x2 = edge->end->x; + /** + * A l'appel de cette fonction, les informations des points n'ont + * pas encore été fixées ni recopiées. + */ + + *x1 = edge->templates[0]->x; + *x2 = edge->templates[edge->count - 1]->x; + } @@ -238,29 +238,20 @@ void g_graph_edge_get_x_borders(const GGraphEdge *edge, gint *x1, gint *x2) void g_graph_edge_resolve(GGraphEdge *edge) { - edge->count = 2 + 2 * edge->m_count; - edge->points = (GdkPoint *)calloc(edge->count, sizeof(GdkPoint)); + const GdkPoint **templates; /* Inspirations de coordonnées */ + size_t i; /* Boucle de parcours */ - edge->points[0] = *edge->start; + templates = edge->templates; - edge->points[1].x = edge->start->x; - edge->points[1].y = edge->mid[0]->y; + edge->points = malloc(edge->count * sizeof(GdkPoint)); - if (edge->m_count == 1) - { - edge->points[2].x = edge->end->x; - edge->points[2].y = edge->mid[0]->y; - } - else + for (i = 0; i < edge->count; i++) { - memcpy(&edge->points[2], edge->mid, edge->m_count * sizeof(GdkPoint)); - - edge->points[4].x = edge->end->x; - edge->points[4].y = edge->mid[3]->y; - + edge->points[i].x = templates[i]->x; + edge->points[i].y = templates[i]->y; } - edge->points[edge->count - 1] = *edge->end; + free(templates); } diff --git a/src/gtkext/graph/edge.h b/src/gtkext/graph/edge.h index d000eb5..23fcf8d 100644 --- a/src/gtkext/graph/edge.h +++ b/src/gtkext/graph/edge.h @@ -64,19 +64,19 @@ typedef enum _EdgeColor GType g_graph_edge_get_type(void); /* Etablit un lien graphique entre deux noeuds graphiques. */ -GGraphEdge *_g_graph_edge_new(const GdkPoint *, const GdkPoint **, size_t, const GdkPoint *, EdgeColor); +GGraphEdge *_g_graph_edge_new(const GdkPoint **, size_t, EdgeColor); -#define g_graph_edge_new(start, y, end) \ - _g_graph_edge_new(start, (const GdkPoint *[]) { y }, 1, end, EGC_DEFAULT) +#define g_graph_edge_new(pts0, pts1, pte0, pte1) \ + _g_graph_edge_new((const GdkPoint *[]) { pts0, pts1, pte0, pte1 }, 4, EGC_DEFAULT) -#define g_graph_edge_new_true(start, y, end) \ - _g_graph_edge_new(start, (const GdkPoint *[]) { y }, 1, end, EGC_GREEN) +#define g_graph_edge_new_true(pts0, pts1, pte0, pte1) \ + _g_graph_edge_new((const GdkPoint *[]) { pts0, pts1, pte0, pte1 }, 4, EGC_GREEN) -#define g_graph_edge_new_false(start, y, end) \ - _g_graph_edge_new(start, (const GdkPoint *[]) { y }, 1, end, EGC_RED) +#define g_graph_edge_new_false(pts0, pts1, pte0, pte1) \ + _g_graph_edge_new((const GdkPoint *[]) { pts0, pts1, pte0, pte1 }, 4, EGC_RED) -#define g_graph_edge_new_loop(start, yt, yb, end) \ - _g_graph_edge_new(start, (const GdkPoint *[]) { yt, yb }, 2, end, EGC_BLUE) +#define g_graph_edge_new_loop(pts0, pts1, ptl0, ptl1, pte0, pte1) \ + _g_graph_edge_new((const GdkPoint *[]) { pts0, pts1, ptl0, ptl1, pte0, pte1 }, 6, EGC_BLUE) /* Fournit les abscisses des points extrèmes de la ligne. */ void g_graph_edge_get_x_borders(const GGraphEdge *, gint *, gint *); diff --git a/src/gtkext/gtkgraphdisplay.c b/src/gtkext/gtkgraphdisplay.c index 749a156..0c65c23 100644 --- a/src/gtkext/gtkgraphdisplay.c +++ b/src/gtkext/gtkgraphdisplay.c @@ -365,7 +365,7 @@ static void gtk_graph_display_compute_requested_size(GtkGraphDisplay *display, g if (display->cluster != NULL) { g_graph_cluster_compute_needed_alloc(display->cluster, &needed); - assert(needed.x == 0 && needed.y == 0); + //assert(needed.x == 0 && needed.y == 0); needed.width += 2 * GRAPH_MARGIN; needed.height += 2 * GRAPH_MARGIN; -- cgit v0.11.2-87-g4458