Comment créer une liste chaînée en VHDL

La liste chaînée est une structure de données dynamique. Une liste chaînée peut être utilisée lorsque le nombre total d'éléments n'est pas connu à l'avance. Il grandit et rétrécit en mémoire, par rapport au nombre d'éléments qu'il contient.

Les listes chaînées sont plus facilement implémentées à l'aide de classes dans un langage de programmation orienté objet. VHDL possède certaines fonctionnalités orientées objet qui peuvent être utilisées pour faire abstraction de la complexité de la mise en œuvre pour l'utilisateur.

Dans cet article, nous allons utiliser des types d'accès, des enregistrements et des types protégés pour implémenter une liste chaînée en VHDL. Nous allons créer un nouveau package VHDL dans lequel nous écrirons tout le code de notre liste chaînée.

Forfait

La première chose que nous allons faire est de déclarer un package qui contiendra notre code. Un package VHDL est une collection de types, d'objets ou de sous-programmes pouvant être importés dans un autre fichier VHDL. La plupart des modules VHDL importent le package std_logic_1164 à partir de la bibliothèque IEEE. Nous créons notre propre package, un peu comme celui-ci.

Le contenu de notre nouveau fichier DataStructures.vhd :

package DataStructures is
   -- Public declarations go here
end package DataStructures;
 
package body DataStructures is
   -- Private declarations and implementations go here
end package body DataStructures;

Même si le package ne contiendra que l'implémentation de la liste chaînée, nous la pérenniserons en la nommant DataStructures. On pourrait facilement imaginer que quelqu'un voudrait y ajouter d'autres structures de données comme des arbres ou des cartes de hachage plus tard.

Un package se compose de deux parties; une région déclarative et un corps. La région déclarative est l'endroit où vous placez tout ce qui doit être visible pour les utilisateurs du package. Le corps est à portée privée et n'est pas accessible de l'extérieur.

Type protégé

Les types protégés sont des constructions de type classe en VHDL. Ils peuvent contenir des sous-programmes, des déclarations de type et des variables. Un type protégé se compose d'une déclaration publique et d'un organisme privé. Nous ajouterons la déclaration à la déclaration du package et le corps au corps du package.

Notre fichier DataStructures.vhd après avoir ajouté le type protégé :

package DataStructures is

   type LinkedList is protected

      -- Prototypes of subprograms
      procedure Push(constant Data : in integer);
      impure function Pop return integer;
      impure function IsEmpty return boolean;

   end protected;

end package DataStructures;

package body DataStructures is

   type LinkedList is protected body
   end protected body;

end package body DataStructures;

Nous avons nommé le type protégé LinkedList car il contiendra tout ce qui concerne la liste liée. Si nous devions ajouter un autre type de structure de données au package, cela signifierait un autre type protégé.

Dans la région déclarative du type protégé, nous avons déclaré trois sous-programmes. Il n'y a pas encore de mise en œuvre, nous y reviendrons plus tard. Pour que les sous-programmes soient visibles en dehors du type protégé, ils doivent être déclarés ici.

Les trois sous-programmes sont les méthodes de liste chaînée standard :Push, Pop et IsEmpty. Push ajoute un nouvel élément au début de la liste. Pop supprime un élément de la fin de la liste. IsEmpty est une fonction utilitaire qui renvoie true si la liste est vide.

Enregistrer

Un enregistrement est un type composite qui peut contenir plusieurs types de membres. Cela fonctionne un peu comme une structure dans le langage de programmation C. Lorsqu'un signal ou une variable est créé à partir du type d'enregistrement, les membres de données peuvent être référencés en utilisant le "." notation. Par exemple MyItem.Data .

Notre déclaration d'enregistrement dans le corps du type protégé :

   type LinkedList is protected body

      type Item is record
         Data : integer;
         NextItem : Ptr;
      end record;

   end protected body;

Nous avons déclaré le type record dans le corps du type protected. La région déclarative d'un type protégé ne peut pas contenir d'autres déclarations de type ou de signal, nous devons donc les déclarer dans le corps du type protégé.

Ce n'est pas un problème pour nous car Item est un type utilisé en interne. Il n'a pas besoin d'être visible de l'extérieur. L'utilisateur de la liste liée doit y accéder uniquement via les trois sous-programmes déclarés publiquement.

Notre enregistrement contient deux membres de données ; Données et élément suivant. Tant que Data est de type integer , NextItem est, pour l'instant, mystérieux de type Ptr.

Type d'accès

