C++: библиотека программиста

 
209 
Одно из несложных усовершенствований заключается в том, чтобы хранить в каждом узле списка не 
только адрес следующего указателя в списке, но и размер блока. Это позволит хранить в одном списке 
блоки разных размеров. При выделении памяти мы просматриваем список, пока не находим блок, 
размеры которого достаточны для наших целей. Для этого придется хранить скрытую информацию о 
размере блока даже после его выделения, чтобы при уничтожении объекта восстанавливать весь блок. 
Стратегия, прямо скажем, тупая и подходит разве что для очень маленьких списков, поскольку время 
поиска возрастает линейно с размером списка. Впрочем, она послужит отправной точкой для нашего 
обсуждения. 
Более эффективное представление — коллекция списков свободной памяти, в которой каждый список 
представляет блоки определенного размера. Ниже показана урощенная, но полезная реализация. 
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; 

---

 210 
} 
*((void**)space) = fl->top_of_list; 
fl->top_of_list 
= 
space; 
} 
Функции 
Allocate()
и 
Deallocate()
вызываются из перегруженных операторов 
new
и 
delete
соответственно. Такой подход предельно упрощен, но работает он неплохо. Вы можете 
воспользоваться им для любого сочетания классов, и он будет работать с производными классами, в 
которых добавились новые переменные. Он также может использоваться в схеме управления памятью 
на базе ведущих указателей. Существуют многочисленные усовершенствования, которые можно 
внести в показанную основу: 
• 
Ограничить размеры блоков числами, кратными некоторому числу байт, степенями 2 или 
числами Фибоначчи. 
• 
Воспользоваться более эффективной структурой данных, чем связанный список списков — 
возможно, бинарным деревом или даже массивом, если диапазон размеров невелик. 
• 
Предоставить функцию 
Flush()
, которая при нехватке памяти удаляет все содержимое 
списков. 
• 
В функции 
Allocate()
при отсутствии в списке свободного места заданного размера выделить 
память под массив блоков этого размера вместо одного блока. 
Подсчет ссылок 
Подсчет ссылок основан на простой идее — мы следим за количеством указателей, ссылающихся на 
объект. Когда счетчик становится равным 0, объект удаляется. Звучит просто, не правда ли? В 
определенных условиях все действительно просто, но подсчет ссылок обладает довольно жесткими 
ограничениями, которые снижают его практическую ценность. 
Базовый класс с подсчетом ссылок 
Начнем с абстрактного базового класса, от которого можно создать производный класс с подсчетом 
ссылок. Базовый класс содержит переменную, в которой хранится количество вызовов функции 
Grab()
за вычетом количества вызовов функции 
Release()
. 
class RefCount { 
private: 
unsigned long count; 
// Счетчик ссылок 
public: 
RefCount() : count(0) {} 
RefCount(const RefCount&) : count(0) {} 
RefCount& 
operator=(const 
RefCount&) 
{ return *this; } // Не изменяет счетчик 
virtual 
~RefCount() 
{} 
// 
Заготовка 
void Grab() { count++; } 
void 
Release() 
{ 
if (count > 0) count --; 
if (count == 0) delete this; 
} 
}; 
Пока клиентский код правильно вызывает функции 
Grab()
и 
Release()
, все работает абсолютно 
надежно. Каждый раз, когда клиент получает или копирует адрес объекта, производного от 
RefCount
, 
он вызывает 
Grab()
. Когда клиент гарантирует, что адрес больше не используется, он вызывает 
Release()
. Если счетчик падает до 0 — бац! Нет больше объекта! 

---