如何在 VHDL 中创建链接列表

链表是一种动态数据结构。当事先不知道元素的总数时，可以使用链表。它在内存中的增长和收缩，相对于它包含的项目数。

使用面向对象编程语言中的类最方便地实现链表。 VHDL 具有一些面向对象的特性，可用于从用户那里抽象出实现的复杂性。

在本文中，我们将使用访问类型、记录和受保护类型在 VHDL 中实现链表。我们将创建一个新的 VHDL 包，我们将在其中编写所有链表代码。

包

我们要做的第一件事是声明一个包含我们代码的包。 VHDL 包是可以导入另一个 VHDL 文件的类型、对象或子程序的集合。大多数 VHDL 模块从 IEEE 库中导入 std_logic_1164 包。我们正在创建自己的包，就像它一样。

我们新的 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;

尽管该包仅包含链表实现，但我们将通过将其命名为 DataStructures 来保证它的未来。可以很容易地想象，以后有人会想向其中添加其他数据结构，例如树或哈希映射。

一个包由两部分组成；一个声明性区域和一个主体。声明性区域是您放置包的用户应该可见的所有内容的地方。正文是私有范围的，不能从外部访问。

受保护的类型

受保护类型是 VHDL 中的类结构。它们可以包含子程序、类型声明和变量。受保护类型由公共声明和私有主体组成。我们将声明添加到包声明中，并将主体添加到包主体中。

添加受保护类型后我们的 DataStructures.vhd 文件：

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;

我们将受保护类型命名为 LinkedList，因为它将包含与链表相关的所有内容。如果我们要在包中添加另一种数据结构，那就意味着另一种受保护的类型。

在受保护类型的声明区域内，我们声明了三个子程序。目前还没有实现，我们稍后会谈到。为了使子程序在受保护类型之外可见，它们必须在此处声明。

这三个子程序是标准的链表方法：Push、Pop 和 IsEmpty。 Push 将一个新元素添加到列表的开头。 Pop 从列表末尾删除一个元素。 IsEmpty 是一个实用函数，它返回 true 如果列表为空。

记录

记录是一种复合类型，可能包含多个成员类型。它的工作方式有点像 C 编程语言中的结构。当从记录类型创建信号或变量时，可以使用“.”来引用数据成员。符号。例如 MyItem.Data .

我们在受保护类型体内的记录声明：

   type LinkedList is protected body

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

   end protected body;

我们已经在受保护类型的主体中声明了记录类型。受保护类型的声明区域不能包含其他类型或信号声明，因此我们必须在受保护类型体中声明它们。

这对我们来说不是问题，因为 Item 是内部使用的类型。它不需要从外面看到。链表的用户只能通过三个公开声明的子程序访问它。

我们的记录包含两个数据成员；数据和 NextItem。而数据的类型是 integer , NextItem 目前属于神秘的 Ptr 类型。

访问类型

访问类型是 VHDL 指针。通过使用它们，我们可以在运行时动态创建对象。我们将声明一个名为 Ptr 的新访问类型，它将指向 Item 类型的动态创建的对象。

添加了新访问类型的包体：

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;

链表节点需要包含对链表中下一个节点的引用。我们已经在带有 NextItem 成员的 Item 记录中实现了这一点。它是 Ptr 类型，而 Ptr 又是指向 Item 类型的指针。为了避免这种先有鸡还是先有蛋的问题，我们首先将 Item 声明为不完整类型。然后，我们将 Ptr 类型声明为指向不完整类型的指针。最后，我们指定Item类型的完整声明。

我们做的最后一件事是声明一个名为 Root 且类型为 Ptr 的新变量。这将是链表的根。如果列表为空，则 Root 的值为 null .否则，它将指向列表中的第一项。

链表方法

现在是时候实现我们在受保护类型的声明区域中声明的子程序了。它们是 Push 过程，以及两个不纯函数：Pop 和 IsEmpty。

我们将子程序的实现放在受保护类型的主体中。

推

Push 是唯一一个是过程的子程序。 VHDL 中的函数需要一个不能省略的返回值。为避免使用虚拟返回值，最好使用过程。

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;

发生的第一件事是动态分配了一个 Item 类型的新对象。这是通过使用 new 关键词。每次new 使用关键字，动态内存被模拟器消耗。

其余的代码只是一个标准的链表算法。新项目被附加到列表的末尾，或者如果列表为空，它将成为根项目。如果您需要更多背景知识，请阅读 Wikipedia 上的链接列表。

流行音乐

Pop 从列表中删除最旧的元素并将其返回给调用者。如果我们只是删除对弹出元素的引用并返回它，模拟器中会出现内存丢失。函数调用完成后，对动态创建的对象的引用将永远丢失。

在 VHDL-2017（也称为 VHDL-2018 或 VHDL-2019）之前的 VHDL 中没有垃圾收集。大多数模拟器不支持 VHDL-2017。因此，我们必须调用 deallocate 在从函数返回之前。

deallocate 运算符释放动态分配的对象使用的内存。每次调用 new ，应该调用 deallocate 在对象的引用被删除之前。

弹出功能：

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;

在我们调用了deallocate之后，我们无法引用 Node 变量所指向的数据。它已被模拟器释放。解决方法是在释放前先将数据复制到一个局部变量中，然后返回该变量的值。

IsEmpty

检查列表是否为空可以简单地通过检查根节点是否指向非空值来完成：

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

测试台

要运行我们的代码，我们需要创建一个测试平台。实际上，链表只能在测试平台中使用。访问类型不可综合，但它们对于验证目的非常有用。

使用库包

在测试台中，我们首先导入work 图书馆。这是 VHDL 中的默认库，也是我们的 DataStructures 包所在的位置。之后，我们可以像这样导入 LinkedList 保护类型：

library work;
use work.DataStructures.LinkedList;

共享变量

共享变量是可以被多个进程访问的变量。与只能在单个进程中声明的常规变量不同，共享变量可以在体系结构的声明区域中声明。因此，它们与信号具有相同的范围。

我们必须使用共享变量，因为不可能声明受保护类型的信号。如果我们尝试，ModelSim 会抱怨：(vcom-1464) 非法声明类型为 work.DataStructures.LinkedList 的信号“List”（类型是受保护的类型）。

我们在测试台的声明区声明了 LinkedList 类型的共享变量：

architecture sim of LinkedListTb is

   shared variable List : LinkedList;

begin

测试平台的最终代码

为了测试我们的三个效用函数，我们创建了一个新进程。在这个过程中，我们添加了一个将五个整数推送到链表的 For 循环。最后，我们在 While 循环中清空链表，直到 IsEmpty 函数返回 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;

DataStructures 包的最终代码

在写完我们之前在本文中谈到的所有代码之后，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 中按下运行按钮时输出到模拟器控制台：

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

从打印输出中我们可以看到，五个整数被推送到链表中。然后，测试台中的 While 循环按插入顺序将它们从列表中弹出。

如何创建自检测试平台基本 VHDL 测验 - 第 4 部分

VHDL