Джонсон Харт - Системное программирование в среде Windows
• Программа не использует потоки (глава 7), или, точнее, процесс (глава 6) имеет только один поток. В данной главе этот флаг используется во всех примерах.
• Каждый поток имеет собственную кучу или набор куч, и никакой другой поток не имеет доступа к этой куче.
• Программа располагает собственным механизмом взаимоисключающей блокировки, который предотвращает одновременный доступ к куче сразу нескольких потоков, использующих функции HeapAlloc и HeapAlloc. Для этой цели также могут применяться функции HeapLock и HeapUnlock.
Флаг HEAP_GENERATE_EXCEPTIONSРазрешение исключений вместо возврата значений NULL в случае сбоев при распределении памяти позволяет избавиться от утомительной необходимости тестирования результатов каждой попытки такого распределения. К тому же, обработчики исключений или завершения могут производить очистку памяти, которая к этому моменту была частично распределена. Эта методика применена в нескольких примерах.
Возможны два кода исключения:
1. STATUS_NO_MEMORY: это значение указывает на то, что системе не удалось создать блок запрошенного объема. Причинами этого могут быть фрагментация памяти, достижение нерастущей кучей максимально допустимого размера или исчерпание всей доступной памяти растущими кучами.
2. STATUS_ACCESS_VIOLATION: это значение указывает на повреждение кучи.
Одной из возможных причин этого может быть выполнение программой записи в память с выходом за границы распределенного блока.
Другие функции кучи
Функция HeapCompact пытается уплотнить, или дефрагментировать, смежные блоки в куче. Функция HeapValidate пытается обнаруживать повреждения кучи. Функция HeapWalk перечисляет блоки в куче, а функция GetProcessHeaps получает все действительные дескрипторы куч.
Функции HeapLock и HeapUnlock позволяют потоки сериализовать доступ к куче, о чем говорится в главе 8.
Имейте в виду, что эти функции не работают под управлением Windows 9x или Windows СЕ. Кроме того, имеются некоторые вышедшие из употребления функции, которые использовались ранее для совместимости с 16-битовыми системами. Мы упомянули об этих функциях лишь для того, чтобы лишний раз подчеркнуть тот факт, что многие функции продолжают поддерживаться, хотя никакой необходимости в них больше нет.
Резюме: управление кучами
Обычная процедура использования куч не представляет никаких сложностей:
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.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);
/* Обработать входной файл, создавая дерево. */
