Фундаментальные алгоритмы и структуры данных в Delphi

Следующий метод, заслуживающий внимания, - 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 не проверяет, принадлежит ли освобождаемый узел к требуемому классу, т.е. находится ли он на странице, контролируемой классом. Это основной вопрос правильного функционирования класса. Если у класса есть узел, который не принадлежит к данному классу, он может иметь неверную длину (что в итоге может привести к перезаписи памяти) или может принадлежать к другому классу, который, возможно, очистит страницу, содержащую узел, и т.д. При отладке имеет смысл проводить проверку принадлежности к классу всех освобождаемых узлов. Реализация, содержащаяся в рамках сопровождающих книгу материалов, включает специальный код проверки при условии, что модель будет компилироваться с использованием утверждений.

Вторая проблема вызвана тем, что мы легко можем удалить экземпляр диспетчера узлов до удаления объектов, которые эти узлы используют. Это приведет к возникновению неизвестных ошибок. Только достаточная внимательность во время программирования может нас избавить от такого рода ошибок.

(Кстати, в качестве простого доказательства того, что мы не зря потеряли время на реализацию диспетчера узлов, можно сказать, что тесты по распределению и освобождению одного миллиона узлов показали, что диспетчер узлов работает в 3-4 раза быстрее, чем диспетчер кучи Delphi.)

Класс односвязного списка

Перед тем как приступить к реализации класса TtdSingleLinkList для представления односвязного списка, рассмотрим несколько вводных замечаний.