Пример: использование базовых указателей

Пример: использование базовых указателей

Рассмотренные выше примеры относились к сортировке файлов в различных ситуациях. Вместе с тем, должно быть очевидным, что наша цель состояла не в обсуждении методик сортировки, а в демонстрации применения различных методов управления памятью. В программе 5.1 используется бинарное дерево поиска, которое уничтожается при переходе к сортировке очередного файла, тогда как в программе 5.4 сортируется массив фиксированных записей, отображенный в памяти компьютера. В приложении В представлены показатели производительности для различных вариантов реализации, включая и тот, который реализует программа 5.5. 

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

Программа 5.5, которая должна применяться совместно с программой 5.6, решает эту проблему, которая проявляется всякий раз, когда отображаются структуры данных, использующие указатели. В предлагаемом решении используется ключевое слово _based, предоставляемое Microsoft С. Альтернативным вариантом было бы отображение файла в массив и обеспечение доступа к записям в представлении объекта отображения файла с помощью индекса.

Программа написана в виде еще одной версии команды sort, которой в данном случае присвоено имя sortMM. Данная версия программы отличается следующими особенностями, заслуживающими внимания:

• Записи могут иметь переменную длину.

• Программа использует первое поле в качестве ключа, но определяет его длину.

• Строятся два представления файла. Одно из них представляет исходный файл, а второе — файл, содержащий отсортированные ключи. Второй файл является индексным файлом (index file), каждая из записей которого содержит ключ и указатель (базовый адрес), относящийся к исходному файлу. Для сортировки индексного файла, во многом по аналогии с программой 5.4, применяется функция qsort.

• Индексный файл сохраняется и впоследствии может быть использован, причем предусмотрена возможность (параметр командной строки –I) отказаться от сортировки и использовать существующий индексный файл. Кроме того, индексный файл может быть использован для быстрого поиска ключей путем проведения бинарного поиска (возможно, с использованием входящей в библиотеку C функции bsearch) в индексном файле.

Взаимосвязь между индексным файлом и сортируемым файлом иллюстрирует рис. 5.5. Главной программой является программа 5.5, которая обеспечивает создание представлений файлов в памяти компьютера, осуществляет сортировку индексного файла и отображает результаты. Эта программа вызывает функцию CreateIndexFile, представленную программой 5.6. 

Рис. 5.5. Сортировка с использованием отображения индексного файла

Программа 5.5. sortMM: использование базовых указателей в индексном файле 

/* Глава 5. Команда sortMM.

 Сортировка отображенного в памяти файла – только один файл. Опции:

 -r Сортировать в обратном порядке.

 -I Использовать индексный файл для получения отсортированного файла. */

#include "EvryThng.h"

int KeyCompare(LPCTSTR , LPCTSTR);

DWORD CreateIndexFile (DWORD, LPCTSTR, LPTSTR);

DWORD KStart, KSize; /* Начальная позиция и размер ключа (TCHAR) . */

BOOL Revrs;

