Как создать связанный список в VHDL

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

Связные списки удобнее всего реализовать с помощью классов в объектно-ориентированном языке программирования. VHDL имеет некоторые объектно-ориентированные функции, которые можно использовать для абстрагирования сложности реализации от пользователя.

В этой статье мы собираемся использовать типы доступа, записи и защищенные типы для реализации связанного списка в VHDL. Мы собираемся создать новый пакет VHDL, в котором мы напишем весь код нашего связанного списка.

Пакет

Первое, что мы сделаем, это объявим пакет, который будет содержать наш код. Пакет VHDL — это набор типов, объектов или подпрограмм, которые можно импортировать в другой файл VHDL. Большинство модулей VHDL импортируют пакет std_logic_1164 из библиотеки IEEE. Мы создаем свой собственный пакет, очень похожий на него.

Содержимое нашего нового файла 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. Push добавляет новый элемент в начало списка. 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. Используя их, мы можем динамически создавать объекты во время выполнения. Мы объявим новый тип доступа с именем Ptr, который будет указывать на динамически создаваемый объект типа Item.

Тело пакета с добавленным новым типом доступа:

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;

Узел связанного списка должен содержать ссылку на следующий узел в списке. Мы реализовали это в записи Item с элементом NextItem. Он имеет тип Ptr, который, в свою очередь, является обратным указателем на тип Item. Чтобы избежать этой проблемы курица/яйцо, мы сначала объявляем Item как неполный тип. Затем мы объявляем тип Ptr как указатель на неполный тип. Наконец, мы указываем полное объявление типа Item.

Последнее, что мы сделали, это объявили новую переменную с именем Root типа Ptr. Это будет корень связанного списка. Если список пуст, значение Root будет null . В противном случае он будет указывать на первый элемент в списке.

Методы связанного списка

Теперь пришло время реализовать подпрограммы, которые мы объявили в декларативной области защищенного типа. Это были процедура Push и две нечистые функции:Pop и IsEmpty.

Мы поместим реализацию подпрограмм в тело защищенного типа.

Отправить

Push — единственная из подпрограмм, которая является процедурой. Функции в 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 до VHDL-2017 (также называемая VHDL-2018 или VHDL-2019) отсутствует. И 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. Он был освобожден симулятором. Решение состоит в том, чтобы скопировать данные в локальную переменную перед освобождением, а затем вернуть значение переменной.

Пусто

Проверить, пуст ли список или нет, можно просто проверив, указывает ли корневой узел на что-то, отличное от нуля:

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 (тип является защищенным типом).

Мы объявляем общую переменную типа LinkedList в декларативной области тестового стенда:

architecture sim of LinkedListTb is

   shared variable List : LinkedList;

begin

Окончательный код тестового стенда

Чтобы протестировать три функции полезности, мы создаем новый процесс. В процессе мы добавляем цикл For, который помещает пять целых чисел в связанный список. Наконец, мы очищаем связанный список в цикле While, который выполняется до тех пор, пока наша функция IsEmpty не вернет true. :

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

Как видно из распечатки, в связанный список помещаются пять целых чисел. Затем цикл While в тестовом стенде извлекает их из списка в том порядке, в котором они были вставлены.