Les types d'accès sont des pointeurs VHDL. En les utilisant, nous pouvons créer dynamiquement des objets pendant l'exécution. Nous allons déclarer un nouveau type d'accès nommé Ptr qui pointera vers un objet créé dynamiquement de type Item.

Le corps du package avec le nouveau type d'accès ajouté :

package body DataStructures is

   type LinkedList is protected body

      -- Declaration of incomplete Item type
      type Item;

      -- Declaration of pointer type to the Item type
      type Ptr is access Item;

      -- Full declaration of the Item type
      type Item is record
         Data : integer;
         NextItem : Ptr; -- Pointer to the next Item
      end record;

      -- Root of the linked list
      variable Root : Ptr;

end package body DataStructures;

Un nœud de liste chaînée doit contenir une référence au nœud suivant de la liste. Nous avons implémenté cela dans l'enregistrement Item avec le membre NextItem. Il est de type Ptr, qui à son tour est un pointeur vers le type Item. Pour éviter ce problème de poule/œuf, nous déclarons d'abord Item comme un type incomplet. Ensuite, nous déclarons le type Ptr comme un pointeur vers le type incomplet. Enfin, nous spécifions la déclaration complète du type Item.

La dernière chose que nous avons faite a été de déclarer une nouvelle variable nommée Root de type Ptr. Ce sera la racine de la liste chaînée. Si la liste est vide, la valeur de Root sera null . Sinon, il pointera vers le premier élément de la liste.

Méthodes de liste chaînée

Il est maintenant temps d'implémenter les sous-programmes que nous avons déclarés dans la région déclarative du type protégé. Il s'agissait de la procédure Push et des deux fonctions impures :Pop et IsEmpty.

Nous placerons l'implémentation des sous-programmes dans le corps du type protégé.

Appuyer

Push est le seul des sous-programmes qui est une procédure. Les fonctions en VHDL nécessitent une valeur de retour qui ne peut pas être omise. Pour éviter d'utiliser une valeur de retour factice, une procédure est préférable.

La procédure Push :

procedure Push(Data : in integer) is
   variable NewItem : Ptr;
   variable Node : Ptr;
begin
   -- Dynamically allocate a new item
   NewItem := new Item;
   NewItem.Data := Data;

   -- If the list is empty, this becomes the root node
   if Root = null then
      Root := NewItem;

   else
      -- Start searching from the root node
      Node := Root;

      -- Find the last node
      while Node.NextItem /= null loop
         Node := Node.NextItem;
      end loop;

      -- Append the new item at the end of the list
      Node.NextItem := NewItem;
   end if;
end;

La première chose qui se passe est qu'un nouvel objet de type Item est alloué dynamiquement. Ceci est fait en utilisant le new mot-clé. Chaque fois que le new mot clé est utilisé, la mémoire dynamique est consommée par le simulateur.

Le reste du code n'est qu'un algorithme de liste chaînée standard. Le nouvel élément est ajouté à la fin de la liste ou devient l'élément racine si la liste est vide. Renseignez-vous sur les listes liées sur Wikipédia si vous avez besoin de plus d'informations.

Pop

Pop supprime l'élément le plus ancien de la liste et le renvoie à l'appelant. Si nous supprimons simplement la référence à l'élément poppé et la renvoyons, il y aura une perte de mémoire dans le simulateur. Une fois l'appel de fonction terminé, la référence à l'objet créé dynamiquement est définitivement perdue.

Il n'y a pas de récupération de place dans VHDL avant VHDL-2017 (également appelé VHDL-2018 ou VHDL-2019). Et VHDL-2017 n'est pas pris en charge par la plupart des simulateurs. Par conséquent, nous devons appeler deallocate avant de revenir de la fonction.

Le deallocate L'opérateur libère la mémoire utilisée par un objet alloué dynamiquement. Pour chaque appel au new , il devrait y avoir un appel à deallocate avant que la référence à un objet ne soit supprimée.

La fonction Pop :

impure function Pop return integer is
   variable Node : Ptr;
   variable RetVal : integer;
begin
   Node := Root;
   Root := Root.NextItem;

   -- Copy and free the dynamic object before returning
   RetVal := Node.Data;
   deallocate(Node);

   return RetVal;
end;

Après avoir appelé le deallocate , nous ne pouvons pas référencer les données pointées par la variable Node. Il a été libéré par le simulateur. La solution consiste à copier les données dans une variable locale avant de les libérer, puis à renvoyer la valeur de la variable.

EstVide

