Джонсон Харт - Системное программирование в среде Windows

Сортировку выполняет описанная в файле функция qsort, входящая в состав библиотеки С. Заметьте, что эта функции требует от программиста предоставления функции, осуществляющей сравнение записей, в качестве которой нами будет использована функция KeyCompare из программы 5.2.

Структура программы достаточно проста. Сначала на основе временной копии входного файла создается объект отображения файла, затем создается единое представление объекта отображения файла в памяти, и, наконец, вызывается функция qsort. При этом какие-либо операции файлового ввода/вывода отсутствуют. Отсортированный файл направляется далее на стандартный вывод, причем в конце отображения файла добавляется нулевой символ.

/* Глава 5. sortFL. Сортировка файлов. Записи имеют фиксированную длину.*/

/* Использование: sortFL файл */

#include "EvryThng.h"

typedef struct _RECORD {

TCHAR Key[KEY_SIZE];

TCHAR Data[DATALEN];

} RECORD;

#define RECSIZE sizeof(RECORD)

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

HANDLE hFile = INVALID_HANDLE_VALUE, hMap = NULL;

LPVOID pFile = NULL;

DWORD FsLow, Result = 2;

TCHAR TempFile[MAX_PATH];

LPTSTR pTFile;

/* Создать имя временного файла, предназначенного для хранения копии сортируемого файла, которая и подвергается сортировке. */

/* Можно действовать и по-другому, оставив файл в качестве постоянно хранимой сортируемой версии. */

_stprintf(TempFile, _T("%s%s"), argv[1], _Т(".tmp"));

CopyFile(argv[1], TempFile, TRUE);

Result = 1; /* Временный файл является вновь созданным и должен быть удален. */

/* Отобразить временный файл и выполнить его сортировку в памяти. */

hFile = CreateFile(TempFile, GENERIC_READ | GENERIC_WRITE, 0, NULL, OPEN_EXISTING, 0, NULL);

FsLow = GetFileSize(hFile, NULL);

hMap = CreateFileMapping(hFile, NULL, PAGE_READWRITE, 0, FsLow + TSIZE, NULL);

pFile = MapViewOfFile(hMap, FILE_MAP_ALL_ACCESS, 0, 0 /* FsLow + TSIZE */, 0);

qsort(pFile, FsLow / RECSIZE, RECSIZE, KeyCompare);

/* KeyCompare – как в программе 5.2. */

/* Отобразить отсортированный файл. */

pTFile = (LPTSTR)pFile;

pTFile[FsLow/TSIZE] = '\0';

_tprintf(_T("%s"), pFile);

UnmapViewOfFile(pFile);

CloseHandle(hMap);

CloseHandle(hFile);

DeleteFile(TempFile);

return 0;

}

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

Как показали предыдущие примеры, во многих случаях метод отображения файлов является весьма удобным. Однако предположим, что в программе создается структура данных с указателями, ссылающимися на область отображения файла, и ожидается, что впоследствии к этому файлу будет производиться обращение. В этом случае указатели оказываются установленными относительно виртуального адреса, возвращенного функцией MapViewOfFile, и не будут иметь смысла при использовании представления объекта отображения в следующий раз. Решение состоит в том, чтобы использовать базовые указатели (based pointers), являющиеся фактически смещениями относительно другого указателя. Соответствующий синтаксис Microsoft С, доступный в Visual C++ и некоторых других системах, выглядит следующим образом:

тип _based (база) объявление

Ниже показаны два примера таких указателей.

LPTSTR pInFile = NULL;

DWORD _based (pInFile) *pSize;

TCHAR _based (pInFile) *pIn;

Обратите внимание на тот факт, что синтаксис требует использования символа *, хотя такая практика противоречит соглашениям Windows.

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

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