From 4d0451c1153eb572f5ab0833c0c0911dfdc5f11a Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Mon, 4 May 2015 21:58:09 +0000 Subject: 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 --- ChangeLog | 19 +++ src/gtkext/graph/edge.c | 50 +++++++ src/gtkext/graph/edge.h | 3 + src/gtkext/graph/layout.c | 46 +++++- src/gtkext/graph/node.c | 16 +- src/gtkext/graph/node.h | 9 +- src/gtkext/graph/nodes/flow.c | 335 ++++++++++++++++++++++++++++++++++++++++-- src/gtkext/graph/nodes/flow.h | 9 ++ 8 files changed, 472 insertions(+), 15 deletions(-) diff --git a/ChangeLog b/ChangeLog index 3349302..7a1bd49 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,22 @@ +15-05-04 Cyrille Bagard + + * src/gtkext/graph/edge.c: + * src/gtkext/graph/edge.h: + Provide a method to compare edges in order to sort them. + + * src/gtkext/graph/layout.c: + Compute the layout twice in order to avoid edges crossings. + + * src/gtkext/graph/node.c: + * src/gtkext/graph/node.h: + Use g_graph_node_set_x_position() in g_graph_node_apply_position(). Find + nodes by either an entry or an exit instruction. + + * src/gtkext/graph/nodes/flow.c: + * src/gtkext/graph/nodes/flow.h: + Update code. Compare slots for edges. Reorder slot indexes in order to + avoid edges crossings. + 15-05-01 Cyrille Bagard * src/common/xml.c: diff --git a/src/gtkext/graph/edge.c b/src/gtkext/graph/edge.c index acd164c..5750198 100644 --- a/src/gtkext/graph/edge.c +++ b/src/gtkext/graph/edge.c @@ -212,6 +212,56 @@ GGraphEdge *g_graph_edge_new(GFlowNode *src_node, node_slot_t *src_slot, GFlowNo /****************************************************************************** * * +* Paramètres : a = premier lien à considérer. * +* b = second lien à considérer. * +* * +* Description : Etablit la comparaison entre deux liens graphiques. * +* * +* Retour : Bilan de la comparaison : -1, 0 ou 1. * +* * +* Remarques : - * +* * +******************************************************************************/ + +int g_graph_edge_compare(const GGraphEdge **a, const GGraphEdge **b) +{ + int result; /* Bilan à retourner */ + const GGraphEdge *_a; /* Commodité d'accès #1 */ + const GGraphEdge *_b; /* Commodité d'accès #2 */ + GdkPoint start_a; /* Point de départ A */ + GdkPoint start_b; /* Point de départ B */ + + _a = *a; + _b = *b; + + /** + * La comparaison s'établit sur le noeud d'arrivée. + */ + + if (_a->dest_node < _b->dest_node) + result = -1; + + else if (_a->dest_node > _b->dest_node) + result = 1; + + else + { + start_a = g_flow_node_get_point_from_slot(_a->src_node, false, _a->src_slot); + start_b = g_flow_node_get_point_from_slot(_b->src_node, false, _b->src_slot); + + result = g_flow_node_compare_slots_for_edges(_a->dest_node, + _a->dest_slot, start_a.x, + _b->dest_slot, start_b.x); + + } + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : edge = ligne de rendu à mettre à jour. * * nodes = noeud au sommet de la hiérarchie. * * ranks = classement global dans lequel s'intégrer. * diff --git a/src/gtkext/graph/edge.h b/src/gtkext/graph/edge.h index 9f7c760..64d9658 100644 --- a/src/gtkext/graph/edge.h +++ b/src/gtkext/graph/edge.h @@ -67,6 +67,9 @@ GType g_graph_edge_get_type(void); /* Etablit un lien graphique entre deux noeuds graphiques. */ GGraphEdge *g_graph_edge_new(GFlowNode *, node_slot_t *, GFlowNode *, node_slot_t *, EdgeColor); +/* Etablit la comparaison entre deux liens graphiques. */ +int g_graph_edge_compare(const GGraphEdge **, const GGraphEdge **); + /* Prend les dispositions nécessaires à l'insertion du lien. */ void g_graph_edge_reserve_vertical_space(GGraphEdge *, GGraphNode *, GGraphRanks *); diff --git a/src/gtkext/graph/layout.c b/src/gtkext/graph/layout.c index d2e3b51..1084578 100644 --- a/src/gtkext/graph/layout.c +++ b/src/gtkext/graph/layout.c @@ -25,6 +25,7 @@ #include +#include #include "node.h" @@ -318,11 +319,17 @@ void g_graph_layout_add_edge(GGraphLayout *layout, GGraphEdge *edge) * Remarques : - * * * ******************************************************************************/ - +#include "node-int.h" void g_graph_layout_refresh(GGraphLayout *layout) { size_t i; /* Boucle de parcours */ + + int counter = 0; + + + restart: + g_graph_ranks_reset_reservations(layout->ranks); bool _reset_cb(GGraphNode *node, GNodeVisitState state, void *unused) @@ -347,6 +354,43 @@ void g_graph_layout_refresh(GGraphLayout *layout) g_graph_node_prepare_x_line(layout->nodes, layout->nodes); g_graph_node_apply_position(layout->nodes); + + + bool _reorder_cb(GGraphNode *node, GNodeVisitState state, GGraphNode *nodes) + { + if (state == GVS_NODE) + g_flow_node_reorder_slots(G_FLOW_NODE(node), nodes); + return true; + } + + //qsort(layout->edges, layout->edges_count, sizeof(GGraphEdge *), (__compar_fn_t)g_graph_edge_compare); + + + + if (counter++ == 0) + { + g_graph_node_visit_nodes(layout->nodes, (graph_node_visitor_cb)_reorder_cb, layout->nodes); + goto restart; + } + + /* + bool _rinint_cb(GGraphNode *node, GNodeVisitState state, GGraphNode *nodes) + { + node->alloc.x = UNINITIALIZED_NODE_POS; + node->alloc.y = UNINITIALIZED_NODE_POS; + return true; + } + + g_graph_node_visit_nodes(layout->nodes, (graph_node_visitor_cb)_rinint_cb, layout->nodes); + + + g_graph_node_apply_position(layout->nodes); + */ + + qsort(layout->edges, layout->edges_count, sizeof(GGraphEdge *), (__compar_fn_t)g_graph_edge_compare); + + + for (i = 0; i < layout->edges_count; i++) g_graph_edge_reserve_horizontal_space(layout->edges[i], layout->ranks); diff --git a/src/gtkext/graph/node.c b/src/gtkext/graph/node.c index 9ff66b3..0210aa3 100644 --- a/src/gtkext/graph/node.c +++ b/src/gtkext/graph/node.c @@ -255,12 +255,14 @@ void g_graph_node_apply_position(GGraphNode *node) case PPF_LEFT_NODE: ref = node->pending_pos.left_node; - node->alloc.x = ref->alloc.x - NODE_HORIZONTAL_MARGIN - node->alloc.width; + x_pos = ref->alloc.x - NODE_HORIZONTAL_MARGIN - node->alloc.width; + g_graph_node_set_x_position(node, x_pos); break; case PPF_RIGHT_NODE: ref = node->pending_pos.right_node; - node->alloc.x = ref->alloc.x + ref->alloc.width - NODE_HORIZONTAL_MARGIN; + x_pos = ref->alloc.x + ref->alloc.width - NODE_HORIZONTAL_MARGIN; + g_graph_node_set_x_position(node, x_pos); break; default: @@ -581,6 +583,7 @@ GGraphNode *convert_blocks_into_nodes(GInstrBlock *block, GtkBufferView **views, * * * Paramètres : nodes = noeud au sommet de la hiérarchie. * * instr = instruction à retrouver. * +* entry = position de cette instruction : première ou dernière.* * * * Description : Recherche le noeud contenant une instruction donnée. * * * @@ -590,15 +593,17 @@ GGraphNode *convert_blocks_into_nodes(GInstrBlock *block, GtkBufferView **views, * * ******************************************************************************/ -GGraphNode *find_node_for_instruction(GGraphNode *nodes, GArchInstruction *instr) +GGraphNode *_find_node_for_instruction(GGraphNode *nodes, GArchInstruction *instr, bool entry) { GGraphNode *result; /* Trouvaille à retourner */ struct visit_params { GArchInstruction *instr; /* Instruction recherchée */ + bool entry; /* Première ou dernière ? */ GGraphNode *found; /* Remontée du noeud trouvé */ } params; /* Paramètres pour le parcours */ params.instr = instr; + params.entry = entry; params.found = NULL; bool _find_node_cb(GFlowNode *node, GNodeVisitState state, struct visit_params *params) @@ -607,8 +612,11 @@ GGraphNode *find_node_for_instruction(GGraphNode *nodes, GArchInstruction *instr if (state == GVS_NODE) { - if (g_flow_node_start_with(node, params->instr)) + if ((params->entry && g_flow_node_start_with(node, params->instr)) + || (!params->entry && g_flow_node_end_with(node, params->instr))) + { params->found = G_GRAPH_NODE(node); + } result = (params->found == NULL); } else result = true; diff --git a/src/gtkext/graph/node.h b/src/gtkext/graph/node.h index ab7d0da..502b366 100644 --- a/src/gtkext/graph/node.h +++ b/src/gtkext/graph/node.h @@ -146,7 +146,14 @@ GtkBufferView *find_graph_view_by_start_address(GtkBufferView **, size_t, const GGraphNode *convert_blocks_into_nodes(GInstrBlock *, GtkBufferView **, size_t); /* Recherche le noeud contenant une instruction donnée. */ -GGraphNode *find_node_for_instruction(GGraphNode *, GArchInstruction *); +GGraphNode *_find_node_for_instruction(GGraphNode *, GArchInstruction *, bool); + + +#define find_node_for_first_instruction(nds, ins) \ + _find_node_for_instruction(nds, ins, true) + +#define find_node_for_last_instruction(nds, ins) \ + _find_node_for_instruction(nds, ins, false) 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 +#include +#include #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, ¶ms.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, ¶ms, 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, ¶ms.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, ¶ms, 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 *); -- cgit v0.11.2-87-g4458