path: root/src/gtkext/graph/nodes/virtual.c

/* Chrysalide - Outil d'analyse de fichiers binaires
 * virtual.c - encapsulation graphique des blocs virtuels
 *
 * 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 "virtual.h"


#include <assert.h>
#include <malloc.h>
#include <sys/param.h>


#include "flow.h"
#include "../node-int.h"



/* ----------------------- MANIPULATION DES PORTES VERTICALES ----------------------- */


/* Etendue verticale d'un lien */
typedef struct _reserved_vspan
{
    unsigned int r1;                        /* Départ d'une ligne          */
    unsigned int r2;                        /* Arrivée de cette même ligne */

} reserved_vspan;

/* Lignes de liens verticales au sein d'un même groupe */
typedef struct _vert_links
{
    reserved_vspan *vspans;                 /* Lignes sans chevauchement   */
    size_t count;                           /* Nombre de ces lignes        */

} vert_links;


/* Initialise les futures portées d'un même niveau. */
static void init_vertical_links(vert_links *);

/* Regarde si des portées verticales se chevauchent ou non. */
static bool is_intersection_with_vertical_spans(const vert_links *, const reserved_vspan *);

/* Ajoute une réservation à un ensemble de portées verticales. */
static void extend_vertical_links_spans(vert_links *, const reserved_vspan *);



/* ---------------------- REPRESENTATIONS DES GROUPES LOGIQUES ---------------------- */


/* Représentation d'un étage */
typedef struct _virtual_level
{
    unsigned int rank;                      /* Rang associé à l'étage      */

    GGraphNode **children;                  /* Noeuds englobés             */
    size_t count;                           /* Quantité de ces noeuds      */

} virtual_level;

/* Encapsulation graphique d'un bloc virtuel (instance) */
struct _GVirtualNode
{
    GGraphNode parent;                      /* A laisser en premier        */

    GVirtualBlock *block;                   /* Bloc virtuel associé        */

    GGraphNode **children;                  /* Noeuds englobés             */
    size_t count;                           /* Quantité de ces noeuds      */
    virtual_level *levels;                  /* Différents étages de noeuds */
    size_t lcount;                          /* Nombre de ces étages        */

    vert_links *left_padding;               /* Espace à gauche pour liens  */
    vspan_slot_t left_count;                /* Nombre de largeurs réservées*/
    vert_links *right_padding;              /* Espace à droite pour liens  */
    vspan_slot_t right_count;               /* Nombre de largeurs réservées*/

};

/* Encapsulation graphique d'un bloc virtuel (classe) */
struct _GVirtualNodeClass
{
    GGraphNodeClass parent;                 /* A laisser en premier        */

};


/* Initialise la classe des encapsulations de blocs virtuels. */
static void g_virtual_node_class_init(GVirtualNodeClass *);

/* Initialise une encapsulation de bloc virtuel. */
static void g_virtual_node_init(GVirtualNode *);

/* Supprime toutes les références externes. */
static void g_virtual_node_dispose(GVirtualNode *);

/* Procède à la libération totale de la mémoire. */
static void g_virtual_node_finalize(GVirtualNode *);

/* Fournit le rang du noeud dans le graphique. */
static unsigned int g_virtual_node_get_rank(const GVirtualNode *);

/* Réinitialise la position d'un noeud d'encapsulation. */
static void g_virtual_node_reset_position(GVirtualNode *);

/* Définit les abscisses relatives du contenu d'un noeud. */
static void g_virtual_node_prepare_x_line(GVirtualNode *, GGraphNode *);

/* Applique une position finale au noeud. */
static void g_virtual_node_apply_position(GVirtualNode *);

/* Définit les abscisses relatives du contenu d'un noeud. */
static void g_virtual_node_apply_x_line(GVirtualNode *);

/* Met à jour la largeur interne du noeud. */
static void g_virtual_node_compute_width(GVirtualNode *);

/* Altère la position du noeud d'encapsulation. */
static void g_virtual_node_set_position(GVirtualNode *, gint);