Vérifier si la liste est vide ou non peut simplement être accompli en vérifiant si le nœud racine pointe vers autre chose que null :

impure function IsEmpty return boolean is
begin
   return Root = null;
end;

Banc de test

Pour exécuter notre code, nous devrons créer un testbench. En fait, la liste chaînée ne peut être utilisée que dans les bancs d'essai. Les types d'accès ne sont pas synthétisables, mais ils sont très utiles à des fins de vérification.

Utiliser un package de bibliothèque

Dans le testbench, nous importons d'abord le work bibliothèque. Il s'agit de la bibliothèque par défaut dans VHDL, et c'est là que réside notre package DataStructures. Après cela, nous pouvons importer le type protégé LinkedList comme ceci :

library work;
use work.DataStructures.LinkedList;

Variable partagée

Une variable partagée est une variable accessible à plusieurs processus. Contrairement aux variables régulières qui ne peuvent être déclarées qu'au sein d'un seul processus, les variables partagées peuvent être déclarées dans la région déclarative de l'architecture. Ainsi, ils ont la même portée que les signaux.

Nous devons utiliser une variable partagée car il n'est pas possible de déclarer un signal de type protégé. Si nous essayions, ModelSim se plaindrait :(vcom-1464) Déclaration illégale du signal "List" de type work.DataStructures.LinkedList (le type est un type protégé).

On déclare la variable partagée de type LinkedList dans la région déclarative du testbench :

architecture sim of LinkedListTb is

   shared variable List : LinkedList;

begin

Le code final pour le testbench

Pour tester nos trois fonctions d'utilité, nous créons un nouveau processus. Dans le processus, nous ajoutons une boucle For qui pousse cinq entiers vers la liste chaînée. Enfin, nous vidons la liste chaînée dans une boucle While qui s'exécute jusqu'à ce que notre fonction IsEmpty renvoie true :

library work;
use work.DataStructures.LinkedList;

entity LinkedListTb is
end entity;

architecture sim of LinkedListTb is

   shared variable List : LinkedList;

begin

   process is
   begin

      for i in 1 to 5 loop
         report "Pushing " & integer'image(i);
         List.Push(i);
      end loop;

      while not List.IsEmpty loop
         report "Popping " & integer'image(List.Pop);
      end loop;

      wait;
   end process;

end architecture;

Le code final du package DataStructures

Après avoir écrit tout le code dont nous avons parlé précédemment dans cet article, le package DataStructures devrait ressembler à ceci :

package DataStructures is
   type LinkedList is protected

      procedure Push(constant Data : in integer);
      impure function Pop return integer;
      impure function IsEmpty return boolean;

   end protected;
end package DataStructures;

package body DataStructures is

   type LinkedList is protected body

      type Item;
      type Ptr is access Item;
      type Item is record
         Data : integer;
         NextItem : Ptr;
      end record;

      variable Root : Ptr;

      procedure Push(Data : in integer) is
         variable NewItem : Ptr;
         variable Node : Ptr;
      begin
         NewItem := new Item;
         NewItem.Data := Data;

         if Root = null then
            Root := NewItem;

         else
            Node := Root;

            while Node.NextItem /= null loop
               Node := Node.NextItem;
            end loop;

            Node.NextItem := NewItem;
         end if;
      end;

      impure function Pop return integer is
         variable Node : Ptr;
         variable RetVal : integer;
      begin
         Node := Root;
         Root := Root.NextItem;

         RetVal := Node.Data;
         deallocate(Node);

         return RetVal;
      end;

      impure function IsEmpty return boolean is
      begin
         return Root = null;
      end;

   end protected body;

end package body DataStructures;

Le résultat

La sortie vers la console du simulateur lorsque nous appuyons sur le bouton d'exécution dans ModelSim :

VSIM 10> run
# ** Note: Pushing 1
#    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
# ** Note: Pushing 2
#    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
# ** Note: Pushing 3
#    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
# ** Note: Pushing 4
#    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
# ** Note: Pushing 5
#    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
# ** Note: Popping 1
#    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
# ** Note: Popping 2
#    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
# ** Note: Popping 3
#    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
# ** Note: Popping 4
#    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb
# ** Note: Popping 5
#    Time: 0 ns  Iteration: 0  Instance: /linkedlisttb

Comme nous pouvons le voir sur l'impression, cinq entiers sont poussés vers la liste chaînée. Ensuite, la boucle While du testbench les extrait de la liste dans l'ordre dans lequel ils ont été insérés.