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

Теперь, когда мы рассмотрели основной алгоритм, пора применить его на практике. Прежде всего, отметим следующее: все фрагменты расширяемой хеш-таблицы хранятся в отдельных файлах: каталога, группы и записей. Для хранения групп и записей мы используем класс TtdRecordStream (в действительности мы будем использовать производный от него класс TtdRecordFile, ориентированный на использование файлов, но внутри программы мы будем считать, что применительно к расширяемой хеш-таблице этот класс является простым потоком). Каталог может храниться и извлекаться из любого класса, производного от TStream, но понятно, что длительного хранения целесообразно использовать класс TFileStream.

Извлечение и реализация каталога - следующая по сложности задача. Код интерфейса для ее выполнения приведен в листинге 7.20.

Листинг 7.20. Интерфейс класса TtdHashDirectory

type

TtdHashDirectory = class private

FCount : integer;

FDepth : integer;

FList : TList;

FName : TtdNameString;

FStream : TStream;

protected

function hdGetItem(aInx : integer): longint;

procedure hdSetItem(aInx : integer; aValue : longint);

function hdErrorMsg(aErrorCode : integer;

const aMethodName : TtdNameString; aIndex : integer): string;

procedure hdLoadFromStream;

procedure hdStoreToStream;

public

constructor Create(aStream : TStream);

destructor Destroy; override;

procedure DoubleCount;

property Count : integer read FCount;

property Depth : integer read FDepth;

property Items [aInx : integer] : longint read hdGetItem write hdSetItem; default;

property Name : TtdNameString read FName write FName;

end;

Для выполнения поставленной задачи этого общедоступного интерфейса вполне достаточно. Мы можем удвоить количество элементов в каталоге, используя метод DoubleCount, и можем получать текущие номера элементов (свойство Count) и разрядную глубину каталога (свойство Depth). Теоретически, мы могли бы обойтись только одним свойством, поскольку Count = 2Depth. Но поддержание обоих свойств - менее трудоемкая задача по сравнению с вычислением степени двух, когда это потребуется. И, наконец, мы может обратиться к отдельным элементам, хранящимся в каталоге в виде значений типа длинных целых. Естественно, эти значения будут номерами групп.

Разделы private и protected содержат еще несколько методов и полей. Во-первых, это методы set и get свойства Items, а, во-вторых, - два метода, предназначенные для выполнения считывания и записи каталога в и из потока. Кроме того, как мы видим, реальным контейнером записей каталога является экземпляр TList.

В листинге 7.21 конструктор создает экземпляр каталога хеш-таблицы, внутренний объект TList и при необходимости выполняет автоматическое считывание из потока.

Листинг 7.21. Создание экземпляра класса TtdHashDirectory

constructor TtdHashDi rector Y.Create(aStrearn : TStream);

begin

Assert(sizeof(pointer) = sizeof(longint), hdErrorMsg(tdePointerLongSize, 1 Create1, 0));

{создать предка}

inherited Create;

{создать каталог как TList}

FList := TList.Create;

FStream := aStream;

{если поток не содержит никаких данных, то инициализировать каталог с одной записью и глубиной равной 0}

if (FStream.Size = 0) then begin

FList.Count := 1;

FCount := 1;

FDepth := 0;

end

{в противном случае выполнить загрузку из потока}

else

hdLoadFromS trearn;

end;

procedure TtdHashDirectory.hdLoadFromStream;

begin

FStream.Seek(0, soFromBeginning);

FStream.ReadBuffer(FDepth, sizeof(FDepth));

FStream.ReadBuffer(FCount, sizeof(FCount));

FList.Count := FCount;

FStream.ReadBuffer(FList.List^, FCount * sizeof(longint));

end;

Я оставил оператор Assert в конструкторе Create. Он проверяет равенство размера указателя размеру значения longint. Это связано с тем, что я немного "схитрил", сохраняя значения каталога непосредственно в TList в виде однотипных указателей. При изменении размера указателя или longint, используемый метод работать не будет. Поэтому, просто на всякий случай, я поместил здесь это утверждение. Если впоследствии компилятор будет генерировать сообщение об ошибке, это можно будет исправить. Если же нет, то во время выполнения будет выводиться сообщение о нарушении утверждения.

А пока что LoadFromStream выполняет минимальную проверку для проверки наличия допустимого каталога в потоке. Поскольку считывание выполняется непосредственно из потока в буфер фиксированного размера, в будущем, возможно, имеет смысл несколько усовершенствовать процесс, включив сигнатуру в поток или добавив проверку с применением циклического избыточного кода и т.п.

Уничтожение экземпляра каталога хеш-таблицы (листинг 7.22) требует считывания его текущего содержимого обратно в поток и освобождения внутреннего объекта TList.

Листинг 7.22. Уничтожение экземпляра класса TtdHashDirectory

destructor TtdHashDirectory.Destroy;

begin

hdStoreToStream;

FList.Free;

inherited Destroy;

end;

procedure TtdHashDirectory.hdStoreToStream;

begin

FStream.Seek(0, soFromBeginning);

FStream.WriteBuffer(FDepth, sizeof(FDepth));

FStream.WriteBuffer(FCount, sizeof(FCount));

FStream.WriteBuffer(FList.List'4, FCount * sizeof(longint));

end;