Ведущие указатели
Как и во многих других стратегиях управления памятью, нам придется хранить множество различных ведущих указателей в одной структуре с возможностью перебора. Напрашивается общий абстрактный базовый класс для всех ведущих указателей. К нашим ведущим указателям предъявляются следующие требования:
1. Ведение счетчика ссылок.
2. Хранение их в специальном пространстве памяти с поддержкой перебора.
3. Вызов деструктора указываемого объекта в деструкторе указателя. В зависимости от
используемого алгоритма сборки мусора мы одновременно пытаемся (или не пытаемся)
вернуть занимаемую объектом память. В нашем примере не стоит беспокоиться о возврате
памяти объекта.
Базовый класс VoidPtr
Ниже показан абстрактный базовый класс, удовлетворяющий этим требованиям.
class VoidPtrPool; // Используется для создания, уничтожения
// и перебора VoidPtr
class VoidPtr {
friend class VoidPtrPool;
private:
unsigned long refcount; // Счетчик ссылок
protected:
void* address; // Адрес указываемого объекта
size_t size; // Размер указываемого объекта в байтах
VoidPtr() : address(NULL), size(0), refcount(0) {}
VoidPtr(void* adr, size_t s) : address(adr), size(s), refcount(0) {}
public:
static VoidPtrPool* pool;
virtual ~VoidPtr() { size = 0; address = NULL; }
void* operator new(size_t)
{
if (pool == NULL)
pool = new VoidPtrPool;
return pool->Allocate();
}
void operator delete(void* space)
{ pool->Deallocate((VoidPtr*)space); }
void Grab() { refcount++; }
void Release()
{
if (refcount > 0) refcount--;
if (refcount <= 0) delete this;
}
};
Шаблон ведущего указателя
Наш ведущий указатель представляет собой шаблон, производный от VoidPtr. Он существует в основном для того, чтобы реализовать оператор -> и виртуальный деструктор, который знает, какой деструктор должен вызываться для указываемого объекта. Я решил запретить копирование и присваивание. При копировании дескриптора должен копироваться адрес ведущего указателя, а не сам ведущий указатель или указываемый объект. Следовательно, нет особой необходимости поддерживать копирование и присваивание для ведущих указателей. Как обычно, существует множество вариаций на тему конструкторов. В данном случае я выбрал ту, в которой конструктор ведущего указателя создает указываемый объект.
template <class Type>
class MP : public VoidPtr {
private: // Чтобы запретить копирование и присваивание
MP(const MP<Type>&) {}
MP<Type>& operator=(const MP<Type>&) { return this; }
public:
MP() : VoidPtr(new Type, sizeof(Type)) {}
virtual ~MP() { ((Type*)address)->Type::~TypeOf(); }
Type* operator->() { return (Type*)address; }
};
Шаблон дескриптора
Это уже знакомый нам шаблон дескриптора с подсчетом ссылок из предыдущей главы.
template <class Type>
class Handle {
private:
MP<Type>* pointer;
public:
Handle() : pointer(new MP<Type>) { pointer->Grab(); }
Handle(const Handle<Type>& h) : pointer(h.pointer)
{ pointer->Grab(); }
Handle<Type>& operator=(const Handle<Type>& h)
{
if (this == &h) return *this;
if (pointer == h.pointer) return *this;
pointer->Release();
h.pointer->Grab();
return *this;
}
MP<Type>& operator->() { return *pointer; }
};
В программе он используется для переменных, ссылающихся на объекты.
class Bar {
private:
H<Foo> foo;
public:
void f();
};
void Bar::f()
{
Handle<Foo> f; // Эквивалентно _____Foo* f = new Foo;
f = foo; // Использует operator=(Handle<Type>(foo));
foo = f; // Использует оператор H<Type>(f)
}
Пул ведущих указателей
Простоты ради мы предположим, что классы, производные от VoidPtr, совпадают по размеру с самим VoidPtr; иначе говоря, в них не добавляются новые переменные. Наша задача упрощается; VoidPtrPool теперь может быть простым связанным списком массивов VoidPtr. Структура массива называется VoidPtrBlock.
struct VoidPtrBlock {
VoidPtrBlock* next; // Следующий блок в списке
VoidPtr slots[BLOCKSIZE]; // Массив позиций
VoidPtrBlock(VoidPtrBlock* next_in_list) : next(next_in_list)
{
// Организовать новые позиции в связанный список
for (int i = 0; i < BLOCKSIZE - 1; i++)
slots[i].address = &slots[i + 1];
slots[BLOCKSIZE - 1].address = NULL;
}
~VoidPtrBlock() { delete next; }
}
class VoidPtrPool {
private:
VoidPtr* free_list; // Список свободных VoidPtr
VoidPtrBlock* block_size; // Начало списка блоков
public:
VoidPtrPool() : block_list(NULL), free_list(NULL) {}
~VoidPtrPool() { delete block_list; }
VoidPtr* Allocate();
void Deallocate(VoidPtr* vp);
};
VoidPtr* VoidPtrPool::Allocate()
{
if (free_list == NULL) // Выделить дополнительный блок
{
block_list = new VoidPtrBlock(block_list);
// Добавить в список
block_list->slots[BLOCKSIZE - 1].address = free_list;
free_list = &block_list->slots[0];
}
VoidPtr* space = (VoidPtr*)free_list;
free_list = (VoidPtr*)space->address;
return space;
}
void VoidPtrPool::Deallocate(VoidPtr* p)
{
vp->address = free_list;
free_list = (VoidPtr*)vp->address;
vp->size = 0;
}
В общем, ничего хитрого. При выделении нового блока мы организуем его позиции связанный список и водружаем поверх списка свободных указателей. Если список свободных указателей пуст, а нам потребовался еще один ведущий указатель, мы выделяем новый блок, а затем берем указатель из списка свободных, в котором к этому времени появились вакансии.
Итератор ведущих указателей
Для перебора всех ведущих указателей мы создадим класс итератора с именем VoidPtrIterator. VoidPtrPool возвращает итератор, перебирающий все активные указатели (то есть все указатели, не присутствующие в списке свободных). Он будет объявлен как чисто абстрактный базовый класс, поскольку в следующей главе тот же интерфейс будет использован для перебора указателей, внедренных в объекты.
class VoidPtrIterator {
protected:
VoidPtrIterator() {}
public:
virtual bool More() = 0;
virtual VoidPtr* Next() = 0;
};
Сам итератор работает весьма прямолинейно. Он просто перебирает блоки в цикле и ищет указатели с ненулевым значением переменной size.
class VoidPtrPoolIterator : public VoidPtrIterator {
private:
VoidPtrBlock* block;
int slot; // Номер позиции в текущем блоке
virtual void Advance() // Найти следующую используемую позицию
{
while (block != NULL)
{
if (slot >= BLOCKSIZE)
{
block = block->next;
slot = 0;
}
else if (block->slots[slot].size != 0)
break;
slot++;
}
}
public:
VoidPtrPoolIterator(VoidPtrBlock* vpb)
: block(vpb), slot(0), { Advance(); }
virtual bool More() { return block != NULL; }
virtual VoidPtr* Next()
{
VoidPtr* vp = &block->slots[slot];
Advance();
return vp;
}
};
Кроме того, мы добавим в VoidPtrPool следующую функцию:
VoidPtrIterator* iterator()
{ return new VoidPtrPoolIterator(this); }
Наконец, нам пришлось объявить VoidPtrPoolIterator другом VoidPtr, чтобы в программе можно
было обратиться к его переменной size. Забегая вперед, скажу, что в главе 16 мы воспользуемся этим итератором для других целей; поэтому функция Advance() и объявлена виртуальной, чтобы производные классы могли добавить свою собственную фильтрацию. Если найденная позиция имеет нулевое значение size, мы пропускаем ее. Во всем остальном работа сводится к простому перебору в массивах, образующих блоки указателей.