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

Харт Джонсон М.
Шрифт:

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

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

Если используется Windows, то сфера применимости таких программ, как программа 5.1, ограничивается файлами небольшого размера, поскольку в виртуальной памяти должны находиться целиком весь файл и копии ключей. Абсолютный верхний предел размера файла определяется объемом доступного виртуального адресного пространства (максимум 3 Гбайт); фактически достижимый предел оказывается еще меньшим. В случае Win64 ограничения подобного рода практически отсутствуют.

В программе 5.1 вызываются некоторые функции управления деревом: FillTree, InsertTree, Scan и TreeCompare. Все они представлены в программе 5.2.

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

Программа 5.1. sortBT: сортировка с использованием бинарного дерева поиска 

/* Глава 5. Команда sortBT. Версия, использующая бинарное дерево поиска.*/

#include "EvryThng.h"

#define KEY_SIZE 8

typedef struct _TreeNode {/* Описание структуры узла. */

 struct _TreeNode *Left, *Right;

 TCHAR Key[KEY_SIZE];

 LPTSTR pData;

} TREENODE, *LPTNODE, **LPPTNODE;

#define NODE_SIZE sizeof(TREENODE)

#define NODE_HEAP_ISIZE 0x8000

#define DATA_HEAP_ISIZE 0x8000

#define MAX_DATA_LEN 0x1000

#define TKEY_SIZE KEY_SIZE * sizeof(TCHAR)

LPTNODE FillTree(HANDLE, HANDLE, HANDLE);

BOOL Scan(LPTNODE);

int KeyCompare (LPCTSTR, LPCTSTR); iFile;

BOOL InsertTree (LPPTNODE, LPTNODE);

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

 HANDLE hIn, hNode = NULL, hData = NULL;

 LPTNODE pRoot;

 CHAR ErrorMessage[256];

 int iFirstFile = Options(argc, argv, _T("n"), &NoPrint, NULL);

 /* Обработать все файлы, указанные в командной строке. */

 for (iFile = iFirstFile; iFile < argc; iFile++) __try {

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

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