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

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

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

} 

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

Пример. Простановка базовых размеров

Из книги AutoCAD 2009. Начали! автора Соколова Татьяна Юрьевна

Пример. Простановка базовых размеров Проставьте линейный размер, а затем от него – базовые (рис. 10.15). Рис. 10.15. Простановка базовых размеровЗапустите команду DIMLINEAR, вызвав ее из меню Dimension ? Linear или щелчком на пиктограмме Linear на панели инструментов Dimension. Ответьте на


7.2.6.4. Учебный пример: использование сигналов в программе fetchmail

Из книги Искусство программирования для Unix автора Реймонд Эрик Стивен

7.2.6.4. Учебный пример: использование сигналов в программе fetchmail Утилита fetchmail обычно устанавливается для работы в качестве демона в фоновом режиме, который без вмешательства пользователя периодически собирает почту со всех удаленных узлов, указанных в конфигурационном


Совет 7. При использовании контейнеров указателей, для которых вызывался оператор new, не забудьте вызвать delete для указателей перед уничтожением контейнера

Из книги Эффективное использование STL автора Мейерс Скотт

Совет 7. При использовании контейнеров указателей, для которых вызывался оператор new, не забудьте вызвать delete для указателей перед уничтожением контейнера Контейнеры STL отличаются умом и сообразительностью. Они поддерживают итераторы для перебора как в прямом, так и в


7.2.6.4. Учебный пример: использование сигналов в программе fetchmail

Из книги Искусство программирования для Unix автора Реймонд Эрик Стивен

7.2.6.4. Учебный пример: использование сигналов в программе fetchmail Утилита fetchmail обычно устанавливается для работы в качестве демона в фоновом режиме, который без вмешательства пользователя периодически собирает почту со всех удаленных узлов, указанных в конфигурационном


Пример: использование обработчиков завершения для повышения качества программ

Из книги Системное программирование в среде Windows автора Харт Джонсон М

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


Пример: использование функции фильтра

Из книги Искусство программирования на языке сценариев командной оболочки автора Купер Мендель

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


Пример: использование таймера ожидания

Из книги UNIX: разработка сетевых приложений автора Стивенс Уильям Ричард

Пример: использование таймера ожидания В программе 14.3 демонстрируется применение таймера ожидания для генерации периодических сигналов.Программа 14.3. TimeBeep: генерация периодических сигналов /* Глава 14. TimeBeep.с. Периодическое звуковое оповещение.  *//* Использование: TimeBeep


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

Из книги автора

Пример: использование указательных типов данных Аргументом потока, передаваемым функции потока при вызове CreateThread и _beginthreadex (см. главу 7), является указатель типа PVOID. Иногда программист может захотеть передать функции потока только целочисленное значение, указывающее,


Пример 10-24. Использование case

Из книги автора

Пример 10-24. Использование case #!/bin/bashecho; echo "Нажмите клавишу и затем клавишу Return."read Keypresscase "$Keypress" in [a-z] ) echo "буква в нижнем регистре";; [A-Z] ) echo "Буква в верхнем регистре";; [0-9] ) echo "Цифра";; * ) echo "Знак пунктуации, пробел или что-то другое";;esac # Допускается указыватль


Пример 22-9. Использование локальных переменных при рекурсии

Из книги автора

Пример 22-9. Использование локальных переменных при рекурсии #!/bin/bash# факториал# ---------# Действительно ли bash допускает рекурсию?# Да! Но...# Нужно быть действительно дубинноголовым, чтобы использовать ее в сценариях# на языке командной


Использование указателей для связи между функциями

Из книги автора

Использование указателей для связи между функциями      Мы только прикоснулись к обширному и увлекательному миру указателей. Сейчас нашей целью является использование указателей для решения задачи об установлении связи между функциями. Ниже приводится программа, в


ИСПОЛЬЗОВАНИЕ УКАЗАТЕЛЕЙ ПРИ РАБОТЕ С МАССИВАМИ

Из книги автора

ИСПОЛЬЗОВАНИЕ УКАЗАТЕЛЕЙ ПРИ РАБОТЕ С МАССИВАМИ      Попробуем написать функцию, использующую массивы, а затем перепишем ее, применяя указатели.      Рассмотрим простую функцию, которая находит (или пытается найти) среднее значение массива целых чисел. На входе функции


Пример: использование функций gethostbyname и getservbyname

Из книги автора

Пример: использование функций gethostbyname и getservbyname Теперь мы можем изменить код нашего TCP-клиента времени и даты, показанный в листинге 1.1, так, чтобы использовать функции gethostbyname и getservbyname и принимать два аргумента командной строки: имя узла и имя службы. Наша программа