diff options
Diffstat (limited to 'src/gtkext/graph/cluster.c')
-rw-r--r-- | src/gtkext/graph/cluster.c | 402 |
1 files changed, 302 insertions, 100 deletions
diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c index 5785251..801929e 100644 --- a/src/gtkext/graph/cluster.c +++ b/src/gtkext/graph/cluster.c @@ -701,7 +701,6 @@ void g_graph_cluster_setup_links(GGraphCluster *cluster) { leaving->straight = true; leaving->straight_level = target_level; - continue; } /* Est-ce une sortie de cluster ? */ @@ -715,10 +714,7 @@ void g_graph_cluster_setup_links(GGraphCluster *cluster) break; if (k == container->ranks_count) - { leaving->cluster_exit = true; - continue; - } } @@ -741,7 +737,6 @@ void g_graph_cluster_setup_links(GGraphCluster *cluster) { leaving->forced_straight = true; leaving->straight_level = target_level; - continue; } } @@ -911,102 +906,267 @@ void g_graph_cluster_dispatch_x(GGraphCluster *cluster) /****************************************************************************** * * -* Paramètres : cluster = graphique de blocs à manipuler. * +* Paramètres : cluster = graphique de blocs à analyser. * +* root = élément à ne jamais croiser dans la paternité. * +* dir = préférence à actualiser si possible. [OUT] * * * -* Description : Réorganise au besoin les liens entrants d'un bloc. * +* Description : Détermine une direction préférée pour la suite du bloc. * * * -* Retour : - * +* Retour : false si une incapacité de détermination a été rencontrée. * * * * Remarques : - * * * ******************************************************************************/ -void g_graph_cluster_sort_incoming_links(GGraphCluster *cluster) +bool g_graph_cluster_get_exit_direction(const GGraphCluster *cluster, const GGraphCluster *root, LeavingLinkDir *dir) { - size_t i; /* Boucle de parcours */ + bool result; /* Bilan à renvoyer */ + size_t i; /* Boucle de parcours #1 */ + const leaving_link_t *leaving; /* Lien sortant à traiter */ + GGraphCluster *iter; /* Boucle de parcours #2 */ + LeavingLinkDir pref; /* Préférence du lien courant */ - qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_link_t *), (__compar_fn_t)cmp_incoming_links); + result = true; - for (i = 0; i < cluster->ranks_count; i++) - sort_graph_rank_incoming_links(&cluster->ranks[i]); + for (i = 0; i < cluster->ba_count && result; i++) + { + leaving = cluster->bottom_anchors[i]; - sort_incoming_links_for_vspace_manager(&cluster->self); + if (!leaving->cluster_exit) + continue; + + /* Validation d'une sortie du cluster d'origine */ + + for (iter = leaving->other->owner; iter != NULL; iter = iter->owner) + if (iter == root) + break; + + if (iter != NULL) + continue; + + pref = get_leaving_link_direction(leaving); + + /* Si la direction est claire... */ + if (*dir == LLD_NO_PREF) + *dir = pref; + + /* Multiples directions, on ne sait pas trancher ! */ + else if (*dir != pref) + result = false; + + } + + for (i = 0; i < cluster->ranks_count && result; i++) + result = get_graph_rank_exit_direction(&cluster->ranks[i], root, dir); + + return result; } /****************************************************************************** * * -* Paramètres : cluster = graphique de blocs à consulter. * -* incoming = adresse de l'autre bout du lien concerné. * +* Paramètres : cluster = graphique de blocs à manipuler. * * * -* Description : Retrouve l'indice d'un lien entrant donné pour un bloc. * +* Description : Réorganise au besoin les liens sortants d'un bloc. * * * -* Retour : Indice à priori toujours valide. * +* Retour : - * * * * Remarques : - * * * ******************************************************************************/ -size_t g_graph_cluster_find_incoming_link(const GGraphCluster *cluster, const leaving_link_t *leaving) +void g_graph_cluster_sort_leaving_links(GGraphCluster *cluster) { - size_t result; /* Indice à retourner */ + size_t i; /* Boucle de parcours */ + leaving_link_t **left; /* Liens à placer à gauche */ + leaving_link_t **center; /* Liens à placer au milieu */ + leaving_link_t **right; /* Liens à placer à droite */ + size_t left_count; /* Quantité de liens à gauche */ + size_t center_count; /* Quantité de liens au milieu */ + size_t right_count; /* Quantité de liens à droite */ + leaving_link_t *leaving; /* Lien sortant à traiter */ + LeavingLinkDir pref; /* Préférence du lien courant */ - for (result = 0; result < cluster->ta_count; result++) - if (cluster->top_anchors[result]->other == leaving) - break; + /** + * On n'intervient que s'il y a lieu de le faire, notamment si les sorties + * du groupe de blocs ont une direction claire. + */ - assert(cluster->ta_count); + pref = LLD_NO_PREF; - return result; + if (!g_graph_cluster_get_exit_direction(cluster, cluster, &pref)) + goto done; + + if (cluster->ba_count < 2 || pref == LLD_NO_PREF) + goto done; + + left = NULL; + center = NULL; + right = NULL; + + left_count = 0; + center_count = 0; + right_count = 0; + + /* Réorganisation des liens */ + + for (i = 0; i < cluster->ba_count; i++) + { + leaving = cluster->bottom_anchors[i]; + + if (SHOULD_BE_VERTICAL(leaving)) + { + if (leaving->cluster_exit) + pref = get_leaving_link_direction(leaving); + + else + pref = LLD_NO_PREF; + + } + else + { + pref = LLD_NO_PREF; + + if (!g_graph_cluster_get_exit_direction(leaving->other->owner, leaving->other->owner, &pref)) + pref = LLD_NO_PREF; + + } + + switch (pref) + { + case LLD_TO_LEFT: + left = realloc(left, ++left_count * sizeof(leaving_link_t *)); + left[left_count - 1] = leaving; + break; + + case LLD_NO_PREF: + center = realloc(center, ++center_count * sizeof(leaving_link_t *)); + center[center_count - 1] = leaving; + break; + + case LLD_TO_RIGHT: + right = realloc(right, ++right_count * sizeof(leaving_link_t *)); + right[right_count - 1] = leaving; + break; + + } + + } + + /* Sauvegarde du nouvel arrangement */ + + assert((left_count + center_count + right_count) == cluster->ba_count); + + cluster->ba_count = 0; + + if (left != NULL) + { + qsort_r(left, left_count, sizeof(leaving_link_t *), + (__compar_d_fn_t)cmp_leaving_links, + (LeavingLinkDir []) { LLD_TO_LEFT }); + + for (i = 0; i < left_count; i++) + cluster->bottom_anchors[cluster->ba_count++] = left[i]; + + free(left); + + } + + if (center != NULL) + { + for (i = 0; i < center_count; i++) + cluster->bottom_anchors[cluster->ba_count++] = center[i]; + + free(center); + + } + + if (right != NULL) + { + qsort_r(right, right_count, sizeof(leaving_link_t *), + (__compar_d_fn_t)cmp_leaving_links, + (LeavingLinkDir []) { LLD_TO_RIGHT }); + + for (i = 0; i < right_count; i++) + cluster->bottom_anchors[cluster->ba_count++] = right[i]; + + free(right); + + } + + assert((left_count + center_count + right_count) == cluster->ba_count); + + for (i = 0; i < cluster->ba_count; i++) + cluster->bottom_anchors[i]->index = i; + + /* Application de la nouvelle disposition */ + + for (i = 0; i < cluster->ranks_count; i++) + reorder_graph_rank_clusters(&cluster->ranks[i], cluster); + + for (i = 0; i < cluster->ranks_count; i++) + reset_graph_rank_allocation(&cluster->ranks[i]); + + for (i = 0; i < cluster->ranks_count; i++) + offset_x_graph_rank(&cluster->ranks[i], cluster->alloc.x); + + g_graph_cluster_dispatch_x(cluster); + + g_graph_cluster_set_y(cluster, cluster->alloc.y); + + done: + + for (i = 0; i < cluster->ranks_count; i++) + visit_graph_rank(&cluster->ranks[i], g_graph_cluster_sort_leaving_links); } /****************************************************************************** * * -* Paramètres : cluster = graphique de blocs à analyser. * -* l2r = indique si le lien trouvé part vers à droite. [OUT]* +* Paramètres : cluster = graphique de blocs à consulter. * +* pos = ordonnées minimale et maximale en bout. [OUT] * * * -* Description : Détermine si un cluster possède un lien sortant. * +* Description : Calcule les ordonnées extrèmes atteintes via liens sortants. * * * -* Retour : true si le chef de file à un lien qui sort de l'ensemble. * +* Retour : true si un lien sortant a été trouvé, false sinon. * * * * Remarques : - * * * ******************************************************************************/ -bool g_graph_cluster_has_exit_link(GGraphCluster *cluster, bool *l2r) +bool g_graph_cluster_compute_min_max_bottom(const GGraphCluster *cluster, gint pos[2]) { bool result; /* Bilan à retourner */ size_t i; /* Boucle de parcours */ - leaving_link_t *leaving; /* Lien manipulé */ - gint x1; /* Abscisse de départ de lien */ - size_t idx; /* Indice du lien entrant */ - gint x2; /* Abscisse d'arrivée de lien */ + const leaving_link_t *leaving; /* Lien sortant à traiter */ + gint y; /* Ordonnée rencontrée */ result = false; - for (i = 0; i < cluster->ba_count && !result; i++) + for (i = 0; i < cluster->ba_count; i++) { leaving = cluster->bottom_anchors[i]; - if (leaving->cluster_exit) - { - result = true; - - x1 = compute_leaving_link_position(leaving); + if (!leaving->cluster_exit) + continue; - idx = g_graph_cluster_find_incoming_link(leaving->other->owner, leaving); + result = true; - x2 = g_graph_cluster_compute_incoming_link_position(leaving->other->owner, idx); + y = leaving->other->owner->alloc.y; - *l2r = (x1 < x2); + if (y < pos[0]) + pos[0] = y; - } + if (pos[1] < y) + pos[1] = y; } + for (i = 0; i < cluster->ranks_count; i++) + result |= compute_graph_rank_min_max_bottom(&cluster->ranks[i], pos); + return result; } @@ -1014,69 +1174,75 @@ bool g_graph_cluster_has_exit_link(GGraphCluster *cluster, bool *l2r) /****************************************************************************** * * -* Paramètres : cluster = premier graphique de blocs à analyser. * -* other = second graphique de blocs à analyser. * -* l2r = indique si le lien trouvé part vers à droite. * +* Paramètres : cluster = graphique de blocs à analyser. * +* origin = cluster d'origine à considérer. * * * -* Description : Compare deux clusters avec lien sortant. * +* Description : Retrouve s'il existe un lien entrant vers un bloc d'origine. * * * -* Retour : Bilan de la comparaison. * +* Retour : Lien vers le bloc d'origine trouvé ou NULL. * * * * Remarques : - * * * ******************************************************************************/ -int g_graph_cluster_compare_by_exit(const GGraphCluster **cluster, const GGraphCluster **other, const bool *l2r) +const leaving_link_t *g_graph_cluster_has_origin(const GGraphCluster *cluster, const GGraphCluster *origin) { - int result; /* Bilan à renvoyer */ + const leaving_link_t *result; /* Lien trouvé à renvoyer */ size_t i; /* Boucle de parcours */ - gint cluster_y; /* Position de la sortie #0 */ - gint other_y; /* Position de la sortie #1 */ - leaving_link_t *leaving; /* Lien manipulé */ - cluster_y = 0; - other_y = 0; + result = NULL; - for (i = 0; i < (*cluster)->ba_count; i++) - { - leaving = (*cluster)->bottom_anchors[i]; + for (i = 0; i < cluster->ta_count && result == NULL; i++) + if (cluster->top_anchors[i]->other->owner == origin) + result = cluster->top_anchors[i]->other; - if (leaving->cluster_exit) - { - cluster_y = leaving->other->owner->alloc.y; - break; - } + return result; - } +} - assert(i < (*cluster)->ba_count); - for (i = 0; i < (*other)->ba_count; i++) - { - leaving = (*other)->bottom_anchors[i]; +/****************************************************************************** +* * +* Paramètres : cluster = premier graphique de blocs à analyser. * +* other = second graphique de blocs à analyser. * +* origin = cluster d'origine à considérer. * +* * +* Description : Compare deux clusters selon un de leurs liens d'origine. * +* * +* Retour : Bilan de la comparaison. * +* * +* Remarques : - * +* * +******************************************************************************/ - if (leaving->cluster_exit) - { - other_y = leaving->other->owner->alloc.y; - break; - } +int g_graph_cluster_compare_by_origin(const GGraphCluster **cluster, const GGraphCluster **other, const GGraphCluster *origin) +{ + int result; /* Bilan à renvoyer */ + const leaving_link_t *leaving; /* Accès au lien manipulé */ + gint x0; /* Première abscisse à traiter */ + gint x1; /* Seconde abscisse à traiter */ - } + leaving = g_graph_cluster_has_origin(*cluster, origin); + + assert(leaving != NULL); + + x0 = compute_leaving_link_position(leaving); + + leaving = g_graph_cluster_has_origin(*other, origin); + + assert(leaving != NULL); - assert(i < (*other)->ba_count); + x1 = compute_leaving_link_position(leaving); - if (cluster_y < other_y) + if (x0 < x1) result = -1; - else if (cluster_y > other_y) + else if (x0 > x1) result = 1; else result = 0; - if (*l2r) - result *= -1; - return result; } @@ -1084,9 +1250,9 @@ int g_graph_cluster_compare_by_exit(const GGraphCluster **cluster, const GGraphC /****************************************************************************** * * -* Paramètres : cluster = graphique de blocs à actualiser. * +* Paramètres : cluster = graphique de blocs à manipuler. * * * -* Description : Réordonne les blocs sortant du cluster au mieux. * +* Description : Réorganise au besoin les liens entrants d'un bloc. * * * * Retour : - * * * @@ -1094,12 +1260,44 @@ int g_graph_cluster_compare_by_exit(const GGraphCluster **cluster, const GGraphC * * ******************************************************************************/ -void g_graph_cluster_reorder_exit_blocks(GGraphCluster *cluster) +void g_graph_cluster_sort_incoming_links(GGraphCluster *cluster) { size_t i; /* Boucle de parcours */ + qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_link_t *), (__compar_fn_t)cmp_incoming_links); + for (i = 0; i < cluster->ranks_count; i++) - reorder_graph_rank_exit_blocks(&cluster->ranks[i]); + sort_graph_rank_incoming_links(&cluster->ranks[i]); + + sort_incoming_links_for_vspace_manager(&cluster->self); + +} + + +/****************************************************************************** +* * +* Paramètres : cluster = graphique de blocs à consulter. * +* incoming = adresse de l'autre bout du lien concerné. * +* * +* Description : Retrouve l'indice d'un lien entrant donné pour un bloc. * +* * +* Retour : Indice à priori toujours valide. * +* * +* Remarques : - * +* * +******************************************************************************/ + +size_t g_graph_cluster_find_incoming_link(const GGraphCluster *cluster, const leaving_link_t *leaving) +{ + size_t result; /* Indice à retourner */ + + for (result = 0; result < cluster->ta_count; result++) + if (cluster->top_anchors[result]->other == leaving) + break; + + assert(result < cluster->ta_count); + + return result; } @@ -2256,6 +2454,25 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList * g_graph_cluster_dispatch_x(result); /** + * Une première passe d'organisation horizontale est réalisée. + * + * A ce point, en proposant des emplacements verticaux en complément, + * on est en mesure de déterminer si les liens qui sortent de leur + * conteneur vont en croiser d'autres. + * + * On réorganise ainsi au besoin les différents blocs pour éviter ce cas + * de figure. Les blocs sont replacés à une nouvelle position horizontale + * au besoin. + * + * Une illustration concrête de la nécessité de cette opération est la + * fonction test_ite_2() de la suite de tests. + */ + + g_graph_cluster_set_y(result, 0); + + g_graph_cluster_sort_leaving_links(result); + + /** * A ce point, tous les blocs 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 @@ -2272,21 +2489,6 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList * g_graph_cluster_sort_incoming_links(result); /** - * Comme des profondeurs de rang identiques peuvent renvoyer à des - * positions verticales différentes selon les chemins présents, - * on lance ici une réorganisation des blocs qui ont une sortie fuyante - * de leur ensemble parent en plaçant, même de façon parcellaire, l'ensemble - * des blocs. - * - * Une illustration concrête de cette nécessité est la fonction test_ite_2() - * de la suite de tests. - */ - - g_graph_cluster_set_y(result, 0); - - g_graph_cluster_reorder_exit_blocks(result); - - /** * Même s'ils ne sont pas encore entièrement tracés, les liens de boucle * voient désormais leurs positions d'arrivée et de départ définies. * |