Type* operator->() { return (Type*)address; }

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

Это уже знакомый нам шаблон дескриптора с подсчетом ссылок из предыдущей главы. template <c1ass Type> class Handle { private:

MP<Type>* pointer; public:

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

{ pointer->Grab(); } Hand1e<Type>& operator=(const Hand1e<Type>& h)

if (this == &h) return *this;

if (pointer == h.pointer) return *this;

pointer->Re1ease();

h.pointer->Grab();

return *this;

MP<Type>& operator->() { return *pointer; }

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

H<Foo> foo; public:

void f();

void Bar::f()

Hand1e<Foo> f; Эквивалентно Foo* f = new Foo;

f = foo; Использует operator=(Hand1e<Type>(foo));

foo = f; Использует оператор H<Type>(f)

Пул ведущих указателей

Простоты ради мы предположим, что классы, производные от VoidPtr, совпадают по размеру с самим VoidPtr; иначе говоря, в них не добавляются новые переменные. Наша задача упрощается; VoidPtrPool теперь может быть простым связанным списком массивов VoidPtr. Структура массива называется VoidPtrBlock.

struct VoidPtrBlock {

VoidPtrBlock* next; Следующий блок в списке VoidPtr s1ots[BLOCKSIZE]; Массив позиций

VoidPtrBlock(VoidPtrBlock* next in 1ist) : next(next in 1ist)

Организовать новые позиции в связанный список for (int i = 0; i < BLOCKSIZE - 1;

s1ots[i].address = &s1ots[i + 1]; s1ots[BLOCKSIZE - 1].address = NULL;

~VoidPtrBlock() { delete next; }

class VoidPtrPool { private:

VoidPtr* free 1ist; Список свободных VoidPtr VoidPtrBlock* b1ock size; Начало списка блоков

public:

VoidPtrPoo1() : b1ock 1ist(NULL), free 1ist(NULL) {}

~VoidPtrPoo1() { delete b1ock 1ist; }

VoidPtr* Al1ocate();

void Dea11ocate(VoidPtr* vp);

VoidPtr* VoidPtrPool::Al1ocate()

if (free 1ist == NULL) Выделить дополнительный блок

b1ock 1ist = new VoidPtrBlock(b1ock 1ist); Добавить в список

b1ock 1ist->s1ots[BLOCKSIZE - 1].address = free 1ist; free 1ist = &b1ock 1ist->s1ots[0];

VoidPtr* space = (VoidPtr*)free 1ist; free 1ist = (VoidPtr*)space->address; return space;

void VoidPtrPoo1::Dea11ocate(VoidPtr* p)

vp->address = free 1ist; free 1ist = (VoidPtr*)vp->address; vp->size = 0;

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

Итератор ведущих указателей

Для перебора всех ведущих указателей мы создадим класс итератора с именем VoidPtrIterator . VoidPtrPool возвращает итератор, перебирающий все активные указатели (то есть все указатели, не присутствующие в списке свободных). Он будет объявлен как чисто абстрактный базовый класс, поскольку в следующей главе тот же интерфейс будет использован для перебора указателей, внедренных в объекты.

class VoidPtrlterator { protected:

VoidPtrIterator() {}

public:

virtual bool More() = 0;

virtual VoidPtr* Next() = 0;

Сам итератор работает весьма прямолинейно. Он просто перебирает блоки в цикле и ищет указатели с ненулевым значением переменной size.

class VoidPtrPoollterator : public VoidPtrlterator { private:

VoidPtrBlock* block;

int slot; Номер позиции в текущем блоке

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

while (block != NULL) {

if (slot >= BLOCKSIZE)

block = b1ock->next; slot = 0;

else if (b1ock->s1ots[s1ot].size != 0)

break; s1ot++;

public:

VoidPtrPoolIterator(VoidPtrBlock* vpb)

: block(vpb), s1ot(0), { Advance(); } virtual bool More() { return block != NULL; } virtual VoidPtr* Next()

VoidPtr* vp = &b1ock->s1ots[s1ot];

Advance();

return vp;

Кроме того, мы добавим в VoidPtrPool следующую функцию: VoidPtrIterator* iterator()

{ return new VoidPtrPoolIterator(this); }

Наконец, нам пришлось объявить VoidPtrPoolIterator другом VoidPtr, чтобы в программе можно было обратиться к его переменной size. Забегая вперед, скажу, что в главе 16 мы воспользуемся этим итератором для других целей; поэтому функция Advance() и объявлена виртуальной, чтобы производные классы могли добавить свою собственную фильтрацию. Если найденная позиция имеет нулевое значение size, мы пропускаем ее. Во всем остальном работа сводится к простому перебору в массивах, образующих блоки указателей.

Вариации

Перед тем как описывать сами алгоритмы уплотнения, давайте рассмотрим другие варианты исходной постановки задачи. Они не оказывают принципиального влияния на архитектуру или алгоритмы, а только на идиомы С++ в их реализации.