Связанные записи в файлеФайловый указатель
При размещении в файле динамических структур данных возникает вопрос, каким образом в файле будут представлены указатели, которые используются в переменных динамических структур данных. Само собой разумеется, что значение указателя, представляющего собой адрес указуемой переменной в памяти программы, никакого смысла при размещении той же переменной в файле не имеет. Но тогда обычному указателю, связывающему две переменные в памяти, нужно сопоставить аналогичный указатель в файле -назовем его ФАЙЛОВЫМ УКАЗАТЕЛЕМ. Его значением является позиция (адрес) переменной при ее размещении в файле. Как известно, позиция в файле определяется значением типа long, поэтому файловый указатель не является типизированным: тип его одинаков для любой переменной. Теперь рассмотрим подробнее задачу размещения связанных переменных (или записей). Если структурированная переменная а1 имеет указатель ptr на переменную a2 , то при размещении в файле переменная a1 должна получить еще один дополнительный параметр -файловый указатель fptr на место размещения в файле переменной a2. Сформировать значение файлового указателя можно следующим образом:
-если указуемая переменная (a2) еще не размещена в файле, позиционироваться на конец файла, получить текущую позицию как значение ее адреса в файле и записать переменную в файл. Если указуемая переменная уже размещена в файле, то просто использовать адрес ее размещения;
-полученный адрес указуемой переменной (a2) в файле сохранить как значение файлового указателя (fptr) в переменной, содержащей обычный указатель (ptr в a1);
-сохранить переменную (a2) в файле.
#define FNULL -1L
struct x
{
int val;
x *ptr;
long fptr;
} a2 = {0,NULL,FNULL}, a1 = {1, &a2, FNULL};
fseek(fd, 0L, SEEK_END);
a1.fptr = ftell(fd);
fwrite((void*)a1->ptr, sizeof(x), 1, fd);
fseek(fd, 0L, SEEK_END);
fwrite((void*)&a1, sizeof(x), 1, fd);
Таким образом, структура данных, имеющая указатели, размещается в файле "хвостом вперед", то есть сначала размещаются указуемые переменные с целью получения их адресов в файле, а затем переменные, содержащие указатели.
Если такой алгоритм по каким- либо причинам нежелателен или невозможен (например, для циклического списка или графа), то можно поступить следующим образом:
-разместить в файле все переменные структуры данных и запомнить их адреса в файле;
-сформировать значения файловых указателей в переменных структуры данных, расположенных в памяти;
-"обновить" значения переменных структуры данных в файле, то есть переписать их из памяти по тем же файловым адресам.
Проиллюстрируем оба варианта на примере сохранения дерева в файле. В первом случае дерево записывается в файл "потомками вперед", причем в режиме последовательного доступа без позиционирования. Фактически получается файл записей фиксированной длины, в котором записи связаны между собой и образуют дерево с головной вершиной в конце файла:
//------------------------------------------------------bk59-03.cpp
#include <stdio.h>
#include <alloc.h>
struct ftree
{
int val;
struct ftree *left,*right; // Указатели в памяти
long fleft,fright; // Указатели в файле
};
#define FNULL -1L
#define TSZ sizeof(ftree)
//------ Функция записи возвращает адрес вершины в файле
//
long PutTree(ftree *p, FILE *fd)
{
long pos;
if (p == NULL) return(FNULL);
p ->fleft = PutTree(p->left,fd);
p ->fright = PutTree(p->right,fd);
pos = ftell(fd);
fwrite( (void*)p, TSZ, 1, fd);
return(pos);
}
//------ Функция формирует файл записей фиксированной длины
// В начало файла записывается указатель на головную
// вершину дерева
void SaveTree(ftree *p, char *name)
{
long pos0; // Указатель на головную запись
FILE *fd;
if ((fd=fopen(name,"wb")) ==NULL) return;
// Резервировать место под указатель
fwrite(&pos0, sizeof(long), 1, fd);
pos0 = PutTree(p,fd);
fseek(fd, 0L, SEEK_SET); // Обновить указатель
fwrite( (void*)&pos0, sizeof(long), 1, fd);
return;
}
Во втором случае рекурсивная функция записи сначала размещает текущую вершину и запоминает ее адрес в файле.
Затем рекурсивно вызывает самое себя для размещения правого и левого поддерева. Полученные после размещения файловые указатели запоминает в текущей вершине, после чего "обновляет" ее в файле:
//------------------------------------------------------bk59-04.cpp
//------Вариант функции записи вершины дерева в файл
long PutTree_(ftree *p, FILE *fd)
{
long cpos; // Адрес в файле текущей
if (p==NULL) return(FNULL); // вершины дерева
fseek(fd, 0L, SEEK_END);
cpos = ftell(fd);
fwrite((void*)p, TSZ, 1, fd); // Записать в файл текущую вершину
p->fright = PutTree(p->right,fd);
p->fleft = PutTree(p->left,fd);
fseek(fd, cpos, SEEK_SET); // Обновить текущую вершину
fwrite((void*)p, TSZ, 1, fd);
return cpos;
}
Последовательность действий по чтению динамической структуры данных более простая: по имеющемуся адресу из файла читается переменная, из которой берутся значения файловых указателей на другие переменные и процесс повторяется. Структура данных в памяти формируется, как правило, с использованием динамических переменных. В качестве примера рассмотрим загрузку дерева из файла, сформированного любым из двух указанных способов:
//------------------------------------------------------bk59-05.cpp
//----- Функция возвращает указатель на динамическую
// переменную - вершину дерева, считывая ее и связанное
// с ней поддерево из файла
ftree *GetTree(long pos, FILE *fd)
{
struct ftree *p;
if (pos == FNULL) return NULL;
if ((p = new ftreeTSZ) ==NULL) return NULL;
fseek(fd,pos,SEEK_SET);
fread((void *)p, TSZ, 1, fd);
p ->left = GetTree(p ->fleft,fd);
p ->right = GetTree(p->fright,fd);
return p;
}
//----- Функция открывает файл и читает файловый указатель
// на головную вершину дерева, по которой загружает дерево
// в память
ftree *LoadTree(char *name)
{
FILE *fd;
long phead;
if ((fd = fopen(name,"rb")) ==NULL) return(NULL);
fread((void*)&phead, sizeof(long), 1, fd);
return GetTree(phead, fd);
}
