Джулиан Бакнелл - Фундаментальные алгоритмы и структуры данных в Delphi
Рисунок 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;
end;
К сожалению, для такого типа постоянных массивов очень сложно перегрузить операцию [], поэтому в классе TtdRecordStream свойство Items не используется. Вместо него введены простые методы Read и Write.
Конструктор Create может вызываться в двух режимах: для постоянного массива в потоке или не в потоке. Режим определяется самим конструктором и в случае, если используется новый поток, создается служебный блок.
Листинг 2.19. Конструктор класса TtdRecordStream
constructor TtdRecordStream.Create(aStream : TStream;
aRecordLength : integer);
begin
inherited Create;
{сохранить поток и его текущую позицию}
FStream := aStream;
FZeroPosition := aStream.Position;
{если размер потока равен нулю, нужно создать служебный заголовок}
if (aStream.Size - FZeroPosition = 0) then
rsCreateHeaderRec(aRecordLength) {в противном случае проверить, содержится ли в потоке действительный служебный заголовок, считать его и установить значения его полей}
else
rsReadHeaderRec;
{выделить память под запись}
FRecordLen4 := FRecordLen + sizeof(longint);
GetMem(FRecord, FRecordLen4);
end;
Обратите внимание, что конструктор считывает текущее положение потока и записывает его в FZeroPosition. Текущее положение, которое, как правило, равно нулю, будет использовать для указания положения служебного заголовка для постоянного массива. Это означает, что перед вызовом конструктора Create программист может записать в поток свой служебный заголовок, и методы класса не будут его изменять. Тем не менее, класс предполагает, что оставшаяся часть потока, начиная с положения FZeroPosition, принадлежит классу и в нее допускается вносить изменения.
Конструктор вызывает либо метод rsCreateHeaderRec, который создает новый служебный заголовок для пустого потока (т.е. при необходимости создания нового массива), либо метод rsReadHeaderRec, который считывает текущий служебный заголовок (и, кроме того, проверяет его корректность).
И, наконец, конструктор Create выделяет из кучи память для записи (память выделяется с учетом размера флага удаления). Деструктор Destroy освобождает память, выделенную под запись.
Листинг 2.20. Деструктор класса TtdRecordStream
destructor TtdRecordStream.Destroy;
begin
if (FHeaderRec <> nil) then
FreeMem(FHeaderRec, FheaderRec^.hrHeaderLen);
if (FRecord <> nil) then
FreeMem(FRecord, FRecordLen4);
inherited Destroy;
end;
А теперь давайте рассмотрим два вспомогательных метода, которые соответственно создают новый или считывают существующий служебный заголовок.
Листинг 2.21. Создание и считывание служебного заголовка
procedure TtdRecordStream.rsCreateHeaderRec(aRecordLen : integer);
begin
{выделить память под служебный заголовок}
if ((aRecordLen + sizeof(longint)) < sizeof(TtdRSHeaderRec)) then begin
FHeaderRec := AllocMem(sizeof(TtdRSHeaderRec));
FHeaderRec^.hrHeaderLen := sizeof(TtdRSHeaderRec);
end
else begin
FHeaderRec := AllocMem( aRecordLen + sizeof(longint));
FHeaderRec^.hrHeaderLen := aRecordLen + sizeof(longint);
end;
{задать значения остальных стандартных полей}
with FHeaderRec^ do
begin
hrSignature := cRSSignature;
hrVersion := $00010000; {Major=1; Minor=0}
hrRecordLen := aRecordLen;
hrCapacity := 0;
hrCount := 0;
hr1stDelRec := cEndOfDeletedChain;
end;
{обновить служебный заголовок}
rsSeekStream(FZeroPosition);
rsWriteStream(FHeaderRec^, FHeaderRec^.hrHeaderLen);
{задать значение поля длины записи}
FRecordLen := aRecordLen;
end;
procedure TtdRecordStream.rsReadHeaderRec;
var
StreamSize : longint;
TempHeaderRec : TtdRSHeaderRec;
begin
{если размер потока меньше размера служебного заголовка, это неверный поток}
StreamSize := FStream.Size - FZeroPosition;
if (StreamSize < sizeof(TtdRSHeaderRec)) then
rsError(tdeRSNoHeaderRec, 'rsReadHeaderRec', 0);
{считать служебный заголовок}
rsSeekStream(FZeroPosition);
rsReadStream(TempHeaderRec, sizeof(TtdRSHeaderRec));
{первая санитарная проверка: сигнатура и счетчик/емкость}
with TempHeaderRec do
begin
if (hrSignatureocRSSignature) or (hrCount > hrCapacity) then
rsError(tdeRSBadHeaderRec, 'rsReadHeaderRec', 0);
end;
{выделить память под реальный служебный заголовок, скопировать уже считанные данные}
FHeaderRec := AllocMem(TempHeaderRec.hrHeaderLen);
Move(TempHeaderRec, FHeaderRec^, TempHeaderRec.hrHeaderLen);
{вторая санитарная проверка: проверка данных записи}
with FHeaderRec^ do
begin
FRecordLen4 := hrRecordLen + 4;
{for rsCalcRecordOffset}
if (StreamSize <> rsCalcRecordOffset(hrCapacity)) then
rsError(tdeRSBadHeaderRec, 'rsReadHeaderRec', 0);
{установить значения полей класса}
FCount :=hrCount;
FCapacity := hrCapacity;
FRecordLen := hrRecordLen;
end;
end;
function TtdRecordStream.rsCalcRecordOffset(aIndex : longint): longint;
begin
Result := FZeroPosition + FHeaderRec^.hrHeaderLen + (aIndex * FRecordLen4);
end;
Приведенный метод создания служебного заголовка вызывается только в случае, когда поток пуст. Принцип его работы очень прост. Сначала служебный заголовок создается в памяти, а затем записывается в поток. Если длина записи больше, чем нормальный размер служебного заголовка, его размер увеличивает до размера записи. В служебном заголовке содержится семь полей: поле сигнатуры, которое может использоваться для контроля при считывании записи;
номер версии служебного заголовка (это позволит в будущем добавлять в заголовок новые поля и сохранять совместимость версий);
длина служебного заголовка;
длина записи;
емкость потока (т.е. количество записей как активных, так и удаленных, которые в данный момент находятся в потоке);
количество активных записей;
и, наконец, порядковый номер первой удаленной записи (здесь значение этого поля устанавливается равным cEndOfDetectedChain или -2).
