Язык С
#DEFINE S_IEXEC 0100 /* EXECUTE PERMISSION */
Теперь мы в состоянии написать программу FSIZE. Если по-
лученный от функции STAT режим указывает, что файл не явля-
ется справочником, то его размер уже под рукой и может быть
напечатан непосредственно. Если же он оказывается справочни-
ком, то мы должны обрабатывать этот справочник отдельно для
каждого файла; так как справочник может в свою очередь со-
держать подсправочники, этот процесс обработки является ре-
курсивным.
Как обычно, ведущая программа главным образом имеет дело
с командной строкой аргументов; она передает каждый аргумент
функции FSIZE в большой буфер.
#INCLUDE
#INCLUDE
#INCLUDE
#INCLUDE
#DEFINE BUFSIZE 256
MAIN(ARGC,ARGV) /*FSIZE:PRINT FILE SIZES*/
CHAR *ARGV[];
(
CHAR BUF[BUFSIZE];
IF(ARGC==1) ( /*DEFAULT:CURRENT DIRECTORY*/
ATRCPY(BUF,”.”);
FSIZE(BUF);
) ELSE
WHILE(--ARGC>0) (
STRCPY(BUF,*++ARGV);
FSIZE(BUF);
)
)
Функция FSIZE печатает размер файла. Если однако файл
оказывается справочником, то FSIZE сначала вызывает функцию
DIRECTORY для обработки всех указанных в нем файлов. Обрати-
те внимание на использование имен флагов S_IFMT и _IFDIR из
файла STAT.H.
179 -
FSIZE(NAME) /*PRINT SIZE FOR NAME*/
CHAR *NAME;
(
STRUCT STAT STBUF;
IF(STAT(NAME,&STBUF)== -1) (
FPRINTF(STDERR,”FSIZE:CAN'T FIND %SN”,NAME);
RETURN;
)
IF((STBUF.ST_MODE & S_IFMT)==S_IFDIR)
DIRECTORY(NAME);
PRINTF(“%8LD %SN”,STBUF.ST_SIZE,NAME);
)
Функция DIRECTORY является самой сложной. Однако значи-
тельная ее часть связана с созданием для обрабатываемого в
данный момент файла его полного имени, по которому можно
восстановить путь в дереве.
DIRECTORY(NAME) /*FSIZE FOR ALL FILES IN NAME*/
CHAR *NAME;
(
STRUCT DIRECT DIRBUF;
CHAR *NBP, *NEP;
INT I, FD;
NBP=NAME+STRLEN(NAME);
*NBP++='/'; /*ADD SLASH TO DIRECTORY NAME*/
IF(NBP+DIRSIZ+2>=NAME+BUFSIZE) /*NAME TOO LONG*/
RETURN;
IF((FD=OPEN(NAME,0))== -1)
RETURN;
WHILE(READ(FD,(CHAR *)&DIRBUF,SIZEOF(DIRBUF))>0) (
IF(DIRBUF.D_INO==0) /*SLOT NOT IN USE*/
CONTINUE;
IF(STRCMP (DIRBUF.D_NAME,”.”)==0
!! STRCMP(DIRBUF.D_NAME,”..”)==0
CONTINUE; /*SKIP SELF AND PARENT*/
FOR (I=0,NEP=NBP;I
*NEP++=DIRBUF.D_NAME[I];
*NEP++=' ';
FSIZE(NAME);
) CLOSE(FD); *--NBP=' '; /*RESTORE
NAME*/
) Если
некоторая дыра
в справочнике
в настоящее
время не
используется
(потому что
файл был удален),
то в соответству-
ющее I-узловое
число равно
нулю, и эта позиция
пропускается.
Каждый справочник
также содержит
запись в самом
себе, назы-
ваемую “.”, и о
своем родителе,
“..”; они, очевидно,
также
должны быть
пропущены, а
то программа
будет работать
весьма
и весьма долго. 180 - Хотя
программа FSIZE
довольно
специализированна,
она все
же демонстрирует
пару важных
идей. во-первых,
многие прог-
раммы не являются
“системными
программами”;
они только ис-
пользуют информацию,
форма или содержание
которой определя-
ется операционной
системой. Во-вторых,
для таких программ
существенно,
что представление
этой информации
входит только
в стандартные
“заголовочные
файлы”, такие
как STAT.H и
DIR.H, и что программы
включают эти
файлы, а не помещают
фактические
описания внутрь
самих программ.
8.7. Пример - распределитель
памяти. В
главе 5 мы написали
бесхитростный
вариант функции
ALLOC. Вариант, который
мы напишем
теперь, не содержит
огра-
ничений: обращения
к функциям
ALLOC и FREE могут перемежать-
ся в любом порядке;
когда это необходимо,
функция ALLOC об-
ращается к
операционной
системе за
дополнительной
памятью.
Кроме того, что
эти процедуры
полезны сами
по себе, они
так-
же иллюстрируют
некоторые
соображения,
связанные с
написани-
ем машинно-зависимых
программ относительно
машинно-независи-
мым образом,
и показывают
практическое
применение
структур,
объединений
и конструкций
TYPEDEF. Вместо
того, чтобы
выделять память
из скомпилированного
внутри массива
фиксированного
размера, функция
ALLOC будет
по мере необходимости
обращаться
за памятью к
операционной
системе. Поскольку
различные
события в программе
могут тре-
бовать асинхронного
выделения
памяти, то память,
управляемая
ALLOC, не может быть
непрерывной.
В силу этого
свободная па-
мять хранится
в виде цепочки
свободных
блоков. Каждый
блок
включает размер,
указатель
следующего
блока и саму
свободную
память. Блоки
упорядочиваются
в порядке возрастания
адресов
памяти, причем
последний блок
(с наибольшим
адресом) указы-
вает на первый,
так что цепочка
фактически
оказывается
коль-
цом. При
поступлении
запроса список
свободных
блоков просмат-
ривается до
тех пор, пока
не будет найден
достаточно
большой
блок. Если этот
блок имеет в
точности требуемый
размер, то
он отцепляется
от списка и
передается
пользователю.
Если же
этот блок слишком
велик, то он
разделяется,
нужное количест-
во передается
пользователю,
а остаток
возвращается
в свобод-
ный список.
Если достаточно
большого блока
найти не удается,
то операционной
системой выделяется
новый блок,
который
включается
в список свободных
блоков; затем
поиск возобнов-
ляется. Освобождение
памяти также
влечет за собой
просмотр сво-
бодного списка
в поиске подходящего
места для введения
осво-
божденного
блока. Если
этот освободившийся
блок с какой-либо
стороны примыкает
к блоку из списка
свободных
блоков, то они
объединяются
в один блок
большего размера,
так что память
не
становится
слишком раздробленной.
Обнаружить
смежные блоки
просто, потому
что свободный
список содержится
в порядке
возрастания
адресов. 181 - Одна
из проблем, о
которой мы
упоминали в
главе 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 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 восмеричных
цифры,
которые рассмативаются
как задающие
значение желаемого
сим-
вола. Специальным
случаем этой
конструкции
является последо-
вательность
(за нулем не
следует цифра),
которая опреде-
ляет символ
NUL. если следующий
за обратной
косой чертой
символ не совпадает
с одним из указанных,
то обратная
косая
черта игнорируется.
10.4.4. Плавающие
константы Плавающая
константа
состоит из
целой части,
десятичной
точки, дробной
части, буквы
E (маленькая)
или E (большая)
и
целой экспоненты
с необязательным
знаком. Как
целая, так и
дробная часть
являются
последовательностью
цифр. Либо целая,
либо дробная
часть (но не
обе) может
отсутствовать;
либо де-
сятичная точка,
либо е (маленькая)
и экспонента
(но не то и
другое одновременно)
может отсутствовать.
Каждая плавающая
константа
считается
имеющей двойную
точность.
10.5. Строки Строка
- это последовательность
символов, заключенная
в
двойные кавычки,
как, наприимер,”...”.
Строка имеет
тип
“массив массивов”
и класс памяти
STATIC (см. Пункт 4 ниже).
Строка инициализирована
указанными
в ней символами.
Все
строки, даже
идентично
записанные,
считаются
различными.
Компилятор
помещает в
конец каждой
строки нулевой
байт , с
тем чтобы
просматривающая
строку программа
могла определить
ее конец. Перед
стоящим внутри
строки символом
двойной ка-
вычки “ должен
быть поставлен
символ обратной
косой черты
;
кроме того,
могут использоваться
те же условия
последова-
тельности, что
и в символьных
константах.
И последнее,
об-
ратная косая
черта , за которой
непосредственно
следует
символ новой
строки, игнорируется. 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” основывает
интерпретацию
идентификатора
на двух
признаках
идентификатора:
его классе
памяти и его
типе.
Класс памяти
определяет
место и время
хранения памяти,
свя-
занной с идентификатором;
тип определяет
смысл величин,
на-
ходящихся в
памяти, определенной
под идентификатором. Имеются
четыре класса
памяти: автоматическая,
статичес-
кая, внешняя
и регистровая.
Автоматические
переменные
явля-
ются локальными
для каждого
вызова блока
и исчезают при
вы-
ходе из этого
блока. Статические
переменные
являются локаль-
ными, но