указываемых объектов. Конструкторы (см. далее) напрямую работают с переменной VoidPtrPool ::tai1. Деструктор исключает экземпляр из списка. Во всем остальном класс VoidPtr остался прежним. Ниже показаны изменения в VoidPtr.

class VoidPtr { private:

Новые переменные для ведения списка VoidPtr* next; Следующий элемент списка

VoidPtr* previous; Предыдущий элемент списка

protected:

Изменившиеся конструкторы

VoidPtr() : address(NULL), size(0), refcount(0),

next(NULL), previous(NULL) {} VoidPtr(void* addr, size t s) : address(addr), size(s), refcount(0),

next(NULL), previous(poo1->tai1->previous)

poo1->tai1->next = this; poo1->tai1 = this;

public:

Измененный деструктор virtual ~VoidPtr()

if (size != 0) Активный указатель - исключить из списка {

if (previous != NULL)

previous->next = next; if (next != NULL)

next->previous = previous; if (poo1->tai1 == this)

poo1->tai1 = previous;

size = 0; address = NULL;

Пул ведущих указателей

Изменения в пуле ведущих указателей VoidPtrPool также весьма тривиальны. class VoidPtrPool { Как и прежде, плюс следующее friend class VoidPtr; Обеспечивает доступ к tail private:

Новые переменные для ведения списка

VoidPtr head; Фиктивный VoidPtr, который ссылается

на список активных указателей VoidPtr* tail; Конец списка public:

Новая версия конструктора

VoidPtrPoo1() : b1ock 1ist(NULL), free 1ist(NULL), tai1(&head) {}

Класс VoidPtrPool идентичен тому, который использовался в алгоритме Бейкера, с добавлением связанного списка активных VoidPtr .

Итератор ведущих указателей

Итератор ведущих указателей устроен элементарно. Он просто перебирает элементы списка от начала к концу - иначе говоря, от нижних адресов памяти к верхним.

class VoidPtrPoollterator : public VoidPtrlterator { private:

VoidPtr* next; public:

VoidPtrIterator(VoidPtr* first) : next(first) {} virtual bool More() { return next != NULL; } virtual VoidPtr* Next()

VoidPtr* vp = next; next = next->next; return vp;

VoidPtrIterator* VoidPtrPoo1::iterator()

return new VoidPtrPoolIterator(&head.next);

Алгоритм уплотнения

Алгоритм уплотнения выглядит так просто, что его можно было бы и не приводить. class Space { private:

unsigned long next byte;

unsigned char bytes[SPACESIZE]; public:

Space() : next byte(0) {}

void* Al1ocate(size t size);

void Compact();

void* Space::Al1ocate(size t size)

Выровнять на границу слова

size = ROUNDUP(size);

if (next byte + size > SPACESIZE)

Compact();

if (next byte + size > SPACESIZE)

Исключение - нехватка памяти

void* space = &bytes[next byte]; next byte += size; return space;

void Space::Compact()

next byte = 0;

VoidPtrIterator* iterator = VoidPtrPoo1::iterator(); while (iterator->More())

VoidPtr* vp = iterator->Next(); void* space = Al1ocate(vp->size);

if (space < vp->address) Проверить, что объект поместится

delete iterator;

Оптимизация

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

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

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

Последовательное уплотнение на месте

Алгоритм уплотнения на месте нетрудно приспособить для условий последовательного уплотнения в фоновом режиме. Все просто: мы сохраняем VoidPtrIterator в виде переменной класса Space и используем его, чтобы смещать вниз один объект при каждом вызове функции Copy1(). Реализация проста и прямолинейна, необходимо лишь соблюдать осторожность с удалением во время уплотнения. Помните, что в процессе перебора списка VoidPtr удаляется один из его элементов. Это простой частный случай проблемы надежности итераторов, которую мы обсуждали в главе 8.

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

Глава получилась очень длинной, а подобная схема уплотнения редко применяется на практике. Подробности оставляю читателю в качестве самостоятельных упражнений.

Перспективы

Программистам на С++ обычно не так уж часто приходится беспокоиться об уплотнении, поэтому все сказанное стоит воспринимать со здоровым скепсисом. Если вам удастся организовать нормальный подсчет ссылок, уплотнение может оказаться приятным дополнением, но в целом эта глава готовит почву для приемов сборки мусора, рассмотренных в следующей главе. Кроме того, она помогает очертить внешние границы языка, поскольку С++ по своей сути не рассчитан на свободное перемещение объектов в памяти.