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

Бакнелл Джулиан М.

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;

Методы предка (листинг 723) свойства Items просто извлекают данные, однотипные longint, из внутреннего объекта TList.

Листинг 7.23. Установка и извлечение значений каталога

function TtdHashDirectory.hdGetItem(aInx : integer): longint;

begin

Assert( (0 <= aInx) and (aInx < FList.Count),

hdErrorMsg(tdeIndexOutOfBounds, 'hdGetItem', aInx));

Result := longint(FList.List^[aInx]);

end;

procedure TtdHashDirectory.hdSetItem(aInx : integer;

aValue : longint );

begin

Assert ((0 <= aInx) and (aInx < FList.Count), hdErrorMsg(tdeIndexOutOfBounds, 'hdGetItem', aInx));

FList.List^[aInx] := pointer(aValue);

end;

И, наконец, в листинге 7.24 приведен код интересного метода класса, который вдвое увеличивает размер каталога.

Листинг 7.24. Увеличение вдвое количества записей в каталоге

procedure TtdHashDirectory.DoubleCount;

var

Inx : integer;

begin

{удвоить значение счетчика, увеличить глубину}

FList.Count := FList.Count * 2;

FCount := FCount * 2;

inc(FDepth);

{теперь

каждая запись в исходном каталоге удваивается; например, значению в записи 0 старого каталога теперь соответствует значение для записей 0 и 1 нового каталога}

for Inx := pred(FList.Count) downto 1 do

FList.List^[Inx] := FList.List^[Inx div 2];

end;

Во-первых, этот метод удваивает значение счетчика элементов во внутреннем объекте TList. Реализация TList гарантирует установку новых элементов в нулевые значения, хотя, как вскоре будет показано, это не имеет никакого значения. Метод удваивает значение внутреннего счетчика и увеличивает значение разрядной глубины. Затем мы копируем и удваиваем все элементы объекта TList (чтобы убедиться, что цикл работает правильно, советуем во время изучения этого материала обращаться к рисункам 7.1 (е) и 7.1 (f)).

Этот класс выполняет ряд важных подготовительных действий, необходимых для работы нашего основного класса TtdHashTableExtendible, код интерфейса которого приведен в листинге 7.25.

Листинг 7.25. Интерфейс класса TtdHashTableExtendible

type

TtdHashTableExtendible = class private

FCompare : TtdCompareRecordKey;

FCount : longint;

FDirectory: TtdHashDirectory;

FHashFunc : TtdHashFuncEx;

FName : TtdNameString;

FBuckets : TtdRecordStream;

FRecords : TtdRecordStream;

FRecord : pointer;

protected

procedure hteCreateNewHashTable;

procedure hteError(aErrorCode : integer;

const aMethodName : TtdNameString);

function hteErrorMsg(aErrorCode : integer;

const aMethodName : TtdNameString): string;

function hteFindBucket(const aKey : string; var aFindInfo): boolean;

procedure hteSplitBucket(var aFindlnfo);

public

constructor Create(aHashFunc : TtdHashFuncEx;

aCompare : TtdCompareRecordKey;

aDirStream : TStream;

aBucketStream : TtdRecordStream;

aRecordStream : TtdRecordStream);

destructor Destroy; override;

function Find(const aKey : string; var aRecord): boolean;

procedure Insert(const aKey : string; var aRecord);

property Count : longint read FCount;

property Name : TtdNameString read FName write FName;

end;

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

Как показано в листинге 7.26, конструктору Create передаются три потока и два указателя на функции. Три потока предназначены для каталога, групп и записей. Первая функция - обычная функция хеширования (хотя для этой хеш-таблицы функции хеширования должны создавать 32-разрядные значения;

в данном случае никакое деление по модулю на размер таблицы не выполняется). Вторая функция -функция сравнения значения ключа Key с записью, которая считывается из потока записей.

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