/* Parcourt tous les blocs d'instructions dans un ordre donné. */
static bool g_virtual_node_visit_flow_nodes(GVirtualNode *, graph_node_visitor_cb, void *);

/* Recherche le noeud contenant un autre noeud. */
static GGraphNode *g_virtual_node_find_container(GVirtualNode *, GGraphNode *);



/* ---------------------------------------------------------------------------------- */
/*                         MANIPULATION DES PORTES VERTICALES                         */
/* ---------------------------------------------------------------------------------- */


/******************************************************************************
*                                                                             *
*  Paramètres  : links = liste à initialiser.                                 *
*                                                                             *
*  Description : Initialise les futures portées d'un même niveau.             *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void init_vertical_links(vert_links *links)
{
    links->vspans = NULL;
    links->count = 0;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : links = liste de portées déjà en place.                      *
*                vspan = nouvelle portée à insérer quelque part.              *
*                                                                             *
*  Description : Regarde si des portées verticales se chevauchent ou non.     *
*                                                                             *
*  Retour      : true si les portées peuvent cohabiter, false sinon.          *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static bool is_intersection_with_vertical_spans(const vert_links *links, const reserved_vspan *vspan)
{
    bool result;                            /* Bilan d'analyse à retourner */
    size_t i;                               /* Boucle de parcours          */

    result = false;

    for (i = 0; i < links->count && !result; i++)
    {
        if (vspan->r1 < links->vspans[i].r1)
            result = vspan->r2 >= links->vspans[i].r1;

        else if (vspan->r1 > links->vspans[i].r2)
            result = vspan->r2 <= links->vspans[i].r2;

        else
        {
            result = links->vspans[i].r1 < vspan->r1 && vspan->r1 < links->vspans[i].r2;
            result |= links->vspans[i].r1 < vspan->r2 && vspan->r2 < links->vspans[i].r2;
        }

    }

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : spans = liste de portées déjà en place.                      *
*                vspan = nouvelle portée à insérer quelque part.              *
*                                                                             *
*  Description : Ajoute une réservation à un ensemble de portées verticales.  *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void extend_vertical_links_spans(vert_links *links, const reserved_vspan *new)
{
    links->vspans = (reserved_vspan *)realloc(links->vspans,
                                              ++links->count * sizeof(reserved_vspan));

    if (new->r1 <= new->r2)
        links->vspans[links->count - 1] = *new;
    else
    {
        links->vspans[links->count - 1].r1 = new->r2;
        links->vspans[links->count - 1].r2 = new->r1;
    }

}



/* ---------------------------------------------------------------------------------- */
/*                        REPRESENTATIONS DES GROUPES LOGIQUES                        */
/* ---------------------------------------------------------------------------------- */


/* Indique le type définit par la GLib pour l'encapsulation d'un bloc virtuel. */
G_DEFINE_TYPE(GVirtualNode, g_virtual_node, G_TYPE_GRAPH_NODE);


/******************************************************************************
*                                                                             *
*  Paramètres  : klass = classe à initialiser.                                *
*                                                                             *
*  Description : Initialise la classe des encapsulations de blocs virtuels.   *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void g_virtual_node_class_init(GVirtualNodeClass *klass)
{
    GObjectClass *object;                   /* Autre version de la classe  */
    GGraphNodeClass *node_class;            /* Version parente de la classe*/

    object = G_OBJECT_CLASS(klass);
    node_class = G_GRAPH_NODE_CLASS(klass);

    object->dispose = (GObjectFinalizeFunc/* ! */)g_virtual_node_dispose;
    object->finalize = (GObjectFinalizeFunc)g_virtual_node_finalize;

    node_class->get_rank = (get_node_rank_fc)g_virtual_node_get_rank;
    node_class->reset_pos = (node_reset_pos_fc)g_virtual_node_reset_position;
    node_class->prepare_x = (node_prepare_x_fc)g_virtual_node_prepare_x_line;
    node_class->apply_pos = (node_apply_pos_fc)g_virtual_node_apply_position;
    node_class->set_pos = (node_set_pos_fc)g_virtual_node_set_position;
    node_class->visit = (visit_flow_nodes_fc)g_virtual_node_visit_flow_nodes;
    node_class->contain = (find_container_fc)g_virtual_node_find_container;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = instance à initialiser.                               *
