/assembly-dictionary

Реализация словаря на ассемблере

Primary LanguageAssembly

Dictionary in assembly

Связный список

Связный список — это структура данных. Пустой список это нулевой указатель; непустой список это указатель на первый элемент списка. Каждый элемент содержит данные и указатель на следующий элемент.

Вот пример связного списка (100, 200, 300). Его начало можно найти по указателю x1:

section .data

x1: 
dq x2
dq 100

x2: 
dq x3
dq 200

x3: 
dq 0
dq 300

Часто есть необходимость хранить набор данных в каком-то контейнере. С контейнером мы производим операции доступа к его элементам, добавления элемента в начало или конец, или на произвольную позицию, сортировки.

Разные контейнеры делают одни из этих операций лёгкими и быстрыми, а другие — медленными. Например, в массив неудобно добавлять элементы, но можно быстро обратиться к уже сущестующему по индексу. В связный список, наоборот, удобно добавлять элементы в любое место, но доступ по индексу сложнее — нужно просмотреть весь список с самого начала.

Задание

Необходимо реализовать на ассемблере словарь в виде связного списка. Каждое вхождение содержит адрес следующей пары в словаре, ключ и значение. Ключи и значения — адреса нуль-терминированых строк.

Словарь задаётся статически, каждый новый элемент добавляется в его начало. С помощью макросов мы автоматизируем этот процесс так, что указав с помощью новой конструкции языка новый элемент он автоматически добавится в начало списка, и указатель на начало списка обновится. Таким образом нам не нужно будет вручную поддерживать правильность связей в списке.

Создайте макрос colon с двумя аргументами: ключом и меткой, которая будет сопоставлена значению. Эта метка не может быть сгенерирована из самого значения, так как в строчке могут быть символы, которые не могут встречаться в метках, например, арифметические знаки, знаки пунктуации и т.д. После использования такого макроса можно напрямую указать значение, сопоставляемое ключу. Пример использования:

section .data

colon "third word", third_word
db "third word explanation", 0

colon "second word", second_word
db "second word explanation", 0 

colon "first word", first_word
db "first word explanation", 0

В реализации необходимо предоставить следующие файлы:

  • main.asm
  • lib.asm
  • dict.asm
  • colon.inc