Реализация динамического связного списка в VHDL с защищенными типами и указателями доступа

Связный список — это динамическая структура данных, которая расширяется и сокращается по мере добавления или удаления элементов. Объектно-ориентированные возможности VHDL — типы доступа, записи и защищенные типы — позволяют реализовать эту структуру чисто и эффективно.

Создание пакета DataStructures

Мы инкапсулируем всю логику связного списка в выделенный VHDL-пакет под названием DataStructures. Это имя, ориентированное на будущее, позволяет легко расширить его до других структур, таких как деревья или хеш-карты, позже.

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-пакет состоит из декларативной области (публичный интерфейс) и тела (приватная реализация). Декларативная область видна пользователям; тело остается внутренним.

Определение защищенного типа

Защищенные типы действуют как легковесные классы в VHDL. Они могут содержать подпрограммы, объявления типов и переменные. Мы определим защищенный тип под названием LinkedList, который предоставляет три операции: Push, Pop и IsEmpty.

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, представляющий узел. Запись содержит полезную нагрузку данных и указатель на следующий узел.

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

Поскольку защищенные типы не могут объявлять новые типы в декларативной области, запись Item определяется внутри тела.

Работа с указателями через типы доступа

Мы используем тип доступа Ptr для ссылки на экземпляры Item динамически. Эта двухэтапная декларация избегает циклических зависимостей.

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 -- 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.