Списки свободных блоков

Упрощенный список свободных блоков, приведенный в предыдущей главе, может использоваться только для объектов постоянного размера. Например, он не будет нормально работать с производными классами, в которых добавляются новые переменные, поскольку они будут иметь другой размер. Сам список тоже ограничивался одним размером; для передачи оператору delete правильного размера требовались виртуальные деструкторы. Впрочем, создать более универсальные списки уже не так уж

трудно.

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

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

Более эффективное представление - коллекция списков свободной памяти, в которой каждый список представляет блоки определенного размера. Ниже показана упрощенная, но полезная реализация.

class MemManager {

private:

struct FreeList { // Список с блоками определенного размера

FreeList* next; // Следующий FreeList

void* top_of_list; // Верх текущего списка

size_t chunk_size; // Размер каждого свободного блока

FreeList(FreeList* successor, size_t size) : next(successor),

top_of_list(NULL), chunk_size(size) {}

};

FreeList* all_lists; // Список всех FreeList

public:

MemManager() : all_lists(NULL) {}

void* Allocate(size_t bytes);

void Deallocate(void* space, size_t bytes);

};

void* MemManager::Allocate(size_t bytes)

{

for (FreeList* fl = all_lists;

fl != NULL && fl->chunk_size != bytes;

fl = fl->next)

{

if (fl->top_of_list != NULL)

{

void* space = fl->top_of_list;

fl->top_of_list = *((void**)(fl->top_of_list));

return space;

}

return ::operator new(bytes); // Пустой список

}

return ::operator new(bytes); // Такого списка нет

}

void MemManager::Deallocate(void* space, size_t bytes)

{

FreeList* fl = NULL;

for (fl = all_lists; fl != NULL; fl = fl->next)

if (fl->chunk_size == bytes) break;

if (fl == NULL) // Списка для такого размера нет

{

fl = new FreeList(all_lists, bytes);

all_lists = fl;

}

*((void**)space) = fl->top_of_list;

fl->top_of_list = space;

}

Функции Allocate() и Deallocate() вызываются из перегруженных операторов new и delete

соответственно. Такой подход предельно упрощен, но работает он неплохо. Вы можете

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

1.Ограничить размеры блоков числами, кратными некоторому числу байт, степенями 2 или числами Фибоначчи.

2.Воспользоваться более эффективной структурой данных, чем связанный список списков - возможно, бинарным деревом или даже массивом, если диапазон размеров невелик.

3.Предоставить функцию Flush(), которая при нехватке памяти удаляет все содержимое

списков.

4.В функции Allocate() при отсутствии в списке свободного места заданного размера выделить память под массив блоков этого размера вместо одного блока.