Описание макросов для списковых структур

Анотация

Здесь приводятся описание макросов для работы с кучей heap.mac.

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

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

Перед началом работы создаётся «головной элемент», содержащий информацию о размере области, отводимой под кучу, указатели на некоторые (обычно первые) элементы списков и др. К головному элементу может добавляться дополнительная область памяти содержащая какую-либо специфическую информацию, которую неудобно размещать в структуре.

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

Рис. 1. Структура памяти в куче.

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

• SFree — часть памяти, которая может быть возвращена в кучу, но первоначально не включается в список свободной памяти. В процессе настройки может понадобиться установить некоторые динамические структуры, которые затем в процессе работы могут быть возвращены в список свободной памяти. Чтобы не расходовать лишнее время на вызовы процедур выделения памяти, необходимый объём может быть просто не включён в список свободных элементов и затем использован для размещения в нём динамических структур.
• LBMN — метка в сегменте данных или косвенная ссылка через регистр на начало кучи (первый байт заголовка).

Прежде, чем использовать кучу в программе, должен быть вызван макрос LInitHeap. Примеры вызова макроса

Следующий макрос формирует головной элемент в памяти, устанавливает список свободных элементов, и устанавливает пустые ссылки в первых Fnill элементах структуры SN.

• SN — Имя головной структуры, размещаемой за заголовком. Необязателен.
• LBMN — База головного элемента, метка или [регистр]. Должен быть или меткой, или индексным регистром. Сложный тип (например, Label1.[ebx]) недопустим. Параметр обязателен.
• SHeap — Общая память, выделенная под кучу, включая заголовок. Константа или регистр, лучше edi. Обязателен.
• SizExt — Размер дополнительной части головной структуры не входящей в SN. Необязателен. Константа или регистр.
• Fnill — Число первых двойных слов SN которые следует заполнить значением nill. Может быть полезно в том случае, когда нужно несколько первых указателей сделать пустыми при установке кучи. Необязателен. Константа или регистр (лучше ecx).
• SFree — Число пропускаемых байт между головной структурой и первым элементом списка свободной памяти. Это может потребоваться, например для создания некоторых элементов списков при настройке кучи. Память, выделяемая по SFree может быть потом перемещена в список свободных элементов. Необязателен. Константа.
• eax — для предачи параметров не использовать.
• Портятся слдующие регистры: — eax, edi; ecx — при наличии Fnill>0.

При использовании Fnill ES и DS должны указывать на один и тот же сегмент.

LInitHeap macro SN, LBMN:REQ, SHeap:REQ, SizExt:=<0>, Fnill, SFree:=<0>

Запись в область данных головной структуры может производиться как

mov [указатель_на_головной_элемент].LUsD.поле_структуры_пользователя, данные

указатель_на_головной_элемент — метка или ссылка в базовом регистре.

Элемент списка в общем случае выглядит так

Здесь SN — некоторая структура данных, её имя используется как имя типа; reg — один из РОНов. «Размер данного элемента списка» включает размер заголовка, размер структуры элемента и размер памяти, выделенной после структуры.

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

Запись в область данных элемента списка или блока может производиться как

mov [Reg].поле_структуры, данные

Обращение к пользовательской части заголовка элемента списка или блока:

mov [Reg-L?&SN&?ExtHd].поле_структуры, данные

Перед использованием операций над элементами списков и подсписков (переходы от одного элемента к другому, выделение и возврат памяти и т. п.), должны быть определены типы списков и подсписков с помощью макросов LDefType и LDefSubType.

Примеры вызова этих макросов

Макросы, описанные в данном файле, предполагают, что каждый список состоит из однотипных элементов, имеющих заголовок, структуру данных SN, и (необязательно) дополнительную область памяти, размер которой может меняться от элемента к элементу. Тип описывается с помощью макроса LDefType. SN является и именем структуры данных, используемых программистом, и именем типа списка. Если требуется создать списки с разным способом доступа к отдельным элементам (например, циклический однонаправленный и линейный двунаправленный) с одинаковой структурой данных, то следует описать её в двух разных структурах данных SN. При описании можно использовать директиву equ:

Далее, можно описать два разных типа SN1 и SN2. В памяти может создаваться несколько списков с одинаковой структурой данных SN и одинаковым методом доступа. Заголовок элемента формируется на основе значений числа направлений в списке dir и величины дополнительной неструктурированной памяти Addmem.

Вход:

