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

    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) { /* слить с верхним */

  bp-›s.size += p-›s.ptr-›s.size; /* соседом */

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

 } else bp-›s.ptr = p-›s.ptr;

 if (p + p-›s.size == bp) { /* слить с нижним соседом */

  p-›s.size += bp-›s.size;

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

 } else p-›s.ptr = bp;

 freep = p;

}

Хотя выделение памяти по своей сути - машинно-зависимая проблема, с ней можно справиться, что и иллюстрирует приведенная программа, в которой машинная зависимость упрятана в очень маленькой ее части. Что касается проблемы выравнивания, то мы разрешили ее с помощью typedef и union (предполагается, что sbrk дает подходящий в смысле выравнивания указатель). Операции приведения типов позволяют нам сделать явными преобразования типов и даже справиться с плохо спроектированным интерфейсом системы. Несмотря на то, что наши рассуждения касались распределения памяти, этот общий подход применим и в других ситуациях.