From 4d9b68040b6147215947d5c5a0c67e9e478fba1c Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Mon, 31 Dec 2018 00:41:52 +0100 Subject: Saved first steps towards a new graph layout. --- src/gtkext/graph/cluster.c | 1688 +++++++++++++++++++++++++++++--------------- src/gtkext/graph/cluster.h | 9 +- src/gtkext/graph/edge.h | 3 + 3 files changed, 1130 insertions(+), 570 deletions(-) diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c index 17af9ce..869851c 100644 --- a/src/gtkext/graph/cluster.c +++ b/src/gtkext/graph/cluster.c @@ -38,9 +38,39 @@ +/* ------------------------- LIEN SORTANT D'UN BLOC DE CODE ------------------------- */ + + +/* Détails sur le départ d'un lien */ +typedef struct _leaving_link_t +{ + GGraphCluster *owner; /* Propriétés du lien */ + + GdkPoint start; /* Point de départ d'un lien */ + size_t index; /* Indice sur ligne de départ */ + +} leaving_link_t; + + +/* Crée un point d'attache pour un lien sortant. */ +static leaving_link_t *create_leaving_link(GGraphCluster *, size_t); + +/* Détruit un point d'attache pour un lien sortant. */ +static void delete_leaving_link(leaving_link_t *); + +/* Calcule l'abscisse d'un lien à son départ d'un bloc. */ +static gint compute_leaving_link_position(const leaving_link_t *); + + + +/* ------------------------- LIEN ENTRANT D'UN BLOC DE CODE ------------------------- */ + + /* Définition du tracé d'un lien */ -typedef struct _incoming_edge +typedef struct _incoming_link_t { + GGraphCluster *owner; /* Propriétés du lien */ + InstructionLinkType type; /* Complexité du tracé */ const size_t *hslot; /* Couche horizontale réservée */ @@ -49,19 +79,24 @@ typedef struct _incoming_edge GGraphEdge *edge; /* Lien complet en préparation */ - GGraphCluster *origin; /* Bloc de départ du lien */ - const size_t *leaving_index; /* Indice du point de départ */ + const leaving_link_t *other; /* Autre extrémité du lien */ -} incoming_edge; +} incoming_link_t; -/* 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 */ +/* Crée un point d'attache pour un lien entrant simple. */ +static incoming_link_t *create_incoming_link(GGraphCluster *, InstructionLinkType, const leaving_link_t *); + +/* Détruit un point d'attache pour un lien entrant. */ +static void delete_incoming_link(incoming_link_t *); + +/* Compare deux liens entrants. */ +static int cmp_incoming_links(const incoming_link_t **, const incoming_link_t **); + + + +/* ---------------------- DESCENDANTS DIRECTS CLASSES PAR RANG ---------------------- */ -} leaving_edge; /* Réservation pour les lignes horizontales */ typedef struct _hspace_booking @@ -72,10 +107,8 @@ typedef struct _hspace_booking } hspace_booking; /* Découpage vertical */ -typedef struct _graph_rank +typedef struct _graph_rank_t { - size_t level; /* Niveau des blocs */ - hspace_booking **right2left; /* Réservations de D -> G */ size_t r2l_count; /* Quantité de ces réservations*/ @@ -85,7 +118,79 @@ typedef struct _graph_rank GGraphCluster **clusters; /* Ensembles de blocs */ size_t count; /* Nombre de ces ensembles */ -} graph_rank; +} graph_rank_t; + + +/* Initialise la gestion d'un ensemble de blocs de même rang. */ +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 *); + +/* 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 *); + +/* Etend un ensemble de blocs de même rang. */ +static void extend_graph_rank(graph_rank_t *, GGraphCluster *); + +/* Détermine l'emplacement requis d'un ensemble de blocs. */ +static void compute_graph_rank_needed_alloc(const graph_rank_t *, bool, GtkAllocation *); + +/* Affine l'abscisse d'un ensemble de blocs de même rang. */ +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. */ +static void offset_x_graph_rank(const graph_rank_t *, gint); + + + +/* ------------------------ ENCADREMENTS D'ESPACES VERTICAUX ------------------------ */ + + +/* Réservations d'espaces latéraux */ +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 */ + +} vspace_booking_t; + +/* Réservations d'espaces latéraux */ +typedef struct _vspace_manager_t +{ + vspace_booking_t *pending; /* Besoins exprimés */ + size_t pending_count; /* Nombre de ces besoins */ + + vspace_booking_t **left; /* Lignes disposées à gauche */ + size_t left_count; /* Quantité de ces lignes */ + + vspace_booking_t **right; /* Lignes disposées à droite */ + size_t right_count; /* Quantité de ces lignes */ + +} vspace_manager_t; + + +/* Initialise les réservations liens verticaux. */ +static void init_vspace_manager(vspace_manager_t *); + +/* Termine les réservations liens verticaux. */ +static void exit_vspace_manager(vspace_manager_t *); + + + +/* -------------------------- DEFINITION D'UN CHEF DE FILE -------------------------- */ + /* Mise en disposition de blocs en graphique (instance) */ struct _GGraphCluster @@ -101,23 +206,25 @@ struct _GGraphCluster //////////////////////////////////////// - incoming_edge **top_anchors; /* Accroches supérieures */ + incoming_link_t **top_anchors; /* Accroches supérieures */ size_t ta_count; /* Quantité de ces accroches */ GCodeBlock *block; /* Bloc d'origine représenté */ GtkWidget *display; /* Vue graphique associée */ GtkAllocation alloc; /* Emplacement final du bloc */ - leaving_edge **bottom_anchors; /* Accroches inférieures */ + leaving_link_t **bottom_anchors; /* Accroches inférieures */ size_t ba_count; /* Quantité de ces accroches */ bool has_straight; /* Présence d'une ligne droite */ size_t straight_level; /* Rang atteint en ligne droite*/ size_t straight_index; /* Indice du lien vertical */ - graph_rank *ranks; /* Répartition verticale */ + graph_rank_t *ranks; /* Répartition verticale */ size_t ranks_count; /* Nombre de divisions */ + vspace_manager_t vspaces; /* Gestion des liens latéraux */ + }; /* Mise en disposition de blocs en graphique (classe) */ @@ -151,13 +258,13 @@ static void g_graph_cluster_dispose(GGraphCluster *); static void g_graph_cluster_finalize(GGraphCluster *); /* Complète un graphique avec un sous-ensemble de blocs. */ -static void g_graph_cluster_add_sub(GGraphCluster *, GGraphCluster *, GCodeBlock *); +static void g_graph_cluster_add_sub(GGraphCluster *, GGraphCluster *); -/* Organisation la disposition d'un ensemble de blocs basiques. */ -static void g_graph_cluster_dispatch_x(GGraphCluster *); +/* Met en place les embryons de liens nécessaires. */ +static void g_graph_cluster_define_links(GGraphCluster *, GHashTable *); -/* Détermine une position pour un ensemble de blocs basiques. */ -//static void g_graph_cluster_set_x(GGraphCluster *, gint); +/* 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. */ static void g_graph_cluster_offset_x(GGraphCluster *, gint); @@ -172,9 +279,6 @@ 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 *); -/* Met en place les embryons de liens nécessaires. */ -static void g_graph_cluster_define_links(GGraphCluster *, GHashTable *); - /* 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); @@ -192,42 +296,61 @@ static void g_graph_cluster_resolve_links(const GGraphCluster *); +/* ------------------------- CALCUL DE REPARTITION DE BLOCS ------------------------- */ + + +/* Liste de blocs restants à traiter */ +typedef struct _pending_blocks +{ + size_t count; /* Taille de la liste */ + GCodeBlock *list[0]; /* Liste de blocs à traiter */ +} pending_blocks; -/* Indique le type défini par la GLib pour les mises en disposition graphique. */ -G_DEFINE_TYPE(GGraphCluster, g_graph_cluster, G_TYPE_OBJECT); +/* Met en place un ensemble de blocs sous forme graphique. */ +static GGraphCluster *setup_graph_clusters(GLoadedBinary *, const GBlockList *, size_t , segcnt_list *, pending_blocks *, GHashTable *); + + + +/* ---------------------------------------------------------------------------------- */ +/* LIEN SORTANT D'UN BLOC DE CODE */ +/* ---------------------------------------------------------------------------------- */ /****************************************************************************** * * -* Paramètres : klass = classe à initialiser. * +* Paramètres : owner = propriétaire du bloc de rattachement. * +* index = indice dans les liens de sortie. * * * -* Description : Initialise la classe des mises en disposition graphique. * +* Description : Crée un point d'attache pour un lien sortant. * * * -* Retour : - * +* Retour : Structure mise en place. * * * * Remarques : - * * * ******************************************************************************/ -static void g_graph_cluster_class_init(GGraphClusterClass *klass) +static leaving_link_t *create_leaving_link(GGraphCluster *owner, size_t index) { - GObjectClass *object; /* Autre version de la classe */ + leaving_link_t *result; /* Structure à retourner */ - object = G_OBJECT_CLASS(klass); + result = malloc(sizeof(leaving_link_t)); - object->dispose = (GObjectFinalizeFunc/* ! */)g_graph_cluster_dispose; - object->finalize = (GObjectFinalizeFunc)g_graph_cluster_finalize; + result->owner = owner; + + result->index = index; + + return result; } /****************************************************************************** * * -* Paramètres : cluster = instance à initialiser. * +* Paramètres : link = structure à libérer de la mémoire. * * * -* Description : Initialise une mise en disposition de blocs en graphique. * +* Description : Détruit un point d'attache pour un lien sortant. * * * * Retour : - * * * @@ -235,39 +358,87 @@ static void g_graph_cluster_class_init(GGraphClusterClass *klass) * * ******************************************************************************/ -static void g_graph_cluster_init(GGraphCluster *cluster) +static void delete_leaving_link(leaving_link_t *link) { + free(link); } /****************************************************************************** * * -* Paramètres : cluster = instance d'objet GLib à traiter. * +* Paramètres : link = information sur un lien à consulter. * * * -* Description : Supprime toutes les références externes. * +* 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_dispose(GGraphCluster *cluster) +static gint compute_leaving_link_position(const leaving_link_t *link) { - g_object_unref(G_OBJECT(cluster->block)); - g_object_unref(G_OBJECT(cluster->display)); + gint result; /* Position à retourner */ - G_OBJECT_CLASS(g_graph_cluster_parent_class)->dispose(G_OBJECT(cluster)); + result = g_graph_cluster_compute_leaving_link_position(link->owner, link->index); + + return result; } + +/* ---------------------------------------------------------------------------------- */ +/* LIEN ENTRANT D'UN BLOC DE CODE */ +/* ---------------------------------------------------------------------------------- */ + + /****************************************************************************** * * -* Paramètres : cluster = instance d'objet GLib à traiter. * +* Paramètres : owner = propriétaire du bloc de rattachement. * +* type = type de lien simple attendu. * +* other = point de départ du lien formé. * * * -* Description : Procède à la libération totale de la mémoire. * +* Description : Crée un point d'attache pour un lien entrant simple. * +* * +* Retour : Structure mise en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static incoming_link_t *create_incoming_link(GGraphCluster *owner, InstructionLinkType type, const leaving_link_t *other) +{ + incoming_link_t *result; /* Structure à retourner */ + + result = malloc(sizeof(incoming_link_t)); + + result->owner = owner; + + result->type = type; + + if (type == ILT_JUMP_IF_TRUE) + result->edge = g_graph_edge_new_true(&other->start, &result->y, &result->end); + + else if (type == ILT_JUMP_IF_FALSE) + result->edge = g_graph_edge_new_false(&other->start, &result->y, &result->end); + + else + result->edge = g_graph_edge_new(&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. * * * * Retour : - * * * @@ -275,75 +446,90 @@ static void g_graph_cluster_dispose(GGraphCluster *cluster) * * ******************************************************************************/ -static void g_graph_cluster_finalize(GGraphCluster *cluster) +static void delete_incoming_link(incoming_link_t *link) { - G_OBJECT_CLASS(g_graph_cluster_parent_class)->finalize(G_OBJECT(cluster)); + free(link); } /****************************************************************************** * * -* Paramètres : block = premier bloc du groupe. * -* highlighted = gestionnaire de surbrillance pour segments. * -* binary = binaire charger dont le code est à représenter.* +* Paramètres : a = premier lien entrant à comparer. * +* b = second lien entrant à comparer. * * * -* Description : * +* Description : Compare deux liens entrants. * * * -* Retour : Adresse de la structure mise en place. * +* Retour : Bilan de comparaison. * * * * Remarques : - * * * ******************************************************************************/ -GGraphCluster *g_graph_cluster_new(GCodeBlock *block, segcnt_list *highlighted, GLoadedBinary *binary) +static int cmp_incoming_links(const incoming_link_t **a, const incoming_link_t **b) { - GGraphCluster *result; /* Structure à retourner */ - GBufferView *view; /* Partie affichée du tampon */ - GtkRequisition requisition; /* Taille à l'écran actuelle */ + int result; /* Bilan à retourner */ + gint pos_a; /* Point de départ pour A */ + gint pos_b; /* Point de départ pour B */ - result = g_object_new(G_TYPE_GRAPH_CLUSTER, NULL); + pos_a = compute_leaving_link_position((*a)->other); - /* Encapsulation du bloc d'entrée */ + pos_b = compute_leaving_link_position((*b)->other); - result->block = block; - g_object_ref(G_OBJECT(block)); + if (pos_a < pos_b) + result = -1; - view = g_code_block_get_view(result->block, highlighted); + else if (pos_a > pos_b) + result = 1; - result->display = gtk_block_display_new(view); - gtk_widget_show(result->display); + else + result = 0; - g_loaded_panel_set_content(G_LOADED_PANEL(result->display), G_LOADED_CONTENT(binary)); + return result; - gtk_block_display_override_view_index(GTK_BLOCK_DISPLAY(result->display), BVW_GRAPH); +} - gtk_display_panel_show_border(GTK_DISPLAY_PANEL(result->display), true); - /* Détermination d'une position initiale centrée */ - gtk_widget_get_preferred_size(result->display, NULL, &requisition); +/* ---------------------------------------------------------------------------------- */ +/* DESCENDANTS DIRECTS CLASSES PAR RANG */ +/* ---------------------------------------------------------------------------------- */ - result->alloc.x = -requisition.width / 2; - result->alloc.y = 0; - result->alloc.width = requisition.width; - result->alloc.height = requisition.height; +/****************************************************************************** +* * +* Paramètres : grank = structure à initialiser. [OUT] * +* cluster = chef de file d'un ensemble de blocs. * +* * +* Description : Initialise la gestion d'un ensemble de blocs de même rang. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ - printf("BLOCK INIT :: %d <> %d\n", result->alloc.x, result->alloc.width); +static void init_graph_rank(graph_rank_t *grank, GGraphCluster *cluster) +{ + grank->right2left = NULL; + grank->r2l_count = 0; - return result; + grank->left2right = NULL; + grank->l2r_count = 0; + + grank->clusters = malloc(sizeof(GGraphCluster *)); + grank->count = 1; + + grank->clusters[0] = cluster; } /****************************************************************************** * * -* Paramètres : cluster = graphique de blocs à compléter. * -* sub = sous-ensemble à intégrer. * -* block = bloc basique de départ du sous-ensemble. * +* Paramètres : grank = structure à vider. * * * -* Description : Complète un graphique avec un sous-ensemble de blocs. * +* Description : Termine la gestion d'un ensemble de blocs de même rang. * * * * Retour : - * * * @@ -351,72 +537,94 @@ GGraphCluster *g_graph_cluster_new(GCodeBlock *block, segcnt_list *highlighted, * * ******************************************************************************/ -static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub, GCodeBlock *block) +static void exit_graph_rank(graph_rank_t *grank) { - size_t 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 */ - level = g_code_block_get_rank(block); + for (i = 0; i < grank->r2l_count; i++) + free(grank->right2left[i]); - for (i = 0; i < cluster->ranks_count; i++) - if (cluster->ranks[i].level == level) - break; + if (grank->right2left != NULL) + free(grank->right2left); - if (i == cluster->ranks_count) - { - new.level = level; + for (i = 0; i < grank->l2r_count; i++) + free(grank->left2right[i]); - new.right2left = NULL; - new.r2l_count = 0; + if (grank->left2right != NULL) + free(grank->left2right); - new.left2right = NULL; - new.l2r_count = 0; + assert(grank->clusters != NULL); - new.clusters = (GGraphCluster **)calloc(1, sizeof(GGraphCluster *)); - new.count = 1; + free(grank->clusters); - new.clusters[0] = sub; +} - int cmp_graph_rank(const graph_rank *a, const graph_rank *b) - { - if (a->level < b->level) - return -1; - else if (a->level > b->level) - return 1; +/****************************************************************************** +* * +* 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. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static size_t get_graph_rank(const graph_rank_t *grank) +{ + size_t result; /* Rang à retourner */ - else - return 0; + result = g_code_block_get_rank(grank->clusters[0]->block); - } + return result; - cluster->ranks = qinsert(cluster->ranks, &cluster->ranks_count, - sizeof(graph_rank), (__compar_fn_t)cmp_graph_rank, &new); +} - } - else - { - rank = &cluster->ranks[i]; +/****************************************************************************** +* * +* Paramètres : a = premier ensemble de même rang à comparer. * +* b = second ensemble de même rang à comparer. * +* * +* Description : Compare deux rangées de blocs de code. * +* * +* Retour : Bilan de comparaison. * +* * +* Remarques : - * +* * +******************************************************************************/ - rank->count++; - rank->clusters = (GGraphCluster **)realloc(rank->clusters, - sizeof(GGraphCluster *) * rank->count); +static int cmp_graph_rank(const graph_rank_t *a, const graph_rank_t *b) +{ + int result; /* Bilan à retourner */ + size_t level_a; /* Niveau de l'ensemble A */ + size_t level_b; /* Niveau de l'ensemble B */ - rank->clusters[rank->count - 1] = sub; + level_a = get_graph_rank(a); + level_b = get_graph_rank(b); - } + if (level_a < level_b) + result = -1; + + else if (level_a > level_b) + result = 1; + + else + result = 0; + + return result; } /****************************************************************************** * * -* Paramètres : cluster = graphique de blocs à manipuler. * +* Paramètres : grank = structure à compléter. * +* cluster = chef de file d'un ensemble de blocs. * * * -* Description : Organisation la disposition d'un ensemble de blocs basiques. * +* Description : Etend un ensemble de blocs de même rang. * * * * Retour : - * * * @@ -424,179 +632,828 @@ static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub, * * ******************************************************************************/ -static void g_graph_cluster_dispatch_x(GGraphCluster *cluster) +static void extend_graph_rank(graph_rank_t *grank, 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 */ + grank->count++; + grank->clusters = realloc(grank->clusters, sizeof(GGraphCluster *) * grank->count); - /** - * 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 ! - */ + grank->clusters[grank->count - 1] = cluster; - 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); +/****************************************************************************** +* * +* 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] * +* * +* Description : Détermine l'emplacement requis d'un ensemble de blocs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ - if (pos_a < pos_b) - result = -1; +static void compute_graph_rank_needed_alloc(const graph_rank_t *grank, bool last, GtkAllocation *alloc) +{ + GtkAllocation needed; /* Taille requise */ - else if (pos_a > pos_b) - result = 1; + switch (grank->count) + { + case 1: - else - result = 0; + g_graph_cluster_compute_needed_alloc(grank->clusters[0], &needed); - return result; + if (needed.x < alloc->x) + { + alloc->width += (alloc->x - needed.x); + alloc->x = needed.x; + } - } + if ((needed.x + needed.width) > (alloc->x + alloc->width)) + alloc->width += needed.x + needed.width - alloc->x - alloc->width; - qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_edge *), (__compar_fn_t)compare_incoming_edges); + /* La hauteur maximale n'est présente qu'avec le dernier morceau */ + if (last) + { + if ((needed.y + needed.height) > (alloc->y + alloc->height)) + alloc->height += needed.y + needed.height - alloc->y - alloc->height; + } - /** - * Il est désormais temps de placer tous les blocs de code inférieurs. - */ + break; + + default: + + assert(grank->count >= 2); + + g_graph_cluster_compute_needed_alloc(grank->clusters[0], &needed); + + if (needed.x < alloc->x) + { + alloc->width += (alloc->x - needed.x); + alloc->x = needed.x; + } + + /* La hauteur maximale n'est présente qu'avec le dernier morceau */ + if (last) + { + if ((needed.y + needed.height) > (alloc->y + alloc->height)) + alloc->height += needed.y + needed.height - alloc->y - alloc->height; + } + + g_graph_cluster_compute_needed_alloc(grank->clusters[grank->count - 1], &needed); + + if ((needed.x + needed.width) > (alloc->x + alloc->width)) + alloc->width += needed.x + needed.width - alloc->x - alloc->width; + + /* La hauteur maximale n'est présente qu'avec le dernier morceau */ + if (last) + { + if ((needed.y + needed.height) > (alloc->y + alloc->height)) + alloc->height += needed.y + needed.height - alloc->y - alloc->height; + } + + break; + + } + +} + + +/****************************************************************************** +* * +* 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. * +* dir = direction du parcours. * +* * +* Description : Affine l'abscisse d'un ensemble de blocs de même rang. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void _place_graph_rank_clusters(GGraphCluster **iter, size_t loop, gint base, int dir) +{ + size_t i; /* Boucle de parcours */ + GtkAllocation needed; /* Taille requise */ + + assert(dir == -1 || dir == 1); + + for (i = 0; i < loop; i++, iter += dir) + { + g_graph_cluster_dispatch_x(*iter); + + g_graph_cluster_compute_needed_alloc(*iter, &needed); + + if (dir > 0) + g_graph_cluster_offset_x(*iter, base - needed.x); + else + g_graph_cluster_offset_x(*iter, base - needed.x - needed.width); + + base += dir * (needed.width + HORIZONTAL_MARGIN); + + } + +} + + +/****************************************************************************** +* * +* Paramètres : grank = ensemble de blocs de même rang à manipuler. * +* * +* Description : Organise la disposition d'un ensemble de blocs basiques. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void dispatch_x_graph_rank(const graph_rank_t *grank) +{ + size_t mid; /* Position centrale de départ */ + gint start; /* Position initiale de départ */ + + if (grank->count % 2 == 1) + { + if (grank->count > 1) + { + mid = grank->count / 2; + + start = grank->clusters[mid]->alloc.x - HORIZONTAL_MARGIN; + + _place_graph_rank_clusters(grank->clusters + mid - 1, mid, start, -1); + + start *= -1; + + _place_graph_rank_clusters(grank->clusters + mid + 1, mid, start, 1); + + } + + else + g_graph_cluster_dispatch_x(grank->clusters[0]); + + } + + else + { + mid = grank->count / 2 - 1; + + start = - HORIZONTAL_MARGIN / 2; + + _place_graph_rank_clusters(grank->clusters + mid, mid + 1, start, -1); + + start *= -1; + + _place_graph_rank_clusters(grank->clusters + mid + 1, mid + 1, start, 1); + + } + +} + + +/****************************************************************************** +* * +* 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. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void offset_x_graph_rank(const graph_rank_t *grank, gint offset) +{ + size_t i; /* Boucle de parcours */ + + for (i = 0; i < grank->count; i++) + g_graph_cluster_offset_x(grank->clusters[i], offset); + +} + + + +/* ---------------------------------------------------------------------------------- */ +/* ENCADREMENTS D'ESPACES VERTICAUX */ +/* ---------------------------------------------------------------------------------- */ + + +/****************************************************************************** +* * +* Paramètres : manager = structure à initialiser. * +* * +* Description : Initialise les réservations liens verticaux. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void init_vspace_manager(vspace_manager_t *manager) +{ + manager->pending = NULL; + manager->pending_count = 0; + + manager->left = NULL; + manager->left_count = 0; + + manager->right = NULL; + manager->right_count = 0; + +} + + +/****************************************************************************** +* * +* Paramètres : manager = structure à vider. * +* * +* Description : Termine les réservations liens verticaux. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void exit_vspace_manager(vspace_manager_t *manager) +{ + if (manager->pending != NULL) + free(manager->pending); + + if (manager->left != NULL) + free(manager->left); + + if (manager->right != NULL) + free(manager->right); + +} + + + +/* ---------------------------------------------------------------------------------- */ +/* DEFINITION D'UN CHEF DE FILE */ +/* ---------------------------------------------------------------------------------- */ + + +/* Indique le type défini par la GLib pour les mises en disposition graphique. */ +G_DEFINE_TYPE(GGraphCluster, g_graph_cluster, G_TYPE_OBJECT); + + +/****************************************************************************** +* * +* Paramètres : klass = classe à initialiser. * +* * +* Description : Initialise la classe des mises en disposition graphique. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_class_init(GGraphClusterClass *klass) +{ + GObjectClass *object; /* Autre version de la classe */ + + object = G_OBJECT_CLASS(klass); + + object->dispose = (GObjectFinalizeFunc/* ! */)g_graph_cluster_dispose; + object->finalize = (GObjectFinalizeFunc)g_graph_cluster_finalize; + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = instance à initialiser. * +* * +* Description : Initialise une mise en disposition de blocs en graphique. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_init(GGraphCluster *cluster) +{ + init_vspace_manager(&cluster->vspaces); + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = instance d'objet GLib à traiter. * +* * +* Description : Supprime toutes les références externes. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_dispose(GGraphCluster *cluster) +{ + g_clear_object(&cluster->block); + g_clear_object(&cluster->display); + + G_OBJECT_CLASS(g_graph_cluster_parent_class)->dispose(G_OBJECT(cluster)); + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = instance d'objet GLib à traiter. * +* * +* Description : Procède à la libération totale de la mémoire. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_finalize(GGraphCluster *cluster) +{ + size_t i; /* Boucle de parcours */ + + for (i = 0; i < cluster->ta_count; i++) + delete_incoming_link(cluster->top_anchors[i]); + + if (cluster->top_anchors != NULL) + free(cluster->top_anchors); + + for (i = 0; i < cluster->ba_count; i++) + delete_leaving_link(cluster->bottom_anchors[i]); + + if (cluster->bottom_anchors != NULL) + free(cluster->bottom_anchors); + + for (i = 0; i < cluster->ranks_count; i++) + exit_graph_rank(&cluster->ranks[i]); + + if (cluster->ranks != NULL) + free(cluster->ranks); + + exit_vspace_manager(&cluster->vspaces); + + G_OBJECT_CLASS(g_graph_cluster_parent_class)->finalize(G_OBJECT(cluster)); + +} + + +/****************************************************************************** +* * +* Paramètres : block = premier bloc du groupe. * +* highlighted = gestionnaire de surbrillance pour segments. * +* binary = binaire charger dont le code est à représenter.* +* * +* Description : * +* * +* Retour : Adresse de la structure mise en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +GGraphCluster *g_graph_cluster_new(GCodeBlock *block, segcnt_list *highlighted, GLoadedBinary *binary) +{ + 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); + + /* Encapsulation du bloc d'entrée */ + + result->block = block; + g_object_ref(G_OBJECT(block)); + + view = g_code_block_get_view(result->block, highlighted); + + result->display = gtk_block_display_new(view); + gtk_widget_show(result->display); + + g_loaded_panel_set_content(G_LOADED_PANEL(result->display), G_LOADED_CONTENT(binary)); + + gtk_block_display_override_view_index(GTK_BLOCK_DISPLAY(result->display), BVW_GRAPH); + + gtk_display_panel_show_border(GTK_DISPLAY_PANEL(result->display), true); + + /* Détermination d'une position initiale centrée */ + + gtk_widget_get_preferred_size(result->display, NULL, &requisition); + + result->alloc.x = -requisition.width / 2; + result->alloc.y = 0; + + result->alloc.width = requisition.width; + result->alloc.height = requisition.height; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à compléter. * +* sub = sous-ensemble à intégrer. * +* * +* Description : Complète un graphique avec un sous-ensemble de blocs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub) +{ + size_t level; /* Niveau du nouvel ensemble */ + size_t i; /* Boucle de parcours */ + graph_rank_t new; /* Nouvel étage à insérer */ + + level = g_code_block_get_rank(sub->block); + + for (i = 0; i < cluster->ranks_count; i++) + if (get_graph_rank(&cluster->ranks[i]) == level) + break; + + if (i == cluster->ranks_count) + { + init_graph_rank(&new, sub); + + cluster->ranks = qinsert(cluster->ranks, &cluster->ranks_count, + sizeof(graph_rank_t), (__compar_fn_t)cmp_graph_rank, &new); + + } + + else + extend_graph_rank(&cluster->ranks[i], sub); + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à actualiser. * +* all = table regroupant tous les groupes créés. * +* * +* Description : Met en place les embryons de liens nécessaires. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +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 */ + + /* 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); + + for (i = 0; i < dcount; i++) + { + dest = g_code_block_get_destination(cluster->block, i); + + switch (dest->type) + { + case ILT_EXEC_FLOW: + case ILT_JUMP: + case ILT_CASE_JUMP: + case ILT_JUMP_IF_TRUE: + case ILT_JUMP_IF_FALSE: + + target = G_GRAPH_CLUSTER(g_hash_table_lookup(all, dest->linked)); + assert(target != NULL); + + /* Point de départ */ + + leaving = create_leaving_link(cluster, cluster->ba_count); + + cluster->bottom_anchors = realloc(cluster->bottom_anchors, + ++cluster->ba_count * sizeof(leaving_link_t *)); + + 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); + + target->top_anchors = realloc(target->top_anchors, + ++target->ta_count * sizeof(incoming_link_t *)); + + target->top_anchors[target->ta_count - 1] = incoming; + + /* 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; + } - void place_sub(GGraphCluster **iter, size_t loop, gint base, int dir) - { - size_t i; /* Boucle de parcours #2 */ - GtkAllocation needed; /* Taille requise */ - assert(dir == -1 || dir == 1); - for (i = 0; i < loop; i++, iter += dir) - { - g_graph_cluster_dispatch_x(*iter); - g_graph_cluster_compute_needed_alloc(*iter, &needed); + break; - if (dir > 0) - g_graph_cluster_offset_x(*iter, base - needed.x); - else - g_graph_cluster_offset_x(*iter, base - needed.x - needed.width); - base += dir * (needed.width + HORIZONTAL_MARGIN); + case ILT_LOOP: - } - } - for (k = 0; k < cluster->ranks_count; k++) - { - rank = &cluster->ranks[k]; - /* Répartition autour d'une ligne verticale */ - if (cluster->has_straight) - { - start = g_graph_cluster_compute_leaving_link_position(cluster, cluster->straight_index); + target = G_GRAPH_CLUSTER(g_hash_table_lookup(all, dest->linked)); + assert(target != NULL); - if (rank->level < cluster->straight_level) - { - /* Répartition à gauche du lien */ + /* Point de départ */ - for (j = rank->count; j > 0; j--) - if (*rank->clusters[j - 1]->parent_index < cluster->straight_index) - break; + leaving = create_leaving_link(cluster, cluster->ba_count); - start -= HORIZONTAL_MARGIN / 2; + cluster->bottom_anchors = realloc(cluster->bottom_anchors, + ++cluster->ba_count * sizeof(leaving_link_t *)); - place_sub(rank->clusters, j, start, -1); + cluster->bottom_anchors[cluster->ba_count - 1] = leaving; - /* Répartition à droite du lien */ + /* Est-ce un lien qui doit être vertical ? */ - for (j = 0; j < rank->count; j++) - if (*rank->clusters[j]->parent_index > cluster->straight_index) - break; - start += HORIZONTAL_MARGIN; + /* FIXME : trop de boucles ! */ - place_sub(rank->clusters + j, rank->count - j, start, 1); + 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); + + target->top_anchors = realloc(target->top_anchors, + ++target->ta_count * sizeof(incoming_link_t *)); + + target->top_anchors[target->ta_count - 1] = incoming; + + /* 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); + + break; + + default: + break; } - /* Répartition homogène */ - else - { - rcount = rank->count; + unref_block_link(dest); - if (rcount % 2 == 1) - { - if (rcount > 1) - { - mid = rcount / 2; + } - start = rank->clusters[mid]->alloc.x - HORIZONTAL_MARGIN; + g_code_block_unlock_dest(cluster->block); - place_sub(rank->clusters + mid - 1, mid, start, -1); - start *= -1; - place_sub(rank->clusters + mid + 1, mid, start, 1); - } + /* Déplacement d'un éventuel lien central */ - else - g_graph_cluster_dispatch_x(rank->clusters[0]); + if (cluster->has_straight) + { + size_t center; + leaving_link_t *tmp; - } + if (cluster->ba_count % 2 == 0) + center = cluster->ba_count / 2 - 1; + else + center = cluster->ba_count / 2; - else - { - mid = rcount / 2 - 1; + 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_link_t *)); - start = - HORIZONTAL_MARGIN / 2; + cluster->bottom_anchors[center] = tmp; - place_sub(rank->clusters + mid, mid + 1, start, -1); + for (i = cluster->straight_index; i <= center; i++) + cluster->bottom_anchors[i]->index = i; - start *= -1; + cluster->straight_index = center; - place_sub(rank->clusters + mid + 1, mid + 1, start, 1); + } - } + 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_link_t *)); + + 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++) + for (j = 0; j < cluster->ranks[i].count; j++) + g_graph_cluster_define_links(cluster->ranks[i].clusters[j], all); + } /****************************************************************************** * * -* Paramètres : cluster = graphique de blocs à actualiser. * -* x = position finale sur l'axe des abscisses. * +* Paramètres : cluster = graphique de blocs à manipuler. * * * -* Description : Détermine une position pour un ensemble de blocs basiques. * +* Description : Organise la disposition d'un ensemble de blocs basiques. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ -/* -static void g_graph_cluster_set_x(GGraphCluster *cluster, gint x) + +static void g_graph_cluster_dispatch_x(GGraphCluster *cluster) { - g_graph_cluster_offset_x(cluster, -cluster->alloc.x); + size_t k; /* Boucle de parcours #1 */ + const graph_rank_t *rank; /* Accès confortable au rang */ + size_t j; /* Boucle de parcours #2 */ + 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 ! + */ + + 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]; + + /* Répartition autour d'une ligne verticale */ + if (cluster->has_straight) + { + start = g_graph_cluster_compute_leaving_link_position(cluster, cluster->straight_index); + + if (get_graph_rank(rank) < cluster->straight_level) + { + /* Répartition à gauche du lien */ + + for (j = rank->count; j > 0; j--) + if (*rank->clusters[j - 1]->parent_index < cluster->straight_index) + break; + + start -= HORIZONTAL_MARGIN / 2; + + _place_graph_rank_clusters(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; - g_graph_cluster_offset_x(cluster, x); + start += HORIZONTAL_MARGIN; + + _place_graph_rank_clusters(rank->clusters + j, rank->count - j, start, 1); + + } + + } + + /* Répartition homogène */ + else + dispatch_x_graph_rank(rank); + + } } -*/ /****************************************************************************** @@ -614,14 +1471,12 @@ static void g_graph_cluster_set_x(GGraphCluster *cluster, gint x) static void g_graph_cluster_offset_x(GGraphCluster *cluster, gint offset) { - size_t i; /* Boucle de parcours #1 */ - size_t j; /* Boucle de parcours #2 */ + size_t i; /* Boucle de parcours */ cluster->alloc.x += offset; for (i = 0; i < cluster->ranks_count; i++) - for (j = 0; j < cluster->ranks[i].count; j++) - g_graph_cluster_offset_x(cluster->ranks[i].clusters[j], offset); + offset_x_graph_rank(&cluster->ranks[i], offset); } @@ -642,7 +1497,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 */ + 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é */ @@ -687,103 +1542,39 @@ static void g_graph_cluster_set_y(GGraphCluster *cluster, gint base) g_graph_cluster_compute_needed_alloc(sub, &alloc); - if ((alloc.y + alloc.height) > max) - max = alloc.y + alloc.height; - - } - - base = max; - - } - -} - - -/****************************************************************************** -* * -* Paramètres : cluster = encapsulation à consulter. * -* alloc = emplacement idéal pour l'affichage. * -* * -* Description : Détermine l'emplacement requis d'un ensemble de blocs. * -* * -* Retour : - * -* * -* Remarques : - * -* * -******************************************************************************/ - -void g_graph_cluster_compute_needed_alloc(const GGraphCluster *cluster, GtkAllocation *alloc) -{ - GtkAllocation needed; /* Taille requise */ - size_t i; /* Boucle de parcours */ - size_t rcount; /* Nombre d'ensembles présents */ - - *alloc = cluster->alloc; - - for (i = 0; i < cluster->ranks_count; i++) - { - rcount = cluster->ranks[i].count; - - switch (rcount) - { - case 1: - - g_graph_cluster_compute_needed_alloc(cluster->ranks[i].clusters[0], &needed); - - if (needed.x < alloc->x) - { - alloc->width += (alloc->x - needed.x); - alloc->x = needed.x; - } - - if ((needed.x + needed.width) > (alloc->x + alloc->width)) - alloc->width += needed.x + needed.width - alloc->x - alloc->width; - - /* La hauteur maximale n'est présente qu'avec le dernier morceau */ - if ((i + 1) == cluster->ranks_count) - { - if ((needed.y + needed.height) > (alloc->y + alloc->height)) - alloc->height += needed.y + needed.height - alloc->y - alloc->height; - } - - break; - - default: - - assert(rcount >= 2); + if ((alloc.y + alloc.height) > max) + max = alloc.y + alloc.height; - g_graph_cluster_compute_needed_alloc(cluster->ranks[i].clusters[0], &needed); + } - if (needed.x < alloc->x) - { - alloc->width += (alloc->x - needed.x); - alloc->x = needed.x; - } + base = max; - /* La hauteur maximale n'est présente qu'avec le dernier morceau */ - if ((i + 1) == cluster->ranks_count) - { - if ((needed.y + needed.height) > (alloc->y + alloc->height)) - alloc->height += needed.y + needed.height - alloc->y - alloc->height; - } + } - g_graph_cluster_compute_needed_alloc(cluster->ranks[i].clusters[rcount - 1], &needed); +} - if ((needed.x + needed.width) > (alloc->x + alloc->width)) - alloc->width += needed.x + needed.width - alloc->x - alloc->width; - /* La hauteur maximale n'est présente qu'avec le dernier morceau */ - if ((i + 1) == cluster->ranks_count) - { - if ((needed.y + needed.height) > (alloc->y + alloc->height)) - alloc->height += needed.y + needed.height - alloc->y - alloc->height; - } +/****************************************************************************** +* * +* Paramètres : cluster = encapsulation à consulter. * +* alloc = emplacement idéal pour l'affichage. * +* * +* Description : Détermine l'emplacement requis d'un ensemble de blocs. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ - break; +void g_graph_cluster_compute_needed_alloc(const GGraphCluster *cluster, GtkAllocation *alloc) +{ + size_t i; /* Boucle de parcours */ - } + *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); } @@ -877,7 +1668,7 @@ static GGraphCluster *g_graph_cluster_find_lower_dest_cluster(const GGraphCluste { GGraphCluster *result; /* Trouvaille à retourner */ size_t i; /* Boucle de parcours #1 */ - const graph_rank *rank; /* Confort d'accès */ + const graph_rank_t *rank; /* Confort d'accès */ size_t j; /* Boucle de parcours #2 */ GArchInstruction *instr; /* Instruction à comparer */ @@ -903,210 +1694,6 @@ static GGraphCluster *g_graph_cluster_find_lower_dest_cluster(const GGraphCluste } #endif -/****************************************************************************** -* * -* Paramètres : cluster = graphique de blocs à actualiser. * -* all = table regroupant tous les groupes créés. * -* * -* Description : Met en place les embryons de liens nécessaires. * -* * -* Retour : - * -* * -* Remarques : - * -* * -******************************************************************************/ - -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_edge *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_edge *incoming; /* Définitions d'arrivée */ - - /* 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); - - for (i = 0; i < dcount; i++) - { - dest = g_code_block_get_destination(cluster->block, i); - - switch (dest->type) - { - case ILT_EXEC_FLOW: - case ILT_JUMP: - case ILT_CASE_JUMP: - case ILT_JUMP_IF_TRUE: - case ILT_JUMP_IF_FALSE: - - target = G_GRAPH_CLUSTER(g_hash_table_lookup(all, dest->linked)); - assert(target != NULL); - - /* Point de départ */ - - 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; - } - - } - - - - - - - /* Point d'arrivée */ - - incoming = (incoming_edge *)calloc(1, sizeof(incoming_edge)); - - 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 */ - - leaving->index = cluster->ba_count - 1; - - incoming->type = dest->type; - - if (incoming->type == ILT_JUMP_IF_TRUE) - incoming->edge = g_graph_edge_new_true(&leaving->start, &incoming->y, &incoming->end); - - else if (incoming->type == ILT_JUMP_IF_FALSE) - incoming->edge = g_graph_edge_new_false(&leaving->start, &incoming->y, &incoming->end); - - else - 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; - - - case ILT_LOOP: - - /* TODO */ - //assert(false); - - break; - - default: - break; - - } - - unref_block_link(dest); - - } - - g_code_block_unlock_dest(cluster->block); - - - - - /* 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++) - for (j = 0; j < cluster->ranks[i].count; j++) - g_graph_cluster_define_links(cluster->ranks[i].clusters[j], all); - -} /****************************************************************************** @@ -1269,7 +1856,7 @@ static void g_graph_cluster_compute_link_x_positions(GGraphCluster *cluster) static void g_graph_cluster_book_hspace_for_links(GGraphCluster *cluster) { size_t i; /* Boucle de parcours #1 */ - graph_rank *rank; /* Rangée à manipuler */ + graph_rank_t *rank; /* Rangée à manipuler */ size_t j; /* Boucle de parcours #2 */ GGraphCluster *sub; /* Bloc inférieur à manipuler */ size_t k; /* Boucle de parcours #3 */ @@ -1398,7 +1985,7 @@ 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 */ + incoming_link_t *incoming; /* Raccourci pour le confort */ size_t j; /* Boucle de parcours #2 */ /* Du côté des départs... */ @@ -1470,36 +2057,9 @@ static void g_graph_cluster_resolve_links(const GGraphCluster *cluster) - - - - - - - - - - - - - -/* Liste de blocs restants à traiter */ -typedef struct _pending_blocks -{ - size_t count; /* Taille de la liste */ - GCodeBlock *list[0]; /* Liste de blocs à traiter */ - -} pending_blocks; - - - - - -/* Met en place un ensemble de blocs sous forme graphique. */ -static GGraphCluster *setup_graph_clusters(GLoadedBinary *, const GBlockList *, size_t , segcnt_list *, pending_blocks *, GHashTable *); - - - +/* ---------------------------------------------------------------------------------- */ +/* CALCUL DE REPARTITION DE BLOCS */ +/* ---------------------------------------------------------------------------------- */ /****************************************************************************** @@ -1645,7 +2205,7 @@ static GGraphCluster *setup_graph_clusters(GLoadedBinary *binary, const GBlockLi sub = setup_graph_clusters(binary, list, next, highlighted, pending, all); - g_graph_cluster_add_sub(result, sub, block); + g_graph_cluster_add_sub(result, sub); } @@ -1661,14 +2221,11 @@ static GGraphCluster *setup_graph_clusters(GLoadedBinary *binary, const GBlockLi } - - - /****************************************************************************** * * -* Paramètres : blocXXXXXXXXXXXXXXXXXXXXks = ensemble des blocs basiques déjà découpés. * -* views = morceaux de codXXXXXXXXXXXXXXXXXxe à afficher de façon organisée. * -* count = quantité de ces morceaux de code.XXXXXXXXXXXXXXXXXX * +* Paramètres : binary = binaire charger dont le code est à représenter.* +* list = ensemble de blocs basiques à manipuler. * +* highlighted = gestionnaire de surbrillance pour segments. * * * * Description : Construit un graphique à partir de blocs basiques. * * * @@ -1686,12 +2243,15 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList * pending_blocks *pending; /* Suivi des blocs à traiter */ GtkAllocation needed; /* Taille requise */ + /* Création des éléments */ all = g_hash_table_new(NULL, NULL); count = g_block_list_count_blocks(list); - pending = (pending_blocks *)calloc(1, sizeof(pending_blocks) + count * sizeof(GCodeBlock *)); + pending = malloc(sizeof(pending_blocks) + count * sizeof(GCodeBlock *)); + + pending->count = 0; result = setup_graph_clusters(binary, list, 0, highlighted, pending, all); @@ -1699,12 +2259,6 @@ 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); diff --git a/src/gtkext/graph/cluster.h b/src/gtkext/graph/cluster.h index 11ce66e..00c6d82 100644 --- a/src/gtkext/graph/cluster.h +++ b/src/gtkext/graph/cluster.h @@ -25,13 +25,15 @@ #define _GTKEXT_GRAPH_CLUSTER_H - #include "../gtkgraphdisplay.h" #include "../../analysis/binary.h" #include "../../analysis/disass/block.h" +/* -------------------------- DEFINITION D'UN CHEF DE FILE -------------------------- */ + + #define G_TYPE_GRAPH_CLUSTER g_graph_cluster_get_type() #define G_GRAPH_CLUSTER(obj) (G_TYPE_CHECK_INSTANCE_CAST((obj), G_TYPE_GRAPH_CLUSTER, GGraphCluster)) #define G_IS_GRAPH_CLUSTER(obj) (G_TYPE_CHECK_INSTANCE_TYPE((obj), G_TYPE_GRAPH_CLUSTER)) @@ -64,10 +66,11 @@ void g_graph_cluster_place(GGraphCluster *, GtkGraphDisplay *); +/* ------------------------- CALCUL DE REPARTITION DE BLOCS ------------------------- */ -GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *list, segcnt_list *highlighted); - +/* Construit un graphique à partir de blocs basiques. */ +GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *, const GBlockList *, segcnt_list *); diff --git a/src/gtkext/graph/edge.h b/src/gtkext/graph/edge.h index 4dbc195..d000eb5 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) +#define g_graph_edge_new_loop(start, yt, yb, end) \ + _g_graph_edge_new(start, (const GdkPoint *[]) { yt, yb }, 2, end, EGC_BLUE) + /* Fournit les abscisses des points extrèmes de la ligne. */ void g_graph_edge_get_x_borders(const GGraphEdge *, gint *, gint *); -- cgit v0.11.2-87-g4458