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 という名前を付けることで、将来的に保証します。誰かがツリーやハッシュマップなどの他のデータ構造を後で追加したいと思うことは容易に想像できます。

パッケージは 2 つの部分で構成されます。宣言領域、および本体。宣言領域は、パッケージのユーザーに表示される必要があるすべてのものを配置する場所です。本文はプライベートスコープであり、外部からアクセスすることはできません。

保護された型

保護された型は、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 という名前を付けました。別の種類のデータ構造をパッケージに追加する場合、それは別の保護された型を意味します。

保護された型の宣言領域内で、3 つのサブプログラムを宣言しました。まだ実装はありません。後で説明します。サブプログラムが保護された型の外で見えるようにするには、ここで宣言する必要があります。

Push、Pop、および IsEmpty の 3 つのサブプログラムは、標準のリンクリストメソッドです。プッシュは、リストの先頭に新しい要素を追加します。 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 は内部で使用される型であるため、これは問題ではありません。外から見える必要はありません。リンクリストのユーザーは、公開されている 3 つのサブプログラムを介してのみアクセスする必要があります。

このレコードには 2 つのデータメンバーが含まれています。データと次のアイテム。データが integer 型である間、NextItem は、今のところ、謎の Ptr タイプです。

アクセスタイプ

アクセスタイプは VHDL ポインタです。それらを使用することで、実行時にオブジェクトを動的に作成できます。 Item タイプの動的に作成されたオブジェクトを指す Ptr という名前の新しいアクセスタイプを宣言します。

新しいアクセスタイプが追加されたパッケージ本体:

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 型で、Item 型へのポインタです。このニワトリ/タマゴの問題を回避するために、最初に Item を不完全型として宣言します。次に、Ptr 型を不完全型へのポインターとして宣言します。最後に、Item タイプの完全な宣言を指定します。

最後に、Ptr 型の Root という名前の新しい変数を宣言しました。これは、リンクされたリストのルートになります。リストが空の場合、ルートの値は null になります .それ以外の場合は、リストの最初の項目を指します。

リンクリストメソッド

保護された型の宣言領域で宣言したサブプログラムを実装する時が来ました。それらは、Push プロシージャと、2 つの不純な関数 (Pop と IsEmpty) でした。

保護された型の本体内にサブプログラムの実装を配置します。

押す

プッシュは、プロシージャーであるサブプログラムの唯一の 1 つです。 VHDL の関数には、省略できない戻り値が必要です。ダミーの戻り値を使用しないようにするには、プロシージャを使用することをお勧めします。

プッシュ手順:

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 のたびにキーワードを使用すると、動的メモリがシミュレータによって消費されます。

コードの残りの部分は、標準のリンクリストアルゴリズムです。新しいアイテムはリストの最後に追加されます。リストが空の場合はルートアイテムになります。さらに背景が必要な場合は、ウィキペディアのリンクリストを参照してください。

ポップ

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 変数が指すデータを参照できません。シミュレーターによって解放されました。解決策は、データを解放する前にローカル変数にコピーしてから、変数の値を返すことです。

空です

リストが空かどうかの確認は、ルートノードが null 以外を指しているかどうかを確認することで簡単に実行できます。

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

テストベンチ

コードを実行するには、テストベンチを作成する必要があります。実際には、連結リストはテストベンチでのみ使用できます。アクセスタイプは合成可能ではありませんが、検証目的には非常に役立ちます。

ライブラリパッケージの使用

テストベンチでは、最初に work をインポートします図書館。これは VHDL のデフォルトライブラリであり、DataStructures パッケージが存在する場所です。その後、次のように LinkedList 保護型をインポートできます。

library work;
use work.DataStructures.LinkedList;

共有変数

共有変数は、複数のプロセスからアクセスできる変数です。単一のプロセス内でのみ宣言できる通常の変数とは異なり、共有変数はアーキテクチャの宣言領域で宣言できます。したがって、それらはシグナルと同じスコープを持ちます。

保護された型のシグナルを宣言することはできないため、共有変数を使用する必要があります。 (vcom-1464) タイプ work.DataStructures.LinkedList のシグナル「リスト」の宣言が不正です (タイプは保護されたタイプです)。

テストベンチの宣言領域で LinkedList 型の共有変数を宣言します。

architecture sim of LinkedListTb is

   shared variable List : LinkedList;

begin

テストベンチの最終的なコード

3 つのユーティリティ関数をテストするために、新しいプロセスを作成します。このプロセスでは、5 つの整数をリンクリストにプッシュする For ループを追加します。最後に、IsEmpty 関数が true を返すまで実行される While ループで、リンクされたリストを空にします。 :

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

プリントアウトからわかるように、5 つの整数がリンクリストにプッシュされます。次に、テストベンチの While ループは、挿入された順序でそれらをリストからポップします。

セルフチェックテストベンチの作成方法基本的な VHDL クイズ – パート 4

VHDL