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입니다. 푸시는 목록의 시작 부분에 새 요소를 추가합니다. 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 포인터입니다. 그것들을 사용함으로써 우리는 런타임 동안 동적으로 객체를 생성할 수 있습니다. 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 유형을 불완전한 유형에 대한 포인터로 선언합니다. 마지막으로 항목 유형의 전체 선언을 지정합니다.

마지막으로 Ptr 유형의 Root라는 새 변수를 선언했습니다. 이것은 연결 목록의 루트가 됩니다. 목록이 비어 있으면 Root 값은 null가 됩니다. . 그렇지 않으면 목록의 첫 번째 항목을 가리킵니다.

연결된 목록 방법

이제 보호된 형식의 선언적 영역에서 선언한 하위 프로그램을 구현할 시간입니다. 푸시 프로시저와 두 가지 순수하지 않은 함수인 Pop 및 IsEmpty입니다.

보호된 유형의 본문 내에 하위 프로그램의 구현을 배치합니다.

푸시

푸시는 프로시저인 서브프로그램 중 유일한 것입니다. 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 키워드가 사용되면 시뮬레이터에서 동적 메모리를 소비합니다.

나머지 코드는 표준 연결 목록 알고리즘일 뿐입니다. 새 항목은 목록 끝에 추가되거나 목록이 비어 있으면 루트 항목이 됩니다. 배경 지식이 더 필요하면 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 변수가 가리키는 데이터를 참조할 수 없습니다. 시뮬레이터에 의해 무료로 제공되었습니다. 해결 방법은 해제하기 전에 데이터를 로컬 변수에 복사한 다음 변수 값을 반환하는 것입니다.

비어 있음

목록이 비어 있는지 여부를 확인하는 것은 루트 노드가 null이 아닌 다른 것을 가리키는지 확인하여 간단히 수행할 수 있습니다.

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

테스트벤치의 최종 코드

세 가지 유틸리티 기능을 테스트하기 위해 새 프로세스를 만듭니다. 이 과정에서 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 루프가 삽입된 순서대로 목록에서 해당 항목을 팝합니다.