Dynamische verkettete Liste in VHDL mit Protected Types und Access-Pointern

Package DataStructures erstellen

Die gesamte Listenlogik wird in einem Package DataStructures gekapselt – erweiterbar für Bäume, Hash-Maps etc.

package DataStructures is
  -- Öffentliche Deklarationen
end package DataStructures;

package body DataStructures is
  -- Private Implementierung
end package body DataStructures;

Ein VHDL-Package besteht aus deklarativem Bereich (Schnittstelle) und Body (Implementierung).

Protected Type definieren

Protected Types verhalten sich wie leichte Klassen: Sie enthalten Subprogramme, Typdeklarationen, Variablen. Wir definieren LinkedList mit Operationen Push, Pop, 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;

Item-Record (Knoten)

Im Protected Body wird der Knoten als Record mit Nutzdaten und Next-Pointer deklariert.

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

Neue Typen können im deklarativen Bereich eines Protected Types nicht eingeführt werden – daher im Body.

Zeiger mit Access Types

Zweistufige Deklaration vermeidet Zirkelabhängigkeiten:

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

Wurzelzeiger Root : Ptr zeigt auf erstes Element; null bedeutet leere Liste.

Listen-Operationen implementieren

Push-Prozedur

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;

Neues Item am Listenende anhängen.

Pop-Funktion

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;

Erstes Element entfernen, Speicher explizit freigeben (kein Garbage Collection vor VHDL-2017).

IsEmpty-Funktion

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

Testbench

Package importieren

library work;
use work.DataStructures.LinkedList;

Shared Variable nutzen

Signale können nicht vom Protected Type sein – shared variable erlaubt Zugriff aus mehreren Prozessen.

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

Vollständige 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;

Komplettes 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;

Testlauf

ModelSim-Konsolenausgabe:

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

Die Liste speichert und liefert Werte in FIFO-Reihenfolge korrekt.