который будет выделен, содержит на одну единицу больше,
предназначаемую для самого заголовка, и это и есть значение,
которое записывается в поле SIZE заголовка. Указатель, возв-
ращаемый функцией ALLOC, указывает на свободное пространст-
во, а не на сам заголовок.
STATIC HEADER BASE; /*EMPTY LIST TO GET STARTED*/
STATIC HEADER *ALLOCP=NULL; /*LAST ALLOCATED BLOCK*/
CHAR *ALLOC(NBYTES)/*GENERAL-PURPOSE STORAGE ALLOCATOR*/
UNSIGNED NBYTES;
\(
HEADER *MORECORE();
REGISTER HEADER *P, *G;
REGISTER INT NUNITS;
NUNITS=1+(NBYTES+SIZEOF(HEADER)-1)/SIZEOF(HEADER);
IF ((G=ALLOCP)==NULL) \( /*NO FREE LIST YET*/
BASE.S PTR=ALLOCP=G=&BASE;
BASE.S.SIZE=0;
\)
FOR (P=G>S.PTR; ; G=P, P=P->S.PTR) \(
IF (P->S.SIZE>=NUNITS) \( /*BIG ENOUGH*/
IF (P->S.SIZE==NUNITS) /*EXACTLY*/
G->S.PTR=P->S.PTR;
ELSE \( /*ALLOCATE TAIL END*/
P->S.SIZE-=NUNITS;
P+=P->S.SIZE;
P->S.SIZE=NUNITS;
\)
ALLOCP=G;
RETURN((CHAR *)(P+1));
\)
IF(P==ALLOCP) /*WRAPPED AROUND FREE LIST*/
IF((P=MORECORE(NUNITS))==NULL)
RETURN(NULL); /*NONE LEFT*/
\)
\)
Переменная BASE используется для начала работы. Если
ALLOCP имеет значение NULL, как в случае первого обращения к
ALLOC, то создается вырожденный свободный список: он состоит
из свободного блока размера нуль и указателя на самого себя.
В любом случае затем исследуется свободный список. Поиск
свободного блока подходящего размера начинается с того места
(ALLOCP), где был найден последний блок; такая стратегия по-
могает сохранить однородность диска. Если найден слишком
большой блок, то пользователю предлагается его хвостовая
часть; это приводит к тому, что в заголовке исходного блока
нужно изменить только его размер. Во всех случаях возвращае-
мый пользователю указатель указывает на действительно сво-
бодную область, лежащую на единицу дальше заголовка. Обрати-
те внимание на то, что функция ALLOC перед возвращением "P"
преобразует его в указатель на символы.
Функция MORECORE получает память от операционной систе-
мы. Детали того, как это осуществляется, меняются, конечно,
от системы к системе. На системе UNIX точка входа SBRK(N)
возвращает указатель на "N" дополнительных байтов памя-
ти.(указатель удволетворяет всем ограничениям на выравнива-
ние). Так как запрос к системе на выделение памяти является
сравнительно дорогой операцией, мы не хотим делать это при
каждом обращении к функции ALLOC. Поэтому функция MORECORE
округляет затребованное число единиц до большего значения;
этот больший блок будет затем разделен так, как необходимо.
Масштабирующая величина является параметром, который может
быть подобран в соответствии с необходимостью.
#DEFINE NALLOC 128 /*#UNITS TO ALLOCATE AT ONCE*/
STATIC HEADER *MORECORE(NU) /*ASK SYSTEM FOR MEMORY*/
UNSIGNED NU;
\(
CHAR *SBRK();
REGISTER CHAR *CP;
REGISTER HEADER *UP;
REGISTER INT RNU;
RNU=NALLOC*((NU+NALLOC-1)/NALLOC);
CP=SBRK(RNU*SIZEOF(HEADER));
IF ((INT)CP==-1) /*NO SPACE AT ALL*/
RETURN(NULL);
UP=(HEADER *)CP;
UP->S.SIZE=RNU;
FREE((CHAR *)(UP+1));
RETURN(ALLOCP);
\)
Если больше не осталось свободного пространства, то фун-
кция SBRK возвращает "-1", хотя NULL был бы лучшим выбором.
Для надежности сравнения "-1" должна быть преобразована к
типу INT. Снова приходится многократно использовать явные
преобразования (перевод) типов, чтобы обеспечить определен-
ную независимость функций от деталей представления указате-
лей на различных машинах.
И последнее - сама функция FREE. Начиная с ALLOCP, она
просто просматривает свободный список в поиске места для
введения свободного блока. Это место находится либо между
двумя существующими блоками, либо в одном из концов списка.
В любом случае, если освободившийся блок примыкает к одному
из соседних, смежные блоки объединяются. Следить нужно толь-
ко затем, чтобы указатели указывали на то, что нужно, и что-
бы размеры были установлены правильно.
FREE(AP) /*PUT BLOCKE AP IN FREE LIST*/
CHAR *AP;
\(
REGISTER HEADER *P, *G;
P=(HEADER*)AP-1; /*POINT TO HEADER*/
FOR (G=ALLOCP; !(P>G && P>G->S.PTR);G=G->S.PTR)
IF (G>=G->S.PTR && (P>G \!\! PS.PTR))
BREAK; /*AT ONE END OR OTHER*/
IF (P+P->S.SIZE==G->S.PTR)\(/*JOIN TO UPPER NBR*/
P->S.SIZE += G->S.PTR->S.SIZE;
P->S.PTR = G->S.PTR->S.PTR;
\) ELSE
P->S.PTR = G->S.PTR;
IF (G+G->S.SIZE==P) \( /*JOIN TO LOWER NBR*/
G->S.SIZE+=P->S.SIZE;
G->S.PTR=P->S.PTR;
\) ELSE
G->S.PTR=P;
ALLOCP = G;
\)
Хотя распределение памяти по своей сути зависит от ис-
пользуемой машины, приведенная выше программа показывает,
как эту зависимость можно регулировать и ограничить весьма
небольшой частью программы. Использование TYPEDEF и UNION
позволяет справиться с выравниванием (при условии, что функ-
ция SBRK обеспечивает подходящий указатель). Переводы типов
организуют выполнение явного преобразования типов и даже
справляются с неудачно разработанным системным интерфейсом.
И хотя рассмотренные здесь подробности связаны с распределе-
нием памяти, общий подход равным образом применим и к другим
ситуациям.
Упражнение 8-6
--------------
Функция из стандартной библиотеки CALLOC(N,SIZE) возвра-
щает указатель на "N" объектов размера SIZE, причем соответ-
ствующая память инициализируется на нуль. напишите программу
для CALLOC, используя функцию ALLOC либо в качестве образца,
либо как функцию, к которой происходит обращение.
Упражнение 8-7
---------------
Функция ALLOC принимает затребованный размер, не прове-
ряя его правдоподобности; функция FREE полагает, что тот
блок, который она должна освободить, содержит правильное
значение в поле размера. Усовершенствуйте эти процедуры,
затратив больше усилий на проверку ошибок.
Упражнение 8-8
---------------
Напишите функцию BFREE(P,N), которая включает произволь-
ный блок "P" из "N" символов в список свободных блоков, уп-
равляемый функциями ALLOC и FREE. С помощью функции BFREE
пользователь может в любое время добавлять в свободный спи-
сок статический или внешний массив.
* 9. Приложение А: справочное руководство по языку 'C' *
9.1. Введение
Это руководство описывает язык 'с' для компьютеров DEC
PDP-11, HONEYWELL 6000, IBM система/370 и INTERDATA 8/32.
там, где есть расхождения, мы сосредотачиваемся на версии
для PDP-11, стремясь в то же время указать детали, которые
зависят от реализации. За малым исключением, эти расхождения
непосредственно обусловлены основными свойствами используе-
мого аппаратного оборудования; различные компиляторы обычно
вполне совместимы.
10. Лексические соглашения
Имеется шесть классов лексем: идентификаторы, ключевые
слова, константы, строки, операции и другие разделители.
Пробелы, табуляции , новые строки и комментарии (совместно,
"пустые промежутки"), как описано ниже, игнорируются, за ис-
ключением тех случаев, когда они служат разделителями лек-
сем. Необходим какой-то пустой промежуток для разделения
идентификаторов, ключевых слов и констант, которые в против-
ном случае сольются.
Если сделан разбор входного потока на лексемы вплоть до
данного символа, то в качестве следующей лексемы берется са-
мая длинная строка символов, которая еще может представлять
собой лексему.
10.1. Комментарии
Комментарий открывается символами /* и заканчивается
символами /*. Комментарии не вкладываются друг в друга.
10.2. Идентификаторы (имена)
Идентификатор - это последовательность букв и цифр; пер-
вый символ должен быть буквой. Подчеркивание _ считается
буквой. Буквы нижнего и верхнего регистров различаются. зна-
чащими являются не более, чем первые восемь символов, хотя
можно использовать и больше. На внешние идентификаторы, ко-
торые используются различными ассемблерами и загрузчиками,
накладыватся более жесткие ограничения:
DEC PDP-11 7 символов, 2 регистра
HONEYWELL 6000 6 символов, 1 регистр
IBM 360/370 7 символов, 1 регистр
INTERDATA 8/32 8 символов, 2 регистра
10.3. Ключевые слова
Следующие идентификаторы зарезервированы для использова-
ния в качестве ключевых слов и не могут использоваться иным
образом:
INT EXTERN ELSE
CHAR REGISTER FOR
FLOAT TYPEDEF DO
DOUBLE STATIC WHILE
STRUCT GOTO SWITCH
UNION RETURN CASE
LONG SIZEOF DEFAULT
SHORT BREAK ENTRY
UNSIGNED CONTINUE
*AUTO IF
Ключевое слово ENTRY в настоящее время не используется ка-
ким-либо компилятором; оно зарезервировано для использования
в будущем. В некоторых реализациях резервируется также слова
FORTRAN и ASM
10.4. Константы
Имеется несколько видов констант, которые перечислены ниже.
В пункте 10.6 резюмируются характеристики аппаратных сред-
ств, которые влияют на размеры.
10.4.1. Целые константы
Целая константа, состоящая из последовательности цифр,
считается восьмеричной, если она начинается с 0 (цифра
нуль), и десятичной в противном случае. Цифры 8 и 9 имеют
восьмеричные значения 10 и 11 соответственно. Последователь-
ность цифр, которой предшествуют символы 0х (нуль, х-малень-
кое) или 0х (нуль х-большое), рассматривается как шестнадца-
тиричное целое. Шестнадцатиричные цифры включают буквы от а
(маленькое) или а (большое) до F (маленькое) или F (большое)
со значениями от 10 до 15. Десятичная константа, величина
которой превышает наибольшее машинное целое со знаком, счи-
тается длинной; восмеричная или шестнадцатиричная константа,
которое превышает наибольшее машинное целое без знака, также
считается длинной.
10.4.2. Явные длинные константы
Десятичная, восмеричная или шестнадцатиричная константа,
за которой непосредственно следует L (эль-маленькое) или L
(эль-большое), является длинной константой. Как обсуждается
ниже, на некоторых машинах целые и длинные значения могут
рассматриваться как идентичные.
10.4.3. Символьные константы
Символьная константа - это символ, заключенный в одиноч-
ные кавычки, как, например, 'X'. Значением символьной конс-
танты является численное значение этого символа в машинном
представлении набора символов.
Некоторые неграфические символы, одиночная кавычка ' и
обратная косая черта \ могут быть представлены в соответст-
вии со следующей таблицей условных последовательностей:
новая строка NL/LF/ \N
горизонтальная табуляция HT \T
символ возврата на одну позицию BS \B
возврат каретки CR \R
переход на новую страницу FF \F
обратная косая черта \ \\
одиночная кавычка ' \'
комбинация битов DDD \DDD
Условная последовательность \DDD состоит из обратной ко-
сой черты, за которой следуют 1,2 или 3 восмеричных цифры,
которые рассмативаются как задающие значение желаемого сим-
вола. Специальным случаем этой конструкции является последо-
вательность \0 (за нулем не следует цифра), которая опреде-
ляет символ NUL. если следующий за обратной косой чертой
символ не совпадает с одним из указанных, то обратная косая
черта игнорируется.
10.4.4. Плавающие константы
Плавающая константа состоит из целой части, десятичной
точки, дробной части, буквы E (маленькая) или E (большая) и
целой экспоненты с необязательным знаком. Как целая, так и
дробная часть являются последовательностью цифр. Либо целая,
либо дробная часть (но не обе) может отсутствовать; либо де-
сятичная точка, либо е (маленькая) и экспонента (но не то и
другое одновременно) может отсутствовать. Каждая плавающая
константа считается имеющей двойную точность.
10.5. Строки
Строка - это последовательность символов, заключенная в
