Exercice donné en test le 06/04/2007

Remarque préliminaire :

cet exercice utilise les résultats de l’exercice BAL multi-producteurs/multi-consommateurs.

Il ne peut donc être effectué qu’après ce dernier.

Il est assez facile d’écrire un itérateur sur un conteneur “linéaire” comme un vector ou une liste chaînée par exemple.

Il suffit en effet de mémoriser dans cet itérateur un pointeur sur l’élément courant.

Le passage à l’élément suivant est obtenu en incrémentant ce pointeur d’une unité pour un vector, ou en appelant la fonction GetSuivant() de l’élément courant de la liste.

C’est beaucoup plus délicat de proposer un itérateur sur un arbre.

En effet, il ne suffit pas de garder un pointeur sur un nœud de l’arbre pour pouvoir passer au suivant : il faut aussi garder tout le chemin parcouru depuis la racine, afin de pouvoir éventuellement remonter dans l’arbre pour en explorer une nouvelle branche, ou de revenir au cœur des appels récursifs pour continuer le parcours, ce qui est totalement impossible.

Les threads offrent une alternative très élégante à ce problème.

Le principe

Un thread parcourt récursivement tous les nœuds de l’arbre (parcours infixé par exemple).

Le traitement du nœud courant consiste à déposer un pointeur sur ce nœud dans une BAL qui, par définition, est bloquante tant que l’information n’a pas été retirée par un consommateur.

Lorsque l’arbre est entièrement parcouru, le thread dépose un pointeur nul dans la BAL.

Un second thread retire successivement de la BAL chaque nœud, qu’il traite, jusqu’à trouver un pointeur de nœud invalide.

L’existant

Pour simplifier, nous travaillerons sur un arbre de recherche d’entiers, déclaré ainsi :

    class CNode;
    typedef CNode * PNode_t;

    class CNode
    {
        int     m_Val;
        PNode_t m_fg;
        PNode_t m_fd;

      public :
        PNode_t GetGauche (void)       const { return m_fg; }
        PNode_t GetDroit  (void)       const { return m_fd; }
        void    SetGauche (PNode_t fg)       { m_fg = fg;   }
        void    SetDroit  (PNode_t fd)       { m_fd = fd;   }

        CNode (int Val, PNode_t fg = 0, PNode_t fd = 0)
            : m_Val (Val), m_fg (fg), m_fd (fd) {}

        int GetVal (void) const { return m_Val; }

    }; // CNode

La classe CSearchTree encapsule la structure arborescente :

    class CSearchTree
    {
        PNode_t m_Racine;

        PNode_t AddNode (int Val, PNode_t Racine);

      public :
        CSearchTree (void) : m_Racine (0) {}
        void AddNode (int Val);

    }; // CSearchTree

La fonction publique non récursive AddNode() appelle la fonction privée récursive AddNode() qui ajoute dans l’arbre la valeur passée en paramètre.

De plus, nous disposons de la classe générique C_BALGen suivante :

    template <typename T>
    class C_BALGen
    {
        // ...
      public :
         C_BALGen (void);
        ~C_BALGen (void);

        void Deposer (const T & Val);
        T    Retirer (void);

    }; // C_BALGen

Classe CIterTree

L’interface (partie visible) de la classe CIterTree est la suivante :

    class CIterTree
    {
        // ...

      public :
        CIterTree (CSearchTree & Arbre);

        PNode_t GetNext (void);

    }; // CIterTree

Un itérateur CIterTree comporte aussi (données membres):

• une BAL qui servira à communiquer les pointeurs des différents noeuds rencontrés,

• une association à l’arbre qu’il doit parcourir (reçu à la construction).

L’utilisateur n’a plus qu’à appeler la fonction GetNext() pour obtenir un pointeur vers le nœud courant (avec passage au nœud suivant).

La fonction GetNext() renvoie un pointeur nul lorsque tout l’arbre a été exploré.

Voici un exemple d’utilisation par un thread utilisateur :

void ThreadUser (void)
{
    // ...
    CSearchTree Arbre;

    // Remplissage de l'arbre

    CIterTree Iter (Arbre);

    for (PNode_t Ptr; (Ptr = Iter.GetNext()); )
    {
        cout << "Valeur lue : " << Ptr->GetVal() << '\n';
        this_thread::sleep (seconds (1));
    }
    // ...

} // ThreadUser()

La classe CIterTree a deux fonctions membres privées :

