Чтение онлайн

на главную

Жанры

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

Программа 5.2. FillTree и другие функции управления деревом поиска 

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++) {

Поделиться:
Популярные книги

Пустоцвет

Зика Натаэль
Любовные романы:
современные любовные романы
7.73
рейтинг книги
Пустоцвет

Комбинация

Ланцов Михаил Алексеевич
2. Сын Петра
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Комбинация

Адмирал южных морей

Каменистый Артем
4. Девятый
Фантастика:
фэнтези
8.96
рейтинг книги
Адмирал южных морей

Совок 5

Агарев Вадим
5. Совок
Фантастика:
детективная фантастика
попаданцы
альтернативная история
6.20
рейтинг книги
Совок 5

Внешняя Зона

Жгулёв Пётр Николаевич
8. Real-Rpg
Фантастика:
фэнтези
попаданцы
рпг
5.00
рейтинг книги
Внешняя Зона

Титан империи 3

Артемов Александр Александрович
3. Титан Империи
Фантастика:
фэнтези
попаданцы
5.00
рейтинг книги
Титан империи 3

Великий князь

Кулаков Алексей Иванович
2. Рюрикова кровь
Фантастика:
альтернативная история
8.47
рейтинг книги
Великий князь

Ледяное проклятье

Михайлов Дем Алексеевич
4. Изгой
Фантастика:
фэнтези
9.20
рейтинг книги
Ледяное проклятье

Бремя империи

Афанасьев Александр
Бремя империи - 1.
Фантастика:
альтернативная история
9.34
рейтинг книги
Бремя империи

Генерал Скала и сиротка

Суббота Светлана
1. Генерал Скала и Лидия
Любовные романы:
любовно-фантастические романы
6.40
рейтинг книги
Генерал Скала и сиротка

Ты не мой Boy 2

Рам Янка
6. Самбисты
Любовные романы:
современные любовные романы
короткие любовные романы
5.00
рейтинг книги
Ты не мой Boy 2

Романов. Том 1 и Том 2

Кощеев Владимир
1. Романов
Фантастика:
фэнтези
попаданцы
альтернативная история
5.25
рейтинг книги
Романов. Том 1 и Том 2

Убивать чтобы жить 6

Бор Жорж
6. УЧЖ
Фантастика:
боевая фантастика
космическая фантастика
рпг
5.00
рейтинг книги
Убивать чтобы жить 6

Законы Рода. Том 4

Flow Ascold
4. Граф Берестьев
Фантастика:
юмористическое фэнтези
аниме
5.00
рейтинг книги
Законы Рода. Том 4