• SN — Имя структуры данных, которое означает и тип списка. Обязателен.
• Direct — Число направлений (1 или 2). Обязателен.
• Addmem — Размер памяти, добавляемый к размеру структуры SN. Если указано значение variable, то формируется элемент с переменным размером, если указано число или параметр опущен, то — с фиксированным. Необязателен.
• Circle — указывает, что список является циклическим, если опущен — линейным. Необязателен. Необязателен, отключает проверку существования следующего элемента.
• ExtHd — размер дополнительной памяти в заголвоке (константа). Если в дополнительном заголовке планируется размещать структуру SNh, то вместо ExtHd надо написать size SNh. Необязателен.

LDefType macro SN:Req, Direct:Req, Addmem:=<0>, Circle, ExtHd:=<0>

Следующие макросы предназначены для формировании в сегменте данных готовых списков.

LDeclareBegin SN:req, ListN:req

LDeclare ListN1

LDeclareEnd

Вход:

• SN — имя типа структуры (обязателен);
• ListN — имя метки, по которой можно обращаться к первому элементу списка (обязателен);
• ListN1 — имя метки элемента, по которой можно обращаться к конкретному элементу списка (не обязателен).

LDeclareBegin macro SN:req, ListN:req

LDeclare macro ListN1

LDeclareEnd macro

В ряде случаев целесообразно создавать список ещё на этапе трансляции программы. Например, если разрабатывается интерпретатор, то на момент начала работы ему уже должен быть известен определённый набор имён функций, который по мере обработки текста программы может постепенно пополняться новыми терминами. Формирование списков на этапе трансляции обеспечивается макросами LDeclareBegin, LDeclare и LDeclareEnd.

Данные макросы отвечают за формирование заголовков элементов списка. Между ними должны следовать директивы аналогичные db,которые заполняют данными область дополнительного заголовка и область данных пользователя.

Пример испльзования макросов

Вложенность и пересечение списков LDeclareBegin…LDeclareEnd не допускается. Если между двумя вызовами LDeclareBegin не стоит LDeclareEnd, то выдаётся сообщение об ошибке. Метки L1 и L2 относятся к началу области пользовательских данных элемента, поэтому записи

дадут правильный результат.

Ниже приведён макрос выделения памяти заданного размера.

Важно! В принципе макрос позволяет выделить память объёмом в один байт, но возвращать в кучу память объёмом менее восьми (8) байт опасно, т. к. при этом велика вероятность (около 100 %) разрушения списковой структуры.

Вход:

• LBMN — метка или индексный регистр, в котором находится ссылка на головной элемент.
• ecx — Размер необходимого блока памяти
• exer — метка выхода для случая, когда блок памяти подходящего размера не найден
• OK — метка выхода для случая, когда память выделена

Выход: EBX — указатель на выделенный блок памяти.

Портятся регистры EAX, EDX.

Данный макрос должен быть оформлен в программе как процедура LGetmem для использования макросов выделения памяти и в простейшем случае может выглядеть следующим образом

LGetm macro LBMN:Req, exer:Req, OK:Req

Данный макрос очень объёмен и потому должен быть оформлен как процедура LFreemem, например, так

LFreem macro LBMN:Req

LGetEl macro SN:Req, AddSize, ExErr:Req

LGetBlock macro BlockName, BlockSize, ExErr:Req

LFreeEl macro SN:Req

LFreeBlock macro BlockName, BlockSize

