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

struct MemControlBlock {

bool avai1ab1e ; MemControlBlock* prev; MemControlBlock* next ;

Ha рис. 4.2 показано распределение пула памяти в виде дважды связанного списка блоков. Переменная-член size больще не нужна, поскольку размер блока можно вычислить с помощью выражения this->next - this. Дополнительные затраты памяти, связанные с необходимостью хранить два указателя и переменную типа bool, по-прежнему существуют. (Как и ранее, можно прибегнуть к системно-зависимым трюкам и запаковать булевскую переменную в один из указателей.)

/ / /

available prev пеуХ

available

prev

next

Рис. 4.2. Распределитель памяти с постоянным временем удаления

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

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

4.3. Распределитель памяти для небольших объектов

Распределитель памяти для небольших объектов работает с четырехслойной структурой, показанной на рис. 4.3. Ее верхние слои используют функциональные возможности, предоставляемые нижними слоями. На дне структуры расположен тип chunk. Каждый объект типа Chunk содержит участок памяти (chunk), состоящий из целого числа блоков фиксированного размера, и управляет им. Объекты типа Chunk позволяют выделять и освобождать блоки памяти. Если в объекте типа Chunk не осталось свободных блоков, функция распределения памяти вернет нуль.

В следующем слое расположен класс FixedAllocator. Объекты этого класса используют участки памяти в качестве строительных блоков. Основное предназначение класса FixedAllocator - удовлетворять запросы на выделение памяти, объем которой превышает размер участка. Для этого объекты класса FixedAllocator образовывают массив объектов типа Chunk. Если поступил запрос на выделение памяти и все существующие участки памяти заняты, объект класса FixedAllocator создает новый объект типа Chunk и записывает его в массив. Затем он выполняет запрос на вьщеле-ние памяти, переадресовывая его этому объекту.

Рис. 4.3. Многослойная структура распределителя памяти для небольших объектов

Класс SmanobjAllocator выполняет общие функции, связанные с выделением и освобождением памяти. Объекты этого класса состоят из нескольких объектов класса FixedAllocator, каждый из которых специализирован для выделения объектов определенного размера. В зависимости от требуемого количества байтов объекты класса SmanobJAllocator направляют запрос одному из объектов класса FixedAllocator или стандартному оператору ::operator new, если запращиваемый объем памяти слищком велик.

На верхнем уровне расположен класс SmallObject, представляющий собой оболочку класса FixedAllocator. Он инкапсулирует все функциональные возможности, связанные с распределением динамической памяти, и предоставляет их другим классам. Класс Smal -1 Object перефужает операторы new и delete и передает их объектам класса Small Ob j Allocate г. Таким образом, объекты, создаваемые профаммистом, могут наследовать функции для работы с динамической памятью от класса Small Object.

Кроме того, можно непосредственно использовать классы SmallObjAllocator и FixedAllocator. (Класс Chunk слищком примитивен и ненадежен, поэтому он определяется в закрытом разделе класса FixedAllocator.) Большей частью, однако, профаммы пользователей просто наследуют свойства базового класса SmallObjAllocator, приобретая функциональные возможности для распределения динамической памяти. Интерфейс этого класса достаточно прост.

4.4. Класс Chunk

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

Ниже приведено определение класса Chunk.

в классе нет закрытых полей - класс Chunk представляет собой

структуру старых простых данных (plain Old Data - POD).

Структура определяется внутри класса FixedAllocator

и управляется только им.

struct Chunk

void initCstd::si2e t blocksize, unsigned char blocks); void* AllocateCstd::size t blocksize); void DeallocateCvoid* p, std::size t blocksize); unsigned char* pData ;

unsigned char

fi rstAvailableBlock , Ы ocksAvai 1 аЫ e ;

Кроме указателя на управляемый участок памяти объект класса Chunk хранит следующие целочисленные величины.

Переменная fi rstAvai 1 аЫ еВТ оск хранит индекс первого доступного блока внутри порции памяти.

Переменная Ы ocksAvai 1 аЫ е представляет собой количество блоков, доступных в данной порции памяти.

Интерфейс класса Chunk очень прост. Функция Init инициализирует объект класса Chunk, а функция Release - освобождает занятую память. Функция Allocate вьщеляет блок памяти, а функция Deal 1 ocate освобождает его. Функциям Al 1 ocate и Deal 1 ocate нужно передавать размер памяти, поскольку в самом объекте класса Chunk эта величина не хранится, так как на верхних уровнях структуры размер блока неизвестен. Если бы в классе Chunk была предусмотрена переменная-член blockSize , это было бы пустой тратой времени и памяти. Не забьгеайте, что мы находимся на самом дне структуры - здесь все имеет значение. По соображениям эффективности в классе Chunk не определены ни конструкторы, ни деструктор, ни оператор присваивания. Попытка определить семантику копирования на этом уровне снизила бы эффективность работы верхних уровней структуры, на которых объекты класса Chunk хранятся внутри векторов.

Структура Chunk демонстрирует важные офаничения. Поскольку переменные blocksAvailable и firstAvailableBlock имеют тип unsigned char, порция не может содержать больще 255 блоков (на компьютерах, где символы состоят из 8 бит). Как мы вскоре убедимся, это решение вполне удачно и позволяет избежать многих неприятностей.

Перейдем теперь к более интересной теме. Блок может быть занят или свободен. Все, что необходимо сохранить, записывается в свободные блоки. В первом байте свободного блока хранится индекс следующего свободного блока. Поскольку первый доступный индекс хранится в переменной fi rstAvai 1 abl ев1 оск , мы получаем полноценный одно-связный список свободных блоков, не используя дополнительной памяти.

В момент инициализации объект класса Chunk выглядит, как показано на рис. 4.4. Код его инициализации приведен ниже.

void Chunk::lnitCstd::size t blocksize, unsigned char blocks) {

pData =new unsigned char[blockSize * blocks];

firstAvai1ablев1оск = 0;

blocksAvai1able = blocks;

unsigned char i = 0;

unsigned char* p = pData ;

for (; i != blocks; p += blocksize)

*p = ++i;

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