Брайан Керниган - Язык программирования Си. Издание 3-е, исправленное

Процедура освобождения сопряжена с прохождением по списку свободных блоков, поскольку нужно найти подходящее место для освобождаемого блока. Если подлежащий освобождению блок примыкает с какой-то стороны к одному из свободных блоков, то он объединяется с ним в один блок большего размера, чтобы по возможности уменьшить раздробленность (фрагментацию) памяти. Выполнение проверки, примыкают ли блоки друг к другу, не составляет труда, поскольку список свободных блоков всегда упорядочен по возрастанию адресов.

Существует проблема, о которой мы уже упоминали в главе 5, состоящая в том, что память, выдаваемая функцией malloc , должна быть соответствующим образом выровнена с учетом объектов, которые будут в ней храниться. Хотя машины и отличаются друг от друга, но для каждой из них существует тип, предъявляющий самые большие требования на выравнивание, и, если по некоему адресу допускается размещение объекта этого типа, то по нему можно разместить и объекты всех других типов. На некоторых машинах таким самым "требовательным" типом является double , на других это может быть int или long .

Свободный блок содержит указатель на следующий блок в списке, свой размер и собственно свободное пространство. Указатель и размер представляют собой управляющую информацию и образуют так называемый "заголовок". Чтобы упростить выравнивание, все блоки создаются кратными размеру заголовка, а заголовок соответствующим образом выравнивается. Этого можно достичь, сконструировав объединение, которое будет содержать соответствующую заголовку структуру и самый требовательный в отношении выравнивания тип. Для конкретности мы выбрали тип long .

typedef long Align; /* для выравнивания по границе long */

union header { /* заголовок блока: */

struct {

union header *ptr; /* след. блок в списке свободных */

unsigned size; /* размер этого блока */

} s;

Align x; /* принудительное выравнивание блока */

};

typedef union header Header;

Поле Align нигде не используется: оно необходимо только для того, чтобы каждый заголовок был выровнен по самому "худшему" варианту границы.

Затребованное число символов округляется в malloc до целого числа единиц памяти размером в заголовок (именно это число и записывается в поле size (размер) в заголовке); кроме того, в блок входит еще одна единица памяти - сам заголовок. Указатель, возвращаемый функцией malloc , указывает на свободное пространство, а не на заголовок. Со свободным пространством пользователь может делать что угодно, но, если он будет писать что-либо за его пределами, то, вероятно, список разрушится.

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

Для организации начала работы используется переменная base . Если freep есть NULL (как это бывает при первом обращении к malloc ), создается "вырожденный" список свободного пространства; он содержит один блок нулевого размера с указателем на самого себя. Поиск свободного блока подходящего размера начинается с этого указателя ( freep ), т. е. с последнего найденного блока; такая стратегия помогает поддерживать список однородным. Если найденный блок окажется слишком большим, пользователю будет отдана его хвостовая часть; при этом потребуется только уточнить его размер в заголовке найденного свободного блока. В любом случае возвращаемый пользователю указатель является адресом свободного пространства, размещающегося в блоке непосредственно за заголовком.

static Header base; /* пустой список для нач. запуска */

static Header *freep = NULL; /* начало в списке своб. блоков */

/* malloc: универсальный распределитель памяти */

void *malloc(unsigned nbytes) {

Header *p, *prevp;

Header *morecore(unsigned);

unsigned nunits;

nunits = (nbytes + sizeof(Header) - 1) / sizeof (Header) + 1;

if ((prevp = freep) == NULL) { /* списка своб. памяти еще нет */

base.s.ptr = freep = prevp = &base;

base.s.size = 0;

}

for (p = prevp-›s.ptr; ; prevp = p, p = p-›s.ptr) {

if (p-›s.size ›= nunits) { /* достаточно большой */

if (p-›s.size == nunits) /* точно нужного размера */

prevp-›s.ptr = p-›s.ptr;

else { /* отрезаем хвостовую часть */

p-›s.size -= nunits;

p += p-›s.size;

p-›s.size = nunits;