Фундаментальные алгоритмы и структуры данных в Delphi
Шрифт:
– ------
Что дает нам постоянный размер узла? При необходимости записи данных в связный список нужно предварительно распределить память под узел. Для этого пришлось бы использовать очень сложный диспетчер кучи Delphi, всего лишь, чтобы распределить 8 байт памяти. Диспетчер кучи содержит код, который может манипулировать кусками памяти, а также распределять и освобождать память любого размера. Все операции выполняются быстро и эффективно. Но мы знаем, что будут использоваться только 8-байтные блоки, и нам нужны только такие блоки. Можно ли, учитывая постоянство размеров блоков, увеличить скорость распределения памяти для новых узлов и освобождения памяти, занимаемой удаляемыми узлами? Конечно же, ответ "да".
А вот теперь начинается самое интересное. Массивы узлов хранятся во внутреннем связном списке, а узлы, которые берутся из этих массивов, попадают в свободный список, который также представляет собой связный список. Таким образом, для увеличения эффективности работы класс связного списка будет использовать массивы и собственно связные списки.
Что в предыдущем абзаце понимается под понятием "свободный список"? Это общепринятая конструкция в программировании. у нас имеется набор некоторых элементов, которые "распределяются" и "освобождаются". При освобождении элемента он, скорее всего, в какой-то момент времени будет использоваться повторно поэтому вместо возвращения занимаемой элементом памяти поддерживается свободный список, т.е. список свободных элементов. Диспетчер кучи Delphi использует свободный список освобожденных блоков памяти различного размера. Многие базы данных поддерживают скрытый свободный список удаленных записей, которые можно использовать повторно. Массив записей, описанный в главе 2, использует цепочку удаленных записей, которая является ни чем иным, как другим названием свободного списка. При необходимости распределения памяти под элемент приложение обращается к свободному списку и выбирает один из свободных элементов.
Давайте разработаем диспетчер распределения узлов. Он будет содержать свободный список узлов, который вначале устанавливается равным nil, что означает, что список пуст. При распределении узла диспетчер будет просматривать свой свободный список. Если он пуст (равен nil), диспетчер распределяет большой блок памяти, обычно называемый страницей, при помощи диспетчера кучи Delphi. Затем станица разделяется на отдельные куски с размером, равным размеру узла, и куски записываются в свободный список. После этого узел извлекается из списка и передается пользователю. При освобождении узла он записывается в свободный список. Под "записью" здесь понимается вставка узла в начало списка, а под "извлечением" - считывание узла с начала списка.
Листинг 3.1. Класс TtdNodeManager
TtdNodeManager = class private
FNodeSize : cardinal;
FFreeList : pointer;
FNodesPerPage : cardinal;
FPageHead : pointer;
FPageSize : cardinal;
protected
procedure nmAllocNewPage;
public
constructor Create(aNodeSize : cardinal);
destructor Destroy; override;
function AllocNode : pointer;
procedure FreeNode(aNode : pointer);
end;
Как видно из приведенного кода, реализация интерфейса класса достаточно проста. Класс позволяет создавать и уничтожать экземпляры и распределять и освобождать узлы. Конструктор Create в качестве единственного входного параметра принимает размер узла, а затем на его основании вычисляет несколько значений: количество узлов на странице и размер страницы. Класс пытается распределять страницы размером 1024 байта. Но если размер узла настолько велик, что на одной
Листинг 3.2. Конструктор TtdNodeManager.Create
constructor TtdNodeManager.Create(aNodeSize : cardinal);
begin
inherited Create;
{сохранить размер узла, округленный до ближайших 4 байт}
if (aNodeSize <= sizeof(pointer)) then
aNodeSize := sizeof(pointer) else
aNodeSize := ((aNodeSize + 3) shr 2) shl 2;
FNodeSize := aNodeSize;
{вычислить размер страницы (по умолчанию используется 1024 байта) и количество узлов на странице; если размер страницы по умолчанию недостаточен для размещения двух или большего количества узлов, выбрать размер страницы равным размеру узла}
FNodesPerPage := (PageSize - sizeof(pointer)) div aNodeSize;
if (FNodesPerPage > 1) then
FPageSize := PageSize
else begin
FNodesPerPage := 1;
FPagesize := aNodeSize + sizeof(pointer);
end;
end;
Код метода AllocNode очень прост. Если свободный список пуст, вызывается метод nmAllocNewPage, который распределяет новую страницу и вносит все ее узлы в свободный список. Если свободный список не пуст, из него выбирается первый узел (фактически с помощью процедуры удаления первого узла).
Листинг 3.3. Распределение памяти для узла в классе TtdNodeManager
function TtdNodeManager.AllocNode : pointer;
begin
{если свободный список пуст, распределить память для новой страницы; это приведет к заполнению свободного списка}
if (FFreeList = nil) then
nmAllocNewPage;
{вернуть первый элемент свободного списка}
Result := FFreeList;
FFreeList := PGenericNode(FFreeList)^.gnNext;
end;
Тип PGenericNode представляет собой запись с одним полем - полем для ссылки gnNext. Этот тип и преобразование типов в коде позволяет работать с узлами в списке свободных узлов на основании общего алгоритма - нечто похожее на тип TSimpleNode, который мы рассматривали ранее. Обратите внимание, конструктор гарантирует, что размер узлов, отслеживаемых диспетчером узлов, составляет, по крайней мере, 4 байта, т.е. размер указателя.
Следующий метод - FreeNode - ничуть не сложнее предыдущего. Он просто вставляет новый узел в начало свободного списка (используется код вставки перед первым узлом).
Листинг 3.4. Освобождение узла в классе TtdNodeManager
procedure TtdNodeManager.FreeNode(aNode : pointer);
begin
{вставить узел (если он не nil) в начало свободного списка}
if (aNode <> nil) then begin
PGenericNode(aNode)^.gnNext := FFreeList;
FFreeList := aNode;
end;
end;
Следующий метод, заслуживающий внимания, - nmAllocNewPage. Этот метод предназначен для распределения памяти объемом FpageSize, вычисленным в конструкторе Create, для новой страницы. Каждая страница содержит указатель и узлы FNodesPerPage. Указатель используется для создания связного списка страниц (именно поэтому конструктор учитывает в своих вычислениях значение sizeof(pointer)). Находящиеся на странице узлы вставляются в свободный список с помощью простого вызова FreeNode. Поскольку переменная NewPage объявлена как PAnsiChar, при выполнении простых операций с указателем для идентификации отдельных узлов на странице преобразование указателя в тип integer не требуется.