Выбрать главу

В заключение рассмотрим функцию 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 дает подходящий в смысле выравнивания указатель). Операции приведения типов позволяют нам сделать явными преобразования типов и даже справиться с плохо спроектированным интерфейсом системы. Несмотря на то, что наши рассуждения касались распределения памяти, этот общий подход применим и в других ситуациях.

Упражнение 8.6. Стандартная функция calloc(n, size) возвращает указатель на n элементов памяти размера size, заполненных нулями. Напишите свой вариант calloc, пользуясь функцией malloc или модифицируя последнюю.

Упражнение 8.7. Функция malloc допускает любой размер, никак не проверяя его на правдоподобие: free предполагает, что размер освобождаемого блока - правильный. Усовершенствуйте эти программы таким образом, чтобы они более тщательно контролировали ошибки.

Упражнение 8.8. Напишите программу bfree(p, n), освобождающую произвольный блок p, состоящий из n символов, путем включения его в список свободной памяти, поддерживаемый функциями malloc и free. C помощью bfree пользователь должен иметь возможность в любое время добавить в список свободной памяти статический или внешний массив.

Приложение A. Справочное руководство

A1. Введение

Данное руководство описывает язык программирования Си, определенный 31 октября 1989 г. в соответствии с проектом, утвержденным в ANSI в качестве Американского национального стандарта для информационных систем: Язык программирования Си, X3.159-1989 ("American National Standard for Information Systems - Programming Language C, X3.159-1989"). Это описание - лишь один из вариантов предлагаемого стандарта, а не сам стандарт, однако мы специально заботились о том, чтобы сделать его надежным руководством по языку.

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

Далее примечания (как и это) набираются с отступом от левого края страницы. В основном эти примечания касаются отличий стандарта от версии языка, описанной в первом издании этой книги, и от последующих нововведений в различных компиляторах.

A2. Соглашения о лексике

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

A2.1. Лексемы (tokens) 

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

Если входной поток уже до некоторого символа разбит на лексемы, то следующей лексемой будет самая длинная строка, которая может быть лексемой.

A2.2. Комментарий

Символы /* открывают комментарий, а символы */ закрывают его. Комментарии нельзя вкладывать друг в друга, их нельзя помещать внутрь строк или текстовых литералов.

A2.3. Идентификаторы

Идентификатор - это последовательность букв и цифр. Первым символом должна быть буква; знак подчеркивания _ считается буквой. Буквы нижнего и верхнего регистров различаются. Идентификаторы могут иметь любую длину; для внутренних идентификаторов значимыми являются первые 31 символ; в некоторых реализациях принято большее число значимых символов. К внутренним идентификаторам относятся имена макросов и все другие имена, не имеющие внешних связей (A11.2). На идентификаторы с внешними связями могут накладываться большие ограничения: иногда воспринимаются не более шести первых символов и могут не различаться буквы верхнего и нижнего регистров.

A2.4. Ключевые слова

Следующие идентификаторы зарезервированы в качестве ключевых слов и в другом смысле использоваться не могут:

auto

break

char

case

char

const

continue

default

do

double

else