логических объектов внутри него - одни являются переменными класса, а другие - базовыми классами. Как правило, адреса этих объектов отличны от того объекта, которому они принадлежат.

Анализ экземпляров

Алгоритмы сборки мусора обычно начинают свою работу с периметра. Для каждого объекта периметра составляется список объектов, которые он содержит и на которые ссылается. Затем для каждого такого объекта составляется новый список и т. д. Рекурсивный перебор продолжается до тех пор, пока удается находить новые объекты. Для этого нам понадобятся некоторые средства, которые позволяют для данного объекта найти все его внедренные объекты и указатели/ссылки.

В SmallTalk и других динамических языках описание структуры экземпляра является задачей объекта класса. В С++ существует несколько вариантов. Первые два решения (см. ниже) вполне практичны, а третье - отчаянная мера, которая подходит только для профессиональных каскадеров на закрытых треках.

Виртуальные функции

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

Объекты классов

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

Осведомленные указатели

В крайнем случае можно воспользоваться умными указателями и обращаться к ним с просьбой описать объект.

class Foo { private:

Bar* bar;

class PFoo { Умный указатель на Foo private:

Foo* foo; public:

FunctionThatEnumeratesPointersInFoo();

Почему я называю этот случай крайним? Вы рискуете тем, что указатель неверно определит тип объекта, на который он ссылается. Конечно, если PFoo - ведущий указатель, мы знаем, что foo действительно является Foo*, но что делать с bar? Как узнать, что это действительно Bar, а не что-то производное от него? Если Bar не имеет только что упоминавшейся самоописывающей виртуальной функции и не возвращает объект класса, остается одно - повсюду раскидать умные указатели и надеяться на лучшее.

class Bar {

class Pbar { Умный указатель на Bar

class Foo { private:

Pbar bar;

class PFoo { Умный указатель на Foo private:

Foo* foo; public:

FunctionThatEnumeratesPointersInFoo();

Теперь мы начинаем с одного умного указателя, PFoo, и рекурсивно находим другой, PBar . Каждый из этих умных указателей разбирается в особенностях строения объекта, на который он ссылается. В этом они превзошли умные указатели, поэтому я называю их осведомленнгми (ingenious), хотя циник, вероятно, назвал бы их нерассуждающими.

Перебор графа объектов

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

Рекурсивные функции и функторы

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

class Functor { Функция обратного вызова public:

virtual void App1y(MotherOfAllClasses*) = 0;

class MotherOfAllClasses { public:

Применить fn к каждому доступному объекту virtual void EachObject(Functor& fn);

Функция EachObject() вызывает fn.Apply(this), а затем вызывает EachObject() для каждого внедренного объекта или объекта, на который указывает переменная класса. Кроме того, EachObject() вызывает Base::EachObject() для каждого базового класса, таким образом члены базового класса тоже включаются в перечисление. В зависимости от алгоритма в MotherOfAllClasses можно включить бит признака, показывающий, что объект был рассмотрен ранее. Впрочем, как мы вскоре убедимся, иногда без этого можно обойтись.

Итераторы

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

class MOAOIterator { MotherOfAllObjectsIterator public:

virtual bool More() = 0;

virtual MotherOfAllObjects* Next() = 0;

class MotherOfAllObjects { public:

virtual MOAOIterator* EachObject();

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

Сборка мусора по алгоритму Бейкера

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

На данный момент мы не будем беспокоиться об объектах, доступных извне, и сосредоточим внимание на периметре стековых переменных.

Поскольку на этот раз мы занимаемся сборкой мусора, нет причин полагаться во всем на подсчет ссылок. Тем не менее, подсчет ссылок продолжает играть важную роль: он применяется для подсчета дескрипторов в стеке, ссылающихся на конкретный ведущий указатель. Ведущий указатель, у которого счетчик ссылок больше 0, непосредственно доступен из стека, а следовательно, входит в периметр. Мы воспользуемся сильными дескрипторами для стековых переменных и слабыми дескрипторами для ссылок из одного объекта на другой через переменные класса. VoidPtr и другие структуры данных из предыдущей главы остаются без изменений, за одним исключением: VoidPtr::Re1ease() не удаляет ведущий указатель при обнулении счетчика. Запомните: нулевой счетчик ссылок означает не то, что объект вообще недоступен, а лишь то, что он недоступен непосредственно из стека.

Шаблон слабого дескриптора

Слабый дескриптор устроен просто. template <c1ass Type> class WH {

friend class Hand1e<Type>; private:

BMP<Type>* pointer;

WH() : pointer(new BMP<Type> (new(object space) Type)) {}; BMP<Type>& operator->() { return *pointer; }

Он используется в переменных классов, которые ссылаются на другие объекты. class Foo { private:

WH<Bar> bar; При конструировании создает Bar + MP<Bar>

Шаблон сильного дескриптора

Шаблон сильного дескриптора идентичен шаблону слабого, за исключением того, что он поддерживает счетчик ссылок для указателя.

template <c1ass Type>

class SH {

private:

BMP<Type>* pointer; public:

SH() : pointer(new BMP<Type>(new Type)) { pointer->Grab(); } SH(const SH<Type>& h) : pointer(h.pointer) { pointer->Grab(); }