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

Ритчи Деннис М.

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;

}

freep = prevp;

return (void *)(p+1);

}

if (p == freep) /* прошли полный цикл по списку */

if ((p = morecore(nunits)) == NULL) return NULL; /*

больше памяти нет */

 }

}

Функция morecore получает память от операционной системы. Детали того, как это делается, могут не совпадать в различных системах. Так как запрос памяти у системы - сравнительно дорогая операция, мы бы не хотели для этого каждый раз обращаться к malloc. Поэтому используется функция morecore, которая запрашивает не менее NALLOC единиц памяти; этот больший кусок памяти будет "нарезаться" потом по мере надобности. После установки в поле размера соответствующего значения функция morecore вызывает функцию free и тем самым включает полученный кусок в список свободных областей памяти.

#define NALLOC 1024 /* миним. число единиц памяти для запроса */

/* morecore: запрашивает у системы дополнительную память */

static Header * morecore(unsigned nu)

{

 char *cp, *sbrk(int);

 Header *up;

 if (nu < NALLOC)

nu = NALLOC;

 cp = sbrk(nu * sizeof(Header));

 if (cp == (char *) -1) /* больше памяти нет. */

return NULL;

 up = (Header *) cp;

 up->s.size = nu;

 free((void *)(up+1));

 return freep;

}

Системный вызов sbrk(n) в UNIXе возвращает указатель на n байт памяти или -1, если требуемого пространства не оказалось, хотя было бы лучше, если бы в последнем случае он возвращал NULL. Константу -1 необходимо привести к типу char *, чтобы ее можно было сравнить с возвращаемым значением. Это еще один пример того, как операция приведения типа делает функцию относительно независимой от конкретного представления указателей на различных машинах. Есть, однако, одна "некорректность", состоящая а том, что сравниваются указатели на различные блоки, выдаваемые функцией sbrk. Такое сравнение не гарантировано стандартом, который позволяет сравнивать указатели лишь в пределах одного и того же массива. Таким образом, эта версия malloc верна только на тех машинах, в которых допускается сравнение любых указателей.

В заключение рассмотрим функцию free. Она просматривает список свободной памяти, начиная с freep, чтобы подыскать место для вставляемого блока. Искомое место может оказаться или между блоками, или в начале списка, или в его конце. В любом случае, если подлежащий освобождению блок примыкает к соседнему блоку, он объединяется с ним в один блок. О чем еще осталось позаботиться, - так это о том, чтобы указатели указывали в нужные места и размеры блоков были правильными.

/* free: включает блок в список свободной памяти */

void free(void *ар) {

 Header *bp, *p;

 bp = (Header *)ap -1; /* указатель на заголовок блока */

 for (p = freep; !(bp › p && bp s.ptr); p = p-›s.ptr)

if (p ›= p-›s.ptr && (bp › p || bp s.ptr)) break; /* освобождаем блок в начале или в конце */

 if (bp + bp-›s.size - p-›s.ptr) { /* слить с верхним */