diff options
Diffstat (limited to 'src/gtkext')
| -rw-r--r-- | src/gtkext/graph/cluster-int.h | 24 | ||||
| -rw-r--r-- | src/gtkext/graph/cluster.c | 402 | ||||
| -rw-r--r-- | src/gtkext/graph/leaving.c | 124 | ||||
| -rw-r--r-- | src/gtkext/graph/leaving.h | 15 | ||||
| -rw-r--r-- | src/gtkext/graph/rank.c | 149 | ||||
| -rw-r--r-- | src/gtkext/graph/rank.h | 18 |
6 files changed, 576 insertions, 156 deletions
diff --git a/src/gtkext/graph/cluster-int.h b/src/gtkext/graph/cluster-int.h index 881a60a..3121d64 100644 --- a/src/gtkext/graph/cluster-int.h +++ b/src/gtkext/graph/cluster-int.h @@ -49,21 +49,27 @@ void g_graph_cluster_setup_links(GGraphCluster *); /* Organise la disposition d'un ensemble de blocs basiques. */ void g_graph_cluster_dispatch_x(GGraphCluster *); +/* Détermine une direction préférée pour la suite du bloc. */ +bool g_graph_cluster_get_exit_direction(const GGraphCluster *, const GGraphCluster *, LeavingLinkDir *); + +/* Réorganise au besoin les liens sortants d'un bloc. */ +void g_graph_cluster_sort_leaving_links(GGraphCluster *); + +/* Calcule les ordonnées extrèmes atteintes via liens sortants. */ +bool g_graph_cluster_compute_min_max_bottom(const GGraphCluster *cluster, gint [2]); + +/* Retrouve s'il existe un lien entrant vers un bloc d'origine. */ +const leaving_link_t *g_graph_cluster_has_origin(const GGraphCluster *, const GGraphCluster *); + +/* Compare deux clusters selon un de leurs liens d'origine. */ +int g_graph_cluster_compare_by_origin(const GGraphCluster **, const GGraphCluster **, const GGraphCluster *); + /* Réorganise au besoin les liens entrants d'un bloc. */ void g_graph_cluster_sort_incoming_links(GGraphCluster *); /* Retrouve l'indice d'un lien entrant donné pour un bloc. */ size_t g_graph_cluster_find_incoming_link(const GGraphCluster *, const leaving_link_t *); -/* Détermine si un cluster possède un lien sortant. */ -bool g_graph_cluster_has_exit_link(GGraphCluster *, bool *); - -/* Compare deux clusters avec lien sortant. */ -int g_graph_cluster_compare_by_exit(const GGraphCluster **, const GGraphCluster **, const bool *); - -/* Réordonne les blocs sortant du cluster au mieux. */ -void g_graph_cluster_reorder_exit_blocks(GGraphCluster *); - /* Réordonne les blocs de départ de boucle au mieux. */ void g_graph_cluster_reorder_loop_blocks(GGraphCluster *); 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. * diff --git a/src/gtkext/graph/leaving.c b/src/gtkext/graph/leaving.c index ad07f04..3147784 100644 --- a/src/gtkext/graph/leaving.c +++ b/src/gtkext/graph/leaving.c @@ -24,6 +24,7 @@ #include "leaving.h" +#include <assert.h> #include <malloc.h> @@ -105,3 +106,126 @@ gint compute_leaving_link_position(const leaving_link_t *link) return result; } + + +/****************************************************************************** +* * +* Paramètres : link = information sur un lien à consulter. * +* * +* Description : Détermine une direction prise par un lien à son départ. * +* * +* Retour : Direction prise à l'écran. * +* * +* Remarques : - * +* * +******************************************************************************/ + +LeavingLinkDir get_leaving_link_direction(const leaving_link_t *link) +{ + LeavingLinkDir result; /* Préférence à retourner */ + gint x1; /* Abscisse de départ de lien */ + GGraphCluster *owner; /* Raccourci vers le proprio */ + size_t idx; /* Indice du lien entrant */ + gint x2; /* Abscisse d'arrivée de lien */ + + x1 = compute_leaving_link_position(link); + + owner = link->other->owner; + + idx = g_graph_cluster_find_incoming_link(owner, link); + + x2 = g_graph_cluster_compute_incoming_link_position(owner, idx); + + if (x1 < x2) + result = LLD_TO_RIGHT; + + else if (x1 > x2) + result = LLD_TO_LEFT; + + else + result = LLD_NO_PREF; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : a = premier lien entrant à comparer. * +* b = second lien entrant à comparer. * +* dir = complément d'information quant à la direction traitée. * +* * +* Description : Compare deux liens sortants. * +* * +* Retour : Bilan de comparaison. * +* * +* Remarques : - * +* * +******************************************************************************/ + +int cmp_leaving_links(const leaving_link_t **a, const leaving_link_t **b, const LeavingLinkDir *dir) +{ + int result; /* Bilan à retourner */ + GGraphCluster *owner; /* Raccourci vers le proprio */ + gint pos_a[2]; /* Points de départ pour A */ + GtkAllocation alloc; /* Emplacement de cluster */ + gint pos_b[2]; /* Points de départ pour B */ + + /* Calcul des ordonnées des points de chute */ + + owner = (*a)->other->owner; + + pos_a[0] = G_MAXINT; + pos_a[1] = 0; + + if (!g_graph_cluster_compute_min_max_bottom(owner, pos_a)) + { + g_graph_cluster_get_allocation(owner, &alloc); + + pos_a[0] = alloc.y; + pos_a[1] = alloc.y; + + } + + owner = (*b)->other->owner; + + pos_b[0] = G_MAXINT; + pos_b[1] = 0; + + if (!g_graph_cluster_compute_min_max_bottom(owner, pos_b)) + { + g_graph_cluster_get_allocation(owner, &alloc); + + pos_b[0] = alloc.y; + pos_b[1] = alloc.y; + + } + + /* Comparaison */ + + if (pos_a[1] < pos_b[1]) + result = -1; + + else if (pos_a[1] > pos_b[1]) + result = 1; + + else + { + if (pos_a[0] < pos_b[0]) + result = -1; + + else if (pos_a[0] > pos_b[0]) + result = 1; + + else + result = 0; + + } + + if (*dir == LLD_TO_RIGHT) + result *= -1; + + return result; + +} diff --git a/src/gtkext/graph/leaving.h b/src/gtkext/graph/leaving.h index c91f232..b81e1ca 100644 --- a/src/gtkext/graph/leaving.h +++ b/src/gtkext/graph/leaving.h @@ -61,6 +61,21 @@ void delete_leaving_link(leaving_link_t *); /* Calcule l'abscisse d'un lien à son départ d'un bloc. */ gint compute_leaving_link_position(const leaving_link_t *); +/* Direction prise par le lien */ +typedef enum _LeavingLinkDir +{ + LLD_NO_PREF, /* Direction variable */ + LLD_TO_LEFT, /* Vers la gauche */ + LLD_TO_RIGHT, /* Vers la droite */ + +} LeavingLinkDir; + +/* Détermine une direction prise par un lien à son départ. */ +LeavingLinkDir get_leaving_link_direction(const leaving_link_t *); + +/* Compare deux liens sortants. */ +int cmp_leaving_links(const leaving_link_t **, const leaving_link_t **, const LeavingLinkDir *); + #endif /* _GTKEXT_GRAPH_LEAVING_H */ diff --git a/src/gtkext/graph/rank.c b/src/gtkext/graph/rank.c index 0fadb27..bffefe9 100644 --- a/src/gtkext/graph/rank.c +++ b/src/gtkext/graph/rank.c @@ -104,6 +104,28 @@ void exit_graph_rank(graph_rank_t *grank) * * * Paramètres : grank = ensemble de même rang à consulter. * * * +* Description : Parcours l'ensemble des blocs du rang avec un visiteur. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void visit_graph_rank(const graph_rank_t *grank, graph_rank_cb cb) +{ + size_t i; /* Boucle de parcours */ + + for (i = 0; i < grank->count; i++) + cb(grank->clusters[i]); + +} + + +/****************************************************************************** +* * +* Paramètres : grank = ensemble de même rang à consulter. * +* * * Description : Assigne à un ensemble de blocs un emplacement initial. * * * * Retour : - * @@ -494,24 +516,29 @@ void dispatch_x_graph_rank(const graph_rank_t *grank) /****************************************************************************** * * -* Paramètres : grank = ensemble de blocs de même rang à actualiser. * +* Paramètres : grank = ensemble de blocs de même rang à actualiser. * +* 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 un ensemble de blocs.* * * -* Retour : - * +* Retour : false si une incapacité de détermination a été rencontrée. * * * * Remarques : - * * * ******************************************************************************/ -void sort_graph_rank_incoming_links(graph_rank_t *grank) +bool get_graph_rank_exit_direction(graph_rank_t *grank, const GGraphCluster *root, LeavingLinkDir *dir) { + bool result; /* Bilan à renvoyer */ size_t i; /* Boucle de parcours */ - for (i = 0; i < grank->count; i++) - g_graph_cluster_sort_incoming_links(grank->clusters[i]); + result = true; - sort_incoming_links_for_vspace_manager(&grank->vspaces); + for (i = 0; i < grank->count && result; i++) + result = g_graph_cluster_get_exit_direction(grank->clusters[i], root, dir); + + return result; } @@ -519,8 +546,37 @@ void sort_graph_rank_incoming_links(graph_rank_t *grank) /****************************************************************************** * * * Paramètres : grank = ensemble de blocs de même rang à actualiser. * +* pos = ordonnées minimale et maximale en bout. [OUT] * +* * +* Description : Calcule les ordonnées extrèmes atteintes via liens sortants. * * * -* Description : Réordonne les blocs sortant d'un ensemble. * +* Retour : true si un lien sortant a été trouvé, false sinon. * +* * +* Remarques : - * +* * +******************************************************************************/ + +bool compute_graph_rank_min_max_bottom(const graph_rank_t *grank, gint pos[2]) +{ + bool result; /* Bilan à renvoyer */ + size_t i; /* Boucle de parcours */ + + result = false; + + for (i = 0; i < grank->count; i++) + result |= g_graph_cluster_compute_min_max_bottom(grank->clusters[i], pos); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : grank = ensemble de blocs de même rang à actualiser. * +* origin = cluster d'origine à considérer. * +* * +* Description : Réorganise au besoin les blocs selon les liens d'origine. * * * * Retour : - * * * @@ -528,64 +584,69 @@ void sort_graph_rank_incoming_links(graph_rank_t *grank) * * ******************************************************************************/ -void reorder_graph_rank_exit_blocks(graph_rank_t *grank) +void reorder_graph_rank_clusters(graph_rank_t *grank, const GGraphCluster *origin) { - GGraphCluster **exit_2_left; /* Liste avec sortie à gauche */ - GGraphCluster **exit_2_right; /* Liste avec sortie à droite */ - GGraphCluster **no_exit; /* Liste sans sortie */ - size_t count_2_left; /* Quantité de présents */ - size_t count_2_right; /* Quantité de présents */ - size_t count_no; /* Quantité de présents */ size_t i; /* Boucle de parcours */ - bool l2r; /* Détermination de catégorie */ + GGraphCluster **filtered; /* Blocs à réorganiser */ + size_t fcount; /* Nombre de ces blocs */ + size_t next; /* Prochain indice à réinsérer */ if (grank->count > 1) { - exit_2_left = malloc(grank->count * sizeof(GGraphCluster *)); - exit_2_right = malloc(grank->count * sizeof(GGraphCluster *)); - no_exit = malloc(grank->count * sizeof(GGraphCluster *)); + /** + * On prend garde de ne déplacer que les blocs avec un lien concernant + * un bloc d'origine, dont les liens au départ ont été réorganisés. + */ - count_2_left = 0; - count_2_right = 0; - count_no = 0; + filtered = malloc(grank->count * sizeof(GGraphCluster *)); + fcount = 0; for (i = 0; i < grank->count; i++) - { - if (g_graph_cluster_has_exit_link(grank->clusters[i], &l2r)) + if (g_graph_cluster_has_origin(grank->clusters[i], origin) != NULL) { - if (l2r) - exit_2_right[count_2_right++] = grank->clusters[i]; - else - exit_2_left[count_2_left++] = grank->clusters[i]; + filtered[fcount++] = grank->clusters[i]; + grank->clusters[i] = NULL; } - else - no_exit[count_no++] = grank->clusters[i]; - } + qsort_r(filtered, fcount, sizeof(GGraphCluster *), + (__compar_d_fn_t)g_graph_cluster_compare_by_origin, (void *)origin); - assert((count_2_left + count_2_right + count_no) == grank->count); + next = 0; - qsort_r(exit_2_left, count_2_left, sizeof(GGraphCluster *), - (__compar_d_fn_t)g_graph_cluster_compare_by_exit, (bool []){ false }); + for (i = 0; i < grank->count; i++) + if (grank->clusters[i] == NULL) + { + assert(next < fcount); + grank->clusters[i] = filtered[next++]; + } - qsort_r(exit_2_right, count_2_right, sizeof(GGraphCluster *), - (__compar_d_fn_t)g_graph_cluster_compare_by_exit, (bool []){ true }); + free(filtered); - grank->count = 0; + } - for (i = 0; i < count_2_left; i++) - grank->clusters[grank->count++] = exit_2_left[i]; +} - for (i = 0; i < count_no; i++) - grank->clusters[grank->count++] = no_exit[i]; - for (i = 0; i < count_2_right; i++) - grank->clusters[grank->count++] = exit_2_right[i]; +/****************************************************************************** +* * +* Paramètres : grank = ensemble de blocs de même rang à actualiser. * +* * +* Description : Réorganise au besoin les liens entrants un ensemble de blocs.* +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ - } +void sort_graph_rank_incoming_links(graph_rank_t *grank) +{ + size_t i; /* Boucle de parcours */ for (i = 0; i < grank->count; i++) - g_graph_cluster_reorder_exit_blocks(grank->clusters[i]); + g_graph_cluster_sort_incoming_links(grank->clusters[i]); + + sort_incoming_links_for_vspace_manager(&grank->vspaces); } diff --git a/src/gtkext/graph/rank.h b/src/gtkext/graph/rank.h index 1a149fc..e28b1f0 100644 --- a/src/gtkext/graph/rank.h +++ b/src/gtkext/graph/rank.h @@ -55,6 +55,12 @@ void init_graph_rank(graph_rank_t *, GGraphCluster *); /* Termine la gestion d'un ensemble de blocs de même rang. */ void exit_graph_rank(graph_rank_t *); +/* Visiteur pour blocs */ +typedef void (* graph_rank_cb) (GGraphCluster *); + +/* Parcours l'ensemble des blocs du rang avec un visiteur. */ +void visit_graph_rank(const graph_rank_t *grank, graph_rank_cb); + /* Assigne à un ensemble de blocs un emplacement initial. */ void reset_graph_rank_allocation(const graph_rank_t *); @@ -89,10 +95,16 @@ void _place_graph_rank_clusters(GGraphCluster **, size_t, gint, int); void dispatch_x_graph_rank(const graph_rank_t *); /* Réorganise au besoin les liens entrants un ensemble de blocs. */ -void sort_graph_rank_incoming_links(graph_rank_t *); +bool get_graph_rank_exit_direction(graph_rank_t *, const GGraphCluster *, LeavingLinkDir *); + +/* Calcule les ordonnées extrèmes atteintes via liens sortants. */ +bool compute_graph_rank_min_max_bottom(const graph_rank_t *, gint [2]); -/* Réordonne les blocs sortant d'un ensemble. */ -void reorder_graph_rank_exit_blocks(graph_rank_t *); +/* Réorganise au besoin les blocs selon les liens d'origine. */ +void reorder_graph_rank_clusters(graph_rank_t *, const GGraphCluster *); + +/* Réorganise au besoin les liens entrants un ensemble de blocs. */ +void sort_graph_rank_incoming_links(graph_rank_t *); /* Réordonne les blocs de départ de boucle d'un ensemble. */ void reorder_graph_rank_loop_blocks(graph_rank_t *); |