pData

firstAvailableBlock :0

biocksAvailable :255

Рис. 4.4. Объект класса Chunk, состоящий из 255 блоков по 4 блока каждый

Посмотрим теперь, почему количество блоков ограничено величиной, соответствующей максимальному значению переменной типа unsigned char. Допустим, что мы используем переменную более широкого типа, например unsigned short, которая на многих компьютерах занимает 2 байт. В этом случае перед нами возникают две проблемы - большая и маленькая.

• Мы не можем размешать блоки, размер которых меньше величины sizeof(unsigned short), что очень неудобно, поскольку мы разрабатываем механизм распределения памяти для небольших объектов. Это маленькая проблема.

• Мы сталкиваемся с вопросами выравнивания участков памяти. Вообразите, что мы создали механизм распределения для 5-байтовых блоков. В этом случае приведение указателя, ссылаюшегося на 5-байтовый блок, к типу unsigned int приведет к непредсказуемым последствиям. Это большая проблема.

Решить эти проблемы довольно просто - нужно использовать тип unsigned char в качестве типа для "тайного индекса" ("sleallh index"). Символьный тип по определению имеет размер, равный 1 байт, поэтому никаких проблем, связанных с выравниванием участков памяти не возникает, поскольку даже указатель на отдельную ячейку памяти ссылается на переменную типа unsigned char.

Это приводит к ограничению максимального количества блоков в объекте класса Chunk, поскольку в нем не может бьггь больше, чем uncharjmax блоков (в большинстве систем эта величина равна 255). Это вполне приемлемо, даже если размер блока действительно мал, например, от 1 до 4 байт. Это относится и к более крупным блокам, поскольку в любом случае объекты класса Chunk по определению должны бьггь маленькими.

Функция распределения памяти извлекает блок, на который ссылается переменная fi rstAvai1ab1eBlock , и устанавливает ее на следуюший свободный блок- типичная операция над списками.

void* Chunk:lAllocateCstd::size t blocksize) {

if C!b1ocksAvai1able ) return 0; unsigned char* pResult =

pData + (firstAvailableBlock * blocksize); присвоение переменной firstAvai1ableBlock указателя на следующий свободный блок firstAvailableBlock = *pResult; --b1ocksAvai1able ;

return pResult;

Итак, функция chunk::Allocate состоит из одной операции сравнения, одной операции доступа по индексу, двух операций вычитания, присваивания и оператора декрементации - вполне приемлемо. Еще более важно то, что в этой функции не выполняется операция поиска. На рис. 4.5 показано состояние объекта класса Chunk после выполнения первой операции распределения памяти.

pData

firstAvailableBlock :0

blocksAvailable :254.

Рис. 4.5. Состояние объекта класса Chunk после выполнения первой операции распределения памяти. Занятая память выделена серым цветом

Функция освобождения памяти работает в точности наоборот. Она возвращает блок в список свободных блоков и увеличивает значение переменной Ы ocksAvai 1-аЫе . Не забудьте о необходимости передавать размер блока в качестве параметра функции Deallocate, поскольку объекту класса Chunk он неизвестен.

void chunk::Deallocate(void* р, std::si2e t blocksize) {

assertCp >= pData );

unsigned char* toRelease = static cast<unsigned char*>(p); проверка выравнивания

assertCCtoRelease - pDatO % blocksize == 0);

*toRelease = firstAvai 1 ablев1оск ;

firstAvai1ablев1оск = static cast<unsigned char>C

(toRelease - pData ) / blocksize); проверка усечения assertCfirstAvai1ablев1оск ==

(toRelease - pData ) / blocksize); ++blocksAvai1abl e ;

Функция освобождения памяти небогата содержанием, однако в ней содержится довольно много диагностических высказываний (которые по-прежнему не перехватывают все ошибочные ситуации). Структура Chunk вполне соответствует традиционным механизмам распределения памяти, принятым в языках С и С++. Если вы передадите функции Chunk: : Deal locate неверный указатель, приготовьтесь к худшему.

4.5. Класс FixedAllocator

На следующем уровне механизма распределения памяти для небольших объектов находится класс FixedAllocator. Этот класс предназначен для распределения памяти

при работе с блоками фиксированного размера, причем этот размер не обязан соответствовать размеру порции.

Для этого объект класса FixedAllocator образует вектор объектов типа Chunk. При поступлении запроса на распределение памяти объект класса FixedAllocator отыскивает подходящий объект класса Chunk. Если все порции заняты, объект класса FixedAllocator создает новый объект класса Chunk. Вот как выглядит эта часть определения класса.

class FixedAllocator {

private:

std::size t blocksize ;

unsigned char numBlocks ;

typedef std::vector<chunk> Chunks;

Chunks chunks ;

Chunk* allocChunk ;

Chunk* deallocChunk ;

Чтобы ускорить работу, класс FixedAllocator не перебирает элементы вектора chunks в поисках подходящего участка памяти при каждом запросе. Вместо этого в объекте хранится указатель на последний объект класса Chunk, который использовался при распределении памяти (переменная al locChunk ). При поступлении нового запроса функция FixedAllocate сначала проверяет, достаточно ли памяти в порции, на которую ссылается указатель allocChunk . Если этот объект удовлетворяет требованиям запроса, то используется именно он. Если нет, выполняется линейный поиск (и, возможно, в вектор chunks записывается новый объект класса Chunk). В любом случае указатель allocChunk устанавливается на найденный или вновь созданный объект класса Chunk. Такой подход повышает вероятность того, что в следующий раз распределение памяти будет выполнено быстро. Вот как выглядит код этого алгоритма.

void* FixedAllocator::Allocate() {

if (allocChunk == 0

allocChunk ->bl ocksAvai 1аЫе == 0)

в данном объекте памяти недостаточно.

попробуйте найти другой.

Chunks::iterator i = chunks .beginC);

for (;; +=i)

if (i == chunks .endO) {

Bee объекты заполнены - добавляем новый. chunks . reserve(chunks .sizeO+l); Chunk newChunk;

newChunk.lnit(blocksize , numBlocks ); chunks .push back(newChunk); allocChunk = &chunks .backQ ; deallocChunk = &chunks .backQ ; break;

if (i->blocksAvailable > 0) {

Объект найден allocChunk = &*i;