Een gekoppelde lijst maken in VHDL

De gekoppelde lijst is een dynamische gegevensstructuur. Een gekoppelde lijst kan worden gebruikt wanneer het totale aantal elementen niet van tevoren bekend is. Het groeit en krimpt in het geheugen, in verhouding tot het aantal items dat het bevat.

Gelinkte lijsten kunnen het gemakkelijkst worden geïmplementeerd met klassen in een objectgeoriënteerde programmeertaal. VHDL heeft enkele objectgeoriënteerde functies die kunnen worden gebruikt om de complexiteit van de implementatie van de gebruiker weg te nemen.

In dit artikel gaan we toegangstypen, records en beschermde typen gebruiken om een ​​gekoppelde lijst in VHDL te implementeren. We gaan een nieuw VHDL-pakket maken waarin we al onze gekoppelde lijstcode zullen schrijven.

Pakket

Het eerste dat we zullen doen, is een pakket declareren dat onze code zal bevatten. Een VHDL-pakket is een verzameling typen, objecten of subprogramma's die in een ander VHDL-bestand kunnen worden geïmporteerd. De meeste VHDL-modules importeren het std_logic_1164-pakket uit de IEEE-bibliotheek. We maken ons eigen pakket, net zoals het.

De inhoud van ons nieuwe DataStructures.vhd-bestand:

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

Hoewel het pakket alleen de implementatie van de gekoppelde lijst zal bevatten, zullen we het toekomstbestendig maken door het DataStructures te noemen. Je zou je gemakkelijk kunnen voorstellen dat iemand er later andere datastructuren zoals bomen of hash-kaarten aan zou willen toevoegen.

Een pakket bestaat uit twee delen; een declaratief gebied en een lichaam. Het declaratieve gebied is waar u alles plaatst dat zichtbaar moet zijn voor de gebruikers van het pakket. Het lichaam is afgeschermd en niet van buitenaf toegankelijk.

Beschermd type

Beveiligde typen zijn klasse-achtige constructies in VHDL. Ze kunnen subprogramma's, typedeclaraties en variabelen bevatten. Een beschermd type bestaat uit een openbare verklaring en een particulier orgaan. We voegen de verklaring toe aan de pakketaangifte en de hoofdtekst aan de hoofdtekst van het pakket.

Ons bestand DataStructures.vhd na toevoeging van het beveiligde type:

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;

We hebben het beschermde type LinkedList genoemd omdat het alles bevat wat met de gekoppelde lijst te maken heeft. Als we een ander soort datastructuur aan het pakket zouden toevoegen, zou dat een ander beveiligd type betekenen.

Binnen het declaratieve gebied van het beschermde type hebben we drie subprogramma's gedeclareerd. Er is nog geen implementatie, daar komen we later op terug. Om de subprogramma's buiten het beschermde type zichtbaar te maken, moeten ze hier worden aangegeven.

De drie subprogramma's zijn de standaard gekoppelde lijstmethoden:Push, Pop en IsEmpty. Push voegt een nieuw element toe aan het begin van de lijst. Pop verwijdert een element aan het einde van de lijst. IsEmpty is een hulpprogramma-functie die true . retourneert als de lijst leeg is.

Opnemen

Een record is een samengesteld type dat meerdere lidtypen kan bevatten. Het werkt een beetje als een struct in de programmeertaal C. Wanneer een signaal of variabele wordt gemaakt op basis van het recordtype, kan naar de gegevensleden worden verwezen met behulp van de "." notatie. Bijvoorbeeld MyItem.Data .

Onze recordaangifte binnen de hoofdtekst van het beschermde type:

   type LinkedList is protected body

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

   end protected body;

We hebben het recordtype in de hoofdtekst van het beschermde type gedeclareerd. De declaratieve regio van een beschermd type kan geen andere type- of signaaldeclaraties bevatten, dus we moeten ze declareren in de beschermde type body.

Dat is voor ons geen probleem omdat Item een ​​intern gebruikt type is. Het hoeft van buitenaf niet zichtbaar te zijn. De gebruiker van de gekoppelde lijst mag er alleen toegang toe krijgen via de drie openbaar verklaarde subprogramma's.

Ons record bevat twee gegevensleden; Gegevens en NextItem. Terwijl gegevens van het type integer zijn , NextItem is van het voorlopig mysterieuze Ptr-type.

Toegangstype

Toegangstypen zijn VHDL-pointers. Door ze te gebruiken, kunnen we dynamisch objecten maken tijdens runtime. We declareren een nieuw toegangstype met de naam Ptr dat verwijst naar een dynamisch gemaakt object van het itemtype.

De pakkettekst met het nieuwe toegangstype toegevoegd:

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;

Een gekoppelde lijstknooppunt moet een verwijzing bevatten naar het volgende knooppunt in de lijst. We hebben dit geïmplementeerd in het itemrecord met het NextItem-lid. Het is van het type Ptr, wat op zijn beurt een verwijzing is naar het itemtype. Om dit kip/ei-probleem te voorkomen, declareren we eerst Item als een incompleet type. Vervolgens declareren we het Ptr-type als een verwijzing naar het onvolledige type. Ten slotte specificeren we de volledige aangifte van het itemtype.

