Списки свободных блоков
Упрощенный список свободных блоков, приведенный в предыдущей главе, может использоваться только для объектов постоянного размера. Например, он не будет нормально работать с производными классами, в которых добавляются новые переменные, поскольку они будут иметь другой размер. Сам список тоже ограничивался одним размером; для передачи оператору 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() при отсутствии в списке свободного места заданного размера выделить память под массив блоков этого размера вместо одного блока.