Язык С (Керниган, Ричи)

«Язык С» Б.В. Керниган, Д.М. Ричи

171

В более ранних редакциях, чем редакция 7 системы UNIX, основная точка входа в систему ввода-вывода называется SEEK. Функция SEEK идентична функции LSEEK, за исключением того, что аргумент OFFSET имеет тип INT, а не LONG. в соответствии с этим, поскольку на PDP-11 целые имеют только 16 битов, аргумент OFFSET, указываемый функции SEEK, ограничен величиной 65535; по этой причине аргумент ORIGIN может иметь значения 3, 4, 5, которые заставляют функцию SEEK умножить заданное значение OFFSET на 512 (количество байтов в одном физическом блоке) и затем интерпретировать ORIGIN, как если это 0, 1 или 2 соответственно. Следовательно, чтобы достичь произвольного места в большом файле, нужно два обращения к SEEK: сначала одно, котороевыделяетнужныйблок, азатемвторое, гдеORIGIN имеетзначение 1 и которое осуществляет передвижение на желаемый байт внутри блока.

Упражнение 8-2.

Очевидно, что SEEK может быть написана в терминалах LSEEK и наоборот. напишите каждую функцию через другую.

8.5. Пример - реализация функций FOPEN и GETC.

Давайте теперь на примере реализации функций FOPEN и GETC из стандартной библиотеки подпрограмм продемонстрируем, как некоторые из описанных элементов объединяются вместе.

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

