Сборка мусора и уплотнение на месте

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

1. Снять пометку со всех VoidPtr, отсутствующих в списке свободных указателей.

2. Пометить все VoidPtr с ненулевым счетчиком ссылок; то есть пометить объекты, доступные

непосредственно из стека.

3. Для каждого только что помеченного VoidPtr пометить все VoidPtr, внедренные в объекты,

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

Бейкера.

4. Повторять шаг 3, пока удается находить новые помечаемые объекты.

5. Удалить все VoidPtr, не помеченные и не находящиеся в списке свободных; в свою очередь, это приведет к вызову деструкторов указываемых объектов. Если вы не собираетесь выполнять уплотнение, следует вернуть память, занимаемую этими объектами.

6. Если уплотнение выполняется, перебрать все помеченные VoidPtr в порядке возрастания

адресов указываемых объектов и сместить объекты вниз для уплотнения фрагментированного пространства.

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