объекты, находящиеся в указанной половине. Итератор VoidPtrPoo1::iterator() из главы 15 заменяется следующим:

Включить в класс VoidPtrPool

class VoidPtrPool {

public:

VoidPtrIterator* Reachab1e()

{ return new ReachableIterator(this); } VoidPtrIterator* InRange(void* low, void* high)

{ return new RangeIterator(this); }

Указатели периметра

Один из типов итераторов, возвращаемых пулом, перебирает непосредственно доступные указатели (имеющие ненулевой счетчик ссылок). В сущности, перед нами тот же VoidPtrPoolIterator с одной изменившейся строкой - теперь Advance() пропускает позиции с нулевым счетчиком ссылок. Класс реализован как производный от VoidPtrPoolIterator.

class ReachableIterator : public VoidPtrPoolIterator { protected:

virtual void Advance() Найти следующую используемую позицию

VoidPtrPoolIterator::Advance(); while (block != NULL && b1ock->s1ots[s1ot].refcount == 0);

public:

Reachab1eIterator(VoidPtrBlock* vpb) : VoidPtrPoolIterator(vpb) {}

Недоступные указатели

В конце цикла мы должны пройтись по ведущим указателям и найти все те, которые продолжают ссылаться на неактивную половину. Это и будут недоступные объекты. Задачу решает следующий итератор, в котором используется очередное тривиальное переопределение VoidPtrPool Iterator.

class InRange : public VoidPtrPoolIterator { private:

void* low; Нижний адрес диапазона void* high; Верхний адрес диапазона

virtual void Advance() Найти следующую используемую позицию

VoidPtrPoolIterator::Advance(); while (block != NULL &&

(b1ock->s1ots[s1ot].address < low b1ock->s1ots[s1ot].address >= high));

public:

InRange(VoidPtrBlock* vpb, void* 1ow addr, void* high addr)

: VoidPtrPoolIterator(vpb), 1ow(1ow addr), high(high addr) {}

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

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

class MotherOfAllObject { Базовый класс для всех остальных public:

virtual VoidPtrIterator* Pointers() = 0;

template <c1ass Type>

class VoidPtrArrayIterator : public VoidPtrIterator { private:

VoidPtr* ptrs[Entries];

int next; Следующая позиция в переборе

public:

VoidPtrArrayIterator() : next(0)

for (int i = 0; i < Entries;

ptrs[i] = NULL;

VoidPtr*& operator[](uint slot) { return ptrs[s1ot]; } virtual bool More() { return next < Entries; } virtual VoidPtr* Next() { return ptrs[next++]; }

Пример класса и итератора

class Foo {

private:

WH<Bar> bar; public:

virtual VoidPtrIterator* Pointers()

new VoidPtrArrayIterator<1>* iterator = new VoidPtrArrayIterato<1>; iterator[0] = bar.Pointer(); return iterator;

VoidPtrArrayIterator сделан на скорую руку и в реальном проекте его использовать не стоит, но по крайней мере он демонстрирует общий принцип. Конечно, его следует дополнить проверками диапазонов и инициированием исключений, если будет затребован VoidPtr* для NULL. Foo::Pointers() показывает общий принцип использования VoidPtrArrayIterator. Для каждого класса мы изменяем размер массива, чтобы он совпадал с количеством WH<Widget> и добавляем для каждого дескриптора по одной строке вида iterator(index++) = widget.Pointer(). Этот шаблон справляется со всеми простыми случаями, в которых нам не приходится беспокоиться о базовых классах. Если Foo имеет базовые классы, придется организовать вложение итераторов для его собственных указателей и указателей базовых классов.

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

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

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

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

template <c1ass 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* Al1ocate(size t size)

void* space = active->Al1ocate(size); if (space == NULL) throw(OutOfMemory()); return space;

void Copy1();

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

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

void Space::Scanvege()

VoidPtrIterator* vpi =

VoidPtr::poo1->InRange(inactive, inactive + sizeof(*inactive)); while (vpi->More()) {

VoidPtr* vp = vpi->Next();

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

delete vpi;