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

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

}