From 3cf2601f5d652037b79ca0cdaee051e4d9679c74 Mon Sep 17 00:00:00 2001
From: Cyrille Bagard <nocbos@gmail.com>
Date: Fri, 21 Oct 2016 01:39:14 +0200
Subject: Extended the number of cases where beautiful graphs are produced.
---
ChangeLog | 7 +
src/gtkext/graph/cluster.c | 714 +++++++++++++++++++++++++++++++++++++--------
src/gtkext/graph/edge.c | 21 ++
src/gtkext/graph/edge.h | 3 +
4 files changed, 631 insertions(+), 114 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index 1f6cfbf..62a1bc6 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,10 @@
+16-10-21 Cyrille Bagard <nocbos@gmail.com>
+
+ * src/gtkext/graph/cluster.c:
+ * src/gtkext/graph/edge.c:
+ * src/gtkext/graph/edge.h:
+ Extend the number of cases where beautiful graphs are produced.
+
16-10-18 Cyrille Bagard <nocbos@gmail.com>
* src/gtkext/gtkgraphview.c:
diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c
index 4c92718..3e18f5f 100644
--- a/src/gtkext/graph/cluster.c
+++ b/src/gtkext/graph/cluster.c
@@ -26,6 +26,7 @@
#include <assert.h>
#include <malloc.h>
+#include <stdlib.h>
#include <string.h>
@@ -37,23 +38,49 @@
/* Définition du tracé d'un lien */
-typedef struct _link_def
+typedef struct _incoming_edge
{
InstructionLinkType type; /* Complexité du tracé */
+ const size_t *hslot; /* Couche horizontale réservée */
GdkPoint y; /* Position des décrochages */
-
GdkPoint end; /* Point d'arrivée final */
GGraphEdge *edge; /* Lien complet en préparation */
-} link_def;
+ GGraphCluster *origin; /* Bloc de départ du lien */
+ const size_t *leaving_index; /* Indice du point de départ */
+
+} incoming_edge;
+
+
+/* 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 */
+
+} leaving_edge;
+
+/* Réservation pour les lignes horizontales */
+typedef struct _hspace_booking
+{
+ gint start; /* Abscisse de départ de ligne */
+ size_t index; /* Indice de rangée verticale */
+
+} hspace_booking;
/* Découpage vertical */
typedef struct _graph_rank
{
unsigned int level; /* Niveau des blocs */
+ hspace_booking **right2left; /* Réservations de D -> G */
+ size_t r2l_count; /* Quantité de ces réservations*/
+
+ hspace_booking **left2right; /* Réservations de G -> D */
+ size_t l2r_count; /* Quantité de ces réservations*/
+
GGraphCluster **clusters; /* Ensembles de blocs */
size_t count; /* Nombre de ces ensembles */
@@ -64,6 +91,7 @@ struct _GGraphCluster
{
GObject parent; /* A laisser en premier */
+ size_t *parent_index; /* Indice du lien au départ */
////////////////////////////////////////
gint top_margin[2]; /* Espaces gauches et droites */
@@ -72,16 +100,20 @@ struct _GGraphCluster
////////////////////////////////////////
- link_def **top_anchors; /* Accroches supérieures */
+ incoming_edge **top_anchors; /* Accroches supérieures */
size_t ta_count; /* Quantité de ces accroches */
GBasicBlock *block; /* Bloc d'origine représenté */
GtkWidget *view; /* Vue graphique associée */
GtkAllocation alloc; /* Emplacement final du bloc */
- GdkPoint **bottom_anchors; /* Accroches inférieures */
+ leaving_edge **bottom_anchors; /* Accroches inférieures */
size_t ba_count; /* Quantité de ces accroches */
+ bool has_straight; /* Présence d'une ligne droite */
+ unsigned int straight_level; /* Rang atteint en ligne droite*/
+ size_t straight_index; /* Indice du lien vertical */
+
graph_rank *ranks; /* Répartition verticale */
size_t ranks_count; /* Nombre de divisions */
@@ -99,7 +131,7 @@ struct _GGraphClusterClass
#define HORIZONTAL_MARGIN 20
/* Espace minimal vertical entre les blocs */
-#define VERTICAL_MARGIN 30
+#define VERTICAL_MARGIN 15
/* Espace minimal entre les liens */
#define LINK_MARGIN 10
@@ -142,8 +174,17 @@ static void g_graph_cluster_set_y(GGraphCluster *, gint);
/* Met en place les embryons de liens nécessaires. */
static void g_graph_cluster_define_links(GGraphCluster *, GHashTable *);
-/* Détermine les positions de tous les liens en place. */
-static void g_graph_cluster_compute_link_positions(GGraphCluster *);
+/* 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);
+
+/* Détermine les abscisses de tous les liens en place. */
+static void g_graph_cluster_compute_link_x_positions(GGraphCluster *);
+
+/* Réserve de l'espace vertical pour les lignes horizontales. */
+static void g_graph_cluster_book_hspace_for_links(GGraphCluster *);
+
+/* Détermine les ordonnées de tous les liens en place. */
+static void g_graph_cluster_compute_link_y_positions(GGraphCluster *);
/* Applique les positions calculées pour chaque lien graphique. */
static void g_graph_cluster_resolve_links(const GGraphCluster *);
@@ -324,7 +365,7 @@ static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub,
unsigned int 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 */
+ graph_rank *rank; /* Nouvel étage à compléter */
level = g_basic_block_get_rank(block);
@@ -336,6 +377,12 @@ static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub,
{
new.level = level;
+ new.right2left = NULL;
+ new.r2l_count = 0;
+
+ new.left2right = NULL;
+ new.l2r_count = 0;
+
new.clusters = (GGraphCluster **)calloc(1, sizeof(GGraphCluster *));
new.count = 1;
@@ -389,9 +436,47 @@ static void g_graph_cluster_add_sub(GGraphCluster *cluster, GGraphCluster *sub,
static void g_graph_cluster_dispatch_x(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 */
- 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 !
+ */
+
+ 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);
+
+ if (pos_a < pos_b)
+ result = -1;
+
+ else if (pos_a > pos_b)
+ result = 1;
+
+ else
+ result = 0;
+
+ return result;
+
+ }
+
+ qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_edge *), (__compar_fn_t)compare_incoming_edges);
+
+ /**
+ * Il est désormais temps de placer tous les blocs de code inférieurs.
+ */
void place_sub(GGraphCluster **iter, size_t loop, gint base, int dir)
{
@@ -418,41 +503,80 @@ static void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
}
-
-
for (k = 0; k < cluster->ranks_count; k++)
{
- rcount = cluster->ranks[k].count;
+ rank = &cluster->ranks[k];
- if (rcount % 2 == 1)
+ /* Répartition autour d'une ligne verticale */
+ if (cluster->has_straight)
{
- if (rcount > 1)
+ start = g_graph_cluster_compute_leaving_link_position(cluster, cluster->straight_index);
+
+ if (rank->level < cluster->straight_level)
{
- mid = rcount / 2;
+ /* Répartition à gauche du lien */
- start = cluster->ranks[k].clusters[mid]->alloc.x - HORIZONTAL_MARGIN;
+ for (j = rank->count; j > 0; j--)
+ if (*rank->clusters[j - 1]->parent_index < cluster->straight_index)
+ break;
- place_sub(cluster->ranks[k].clusters + mid - 1, mid, start, -1);
+ start -= HORIZONTAL_MARGIN / 2;
- start *= -1;
+ place_sub(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;
- place_sub(cluster->ranks[k].clusters + mid + 1, mid, start, 1);
+ start += HORIZONTAL_MARGIN;
+
+ place_sub(rank->clusters + j, rank->count - j, start, 1);
}
}
+ /* Répartition homogène */
else
{
- mid = rcount / 2 - 1;
+ rcount = rank->count;
+
+ if (rcount % 2 == 1)
+ {
+ if (rcount > 1)
+ {
+ mid = rcount / 2;
+
+ start = rank->clusters[mid]->alloc.x - HORIZONTAL_MARGIN;
+
+ place_sub(rank->clusters + mid - 1, mid, start, -1);
+
+ start *= -1;
+
+ place_sub(rank->clusters + mid + 1, mid, start, 1);
+
+ }
- start = - HORIZONTAL_MARGIN / 2;
+ else
+ g_graph_cluster_dispatch_x(rank->clusters[0]);
+
+ }
+
+ else
+ {
+ mid = rcount / 2 - 1;
+
+ start = - HORIZONTAL_MARGIN / 2;
- place_sub(cluster->ranks[k].clusters + mid, mid + 1, start, -1);
+ place_sub(rank->clusters + mid, mid + 1, start, -1);
- start *= -1;
+ start *= -1;
- place_sub(cluster->ranks[k].clusters + mid + 1, mid + 1, start, 1);
+ place_sub(rank->clusters + mid + 1, mid + 1, start, 1);
+
+ }
}
@@ -527,6 +651,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 */
gint max; /* Hauteur maximale rencontrée */
size_t j; /* Boucle de parcours #2 */
GGraphCluster *sub; /* Sous-ensemble traité */
@@ -538,13 +663,34 @@ static void g_graph_cluster_set_y(GGraphCluster *cluster, gint base)
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 < cluster->ranks[i].count; j++)
+ for (j = 0; j < rank->count; j++)
{
- sub = cluster->ranks[i].clusters[j];
+ sub = rank->clusters[j];
g_graph_cluster_set_y(sub, base);
@@ -756,18 +902,23 @@ static GGraphCluster *g_graph_cluster_find_lower_dest_cluster(const GGraphCluste
static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all)
{
+ unsigned int level; /* Niveau du nouvel ensemble */
GArchInstruction *last; /* Dernière instruction du bloc*/
GArchInstruction **dests; /* Instr. visée par une autre */
InstructionLinkType *types; /* Type de lien entre lignes */
size_t dcount; /* Nombre de liens de dest. */
size_t i; /* Boucle de parcours #1 */
GGraphCluster *target; /* Bloc ciblé par un lien */
- GdkPoint *start; /* Point de départ d'un lien */
- link_def *end; /* Définitions d'arrivée */
+ leaving_edge *leaving; /* Point de départ d'un lien */
+ unsigned int 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_basic_block_get_rank(cluster->block);
+
g_basic_block_get_boundary(cluster->block, NULL, &last);
g_arch_instruction_rlock_dest(last);
@@ -787,32 +938,80 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all
/* Point de départ */
- start = (GdkPoint *)calloc(1, sizeof(GdkPoint));
+ 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;
+ }
+
+ }
+
+
+
+
- cluster->bottom_anchors = (GdkPoint **)realloc(cluster->bottom_anchors,
- ++cluster->ba_count * sizeof(GdkPoint *));
- cluster->bottom_anchors[cluster->ba_count - 1] = start;
/* Point d'arrivée */
- end = (link_def *)calloc(1, sizeof(link_def));
+ incoming = (incoming_edge *)calloc(1, sizeof(incoming_edge));
- target->top_anchors = (link_def **)realloc(target->top_anchors,
- ++target->ta_count * sizeof(link_def *));
- target->top_anchors[target->ta_count - 1] = end;
+ 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 */
- end->type = types[i];
+ leaving->index = cluster->ba_count - 1;
+
+ incoming->type = types[i];
if (types[i] == ILT_JUMP_IF_TRUE)
- end->edge = g_graph_edge_new_true(start, &end->y, &end->end);
+ incoming->edge = g_graph_edge_new_true(&leaving->start, &incoming->y, &incoming->end);
else if (types[i] == ILT_JUMP_IF_FALSE)
- end->edge = g_graph_edge_new_false(start, &end->y, &end->end);
+ incoming->edge = g_graph_edge_new_false(&leaving->start, &incoming->y, &incoming->end);
else
- end->edge = g_graph_edge_new(start, &end->y, &end->end);
+ 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;
@@ -820,7 +1019,7 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all
case ILT_LOOP:
/* TODO */
- assert(false);
+ //assert(false);
break;
@@ -831,6 +1030,57 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all
g_arch_instruction_runlock_dest(last);
+
+
+
+ /* 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++)
@@ -842,60 +1092,113 @@ static void g_graph_cluster_define_links(GGraphCluster *cluster, GHashTable *all
/******************************************************************************
* *
-* Paramètres : cluster = graphique de blocs à actualiser. *
+* Paramètres : cluster = graphique de blocs à consulter. *
+* index = indice du lien à considérer. *
* *
-* Description : Détermine les positions de tous les liens en place. *
+* 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_compute_link_positions(GGraphCluster *cluster)
+static gint g_graph_cluster_compute_leaving_link_position(const GGraphCluster *cluster, size_t index)
{
+ gint result; /* Position à retourner */
gint mid_x; /* Abscisse centrale */
size_t half; /* Indice de répartition égale */
- gint y; /* Ordonnée d'application */
+ assert(index < cluster->ba_count);
+
+ mid_x = cluster->alloc.x + (cluster->alloc.width / 2);
+
+ half = cluster->ba_count / 2;
+
+ if (cluster->ba_count % 2 == 1)
+ {
+ if (index < half)
+ result = mid_x - (half - index) * LINK_MARGIN;
+
+ else if (index == half)
+ result = mid_x;
+
+ else
+ result = mid_x + (index - half) * LINK_MARGIN;
+
+ }
+
+ else
+ {
+ if (index < half)
+ result = mid_x - LINK_MARGIN / 2 - (half - index - 1) * LINK_MARGIN;
+
+ else
+ result = mid_x + LINK_MARGIN / 2 + (index - half) * LINK_MARGIN;
+
+ }
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : cluster = graphique de blocs à actualiser. *
+* *
+* Description : Détermine les abscisses de tous les liens en place. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_graph_cluster_compute_link_x_positions(GGraphCluster *cluster)
+{
+ gint mid_x; /* Abscisse centrale */
size_t i; /* Boucle de parcours #1 */
+ size_t half; /* Indice de répartition égale */
GdkPoint *pt; /* Point à actualiser */
size_t j; /* Boucle de parcours #2 */
-
-
mid_x = cluster->alloc.x + (cluster->alloc.width / 2);
/* Du côté des départs... */
if (cluster->ba_count > 0)
- {
- half = cluster->ba_count / 2;
+ for (i = 0; i < cluster->ba_count; i++)
+ {
+ pt = &cluster->bottom_anchors[i]->start;
- y = cluster->alloc.y + cluster->alloc.height;
+ pt->x = g_graph_cluster_compute_leaving_link_position(cluster, i);
+
+ }
+
+ /* Du côté des arrivées... */
+
+ if (cluster->ta_count > 0)
+ {
+ half = cluster->ta_count / 2;
- if (cluster->ba_count % 2 == 1)
+ if (cluster->ta_count % 2 == 1)
{
for (i = half; i > 0; i--)
{
- pt = cluster->bottom_anchors[i - 1];
+ pt = &cluster->top_anchors[i - 1]->end;
pt->x = mid_x - (half - i + 1) * LINK_MARGIN;
- pt->y = y;
}
- pt = cluster->bottom_anchors[half];
-
- pt->x = mid_x;
- pt->y = y;
+ cluster->top_anchors[half]->end.x = mid_x;
- for (i = half + 1; i < cluster->ba_count; i++)
+ for (i = half + 1; i < cluster->ta_count; i++)
{
- pt = cluster->bottom_anchors[i];
+ pt = &cluster->top_anchors[i]->end;
pt->x = mid_x + (i - half) * LINK_MARGIN;
- pt->y = y;
}
@@ -905,19 +1208,17 @@ static void g_graph_cluster_compute_link_positions(GGraphCluster *cluster)
{
for (i = half; i > 0; i--)
{
- pt = cluster->bottom_anchors[i - 1];
+ pt = &cluster->top_anchors[i - 1]->end;
pt->x = mid_x - LINK_MARGIN / 2 - (half - i) * LINK_MARGIN;
- pt->y = y;
}
- for (i = half; i < cluster->ba_count; i++)
+ for (i = half; i < cluster->ta_count; i++)
{
- pt = cluster->bottom_anchors[i];
+ pt = &cluster->top_anchors[i]->end;
pt->x = mid_x + LINK_MARGIN / 2 + (half - i) * LINK_MARGIN;
- pt->y = y;
}
@@ -925,78 +1226,191 @@ static void g_graph_cluster_compute_link_positions(GGraphCluster *cluster)
}
- /* Du côté des arrivées... */
+ /* Propagation des déterminations */
- if (cluster->ta_count > 0)
+ for (i = 0; i < cluster->ranks_count; i++)
+ for (j = 0; j < cluster->ranks[i].count; j++)
+ g_graph_cluster_compute_link_x_positions(cluster->ranks[i].clusters[j]);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : cluster = graphique de blocs à traiter. *
+* *
+* Description : Réserve de l'espace vertical pour les lignes horizontales. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void g_graph_cluster_book_hspace_for_links(GGraphCluster *cluster)
+{
+ size_t i; /* Boucle de parcours #1 */
+ graph_rank *rank; /* Rangée à manipuler */
+ size_t j; /* Boucle de parcours #2 */
+ GGraphCluster *sub; /* Bloc inférieur à manipuler */
+ size_t k; /* Boucle de parcours #3 */
+ gint x1; /* Abscisse de départ de lien */
+ gint x2; /* Abscisse d'arrivée de lien */
+ hspace_booking *new; /* Nouvelle réservation */
+
+ for (i = 0; i < cluster->ranks_count; i++)
{
- half = cluster->ta_count / 2;
+ rank = &cluster->ranks[i];
- y = cluster->alloc.y;
+ /* Enregistrement des besoins */
- if (cluster->ta_count % 2 == 1)
+ for (j = 0; j < rank->count; j++)
{
- for (i = half; i > 0; i--)
+ sub = rank->clusters[j];
+
+ for (k = 0; k < sub->ta_count; k++)
{
- pt = &cluster->top_anchors[i - 1]->end;
+ g_graph_edge_get_x_borders(sub->top_anchors[k]->edge, &x1, &x2);
- pt->x = mid_x - (half - i + 1) * LINK_MARGIN;
- pt->y = y;
+ if (x1 > x2)
+ {
+ new = (hspace_booking *)calloc(1, sizeof(hspace_booking));
- }
+ new->start = x1;
+ sub->top_anchors[k]->hslot = &new->index;
- pt = &cluster->top_anchors[half]->end;
+ int compare_right_to_left(const hspace_booking **a, const hspace_booking **b)
+ {
+ int result; /* Bilan à retourner */
- pt->x = mid_x;
- pt->y = y;
+ if ((*a)->start > (*b)->start)
+ result = -1;
- for (i = half + 1; i < cluster->ta_count; i++)
- {
- pt = &cluster->top_anchors[i]->end;
+ else if ((*a)->start < (*b)->start)
+ result = 1;
- pt->x = mid_x + (i - half) * LINK_MARGIN;
- pt->y = y;
+ else
+ {
+ assert(false);
+ result = 0;
+ }
- }
+ return result;
- }
+ }
- else
- {
- for (i = half; i > 0; i--)
- {
- pt = &cluster->top_anchors[i - 1]->end;
+ rank->right2left = qinsert(rank->right2left, &rank->r2l_count,
+ sizeof(hspace_booking *),
+ (__compar_fn_t)compare_right_to_left, &new);
- pt->x = mid_x - LINK_MARGIN / 2 - (half - i) * LINK_MARGIN;
- pt->y = y;
+ }
- }
+ else if (x1 < x2)
+ {
+ new = (hspace_booking *)calloc(1, sizeof(hspace_booking));
- for (i = half; i < cluster->ta_count; i++)
- {
- pt = &cluster->top_anchors[i]->end;
+ new->start = x1;
+ sub->top_anchors[k]->hslot = &new->index;
- pt->x = mid_x + LINK_MARGIN / 2 + (half - i) * LINK_MARGIN;
- pt->y = y;
+ int compare_left_to_right(const hspace_booking **a, const hspace_booking **b)
+ {
+ int result; /* Bilan à retourner */
+
+ if ((*a)->start < (*b)->start)
+ result = -1;
+
+ else if ((*a)->start > (*b)->start)
+ result = 1;
+
+ else
+ {
+ assert(false);
+ result = 0;
+ }
+
+ return result;
+
+ }
+
+ rank->left2right = qinsert(rank->left2right, &rank->l2r_count,
+ sizeof(hspace_booking *),
+ (__compar_fn_t)compare_left_to_right, &new);
+
+ }
+
+ else
+ sub->top_anchors[k]->hslot = NULL;
}
}
+ /* Définition des couches */
+ for (j = 0; j < rank->r2l_count; j++)
+ rank->right2left[j]->index = j;
+ for (j = 0; j < rank->l2r_count; j++)
+ rank->left2right[j]->index = j;
+ /* Propagation des déterminations */
+ for (j = 0; j < rank->count; j++)
+ g_graph_cluster_book_hspace_for_links(rank->clusters[j]);
+ }
+}
- for (i = 0; i < cluster->ta_count; i++)
- cluster->top_anchors[i]->y.y = cluster->top_anchors[i]->end.y - 18;
+/******************************************************************************
+* *
+* Paramètres : cluster = graphique de blocs à actualiser. *
+* *
+* Description : Détermine les ordonnées de tous les liens en place. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+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 */
+ size_t j; /* Boucle de parcours #2 */
+
+ /* Du côté des départs... */
+ if (cluster->ba_count > 0)
+ {
+ y = cluster->alloc.y + cluster->alloc.height;
+ for (i = 0; i < cluster->ba_count; i++)
+ cluster->bottom_anchors[i]->start.y = y;
+ }
+ /* Du côté des arrivées... */
+ if (cluster->ta_count > 0)
+ {
+ y = cluster->alloc.y;
+
+ for (i = 0; i < cluster->ta_count; i++)
+ {
+ incoming = cluster->top_anchors[i];
+
+ incoming->end.y = y;
+
+ incoming->y.y = incoming->end.y - VERTICAL_MARGIN;
+
+ if (incoming->hslot != NULL)
+ incoming->y.y -= *incoming->hslot * LINK_MARGIN;
+
+ }
}
@@ -1004,7 +1418,7 @@ static void g_graph_cluster_compute_link_positions(GGraphCluster *cluster)
for (i = 0; i < cluster->ranks_count; i++)
for (j = 0; j < cluster->ranks[i].count; j++)
- g_graph_cluster_compute_link_positions(cluster->ranks[i].clusters[j]);
+ g_graph_cluster_compute_link_y_positions(cluster->ranks[i].clusters[j]);
}
@@ -1124,8 +1538,6 @@ static GGraphCluster *setup_graph_clusters(GLoadedBinary *binary, const GBlockLi
g_arch_instruction_rlock_dest(last);
dcount = g_arch_instruction_get_destinations(last, &dests, &types, NULL);
- printf(" ... block=%p dest=%zu\n", block, dcount);
-
for (i = 0; i < dcount; i++)
switch (types[i])
{
@@ -1158,9 +1570,33 @@ static GGraphCluster *setup_graph_clusters(GLoadedBinary *binary, const GBlockLi
if (j == pending->count)
{
- assert((pending->count + 1) < g_block_list_count_blocks(list));
- pending->list[pending->count++] = target;
- printf(" --push-- %d -> %p\n", types[i], target);
+ /**
+ * Il faut vérifier ici si la destination n'a pas déjà été
+ * empruntée, sauf peine de faire réagir l'assertion plus
+ * haut au moment de l'insertion.
+ *
+ * Le type de code à problème est le suivant :
+ *
+ * ...
+ * if (...)
+ * ...
+ * ...
+ *
+ * Le code suivant le bloc conditionnel a deux origines,
+ * qui vont chacune poursuivre le traitement vers ce code
+ * commun.
+ *
+ * Et comme les origines ne sont pas dominantes, on utilise
+ * la table globale.
+ */
+
+ if (!g_hash_table_contains(all, dests[i]))
+ {
+ assert((pending->count + 1) < g_block_list_count_blocks(list));
+ pending->list[pending->count++] = target;
+ printf(" --push-- %d -> %p\n", types[i], target);
+ }
+
}
do
@@ -1266,12 +1702,15 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
-
+#if 0
do
{
size_t i;
GBasicBlock *block;
const bitfield_t *domination;
+ GArchInstruction *first; /* Première instruction du bloc*/
+ GArchInstruction *last; /* Dernière instruction du bloc*/
+
printf("DBG // count : %zu\n", count);
@@ -1280,8 +1719,12 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
block = g_block_list_get_block(list, i);
domination = g_basic_block_get_domination(block);
- printf("DBG // block [%zu] : 0x%08lx -- rank = %u\n",
- i, gfw(domination), g_basic_block_get_rank(block));
+ g_basic_block_get_boundary(block, &first, &last);
+
+ printf("DBG // block [%zu] @ 0x%08x : 0x%08lx -- rank = %u\n",
+ i,
+ (unsigned int)first->range.addr.virtual,
+ gfw(domination), g_basic_block_get_rank(block));
}
@@ -1292,6 +1735,39 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
+ void show_tree(GGraphCluster *cluster, int depth)
+ {
+ int i;
+ GArchInstruction *first;
+ size_t j;
+ size_t k;
+
+ printf("TREE | ");
+
+ for (i = 0; i < depth; i++)
+ printf(" ");
+
+ g_basic_block_get_boundary(cluster->block, &first, NULL);
+
+ printf("cluster @ 0x%08x\n", (unsigned int)first->range.addr.virtual);
+
+ for (j = 0; j < cluster->ranks_count; j++)
+ {
+ printf("TREE | ");
+
+ for (i = 0; i < depth; i++)
+ printf(" ");
+
+ printf(" + rank %u +\n", cluster->ranks[j].level);
+
+ for (k = 0; k < cluster->ranks[j].count; k++)
+ show_tree(cluster->ranks[j].clusters[k], depth + 1);
+
+ }
+
+
+ }
+#endif
result = setup_graph_clusters(binary, list, 0, highlighted, pending, all);
@@ -1300,12 +1776,16 @@ 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);
- g_graph_cluster_set_y(result, 0);
-
/* Réajustement vers la droite */
g_graph_cluster_compute_needed_alloc(result, &needed);
@@ -1314,7 +1794,13 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
/* Application finale sur les liens */
- g_graph_cluster_compute_link_positions(result);
+ g_graph_cluster_compute_link_x_positions(result);
+
+ g_graph_cluster_book_hspace_for_links(result);
+
+ g_graph_cluster_set_y(result, 0);
+
+ g_graph_cluster_compute_link_y_positions(result);
g_graph_cluster_resolve_links(result);
diff --git a/src/gtkext/graph/edge.c b/src/gtkext/graph/edge.c
index a917cc3..ab3a666 100644
--- a/src/gtkext/graph/edge.c
+++ b/src/gtkext/graph/edge.c
@@ -205,6 +205,27 @@ GGraphEdge *_g_graph_edge_new(const GdkPoint *start, const GdkPoint **mid, size_
/******************************************************************************
* *
+* Paramètres : edge = ligne de rendu à consulter. *
+* x1 = abscisse du point de départ de la ligne. [OUT] *
+* x2 = abscisse du point d'arrivée de la ligne. [OUT] *
+* *
+* Description : Fournit les abscisses des points extrèmes de la ligne. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void g_graph_edge_get_x_borders(const GGraphEdge *edge, gint *x1, gint *x2)
+{
+ *x1 = edge->start->x;
+ *x2 = edge->end->x;
+}
+
+
+/******************************************************************************
+* *
* Paramètres : edge = ligne de rendu à définir dans les détails. *
* *
* Description : Détermine les positions finales d'un lien graphique. *
diff --git a/src/gtkext/graph/edge.h b/src/gtkext/graph/edge.h
index 602c559..e2237c3 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)
+/* Fournit les abscisses des points extrèmes de la ligne. */
+void g_graph_edge_get_x_borders(const GGraphEdge *, gint *, gint *);
+
/* Détermine les positions finales d'un lien graphique. */
void g_graph_edge_resolve(GGraphEdge *);
--
cgit v0.11.2-87-g4458