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 consist 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.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

2 thoughts on “How to create a Linked List in VHDL

  1. 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.

    Posted on January 18, 2019 at 10:19 pm
    1. You are quite right. I changed the text to “Pop removes the oldest element from the list and returns it to the caller”

      Posted on January 19, 2019 at 6:51 am