Системное программирование в среде Windows

Рассмотренные выше примеры относились к сортировке файлов в различных ситуациях. Вместе с тем, должно быть очевидным, что наша цель состояла не в обсуждении методик сортировки, а в демонстрации применения различных методов управления памятью. В программе 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);