Implementación de lista enlazada dinámica en VHDL con tipos protegidos y punteros de acceso

Una lista enlazada es una estructura de datos dinámica que se expande y contrae a medida que se añaden o eliminan elementos. Las características orientadas a objetos de VHDL —tipos de acceso, records y tipos protegidos— permiten implementar esta estructura de forma limpia y eficiente.

Creando el paquete DataStructures

Encapsularemos toda la lógica de la lista enlazada en un paquete VHDL dedicado llamado DataStructures. Este nombre a prueba de futuro permite una fácil extensión a otras estructuras como árboles o mapas hash más adelante.

package DataStructures is
  -- Declaraciones públicas van aquí
end package DataStructures;

package body DataStructures is
  -- Declaraciones privadas e implementaciones van aquí
end package body DataStructures;

Un paquete VHDL consiste en una región declarativa (interfaz pública) y un cuerpo (implementación privada). La región declarativa es visible para los usuarios; el cuerpo permanece interno.

Definiendo un tipo protegido

Los tipos protegidos actúan como clases ligeras en VHDL. Pueden contener subprogramas, declaraciones de tipo y variables. Definiremos un tipo protegido llamado LinkedList que expone tres operaciones: Push, Pop y 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;

Introduciendo el record Item

Dentro del cuerpo protegido declaramos un record que representa un nodo. El record contiene la carga de datos y un puntero al siguiente nodo.

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

Debido a que los tipos protegidos no pueden declarar nuevos tipos en la región declarativa, el record Item se define dentro del cuerpo.

Manejo de punteros con tipos de acceso

Usamos un tipo de acceso Ptr para referenciar instancias de Item dinámicamente. Esta declaración en dos pasos evita dependencias circulares.

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

Un puntero raíz rastrea el primer nodo. Cuando la lista está vacía, Root es null.

variable Root : Ptr;

Implementando operaciones de lista enlazada

Procedimiento Push

Añadir un nuevo elemento es sencillo: asignar un nuevo Item, poblarlo y enlazarlo al final.

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;

Función Pop

Eliminar el primer elemento requiere gestión cuidadosa de memoria. Como VHDL carece de recolección de basura (pre-2017), desasignamos explícitamente el nodo eliminado.

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;

Función IsEmpty

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

Probando la lista enlazada

Aunque los tipos de acceso no son sintetizables, son ideales para verificación. Un testbench demuestra el comportamiento de la lista enlazada.

Importando el paquete

library work;
use work.DataStructures.LinkedList;

Usando una variable compartida

Las señales no pueden ser de tipo protegido, así que usamos una variable compartida para permitir que múltiples procesos interactúen con la lista.

architecture sim of LinkedListTb is
  shared variable List : LinkedList;
begin
  -- Proceso de prueba
end architecture;

Testbench completo

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;

Paquete DataStructures completo

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;

Ejecutando la prueba

Cuando se ejecuta en ModelSim, la consola muestra:

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

La salida confirma que la lista almacena y recupera correctamente valores en orden FIFO.