Cómo crear una lista enlazada en VHDL

La lista enlazada es una estructura de datos dinámica. Se puede utilizar una lista enlazada cuando no se conoce de antemano el número total de elementos. Crece y se reduce en la memoria, en relación con la cantidad de elementos que contiene.

Las listas enlazadas se implementan más convenientemente usando clases en un lenguaje de programación orientado a objetos. VHDL tiene algunas funciones orientadas a objetos que se pueden usar para abstraer al usuario de la complejidad de la implementación.

En este artículo vamos a utilizar tipos de acceso, registros y tipos protegidos para implementar una lista enlazada en VHDL. Vamos a crear un nuevo paquete VHDL donde escribiremos todo nuestro código de lista enlazada.

Paquete

Lo primero que haremos será declarar un paquete que contendrá nuestro código. Un paquete VHDL es una colección de tipos, objetos o subprogramas que se pueden importar a otro archivo VHDL. La mayoría de los módulos VHDL importan el paquete std_logic_1164 de la biblioteca IEEE. Estamos creando nuestro propio paquete, muy parecido.

El contenido de nuestro nuevo archivo DataStructures.vhd:

package DataStructures is
   -- Public declarations go here
end package DataStructures;
 
package body DataStructures is
   -- Private declarations and implementations go here
end package body DataStructures;

Aunque el paquete solo contendrá la implementación de la lista enlazada, lo prepararemos para el futuro llamándolo DataStructures. Uno podría imaginar fácilmente que alguien querría agregarle otras estructuras de datos como árboles o mapas hash más tarde.

Un paquete consta de dos partes; una región declarativa, y un cuerpo. La región declarativa es donde coloca todo lo que debería ser visible para los usuarios del paquete. El cuerpo es de ámbito privado y no se puede acceder a él desde el exterior.

Tipo protegido

Los tipos protegidos son construcciones similares a clases en VHDL. Pueden contener subprogramas, declaraciones de tipos y variables. Un tipo protegido consta de una declaración pública y un organismo privado. Agregaremos la declaración a la declaración del paquete y el cuerpo al cuerpo del paquete.

Nuestro archivo DataStructures.vhd después de agregar el tipo protegido:

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;

Nombramos el tipo protegido LinkedList porque contendrá todo lo relacionado con la lista vinculada. Si tuviéramos que agregar otro tipo de estructura de datos al paquete, eso significaría otro tipo protegido.

Dentro de la región declarativa del tipo protegido, hemos declarado tres subprogramas. Todavía no hay implementación, hablaremos de eso más adelante. Para que los subprogramas sean visibles fuera del tipo protegido, deben declararse aquí.

Los tres subprogramas son los métodos de lista enlazada estándar:Push, Pop y IsEmpty. Push agrega un nuevo elemento al comienzo de la lista. Pop elimina un elemento del final de la lista. IsEmpty es una función de utilidad que devuelve true si la lista está vacía.

Grabar

Un registro es un tipo compuesto que puede contener varios tipos de miembros. Funciona como una estructura en el lenguaje de programación C. Cuando se crea una señal o variable a partir del tipo de registro, se puede hacer referencia a los miembros de datos utilizando el “.” notación. Por ejemplo MyItem.Data .

Nuestra declaración de registro dentro del cuerpo del tipo protegido:

   type LinkedList is protected body

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

   end protected body;

Hemos declarado el tipo de registro en el cuerpo del tipo protegido. La región declarativa de un tipo protegido no puede contener declaraciones de otro tipo o señal, por lo que debemos declararlas en el cuerpo del tipo protegido.

Eso no es un problema para nosotros porque Item es un tipo de uso interno. No es necesario que sea visible desde el exterior. El usuario de la lista enlazada debe acceder a ella solo a través de los tres subprogramas declarados públicamente.

Nuestro registro contiene dos miembros de datos; Datos y NextItem. Mientras que los datos son de tipo integer , NextItem es del, por ahora, misterioso tipo Ptr.

Tipo de acceso

Los tipos de acceso son punteros VHDL. Usándolos, podemos crear objetos dinámicamente durante el tiempo de ejecución. Declararemos un nuevo tipo de acceso llamado Ptr que apuntará a un objeto creado dinámicamente del tipo Item.

El cuerpo del paquete con el nuevo tipo de acceso agregado:

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;

Un nodo de lista enlazada debe contener una referencia al siguiente nodo de la lista. Hemos implementado esto en el registro del artículo con el miembro NextItem. Es de tipo Ptr, que a su vez es un puntero al tipo Item. Para evitar este problema del huevo y la gallina, primero declaramos Item como un tipo incompleto. Luego, declaramos el tipo Ptr como un puntero al tipo incompleto. Finalmente, especificamos la declaración completa del tipo de artículo.

