пуст, из него выбирается первый узел (фактически с помощью процедуры удаления первого узла).
Листинг 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 не требуется.
Листинг 3.5. Распределение новой страницы в классе TtdNodeManager
procedure TtdNodeManager.nmAllocNewPage;
var
NewPage : PAnsiChar;
i : integer;
begin
{распределить новую страницу и вставить ее в начало списка страниц}
GetMem(NewPage, FPageSize);
PGenericNode(NewPage)^.gnNext := FPageHead;
FPageHead := NewPage;
{разделить новую страницу на узлы и вставить их в начале свободного списка; обратите внимание, что первые 4 байта страницы представляют собой указатель на следующую страницу, поэтому не забудьте их пропустить}
inc(NewPage, sizeof(pointer));
for i := pred(FNodesPerPage) downto 0 do
begin
FreeNode(NewPage);
inc(NewPage, FNodeSize);
end;
end;
И, наконец, деструктор Destroy удаляет все страницы в списке страниц. Он ничего не делает со свободным списком, поскольку все узлы в нем находятся на освобождаемых страницах и будут освобождены в любом случае.
Листинг 3.6. Удаление экземпляра класса TtdNodeManager
destructor TtdNodeManager.Destroy;
var
Temp : pointer;
begin
{освободить все имеющиеся страницы}
while (FPageHead <> nil) do
begin
Temp := PGenericNode (FPageHead)^.gnNext;
FreeMem(FPageHead, FPageSize);
FPageHead := Temp;
end;
inherited Destroy;
end;
-------
Рекомендации на будущее. Уже в недалеком будущем мы получим новую версию Windows, использующую 64-битные указатели и написанную для 64-разрядных процессоров Intel. Понятно, что подобная же участь ждет и операционную систему Linux. Вскоре после выхода в свет 64-разрядных систем на рынке появятся версии Delphi и Kylix, поддерживающие длинные указатели. Весь код в настоящей книге основан на предположении, что длина указателей может составлять и не 4 байта, или 32 бита. Для определения длины указателей используется функция sizeof(pointer). Нигде в коде мы не считаем значения sizeof(pointer) и sizeof(longint) равными - простая хитрость, которая может оказаться полезной при работе с будущими версиями Delphi. Примером описанного принципа программирования может служить диспетчер узлов.
-------
Полный код класса TtdNodeManager можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDNdeMgr.pas.
Перед тем как вернуться к дальнейшим исследованиям односвязных списков, с которых мы начали наши рассуждения, отметим несколько недостатков класса TtdNodeManager. Первое, что следует отметить - это то, что метод FreeNode не проверяет, принадлежит ли освобождаемый узел к требуемому классу, т.е. находится ли он на странице, контролируемой классом. Это основной вопрос правильного функционирования класса. Если у класса есть узел, который не принадлежит к данному классу, он может
