Een dynamische gelinkte lijst in VHDL implementeren met protected types en access pointers

Een gelinkte lijst is een dynamische datastructuur die uitbreidt en inkrimpt naarmate elementen worden toegevoegd of verwijderd. VHDL's objectgeoriënteerde functies – access types, records en protected types – maken het mogelijk om deze structuur netjes en efficiënt te implementeren.

Het DataStructures-package maken

We encapsuleren alle gelinkte-lijstlogica in een speciaal VHDL-package genaamd DataStructures. Deze toekomstbestendige naam maakt eenvoudige uitbreiding naar andere structuren zoals bomen of hash maps mogelijk.

package DataStructures is -- Publieke declaraties gaan hier end package DataStructures; package body DataStructures is -- Privé declaraties en implementaties gaan hier end package body DataStructures; 

Een VHDL-package bestaat uit een declaratieve regio (publieke interface) en een body (privé implementatie). De declaratieve regio is zichtbaar voor gebruikers; de body blijft intern.

Een protected type definiëren

Protected types werken als lichtgewicht klassen in VHDL. Ze kunnen subprogramma's, typedeclaraties en variabelen bevatten. We definiëren een protected type genaamd LinkedList dat drie operaties blootlegt: Push, Pop en 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; 

Het Item-record introduceren

Binnen de protected body declareren we een record die een node vertegenwoordigt. Het record bevat de data-payload en een pointer naar de volgende node.

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

Omdat protected types geen nieuwe typen in de declaratieve regio mogen declareren, wordt het Item-record binnen de body gedefinieerd.

Pointers afhandelen met access types

We gebruiken een access type Ptr om Item-instanties dynamisch te refereren. Deze tweestapsdeclaratie vermijdt circulaire afhankelijkheden.

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

Root null.

variable Root : Ptr; 

Gelinkte-lijstoperaties implementeren

Push-procedure

Het toevoegen van een nieuw element is eenvoudig: reserveer een nieuw Item, vul het en koppel het aan het einde.

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; 

Pop-functie

Het verwijderen van het eerste element vereist zorgvuldig geheugenbeheer. Omdat VHDL (voor 2017) geen garbage collection heeft, deallokeer we de verwijderde node expliciet.

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; 

IsEmpty-functie

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

De gelinkte lijst testen

Hoewel access types niet synthetiseerbaar zijn, zijn ze ideaal voor verificatie. Een testbench demonstreert het gedrag van de gelinkte lijst.

Het package importeren

library work; use work.DataStructures.LinkedList; 

Een shared variable gebruiken

Signalen kunnen niet van protected type zijn, dus we gebruiken een shared variable om meerdere processen te laten interacteren met de lijst.

architecture sim of LinkedListTb is shared variable List : LinkedList; begin -- Testproces end architecture; 

Complete testbench

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; 

Volledig DataStructures-package

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; 

De test draaien

Wanneer uitgevoerd in ModelSim, toont de console:

# ** 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 

De output bevestigt dat de lijst waarden correct opslaat en ophaalt in FIFO-volgorde.