Como criar uma lista vinculada em VHDL

A lista vinculada é uma estrutura de dados dinâmica. Uma lista encadeada pode ser usada quando o número total de elementos não é conhecido antecipadamente. Ele cresce e diminui na memória, em relação ao número de itens que contém.

As listas vinculadas são implementadas de maneira mais conveniente usando classes em uma linguagem de programação orientada a objetos. O VHDL tem alguns recursos orientados a objetos que podem ser usados ​​para abstrair a complexidade da implementação do usuário.

Neste artigo vamos usar tipos de acesso, registros e tipos protegidos para implementar uma lista encadeada em VHDL. Vamos criar um novo pacote VHDL onde escreveremos todo o nosso código de lista encadeada.

Pacote

A primeira coisa que faremos é declarar um pacote que conterá nosso código. Um pacote VHDL é uma coleção de tipos, objetos ou subprogramas que podem ser importados para outro arquivo VHDL. A maioria dos módulos VHDL importa o pacote std_logic_1164 da biblioteca IEEE. Estamos criando nosso próprio pacote, bem parecido.

O conteúdo do nosso novo arquivo 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;

Mesmo que o pacote contenha apenas a implementação da lista vinculada, nós a provaremos no futuro nomeando-a DataStructures. Pode-se facilmente imaginar que alguém gostaria de adicionar outras estruturas de dados, como árvores ou mapas de hash, mais tarde.

Um pacote consiste em duas partes; uma região declarativa e um corpo. A região declarativa é onde você coloca tudo o que deve ficar visível para os usuários do pacote. O corpo tem escopo privado e não é acessível do lado de fora.

Tipo protegido

Os tipos protegidos são construções semelhantes a classes em VHDL. Eles podem conter subprogramas, declarações de tipo e variáveis. Um tipo protegido consiste em uma declaração pública e um órgão privado. Adicionaremos a declaração à declaração do pacote e o corpo ao corpo do pacote.

Nosso arquivo DataStructures.vhd após adicionar o 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;

Nomeamos o tipo protegido LinkedList porque ele conterá tudo relacionado à lista vinculada. Se adicionarmos outro tipo de estrutura de dados ao pacote, isso significaria outro tipo protegido.

Dentro da região declarativa do tipo protegido, declaramos três subprogramas. Ainda não há implementação, trataremos disso mais tarde. Para que os subprogramas sejam visíveis fora do tipo protegido, eles devem ser declarados aqui.

Os três subprogramas são os métodos de lista encadeada padrão:Push, Pop e IsEmpty. Push adiciona um novo elemento ao início da lista. Pop remove um elemento do final da lista. IsEmpty é uma função utilitária que retorna true se a lista estiver vazia.

Gravar

Um registro é um tipo composto que pode conter vários tipos de membros. Funciona como uma estrutura na linguagem de programação C. Quando um sinal ou variável é criado a partir do tipo de registro, os membros de dados podem ser referenciados usando o “.” notação. Por exemplo MyItem.Data .

Nossa declaração de registro no corpo do tipo protegido:

   type LinkedList is protected body

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

   end protected body;

Declaramos o tipo de registro no corpo do tipo protegido. A região declarativa de um tipo protegido não pode conter outros tipos ou declarações de sinal, então temos que declará-los no corpo do tipo protegido.

Isso não é um problema para nós porque Item é um tipo usado internamente. Não precisa ser visível do lado de fora. O usuário da lista encadeada deve acessá-la somente através dos três subprogramas declarados publicamente.

Nosso registro contém dois membros de dados; Dados e PróximoItem. Enquanto os dados são do tipo integer , NextItem é do tipo Ptr, por enquanto, misterioso.

Tipo de acesso

Os tipos de acesso são ponteiros VHDL. Ao usá-los, podemos criar objetos dinamicamente durante o tempo de execução. Declararemos um novo tipo de acesso chamado Ptr que apontará para um objeto criado dinamicamente do tipo Item.

O corpo do pacote com o novo tipo de acesso adicionado:

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;

Um nó de lista vinculada precisa conter uma referência ao próximo nó da lista. Implementamos isso no registro Item com o membro NextItem. É do tipo Ptr, que por sua vez é um ponteiro de volta para o tipo Item. Para evitar esse problema de galinha/ovo, primeiro declaramos Item como um tipo incompleto. Em seguida, declaramos o tipo Ptr como um ponteiro para o tipo incompleto. Por fim, especificamos a declaração completa do tipo Item.

