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

/* Открыть входной файл. */

hIn = CreateFile(argv[iFile], GENERIC_READ, 0, NULL, OPEN_EXISTING, 0, NULL);

if (hIn == INVALID_HANDLE_VALUE) RaiseException(0, 0, 0, NULL);

__try { /* Распределить две кучи. */

hNode = HeapCreate(HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE, NODE_HEAP_ISIZE, 0);

hData = HeapCreate(HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE, DATA_HEAP_ISIZE, 0);

/* Обработать входной файл, создавая дерево. */

pRoot = FillTree(hIn, hNode, hData);

/* Отобразить дерево в порядке следования ключей. */

_tprintf(_T("Сортируемый файл: %s\n"), argv [iFile]);

Scan(pRoot);

} _ finally { /* Кучи и дескрипторы файлов всегда закрываются.

/* Уничтожить обе кучи и структуры данных. */

if (hNode !=NULL) HeapDestroy (hNode);

if (hNode != NULL) HeapDestroy (hData);

hNode = NULL;

hData = NULL;

if (hIn != INVALID_HANDLE_VALUE) CloseHandle (hIn);

}

} /* Конец основного цикла обработки файлов и try-блока. */

__except(EXCEPTION_EXECUTE_HANDLER) {

_stprintf(ErrorMessage, _T("\n%s %s"), _T("sortBT, ошибка при обработке файла:"), argv [iFile]);

ReportError(ErrorMessage, 0, TRUE);

}

return 0;

}

В программе 5.2 представлены функции, которые фактически реализуют алгоритмы поиска с использованием бинарного дерева. Первая из этих функций, FillTree, распределяет память в обеих кучах. Вторая функция, KeyCompare, используется также в нескольких других программах в данной главе. Заметьте, что функции FillTree и KeyCompare используют обработчики завершения и исключений программы 5.1, которая вызывает эти функции. Таким образом, ошибки распределения памяти будут обрабатываться основной программой, которая после этого продолжит свое выполнение, переходя к обработке следующего файла.

LPTNODE FillTree(HANDLE hIn, HANDLE hNode, HANDLE hData)

/* Заполнение дерева записями из входного файла. Используется обработчик исключений вызывающей программы. */

{

LPTNODE pRoot = NULL, pNode;

DWORD nRead, i;

BOOL AtCR;

TCHAR DataHold [MAX_DATA_LEN] ;

LPTSTR pString;

while (TRUE) {

/* Разместить и инициализировать новый узел дерева. */

pNode = HeapAlloc(hNode, HEAP_ZERO_MEMORY, NODE_SIZE);

/* Считать ключ из следующей записи файла. */

if (!ReadFile(hIn, pNode->Key, TKEY_SIZE, &nRead, NULL) || nRead != TKEY_SIZE) return pRoot;

AtCR = FALSE; /* Считать данные до конца строки. */

for (i = 0; i < MAX_DATA_LEN; i++) {

ReadFile(hIn, &DataHold [i], TSIZE, &nRead, NULL);

if (AtCR && DataHold [i] == LF) break;

AtCR = (DataHold [i] == CR);

}

DataHold[i – 1] = '\0';

/* Объединить ключ и данные — вставить в дерево. */

pString = HeapAlloc(hData, HEAP_ZERO_MEMORY, (SIZE_T)(KEY_SIZE + _tcslen (DataHold) + 1) * TSIZE);

memcpy(pString, pNode->Key, TKEY_SIZE);

pString [KEY_SIZE] = '\0';

_tcscat (pString, DataHold);

pNode->pData = pString;

InsertTree(&pRoot, pNode);

} /* Конец цикла while (TRUE). */

return NULL; /* Ошибка */

}

BOOL InsertTree(LPPTNODE ppRoot, LPTNODE pNode)

/* Добавить в дерево одиночный узел, содержащий данные. */

{

if (*ppRoot == NULL) {

*ppRoot = pNode;

return TRUE;

}

/* Обратите внимание на рекурсивные вызовы InsertTree. */

if (KeyCompare(pNode->Key, (*ppRoot)->Key) < 0) InsertTree(&((*ppRoot)->Left), pNode);

else InsertTree(&((*ppRoot)->Right), pNode);

}

static int KeyCompare(LPCTSTR pKey1, LPCTSTR pKey2)

/* Сравнить две записи, состоящие из обобщенных символов. */

{

return _tcsncmp(pKey1, pKey2, KEY_SIZE);

}

static BOOL Scan(LPTNODE pNode)

/* Рекурсивный просмотр и отображение содержимого бинарного дерева. */

{

if (pNode == NULL) return TRUE;

Scan(pNode->Left);

_tprintf(_T ("%s\n"), pNode->pData);

Scan(pNode->Right);

return TRUE;

}

Примечание

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

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

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