int _tmain(int argc, LPTSTR argv []) {

 HANDLE hInFile, hInMap; /* Дескрипторы входного файла. */

 HANDLE hXFile, hXMap; /* Дескрипторы индексного файла. */

 HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);

 BOOL IdxExists;

 DWORD FsIn, FsX, RSize, iKey, nWrite, *pSizes;

 LPTSTR pInFile = NULL;

 LPBYTE pXFile = NULL, pX;

 TCHAR _based(pInFile) *pIn; 

 TCHAR IdxFlNam [MAX_PATH], ChNewLine = TNEWLINE;

 int FlIdx = Options(argc, argv, _T("rI"), &Revrs, &IdxExists, NULL);

 /* Шаг 1: открыть и отобразить входной файл. */

 hInFile = CreateFile(argv [FlIdx], GENERIC_READ | GENERIC_WRITE, 0, NULL, OPEN_EXISTING, 0, NULL);

 hInMap = CreateFileMapping(hInFile, NULL, PAGE_READWRITE, 0, 0, NULL);

 pInFile = MapViewOfFile(hInMap, FILE_MAP_ALL_ACCESS, 0, 0, 0);

 FsIn = GetFileSize(hInFile, NULL);

 /* Шаги 2 и З: создать имя индексного файла. */

 _stprintf(IdxFlNam, _T("%s%s"), argv[FlIdx], _T(".idx"));

 if (!IdxExists) RSize = CreateIndexFile(FsIn, IdxFlNam, pInFile);

 /* Шаг 4: отобразить индексный файл. */

 hXFile = CreateFile(IdxFlNam, GENERIC_READ | GENERIC_WRITE, 0, NULL, OPEN_EXISTING, 0, NULL);

 hXMap = CreateFileMapping(hXFile, NULL, PAGE_READWRITE, 0, 0, NULL);

 pXFile = MapViewOfFile(hXMap, FILE_MAP_ALL_ACCESS, 0, 0, 0);

 FsX = GetFileSize(hXFile, NULL);

 pSizes = (LPDWORD)pXFile; /* Поля размера в .idx-файле. */

 KSize = *pSizes; /* Размер ключа */

 KStart = *(pSizes + 1); /* Начальная позиция ключа в записи. */

 FsX –= 2 * sizeof(DWORD);

 /* Шаг 5: сортировать индексный файл при помощи qsort. */

 if (!IdxExists) qsort(pXFile + 2 * sizeof(DWORD), FsX / RSize, RSize, KeyCompare);

 /* Шаг 6: отобразить входной файл в отсортированном виде. */

 рХ = pXFile + 2 * sizeof(DWORD) + RSize – sizeof(LPTSTR);

 for (iKey = 0; iKey < FsX / RSize; iKey++) {

  WriteFile(hStdOut, &ChNewLine, TSIZE, &nWrite, NULL);

  /* Приведение типа рХ, если это необходимо! */

  pIn = (TCHAR _based (pInFile)*) *(LPDWORD)pX;

  while ((*pIn != CR || * (pIn + 1) != LF) && (DWORD) pIn < FsIn) {

   WriteFile(hStdOut, pIn, TSIZE, &nWrite, NULL); pIn++;

  }

  рХ += RSize;

 }

 UnmapViewOfFile(pInFile);

 CloseHandle(hInMap);

 CloseHandle(hInFile);

 UnmapViewOfFile(pXFile);

 CloseHandle(hXMap);

 CloseHandle(hXFile);

 return 0;

}

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

Программа 5.6. sortMM: создание индексного файла 

DWORD CreateIndexFile(DWORD FsIn, LPCTSTR IdxFlNam, LPTSTR pInFile) {

 HANDLE hXFile;

 TCHAR _based (pInFile) *pInScan = 0;

 DWORD nWrite;

 /* Шаг 2а: создать индексный файл. Не отображать его на данной стадии. */

 hXFile = CreateFile(IdxFlNam, GENERIC_READ | GENERIC_WRITE, FILE_SHARE_READ, NULL, CREATE_ALWAYS, 0, NULL);

 /* Шаг 2b: получить первый ключ и определить его размер и начальную позицию. Пропустить пробел и получить длину ключа. */

 KStart = (DWORD) pInScan;

 while (*pInScan != TSPACE && *pInScan != TAB) pInScan++; /* Найти поле первого ключа. */

 KSize = ((DWORD)pInScan – KStart) / TSIZE;

 /* Шаг 3: просмотреть весь файл, записывая ключи и указатели записей в индексный файл. */

 WriteFile(hXFile, &KSize, sizeof(DWORD) , &nWrite, NULL);

 WriteFile(hXFile, &KStart, sizeof(DWORD), &nWrite, NULL);

 pInScan = 0;

 while ((DWORD)pInScan < FsIn) {

  WriteFile(hXFile, pInScan + KStart, KSize * TSIZE, &nWrite, NULL);

  WriteFile(hXFile, &pInScan, sizeof(LPTSTR), &nWrite, NULL);

  while ((DWORD)pInScan < FsIn && ((*pInScan != CR) || (*(pInScan + 1) != LF))) {

   pInScan++; /* Пропустить до конца строки. */

  }

  pInScan += 2; /* Пропустить CR, LF. */

 }

 CloseHandle(hXFile);

 /* Размер отдельной записи. */

 return KSize * TSIZE + sizeof(LPTSTR);

}