void Parcours (PNode_t Racine);
void Parcours ();

La première, récursive, parcourt dans l’ordre infixé l’arbre à partir du nœud qui lui est passé en paramètre.

Rappel d’un parcours d’arbre :

void Parcours (PNode_t Node)
{
    if (!Node) return;

    // Traitement préfixé de *Node

    Parcours (Node->GetGauche());

    // Traitement infixé de *Node

    Parcours (Node->GetDroit());

    // Traitement postfixé de *Node

} // Parcours()

La seconde, non récursive, sert à amorcer la récursivité sur la totalité de l’arbre associé à l’itérateur.

Le constructeur de CIterTree lance un thread ParcoursThr() (fonction membre statique de la classe) dont le paramètre est un pointeur vers l’itérateur d’arbre qui est en train de le lancer.

Ce thread parcourt l’arbre associé à l’itérateur qui l’a lancé à travers la fonction Parcours()) qui dépose successivement dans la BAL de l’itérateur tous les nœuds rencontrés, puis un pointeur nul.

Le ThreadUser récupère les nœuds dans la BAL de l’itérateur à travers la fonction GetNext().

Travail à effectuer

Créer le projet IterArbreThreadsBoost.

Dans l’espace de noms anonyme du fichier IterArbreThreadsBoost.cpp, recopier la classe CBALGen générique ci-dessous :

    template <class CLettre>
    class CBALGen
    {
        condition_variable  m_CondVarProd;
        condition_variable  m_CondVarConsomm;
        mutex               m_MtxCondVar;
        CLettre             m_Lettre;
        bool                m_IsVide;

      public :
        CBALGen () : m_IsVide (true) {}

        void Deposer (const CLettre & MaLettre)
        {
            {
                unique_lock <mutex> Lock (m_MtxCondVar);
                if (!m_IsVide) m_CondVarProd.wait (Lock);

                m_Lettre = MaLettre;
                m_IsVide = false;
            }
            m_CondVarConsomm.notify_one();

        } // Deposer()

        CLettre Retirer ()
        {
            CLettre MaLettre;
            {
                unique_lock <mutex> Lock (m_MtxCondVar);
                if (m_IsVide) m_CondVarConsomm.wait (Lock);

                MaLettre = m_Lettre;
                m_IsVide = true;
           }
           m_CondVarProd.notify_one();

           return MaLettre;

        } // Retirer()

    }; // CBALGen

Recopier et compléter si nécessaire les classes CNode et CSearchTree décrites ci-dessus (en particulier, indiquer si nécessaire les friends à y ajouter).

Écrire la classe CIterTree (déclarations/définitions dans la déclaration de la classe).

Test de la classe CIterTree

Pour tester la classe CIterTree, nous vous proposons la séquence suivante :

• dans l’espace de noms anonyme du fichier IterArbreThreadsBoost.cpp, déclarer un arbre de recherche d’entiers Arbre,

• dans l’espace de noms anonyme du fichier IterArbreThreadsBoost.cpp, écrire la classe functor CLecteur ayant pour seule donnée-membre son ID (numéro d’ordre donné à la construction permettant d’identifier le thread correspondant),

• ajouter à la classe CLecteur l’operator() qui :

  1. affiche le message :

     Debut du lecteur xxx
     

     où xxx désigne l’ID du thread

  2. déclare un itérateur sur l’arbre Arbre déclaré précédemment,

  3. parcourt tout l’arbre en affichant à chaque noeud le message suivant :

     Valeur lue par lecteur xxx : yyy
     

     où xxx désigne l’ID du thread et yyy la valeur associée au noeud courant.

     Le lecteur dort 1 seconde entre chaque affichage;

  4. affiche le message suivant après la fin du parcours et avant la fin du thread :

     Fin du lecteur xxx
     

  Dans la fonction main() :

  ajouter successivement 10 valeurs entières quelconques à l’Arbre précédemment déclaré,

  • créer un groupe de threads,

  • lancer plusieurs CLecteurs décalés dans le temps.

Vous constaterez (en principe !) que chaque lecteur accède indépendamment à tous les éléments de l’arbre.

Autre test possible

Un problème classique consiste à comparer les contenus de deux arbres binaires AVL n’ayant pas la même structure.

Il est alors nécessaire de les parcourir en parallèle (au moyen de deux itérateurs) et de comparer les valeurs obtenues.

S’il vous reste du temps, construisez deux arbres AVL de structures différentes mais de contenus identiques, et conparez-les.