/* Chrysalide - Outil d'analyse de fichiers binaires
* ranks.c - calcul de l'ordonnée des différents classements
*
* Copyright (C) 2013 Cyrille Bagard
*
* This file is part of Chrysalide.
*
* OpenIDA is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 3 of the License, or
* (at your option) any later version.
*
* OpenIDA is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Foobar. If not, see <http://www.gnu.org/licenses/>.
*/
#include "ranks.h"
#include <malloc.h>
#include <sys/param.h>
#include "params.h"
/* ---------------------- MANIPULATION DES PORTES HORIZONTALES ---------------------- */
/* Etendue horizontale d'un lien */
typedef struct _reserved_hspan
{
gint x1; /* Départ d'une ligne */
gint x2; /* Arrivée de cette même ligne */
} reserved_hspan;
/* Lignes de liens d'un même niveau */
typedef struct _links_spans
{
reserved_hspan *hspans; /* Lignes sans chevauchement */
size_t count; /* Nombre de ces lignes */
} links_spans;
/* Initialise les futures portées d'un même niveau. */
static void init_links_spans(links_spans *);
/* Regarde si des portées horizontales se chevauchent ou non. */
static bool is_intersection_with_spans(const links_spans *, const reserved_hspan *);
/* Ajoute une réservation à un ensemble de portées horizontales. */
static void extend_links_spans(links_spans *, const reserved_hspan *);
/* ------------------------ GESTION D'UN ETAGE DE CLASSEMENT ------------------------ */
/* Information relatives à un rang de classement */
typedef struct _rank_props
{
links_spans *top_spans; /* Niveaux de lignes supérieurs*/
hspan_slot_t top_count; /* Nbre des niveaux de lignes */
links_spans *bottom_spans; /* Niveaux de lignes inférieurs*/
hspan_slot_t bottom_count; /* Nbre des niveaux de lignes */
gint height; /* Hauteur minimale */
gint y; /* Ordonnée finale */
} rank_props;
/* Réserve une portion de hauteur pour un lien. */
static hspan_slot_t reserve_span_in_rank_props(rank_props *, gint, gint, bool);
/* Calcule la position verticale du rang de classement. */
static gint compute_rank_props_y_pos(rank_props *, gint *, gint);
/* Fournit la position verticale obtenue par réservation. */
static gint get_y_for_rank_props_hspan_slot(const rank_props *, hspan_slot_t, bool);
/* ------------------------- CLASSEMENT VERTICAL DES NOEUDS ------------------------- */
/* Calcul de l'ordonnée des différents classements (instance) */
struct _GGraphRanks
{
GObject parent; /* A laisser en premier */
rank_props *props; /* Propriétés des rangs */
unsigned int count; /* Nombre de rangs présents */
gint height; /* Hauteur totale du graphique */
};
/* Calcul de l'ordonnée des différents classements (classe) */
struct _GGraphRanksClass
{
GObjectClass parent; /* A laisser en premier */
};
/* Initialise la classe de calcul de l'ordonnée des classements. */
static void g_graph_ranks_class_init(GGraphRanksClass *);
/* Initialise un calcul de l'ordonnée des classements. */
static void g_graph_ranks_init(GGraphRanks *);
/* Supprime toutes les références externes. */
static void g_graph_ranks_dispose(GGraphRanks *);
/* Procède à la libération totale de la mémoire. */
static void g_graph_ranks_finalize(GGraphRanks *);
/* ---------------------------------------------------------------------------------- */
/* MANIPULATION DES PORTES HORIZONTALES */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : spans = liste à initialiser. *
* *
* Description : Initialise les futures portées d'un même niveau. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void init_links_spans(links_spans *spans)
{
spans->hspans = NULL;
spans->count = 0;
}
/******************************************************************************
* *
* Paramètres : spans = liste de portées déjà en place. *
* hspan = nouvelle portée à insérer quelque part. *
* *
* Description : Regarde si des portées horizontales se chevauchent ou non. *
* *
* Retour : true si les portées peuvent cohabiter, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool is_intersection_with_spans(const links_spans *spans, const reserved_hspan *hspan)
{
bool result; /* Bilan d'analyse à retourner */
size_t i; /* Boucle de parcours */
result = false;
for (i = 0; i < spans->count && !result; i++)
{
if (hspan->x1 < spans->hspans[i].x1)
result = hspan->x2 >= spans->hspans[i].x1;
else if (hspan->x1 > spans->hspans[i].x2)
result = hspan->x2 <= spans->hspans[i].x2;
else
{
result = spans->hspans[i].x1 < hspan->x1 && hspan->x1 < spans->hspans[i].x2;
result |= spans->hspans[i].x1 < hspan->x2 && hspan->x2 < spans->hspans[i].x2;
}
}
return result;
}
/******************************************************************************
* *
* Paramètres : spans = liste de portées déjà en place. *
* hspan = nouvelle portée à insérer quelque part. *
* *
* Description : Ajoute une réservation à un ensemble de portées horizontales.*
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void extend_links_spans(links_spans *spans, const reserved_hspan *new)
{
spans->hspans = (reserved_hspan *)realloc(spans->hspans,
++spans->count * sizeof(reserved_hspan));
if (new->x1 <= new->x2)
spans->hspans[spans->count - 1] = *new;
else
{
spans->hspans[spans->count - 1].x1 = new->x2;
spans->hspans[spans->count - 1].x2 = new->x1;
}
}
/* ---------------------------------------------------------------------------------- */
/* GESTION D'UN ETAGE DE CLASSEMENT */
/* ---------------------------------------------------------------------------------- */
/******************************************************************************
* *
* Paramètres : props = propriétés de rang à mettre à jour. *
* *
* Description : Supprime les portions de hauteur pour un lien. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void reset_spans_in_rank_props(rank_props *props)
{
hspan_slot_t i; /* Boucle de parcours */
for (i = 0; i < props->top_count; i++)
if (props->top_spans[i].hspans != NULL)
free(props->top_spans[i].hspans);
if (props->top_spans != NULL)
{
free(props->top_spans);
props->top_spans = NULL;
props->top_count = 0;
}
for (i = 0; i < props->bottom_count; i++)
if (props->bottom_spans[i].hspans != NULL)
free(props->bottom_spans[i].hspans);
if (props->bottom_spans != NULL)
{
free(props->bottom_spans);
props->bottom_spans = NULL;
props->bottom_count = 0;
}
props->y = 0;
props->height = 0;
}
/******************************************************************************
* *
* Paramètres : props = propriétés de rang à mettre à jour. *
* x1 = début de la portée à réserver. *
* x2 = fin de la portée à réserver. *
* top = désignation de la zone à traiter. *
* *
* Description : Réserve une portion de hauteur pour un lien. *
* *
* Retour : Indice de la hauteur adaptée et réservée. *
* *
* Remarques : - *
* *
******************************************************************************/
static hspan_slot_t reserve_span_in_rank_props(rank_props *props, gint x1, gint x2, bool top)
{
hspan_slot_t result; /* Indice à retourner */
reserved_hspan hspan; /* Portée à constituer */
links_spans **list; /* Liste à parcourir */
hspan_slot_t *count; /* Taille de cette liste */
hspan.x1 = x1;
hspan.x2 = x2;
if (top)
{
list = &props->top_spans;
count = &props->top_count;
}
else
{
list = &props->bottom_spans;
count = &props->bottom_count;
}
for (result = 0; result < *count; result++)
if (!is_intersection_with_spans(&(*list)[result], &hspan))
break;
if (result == *count)
{
*list = (links_spans *)realloc(*list, ++(*count) * sizeof(links_spans));
init_links_spans(&(*list)[result]);
}
extend_links_spans(&(*list)[result], &hspan);
return result;
}
/******************************************************************************
* *
* Paramètres : props = propriétés de rang à mettre à jour. *
* y = ordonnée courante à faire évoluer. *
* last_bottom = espace inférieur requis du niveau précédent. *
* *
* Description : Calcule la position verticale du rang de classement. *
* *
* Retour : Espace inférieur nécessaire au niveau de classement. *
* *
* Remarques : - *
* *
******************************************************************************/
static gint compute_rank_props_y_pos(rank_props *props, gint *y, gint last_bottom)
{
gint result; /* Espace Sud à retourner */
gint top_margin; /* Espace Nord nécessaire */
/* Espace supérieur pour les liens */
top_margin = last_bottom;
if (props->top_count > 0)
{
top_margin += props->top_count * EDGE_VERTICAL_MIN_SEP;
top_margin += EDGE_SLOT_VERT_MARGIN;
}
/**
* L'espace vertical entre les noeuds n'a lieu d'être qu'en présence de noeuds !
*/
top_margin = MAX(top_margin, (*y > 0 && props->height > 0 ? NODE_VERTICAL_MARGIN : 0));
/* Position des noeuds */
props->y = *y + top_margin;
*y = props->y + props->height;
/* Espace inférieur pour les liens */
/**
* Fournit une marge minimum : si des liens autres que boucles partent de ce rang,
* il ne sont pas enregistrés à ce niveau, mais ont besoin d'espace quand même.
* On prend néanmoins garde aux rangs terminaux, potentiellement vides.
*/
result = (props->height > 0 ? EDGE_SLOT_VERT_MARGIN : 0);
if (props->bottom_count > 0)
result += props->bottom_count * EDGE_VERTICAL_MIN_SEP;
return result;
}
/******************************************************************************
* *
* Paramètres : props = propriétés de rang à consulter. *
* slot = numérod de la réservation. *
* top = désignation de la zone à traiter. *
* *
* Description : Fournit la position verticale obtenue par réservation. *
* *
* Retour : Ordonnée à utiliser. *
* *
* Remarques : - *
* *
******************************************************************************/
static gint get_y_for_rank_props_hspan_slot(const rank_props *props, hspan_slot_t slot, bool top)
{
gint result; /* Ordonnée à retourner */
result = EDGE_SLOT_VERT_MARGIN + slot * EDGE_VERTICAL_MIN_SEP;
if (top)
result = props->y - result;
else
result += props->y + props->height;
return result;
}
/* ---------------------------------------------------------------------------------- */
/* CLASSEMENT VERTICAL DES NOEUDS */
/* ---------------------------------------------------------------------------------- */
/* Indique le type définit par la GLib pour le calcul de l'ordonnée des classements. */
G_DEFINE_TYPE(GGraphRanks, g_graph_ranks, G_TYPE_OBJECT);
/******************************************************************************
* *
* Paramètres : klass = classe à initialiser. *
* *
* Description : Initialise la classe de calcul de l'ordonnée des classements.*
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_ranks_class_init(GGraphRanksClass *klass)
{
GObjectClass *object; /* Autre version de la classe */
object = G_OBJECT_CLASS(klass);
object->dispose = (GObjectFinalizeFunc/* ! */)g_graph_ranks_dispose;
object->finalize = (GObjectFinalizeFunc)g_graph_ranks_finalize;
}
/******************************************************************************
* *
* Paramètres : ranks = instance à initialiser. *
* *
* Description : Initialise un calcul de l'ordonnée des classements. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_ranks_init(GGraphRanks *ranks)
{
}
/******************************************************************************
* *
* Paramètres : node = instance d'objet GLib à traiter. *
* *
* Description : Supprime toutes les références externes. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_ranks_dispose(GGraphRanks *ranks)
{
G_OBJECT_CLASS(g_graph_ranks_parent_class)->dispose(G_OBJECT(ranks));
}
/******************************************************************************
* *
* Paramètres : ranks = instance d'objet GLib à traiter. *
* *
* Description : Procède à la libération totale de la mémoire. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_graph_ranks_finalize(GGraphRanks *ranks)
{
if (ranks->props != NULL)
free(ranks->props);
G_OBJECT_CLASS(g_graph_ranks_parent_class)->finalize(G_OBJECT(ranks));
}
/******************************************************************************
* *
* Paramètres : count = nombre de rangs dans le classement au total. *
* *
* Description : Prépare de quoi se définir au mieux les ordonnées des noeuds.*
* *
* Retour : Adresse de la structure mise en place. *
* *
* Remarques : - *
* *
******************************************************************************/
GGraphRanks *g_graph_ranks_new(unsigned int count)
{
GGraphRanks *result; /* Structure à retourner */
result = g_object_new(G_TYPE_GRAPH_RANKS, NULL);
result->count = count;
result->props = (rank_props *)calloc(count, sizeof(rank_props));
return result;
}
/******************************************************************************
* *
* Paramètres : ranks = ensemble des rangs de classement à manipuler. *
* index = indice du rang visé. *
* height = hauteur minimale requise pour le rang donné. *
* *
* Description : Note une hauteur minimale requise pour un rang du classement.*
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_ranks_set_min_height(GGraphRanks *ranks, unsigned int index, gint height)
{
/*BUG_ON(index >= ranks->count) */
ranks->props[index].height = MAX(ranks->props[index].height, height);
}
/******************************************************************************
* *
* Paramètres : ranks = ensemble des rangs de classement à consulter. *
* *
* Description : Fournit la hauteur requise pour l'affichage des rangs. *
* *
* Retour : Hauteur nécessaire en pixel. *
* *
* Remarques : - *
* *
******************************************************************************/
gint g_graph_ranks_get_height(const GGraphRanks *ranks)
{
return ranks->height;
}
/******************************************************************************
* *
* Paramètres : ranks = ensemble des rangs à mettre à jour. *
* *
* Description : Supprime toutes les réservations faites pour les liens. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_ranks_reset_reservations(GGraphRanks *ranks)
{
unsigned int i; /* Boucle de parcours */
for (i = 0; i < ranks->count; i++)
reset_spans_in_rank_props(&ranks->props[i]);
}
/******************************************************************************
* *
* Paramètres : ranks = ensemble des rangs à mettre à jour. *
* index = indice du rang visé. *
* x1 = début de la portée à réserver. *
* x2 = fin de la portée à réserver. *
* top = désignation de la zone à traiter. *
* *
* Description : Réserve une portion de hauteur pour un lien. *
* *
* Retour : Indice de la hauteur adaptée et réservée. *
* *
* Remarques : - *
* *
******************************************************************************/
hspan_slot_t g_graph_ranks_reserve_span(GGraphRanks *ranks, unsigned int index, gint x1, gint x2, bool top)
{
/*BUG_ON(index >= ranks->count) */
return reserve_span_in_rank_props(&ranks->props[index], x1, x2, top);
}
/******************************************************************************
* *
* Paramètres : ranks = ensemble des rangs de classement à manipuler. *
* *
* Description : Calcule l'ordonnée finale de chaque rang du classement. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_graph_ranks_compute_y_line(GGraphRanks *ranks)
{
gint last_bottom; /* Espace minimal à transmettre*/
gint y; /* Ordonnée courante à proposer*/
size_t i; /* Boucle de parcours */
last_bottom = GRAPH_VERTICAL_MARGIN;
y = 0;
for (i = 0; i < ranks->count; i++)
last_bottom = compute_rank_props_y_pos(&ranks->props[i], &y, last_bottom);
ranks->height = y + last_bottom + GRAPH_VERTICAL_MARGIN;
}
/******************************************************************************
* *
* Paramètres : ranks = ensemble des rangs de classement à consulter. *
* index = indice du rang visé. *
* *
* Description : Fournit la position verticale correspondant à un rang donné. *
* *
* Retour : Ordonnée à utiliser. *
* *
* Remarques : - *
* *
******************************************************************************/
gint g_graph_ranks_get_y_for_rank(const GGraphRanks *ranks, unsigned int index)
{
/*BUG_ON(index >= ranks->count) */
return ranks->props[index].y;
}
/******************************************************************************
* *
* Paramètres : ranks = ensemble des rangs de classement à consulter. *
* index = indice du rang visé. *
* slot = numérod de la réservation. *
* top = désignation de la zone à traiter. *
* *
* Description : Fournit la position verticale obtenue par réservation. *
* *
* Retour : Ordonnée à utiliser. *
* *
* Remarques : - *
* *
******************************************************************************/
gint g_graph_ranks_get_y_for_hspan_slot(const GGraphRanks *ranks, unsigned int index, hspan_slot_t slot, bool top)
{
/*BUG_ON(index >= ranks->count) */
return get_y_for_rank_props_hspan_slot(&ranks->props[index], slot, top);
}