Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


Ѕазовые указатели




 ак показали предыдущие примеры, во многих случа€х метод отображени€ файлов €вл€етс€ весьма удобным. ќднако предположим, что в программе создаетс€ структура данных с указател€ми, ссылающимис€ на область отображени€ файла, и ожидаетс€, что впоследствии к этому файлу будет производитьс€ обращение. ¬ этом случае указатели оказываютс€ установленными относительно виртуального адреса, возвращенного функцией 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.  огда программа будет запущена в следующий раз и создаст отображение файла, эти указатели окажутс€ бесполезными.

ѕрограмма 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);

}





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-09-20; ћы поможем в написании ваших работ!; просмотров: 510 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

¬аше врем€ ограничено, не тратьте его, жив€ чужой жизнью © —тив ƒжобс
==> читать все изречени€...

499 - | 515 -


© 2015-2023 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.021 с.