VHDLで保護型とアクセスポインタを用いた動的リンクリスト実装

リンクリストは、要素の追加・削除に応じて拡張・縮小する動的データ構造です。VHDLのオブジェクト指向機能（アクセス型、レコード、保護型）を用いると、この構造をクリーンかつ効率的に実装できます。

DataStructuresパッケージの作成

リンクロジックを専用VHDLパッケージDataStructuresにカプセル化します。この将来を見据えた名前により、後でツリーやハッシュマップなど他の構造へ容易に拡張可能です。

package DataStructures is
  -- 公開宣言
end package DataStructures;

package body DataStructures is
  -- 非公開宣言と実装
end package body DataStructures;

VHDLパッケージは宣言部（公開インターフェース）と本体（非公開実装）で構成されます。宣言部はユーザーから見え、本体は内部に隠蔽されます。

保護型の定義

保護型はVHDLにおける軽量クラスのようなもので、サブプログラム、型宣言、変数を含められます。LinkedListという保護型を定義し、Push、Pop、IsEmptyの3操作を公開します。

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;

アイテムレコードの導入

保護型本体内で、ノードを表すrecordを宣言します。レコードはデータペイロードと次のノードへのポインタを含みます。

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

保護型では宣言部で新しい型を宣言できないため、Itemレコードは本体内で定義します。

アクセス型でポインタを扱う

Itemインスタンスを動的に参照するため、アクセス型Ptrを使用します。この2段階宣言で循環依存を回避します。

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
  -- テストプロセス
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: Pushing 3
# ** Note: Popping 4
# ** Note: Popping 5

出力は、リストが値をFIFO順で正しく格納・取得することを確認しています。