diff options
| -rw-r--r-- | src/gtkext/graph/cluster.c | 321 |
1 files changed, 283 insertions, 38 deletions
diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c index e0d67eb..7872000 100644 --- a/src/gtkext/graph/cluster.c +++ b/src/gtkext/graph/cluster.c @@ -26,6 +26,7 @@ #include <assert.h> #include <malloc.h> +#include <stdint.h> #include <stdlib.h> #include <string.h> @@ -38,6 +39,10 @@ +/* Définition du tracé d'un lien */ +typedef struct _incoming_link_t incoming_link_t; + + /* ------------------------- LIEN SORTANT D'UN BLOC DE CODE ------------------------- */ @@ -49,9 +54,19 @@ typedef struct _leaving_link_t GdkPoint start[2]; /* Point de départ d'un lien */ size_t index; /* Indice sur ligne de départ */ + bool straight; /* Présence d'une ligne droite */ + 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) + + /* Crée un point d'attache pour un lien sortant. */ static leaving_link_t *create_leaving_link(GGraphCluster *, size_t); @@ -67,7 +82,7 @@ static gint compute_leaving_link_position(const leaving_link_t *); /* Définition du tracé d'un lien */ -typedef struct _incoming_link_t +struct _incoming_link_t { GGraphCluster *owner; /* Propriétaire du lien */ @@ -80,7 +95,7 @@ typedef struct _incoming_link_t leaving_link_t *other; /* Autre extrémité du lien */ -} incoming_link_t; +}; /* Crée un point d'attache pour un lien entrant simple. */ @@ -204,9 +219,6 @@ 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 *); -/* Etend un ensemble de blocs de même rang. */ -static void extend_graph_rank(graph_rank_t *, GGraphCluster *); - /* Compare deux rangées de blocs de code. */ static int cmp_graph_rank(const graph_rank_t *, const graph_rank_t *); @@ -219,6 +231,12 @@ static bool has_graph_rank_cluster(const graph_rank_t *, GGraphCluster *); /* Inscrit à l'endroit idéal une réservation d'espace latéral. */ static bool extend_graph_rank_vspace_manager(graph_rank_t *, leaving_link_t *, incoming_link_t *, GdkPoint *, bool); +/* Met en place les embryons de liens nécessaires. */ +static void define_graph_rank_links(const graph_rank_t *, GHashTable *); + +/* Repère les liens marquants à destination d'autres blocs. */ +static void setup_graph_rank_links(const graph_rank_t *); + /* Détermine l'emplacement requis d'un ensemble de blocs. */ static void compute_graph_rank_needed_alloc(const graph_rank_t *, bool, GtkAllocation *); @@ -259,6 +277,8 @@ struct _GGraphCluster GGraphCluster *owner; /* Ensemble lié parent */ size_t *parent_index; /* Indice du lien au départ */ + GGraphCluster *container; /* Conteneur de l'ensemble */ + //////////////////////////////////////// gint top_margin[2]; /* Espaces gauches et droites */ gint left_margin; /* Espaces remontant à gauche */ @@ -329,6 +349,9 @@ static void g_graph_cluster_extend_vspace_manager(GGraphCluster *, leaving_link_ /* Met en place les embryons de liens nécessaires. */ static void g_graph_cluster_define_links(GGraphCluster *, GHashTable *); +/* Repère les liens marquants à destination d'autres blocs. */ +static void g_graph_cluster_setup_links(GGraphCluster *); + /* Organise la disposition d'un ensemble de blocs basiques. */ static void g_graph_cluster_dispatch_x(GGraphCluster *); @@ -424,6 +447,11 @@ static leaving_link_t *create_leaving_link(GGraphCluster *owner, size_t index) result->index = index; + result->straight = false; + result->straight_level = SIZE_MAX; + result->cluster_exit = false; + result->forced_straight = false; + return result; } @@ -1305,6 +1333,51 @@ static bool extend_graph_rank_vspace_manager(graph_rank_t *grank, leaving_link_t /****************************************************************************** * * * Paramètres : grank = ensemble de descendants d'un même rang. * +* all = table regroupant tous les groupes créés. * +* * +* Description : Met en place les embryons de liens nécessaires. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void define_graph_rank_links(const graph_rank_t *grank, GHashTable *all) +{ + size_t i; /* Boucle de parcours */ + + for (i = 0; i < grank->count; i++) + g_graph_cluster_define_links(grank->clusters[i], all); + +} + + +/****************************************************************************** +* * +* Paramètres : grank = ensemble de descendants d'un même rang. * +* * +* Description : Repère les liens marquants à destination d'autres blocs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void setup_graph_rank_links(const graph_rank_t *grank) +{ + size_t i; /* Boucle de parcours */ + + for (i = 0; i < grank->count; i++) + g_graph_cluster_setup_links(grank->clusters[i]); + +} + + +/****************************************************************************** +* * +* 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] * * * @@ -1761,6 +1834,8 @@ static void g_graph_cluster_class_init(GGraphClusterClass *klass) static void g_graph_cluster_init(GGraphCluster *cluster) { + cluster->container = cluster; + init_vspace_manager(&cluster->self); } @@ -1947,6 +2022,9 @@ static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub) sub->owner = cluster; + if (sub->ranks_count == 0) + sub->container = cluster; + } @@ -2035,7 +2113,6 @@ static void g_graph_cluster_extend_vspace_manager(GGraphCluster *target, leaving } - /****************************************************************************** * * * Paramètres : cluster = graphique de blocs à actualiser. * @@ -2053,13 +2130,12 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all { size_t dcount; /* Nombre de liens de dest. */ block_link_t *links; /* Liens associés au bloc */ - size_t i; /* Boucle de parcours #1 */ + size_t i; /* Boucle de parcours */ block_link_t *dest; /* Bloc visé par un autre */ 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 */ @@ -2100,6 +2176,8 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all /* Etablissement d'un embryon de lien */ + leaving->other = incoming; + g_graph_cluster_setup_link_for_target(cluster, target, leaving); break; @@ -2135,6 +2213,8 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all /* Etablissement d'un embryon de lien */ + leaving->other = incoming; + g_graph_cluster_setup_link_for_target(NULL, target, leaving); break; @@ -2174,7 +2254,7 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all /* Déplacement d'un éventuel lien central en position centrale */ - if (cluster->has_straight) + if (0 && cluster->has_straight) { size_t center; leaving_link_t *tmp; @@ -2223,8 +2303,102 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all /* Propagation de la mise en place */ for (i = 0; i < cluster->ranks_count; i++) - for (j = 0; j < cluster->ranks[i].count; j++) - g_graph_cluster_define_links(cluster->ranks[i].clusters[j], all); + define_graph_rank_links(&cluster->ranks[i], all); + +} + + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à actualiser. * +* * +* Description : Repère les liens marquants à destination d'autres blocs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_setup_links(GGraphCluster *cluster) +{ + size_t i; /* Boucle de parcours #1 */ + leaving_link_t *leaving; /* Départ de lien */ + incoming_link_t *incoming; /* Arrivée de lien */ + size_t level; /* Niveau du bloc courant */ + size_t target_level; /* Rang du bloc ciblé */ + GGraphCluster *container; /* Conteneur parent à parcourir*/ + size_t k; /* Boucle de parcours #2 */ + + for (i = 0; i < cluster->ba_count; i++) + { + leaving = cluster->bottom_anchors[i]; + incoming = leaving->other; + + if (incoming->type == ILT_LOOP) + continue; + + /* Est-ce un lien qui doit être vertical ? */ + + level = g_code_block_get_rank(leaving->owner->block); + target_level = g_code_block_get_rank(incoming->owner->block); + + if (target_level > (level + 1)) + { + leaving->straight = true; + leaving->straight_level = target_level; + continue; + } + + /* Est-ce une sortie de cluster ? */ + + if (leaving->owner->container != incoming->owner->container) + { + container = leaving->owner->container; + + for (k = 0; k < container->ranks_count; k++) + if (has_graph_rank_cluster(&container->ranks[k], incoming->owner)) + break; + + if (k == container->ranks_count) + { + leaving->cluster_exit = true; + continue; + } + + } + + /* Doit-on forcer un lien strictement vertical ? */ + + if (cluster->ba_count == 1) + { + /** + * Attention : les boucles aussi ont un seul lien sortant ! + * Le filtrage est cependant réalisé au début de l'itération. + */ + + container = leaving->owner->container; + + for (k = 0; k < container->ranks_count; k++) + if (has_graph_rank_cluster(&container->ranks[k], incoming->owner)) + break; + + if (k < container->ranks_count) + { + leaving->forced_straight = true; + leaving->straight_level = target_level; + continue; + } + + } + + } + + /* Propagation de la mise en place */ + + for (i = 0; i < cluster->ranks_count; i++) + setup_graph_rank_links(&cluster->ranks[i]); } @@ -2243,33 +2417,55 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all static void g_graph_cluster_dispatch_x(GGraphCluster *cluster) { - size_t k; /* Boucle de parcours #1 */ + size_t i; /* Boucle de parcours #1 */ + leaving_link_t *straight_leaving; /* Lien à présenter vertical */ + size_t straight_index; /* Indice du lien vertical */ + gint straight_start; /* Position initiale de départ */ + size_t straight_level; /* Rang atteint en ligne droite*/ const graph_rank_t *rank; /* Accès confortable au rang */ + gint start; /* Position initiale modifiable*/ 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 */ + leaving_link_t *leaving; /* Départ de lien */ + + /* Recherche d'une limite verticale */ + + straight_leaving = NULL; + + for (i = 0; i < cluster->ba_count; i++) + if (SHOULD_BE_VERTICAL(cluster->bottom_anchors[i])) + { + straight_leaving = cluster->bottom_anchors[i]; + straight_index = i; + + straight_start = g_graph_cluster_compute_leaving_link_position(cluster, i); + straight_level = straight_leaving->straight_level; + + break; + + } /** * Il est désormais temps de placer tous les blocs de code inférieurs. */ - for (k = 0; k < cluster->ranks_count; k++) + for (i = 0; i < cluster->ranks_count; i++) { - rank = &cluster->ranks[k]; + rank = &cluster->ranks[i]; /* Répartition autour d'une ligne verticale */ - if (cluster->has_straight) + if (straight_leaving != NULL) { - start = g_graph_cluster_compute_leaving_link_position(cluster, cluster->straight_index); - - if (get_graph_rank(rank) < cluster->straight_level) + if (get_graph_rank(rank) < straight_level) { + start = straight_start; + /* Répartition à gauche du lien */ for (j = rank->count; j > 0; j--) - if (*rank->clusters[j - 1]->parent_index < cluster->straight_index) + if (*rank->clusters[j - 1]->parent_index < straight_index) break; start -= HORIZONTAL_MARGIN / 2; @@ -2279,7 +2475,7 @@ static void g_graph_cluster_dispatch_x(GGraphCluster *cluster) /* Répartition à droite du lien */ for (j = 0; j < rank->count; j++) - if (*rank->clusters[j]->parent_index > cluster->straight_index) + if (*rank->clusters[j]->parent_index > straight_index) break; start += HORIZONTAL_MARGIN; @@ -2288,38 +2484,73 @@ static void g_graph_cluster_dispatch_x(GGraphCluster *cluster) } - else if (get_graph_rank(rank) == cluster->straight_level) + else if (get_graph_rank(rank) == 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); + dispatch_x_graph_rank(rank); - target = rank->clusters[0]; + if (straight_leaving->straight || straight_leaving->forced_straight) + { + /** + * 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); - idx = g_graph_cluster_find_incoming_link(target, cluster->bottom_anchors[cluster->straight_index]); + target = rank->clusters[0]; - end = g_graph_cluster_compute_incoming_link_position(target, idx); + idx = g_graph_cluster_find_incoming_link(target, straight_leaving); - g_graph_cluster_offset_x(target, start - end); + end = g_graph_cluster_compute_incoming_link_position(target, idx); - dispatch_x_graph_rank(rank); + g_graph_cluster_offset_x(target, straight_start - end); + + } + + straight_leaving = NULL; + + goto look_for_forced; } else - dispatch_x_graph_rank(rank); + assert(false); } /* Répartition homogène */ else + { dispatch_x_graph_rank(rank); + look_for_forced: + + /* Lien vertical interne ? */ + + if (rank->count != 1) + continue; + + target = rank->clusters[0]; + + if (target->ba_count != 1) + continue; + + leaving = target->bottom_anchors[0]; + + if (leaving->forced_straight) + { + straight_leaving = leaving; + straight_index = 0; + + straight_start = g_graph_cluster_compute_leaving_link_position(target, 0); + straight_level = leaving->straight_level; + + } + + } + } } @@ -2745,6 +2976,8 @@ static gint g_graph_cluster_compute_incoming_link_position(const GGraphCluster * static void g_graph_cluster_insert_left_margin(GGraphCluster *cluster, gint margin) { GGraphCluster *container; /* Parent direct à décaler */ + size_t i; /* Boucle de parcours */ + size_t straight_index; /* Indice du lien vertical */ if (margin > 0) { @@ -2763,10 +2996,20 @@ static void g_graph_cluster_insert_left_margin(GGraphCluster *cluster, gint marg */ while (container->owner != NULL) { - if (!container->owner->has_straight) + if (container->owner->ba_count == 0) break; - if (container->owner->straight_index != *container->parent_index) + for (i = 0; i < container->owner->ba_count; i++) + if (SHOULD_BE_VERTICAL(container->owner->bottom_anchors[i])) + { + straight_index = i; + break; + } + + if (i == container->owner->ba_count) + break; + + if (straight_index != *container->parent_index) break; container = container->owner; @@ -3322,6 +3565,8 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList * g_graph_cluster_define_links(result, all); + g_graph_cluster_setup_links(result); + /* Positionnements dans l'espace */ g_graph_cluster_dispatch_x(result); |