The linked list is a dynamic data structure. A linked list can be used when the total number of elements is not known in advance. It grows and shrinks in memory, relative to the number of items it contains.
Linked lists are most conveniently implemented using classes in an object-oriented programming language. VHDL has some object-oriented features which can be used for abstracting away the complexity of the implementation from the user.
In this article we are going to use access types, records, and protected types to implement a linked list in VHDL. We are going to create a new VHDL package where we will write all of our linked list code.
Package
The first thing we will do is to declare a package which will contain our code. A VHDL package is a collection of types, objects, or subprograms that can be imported into another VHDL file. Most VHDL modules import the std_logic_1164 package from the IEEE library. We are creating our own package, much like it.
The contents of our new DataStructures.vhd file:
package DataStructures is -- Public declarations go here end package DataStructures; package body DataStructures is -- Private declarations and implementations go here end package body DataStructures;
Even though the package only will contain the linked list implementation, we will future-proof it by naming it DataStructures. One could easily imagine that someone would want to add other data structures like trees or hash maps to it later.
A package consists of two parts; a declarative region, and a body. The declarative region is where you put everything that should be visible to the users of the package. The body is privately scoped, and not accessible from the outside.
Protected type
Protected types are class-like constructs in VHDL. They can contain subprograms, type declarations, and variables. A protected type consists of a public declaration and a private body. We will add the declaration to the package declaration, and the body to the package body.
Our DataStructures.vhd file after adding the protected 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 named the protected type LinkedList because it will contain everything related to the linked list. If we were to add another kind of data structure to the package, that would mean another protected type.
Within the declarative region of the protected type, we have declared three subprograms. There is no implementation yet, we will come to that later. For the subprograms to be visible outside of the protected type, they have to be declared here.
The three subprograms are the standard linked list methods: Push, Pop, and IsEmpty. Push adds a new element to the start of the list. Pop removes an element from the end of the list. IsEmpty is a utility function that returns true if the list is empty.
Record
A record is a composite type that may contain multiple member types. It works kind of like a struct in the C programming language. When a signal or variable is created from the record type, the data members can be referenced by using the “.” notation. For instance MyItem.Data.
Our record declaration within the body of the protected type:
type LinkedList is protected body
type Item is record
Data : integer;
NextItem : Ptr;
end record;
end protected body;
We have declared the record type in the body of the protected type. The declarative region of a protected type cannot contain other type or signal declarations, so we have to declare them in the protected type body.
That’s not a problem for us because Item is an internally used type. It doesn’t need to be visible from the outside. The user of the linked list should access it only through the three publicly declared subprograms.
Our record contains two data members; Data and NextItem. While Data is of type integer, NextItem is of the, for now, mysterious Ptr type.
Access type
Access types are VHDL pointers. By using them, we can dynamically create objects during run-time. We will declare a new access type named Ptr that will point to a dynamically created object of the Item type.
The package body with the new access type added:
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;
A linked list node needs to contain a reference to the next node in the list. We have implemented this in the Item record with the NextItem member. It is of type Ptr, which in turn is a pointer back to the Item type. To avoid this chicken/egg problem, we first declare Item as an incomplete type. Then, we declare the Ptr type as a pointer to the incomplete type. Finally, we specify the full declaration of the Item type.
The last thing we did was to declare a new variable named Root of type Ptr. This will be the root of the linked list. If the list is empty, the value of Root will be null. Otherwise, it will point to the first item in the list.
Linked list methods
It is now time to implement the subprograms that we declared in the declarative region of the protected type. They were the Push procedure, and the two impure functions: Pop and IsEmpty.
We will place the implementation of the subprograms within the body of the protected type.
Push
Push is the only one of the subprograms which is a procedure. Functions in VHDL require a return value that cannot be omitted. To avoid using a dummy return value, a procedure is preferable.
The 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;
The first thing that happens is that a new object of type Item is dynamically allocated. This is done by using the new keyword. Every time the new keyword is used, dynamic memory is consumed by the simulator.
The rest of the code is just a standard linked list algorithm. The new item is appended to the end of the list, or it becomes the Root item if the list is empty. Read up on linked lists on Wikipedia if you need more background.
Pop
Pop removes the oldest element from the list and returns it to the caller. If we just remove the reference to the popped element and return it, there will be memory loss in the simulator. After the function call finishes, the reference to the dynamically created object is lost forever.
There is no garbage collection in VHDL prior to VHDL-2017 (also referred to as VHDL-2018 or VHDL-2019). And VHDL-2017 is unsupported by most simulators. Therefore, we must call deallocate before returning from the function.
The deallocate operator frees the memory used by a dynamically allocated object. For every call to new, there should be a call to deallocate before the reference to an object is deleted.
The Pop function:
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;
After we have called deallocate, we cannot reference the data pointed to by the Node variable. It has been free’d by the simulator. The solution is to copy the data to a local variable before freeing, and then return the value of the variable.
IsEmpty
Checking if the list is empty or not can simply be accomplished by checking if the root node points to something other than null:
impure function IsEmpty return boolean is begin return Root = null; end;
Testbench
To run our code, we will need to create a testbench. Actually, the linked list can only be used in testbenches. Access types are not synthesizable, but they are very useful for verification purposes.
Using a library package
In the testbench, we first import the work library. This is the default library in VHDL, and this is where our DataStructures package resides. After that, we can import the LinkedList protected type like this:
library work; use work.DataStructures.LinkedList;
Shared variable
A shared variable is a variable that can be access by several processes. Unlike regular variables which can only be declared within a single process, shared variables can be declared in the declarative region of the architecture. Thus, they have the same scope as signals.
We have to use a shared variable because it isn’t possible to declare a signal of protected type. If we tried, ModelSim would complain: (vcom-1464) Illegal declaration of signal “List” of type work.DataStructures.LinkedList (type is a protected type).
We declare the shared variable of type LinkedList in the declarative region of the testbench:
architecture sim of LinkedListTb is shared variable List : LinkedList; begin
The final code for the testbench
To test our three utility functions, we create a new process. In the process, we add a For-loop that pushes five integers to the linked list. Finally, we empty the linked list in a While-loop that runs until our IsEmpty function returns 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;
The final code for the DataStructures package
After writing all of the code that we previously talked about in this article, the DataStructures package should look like this:
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;
The result
The output to the simulator console when we press the run button in 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
As we can see from the printout, five integers are pushed to the linked list. Then, the While-loop in the testbench pops them from the list in the order that they were inserted.
Your implementation of Pop() does not match your definition:
“Pop removes the last element from the list and returns it to the caller.”
The implementation returns the current root which results in the popped values being in pushed order rather than in reverse.
You are quite right. I changed the text to “Pop removes the oldest element from the list and returns it to the caller”
Hi Jonas,
This tutorial has been most helpful in my understanding of a linked list in VHDL.
For my own implementation in a testbench I would like to use an array of linked lists. However, I cannot get my head around how to write the VHDL for this. I tried to declare a new type as an array of the LinkedList type.
This causes an error in the ModelSim compiler: ” An element of a protected type (LinkedList) is not allowed in a composite type”
Do you have any suggestions on how to create an array of linked lists?
Hello Filip,
Arrays of protected type are only possible in VHDL-2019. See the Composites of protected types section in my article about what’s new in VHDL-2019.
But you can emulate it by creating another protected type in a package. I will make a blog post about that later, but I’m afraid it may be too late for your application.
Hi Jonas,
Thanks for your reply.
I inherited a project where a linked list was created within the architecture of the testbench and not using a package. In this way it seems also possible to create an array of these linked lists. However, readability and maintainability of this code is ‘not optimal’.
As I was not familiar with linked lists in VHDL at all I did a search on the web which led me to your very helpful site.
For future projects I’m still very interested in that new blog post!
Hello Filip,
I investigated this further, and I found it impossible to create an array of protected types.
The problem is that you can’t create a composite type (like an array or record) containing a protected type. And the object pointed to by an access type cannot be of a protected type.
Therefore, there’s no way that we can dynamically store a collection of protected type objects. The only way is to explicitly declare N shared variables, as shown below.
If you need an array of linked lists, you can modify the original linked list code. You can’t use it as elements in another dynamic list for the reasons I mentioned.
You can solve it by adding another level of records and pointers, as shown below. You will have to invent some subprograms to manage the new data structure.
Is there a way to declare data as a void pointer like *void in c? This will allow more flexibility in the data structure.
Hi Jonas,
Is the Root ptr not required to be initialized to null (as added, below, to your example), so that the list is empty upon creation?
Since your example didn’t include initialization, does this mean that the VHDL standard specifies that the initial value of an access types is to be null? Or is this simulator dependent?
-- Root of the linked list variable Root : Ptr := null;It should be
nullinitially in any simulator, but it doesn’t hurt to be explicit. 🙂 Not everybody knows that the VHDL language reference manual says that: “The nullvalue of an access type is the default initial value of the type.”
Nice post, liked it a lot.
In the example, Data is always integer.
If I would need several linked lists for several data types, I would haveto rewrite several times the same code but changing the Data integer to a different one.
Is there any way to have a linked list code that would work for any type, not only integer?
Yes, you can use package generics to store any data type in the list. The package declaration would look something like this:
package generic_list is generic(type data_type); type generic_list is protected ... end protected; end package;But you can’t use this list directly in your testbench because the
data_typegeneric must be given a specific value. You can do that by creating a new VHDL package for each type you want to store.For example, create an integer_list.vhd file with this content:
Then you can import the new integer list package in your main testbench and create an object from it:
Read more in the Generic list – User manual.pdf which you can download from here:
VHDL package: Generic list of protected type
Hello Jonas,
Thanks very much for all your succinct VHDL posts. Learning a lot. I am new to OOP. Mainly a Verilog/SystemVerilog/Assertions/VHDL design engineer. Hence, my questions are very basic and hope they make sense.
In the push procedure or pop function, what is “Node”? Which part of linked list is Node?
Also,
In the push procedure, if Root is null, then Root points to the same address where NewItem is pointing to “Root := NewItem;” . Pointer address is copied, not the data at the pointer. Correct? If Root is not null, then we do “Node := Root”. So, now the Node pointer is pointing to where the Root is pointing to (I consider this assignment as copy of the pointer and not the data pointed to). In that case, why can’t you have (since Node and Root are pointing to the same address location).
while Root.NextItem /= null loop Root:= Root.NextItem; end loop; Root.NextItem := NewItem;Also, could you please explain the pop function? I don’t understand Root := Root.NextItem; Pop pops an Item from the end of the list. So, don’t understand this Root assignment. Also, what if Root is null when you try to pop?
Bear with me if my terminology/explanation does not make sense. Very new to OOP.
Thanks very much.
Ashok
p.s. Maybe you can create a paid advanced post on OOP aspects of VHDL. Access Type, Protected Types, Linked List etc. There isn’t much on web when it comes to OOP and VHDL.
Hello Ashok,
It’s nice to hear that you found my blog post to be interesting! Now, let me try to answer your questions.
The
Nodevariable is a pointer to an Item record stored in the simulator’s dynamic memory (created at run-time). Below you can see the declaration of the record andPtrpointer, which is theNodevariable’s type.type Item; type Ptr is access Item; type Item is record Data : integer; NextItem : Ptr; end record;We use the
Nodevariable in the procedures to traverse the linked list.Yes,
RootandNewItemare now pointing to the same location in the simulator’s dynamic memory.We can’t do that because then we overwrite the pointer to the start of the list. Yes, we can insert the new item as the last position, but then
Rootis pointing to the last item, and we cannot access the first element.Rootis always supposed to point to the oldest element in the list.If you try to pop when
Rootis null you get a null pointer error in the simulator. The user of the list should always call theIsEmptyfunction before popping.If you want to make it even more verbose, you can add an assertion at the beginning of the
Popfunction. Something like this:Hi Jonas,
Thanks very much for the explanation. Fog is clearing.
Last question though. In the Pop function, you have
[vhdl]
Node := Root;
Root := Root.NextItem;
RetVal := Node.Data;
[\vhdl]
As I understand, you are assigning Node := Root meaning Node is now pointing to the start of the list and Root is assigned to the next (second) item in the list. Then when you call Pop again, Root points to the second item which is assigned to Node and Node extracts value from the second item. My question is, this looks like we are popping values from the start of the list. I had thought that we should be popping from the end of the list (FIFO).
Thanks again for your help.
Ashok
Hello Ashok,
Yes, you can pop from any side of the list. As long as you insert at the other end it will behave as a FIFO. If you push to and pop from the same end, it will be a stack.
It comes down to personal preference if you want the oldest element to be at the root or not.
Hi Jonas,
Thanks for further explanation. I am much farther ahead. Have created my own working examples. My FIFO example successfully writes/reads from FIFO. But even though I know how to create such lists, there is one question that I am not clear on.
When we declare the following:
variable Root : Ptr;
We say that “the Root pointer now points to the first node in the list”. Root is a pointer and not a node (exists in Stack and not heap).
My question is how does the Root/head pointer point to the first node in the list? Where is the list? We haven’t created one. All we have done is declare the variable Root.
Then, (later in the code), we say that
variable Node : Ptr;
So, shouldn’t the variable Node also point to the first node in the list? It is also declared just as the Root variable is declared.
Then we say:
Node := Root;
Which means the Node pointer also points to the first node in the list; same address where Root is pointing to.
So, the question is what does “Node := Root” mean; if both Node and Root are already pointing to the first item in the list?
Just a basic stumbling block. Thanks in advance for your clarification.
Sorry about the late reply. You’ve probably figured it out already.
This list resizes itself dynamically when we add elements to it. In the beginning, the list is empty, and the Root variable will point to a Null (no object). Then, when we add new items, the list grows indefinitely, and the new items are stored in the simulator’s memory. Thus, the list isn’t synthesizable. It’s only for use in testbenches.
Every time we use the “new” keyword, a new element is created in the simulator’s memory:
It’s a generic linked list, and you can read more about this data structure on Wikipedia: https://en.wikipedia.org/wiki/Linked_list
Hi Jonas.
How would you write a function for the protected type to return a pointer to the root of list for the purpose of “copying” the list?
If a PTR type is returned from such a function, this means that the PTR type has to be defined in the declarative part of the protective type, which isn’t allowed.
Hello Paul,
That wouldn’t work because you can’t return an access type (pointer) from a protected type method.
OK, thanks Jonas.