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

Перед каждой записью находится 4-байтный префикс - значение типа longint. Он предназначен для хранения флага удаления. Его нормальное значение -1 - значение, которое указывает, что запись не удалена. Любое другое значение будет означать, что запись удалена. Но это еще не все. Обратите внимание, что размер каждой записи увеличивается на 4 байта. В свою очередь, пользователь считает, что размер записи не изменился. В служебном заголовке хранится еще одно значение типа longint, которое представляет собой порядковый номер первой удаленной записи. Нормальное значение для этого поля -2, которое означает, что в файле нет удаленных записей.

Рисунок 2.3. Удаление записи

При удалении первой записи мы поступаем следующим образом. Сначала устанавливаем значение флага удаления записи равным значению поля порядкового номера первой удаленной записи служебного заголовка, т.е. значению -2. Затем значение флага удаления записывается на диск. После этого в поле порядкового номера первой удаленной записи служебного заголовка записываем порядковый номер только что удаленной записи. В результате получаем следующее: во-первых, значение флага удаления записи не равно -1 (т.е. теперь запись отмечена как удаленная) и, во-вторых, поле порядкового номера первой удаленной записи служебного заголовка теперь указывает на удаленную запись (т.е. запись, место, занимаемое которой, можно использовать повторно).

При удалении второй записи выполняются все те же операции. После них флаг второй уделенной записи будет содержать порядковый номер первой удаленной записи (не равный -1, что говорит о том, что запись удалена), а поле первой удаленной записи служебного заголовка будет указывать на вторую удаленную запись.

А что происходит при добавлении в файл новой записи? Вместо простого добавления записи в конец файла, как мы делали раньше, проверяем значение поля порядкового номера удаленной записи в служебном заголовке. Если значение не равно -1, значит, существует запись, занимаемое которой место можно использовать повторно. При вставке новой записи потребуется изменить содержащееся в служебном заголовке значение. Если этого не сделать, при последующем добавлений записи она снова будет записана на то же место, а предыдущая запись будет потеряна. В этом случае мы считываем флаг удаления записи, занимаемое которой место будет использоваться повторно, и переносим его в поле первой удаленной записи служебного заголовка данных. Обратите внимание, что при повторном использовании последней удаленной записи в поле первой удаленной записи служебного заголовка будет установлено значение -2, поскольку флаг удаления записи содержал это значение.

Есть еще один вопрос, который проще рассмотреть на примере кода. Было бы довольно глупо ограничить концепцию постоянных (устойчивых) массивов только до файлов на диске. Несмотря на то что в подавляющем большинстве случаев будут использоваться файлы, ничто не мешает нам организовать постоянный массив в памяти или на любом другом устройстве хранения данных. Было бы удобно иметь класс постоянного массива, который пользуется потоками. В Delphi предусмотрен богатый набор классов потоков, включая файловый поток. Таким образом, если мы напишем код, использующий класс TStream, его можно будет применять со всеми другими классами, порожденными от TStream.

Ниже приведен код класса TtdRecordStream - класса, предназначенного для постоянного хранения в потоке массива записей.

Листинг 2.18. Класс TtdRecordStream для хранения постоянных массивов.

type

TtdRecordStream = class private

FStream : TStream;

FCount : longint;

FCapacity : longint;

FHeaderRec : PtdRSHeaderRec;

FName : TtdNameString;

FRecord : PByteArray;

FRecordLen : integer;

FRecordLen4 : integer;

FZeroPosition : longint;

protected

procedure rsSetCapacity(aCapacity : longint);

procedure rsError(aErrorCode : integer; const aMethodName : TtdNameString; aNumValue : longint);

function rsCalcRecordOffset(aIndex : longint): longint;

procedure rsCreateHeaderRec(aRecordLen : integer);

procedure rsReadHeaderRec;

procedure rsReadStream(var aBuffer; aBufLen : integer);

procedure rsWriteStream(var aBuffer; aBufLen : integer);

procedure rsSeekStream(aOffset : longint);

public

constructor Create(aStream : TStream; aRecordLength : integer);

destructor Destroy; override;

procedure Flush; virtual;

function Add(var aRecord): longint;

procedure Clear;

procedure Delete(aIndex : longint);

procedure Read(aIndex : longint; var aRecord; var alsDeleted : boolean);

procedure Write(aIndex : longint; var aRecord);

property Capacity : longint read FCapacity write rsSetCapacity;

property Count : longint read FCount;

property RecordLength : integer read FRecordLen;

property Name : TtdNameString read FName write FName;