So erstellen Sie eine verknüpfte Liste in VHDL

Die verknüpfte Liste ist eine dynamische Datenstruktur. Eine verknüpfte Liste kann verwendet werden, wenn die Gesamtzahl der Elemente nicht im Voraus bekannt ist. Es wächst und schrumpft im Speicher, relativ zur Anzahl der enthaltenen Elemente.

Verkettete Listen werden am bequemsten unter Verwendung von Klassen in einer objektorientierten Programmiersprache implementiert. VHDL hat einige objektorientierte Eigenschaften, die verwendet werden können, um die Komplexität der Implementierung vom Benutzer zu abstrahieren.

In diesem Artikel verwenden wir Zugriffstypen, Datensätze und geschützte Typen, um eine verknüpfte Liste in VHDL zu implementieren. Wir werden ein neues VHDL-Paket erstellen, in das wir den gesamten Code unserer verknüpften Liste schreiben werden.

Paket

Das erste, was wir tun werden, ist, ein Paket zu deklarieren, das unseren Code enthalten wird. Ein VHDL-Paket ist eine Sammlung von Typen, Objekten oder Unterprogrammen, die in eine andere VHDL-Datei importiert werden können. Die meisten VHDL-Module importieren das Paket std_logic_1164 aus der IEEE-Bibliothek. Wir erstellen unser eigenes Paket, ähnlich wie es.

Der Inhalt unserer neuen DataStructures.vhd-Datei:

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

Obwohl das Paket nur die Implementierung der verknüpften Liste enthalten wird, werden wir es zukunftssicher machen, indem wir es DataStructures nennen. Man könnte sich leicht vorstellen, dass jemand später andere Datenstrukturen wie Bäume oder Hash-Maps hinzufügen möchte.

Ein Paket besteht aus zwei Teilen; eine deklarative Region und einen Körper. In den deklarativen Bereich legen Sie alles, was für die Benutzer des Pakets sichtbar sein soll. Der Körper ist privat und von außen nicht zugänglich.

Geschützter Typ

Geschützte Typen sind klassenähnliche Konstrukte in VHDL. Sie können Unterprogramme, Typdeklarationen und Variablen enthalten. Ein geschützter Typ besteht aus einer öffentlichen Deklaration und einem privaten Körper. Wir fügen die Deklaration der Paketdeklaration und den Hauptteil dem Pakethauptteil hinzu.

Unsere DataStructures.vhd-Datei nach dem Hinzufügen des geschützten Typs:

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;

Wir haben den geschützten Typ LinkedList genannt, weil er alles enthält, was mit der verknüpften Liste zu tun hat. Wenn wir dem Paket eine andere Art von Datenstruktur hinzufügen würden, würde das einen anderen geschützten Typ bedeuten.

Innerhalb des deklarativen Bereichs des geschützten Typs haben wir drei Unterprogramme deklariert. Es gibt noch keine Implementierung, dazu kommen wir später. Damit die Unterprogramme außerhalb des geschützten Typs sichtbar sind, müssen sie hier deklariert werden.

Die drei Unterprogramme sind die standardmäßigen Linked-List-Methoden:Push, Pop und IsEmpty. Push fügt am Anfang der Liste ein neues Element hinzu. Pop entfernt ein Element vom Ende der Liste. IsEmpty ist eine Hilfsfunktion, die true zurückgibt wenn die Liste leer ist.

Aufnehmen

Ein Datensatz ist ein zusammengesetzter Typ, der mehrere Mitgliedstypen enthalten kann. Es funktioniert ähnlich wie eine Struktur in der Programmiersprache C. Wenn ein Signal oder eine Variable aus dem Datensatztyp erstellt wird, können die Datenelemente mit dem „.“ referenziert werden. Notation. Zum Beispiel MyItem.Data .

Unsere Datensatzerklärung innerhalb des Körpers des geschützten Typs:

   type LinkedList is protected body

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

   end protected body;

Wir haben den Datensatztyp im Körper des geschützten Typs deklariert. Der deklarative Bereich eines geschützten Typs kann keine anderen Typ- oder Signaldeklarationen enthalten, also müssen wir sie im Hauptteil des geschützten Typs deklarieren.

Das ist für uns kein Problem, da Item ein intern verwendeter Typ ist. Es muss nicht von außen sichtbar sein. Der Benutzer der verknüpften Liste sollte nur über die drei öffentlich deklarierten Unterprogramme darauf zugreifen.

Unser Datensatz enthält zwei Datenelemente; Daten und NextItem. Während Daten vom Typ integer sind , NextItem ist vorerst vom mysteriösen Ptr-Typ.

Zugriffstyp

Zugriffstypen sind VHDL-Zeiger. Indem wir sie verwenden, können wir Objekte während der Laufzeit dynamisch erstellen. Wir werden einen neuen Zugriffstyp namens Ptr deklarieren, der auf ein dynamisch erstelltes Objekt des Typs Item zeigt.

Der Paketkörper mit dem neuen hinzugefügten Zugriffstyp:

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;

Ein verknüpfter Listenknoten muss einen Verweis auf den nächsten Knoten in der Liste enthalten. Wir haben dies im Item-Datensatz mit dem NextItem-Member implementiert. Es ist vom Typ Ptr, der wiederum ein Zeiger zurück auf den Item-Typ ist. Um dieses Henne/Ei-Problem zu vermeiden, deklarieren wir Item zunächst als unvollständigen Typ. Dann deklarieren wir den Ptr-Typ als Zeiger auf den unvollständigen Typ. Schließlich spezifizieren wir die vollständige Deklaration des Item-Typs.