Lo último que hicimos fue declarar una nueva variable llamada Raíz de tipo Ptr. Esta será la raíz de la lista enlazada. Si la lista está vacía, el valor de Root será null . De lo contrario, apuntará al primer elemento de la lista.

Métodos de lista enlazada

Ahora es el momento de implementar los subprogramas que declaramos en la región declarativa del tipo protegido. Eran el procedimiento Push y las dos funciones impuras:Pop y IsEmpty.

Colocaremos la implementación de los subprogramas dentro del cuerpo del tipo protegido.

Empujar

Push es el único de los subprogramas que es un procedimiento. Las funciones en VHDL requieren un valor de retorno que no se puede omitir. Para evitar el uso de un valor de retorno ficticio, es preferible un procedimiento.

El procedimiento Push:

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;

Lo primero que ocurre es que se asigna dinámicamente un nuevo objeto de tipo Item. Esto se hace usando el new palabra clave. Cada vez que el new se utiliza la palabra clave, el simulador consume la memoria dinámica.

El resto del código es solo un algoritmo de lista enlazada estándar. El nuevo elemento se agrega al final de la lista o se convierte en el elemento raíz si la lista está vacía. Lea las listas vinculadas en Wikipedia si necesita más información.

pop

Pop elimina el elemento más antiguo de la lista y se lo devuelve a la persona que llama. Si simplemente eliminamos la referencia al elemento emergente y lo devolvemos, habrá pérdida de memoria en el simulador. Una vez que finaliza la llamada a la función, la referencia al objeto creado dinámicamente se pierde para siempre.

No hay recolección de basura en VHDL antes de VHDL-2017 (también conocido como VHDL-2018 o VHDL-2019). Y VHDL-2017 no es compatible con la mayoría de los simuladores. Por lo tanto, debemos llamar a deallocate antes de regresar de la función.

El deallocate El operador libera la memoria utilizada por un objeto asignado dinámicamente. Por cada llamada a new , debería haber una llamada a deallocate antes de que se elimine la referencia a un objeto.

La función Pop:

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;

Después de haber llamado deallocate , no podemos hacer referencia a los datos a los que apunta la variable Nodo. Ha sido liberado por el simulador. La solución es copiar los datos a una variable local antes de liberarlos y luego devolver el valor de la variable.

Está vacío

Comprobar si la lista está vacía o no se puede lograr simplemente comprobando si el nodo raíz apunta a algo que no sea nulo:

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

Banco de pruebas

Para ejecutar nuestro código, necesitaremos crear un banco de pruebas. En realidad, la lista enlazada solo se puede usar en bancos de prueba. Los tipos de acceso no son sintetizables, pero son muy útiles para propósitos de verificación.

Usando un paquete de biblioteca

En el banco de pruebas, primero importamos el work biblioteca. Esta es la biblioteca predeterminada en VHDL, y aquí es donde reside nuestro paquete DataStructures. Después de eso, podemos importar el tipo protegido LinkedList así:

library work;
use work.DataStructures.LinkedList;

Variable compartida

Una variable compartida es una variable a la que pueden acceder varios procesos. A diferencia de las variables regulares que solo se pueden declarar dentro de un solo proceso, las variables compartidas se pueden declarar en la región declarativa de la arquitectura. Por lo tanto, tienen el mismo alcance que las señales.

Tenemos que usar una variable compartida porque no es posible declarar una señal de tipo protegido. Si lo intentáramos, ModelSim se quejaría:(vcom-1464) Declaración ilegal de la señal "Lista" de tipo work.DataStructures.LinkedList (el tipo es un tipo protegido).

Declaramos la variable compartida de tipo LinkedList en la región declarativa del banco de pruebas:

architecture sim of LinkedListTb is

   shared variable List : LinkedList;

begin

El código final para el banco de pruebas

Para probar nuestras tres funciones de utilidad, creamos un nuevo proceso. En el proceso, agregamos un For-loop que empuja cinco enteros a la lista enlazada. Finalmente, vaciamos la lista enlazada en un ciclo While que se ejecuta hasta que nuestra función IsEmpty devuelve 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;

El código final para el paquete DataStructures

Después de escribir todo el código del que hablamos anteriormente en este artículo, el paquete DataStructures debería verse así:

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;

El resultado

La salida a la consola del simulador cuando presionamos el botón ejecutar en 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

Como podemos ver en la impresión, cinco números enteros se envían a la lista enlazada. Luego, el bucle While en el banco de pruebas los saca de la lista en el orden en que fueron insertados.