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

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

Массивы на диске

Одним из приложений массивов, которое описывается во многих книгах, - это массивы на диске (или, если хотите, дисковые массивы, но не путайте их с RAID!), т.е. файлы записей фиксированной длины. Этот тип массивов обладает своими собственными особенностями, заслуживающими отдельного рассмотрения, после которого мы напишем класс, заключающий в себе файл записей (или данных). Постоянные массивы известны как файлы данных или файлы записей, а элементы таких массивов представляют собой записи. Индекс элементов в постоянных массивах называется порядковым номером записи.

Язык Pascal всегда поддерживал файлы записей и Delphi продолжает эту традицию. Стандартный метод работы с файлами записей выгладит следующим

образом:

var

MyRecord : TMyRecord;

MyFile : file of TMyRecord;

begin

{открыть файл данных}

System.Assign (MyFile, 'MyData.DAT');

System.Rewrite (MyFile);

try

{сохранить запись в позицию 0}

..установить поля MyRecord..

System.Write(MyFile, MyRecord);

{считать запись с позиции 0}

System.Seek(MyFile, Ob-System.Read(MyFile, MyRecord);

finally

System.Close(MyFile);

end;

end;

В приведенном блоке кода открывается файл данных (процедуры Assign и Rewrite), затем в файл записывается новая запись (процедура Write) и, наконец, запись считывается (процедуры Seek и Read). Обратите внимание, что перед считыванием необходимо с помощью процедуры Seek установить указатель позиции в файле на начало записи. Если этого не сделать, будет считана вторая запись файла. Код примера включает блок try..finally, который гарантирует, что файл будет закрыт независимо от того, что происходит при выполнении процедуры Rewrite.

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

И вторая проблема - файлы данных не содержат информации о структуре записей, количестве полей и их типах. Если бы в файле хранился больший объем информации, работать с записями и самими файлами было бы намного проще.

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

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

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

Существует два возможных решения для организации удаления записей. Первое - самое простое, которое используется в файлах данных dBASE. Для каждой записи в файле устанавливается префикс, состоящий из одного байта и содержащий флаг удаления. Флаг может быть булевым значением (true/fasle) или символом (например, 'Y'/'N' или '*'/пусто). При удалении записи устанавливается флаг удаления, который и будет говорить о том, что данная запись удалена. Все кажется достаточно простым, но что делать с удаленными записями? Вариант А - просто игнорировать.

К сожалению, в этом случае в файле будет накапливаться все большее и большее число удаленных записей и в некоторый момент времени файл придется уплотнять, дабы избавиться от ненужных записей и уменьшить размер файла данных. Вариант В - повторно использовать место, занимаемое удаленными записями. При добавлении в файл новой записи по файлу выполняется поиск удаленной записи, на место которой и будет добавлена новая запись. Очевидно, что вариант В неэффективен. Представьте себе, что в файле, содержащем 10000 записей, удалена только одна запись. Для того чтобы найти всего одну удаленную запись, нам придется выполнить цикл, по крайней мере, по 5000 записям. Эта операция принадлежит к классу О(n), поэтому вариант В лучше не реализовывать.

Тем не менее, вариант В имеет и свои положительные стороны, в частности, повторное использование места, занимаемого удаленными записями. Если бы только нам удалось привести его к классу O(1)! Такие рассуждения привели к разработке еще одного метода удаления записей - цепочке уделенных записей (для этого метода наличие служебного блока данных обязательно, поэтому будем считать, что служебные данные присутствуют).

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

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

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

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

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