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, мы пропускаем ее. Во всем остальном работа сводится к простому перебору в массивах, образующих блоки указателей.

Вариации

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

Невидимые ведущие указатели

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

class Foo { public:

static Foo* make(); Возвращает пару указатель-указываемый объект

virtual void Member1() = 0;

И т.д. для открытого интерфейса

В файле foo.cpp

class FooPtr : public Foo, public VoidPtr { public:

FooPtr(Foo* foo, size t size) : VoidPtr(foo, size) {} virtual ~FooPtr() { delete (Foo*)address; } virtual void Member1()

{ ((Foo*)address)->Member1(); } И т.д. для остальных открытых функций

class RealFoo : public Foo { ... }; Foo* Foo::make()

return new FooPtr(new RealFoo, sizeof(RealFoo));

В клиентском коде class Bar { private:

Foo* foo; На самом деле невидимый указатель public:

Bar() : foo(Foo::make()) {}

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

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

Возможен и другой вариант - потребовать, чтобы все объекты происходили от общего класса-предка, способного возвратить объект класса для данного объекта или, по крайней мере, размер объекта. В этом случае вам уже не придется хранить в указателе объект экземпляра, поскольку его можно будет получить у объекта класса. Если вы готовы смириться с некоторым насилием в отношении типов в дескрипторах, это также позволит вам избежать шаблонов второго уровня, используемых для главных указателей. Вместо void* в VoidPtr можно будет хранить CommonBase* (где CommonBase - общий базовый класс). Мы избавляемся от переменной size, от необходимости иметь шаблон, производный от VoidPtr, и от виртуального деструктора в VoidPtr, и как следствие - от 4-байтового адреса v-таблицы. С другой стороны, если управляемые объекты уже содержат v-таблицы и не принуждают вас к применению множественного наследования, дополнительных затрат не будет.