From f16787410dd6eaf48df986644d0c3ac2b021748b Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Tue, 1 Jan 2019 23:18:04 +0100 Subject: Refactored some code for the graph layout. --- src/gtkext/graph/cluster.c | 507 +++++++++++++++++++++++++-------------------- 1 file changed, 284 insertions(+), 223 deletions(-) diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c index 869851c..d21818a 100644 --- a/src/gtkext/graph/cluster.c +++ b/src/gtkext/graph/cluster.c @@ -87,6 +87,9 @@ typedef struct _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 *); +/* 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 *); + /* Détruit un point d'attache pour un lien entrant. */ static void delete_incoming_link(incoming_link_t *); @@ -106,6 +109,17 @@ typedef struct _hspace_booking } hspace_booking; + +/* Prépare une réservation d'espace pour ligne horizontale. */ +static hspace_booking *create_hspace_booking(gint); + +/* Compare deux réservations d'espace. */ +static int cmp_hspace_booking_r2l(const hspace_booking **, const hspace_booking **); + +/* Compare deux réservations d'espace. */ +static int cmp_hspace_booking_l2r(const hspace_booking **, const hspace_booking **); + + /* Découpage vertical */ typedef struct _graph_rank_t { @@ -139,6 +153,9 @@ static int cmp_graph_rank(const graph_rank_t *, const graph_rank_t *); /* Etend un ensemble de blocs de même rang. */ static void extend_graph_rank(graph_rank_t *, GGraphCluster *); +/* Etablit les connexions entre blocs selon les rangs. */ +static bool setup_graph_rank_link_for_target(const graph_rank_t *, GGraphCluster *, GGraphCluster *, leaving_link_t *); + /* Détermine l'emplacement requis d'un ensemble de blocs. */ static void compute_graph_rank_needed_alloc(const graph_rank_t *, bool, GtkAllocation *); @@ -148,9 +165,12 @@ 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 *); -/* Décalle vers la droite un ensemble de blocs basiques. */ +/* Décale vers la droite un ensemble de blocs basiques. */ static void offset_x_graph_rank(const graph_rank_t *, gint); +/* Décale vers le bas un ensemble de blocs basiques. */ +static void set_y_for_graph_rank(const graph_rank_t *, gint *); + /* ------------------------ ENCADREMENTS D'ESPACES VERTICAUX ------------------------ */ @@ -266,10 +286,10 @@ 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 *); -/* Décalle vers la droite un ensemble de blocs basiques. */ +/* Décale vers la droite un ensemble de blocs basiques. */ static void g_graph_cluster_offset_x(GGraphCluster *, gint); -/* Décalle vers le bas un ensemble de blocs basiques. */ +/* Décale vers le bas un ensemble de blocs basiques. */ static void g_graph_cluster_set_y(GGraphCluster *, gint); @@ -436,6 +456,38 @@ static incoming_link_t *create_incoming_link(GGraphCluster *owner, InstructionLi /****************************************************************************** * * +* Paramètres : owner = propriétaire du bloc de rattachement. * +* other = point de départ du lien formé. * +* * +* Description : Crée un point d'attache pour un lien entrant de boucle. * +* * +* Retour : Structure mise en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static incoming_link_t *create_incoming_loop_link(GGraphCluster *owner, const leaving_link_t *other) +{ + incoming_link_t *result; /* Structure à retourner */ + + result = malloc(sizeof(incoming_link_t)); + + result->owner = owner; + + result->type = ILT_LOOP; + + result->edge = g_graph_edge_new_loop(&other->start, &other->start, &result->y, &result->end); + + result->other = other; + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : link = structure à libérer de la mémoire. * * * * Description : Détruit un point d'attache pour un lien entrant. * @@ -498,6 +550,99 @@ static int cmp_incoming_links(const incoming_link_t **a, const incoming_link_t * /****************************************************************************** * * +* Paramètres : start = abscisse de départ de ligne. * +* * +* Description : Prépare une réservation d'espace pour ligne horizontale. * +* * +* Retour : Structure mise en place pour la conservation d'informations. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static hspace_booking *create_hspace_booking(gint start) +{ + hspace_booking *result; /* Structure à retourner */ + + result = malloc(sizeof(hspace_booking)); + + result->start = start; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : a = première réservation d'espace à comparer. * +* b = seconde réservation d'espace à comparer. * +* * +* Description : Compare deux réservations d'espace. * +* * +* Retour : Bilan de comparaison. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static int cmp_hspace_booking_r2l(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; + +} + + +/****************************************************************************** +* * +* Paramètres : a = première réservation d'espace à comparer. * +* b = seconde réservation d'espace à comparer. * +* * +* Description : Compare deux réservations d'espace. * +* * +* Retour : Bilan de comparaison. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static int cmp_hspace_booking_l2r(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; + +} + + +/****************************************************************************** +* * * Paramètres : grank = structure à initialiser. [OUT] * * cluster = chef de file d'un ensemble de blocs. * * * @@ -644,6 +789,62 @@ static void extend_graph_rank(graph_rank_t *grank, GGraphCluster *cluster) /****************************************************************************** * * +* Paramètres : grank = ensemble de descendants d'un même rang. * +* source = bloc courant ou NULL pour limiter les calculs. * +* target = bloc ciblé pour l'arrivée d'un lien. * +* leaving = représentation d'un lien sortant. * +* * +* Description : Etablit les connexions entre blocs selon les rangs. * +* * +* Retour : true si la cible a été rencontrée. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static bool setup_graph_rank_link_for_target(const graph_rank_t *grank, GGraphCluster *source, GGraphCluster *target, leaving_link_t *leaving) +{ + bool result; /* Bilan à retourner */ + size_t level; /* Niveau du nouvel ensemble */ + size_t i; /* Boucle de parcours */ + size_t target_level; /* Rang du bloc ciblé */ + + result = false; + + if (source != NULL) + level = g_code_block_get_rank(source->block); + + for (i = 0; i < grank->count && !result; i++) + if (grank->clusters[i] == target) + { + result = true; + + target->parent_index = &leaving->index; + + if (source != NULL) + { + target_level = get_graph_rank(grank); + + /* Est-ce un lien qui doit être vertical ? */ + + if (target_level > (level + 1) && target_level > source->straight_level) + { + source->has_straight = true; + source->straight_level = target_level; + source->straight_index = source->ba_count - 1; + } + + } + + } + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : grank = ensemble de descendants d'un même rang. * * last = indique s'il s'agit du dernier étage de l'ensemble. * * alloc = emplacement idéal pour l'affichage. [OUT] * @@ -822,7 +1023,7 @@ static void dispatch_x_graph_rank(const graph_rank_t *grank) * Paramètres : grank = ensemble de blocs de même rang à actualiser. * * offset = décalage à appliquer. * * * -* Description : Décalle vers la droite un ensemble de blocs basiques. * +* Description : Décale vers la droite un ensemble de blocs basiques. * * * * Retour : - * * * @@ -840,6 +1041,68 @@ static void offset_x_graph_rank(const graph_rank_t *grank, gint offset) } +/****************************************************************************** +* * +* Paramètres : grank = ensemble de blocs de même rang à actualiser. * +* base = position ordonnée à appliquer. * +* * +* Description : Décale vers le bas un ensemble de blocs basiques. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void set_y_for_graph_rank(const graph_rank_t *grank, gint *base) +{ + gint max; /* Hauteur maximale rencontrée */ + size_t i; /* Boucle de parcours */ + GGraphCluster *sub; /* Sous-ensemble traité */ + GtkAllocation alloc; /* Allocation courante */ + + /* On ajoute l'espace vertical pour les lignes horizontales */ + + if (grank->r2l_count > grank->l2r_count) + max = grank->r2l_count; + else + max = grank->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); + *base += VERTICAL_MARGIN; + } + + /* On ajoute l'espace requis pour l'affichage des blocs */ + + max = 0; + + for (i = 0; i < grank->count; i++) + { + sub = grank->clusters[i]; + + g_graph_cluster_set_y(sub, *base); + + g_graph_cluster_compute_needed_alloc(sub, &alloc); + + if ((alloc.y + alloc.height) > max) + max = alloc.y + alloc.height; + + } + + *base = max; + +} + + /* ---------------------------------------------------------------------------------- */ /* ENCADREMENTS D'ESPACES VERTICAUX */ @@ -1122,21 +1385,16 @@ static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub) static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all) { - size_t level; /* Niveau du nouvel ensemble */ size_t dcount; /* Nombre de liens de dest. */ size_t i; /* Boucle de parcours #1 */ const block_link_t *dest; /* Bloc visé par une autre */ GGraphCluster *target; /* Bloc ciblé par un lien */ leaving_link_t *leaving; /* Point de départ d'un lien */ - size_t target_level; /* Rang du bloc ciblé */ - size_t j; /* Boucle de parcours #2 */ - size_t k; /* Boucle de parcours #3 */ incoming_link_t *incoming; /* Définitions d'arrivée */ + size_t j; /* Boucle de parcours #2 */ /* Au niveau du bloc courant */ - level = g_code_block_get_rank(cluster->block); - g_code_block_lock_dest(cluster->block); dcount = g_code_block_count_destinations(cluster->block); @@ -1164,33 +1422,6 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all 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 = get_graph_rank(&cluster->ranks[j]); - - 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; - } - - } - - - - - - /* Point d'arrivée */ incoming = create_incoming_link(target, dest->type, leaving); @@ -1202,32 +1433,14 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all /* Etablissement d'un embryon de lien */ - - - /* 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; - } - - - + for (j = 0; j < cluster->ranks_count; j++) + if (setup_graph_rank_link_for_target(&cluster->ranks[j], cluster, target, leaving)) + break; break; - case ILT_LOOP: - - - - target = G_GRAPH_CLUSTER(g_hash_table_lookup(all, dest->linked)); assert(target != NULL); @@ -1240,36 +1453,9 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all 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 = get_graph_rank(&cluster->ranks[j]); - - 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; - } - - } - - - - - - /* Point d'arrivée */ - incoming = create_incoming_link(target, dest->type, leaving); + incoming = create_incoming_loop_link(target, leaving); target->top_anchors = realloc(target->top_anchors, ++target->ta_count * sizeof(incoming_link_t *)); @@ -1278,33 +1464,9 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all /* Etablissement d'un embryon de lien */ - incoming->edge = g_graph_edge_new_loop(&leaving->start, &leaving->start, - &incoming->y, &incoming->end); - - - /* 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; - } - - - - - - - - - - - /* TODO */ - //assert(false); + for (j = 0; j < cluster->ranks_count; j++) + if (setup_graph_rank_link_for_target(&cluster->ranks[j], NULL, target, leaving)) + break; break; @@ -1461,7 +1623,7 @@ static void g_graph_cluster_dispatch_x(GGraphCluster *cluster) * Paramètres : cluster = graphique de blocs à actualiser. * * offset = décalage à appliquer. * * * -* Description : Décalle vers la droite un ensemble de blocs basiques. * +* Description : Décale vers la droite un ensemble de blocs basiques. * * * * Retour : - * * * @@ -1486,7 +1648,7 @@ static void g_graph_cluster_offset_x(GGraphCluster *cluster, gint offset) * Paramètres : cluster = graphique de blocs à actualiser. * * base = position ordonnée à appliquer. * * * -* Description : Décalle vers le bas un ensemble de blocs basiques. * +* Description : Décale vers le bas un ensemble de blocs basiques. * * * * Retour : - * * * @@ -1496,60 +1658,14 @@ 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_t *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é */ - GtkAllocation alloc; /* Allocation courante */ + size_t i; /* Boucle de parcours */ cluster->alloc.y = base; base += cluster->alloc.height; 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 < rank->count; j++) - { - sub = rank->clusters[j]; - - g_graph_cluster_set_y(sub, base); - - g_graph_cluster_compute_needed_alloc(sub, &alloc); - - if ((alloc.y + alloc.height) > max) - max = alloc.y + alloc.height; - - } - - base = max; - - } + set_y_for_graph_rank(&cluster->ranks[i], &base); } @@ -1878,71 +1994,18 @@ static void g_graph_cluster_book_hspace_for_links(GGraphCluster *cluster) { g_graph_edge_get_x_borders(sub->top_anchors[k]->edge, &x1, &x2); - if (x1 > x2) - { - new = (hspace_booking *)calloc(1, sizeof(hspace_booking)); - - new->start = x1; - sub->top_anchors[k]->hslot = &new->index; - - int compare_right_to_left(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; - - } + new = create_hspace_booking(x1); + sub->top_anchors[k]->hslot = &new->index; + if (x1 > x2) rank->right2left = qinsert(rank->right2left, &rank->r2l_count, sizeof(hspace_booking *), - (__compar_fn_t)compare_right_to_left, &new); - - } + (__compar_fn_t)cmp_hspace_booking_r2l, &new); else if (x1 < x2) - { - new = (hspace_booking *)calloc(1, sizeof(hspace_booking)); - - new->start = x1; - sub->top_anchors[k]->hslot = &new->index; - - 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); - - } + (__compar_fn_t)cmp_hspace_booking_l2r, &new); else sub->top_anchors[k]->hslot = NULL; @@ -2286,8 +2349,6 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList * g_hash_table_unref(all); - return result; - } -- cgit v0.11.2-87-g4458