How to create a linked list in VHDL

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.

Jonas Julian Jensen

I’m from Norway, but I live in Bangkok, Thailand. Before I started VHDLwhiz, I worked as an FPGA engineer in the defense industry. I earned my master’s degree in informatics at the University of Oslo.

In-depth

How the AXI-style ready/valid handshake works

ByJonas Julian Jensen September 2, 2022September 3, 2022

The ready/valid hardware data transfer protocol is simple and ingenious, providing flow control with only two control signals. The rules are straightforward: data transfer only happens when both ready and valid are ‘1’ during the same clock cycle.

Opinion

Why you always need a testbench

ByJonas Julian Jensen April 11, 2019October 18, 2020

As most hardware engineers, I started off my computer science career by learning a sequential programming language. The first language I learned at the University of Oslo was Java. While it’s not considered to be the most exciting language today, at the time, Java was at the pinnacle of its popularity. The engineers who built…

Tutorial

How to use the most common VHDL type: std_logic

ByJonas Julian Jensen August 22, 2017August 10, 2024

The most common type used in VHDL is the std_logic. Think of this type as a single bit, the digital information carried by a single physical wire. The std_logic gives us a more fine-grained control over the resources in our design than the integer type, which we have been using in the previous tutorials. Normally,…

In-depth

Using the ‘stable and ‘quiet attributes in VHDL

ByJonas Julian Jensen October 4, 2021October 29, 2021

The ‘stable and ‘quiet attributes are predefined in the VHDL standard and work on signal objects. We can use these special features in simulation to check that a signal’s value remains untouched for a given period.

In-depth

Delta cycles explained

ByJonas Julian Jensen October 23, 2018October 28, 2023

Delta cycles are non-time-consuming timesteps used by VHDL simulators for modeling events during execution of VHDL code. They are events that happen in zero simulation time after a preceding event. VHDL is a parallel programming language, while computers and CPUs work in a sequential manner. When a normal programming language is run, the CPU executes…

In-depth

Entity instantiation and component instantiation

ByJonas Julian Jensen September 24, 2020October 8, 2020

There are two ways to instantiate a module in VHDL: component instantiation and entity instantiation. Some people refer to the latter as direct instantiation. Entity instantiation didn’t exist in the first revisions VHDL, but it has been available since VHDL’93. This is the method that I recommend unless you have specific reasons to use component…

20 Comments

Ryan Tennill says:

January 18, 2019 at 22:19

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.

Reply
1. Jonas Julian Jensen says:
  
  January 19, 2019 at 06:51
  
  You are quite right. I changed the text to “Pop removes the oldest element from the list and returns it to the caller”
  
  Reply
Filip Fontaine says:

November 2, 2020 at 12:52
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.
```
 type ListArray is array (0 to 7) of LinkedList;
 
```
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?
Reply
1. Jonas Julian Jensen says:
  
  November 8, 2020 at 12:22
  
  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.
  
  Reply
  1. Filip Fontaine says:
    
    November 24, 2020 at 10:43
    
    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!
    
    Reply
    1. Jonas Julian Jensen says:
      
      December 5, 2020 at 09:43
      
      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.
      
      package body protected_t_arr is shared variable item1 : LinkedList; shared variable item2 : LinkedList; shared variable item3 : LinkedList; -- And so on.. type protected_t_arr is protected body
      
      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.
      
      type LinkedListItem; type LinkedListPtr is access LinkedListItem; type LinkedListItem is record Data : integer; NextItem : LinkedListPtr; end record; type ArrayItem; type ArrayPtr is access ArrayItem; type ArrayItem is record Data : LinkedListItem; NextItem : ArrayPtr; end record;
      
      Reply
Elik Livnat says:

April 22, 2021 at 21:41

Is there a way to declare data as a void pointer like *void in c? This will allow more flexibility in the data structure.

Reply
Paul Urbanus says:

February 21, 2022 at 14:13
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;
```
Reply
1. Jonas Julian Jensen says:
  
  February 21, 2022 at 16:08
  
  It should be null initially in any simulator, but it doesn’t hurt to be explicit. 🙂 Not everybody knows that the VHDL language reference manual says that: “The null
  value of an access type is the default initial value of the type.”
  
  Reply
Eustaquio says:

March 1, 2022 at 23:38

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?

Reply
1. Jonas Julian Jensen says:
  
  March 2, 2022 at 07:49
  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_type generic 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:
```
package integer_list is new work.generic_list
  generic map(integer);
```
  Then you can import the new integer list package in your main testbench and create an object from it:
```
use work.integer_list.all;

entity my_tb is
end my_tb;

architecture sim of my_tb is

  shared variable list : generic_list;
```
  Read more in the Generic list – User manual.pdf which you can download from here:
  VHDL package: Generic list of protected type
  Reply
Ashok Mehta says:

March 12, 2022 at 22:44
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.
Reply
1. Jonas Julian Jensen says:
  
  March 13, 2022 at 13:05
  Hello Ashok,
  
  It’s nice to hear that you found my blog post to be interesting! Now, let me try to answer your questions.
  
  In the push procedure or pop function, what is “Node”? Which part of linked list is Node?
  
  The Node variable 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 and Ptr pointer, which is the Node variable’s type.
```
     type Item;
      type Ptr is access Item;
      type Item is record
         Data : integer;
         NextItem : Ptr;
      end record;
```
  We use the Node variable in the procedures to traverse the linked list.
  
  “Root := NewItem;” . Pointer address is copied, not the data at the pointer. Correct?
  
  Yes, Root and NewItem are now pointing to the same location in the simulator’s dynamic memory.
  
  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;
  
  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 Root is pointing to the last item, and we cannot access the first element. Root is always supposed to point to the oldest element in the list.
  
  Also, what if Root is null when you try to pop?
  
  If you try to pop when Root is null you get a null pointer error in the simulator. The user of the list should always call the IsEmpty function before popping.
  
  If you want to make it even more verbose, you can add an assertion at the beginning of the Pop function. Something like this:
```
assert Root /= null
  report "Pop attempt while the list is empty"
  severity failure;
```
  Reply
  1. Ashok says:
    
    March 13, 2022 at 16:56
    
    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
    
    Reply
    1. Jonas Julian Jensen says:
      
      March 20, 2022 at 04:58
      
      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.
      
      Reply
      1. Ashok says:
        
        February 4, 2023 at 18:37
        
        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.
      2. Jonas Julian Jensen says:
        
        February 18, 2023 at 04:10
        
        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:
        
        NewItem := new Item;
        
        It’s a generic linked list, and you can read more about this data structure on Wikipedia: https://en.wikipedia.org/wiki/Linked_list
Paul F says:

April 7, 2022 at 07:55

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.

Reply
1. Jonas Julian Jensen says:
  
  April 13, 2022 at 06:06
  
  Hello Paul,
  
  That wouldn’t work because you can’t return an access type (pointer) from a protected type method.
  
  Reply
  1. Paul F says:
    
    April 13, 2022 at 12:54
    
    OK, thanks Jonas.
    
    Reply

Package

Protected type

Record

Access type

Linked list methods

Push

Pop

IsEmpty

Testbench

Using a library package

Shared variable

The final code for the testbench

The final code for the DataStructures package

The result

Similar Posts

20 Comments

Leave a Reply Cancel reply