Implémentation d'une liste chainée dynamique en VHDL avec types protégés et pointeurs d'accès

Une liste chainée est une structure de données dynamique qui s'agrandit et se rétrécit au fur et à mesure que des éléments sont ajoutés ou supprimés. Les fonctionnalités orientées objet de VHDL - types d'accès, enregistrements et types protégés - permettent d'implémenter cette structure proprement et efficacement.

Création du package DataStructures

Nous allons encapsuler toute la logique de liste chainée dans un package VHDL dédié appelé DataStructures. Ce nom à l'épreuve du temps permet une extension facile vers d'autres structures comme les arbres ou les tables de hachage plus tard.

package DataStructures is
  -- Déclarations publiques ici
end package DataStructures;

package body DataStructures is
  -- Déclarations privées et implémentations ici
end package body DataStructures;

Un package VHDL consiste en une région déclarative (interface publique) et un corps (implémentation privée). La région déclarative est visible pour les utilisateurs ; le corps reste interne.

Définition d'un type protégé

Les types protégés agissent comme des classes légères en VHDL. Ils peuvent contenir des sous-programmes, des déclarations de types et des variables. Nous allons définir un type protégé appelé LinkedList qui expose trois opérations : Push, Pop et IsEmpty.

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
  end protected body;
end package body DataStructures;

Introduction de l'enregistrement Item

À l'intérieur du corps protégé, nous déclarons un record qui représente un nœud. L'enregistrement contient la charge utile de données et un pointeur vers le nœud suivant.

type LinkedList is protected body
  type Item is record
    Data : integer;
    NextItem : Ptr;
  end record;
end protected body;

Parce que les types protégés ne peuvent pas déclarer de nouveaux types dans la région déclarative, l'enregistrement Item est défini à l'intérieur du corps.

Gestion des pointeurs avec les types d'accès

Nous utilisons un type d'accès Ptr pour référencer dynamiquement des instances Item. Cette déclaration en deux étapes évite les dépendances circulaires.

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

Un pointeur racine suit le premier nœud. Quand la liste est vide, Root est null.

variable Root : Ptr;

Implémentation des opérations de liste chainée

Procédure Push

Ajouter un nouvel élément est simple : allouer un nouvel Item, le peupler, et le lier à la fin.

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;

Fonction Pop

Supprimer le premier élément nécessite une gestion de mémoire soignée. Puisque VHDL n'a pas de ramasse-miettes (avant 2017), nous déallouons explicitement le nœud supprimé.

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;

Fonction IsEmpty

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

Test de la liste chainée

Bien que les types d'accès ne soient pas synthétisables, ils sont idéaux pour la vérification. Un testbench démontre le comportement de la liste chainée.

Importation du package

library work;
use work.DataStructures.LinkedList;

Utilisation d'une variable partagée

Les signaux ne peuvent pas être de type protégé, donc nous utilisons une variable partagée pour permettre à plusieurs processus d'interagir avec la liste.

architecture sim of LinkedListTb is
  shared variable List : LinkedList;
begin
  -- Processus de test
end architecture;

Testbench complet

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;

Package DataStructures complet

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;

Exécution du test

Lors de l'exécution dans ModelSim, la console affiche :

# ** Note: Pushing 1
# ** Note: Pushing 2
# ** Note: Pushing 3
# ** Note: Pushing 4
# ** Note: Pushing 5
# ** Note: Popping 1
# ** Note: Popping 2
# ** Note: Popping 3
# ** Note: Popping 4
# ** Note: Popping 5

La sortie confirme que la liste stocke et récupère correctement les valeurs dans l'ordre FIFO.