Перебор указателей

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

Интерфейс Space слегка отличается от того, который использовался для уплотнения. Вместо одного итератора приходится поддерживать стек итераторов, поскольку мы перемещаемся по графу объектов. Кроме того, появилась новая функция Scavenge(), которая вызывается в конце каждого прохода по половине. Предполагается, что у нас уже имеется готовый шаблон стека Stack.

template <class Type>

class Stack {

public:

Push(Type*);

Type* Pop(); // Возвращает NULL для пустого стека

};

class Space {

private:

VoidPtrIterator* iterator; // Итератор верхнего уровня

Stack<VoidPtrIterator> iterator_stack;

HalfSpace A, B;

HalfSpace* active;

HalfSpace* inactive;

void Scavenge(); // Уничтожить недоступные объекты

void Swap(); // Переключить активную половину

public:

Space() : active(&a), inactive(&B), iterator(NULL) { Swap(); }

void* Allocate(size_t size)

{

void* space = active->Allocate(size);

if (space == NULL) throw(OutOfMemory());

return space;

}

void Copy1();

};

Три ключевые функции - Scavenge(), Swap() и Copy1() - ниже рассматриваются более подробно.

Scavenge

Функция Scavenge() вызывается после одного полного цикла. Она перебирает все ведущие указатели и ищет объекты, оставшиеся в неактивной половине. Эти объекты недоступны. Для каждого объекта она удаляет указатель, который, в свою очередь, вызывает деструктор объекта.

void Space::Scanvege()

{

VoidPtrIterator* vpi =

VoidPtr::pool->InRange(inactive, inactive + sizeof(*inactive));

while (vpi->More()) {

VoidPtr* vp = vpi->Next();

delete vp; // Вызывает деструктор указываемого объекта

}

delete vpi;

}

Swap

Функция Swap() переключает активную половину. Сначала она вызывает Scavenge() в завершение предыдущего цикла, а потом сбрасывает все в исходное состояние, чтобы при следующем вызове функции Copy1() копирование пошло в обратную сторону.

void Space::Swap()

{

Scavenge(); // Уничтожить объекты в неактивной половине

if (active == &A)

{

active = &B;

inactive = &A;

}

else

{

active = &A;

inactive = &B;

}

active->Reinitialize();

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

}

Copy1

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

void Space::Copy1()

{

if (!iterator->More())

{

// Перебор закончен, удалить итератор и вытолкнуть из стека

delete iterator;

iterator = iterator_stack.Pop();

if (iterator == NULL) // Готово!

Swap(); // Начинаем двигаться в другую сторону

}

else

{

VoidPtr* vp = iterator->Next();

if (vp->address >= &inactive &&

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

{

// Объект доступен и его нужно переместить

void* new_space = active->Allocate(vp->size);

if (new_space == NULL)

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

memcpy(new_space, vp->address, vp->size);

vp->address = new_space;

iterator_stack.Push(iterator);

iterator = vp->address->Pointers();

}

// Иначе перемещение уже состоялось

}

}