Описывающая файл структура данных содержится в файле STDIO.H, который должен включаться (посредством #INCLUDE) в любой исходный файл, в котором используются функции из стандартной библиотеки. Он также включается функциями этой библиотеки. В приводимой ниже выдержке из файла STDIO.H имена, предназначаемые только для использования функциями библиотеки, начинаются с подчеркивания, с тем чтобы уменьшить вероятность совпадения с именами в программе пользователя.

DEFINE _BUFSIZE 512

DEFINE _NFILE		20 /*FILES THAT CAN BE HANDLED*/
TYPEDEF STRUCT _IOBUF \(
CHAR*_PTR; /*NEXT CHARACTER POSITION*/
INT _CNT;	/*NUMBER OF CHARACTERS LEFT*/
CHAR*_BASE;		/*LOCATION OF BUFFER*/
INT _FLAG; /*MODE OF FILE ACCESS*/
INT _FD;	/*FILE DESCRIPTOR*/
) FILE;

172

XTERN FILE _IOB[_NFILE];
DEFINE	STDIN	(&_IOB[0])
DEFINE	STDOUT	(&_IOB[1])
DEFINE	STDERR	(&_IOB[2])
DEFINE	_READ	01 /* FILE OPEN FOR READING */
DEFINE	_WRITE	02 /* FILE OPEN FOR WRITING */
DEFINE	_UNBUF	04 /* FILE IS UNBUFFERED */
DEFINE	_BIGBUF 010 /* BIG BUFFER ALLOCATED */
DEFINE _EOF 020 /* EOF HAS OCCURRED ON THIS FILE */
DEFINE _ERR 040 /* ERROR HAS OCCURRED ON THIS FILE */
DEFINE	NULL 0
DEFINE	EOF (-1)
DEFINE	GETC(P) (—(P)->_CNT >= 0 \
? *(P)->_PTR++ & 0377 : _FILEBUF(P))
DEFINE	GETCHAR() GETC(STDIN)
DEFINE	PUTC(X,P) (—(P)->_CNT >= 0 \
? *(P)->_PTR++ = (X) : _FLUSHBUF((X),P))
DEFINE	PUTCHAR(X)		PUTC(X,STDOUT)

ВнормальномсостояниимакросGETCпростоуменьшаетсчетчик,передвигает указатель и возвращает символ. (Если определение #DEFINE слишком длинное, то оно продолжается с помощью обратной косой черты). Если однако счетчик становитсяотрицательным,тоGETCвызываетфункцию_FILEBUF,котораяснова заполняетбуфер,реинициализируетсодержимоеструктурыивозвращаетсимвол. Функцияможетпредоставлятьпереносимыйинтерфейсивтожевремясодержать непереносимые конструкции: GETC маскирует символ числом 0377, которое подавляет знаковое расширение, осуществляемое на PDP-11, и тем самым гарантирует положительность всех символов.

Хотя мы не собираемся обсуждать какие-либо детали, мы все же включили сюда определение макроса PUTC, для того чтобы показать, что она работает в основном точно также, как и GETC, обращаясь при заполнении буфера к функции _FLUSHBUF.

Теперь может быть написана функция FOPEN. Большая часть программы функции FOPEN связана с открыванием файла и расположением его в нужном месте, а также с установлением битов признаков таким образом, чтобы они указывалинужноесостояние. ФункцияFOPEN невыделяеткакой-либобуферной памяти; это делается функцией _FILEBUF при первом чтении из файла.

#INCLUDE <STDIO.H>

#DEFINE PMODE 0644 /*R/W FOR OWNER;R FOR OTHERS*/ FILE *FOPEN(NAME,MODE) /*OPEN FILE,RETURN FILE PTR*/

REGISTER CHAR *NAME, *MODE; \(

REGISTER INT FD;

«Язык С» Б.В. Керниган, Д.М. Ричи

173

REGISTER FILE *FP;

IF(*MODE !=’R’&&*MODE !=’W’&&*MODE !=’A’) \( FPRINTF(STDERR,”ILLEGAL MODE %S OPENING %S\N”, MODE,NAME);

EXIT(1);

\)

FOR (FP=_IOB;FP<_IOB+_NFILE;FP++) IF((FP->_FLAG & (_READ \! _WRITE))==0) BREAK; /*FOUND FREE SLOT*/ IF(FP>=_IOB+_NFILE) /*NO FREE SLOTS*/ RETURN(NULL);

IF(*MODE==’W’) /*ACCESS FILE*/ FD=CREAT(NAME,PMODE);

ELSE IF(*MODE==’A’) \( IF((FD=OPEN(NAME,1))==-1) FD=CREAT(NAME,PMODE); LSEEK(FD,OL,2);

\) ELSE FD=OPEN(NAME,0);

IF(FD==-1) /*COULDN’T ACCESS NAME*/ RETURN(NULL);

FP->_FD=FD;

FP->_CNT=0; FP->_BASE=NULL;

FP->_FLAG &=(_READ \! _WRITE);

FP->_FLAG \!=(*MODE==’R’) ? _READ : _WRITE; RETURN(FP);

\)

Функция _FILEBUF несколько более сложная. Основная трудность заключается в том, что _FILEBUF стремится разрешить доступ к файлу и в том случае, когда может не оказаться достаточно места в памяти для буферизации ввода или вывода. если пространство для нового буфера может быть получено обращением к функции CALLOC, то все отлично; если же нет, то _FILEBUF осуществляет небуферизованный ввод/ вывод, используя отдельный символ, помещенный в локальном массиве.

#INCLUDE <STDIO.H>

_FILLBUF(FP) /*ALLOCATE AND FILL INPUT BUFFER*/ REGISTER FILE *FP;

(

STATIC CHAR SMALLBUF(NFILE);/*FOR UNBUFFERED 1/0*/

CHAR *CALLOC(); IF((FR->_FLAG&_READ)==0\!\!(FP >_FLAG&(EOF\!_ERR))\!=0

RETURN(EOF);

WHILE(FP->_BASE==NULL) /*FIND BUFFER SPACE*/

174

IF(FP->_FLAG & _UNBUF) /*UNBUFFERED*/ FP >_BASE=&SMALLBUF[FP->_FD];

ELSE IF((FP->_BASE=CALLOC(_BUFSIZE,1))==NULL)

FP->_FLAG \!=_UNBUF; /*CAN’T GET BIG BUF*/ ELSE

FP->_FLAG \!=_BIGBUF; /*GOT BIG ONE*/ FP->_PTR=FP >_BASE; FP->_CNT=READ(FP->_FD, FP->_PTR,

FP->_FLAG & _UNBUF ? 1 : _BUFSIZE); FF(—FP->_CNT<0) \( IF(FP->_CNT== -1)

FP->_FLAG \! = _EOF; ELSE

FP->_FLAG \! = _ ERR; FP->_CNT = 0; RETURN(EOF);

\)

RETURN(*FP->_PTR++ & 0377); /*MAKE CHAR POSITIVE*/ )

При первом обращении к GETC для конкретного файла счетчик оказывается равным нулю, что приводит к обращению к _FILEBUF. Если функция _FILEBUF найдет, что этот файл не открыт для чтения, она немедленно возвращает EOF. В противном случае она пытается выделить большой буфер, а если ей это не удается, то буфер из одного символа. При этом она заносит в _FLAG соответствующую информацию о буферизации.

Раз буфер уже создан, функция _FILEBUF просто вызывает функцию READ для его заполнения, устанавливает счетчик и указатели и возвращает символ из начала буфера.

Единственный оставшийся невыясненным вопрос состоит в том, как все начинается. Массив _IOB должен быть определен и инициализирован для

STDIN, STDOUT и STDERR:

FILE _IOB[NFILE] = \( (NULL,0,_READ,0), /*STDIN*/ (NULL,0,NULL,1), /*STDOUT*/

(NULL,0,NULL,_WRITE \! _UNBUF,2) /*STDERR*/ );

Из инициализации части _FLAG этого массива структур видно, что файл STDIN предназначен для чтения, файл STDOUT - для записи и файл STDERR - для записи без использования буфера.

Упражнение 8-3.

Перепишите функции FOPEN и _FILEBUF, используя поля вместо явных побитовых операций.

Упражнение 8-4.

Разработайте и напишите функции _FLUSHBUF и FCLOSE.

«Язык С» Б.В. Керниган, Д.М. Ричи

175

Упражнение 8-5.

Стандартная библиотека содержит функцию

FSEEK(FP, OFFSET, ORIGIN)

которая идентична функции LSEEK, исключая то, что FP является указателем файла, а не дескриптором файла. Напишите FSEEK. Убедитесь, что ваша FSEEK правильно согласуется с буферизацией, сделанной для других функций библиотеки.

8.6. Пример - распечатка справочников

Иногда требуется другой вид взаимодействия с системой файлов - определение информации о файле, а не того, что в нем содержится. Примером может служить команда LS (“список справочника”) системы UNIX. По этой команде распечатываются имена файлов из справочника и, необязательно, другая информация, такая как размеры, разрешения и т.д.

Поскольку, по крайней мере, на системе UNIX справочник является просто файлом, то в такой команде, как LS нет ничего особенного; она читает файл и выделяет нужные части из находящейся там информации. Однако формат информации определяется системой, так что LS должна знать, в каком виде все представляется в системе.

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

Для начала дадим краткий обзор структуры системы файлов. Справочник

-это файл, который содержит список имен файлов и некоторое указание о том, где они размещаются. Фактически это указание является индексом для другой таблицы, которую называют “I - узловой таблицей”. Для файла I-узел

-это то, где содержится вся информация о файле, за исключением его имени. Запись в справочнике состоит только из двух элементов: номера I-узла и имени файла. Точная спецификация поступает при включении файла SYS/ DIR.H, который содержит

#DEFINE DIRSIZ 14 /*MAX LENGTH OF FILE NAME*/ STRUCT DIRECT /*STRUCTURE OF DIRECTORY ENTRY*/ \(

INO_T&_INO; /*INODE NUMBER*/

CHAR &_NAME[DIRSIZ]; /*FILE NAME*/ \);

“Тип” INO_T - это определяемый посредством TYPEDEF тип, который описывает индекс I-узловой таблицы. На PDP-11 UNIX этим типом

176

оказывается UNSIGNED, но это не тот сорт информации, который помещают внутрь программы: на разных системах этот тип может быть различным. Поэтому и следует использовать TYPEDEF. Полный набор “системных” типов находится в файле SYS/TUPES.H.

Функция STAT берет имя файла и возвращает всю содержащуюся в I-ом узле информацию об этом файле (или -1, если имеется ошибка). Таким образом, в результате

STRUCT STAT STBUF;

CHAR *NAME;

STAT(NAME,&STBUF);

структура STBUF наполняется информацией из I-го узла о файле с именем NAME. Структура, описывающая возвращаемую функцией STAT информацию, находится в файле SYS/STAT.H и выглядит следующим образом:

STRUCT STAT /*STRUCTURE RETURNED BY STAT*/

\(	ST_DEV;	/* DEVICE OF INODE */
DEV_T
INO_T	ST_INO;	/* INODE NUMBER */
SHORT	ST_MODE	/* MODE BITS */
SHORT	ST_NLINK;	/ *NUMBER OF LINKS TO FILE */
SHORT	ST_UID;	/* OWNER’S USER ID */
SHORT	ST_GID;	/* OWNER’S GROUP ID */
DEV_T	ST_RDEV;	/* FOR SPECIAL FILES */
OFF_T	ST_SIZE;	/* FILE SIZE IN CHARACTERS */

TIME_T ST_ATIME; /* TIME LAST ACCESSED */ TIME_T ST_MTIME; /* TIME LAST MODIFIED */ TIME_T ST_CTIME; /* TIME ORIGINALLY CREATED */ \)

Большая часть этой информации объясняется в комментариях. Элемент ST.MODE содержит набор флагов, описывающих файл; для удобства определения флагов также находятся в файле SYS/STAT.H.

#DEFINE S_IFMT	0160000 /* TYPE OF FILE */
#DEFINE S_IFDIR	0040000		/*	DIRECTORY */
#DEFINE S_IFCHR	0020000		/* CHARACTER SPECIAL */
#DEFINE S_IFBLK	0060000		/*	BLOCK SPECIAL */
#DEFINE S_IFREG	0100000		/*	REGULAR */
#DEFINE S_ISUID 04000		/* SET		USER ID ON EXECUTION */
#DEFINE S_ISGID 02000		/* SET		GROUP ID ON EXECUTION */
#DEFINE S_ISVTX 01000		/*SAVE		SWAPPED TEXT AFTER USE*/
#DEFINE S_IREAD 0400 /* READ				PERMISSION */

			«Язык С» Б.В. Керниган, Д.М. Ричи		177
#DEFINE	S_IWRITE	0200	/*	WRITE PERMISSION */
#DEFINE	S_IEXEC	0100	/*	EXECUTE PERMISSION */

Теперь мы в состоянии написать программу FSIZE. Если полученный от функции STAT режим указывает, что файл не является справочником, то его размер уже под рукой и может быть напечатан непосредственно. Если же он оказывается справочником, то мы должны обрабатывать этот справочник отдельно для каждого файла; так как справочник может в свою очередь содержать подсправочники, этот процесс обработки является рекурсивным.

Как обычно, ведущая программа главным образом имеет дело с командной строкой аргументов; она передает каждый аргумент функции FSIZE в большой буфер.

#INCLUDE		<STDIO.H.>		/*TYPEDEFS*/
#INCLUDE		<SYS/TYPES.H>
#INCLUDE <SYS/DIR.H>				/*DIRECTORY ENTRY STRUCTURE*/
#INCLUDE <SYS/STAT.H>				/*STRUCTURE RETURNED BY STAT*/
#DEFINE BUFSIZE			256
MAIN(ARGC,ARGV)			/*FSIZE:PRINT FILE SIZES*/
CHAR	*ARGV[];
\(	BUF[BUFSIZE];
CHAR
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.

FSIZE(NAME) /*PRINT SIZE FOR NAME*/ CHAR *NAME;

\(

STRUCT STAT STBUF; IF(STAT(NAME,&STBUF)== -1) \(

FPRINTF(STDERR,”FSIZE:CAN’T FIND %S\N”,NAME); RETURN; \)

IF((STBUF.ST_MODE & S_IFMT)==S_IFDIR)

DIRECTORY(NAME);

178

PRINTF(“%8LD %S\N”,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<DIRSIZ;I++)

*NEP++=DIRBUF.D_NAME[I]; *NEP++=’\0'; FSIZE(NAME);

\)

CLOSE(FD);

*—NBP=’\0'; /*RESTORE NAME*/

)

Если некоторая дыра в справочнике в настоящее время не используется (потому что файл был удален), то в соответствующее I-узловое число равно нулю, и эта позиция пропускается. Каждый справочник также содержит запись в самом себе, называемую “.”, и о своем родителе, “..”; они, очевидно, также должны быть пропущены, а то программа будет работать весьма и весьма долго.

ХотяпрограммаFSIZEдовольноспециализированна,онавсежедемонстрирует пару важных идей. во-первых, многие программы не являются “системными программами”; они только используют информацию, форма или содержание которой определяется операционной системой. Во-вторых, для таких программ существенно, что представление этой информации входит только в стандартные “заголовочные файлы”, такие как STAT.H и DIR.H, и что программы включают эти файлы, а не помещают фактические описания внутрь самих программ.

«Язык С» Б.В. Керниган, Д.М. Ричи

179

8.7.Пример - распределитель памяти.

Вглаве 5 мы написали бесхитростный вариант функции ALLOC. Вариант, который мы напишем теперь, не содержит ограничений: обращения к функциям ALLOC и FREE могут перемежаться в любом порядке; когда это необходимо, функцияALLOCобращаетсякоперационнойсистемезадополнительнойпамятью. Кроме того, что эти процедуры полезны сами по себе, они также иллюстрируют некоторыесоображения, связанныеснаписаниеммашинно-зависимыхпрограмм относительно машинно-независимым образом, и показывают практическое применение структур, объединений и конструкций TYPEDEF.

Вместо того, чтобы выделять память из скомпилированного внутри массива фиксированного размера, функция ALLOC будет по мере необходимости обращаться за памятью к операционной системе. Поскольку различные события

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

При поступлении запроса список свободных блоков просматривается до тех пор, пока не будет найден достаточно большой блок. Если этот блок имеет

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

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

Одна из проблем, о которой мы упоминали в главе 5, заключается в обеспечении того, чтобы возвращаемая функцией ALLOC память была выровнена подходящим образом для тех объектов, которые будут в ней храниться. Хотя машины и различаются, для каждой машины существует тип, требующий наибольших ограничений по размещению памяти, если данные самого ограничительного типа можно поместить в некоторый определенный адрес, то это же возможно и для всех остальных типов. Например, на IBM 360/370,HONEYWELL 6000 и многих других машинах любой объект может храниться в границах, соответствующим переменным типа DOUBLE; на PDP-11 будут достаточны переменные типа INT.

Свободный блок содержит указатель следующего блока в цепочке, запись

180

о размере блока и само свободное пространство; управляющая информация в начале называется заголовком. Для упрощения выравнивания все блоки кратны размеру заголовка, а сам заголовок выровнен надлежащим образом. Это достигается с помощью объединения, которое содержит желаемую структуру заголовка и образец наиболее ограничительного по выравниванию типа:

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;

\)

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));