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