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

В данном примере для использования в качестве ключа произвольно выбраны первые 8 байтов строки, а не целая строка. В двух других вариантах реализации сортировки, приведенных в настоящей главе (программы 5.4 и 5.5), выполняется сортировка индексированных файлов, а показатели производительности всех трех программ сравниваются в приложении В.

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

Примечание

Фактическое расположение куч и блоков в пределах куч зависит от варианта реализации Windows, а также от предыстории использования памяти процессом, включая рост кучи сверх ее начального размера. Кроме того, после увеличения размера растущей кучи с выходом за границы начальной области она может уже не занимать непрерывное адресное пространство. Наиболее оптимальная практика программирования состоит в том, чтобы не делать относительно фактической топологии распределения памяти никаких предположений; просто используйте функции управления памятью так, как это определяют правила работы с ними.

Рис. 5.2. Управление памятью при наличии нескольких куч

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

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

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

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

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