Implementando Lista Encadeada Dinâmica em VHDL com Tipos Protegidos e Ponteiros de Acesso

Uma lista encadeada é uma estrutura de dados dinâmica que se expande e contrai conforme elementos são adicionados ou removidos. Os recursos orientados a objetos do VHDL — tipos de acesso, records e tipos protegidos — tornam possível implementar esta estrutura de forma limpa e eficiente.

Criando o Pacote DataStructures

Encapsularemos toda a lógica da lista encadeada em um pacote VHDL dedicado chamado DataStructures. Este nome à prova de futuro permite fácil extensão para outras estruturas, como árvores ou hash maps, posteriormente.

package DataStructures is -- Declarações públicas vão aqui end package DataStructures; package body DataStructures is -- Declarações privadas e implementações vão aqui end package body DataStructures; 

Um pacote VHDL consiste em uma região declarativa (interface pública) e um corpo (implementação privada). A região declarativa é visível aos usuários; o corpo permanece interno.

Definindo um Tipo Protegido

Tipos protegidos funcionam como classes leves em VHDL. Eles podem conter subprogramas, declarações de tipo e variáveis. Definiremos um tipo protegido chamado LinkedList que expõe três operações: Push, Pop e 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; 

Introduzindo o Record Item

Dentro do corpo protegido, declaramos um record que representa um nó. O record contém a carga de dados e um ponteiro para o próximo nó.

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

Como tipos protegidos não podem declarar novos tipos na região declarativa, o record Item é definido dentro do corpo.

Manipulando Ponteiros com Tipos de Acesso

Usamos um tipo de acesso Ptr para referenciar instâncias de Item dinamicamente. Esta declaração em dois passos evita dependências circulares.

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

Um ponteiro raiz rastreia o primeiro nó. Quando a lista está vazia, Root é null.

variable Root : Ptr; 

Implementando Operações da Lista Encadeada

Procedimento Push

Adicionar um novo elemento é simples: alocar um novo Item, preenchê-lo e vinculá-lo no 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; 

Função Pop

Remover o primeiro elemento requer gerenciamento cuidadoso de memória. Como VHDL não tem coleta de lixo (pré-2017), desalocamos explicitamente o nó removido.

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; 

Função IsEmpty

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

Testando a Lista Encadeada

Embora tipos de acesso não sejam sintetizáveis, são ideais para verificação. Um testbench demonstra o comportamento da lista encadeada.

Importando o Pacote

library work; use work.DataStructures.LinkedList; 

Usando Variável Compartilhada

Sinais não podem ser de tipo protegido, então usamos uma variável compartilhada para permitir que múltiplos processos interajam com a lista.

architecture sim of LinkedListTb is shared variable List : LinkedList; begin -- Processo de teste 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; 

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

Executando o Teste

Quando executado no ModelSim, o console exibe:

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

A saída confirma que a lista armazena e recupera corretamente valores em ordem FIFO.