Память выделяется под элемент списка (или блок динамической памяти) по вызову макроса LGetEl (или LGetBlock) и в дальнейшем изменяться не может, только, если элемент удаляется макросом LFreeEl (или для блоков LFreeBlock. Эти макросы вызывают процедуры LGetmem и LFreemem, которые должны быть описаны в программе пользователя. В простейшем случае описание должно выглядеть следующим образом

где LGetm, LFreem — макросы, уже описанные в данном файле. Примеры использования некоторых макросов:

Следующие ниже обозначения являются общими для всех приводимых ниже макросов

• SN — тип списка
• Fld — имя поля структуры SN, которое используется как ссылка на подсписок или следующий элемент многомерного списка.

Размер блока с учётом заголовка (если есть) должен быть не меньше 8 байт! Иначе при его возврате в кучу может быть нарушена структура списков. Блоки могут быть типизированными и нетипизированными. Для типизированных блоков фиксированного размера, размер увеличивается до 8 байт автоматически, для нетипизированных блоков и блоков переменного размера, он должен корректироваться программистом, например, с помощью макроса LCorrectSize. Типизированные блоки, в отличие от нетипизированных, определяются с помощью макроса LDefBlockType, и к типизированным блокам может быть применён макрос LDefSubType, а к нетипизированным — нет.

На основе элментов списков и блоков выделенной памяти могут организовываться древовидные структуры и многомерные списки. Возможные варианты размещения ссылок на подсписки в элементе приведены ниже.

Здесь P— указатель на элемент подсписка; PN— Указатель на следующий элемент подсписка, PP— указатель на предыду- щий элемент списка; Fld — поле, являющееся ссылкой или массивом ссылок; IReg— один из РОНов, содержащий номер ин- тересующей ссылки в массиве ссылок, на начало которого указывает Fld. Размер одной ссылки 4 байта. Если использует- ся двунаправленный список, то все ссылки сдвоенные (т. е. размер одного вхождения — 8 байт), указывают на сле- дующий и на предыдущий элементы. Перед таблицей ссылок может размещаться необязательное однобайтовое поле, содержа- щее количество ссылок в таблице (при этом количество ссылок (одно- или двунаправленных) должно лежать в пределах от 1 до 256 иначе они не поместятся в поле). Поле LapTabl должно быть описано в структуре SN в байте, пред- шествующем началу таблицы ссылок. Использовать поле имеет смысл только при динамическом определении количества ссы- лок. При статическом определении можно использовать более 256 ссылок. Проверка, выходит ли индекс за размер таблицы осуществляется макросом LChckInd, который должен указываться перед макросами, обращающимися к таблицам ссылок.

Пример:

Данный макрос определяет тип ссылок на элементы подсписков для типов подсписков Б и В.

Вход:

• Примерные виды списков: P — указатель; D — к-л данныеDirect — Число направлений (1 или 2 для списков типа В и EnterSubList для типа Б). Обязателен.
• Circle — указывает, что многомерный список является циклическим, если опущен - линейным. Необязателен, отключает проверку существования следующего элемента.
• ItsTable — Указывает (если есть), что поле является таблицей ссылок. Необязателен. При использовании LapTablS=<variable> допустимы следующие значения: <byte>, <word> и <dword>, указывающие соответственно, что поле размера является байтом, словом или двойным словом.
• LapTablS — Число ссылок в таблице. Если параметр не указан, то проверка, попадает ли индекс в таблицу ссылок, не выполняется. Если указано нулевое значение, то считается, что размер таблицы задаётся байтом, предшествующим, таблице (что вносит ограничение — 256 ссылок одно- или двунаправленных при использовании таблиц переменного размера //значения индексного регистра могут лежать в пределах IReg=0…255, 0 соответствует первой ссылке//. Таблицы постоянного размера могут содержать большее число ссылок).

LDefSubType macro SN:Req, Fld:Req, Direct:Req, Circle, ItsTable, LapTablS

Макрос предназначен для определения типа блока, чтобы можно было использовать ссылки на другие подсписки (при совместном использовании с LDefSubType) и для автоматизации выделения памяти

• BlockName — имя типа блока. Обязателен
• BlockSize — размер блока или variable. Необязателен. Если параметр не указан или равен variable, то подразумевается переменный размер блока.
• ExtHd — размер дополнительной памяти в заголовке (константа). Если в дополнительном заголовке планируется размещать структуру SN2, то вместо ExtHd надо написать size SN2. Необязателен.

LDefBlockType macro BlockName:REQ, BlockSize:=<variable>, ExtHd:=<0>

Переходы от одного элемента к другому осуществляются с помощью макросов LGetNext и LGetPred (последний может использоваться только для двунаправленных списков):

Переходы от одного элемента к другому в многомерных и ветвящихся подсписках, а также вход в иерархические подсписки осуществляются с помощью макросов LGetSubNext и LGetSubPred (последний может использоваться только для двунаправленных подсписков):

Следующие макросы описывают переходы к следующему элементу списка типа А (LGetNext), а также к входу в подсписок типа Б и к переходу к следующему элементу многомерного списка типа В (LGetSubNext).

Вход:
• [Reg] - указатель на начало элемента, по умолчанию [ebx]
• exer — метка, на которую переходит макрос в случае, если следующий элемент не существует. Нужен только для линейных списков.
• Выход: [Reg] — новый элемент, или переход по метке, exer если следующий элемент отсутствует.

Для макроса LGetSubNext должны дополнительно указываться следующие параметры

IReg — индексный регистр, содержащий номер интересующей ссылки в таблице ссылок Fld. Необходим и используется только в том случае, когда Fld является не единичной ссылкой, а таблицей ссылок. Может быть также смещением ссылки в Fld (числом).

LGetNext macro SN:Req, Reg:=<ebx>, exer:Req ; Переход к следующему элементу списка типа А

LGetSubNext macro SN:Req, Fld:Req, Reg:=<ebx>, exer:Req, IReg ; Переход к следующему

Следующие макросы осуществляют переход к предыдущему элементу, могут применяться только к двунаправленным спискам (LGetPred) и к двунаправленным многомерным спискам типа В (LGetSubPred).

• [Reg] — указатель на начало элемента, по умолчанию [ebx]
• exer — метка, на которую переходит макрос в случае, если следующий элемент не существует
• Выход: [Reg] — новый элемент, или переход по метке exer если произошла ошибка

Для макроса LGetSubPred должны дополнительно указываться следующие параметры

LGetPred macro SN:Req, Reg:=<ebx>, exer ; Переход к предыдущему элементу

LGetSubPred macro SN:Req, Fld:Req, Reg:=<ebx>, exer, IReg ; Переход к предыдущему элементу подсписка

Следующие макросы описывают загрузку указателей на следующий элемент списка типа А (LLoadNext) в регистр, а также на элемент подсписка типа Б или на следующий элемент многомерного списка типа В (LLoadSubNext).

Вход:

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

Выход:

• [LReg] — новый элемент, или переход по метке, exer если следующий элемент отсутствует.

Для макроса LGetSubNext должны дополнительно указываться следующие параметры

LLoadnext macro SN:Req, LReg:Req, Reg:Req, NoEl ; Переход к следующему элементу списка типа А

LLoadSubNext macro SN:Req, Fld:Req, LReg:Req, Reg:Req, NoEl, IReg ; Переход к следующему

Следующие макросы осуществляют загрузку указателя на предыдущий элемент в регистр, могут применяться только к двунаправленным спискам (LGetPred) и к двунаправленным многомерным спискам типа В (LGetSubPred).

• LReg — указатель на начало элемента
• Reg — Регистр, в который загружается указатель на предыдущий элемент
• NoEl — метка, на которую переходит макрос в случае, если следующий элемент не существует.
Выход: Reg — новый элемент, или переход по метке exer, если элемент отсутствует

Для макроса LGetSubPred должны дополнительно указываться следующие параметры

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

LLoadPred macro SN:Req, LReg:Req, Reg:Req, NoEl ; Переход к предыдущему элементу

LLoadSubPred macro SN:Req, Fld:Req, LReg:Req, Reg:Req, NoEl, IReg ; Переход к предыдущему

Включение и исключение элементов из списка выполнют, соответственно, макросы LIncEl и LExcEl.

Включение и исключение элементов из многомерных списков (тип В) выполнют, соответственно, макросы LIncSubEl и LExcSubEl

Макросы вставки элементов в списки (LIncEl) и многомерные подсписки типа В (LIncSubEl)

В списке (подсписке) до вставки должно присутствовать не меньше одного элемента.

• [ecx] — элемент, после которого нужно вставить другой элемент
• [ebx] — Элемент, который нужно вставить в список

Портит регистр EAX

Для макроса LIncSubEl должны дополнительно указываться следующие параметры

Данный макрос не предназначен для работы с обычными подсписками (тип Б). Подсписки могут быть только многомерными (тип В). Портит eax

LIncEl macro SN:Req ; Вставка элемента в список

LIncSubEl macro SN:Req, Fld:Req, IReg ; Вставка элемента в подсписок

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

Для макроса LExcSubEl должны дополнительно указываться следующие параметры.

LExcEl macro SN:Req ; Исключить элемент из списка

LExcSubEl macro SN:Req, Fld:Req, IReg ; Исключить элемент из подсписка

Выполняет вставку первого элемента в линейный список или подсписок.

Вход:

• Reg1 — Элемент, который должен быть вставлен, по умолчанию [ebx];
• Reg2 — Первый элемент списка, если Reg2=nill, то в [reg2] ни чего не заносится;
• IReg — индексный регистр, содержащий номер интересующей ссылки в таблице ссылок Fld. Необходим и используется только в том случае, когда Fld является не единичной ссылкой, а таблицей ссылок. Может быть также смещением ссылки в Fld.

LIncFirst macro SN:req, Reg1:=<ebx>, Reg2:req

LIncSubFirst macro SN:req, Fld:req, Reg1:=<ebx>, Reg2:req, IReg:=<0>

Выполняет вставку последнего элемента в линейный список или подсписок.

Вход:

1. Reg1 — Элемент, который должен быть вставлен, по умолчанию [ebx];
2. Reg2 — Последний элемент списка;
3. IReg — индексный регистр, содержащий номер интересующей ссылки в таблице ссылок Fld. Необходим и используется только в том случае, когда  ld является не единичной ссылкой, а таблицей ссылок. Может быть также смеще- нием ссылки в Fld.

LIncLast macro SN:req, Reg1:=<ebx>, Reg2:req

LIncSubLast macro SN:req, Fld:req, Reg1:=<ebx>, Reg2:req, IReg:=<0>

Выполняет исключение первого элемента из линейного списка.

LExclFirst macro SN:Req, Reg1:Req, Reg2:Req, Skp

LExclSubFirst macro SN:Req, Fld:req, Reg1:Req, Reg2:Req, Skp, IReg:=<0>

Если поле указывает на подсписок, то ссылка в него включается с помощью команды

где reg_2 — указывает на элемент подсписка, который надо включить.

Для контроля попадания

LChckInd StrucName2, FldPoint, ebx, edx, dl, ExErr

Замечание. После входа в подсписок (тип Б) перемещения внутри него должны происходить с помощью макросов LGetNext и LGetPred. В списках типа "В" — с помощью LGetSubNext и LGetSubPred.

Проверка попадания индекса в пределы таблицы ссылок

Изменяемые регистры: Flags

Особенности работы: Если ExErr не указан, то после выполнения макроса флаги установлены таким образом, что по ко- манде 'ja xxx' будет выполнен переход в том случае, если индекс выходит за пределы таблицы, а по команде 'jbe xxx', если не выходит. Если размер памяти, отводимой под таблицу ссылок, выделяется динамически, т. е. перед таблицей имеется поле размера, и метка ExErr не указана, то проверке подвергается только младший байт регистра, что может быть использовано в тех случаях, когда заведомо известно, что индекс помещённый в IReg не превышает 255 (например, когда индекс заносится командой movzx).

LChckInd macro SN:REQ, Fld:REQ, Reg:=<ebx>, ExErr, IReg:REQ, LIReg:REQ

Макрос устанавливает ссылки в элементе списка так, как если бы он был первым и единственным элементом в списке

1. Reg — регистр, указывающий на элемент
2. IReg — индексный регистр, содержащий номер интересующей ссылки в таблице ссылок Fld. Необходим и используется только в том случае, когда Fld является не единичной ссылкой, а таблицей ссылок. Может быть также смещением ссылки в Fld.

LMakeFirstEl macro SN:Req, Reg:=<ebx>

LMakeSubFirstEl macro SN:Req, Fld:Req, Reg:=<ebx>, IReg:Req

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

Вход:

• Reg — регистр, указывающий на элемент, по умолчанию [ebx];
• IReg — индексный регистр, содержащий номер интересующей ссылки в таблице ссылок Fld. Необходим и используется только в том случае, когда Fld является не единичной ссылкой, а таблицей ссылок. Может быть также сме- щением ссылки в Fld.

LChckLast macro SN:REQ, Reg:=<ebx>

LChckSubLast macro SN:REQ, Fld:req, Reg:=<ebx>, IReg:=<0>

Проверяет, является ли элемент первым в списке (подсписке). Используется только для линейных двунаправленных списков. Если ссылка на предыдущий элемент пустая, то элемент — первый.

LChckFirst macro SN:REQ, Reg:=<ebx>

LChckSubFirst macro SN:REQ, Fld:req, Reg:=<ebx>, IReg:=<0>

Проверяет размер затребованной ОЗУ и, если надо, корректирует его. Если размер запрашиваемой ОЗУ меньше 8 байт, то он приравнивается 8 байтам.

Вход: ReqSize — регистр или память, содержащий затребованный объём ОЗУ

Выход:

• ReqSize — Содержит скорректированный объём ОЗУ
• Flags — флаги. Если выдать команду «jb xxx», то, если коррекция выполнялась, будет выполнен переход по метке 'xxx', а если «jae xxx» — то если не выполнялась.
• JNoCorrect — переход по метке, если коррекция не выполноялась, параметр не обязателен.

LCorrectSize macro ReqSize:req, JNoCorrect

©   Жуков И. Б.

e-mail: ibzh@yandex.ru

При использовании материалов, пожалуйста,

ставьте индексируемую ссылку на сайт https://ibzh.eko3.ru/

Число посетителей
		Число посетителей