Реферат: Язык С 
Одна из проблем, о которой мы
упоминали в главе 5, зак-
лючается в обеспечении того, чтобы
возвращаемая функцией
ALLOC память была выровнена
подходящим образом для тех
объектов, которые будут в ней
храниться. Хотя машины и раз-
личаются, для каждой машины
существует тип, требующий наи-
больших ограничений по размещению
памяти, если данные самого
ограничительного типа можно
поместить в некоторый определен-
ный адрес, то это же возможно и для
всех остальных типов.
Например, на IBM 360/370,HONEYWELL
6000 и многих других ма-
шинах любой объект может храниться
в границах, соответствую-
щим переменным типа DOUBLE; на
PDP-11 будут достаточны пере-
менные типа INT.
Свободный блок содержит указатель
следующего блока в це-
почке, запись о размере блока и
само свободное пространство;
управляющая информация в начале
называется заголовком. Для
упрощения выравнивания все блоки
кратны размеру заголовка, а
сам заголовок выровнен надлежащим
образом. Это достигается с
помощью объединения, которое
содержит желаемую структуру за-
головка и образец наиболее
ограничительного по выравниванию
типа:
TYPEDEF INT ALIGN; /*FORCES
ALIGNMENT ON PDP-11*/
UNION HEADER \( /*FREE BLOCK
HEADER*/
STRUCT \(
UNION HEADER *PTR; /*NEXT FREE
BLOCK*/
UNSIGNED SIZE; /*SIZE OF THIS FREE
BLOCK*/
\) S;
ALIGN X; /*FORCE ALIGNMENT OF
BLOCKS*/
\);
TYPEDEF UNION HEADER HEADER;
Функция ALLOC округляет
требуемый размер в символах до
нужного числа единиц размера
заголовка; фактический блок,
который будет выделен, содержит на
одну единицу больше,
предназначаемую для самого
заголовка, и это и есть значение,
которое записывается в поле 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;
\)
·
182 -
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
округляет затребованное число
единиц до большего значения;
этот больший блок будет затем
разделен так, как необходимо.
Масштабирующая величина является
параметром, который может
быть подобран в соответствии с
необходимостью.
·
183 -
#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;
\)
·
184 -
Хотя распределение памяти по
своей сути зависит от ис-
пользуемой машины, приведенная выше
программа показывает,
как эту зависимость можно
регулировать и ограничить весьма
небольшой частью программы. Использование
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 регистра
·
186 -
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'.
Значением символьной конс-
танты является численное значение
этого символа в машинном
представлении набора символов.
·
187 -
Некоторые неграфические
символы, одиночная кавычка ' и
обратная косая черта \ могут
быть представлены в соответст-
вии со следующей таблицей
условных последовательностей:
новая
строка 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. Строки
Строка - это
последовательность символов, заключенная в
двойные кавычки, как,
наприимер,”...”. Строка имеет тип
“массив массивов” и класс памяти
STATIC (см. Пункт 4 ниже).
Строка инициализирована указанными
в ней символами. Все
строки, даже идентично записанные,
считаются различными.
Компилятор помещает в конец каждой
строки нулевой байт \0, с
тем чтобы просматривающая строку
программа могла определить
ее конец. Перед стоящим внутри
строки символом двойной ка-
вычки “ должен быть поставлен
символ обратной косой черты \;
кроме того, могут использоваться те
же условия последова-
тельности, что и в символьных
константах. И последнее, об-
ратная косая черта \, за которой
непосредственно следует
символ новой строки, игнорируется.
·
188 -
10.6. Характеристики аппаратных
средств
Следующая ниже таблица
суммирует некоторые свойства ап-
паратного оборудования, которые
меняются от машины к машине.
Хотя они и влияют на переносимость
программ, на практике они
представляют маленькую проблему,
чем это может казаться за-
ранее.
Таблица 1
DEC
PDP-11 HONEYWELL IBM 370 INTERDATA 8/32
ASCII ASCII EBCDIC ASCII
CHAR 8
BITS 9 BITS 8 BITS 8 BITS
INT
16 36 32 32
SHORT
16 36 16 16
LONG
32 36 32 32
FLOAT
32 36 32 32
DOUBLE
64 72 64 64
RANGE -38/+38 -38/+38 -76/+76 -76/+76
11. Синтаксическая нотация
В используемой в этом руководстве
синтаксической нотации
синтаксические категории выделяются
курсивом (прим. перев.:
в настоящее время синтексические
категории вместо курсивом
выделяются подчеркиванием), а
литерные слова и символы -
жирным шрифтом. Альтернативные
категории перечисляются на
отдельных строчках. Необязательный
символ, терминальный или
нетерминальный, указывается
индексом “необ”, так что
\( выражение
--------- необ \)
указывает на необязательное
выражение, заключенное в фигур-
ных скобках. Синтаксис суммируется
в пункте 18.
12. Что в имене тебе моем?
Язык “C” основывает
интерпретацию идентификатора на двух
признаках идентификатора: его
классе памяти и его типе.
Класс памяти определяет место и
время хранения памяти, свя-
занной с идентификатором; тип
определяет смысл величин, на-
ходящихся в памяти, определенной
под идентификатором.
Имеются четыре класса памяти:
автоматическая, статичес-
кая, внешняя и регистровая.
Автоматические переменные явля-
ются локальными для каждого вызова
блока и исчезают при вы-
ходе из этого блока. Статические
переменные являются локаль-
ными, но сохраняют свои значения
для следующего входа в блок
даже после того, как управление
передается за пределы блока.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28
|
