用VHDL受保护类型和访问指针实现动态链表

链表是一种动态数据结构，随元素增删而扩缩。VHDL的面向对象特性——访问类型、记录和受保护类型——使其能清晰高效地实现此结构。

创建DataStructures包

我们将所有链表逻辑封装在专用VHDL包DataStructures中。这个面向未来的名字便于日后扩展树、哈希图等结构。

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

VHDL包包含声明区（公共接口）和包体（私有实现）。声明区对用户可见；包体保持内部。

定义受保护类型

受保护类型在VHDL中如轻量级类。可包含子程序、类型声明和变量。我们定义名为LinkedList的受保护类型，暴露三个操作：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表示节点。记录包含数据载荷和指向下一节点的指针。

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

因受保护类型不能在声明区声明新类型，Item记录定义在包体内。

用访问类型处理指针

用访问类型Ptr动态引用Item实例。这种两步声明避免循环依赖。

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

根指针跟踪首节点。链表为空时Root为null。

variable Root : Ptr; 

实现链表操作

Push过程

追加新元素很简单：分配新Item，填充数据，链接到末尾。

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; 

Pop函数

移除首元素需谨慎内存管理。VHDL无垃圾回收（2017前），显式释放被移除节点。

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; 

IsEmpty函数

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

测试链表

虽访问类型不可综合，但非常适合验证。测试平台演示链表行为。

导入包

library work; use work.DataStructures.LinkedList; 

使用共享变量

信号不能是受保护类型，故用共享变量允许多进程与链表交互。

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

完整测试平台

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; 

DataStructures完整包

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; 

运行测试

在ModelSim执行时控制台显示：

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

输出确认链表正确按FIFO顺序存取值。