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

Обычная процедура использования куч не представляет никаких сложностей:

1. Получите дескриптор кучи, воспользовавшись одной из функций CreateНеар или GetProcessHeap.

2. Распределите блоки из кучи, используя функцию HeapAlloc.

3. В случае необходимости освободите все или только некоторые блоки при помощи функции HeapFree.

4. Уничтожьте кучу и закройте ее дескриптор при помощи функции HeapDestroy.

Этот процесс иллюстрируют рис. 5.2 и программа 5.2.

В отсутствие необходимости создания отдельных куч или генерации исключений программисты, которые привыкли использовать функции управления памятью из библиотеки С, могут использовать их и далее. При этом, если речь идет о куче процесса, функция malloc эквивалентна функции HeapAlloc, функция realloc — функции HeapReAlloc, а функция free — функции HeapFree. Функция calloc распределяет память и инициализирует объекты, и ее поведение легко эмулируется функцией HeapAlloc. Эквивалент функции HeapSize в библиотеке С отсутствует.

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

Программа sortBT (программа 5.1) реализует ограниченную версию UNIX-команды sort за счет создания бинарного дерева поиска с использованием двух куч. Ключи размещаются в куче узлов (node heap), представляющей дерево поиска. Каждый узел содержит левый и правый указатели, ключ и указатель на запись в куче данных (data heap). Заметьте, что куча узлов состоит из блоков фиксированного размера, тогда как куча данных содержит строки переменной длины. Наконец, отсортированный файл выводится путем обхода дерева.

В данном примере для использования в качестве ключа произвольно выбраны первые 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. Команда 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-блока. */