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

Программа 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++) {
 ReadFile(hIn, &DataHold [i], TSIZE, &nRead, NULL);
 if (AtCR && DataHold [i] == LF) break;
 AtCR = (DataHold [i] == CR);
 }
 DataHold[i – 1] = '\0';
 /* Объединить ключ и данные — вставить в дерево. */
 pString = HeapAlloc(hData, HEAP_ZERO_MEMORY, (SIZE_T)(KEY_SIZE + _tcslen (DataHold) + 1) * TSIZE);
 memcpy(pString, pNode->Key, TKEY_SIZE);
 pString [KEY_SIZE] = '\0';
 _tcscat (pString, DataHold);
 pNode->pData = pString;
 InsertTree(&pRoot, pNode);
 } /* Конец цикла while (TRUE). */
 return NULL; /* Ошибка */
}

BOOL InsertTree(LPPTNODE ppRoot, LPTNODE pNode)
/* Добавить в дерево одиночный узел, содержащий данные. */
{
 if (*ppRoot == NULL) {
 *ppRoot = pNode;
 return TRUE;
 }
 /* Обратите внимание на рекурсивные вызовы InsertTree. */
 if (KeyCompare(pNode->Key, (*ppRoot)->Key) < 0) InsertTree(&((*ppRoot)->Left), pNode);
 else InsertTree(&((*ppRoot)->Right), pNode);
}

static int KeyCompare(LPCTSTR pKey1, LPCTSTR pKey2)
/* Сравнить две записи, состоящие из обобщенных символов. */
{
 return _tcsncmp(pKey1, pKey2, KEY_SIZE);
}

static BOOL Scan(LPTNODE pNode)
/* Рекурсивный просмотр и отображение содержимого бинарного дерева. */
{
 if (pNode == NULL) return TRUE;
 Scan(pNode->Left);
 _tprintf(_T ("%s\n"), pNode->pData);
 Scan(pNode->Right);
 return TRUE;
}

Примечание

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

Отображение файлов

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

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

• Отпадает необходимость в выполнении операций непосредственного файлового ввода/вывода (чтения и записи).

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

• Становится возможным применение удобных и эффективных алгоритмов, ориентированных на работу с файлами "в памяти" (in-memory files) (сортировка, деревья поиска, обработка строк и тому подобное), которые позволяют обрабатывать хранящиеся в файлах данные даже в тех случаях, когда размеры файлов значительно превышают доступный объем физической памяти. При больших размерах файлов особенности организации страничного обмена могут оказывать заметное влияние на производительность.

• В некоторых случаях значительно повышается эффективность обработки файлов.

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

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

• Отпадает необходимость в расходовании излишнего пространства файла подкачки. 

ОС сама использует методы отображения файлов для реализации DLL, а также для загрузки и выполнения исполняемых (.EXE) файлов. Библиотеки DLL описаны в конце настоящей главы.

Объекты отображения файлов

Сначала необходимо создать для открытого файла объект отображения файла (file mapping object), у которого имеется дескриптор, а затем отобразить этот файл или только некоторую его часть на виртуальное адресное пространство процесса. Объектам отображения можно присваивать имена, по которым к ним смогут обращаться другие процессы, разделяющие память совместно с данным процессом. Кроме того, объекты отображения файлов имеют параметры размера и атрибуты защиты.