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 \!\! P<G->S.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 пользователь может в любое время добавлять в свободный список статический или внешний массив.
185
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 (большая) и целой экспоненты с необязательным знаком. Как целая, так и дробная часть являются последовательностью цифр. Либо целая, либо дробная часть (но не обе) может отсутствовать; либо десятичная точка, либо е (маленькая) и экспонента (но не то и другое одновременно) может отсутствовать. Каждая плавающая константа считается имеющей двойную точность.