VHDL에서 보호 타입과 액세스 포인터로 동적 링크드 리스트 구현하기

링크드 리스트는 요소가 추가/제거될 때 확장/축소되는 동적 자료구조입니다. VHDL의 객체지향 기능인 액세스 타입, 레코드, 보호 타입을 사용하면 이 구조를 깔끔하고 효율적으로 구현할 수 있습니다.

DataStructures 패키지 생성

링크드 리스트 관련 로직을 DataStructures라는 전용 VHDL 패키지에 캡슐화하겠습니다. 이 이름은 향후 트리나 해시맵 같은 다른 구조로 확장하기에도 좋습니다.

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 패키지는 선언부(공개 인터페이스)와 본문(비공개 구현)으로 구성됩니다. 선언부는 사용자에게 보이고, 본문은 내부적으로 남습니다.

보호 타입(Protected Type) 정의

보호 타입은 VHDL에서 경량 클래스처럼 동작합니다. 서브프로그램, 타입 선언, 변수를 포함할 수 있습니다. Push, Pop, IsEmpty 세 가지 연산을 노출하는 LinkedList라는 보호 타입을 정의하겠습니다.

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) 도입

보호 타입 본문 안에서 노드를 나타내는 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; 

공유 변수(Shared Variable) 사용

시그널은 보호 타입이 될 수 없으므로, 여러 프로세스가 리스트와 상호작용하게 하려면 공유 변수를 써야 합니다.

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 순서로 올바르게 저장하고 꺼냄을 확인시켜 줍니다.