Als letztes haben wir eine neue Variable namens Root vom Typ Ptr deklariert. Dies wird der Stamm der verknüpften Liste sein. Wenn die Liste leer ist, ist der Wert von Root null . Andernfalls zeigt es auf das erste Element in der Liste.

Linked-List-Methoden

Jetzt ist es an der Zeit, die Unterprogramme zu implementieren, die wir im deklarativen Bereich des geschützten Typs deklariert haben. Das waren die Push-Prozedur und die zwei unreinen Funktionen:Pop und IsEmpty.

Wir werden die Implementierung der Unterprogramme innerhalb des Hauptteils des geschützten Typs platzieren.

Drücken

Push ist das einzige der Unterprogramme, das eine Prozedur ist. Funktionen in VHDL erfordern einen Rückgabewert, der nicht weggelassen werden kann. Um die Verwendung eines Dummy-Rückgabewerts zu vermeiden, ist eine Prozedur vorzuziehen.

Das Push-Verfahren:

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;

Als erstes wird dynamisch ein neues Objekt vom Typ Item zugewiesen. Dies geschieht mit dem new Stichwort. Jedes Mal, wenn die new Schlüsselwort verwendet wird, wird dynamischer Speicher vom Simulator verbraucht.

Der Rest des Codes ist nur ein standardmäßiger Linked-List-Algorithmus. Das neue Element wird an das Ende der Liste angehängt oder wird zum Root-Element, wenn die Liste leer ist. Informieren Sie sich über verknüpfte Listen auf Wikipedia, wenn Sie mehr Hintergrundinformationen benötigen.

Pop

Pop entfernt das älteste Element aus der Liste und gibt es an den Aufrufer zurück. Wenn wir einfach den Verweis auf das geknallte Element entfernen und zurückgeben, kommt es im Simulator zu Speicherverlust. Nachdem der Funktionsaufruf beendet ist, geht der Verweis auf das dynamisch erstellte Objekt für immer verloren.

Vor VHDL-2017 (auch als VHDL-2018 oder VHDL-2019 bezeichnet) gibt es in VHDL keine Garbage Collection. Und VHDL-2017 wird von den meisten Simulatoren nicht unterstützt. Daher müssen wir deallocate aufrufen bevor Sie von der Funktion zurückkehren.

Die deallocate -Operator gibt den Speicher frei, der von einem dynamisch zugewiesenen Objekt verwendet wird. Für jeden Aufruf von new , sollte ein Aufruf von deallocate erfolgen bevor der Verweis auf ein Objekt gelöscht wird.

Die Pop-Funktion:

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;

Nachdem wir deallocate angerufen haben , können wir nicht auf die Daten verweisen, auf die die Node-Variable zeigt. Es wurde vom Simulator befreit. Die Lösung besteht darin, die Daten vor dem Freigeben in eine lokale Variable zu kopieren und dann den Wert der Variablen zurückzugeben.

Ist leer

Die Überprüfung, ob die Liste leer ist oder nicht, kann einfach dadurch erreicht werden, dass überprüft wird, ob der Wurzelknoten auf etwas anderes als null zeigt:

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

Testbench

Um unseren Code auszuführen, müssen wir eine Testbench erstellen. Eigentlich kann die verknüpfte Liste nur in Testbenches verwendet werden. Zugriffsarten sind nicht synthetisierbar, aber für Überprüfungszwecke sehr nützlich.

Ein Bibliothekspaket verwenden

In der Testbench importieren wir zunächst den work Bibliothek. Dies ist die Standardbibliothek in VHDL, und hier befindet sich unser DataStructures-Paket. Danach können wir den geschützten LinkedList-Typ wie folgt importieren:

library work;
use work.DataStructures.LinkedList;

Gemeinsame Variable

Eine Shared Variable ist eine Variable, auf die mehrere Prozesse zugreifen können. Im Gegensatz zu regulären Variablen, die nur innerhalb eines einzelnen Prozesses deklariert werden können, können gemeinsam genutzte Variablen im deklarativen Bereich der Architektur deklariert werden. Damit haben sie den gleichen Geltungsbereich wie Signale.

Wir müssen eine gemeinsam genutzte Variable verwenden, da es nicht möglich ist, ein Signal mit geschütztem Typ zu deklarieren. Wenn wir es versuchen würden, würde sich ModelSim beschweren:(vcom-1464) Illegale Deklaration des Signals „List“ des Typs work.DataStructures.LinkedList (Typ ist ein geschützter Typ).

Wir deklarieren die gemeinsam genutzte Variable vom Typ LinkedList im deklarativen Bereich der Testbench:

architecture sim of LinkedListTb is

   shared variable List : LinkedList;

begin

Der endgültige Code für die Testbench

Um unsere drei Hilfsfunktionen zu testen, erstellen wir einen neuen Prozess. Dabei fügen wir eine For-Schleife hinzu, die fünf ganze Zahlen in die verknüpfte Liste schiebt. Schließlich leeren wir die verknüpfte Liste in einer While-Schleife, die ausgeführt wird, bis unsere IsEmpty-Funktion true zurückgibt :

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;

Der endgültige Code für das DataStructures-Paket

Nachdem Sie den gesamten Code geschrieben haben, über den wir zuvor in diesem Artikel gesprochen haben, sollte das DataStructures-Paket wie folgt aussehen:

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;

Das Ergebnis

Die Ausgabe an die Simulatorkonsole, wenn wir die Run-Taste in ModelSim drücken:

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

Wie wir aus dem Ausdruck sehen können, werden fünf Ganzzahlen in die verknüpfte Liste geschoben. Dann entfernt die While-Schleife in der Testbench sie aus der Liste in der Reihenfolge, in der sie eingefügt wurden.