active = &A; inactive = &B;

active->Rei nitia1ize();

Перебрать все VoidPtr и найте активные объекты VoidPtrIterator* iterator = VoidPtr::poo1->iterator(); while (iterator->More())

VoidPtr* vp = iterator->Next(); if (vp->address >= inactive &&

vp->address < inactive + sizeof(*inactive))

void* new space = active->Al1ocate(vp->size); if (new space == NULL)

Исключение - нехватка памяти memcpy(new space, vp->address, vp->size); vp->address = new space;

delete iterator;

Все существенное происходит в цикле while функции Space::Swap(). Каждый объект в предыдущей, ранее активной половине копируется в новую активную половину. Вскоре вы поймете, зачем мы проверяем, принадлежит ли адрес старой половине.

Оператор new

Конечно, у нас появляется перегруженный оператор new, который использует эту структуру. void* operator new(size t size, Space* space)

return space->Al1ocate(size);

Ведущие указатели

Наконец, ведущие указатели должны использовать это пространство при создании объектов. template <c1ass Type> class BMP : public VoidPtr {

private: Запретить копирование и присваивание указателей BMP(const MP<Type>&) {}

BMP<Type>& operator=(const BMP<Type>&) { return *this; } public:

BMP() : VoidPtr(new(object space) Type, sizeof(Type)) {} virtual ~BMP() { ((Type*)address->Type::~Type(); } Type* operator->() { return (Type*)address; }

Здесь object space - глобальная переменная (а может быть, статическая переменная класса VoidPtr), которая ссылается на рабочее пространство Space.

Последовательное копирование

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

На мосту Бей-Бридж в Сан-Франциско постоянно работает бригада маляров. Она начинает красить мост с одного конца и через пару лет успешно докрашивает до другого. К этому времени можно начинать красить заново, в другую сторону. Работа идет постоянно, не считая редких перерывов из-за землетрясений или демонстраций протеста. В сущности, именно так алгоритм Бейкера превращается в схему последовательного уплотнения.

Начинаем следующий заход на класс Space. Функция Swap() делится на две части, одна из которых переключает активные половины, а другая многократно вызывается и при каждом вызове копирует по одному объекту.

class Space {

private:

VoidPtrIterator* iterator; Информация о копировании

HalfSpace A, B; HalfSpace* active; HalfSpace* inactive;

void Swap(); Переключить активную половину, скопировать объекты public:

Space() : active(&A), inactive(&B), iterator(NULL) { Swap(); } void* Al1ocate(size t size); void Copy1();

void* Space::Al1ocate(size t size)

void* space = active->Al1ocate(size); if (space != NULL)

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

void Space::Swap()

if (active == &A)

active = &B; inactive = &A;

else

active = &A; inactive = &B;

active->Rei nitia1ize(); delete iterator;

iterator = VoidPtr::poo1->iterator();

void Space::Copy1()

if (!iterator->More())

Swap(); Начать работу в другую сторону

else

VoidPtr* vp = iterator->Next(); if (vp->address >= inactive &&

vp->address < inactive + sizeof(*inactive))

void* new space = active->Al1ocate(size); if (new space == NULL)

throw(OutOfMemory()); memcpy(new space, vp->address, vp->size); vp->address = new space;

Функцию Copy1() необходимо вызывать как можно чаще, однако делать это можно в ходе нормальной работы программы. Новые объекты размещаются в активной половине, смешиваются со скопированными объектами, но это не приносит вреда. Поскольку перед копированием мы убеждаемся, что объект в данный момент находится в неактивном пространстве, созданные в активной половине объекты остаются без изменений.

Внешние объекты

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

SystemCa11(&aString); aString не следует перемещать до тех пор,

пока его адрес остается в распоряжении системы

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

class Space { public:

void Externa1ize(VoidPtr* vp)

void* space = ::operator new(vp->size); memcpy(space, vp->address, vp->size); vp->address = space;

void Interna1ize(VoidPtr* vp)

void* space = Al1ocate(vp->size); memcpy(space, vp->address, vp->size); ::operator de1ete(vp->address); vp->address = space;