Поле 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;
}