A última coisa que fizemos foi declarar uma nova variável chamada Root do tipo Ptr. Esta será a raiz da lista vinculada. Se a lista estiver vazia, o valor de Root será null . Caso contrário, ele apontará para o primeiro item da lista.

Métodos de lista vinculada

Agora é hora de implementar os subprogramas que declaramos na região declarativa do tipo protegido. Eram o procedimento Push e as duas funções impuras:Pop e IsEmpty.

Colocaremos a implementação dos subprogramas dentro do corpo do tipo protegido.

Empurre

Push é o único dos subprogramas que é um procedimento. Funções em VHDL requerem um valor de retorno que não pode ser omitido. Para evitar o uso de um valor de retorno fictício, é preferível um procedimento.

O procedimento de empurrar:

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;

A primeira coisa que acontece é que um novo objeto do tipo Item é alocado dinamicamente. Isso é feito usando o new palavra-chave. Toda vez que o new palavra-chave é usada, a memória dinâmica é consumida pelo simulador.

O resto do código é apenas um algoritmo de lista encadeada padrão. O novo item é anexado ao final da lista ou se torna o item Raiz se a lista estiver vazia. Leia as listas vinculadas na Wikipedia se precisar de mais informações.

Pop

Pop remove o elemento mais antigo da lista e o devolve ao chamador. Se apenas removermos a referência ao elemento popped e o retornarmos, haverá perda de memória no simulador. Após a conclusão da chamada da função, a referência ao objeto criado dinamicamente é perdida para sempre.

Não há coleta de lixo em VHDL anterior ao VHDL-2017 (também conhecido como VHDL-2018 ou VHDL-2019). E o VHDL-2017 não é suportado pela maioria dos simuladores. Portanto, devemos chamar deallocate antes de retornar da função.

O deallocate O operador libera a memória usada por um objeto alocado dinamicamente. Para cada chamada para new , deve haver uma chamada para deallocate antes que a referência a um objeto seja excluída.

A função 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;

Depois de chamarmos deallocate , não podemos referenciar os dados apontados pela variável Node. Foi liberado pelo simulador. A solução é copiar os dados para uma variável local antes de liberar e, em seguida, retornar o valor da variável.

Está vazio

Verificar se a lista está vazia ou não pode ser feita simplesmente verificando se o nó raiz aponta para algo diferente de null:

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

Banco de teste

Para executar nosso código, precisaremos criar um testbench. Na verdade, a lista encadeada só pode ser usada em testbenches. Os tipos de acesso não são sintetizáveis, mas são muito úteis para fins de verificação.

Usando um pacote de biblioteca

No testbench, primeiro importamos o work biblioteca. Esta é a biblioteca padrão em VHDL e é onde reside nosso pacote DataStructures. Depois disso, podemos importar o tipo protegido LinkedList assim:

library work;
use work.DataStructures.LinkedList;

Variável compartilhada

Uma variável compartilhada é uma variável que pode ser acessada por vários processos. Ao contrário das variáveis ​​regulares que só podem ser declaradas dentro de um único processo, as variáveis ​​compartilhadas podem ser declaradas na região declarativa da arquitetura. Assim, eles têm o mesmo escopo que os sinais.

Temos que usar uma variável compartilhada porque não é possível declarar um sinal do tipo protegido. Se tentássemos, o ModelSim reclamaria:(vcom-1464) Declaração ilegal do sinal “List” do tipo work.DataStructures.LinkedList (type é um tipo protegido).

Declaramos a variável compartilhada do tipo LinkedList na região declarativa do testbench:

architecture sim of LinkedListTb is

   shared variable List : LinkedList;

begin

O código final para o testbench

Para testar nossas três funções de utilidade, criamos um novo processo. No processo, adicionamos um loop For que envia cinco inteiros para a lista vinculada. Por fim, esvaziamos a lista vinculada em um loop while que é executado até que nossa função IsEmpty retorne 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;

O código final para o pacote DataStructures

Depois de escrever todo o código sobre o qual falamos anteriormente neste artigo, o pacote DataStructures deve ficar assim:

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;

O resultado

A saída para o console do simulador quando pressionamos o botão de execução no 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 na impressão, cinco números inteiros são enviados para a lista vinculada. Em seguida, o loop While no testbench os retira da lista na ordem em que foram inseridos.