Компьютерные книги
Главное меню
Главная Поиск по сайту Добавить материал О нас Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Языки программирования -> Кубенский А.А. -> "Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++" -> 103

Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ - Кубенский А.А.

Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ — Спб.: БВХ-Петербург , 2004. — 464 c.
ISBN 5-94157-506-8
Скачать (прямая ссылка): strukturiialgoritmiobrabotkidannih2004.djvu
Предыдущая << 1 .. 97 98 99 100 101 102 < 103 > 104 105 106 107 108 109 .. 161 >> Следующая

На рис. 5.1 показана схема организации пула памяти в такой системе. Штриховкой выделены участки, содержащие блоки, уже отданные системой и используемые другими частями программы. В нижней части рисунка в области больших адресов по пулу памяти находится свободная область памяти, из которой выделяются новые, еще не распределенные ранее блоки. Нарисован также связанный список свободных блоков памяти, которые были когда-то выделены системой, а потом возвращены обратно.
Рис. 5.1. Схема организации памяти для системы управления памятью с блоками постоянной длины
Теперь уже легко запрограммировать соответствующий класс. В листинге 5.4 определен шаблон класса BiockBuffer и реализованы операции get и release для управления памятью. Параметром шаблона является размер выделяемых блоков памяти в байтах. Для того чтобы система работала правильно, необ-
Алгоритмы распределения памяти
297
ходимо, чтобы в свободных блоках памяти можно было организовать список, а это возможно, только если в таком блоке достаточно места для размещения указателя. Мы не делаем такую проверку, считая, что параметр шаблона blockSize заведомо больше величины sizeof (void *).
Для организации работы системы используются арифметические операции над указателями. Так, например, в реализации метода get для того, чтобы получить указатель на первый байт свободной области памяти, используется выражение (char *) buffer + freeArea*biocksize, где buffer— указатель на всю распределяемую память, freeArea— индекс первого свободного байта в области нераспределенной памяти, a biocksize — размер выделяемых блоков памяти. Работа со списком свободных блоков тоже требует аккуратной работы с указателями. Например, чтобы извлечь из памяти указатель, хранящийся в начале свободного блока с адресом freePtr, требуется написать выражение
* (void **) freePtr.
// Класс BlockBuffer представляет буферный пул памяти и систему // управления ею для размещения в ней блоков постоянного размера
public :
// Конструктор:
BlockBuffer(int n) {
buffer = calloc(size = n, blockSize); if (buffer == NULL) {
throw NoMoreMemoryException () ;
}
clear();
//=
template <int blockSize> class BlockBuffer {
void * buffer;
int size;
// Указатель на буфер // Размер буфера в блоках
// Указатели свободных блоков:
void * freePtr; int freeArea;
// в списке свободных блоков
// в области нераспределенной памяти
// Деструктор:
-BlockBuffer() { free(buffer); }
298
Гпава 5
П Очистка памяти, void clear() { freePtr = NULL; freeArea = 0;
}
11 Операция выделения элемента свободной части буфера void * get() { if (freePtr) {
void * ret = freePtr; freePtr = *(void **)freePtr;
} else if (freeArea < size) {
return (char *)buffer + (freeArea++)*blockSize;
} else {
throw NoMoreMemoryException () ;
}
}
void release(void * ptr) {
*(void **)ptr = freePtr; freePtr = ptr;
}
};
Реализованную с помощью класса BlockBuffer систему управления памятью можно использовать при отведении памяти под значения какого-либо одного класса. Пусть, например, в программе организуется дерево поиска с элементами типа string, причем известно, что количество элементов в этом дереве не будет превышать тысячи. Используем только что реализованную систему распределения памяти для размещения в ней элементов этого дерева.
Здесь мы не будем переопределять операторы new и delete для узлов дерева. Вместо этого используем еще одну возможность языка C++: при вызове стандартного оператора new будем явно указывать ту область памяти, в которой следует размещать новый узел дерева. Разумеется, это будет область памяти, выделенная нашей системой распределения памяти.
Итак, в нашей программе будут участвовать система распределения и управления памятью, представленная объектом memoryManagement класса BlockBuffer, словарь, представленный ДВОИЧНЫМ деревом поиска класса TreeDictionary, и узлы этого дерева, которые будут размещаться в областях памяти, предоставляемых системой memoryManagement. Объект memoryManagement создадим В МО-мент исполнения конструктора класса TreeDictionary. Именно дерево будет отвечать за использование этой системы и размещать в ней узлы дерева. Зна-
Алгоритмы распределения памяти
299
чением параметра, определяющего размер выделяемых блоков, будет размер узла дерева в байтах. Далее, при добавлении в словарь новых слов дерево будет обычным образом вызывать оператор new для создания нового узла, но в качестве памяти для размещения нового узла будет указывать блок, выделенный системой memoryManagement.
В нашем маленьком примере слова не будут удаляться из словаря, однако если бы удаление слов все же нужно было реализовать для класса TreeDictionary, то использовать для этого оператор delete было бы некорректно. Вместо этого надо было бы возвращать освободившийся блок памяти в систему, вызывая метод release. Правда, в этом случае не отработает деструктор класса Treeitem. На самом деле, если планируется реализовать удаление слов из словаря, то лучше было бы отводить память под элементы нашего дерева несколько по-другому, переопределив, как и раньше, операторы new и delete для класса Treeitem. Если же, как в приведенном ниже примере, слова в словарь только добавляются, а заботиться о том, чтобы для каждого элемента словаря вызывался деструктор нет необходимости, то вместо уничтожения отдельных узлов дерева можно просто в деструкторе дерева вызвать деструктор системы распределения памяти, освободив разом всю захваченную ею память.
Предыдущая << 1 .. 97 98 99 100 101 102 < 103 > 104 105 106 107 108 109 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.