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

Пример: сортировка файлов с использованием бинарного дерева поиска

Пример: сортировка файлов с использованием бинарного дерева поиска

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

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

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

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

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

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] = '';
  /* Объединить ключ и данные — вставить в дерево. */
  pString = HeapAlloc(hData, HEAP_ZERO_MEMORY, (SIZE_T)(KEY_SIZE + _tcslen (DataHold) + 1) * TSIZE);
  memcpy(pString, pNode->Key, TKEY_SIZE);
  pString [KEY_SIZE] = '';
  _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 ("%sn"), pNode->pData);
 Scan(pNode->Right);
 return TRUE;
} 

Оглавление книги