*                                                                             *
*  Description : Initialise une encapsulation de bloc virtuel.                *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void g_virtual_node_init(GVirtualNode *node)
{

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = instance d'objet GLib à traiter.                      *
*                                                                             *
*  Description : Supprime toutes les références externes.                     *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void g_virtual_node_dispose(GVirtualNode *node)
{
    size_t i;                               /* Boucle de parcours          */

    g_object_unref(G_OBJECT(node->block));

    for (i = 0; i < node->count; i++)
        g_object_unref(G_OBJECT(node->children[i]));

    if (node->children != NULL)
        free(node->children);

    G_OBJECT_CLASS(g_virtual_node_parent_class)->dispose(G_OBJECT(node));

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = instance d'objet GLib à traiter.                      *
*                                                                             *
*  Description : Procède à la libération totale de la mémoire.                *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void g_virtual_node_finalize(GVirtualNode *node)
{
    G_OBJECT_CLASS(g_virtual_node_parent_class)->finalize(G_OBJECT(node));

}


/******************************************************************************
*                                                                             *
*  Paramètres  : block = bloc virtuel représenté graphiquement.               *
*                                                                             *
*  Description : Encapsule graphiquement un bloc virtuel.                     *
*                                                                             *
*  Retour      : Adresse de la structure mise en place.                       *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

GGraphNode *g_virtual_node_new(GVirtualBlock *block)
{
    GVirtualNode *result;                   /* Structure à retourner       */

    result = g_object_new(G_TYPE_VIRTUAL_NODE, NULL);

    g_object_ref(G_OBJECT(block));

    result->block = block;

    return G_GRAPH_NODE(result);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = noeud graphique à consulter.                          *
*                                                                             *
*  Description : Fournit le rang du noeud dans le graphique.                  *
*                                                                             *
*  Retour      : Indice supérieur ou égal à zéro.                             *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static unsigned int g_virtual_node_get_rank(const GVirtualNode *node)
{
    /* BUG_ON(node->count == 0) */

    return g_graph_node_get_rank(node->children[0]);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = noeud graphique à manipuler.                          *
*                                                                             *
*  Description : Réinitialise la position d'un noeud d'encapsulation.         *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void g_virtual_node_reset_position(GVirtualNode *node)
{
    size_t i;                               /* Boucle de parcours          */

    for (i = 0; i < node->count; i++)
        g_graph_node_reset_position(node->children[i]);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node  = noeud d'encapsulation à traiter.                     *
*                nodes = ensemble des noeuds en place.                        *
*                                                                             *
*  Description : Définit les abscisses relatives du contenu d'un noeud.       *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void g_virtual_node_prepare_x_line(GVirtualNode *node, GGraphNode *nodes)
{
    size_t i;                               /* Boucle de parcours          */

    for (i = 0; i < node->count; i++)
        g_graph_node_prepare_x_line(node->children[i], nodes);

}



/******************************************************************************
*                                                                             *
*  Paramètres  : node  = noeud d'encapsulation à traiter.                     *
*                                                                             *
*  Description : Applique une position finale au noeud.                       *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void g_virtual_node_apply_position(GVirtualNode *node)
{
    gint min;                               /* Valeur minimale rencontrée  */
    size_t i;                               /* Boucle de parcours          */
    gint x_pos;                             /* Nouvelle position #1        */
    gint offset;                            /* Décallage à faire suivre    */

    g_virtual_node_apply_x_line(node);

    /* Collecte de l'ensemble des positions */

    min = 0;

    for (i = 0; i < node->count; i++)
    {
        g_graph_node_get_position(node->children[i], &x_pos, NULL);
        min = MIN(min, x_pos);
    }

    /* Espace pour les liens remontants */

    if (node->left_count > 0)
        offset = EDGE_SLOT_HORIZ_MARGIN + EDGE_HORIZONTAL_MIN_SEP * (node->left_count - 1);
    else
        offset = 0;

    /* Ajout du décallage le plus grand */

    offset += -min;

    /* Traitement des sous-noeuds */

    for (i = 0; i < node->count; i++)
    {
        /* BUG_ON(node->children[i]->alloc.x != UNINITIALIZED_NODE_POS); */

        g_graph_node_get_position(node->children[i], &x_pos, NULL);

        printf(" == vapply ==  %p : %d + %d -> %d\n",
               node->children[i], x_pos, offset, (int)(x_pos + offset));

        x_pos += offset;

        g_graph_node_set_x_position(node->children[i], x_pos);

    }

    g_virtual_node_compute_width(node);

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = noeud d'encapsulation à traiter.                      *
*                                                                             *
*  Description : Définit les abscisses relatives du contenu d'un noeud.       *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void g_virtual_node_apply_x_line(GVirtualNode *node)
{
    size_t i;                               /* Boucle de parcours #1       */
    virtual_level *level;                   /* Accès rapide                */
    size_t j;                               /* Boucle de parcours #2       */
    gint width_sum;                         /* Largeur d'un étage traité   */
    gint x_pos;                             /* Abscisse à attribuer        */

    for (i = 0; i < node->lcount; i++)
    {
        level = &node->levels[i];

        /* Si l'ensemble de l'étage doit être centré */
        if (level->children[0]->pending_flag == PPF_NONE)
        {
            width_sum = 0;

            for (j = 0; j < level->count; j++)
            {
                assert(level->children[j]->pending_flag == PPF_NONE);

                g_graph_node_apply_position(level->children[j]);
                width_sum += level->children[j]->alloc.width;

            }

            width_sum += NODE_HORIZONTAL_MARGIN * (level->count - 1);

            x_pos = - width_sum / 2;

            for (j = 0; j < level->count; j++)
            {
                g_graph_node_set_x_position(level->children[j], x_pos);
                x_pos += level->children[j]->alloc.width + NODE_HORIZONTAL_MARGIN;
            }

        }

        /* On traite les noeuds individuellement */
        else
        {
            void _apply_rel_position(GGraphNode *child)
            {
                switch (node->children[0]->pending_flag)
                {
                    case PPF_LEFT_NODE:
                        if (!g_graph_node_has_x_position(child->pending_pos.left_node))
                            _apply_rel_position(child->pending_pos.left_node);
                        break;

                    case PPF_RIGHT_NODE:
                        if (!g_graph_node_has_x_position(child->pending_pos.right_node))
                            _apply_rel_position(child->pending_pos.right_node);
                        break;

                    default:
                        break;

                }

                g_graph_node_apply_position(child);

            }

            for (j = 0; j < level->count; j++)
                if (!g_graph_node_has_x_position(level->children[j]))
                    _apply_rel_position(level->children[j]);

        }

    }

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = noeud graphique à mettre à jour.                      *
*                                                                             *
*  Description : Met à jour la largeur interne du noeud.                      *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void g_virtual_node_compute_width(GVirtualNode *node)
{
    GGraphNode *base;                       /* Accès rapides               */
    size_t i;                               /* Boucle de parcours          */
    GGraphNode *child;                      /* Raccourci confortable       */

    base = G_GRAPH_NODE(node);

    /* Largeur maximale des niveaux */

    base->alloc.width = 0;

    for (i = 0; i < node->lcount; i++)
    {
        child = node->levels[i].children[node->levels[i].count - 1];

        base->alloc.width = MAX(base->alloc.width, child->alloc.x + child->alloc.width);

    }

    /* Bordures gauche et droite   */

    if (node->left_count > 0)
    {
        base->alloc.width += EDGE_SLOT_HORIZ_MARGIN;
        base->alloc.width += (node->left_count - 1) * EDGE_HORIZONTAL_MIN_SEP;
    }

    if (node->right_count > 0)
    {
        base->alloc.width += EDGE_SLOT_HORIZ_MARGIN;
        base->alloc.width += (node->right_count - 1) * EDGE_HORIZONTAL_MIN_SEP;
    }

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = noeud graphique à manipuler.                          *
*                x    = éventuelle abscisse à intégrer.                       *
*                                                                             *
*  Description : Altère la position du noeud d'encapsulation.                 *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static void g_virtual_node_set_position(GVirtualNode *node, gint x)
{
    GGraphNode *base;                       /* Autre version de l'instance */
    gint offset;                            /* Décallage à faire suivre    */
    size_t i;                               /* Boucle de parcours          */
    gint x_pos;                             /* Nouvelle position #1        */

    base = G_GRAPH_NODE(node);

    if (base->alloc.x == UNINITIALIZED_NODE_POS)
        offset = x;
    else
        offset = x - base->alloc.x;

    for (i = 0; i < node->count; i++)
    {
        /* BUG_ON(node->children[i]->alloc.x != UNINITIALIZED_NODE_POS); */

        g_graph_node_get_position(node->children[i], &x_pos, NULL);
        x_pos += offset;

        g_graph_node_set_x_position(node->children[i], x_pos);

    }

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node     = noeud graphique démarrant la visite.              *
*                callback = ensemble de blocs à parcourir.                    *
*                data     = donnée utilisateur à associer au parcours.        *
*                                                                             *
*  Description : Parcourt tous les blocs d'instructions dans un ordre donné.  *
*                                                                             *
*  Retour      : true si le parcours a été jusqu'à son terme, false sinon.    *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static bool g_virtual_node_visit_flow_nodes(GVirtualNode *node, graph_node_visitor_cb callback, void *data)
{
    bool result;                            /* Bilan à retourner           */
    size_t i;                               /* Boucle de parcours          */

    result = callback(G_GRAPH_NODE(node), GVS_ENTER, data);

    for (i = 0; i < node->count && result; i++)
        result = g_graph_node_visit_nodes(node->children[i], callback, data);

    if (result)
        result = callback(G_GRAPH_NODE(node), GVS_EXIT, data);

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : nodes  = noeud à consulter.                                  *
*                target = élément à retrouver dans l'ensemble de noeuds.      *
*                                                                             *
*  Description : Recherche le noeud contenant un autre noeud.                 *
*                                                                             *
*  Retour      : Noeud trouvé ou NULL si aucun.                               *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

static GGraphNode *g_virtual_node_find_container(GVirtualNode *node, GGraphNode *target)
{
    GGraphNode *result;                     /* Trouvaille à retourner      */
    size_t i;                               /* Boucle de parcours          */

    result = NULL;

    for (i = 0; i < node->count && result == NULL; i++)
    {
        if (node->children[i] == target)
            result = G_GRAPH_NODE(node);
        else
            result = g_graph_node_find_container(node->children[i], target);
    }

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node  = noeud d'encapsulation à compléter.                   *
*                child = sous-noeud à insérer.                                *
*                                                                             *
*  Description : Ajoute un noeud au groupe courant.                           *
*                                                                             *
*  Retour      : -                                                            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void g_virtual_node_add_child(GVirtualNode *node, GGraphNode *child)
{
    unsigned int rank;                      /* Rang de l'enfant            */
    virtual_level *level;                   /* Niveau d'intégration        */
    size_t i;                               /* Boucle de parcours          */

    /* Liste globale */

    node->children = (GGraphNode **)realloc(node->children,
                                              ++node->count * sizeof(GGraphNode *));

    node->children[node->count - 1] = child;

    g_object_ref(G_OBJECT(child));

    /* Intégration dans l'étage correspondant */

    rank = g_graph_node_get_rank(child);

    level = NULL;

    for (i = 0; i < node->lcount && level == NULL; i++)
        if (node->levels[i].rank == rank)
            level = &node->levels[i];

    if (level == NULL)
    {
        node->levels = (virtual_level *)realloc(node->levels,
                                                ++node->lcount * sizeof(virtual_level));
        level = &node->levels[node->lcount - 1];

        level->rank = rank;
        level->children = NULL;
        level->count = 0;

    }

    level->children = (GGraphNode **)realloc(level->children,
                                             ++level->count * sizeof(GGraphNode *));

    level->children[level->count - 1] = child;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node  = noeud d'encapsulation à consulter.                   *
*                                                                             *
*  Description : Compte le nombre de noeuds contenus dans le groupe courant.  *
*                                                                             *
*  Retour      : Quantité normalement non nulle.                              *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

size_t g_virtual_node_count_children(const GVirtualNode *node)
{
    return node->count;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node  = noeud d'encapsulation à consulter.                   *
*                index = indice du sous-bloc recherché.                       *
*                                                                             *
*  Description : Renvoie un des noeuds contenus dans le groupe courant.       *
*                                                                             *
*  Retour      : Un des blocs du groupe.                                      *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

GGraphNode *g_virtual_node_get_child(const GVirtualNode *node, size_t index)
{
    if (index >= node->count)
        return NULL;

    else
        return node->children[index];

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = groupe de noeuds à mettre à jour.                     *
*                r1   = début de la portée à réserver.                        *
*                r2   = fin de la portée à réserver.                          *
*                left = désignation de la zone à traiter.                     *
*                                                                             *
*  Description : Réserve une portion de largeur pour un lien.                 *
*                                                                             *
*  Retour      : Indice de la largeur adaptée et réservée.                    *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

vspan_slot_t g_virtual_node_reserve_span(GVirtualNode *node, unsigned int r1, unsigned int r2, bool left)
{
    vspan_slot_t result;                    /* Identifiant à retourner     */
    reserved_vspan vspan;                   /* Portée à constituer         */
    vert_links **list;                      /* Liste à parcourir           */
    vspan_slot_t *count;                    /* Taille de cette liste       */

    vspan.r1 = r1;
    vspan.r2 = r2;

    if (left)
    {
        list = &node->left_padding;
        count = &node->left_count;
    }
    else
    {
        list = &node->right_padding;
        count = &node->right_count;
    }

    for (result = 0; result < *count; result++)
        if (!is_intersection_with_vertical_spans(&(*list)[result], &vspan))
            break;

    if (result == *count)
    {
        *list = (vert_links *)realloc(*list, ++(*count) * sizeof(vert_links));
        init_vertical_links(&(*list)[result]);
    }

    extend_vertical_links_spans(&(*list)[result], &vspan);

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : node = conteneur de noeuds à consulter.                      *
*                slot = numérod de la réservation.                            *
*                left = désignation de la zone à traiter.                     *
*                                                                             *
*  Description : Fournit la position horizontale obtenue par réservation.     *
*                                                                             *
*  Retour      : Abscisse à utiliser.                                         *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

gint g_virtual_node_get_x_for_vspan_slot(const GVirtualNode *node, vspan_slot_t slot, bool left)
{
    gint result;                            /* Position à retourner        */
    GtkAllocation alloc;                    /* Taille totale requise       */

    alloc = G_GRAPH_NODE(node)->alloc;

    if (left)
    {
        /*BUG_ON(slot >= node->left_count) */

        result = -(node->left_count - 1) * EDGE_HORIZONTAL_MIN_SEP/* + EDGE_SLOT_HORIZ_MARGIN*/;
        result += (slot * EDGE_HORIZONTAL_MIN_SEP/* + EDGE_SLOT_HORIZ_MARGIN*/);

        result += alloc.x;

    }
    else
    {
        /*BUG_ON(slot >= node->right_count) */

        result = /*EDGE_SLOT_HORIZ_MARGIN + */slot * EDGE_HORIZONTAL_MIN_SEP;

        result += alloc.x + alloc.width/* - EDGE_SLOT_HORIZ_MARGIN*/;
        if (node->right_count > 0)
            result -= (node->right_count - 1) * EDGE_HORIZONTAL_MIN_SEP;

        /* On pense à la largeur du trait... */
        result -= 2;

    }

    return result;

}