diff options
Diffstat (limited to 'src/gtkext/graph')
| -rw-r--r-- | src/gtkext/graph/cluster.c | 1498 | ||||
| -rw-r--r-- | src/gtkext/graph/cluster.h | 9 | ||||
| -rw-r--r-- | src/gtkext/graph/edge.h | 3 |
3 files changed, 1035 insertions, 475 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; + + +/* 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 *); -/* Indique le type défini par la GLib pour les mises en disposition graphique. */ -G_DEFINE_TYPE(GGraphCluster, g_graph_cluster, G_TYPE_OBJECT); + +/* ---------------------------------------------------------------------------------- */ +/* 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 : - * +* * +******************************************************************************/ - else - return 0; +static size_t get_graph_rank(const graph_rank_t *grank) +{ + size_t result; /* Rang à retourner */ - } + result = g_code_block_get_rank(grank->clusters[0]->block); - cluster->ranks = qinsert(cluster->ranks, &cluster->ranks_count, - sizeof(graph_rank), (__compar_fn_t)cmp_graph_rank, &new); + return result; - } +} - else - { - rank = &cluster->ranks[i]; - rank->count++; - rank->clusters = (GGraphCluster **)realloc(rank->clusters, - sizeof(GGraphCluster *) * rank->count); +/****************************************************************************** +* * +* 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->clusters[rank->count - 1] = sub; +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 */ - } + 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,152 +632,185 @@ 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; - void place_sub(GGraphCluster **iter, size_t loop, gint base, int dir) - { - size_t i; /* Boucle de parcours #2 */ - GtkAllocation needed; /* Taille requise */ + default: - assert(dir == -1 || dir == 1); + assert(grank->count >= 2); - for (i = 0; i < loop; i++, iter += dir) - { - g_graph_cluster_dispatch_x(*iter); + g_graph_cluster_compute_needed_alloc(grank->clusters[0], &needed); - g_graph_cluster_compute_needed_alloc(*iter, &needed); + if (needed.x < alloc->x) + { + alloc->width += (alloc->x - needed.x); + alloc->x = needed.x; + } - if (dir > 0) - g_graph_cluster_offset_x(*iter, base - needed.x); - else - g_graph_cluster_offset_x(*iter, base - needed.x - needed.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; + } - base += dir * (needed.width + HORIZONTAL_MARGIN); + 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; - 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 (rank->level < 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; +/****************************************************************************** +* * +* 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 : - * +* * +******************************************************************************/ - start -= HORIZONTAL_MARGIN / 2; +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 */ - place_sub(rank->clusters, j, start, -1); + assert(dir == -1 || dir == 1); - /* Répartition à droite du lien */ + for (i = 0; i < loop; i++, iter += dir) + { + g_graph_cluster_dispatch_x(*iter); - for (j = 0; j < rank->count; j++) - if (*rank->clusters[j]->parent_index > cluster->straight_index) - break; + g_graph_cluster_compute_needed_alloc(*iter, &needed); - start += HORIZONTAL_MARGIN; + if (dir > 0) + g_graph_cluster_offset_x(*iter, base - needed.x); + else + g_graph_cluster_offset_x(*iter, base - needed.x - needed.width); - place_sub(rank->clusters + j, rank->count - j, start, 1); + base += dir * (needed.width + HORIZONTAL_MARGIN); - } + } - } +} - /* Répartition homogène */ - else - { - rcount = rank->count; - if (rcount % 2 == 1) - { - if (rcount > 1) - { - mid = rcount / 2; +/****************************************************************************** +* * +* Paramètres : grank = ensemble de blocs de même rang à manipuler. * +* * +* Description : Organise la disposition d'un ensemble de blocs basiques. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ - start = rank->clusters[mid]->alloc.x - HORIZONTAL_MARGIN; +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 */ - place_sub(rank->clusters + mid - 1, mid, start, -1); + if (grank->count % 2 == 1) + { + if (grank->count > 1) + { + mid = grank->count / 2; - start *= -1; + start = grank->clusters[mid]->alloc.x - HORIZONTAL_MARGIN; - place_sub(rank->clusters + mid + 1, mid, start, 1); + _place_graph_rank_clusters(grank->clusters + mid - 1, mid, start, -1); - } + start *= -1; - else - g_graph_cluster_dispatch_x(rank->clusters[0]); + _place_graph_rank_clusters(grank->clusters + mid + 1, mid, start, 1); - } + } - else - { - mid = rcount / 2 - 1; + else + g_graph_cluster_dispatch_x(grank->clusters[0]); - start = - HORIZONTAL_MARGIN / 2; + } - place_sub(rank->clusters + mid, mid + 1, start, -1); + else + { + mid = grank->count / 2 - 1; - start *= -1; + start = - HORIZONTAL_MARGIN / 2; - place_sub(rank->clusters + mid + 1, mid + 1, start, 1); + _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); } @@ -578,33 +819,38 @@ static void g_graph_cluster_dispatch_x(GGraphCluster *cluster) /****************************************************************************** * * -* Paramètres : cluster = graphique de blocs à actualiser. * -* x = position finale sur l'axe des abscisses. * +* Paramètres : grank = ensemble de blocs de même rang à actualiser. * +* offset = décalage à appliquer. * * * -* Description : Détermine une position pour un ensemble de blocs basiques. * +* Description : Décalle vers la droite un ensemble de blocs basiques. * * * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ -/* -static void g_graph_cluster_set_x(GGraphCluster *cluster, gint x) + +static void offset_x_graph_rank(const graph_rank_t *grank, gint offset) { - g_graph_cluster_offset_x(cluster, -cluster->alloc.x); + size_t i; /* Boucle de parcours */ - g_graph_cluster_offset_x(cluster, x); + for (i = 0; i < grank->count; i++) + g_graph_cluster_offset_x(grank->clusters[i], offset); } -*/ + + + +/* ---------------------------------------------------------------------------------- */ +/* ENCADREMENTS D'ESPACES VERTICAUX */ +/* ---------------------------------------------------------------------------------- */ /****************************************************************************** * * -* Paramètres : cluster = graphique de blocs à actualiser. * -* offset = décalage à appliquer. * +* Paramètres : manager = structure à initialiser. * * * -* Description : Décalle vers la droite un ensemble de blocs basiques. * +* Description : Initialise les réservations liens verticaux. * * * * Retour : - * * * @@ -612,26 +858,25 @@ static void g_graph_cluster_set_x(GGraphCluster *cluster, gint x) * * ******************************************************************************/ -static void g_graph_cluster_offset_x(GGraphCluster *cluster, gint offset) +static void init_vspace_manager(vspace_manager_t *manager) { - size_t i; /* Boucle de parcours #1 */ - size_t j; /* Boucle de parcours #2 */ + manager->pending = NULL; + manager->pending_count = 0; - cluster->alloc.x += offset; + manager->left = NULL; + manager->left_count = 0; - 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); + manager->right = NULL; + manager->right_count = 0; } /****************************************************************************** * * -* Paramètres : cluster = graphique de blocs à actualiser. * -* base = position ordonnée à appliquer. * +* Paramètres : manager = structure à vider. * * * -* Description : Décalle vers le bas un ensemble de blocs basiques. * +* Description : Termine les réservations liens verticaux. * * * * Retour : - * * * @@ -639,72 +884,59 @@ static void g_graph_cluster_offset_x(GGraphCluster *cluster, gint offset) * * ******************************************************************************/ -static void g_graph_cluster_set_y(GGraphCluster *cluster, gint base) +static void exit_vspace_manager(vspace_manager_t *manager) { - size_t i; /* Boucle de parcours #1 */ - const graph_rank *rank; /* Accès simplifié à la rangée */ - gint max; /* Hauteur maximale rencontrée */ - size_t j; /* Boucle de parcours #2 */ - GGraphCluster *sub; /* Sous-ensemble traité */ - GtkAllocation alloc; /* Allocation courante */ - - 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; + if (manager->pending != NULL) + free(manager->pending); - base += VERTICAL_MARGIN; + if (manager->left != NULL) + free(manager->left); - /** - * Comme les liens purement verticaux n'entrainent pas de réservation, - * il n'y a potentiellement pas toujours d'espace à ajouter. - */ + if (manager->right != NULL) + free(manager->right); - if (max > 0) - base += ((max - 1) * LINK_MARGIN); +} - /* On ajoute l'espace requis pour l'affichage des blocs */ - base += VERTICAL_MARGIN; - max = 0; +/* ---------------------------------------------------------------------------------- */ +/* DEFINITION D'UN CHEF DE FILE */ +/* ---------------------------------------------------------------------------------- */ - for (j = 0; j < rank->count; j++) - { - sub = rank->clusters[j]; - g_graph_cluster_set_y(sub, base); +/* Indique le type défini par la GLib pour les mises en disposition graphique. */ +G_DEFINE_TYPE(GGraphCluster, g_graph_cluster, G_TYPE_OBJECT); - g_graph_cluster_compute_needed_alloc(sub, &alloc); - if ((alloc.y + alloc.height) > max) - max = alloc.y + alloc.height; +/****************************************************************************** +* * +* 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 */ - base = max; + object = G_OBJECT_CLASS(klass); - } + object->dispose = (GObjectFinalizeFunc/* ! */)g_graph_cluster_dispose; + object->finalize = (GObjectFinalizeFunc)g_graph_cluster_finalize; } /****************************************************************************** * * -* Paramètres : cluster = encapsulation à consulter. * -* alloc = emplacement idéal pour l'affichage. * +* Paramètres : cluster = instance à initialiser. * * * -* Description : Détermine l'emplacement requis d'un ensemble de blocs. * +* Description : Initialise une mise en disposition de blocs en graphique. * * * * Retour : - * * * @@ -712,196 +944,168 @@ static void g_graph_cluster_set_y(GGraphCluster *cluster, gint base) * * ******************************************************************************/ -void g_graph_cluster_compute_needed_alloc(const GGraphCluster *cluster, GtkAllocation *alloc) +static void g_graph_cluster_init(GGraphCluster *cluster) { - 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; - } + init_vspace_manager(&cluster->vspaces); - 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); - - 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; - } - - /* 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; - } - break; +/****************************************************************************** +* * +* 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 = encapsulation à consulter. * +* Paramètres : cluster = instance d'objet GLib à traiter. * * * -* Description : Fournit le composant graphique principal du groupe. * +* Description : Procède à la libération totale de la mémoire. * * * -* Retour : Composant graphique principal utilisé. * +* Retour : - * * * * Remarques : - * * * ******************************************************************************/ -GtkWidget *g_graph_cluster_get_widget(GGraphCluster *cluster) +static void g_graph_cluster_finalize(GGraphCluster *cluster) { - GtkWidget *result; + size_t i; /* Boucle de parcours */ - result = cluster->display; + for (i = 0; i < cluster->ta_count; i++) + delete_incoming_link(cluster->top_anchors[i]); - g_object_ref(G_OBJECT(result)); + if (cluster->top_anchors != NULL) + free(cluster->top_anchors); - return result; + 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 : cluster = encapsulation à traiter. * -* display = support de destination finale. * +* Paramètres : block = premier bloc du groupe. * +* highlighted = gestionnaire de surbrillance pour segments. * +* binary = binaire charger dont le code est à représenter.* * * -* Description : Dispose chaque noeud sur la surface de destination donnée. * +* Description : * * * -* Retour : - * +* Retour : Adresse de la structure mise en place. * * * * Remarques : - * * * ******************************************************************************/ -void g_graph_cluster_place(GGraphCluster *cluster, GtkGraphDisplay *display) +GGraphCluster *g_graph_cluster_new(GCodeBlock *block, segcnt_list *highlighted, GLoadedBinary *binary) { - size_t i; /* Boucle de parcours #1 */ - size_t j; /* Boucle de parcours #2 */ - - g_object_ref(G_OBJECT(cluster->display)); - gtk_graph_display_put(display, cluster->display, &cluster->alloc); - - for (i = 0; i < cluster->ta_count; i++) - { - g_object_ref(G_OBJECT(cluster->top_anchors[i]->edge)); - gtk_graph_display_add_edge(display, cluster->top_anchors[i]->edge); - } + GGraphCluster *result; /* Structure à retourner */ + GBufferView *view; /* Partie affichée du tampon */ + GtkRequisition requisition; /* Taille à l'écran actuelle */ - for (i = 0; i < cluster->ranks_count; i++) - for (j = 0; j < cluster->ranks[i].count; j++) - g_graph_cluster_place(cluster->ranks[i].clusters[j], display); + 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 à consulter ou remonter. * -* first = première instruction du bloc basique recherché. * +* Paramètres : cluster = graphique de blocs à compléter. * +* sub = sous-ensemble à intégrer. * * * -* Description : Recherche le bloc basique à l'extrémité d'un lien. * +* Description : Complète un graphique avec un sous-ensemble de blocs. * * * -* Retour : Bloc graphique de destination pour un lien ou NULL si échec. * +* Retour : - * * * * Remarques : - * * * ******************************************************************************/ -#if 0 -static GGraphCluster *g_graph_cluster_find_lower_dest_cluster(const GGraphCluster *cluster, const GArchInstruction *first) + +static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub) { - GGraphCluster *result; /* Trouvaille à retourner */ - size_t i; /* Boucle de parcours #1 */ - const graph_rank *rank; /* Confort d'accès */ - size_t j; /* Boucle de parcours #2 */ - GArchInstruction *instr; /* Instruction à comparer */ + size_t level; /* Niveau du nouvel ensemble */ + size_t i; /* Boucle de parcours */ + graph_rank_t new; /* Nouvel étage à insérer */ - result = NULL; + level = g_code_block_get_rank(sub->block); - for (i = 0; i < cluster->ranks_count && result == NULL; i++) - { - rank = &cluster->ranks[i]; - - for (j = 0; j < rank->count && result == NULL; j++) - { - g_basic_block_get_boundaries(rank->clusters[j]->block, &instr, NULL); + for (i = 0; i < cluster->ranks_count; i++) + if (get_graph_rank(&cluster->ranks[i]) == level) + break; - if (instr == first) - result = rank->clusters[j]; + 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); } - return result; + else + extend_graph_rank(&cluster->ranks[i], sub); } -#endif + /****************************************************************************** * * @@ -923,11 +1127,11 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all 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 */ + 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_edge *incoming; /* Définitions d'arrivée */ + incoming_link_t *incoming; /* Définitions d'arrivée */ /* Au niveau du bloc courant */ @@ -953,10 +1157,11 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all /* Point de départ */ - leaving = (leaving_edge *)calloc(1, sizeof(leaving_edge)); + 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 = (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 ? */ @@ -970,7 +1175,7 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all 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; + target_level = get_graph_rank(&cluster->ranks[j]); if (target_level > (level + 1) && target_level > cluster->straight_level) { @@ -988,29 +1193,93 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all /* Point d'arrivée */ - incoming = (incoming_edge *)calloc(1, sizeof(incoming_edge)); + 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 = (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); + /* FIXME : trop de boucles ! */ - else if (incoming->type == ILT_JUMP_IF_FALSE) - incoming->edge = g_graph_edge_new_false(&leaving->start, &incoming->y, &incoming->end); + target_level = -1; - else - incoming->edge = g_graph_edge_new(&leaving->start, &incoming->y, &incoming->end); + 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: + + + + + + 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 */ - incoming->origin = cluster; - incoming->leaving_index = &leaving->index; + incoming->edge = g_graph_edge_new_loop(&leaving->start, &leaving->start, + &incoming->y, &incoming->end); /* FIXME : trop de boucles ! */ @@ -1028,10 +1297,11 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all - break; - case ILT_LOOP: + + + /* TODO */ //assert(false); @@ -1057,7 +1327,7 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all if (cluster->has_straight) { size_t center; - leaving_edge *tmp; + leaving_link_t *tmp; if (cluster->ba_count % 2 == 0) center = cluster->ba_count / 2 - 1; @@ -1070,7 +1340,7 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all memmove(cluster->bottom_anchors + cluster->straight_index, cluster->bottom_anchors + cluster->straight_index + 1, - (center - cluster->straight_index) * sizeof(leaving_edge *)); + (center - cluster->straight_index) * sizeof(leaving_link_t *)); cluster->bottom_anchors[center] = tmp; @@ -1087,7 +1357,7 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all memmove(cluster->bottom_anchors + center + 1, cluster->bottom_anchors + center, - (cluster->straight_index - center) * sizeof(leaving_edge *)); + (cluster->straight_index - center) * sizeof(leaving_link_t *)); cluster->bottom_anchors[center] = tmp; @@ -1111,6 +1381,323 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all /****************************************************************************** * * +* Paramètres : cluster = graphique de blocs à manipuler. * +* * +* Description : Organise la disposition d'un ensemble de blocs basiques. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_dispatch_x(GGraphCluster *cluster) +{ + 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; + + 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); + + } + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à actualiser. * +* offset = décalage à appliquer. * +* * +* Description : Décalle vers la droite un ensemble de blocs basiques. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_graph_cluster_offset_x(GGraphCluster *cluster, gint offset) +{ + size_t i; /* Boucle de parcours */ + + cluster->alloc.x += offset; + + for (i = 0; i < cluster->ranks_count; i++) + offset_x_graph_rank(&cluster->ranks[i], offset); + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à actualiser. * +* base = position ordonnée à appliquer. * +* * +* Description : Décalle vers le bas un ensemble de blocs basiques. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +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 */ + + 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; + + } + +} + + +/****************************************************************************** +* * +* 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) +{ + 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); + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = encapsulation à consulter. * +* * +* Description : Fournit le composant graphique principal du groupe. * +* * +* Retour : Composant graphique principal utilisé. * +* * +* Remarques : - * +* * +******************************************************************************/ + +GtkWidget *g_graph_cluster_get_widget(GGraphCluster *cluster) +{ + GtkWidget *result; + + result = cluster->display; + + g_object_ref(G_OBJECT(result)); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = encapsulation à traiter. * +* display = support de destination finale. * +* * +* Description : Dispose chaque noeud sur la surface de destination donnée. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void g_graph_cluster_place(GGraphCluster *cluster, GtkGraphDisplay *display) +{ + size_t i; /* Boucle de parcours #1 */ + size_t j; /* Boucle de parcours #2 */ + + g_object_ref(G_OBJECT(cluster->display)); + gtk_graph_display_put(display, cluster->display, &cluster->alloc); + + for (i = 0; i < cluster->ta_count; i++) + { + g_object_ref(G_OBJECT(cluster->top_anchors[i]->edge)); + gtk_graph_display_add_edge(display, cluster->top_anchors[i]->edge); + } + + for (i = 0; i < cluster->ranks_count; i++) + for (j = 0; j < cluster->ranks[i].count; j++) + g_graph_cluster_place(cluster->ranks[i].clusters[j], display); + +} + + + + + + + + +////////////////////////////////////////////////////////// + + + + + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à consulter ou remonter. * +* first = première instruction du bloc basique recherché. * +* * +* Description : Recherche le bloc basique à l'extrémité d'un lien. * +* * +* Retour : Bloc graphique de destination pour un lien ou NULL si échec. * +* * +* Remarques : - * +* * +******************************************************************************/ +#if 0 +static GGraphCluster *g_graph_cluster_find_lower_dest_cluster(const GGraphCluster *cluster, const GArchInstruction *first) +{ + GGraphCluster *result; /* Trouvaille à retourner */ + size_t i; /* Boucle de parcours #1 */ + const graph_rank_t *rank; /* Confort d'accès */ + size_t j; /* Boucle de parcours #2 */ + GArchInstruction *instr; /* Instruction à comparer */ + + result = NULL; + + for (i = 0; i < cluster->ranks_count && result == NULL; i++) + { + rank = &cluster->ranks[i]; + + for (j = 0; j < rank->count && result == NULL; j++) + { + g_basic_block_get_boundaries(rank->clusters[j]->block, &instr, NULL); + + if (instr == first) + result = rank->clusters[j]; + + } + + } + + return result; + +} +#endif + + + +/****************************************************************************** +* * * Paramètres : cluster = graphique de blocs à consulter. * * index = indice du lien à considérer. * * * @@ -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 *); |