Het laatste wat we deden was een nieuwe variabele declareren met de naam Root van het type Ptr. Dit wordt de root van de gekoppelde lijst. Als de lijst leeg is, is de waarde van Root null . Anders wijst het naar het eerste item in de lijst.

Gelinkte lijstmethoden

Het is nu tijd om de subprogramma's te implementeren die we hebben gedeclareerd in het declaratieve gebied van het beschermde type. Het waren de Push-procedure en de twee onzuivere functies:Pop en IsEmpty.

We zullen de implementatie van de subprogramma's in de hoofdtekst van het beschermde type plaatsen.

Duwen

Push is de enige van de subprogramma's die een procedure is. Functies in VHDL vereisen een retourwaarde die niet kan worden weggelaten. Om het gebruik van een dummy-retourwaarde te vermijden, verdient een procedure de voorkeur.

De push-procedure:

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;

Het eerste dat gebeurt, is dat een nieuw object van het type Item dynamisch wordt toegewezen. Dit wordt gedaan met behulp van de new trefwoord. Elke keer dat de new trefwoord wordt gebruikt, wordt dynamisch geheugen verbruikt door de simulator.

De rest van de code is slechts een standaard algoritme voor gekoppelde lijsten. Het nieuwe item wordt aan het einde van de lijst toegevoegd, of het wordt het Root-item als de lijst leeg is. Lees de gelinkte lijsten op Wikipedia als je meer achtergrondinformatie nodig hebt.

Pop

Pop verwijdert het oudste element uit de lijst en geeft het terug aan de beller. Als we gewoon de verwijzing naar het gepofte element verwijderen en retourneren, is er geheugenverlies in de simulator. Nadat de functieaanroep is voltooid, gaat de verwijzing naar het dynamisch gecreëerde object voor altijd verloren.

Er is geen garbagecollection in VHDL voorafgaand aan VHDL-2017 (ook wel VHDL-2018 of VHDL-2019 genoemd). En VHDL-2017 wordt niet ondersteund door de meeste simulatoren. Daarom moeten we deallocate . bellen voordat u terugkeert van de functie.

De deallocate operator maakt het geheugen vrij dat wordt gebruikt door een dynamisch toegewezen object. Voor elke oproep naar new , er moet een oproep zijn naar deallocate voordat de verwijzing naar een object wordt verwijderd.

De Pop-functie:

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;

Nadat we deallocate . hebben gebeld , kunnen we niet verwijzen naar de gegevens waarnaar wordt verwezen door de Node-variabele. Het is vrijgemaakt door de simulator. De oplossing is om de gegevens naar een lokale variabele te kopiëren voordat ze worden vrijgemaakt en vervolgens de waarde van de variabele terug te sturen.

IsEmpty

Controleren of de lijst leeg is of niet, kan eenvoudig worden bereikt door te controleren of de root-node naar iets anders dan null verwijst:

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

Testbank

Om onze code uit te voeren, moeten we een testbench maken. Eigenlijk is de gekoppelde lijst alleen te gebruiken in testbanken. Toegangstypes kunnen niet worden samengevoegd, maar ze zijn erg handig voor verificatiedoeleinden.

Een bibliotheekpakket gebruiken

In de testbench importeren we eerst de work bibliotheek. Dit is de standaardbibliotheek in VHDL en dit is waar ons DataStructures-pakket zich bevindt. Daarna kunnen we het door LinkedList beveiligde type als volgt importeren:

library work;
use work.DataStructures.LinkedList;

Gedeelde variabele

Een gedeelde variabele is een variabele waartoe verschillende processen toegang hebben. In tegenstelling tot reguliere variabelen die alleen binnen een enkel proces kunnen worden gedeclareerd, kunnen gedeelde variabelen worden gedeclareerd in het declaratieve gebied van de architectuur. Ze hebben dus hetzelfde bereik als signalen.

We moeten een gedeelde variabele gebruiken omdat het niet mogelijk is om een ​​signaal van het beschermde type te declareren. Als we het probeerden, zou ModelSim klagen:(vcom-1464) Illegale aangifte van signaal "List" van het type work.DataStructures.LinkedList (type is een beschermd type).

We declareren de gedeelde variabele van het type LinkedList in het declaratieve gebied van de testbench:

architecture sim of LinkedListTb is

   shared variable List : LinkedList;

begin

De definitieve code voor de testbench

Om onze drie hulpprogramma's te testen, maken we een nieuw proces. In het proces voegen we een For-lus toe die vijf gehele getallen naar de gekoppelde lijst duwt. Ten slotte maken we de gekoppelde lijst leeg in een While-lus die wordt uitgevoerd totdat onze functie IsEmpty true retourneert :

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;

De definitieve code voor het DataStructures-pakket

Na het schrijven van alle code waarover we eerder in dit artikel hebben gesproken, zou het DataStructures-pakket er als volgt uit moeten zien:

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;

Het resultaat

De uitvoer naar de simulatorconsole wanneer we op de run-knop in ModelSim drukken:

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

Zoals we op de afdruk kunnen zien, worden vijf gehele getallen naar de gekoppelde lijst gepusht. Vervolgens haalt de While-lus in de testbench ze uit de lijst in de volgorde waarin ze zijn ingevoegd.