summaryrefslogtreecommitdiff
path: root/src/gtkext/graph/nodes
diff options
context:
space:
mode:
authorCyrille Bagard <nocbos@gmail.com>2015-05-04 21:58:09 (GMT)
committerCyrille Bagard <nocbos@gmail.com>2015-05-04 21:58:09 (GMT)
commit4d0451c1153eb572f5ab0833c0c0911dfdc5f11a (patch)
tree6fb1690ded59d323bb21ac200dabb69dca528f2d /src/gtkext/graph/nodes
parent08adf78fbff30d213891a533fbf43d91816b166a (diff)
Reordered slot indexes in order to avoid edges crossings.
git-svn-id: svn://svn.gna.org/svn/chrysalide/trunk@525 abbe820e-26c8-41b2-8c08-b7b2b41f8b0a
Diffstat (limited to 'src/gtkext/graph/nodes')
-rw-r--r--src/gtkext/graph/nodes/flow.c335
-rw-r--r--src/gtkext/graph/nodes/flow.h9
2 files changed, 335 insertions, 9 deletions
diff --git a/src/gtkext/graph/nodes/flow.c b/src/gtkext/graph/nodes/flow.c
index e502293..ca5dceb 100644
--- a/src/gtkext/graph/nodes/flow.c
+++ b/src/gtkext/graph/nodes/flow.c
@@ -25,6 +25,8 @@
#include <assert.h>
+#include <malloc.h>
+#include <stdlib.h>
#include "../layout.h"
@@ -249,8 +251,6 @@ GGraphNode *g_flow_node_new(GFlowBlock *block, GtkBufferView *view)
gtk_widget_get_preferred_size(GTK_WIDGET(result->view), NULL, &requisition);
- printf("PREFERED :: (%d ; %d)\n", requisition.width, requisition.height);
-
G_GRAPH_NODE(result)->alloc.width = requisition.width;
G_GRAPH_NODE(result)->alloc.height = requisition.height;
@@ -325,7 +325,7 @@ static void g_flow_node_prepare_x_line(GFlowNode *node, GGraphNode *nodes)
if (loop_index == node->exits_count)
{
- target = G_FLOW_NODE(find_node_for_instruction(nodes, node->exits[0].instr));
+ target = G_FLOW_NODE(find_node_for_first_instruction(nodes, node->exits[0].instr));
/* Cf. commentaire de g_flow_node_link() */
if (target == NULL) break;
@@ -336,7 +336,7 @@ static void g_flow_node_prepare_x_line(GFlowNode *node, GGraphNode *nodes)
}
else
{
- target = G_FLOW_NODE(find_node_for_instruction(nodes, node->exits[1].instr));
+ target = G_FLOW_NODE(find_node_for_first_instruction(nodes, node->exits[1].instr));
/* Cf. commentaire de g_flow_node_link() */
if (target == NULL) break;
@@ -370,8 +370,8 @@ static void g_flow_node_prepare_x_line(GFlowNode *node, GGraphNode *nodes)
case 2:
- target_a = G_FLOW_NODE(find_node_for_instruction(nodes, node->exits[0].instr));
- target_b = G_FLOW_NODE(find_node_for_instruction(nodes, node->exits[1].instr));
+ target_a = G_FLOW_NODE(find_node_for_first_instruction(nodes, node->exits[0].instr));
+ target_b = G_FLOW_NODE(find_node_for_first_instruction(nodes, node->exits[1].instr));
rank_a = g_flow_node_get_rank(target_a);
rank_b = g_flow_node_get_rank(target_b);
@@ -506,6 +506,30 @@ bool g_flow_node_start_with(const GFlowNode *node, GArchInstruction *instr)
/******************************************************************************
* *
* Paramètres : node = noeud graphique à consulter. *
+* instr = instruction à considérer. *
+* *
+* Description : Précise si le noeud a pour dernière instruction celle donnée.*
+* *
+* Retour : true si la dernière instruction du noeud est celle indiquée. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+bool g_flow_node_end_with(const GFlowNode *node, GArchInstruction *instr)
+{
+ GArchInstruction *last; /* Dernière instr. du noeud */
+
+ g_flow_block_get_boundary(node->block, NULL, &last);
+
+ return (last == instr);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : node = noeud graphique à consulter. *
* ranks = classement à mettre à jour. *
* *
* Description : Précise la hauteur minimale requise pour un noeud. *
@@ -578,7 +602,7 @@ void g_flow_node_link(GFlowNode *node, GGraphLayout *layout, GGraphNode *nodes)
for (i = 0; i < node->exits_count; i++)
{
- target = G_FLOW_NODE(find_node_for_instruction(nodes, node->exits[i].instr));
+ target = G_FLOW_NODE(find_node_for_first_instruction(nodes, node->exits[i].instr));
/**
* Il semblerait que l'adresse ciblée puisse ne correspondre à aucun bloc.
@@ -646,6 +670,114 @@ void g_flow_node_place(const GFlowNode *node, GtkGraphView *view)
/******************************************************************************
* *
+* Paramètres : node = noeud graphique contenant les accrochées indiquées. *
+* a = première accroche à considérer. *
+* b = seconde accroche à considérer. *
+* *
+* Description : Compare deux accroches pour liens entre noeuds. *
+* *
+* Retour : Bilan de la comparaison : -1, 0 ou 1. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+int g_flow_node_compare_slots_for_edges(const GFlowNode *node, const node_slot_t *a, gint src_a, const node_slot_t *b, gint src_b)
+{
+ int result; /* Bilan à retourner */
+ GGraphNode *base; /* Accès rapides */
+ gint middle; /* Milieu du noeud traité */
+ gint diff_a; /* Distance A <-> centre */
+ gint diff_b; /* Distance B <-> centre */
+
+
+ /**
+ * On place les extrémités en premier, afin de les traiter en premier.
+ */
+
+ int cmp_slot_indexes(const node_slot_t *a, const node_slot_t *b)
+ {
+ int result;
+
+ if (a->slot_index < b->slot_index)
+ result = 1;
+
+ else if (a->slot_index > b->slot_index)
+ result = -1;
+
+ else
+ result = 0;
+
+ return result;
+
+ }
+
+
+ switch (node->entries_count)
+ {
+ case 0:
+ case 1:
+ assert(0);
+ break;
+
+ case 2:
+
+ /**
+ * Le tri se fait simplement : un accroche à gauche, l'autre à droite.
+ */
+
+ result = cmp_slot_indexes(a, b);
+ break;
+
+ default:
+
+ /**
+ * On donne plus de poids aux accroches éloignées du centre.
+ * Facile quand les accroches sont distribuées d'un même côté, centre
+ * à utiliser dans les calculs sinon.
+ */
+
+ base = G_GRAPH_NODE(node);
+
+ middle = base->alloc.x + (base->alloc.width / 2);
+
+
+ /* Les deux accroches sont à gauche */
+ if (src_a <= middle && src_b <= middle)
+ result = cmp_slot_indexes(b, a);
+
+ /* Les deux accroches sont à droite */
+ else if (src_a > middle && src_b > middle)
+ result = cmp_slot_indexes(a, b);
+
+ /* Les deux accroches sont de chaque côté */
+ else
+ {
+ diff_a = (middle > src_a ? middle - src_a : src_a - middle);
+ diff_b = (middle > src_b ? middle - src_b : src_b - middle);
+
+ if (diff_a < diff_b)
+ result = 1;
+
+ else if (diff_a > diff_b)
+ result = -1;
+
+ else
+ result = 0;
+
+ }
+
+ break;
+
+ }
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
* Paramètres : node = intermédiaire à compléter. *
* *
* Description : Prépare les points d'entrées du noeud. *
@@ -719,7 +851,7 @@ static void g_flow_node_setup_entry_slots(GFlowNode *node)
node->entries[used].type = types[i];
node->entries[used].group_index = g_arch_instruction_compute_group_index(&instrs[i],
instrs, icount);
- node->entries[used].slot_index = i;
+ node->entries[used].slot_index = used;
used++;
@@ -810,7 +942,7 @@ static void g_flow_node_setup_exit_slots(GFlowNode *node)
node->exits[used].type = types[i];
node->exits[used].group_index = g_arch_instruction_compute_group_index(&instrs[i],
instrs, icount);
- node->exits[used].slot_index = i;
+ node->exits[used].slot_index = used;
used++;
@@ -913,6 +1045,8 @@ static gint g_flow_node_get_slot_offset(const GFlowNode *node, bool entry, const
index = (slot - slots);
/* BUG_ON(index >= count); */
+ index = slot->slot_index;
+
result = slots_left + index * SPACE_BETWEEN_SLOT;
return result;
@@ -922,6 +1056,182 @@ static gint g_flow_node_get_slot_offset(const GFlowNode *node, bool entry, const
/******************************************************************************
* *
+* Paramètres : node = intermédiaire à consulter. *
+* nodes = ensemble des noeuds en place. *
+* *
+* Description : Réorganise au mieux les points d'accroche d'un noeud. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+#include "../../../arch/instruction-int.h"
+void g_flow_node_reorder_slots(const GFlowNode *node, GGraphNode *nodes)
+{
+
+ typedef struct _reordering_params
+ {
+ GdkPoint middle; /* Milieu du noeud traité */
+ bool down_first; /* Liens descendants aux bords */
+
+ bool entry; /* Zone d'accrochage aux bouts */
+ GArchInstruction *instr; /* Instruction du bloc courant */
+
+ } reordering_params;
+
+ typedef struct _reordered_slot
+ {
+ const reordering_params *params; /* Informations partagées */
+
+ GdkPoint dest; /* Position à l'extrémité */
+
+ size_t orig_index; /* Indice d'accroche d'origine */
+
+ } reordered_slot;
+
+
+ GGraphNode *base; /* Accès rapides */
+ reordering_params params; /* Directives générales */
+
+
+ int cmp_slots_for_reordering(const reordered_slot *a, const reordered_slot *b)
+ {
+ const reordering_params *params; /* Informations partagées */
+ bool on_left_a; /* Lien A vers la gauche ? */
+ bool on_left_b; /* Lien B vers la gauche ? */
+ bool go_down_a; /* Lien A vers le bas ? */
+ bool go_down_b; /* Lien B vers le bas ? */
+
+ params = a->params;
+
+ /* Première distinction : côté par rapport au centre */
+
+ on_left_a = (a->dest.x <= params->middle.x);
+ on_left_b = (b->dest.x <= params->middle.x);
+
+ if (on_left_a && !on_left_b) return -1;
+ else if (!on_left_a && on_left_b) return 1;
+
+ /* On évite les recoupements entre montées et descentes */
+
+ go_down_a = (a->dest.y >= params->middle.y);
+ go_down_b = (b->dest.y >= params->middle.y);
+
+ if (go_down_a && !go_down_b) return (params->down_first ? -1 : 1);
+ else if (!go_down_a && go_down_b) return (params->down_first ? -1 : 1);
+
+ /* Au sein d'une même catégorie, on se base uniquement sur la position */
+
+ return (a->dest.x <= b->dest.x ? -1 : 1);
+
+ }
+
+ void reorder_slots(node_slot_t *slots, size_t count, __compar_fn_t cmp, const reordering_params *params, GGraphNode *nodes)
+ {
+ reordered_slot *rslots; /* Créneaux réorganisés */
+ reordered_slot *iter; /* Boucle de parcours #1 */
+ size_t used; /* Nombre de liens valides */
+ size_t i; /* Boucle de parcours #2 */
+ GFlowNode *target; /* Bloc visé par le lien */
+ node_slot_t *dest_slot; /* Accrochage associé */
+
+ rslots = (reordered_slot *)calloc(count, sizeof(reordered_slot));
+
+ /* Constitution d'une liste triée */
+
+ iter = rslots;
+ used = 0;
+
+ for (i = 0; i < count; i++)
+ {
+ iter->params = params;
+
+ target = G_FLOW_NODE(_find_node_for_instruction(nodes, slots[i].instr, params->entry));
+
+ /* Cf. commentaire de g_flow_node_link() */
+ if (target == NULL) continue;
+
+ dest_slot = g_flow_node_get_slot(target, params->entry,
+ params->instr, slots[i].group_index);
+
+ iter->dest = g_flow_node_get_point_from_slot(target, params->entry, dest_slot);
+
+ iter->orig_index = i;
+
+ iter++;
+ used++;
+
+ }
+
+ /* TODO : utiliser qsort_r, avec params en argument ? */
+ qsort(rslots, used, sizeof(reordered_slot), cmp);
+
+
+
+
+ for (i = 0; i < used; i++)
+ {
+
+
+ if (rslots[i].orig_index != i)
+ printf("Could reorder %zu -> %zu\n", rslots[i].orig_index, i);
+
+ if (rslots[i].orig_index != i)
+ slots[rslots[i].orig_index].slot_index = i;
+
+
+
+ }
+
+ free(rslots);
+
+ }
+
+
+ base = G_GRAPH_NODE(node);
+
+ /* Régorganise les accroches d'entrée */
+
+ if (node->entries_count > 1)
+ {
+ params.middle.x = base->alloc.x + (base->alloc.width / 2);
+ params.middle.y = base->alloc.y;
+
+ params.down_first = true;
+
+ params.entry = false;
+ g_flow_block_get_boundary(node->block, &params.instr, NULL);
+
+ printf(" ### REORDERING ENTRIES OF 0x%08x\n", (unsigned int)params.instr->range.addr.virtual);
+
+ reorder_slots(node->entries, node->entries_count, (__compar_fn_t)cmp_slots_for_reordering, &params, nodes);
+
+ }
+
+ /* Régorganise les accroches de sortie */
+
+ if (node->exits_count > 1)
+ {
+ params.middle.x = base->alloc.x + (base->alloc.width / 2);
+ params.middle.y = base->alloc.y + base->alloc.height;
+
+ params.down_first = false;
+
+ params.entry = true;
+ g_flow_block_get_boundary(node->block, NULL, &params.instr);
+
+ printf(" ### REORDERING EXITS OF 0x%08x\n", (unsigned int)params.instr->range.addr.virtual);
+
+ reorder_slots(node->exits, node->exits_count, (__compar_fn_t)cmp_slots_for_reordering, &params, nodes);
+
+ }
+
+}
+
+
+/******************************************************************************
+* *
* Paramètres : node = noeud graphique à consulter. *
* entry = indique le type d'accrochage recherché. *
* slot = accroche dont l'emplacement est à définir. *
@@ -969,6 +1279,13 @@ GdkPoint g_flow_node_get_point_from_slot(const GFlowNode *node, bool entry, cons
index = (slot - slots)/* / sizeof(node_slot_t)*/;
/* BUG_ON(index >= count); */
+
+ if (count > 1 && entry)
+ printf(" -->> index = %zu vs %zu (max = %zu)\n", index, slot->slot_index, count);
+
+ index = slot->slot_index;
+
+
result.x = slots_left + index * SPACE_BETWEEN_SLOT;
return result;
diff --git a/src/gtkext/graph/nodes/flow.h b/src/gtkext/graph/nodes/flow.h
index f659a77..76d0a03 100644
--- a/src/gtkext/graph/nodes/flow.h
+++ b/src/gtkext/graph/nodes/flow.h
@@ -65,6 +65,9 @@ GFlowBlock *g_flow_node_get_block(const GFlowNode *);
/* Précise si le noeud a pour première instruction celle donnée. */
bool g_flow_node_start_with(const GFlowNode *, GArchInstruction *);
+/* Précise si le noeud a pour dernière instruction celle donnée. */
+bool g_flow_node_end_with(const GFlowNode *, GArchInstruction *);
+
/* Précise la hauteur minimale requise pour un noeud. */
void g_flow_node_register_rank(const GFlowNode *, GGraphRanks *);
@@ -82,6 +85,12 @@ void g_flow_node_place(const GFlowNode *, GtkGraphView *);
/* ------------------------ GESTION DES ACCROCHES D'UN NOEUD ------------------------ */
+/* Compare deux accroches pour liens entre noeuds. */
+int g_flow_node_compare_slots_for_edges(const GFlowNode *, const node_slot_t *, gint, const node_slot_t *, gint);
+
+/* Réorganise au mieux les points d'accroche d'un noeud. */
+void g_flow_node_reorder_slots(const GFlowNode *, GGraphNode *);
+
/* Localise un point d'accroche à un noeud graphique. */
GdkPoint g_flow_node_get_point_from_slot(const GFlowNode *, bool, const node_slot_t *);