Нормально при работе с файлами ввод и вывод осуществля-ется последовательно: при каждом обращении к функциям READ иWRITE чтение или запись начинаются с позиции, непосредствен-но следующей за предыдущей обработанной. Но при необходимос-ти файл может читаться или записываться в любом произвольномпорядке. Обращение к системе с помощью функции LSEEK позво-ляет передвигаться по файлу, не производя фактического чте-ния или записи. В результате обращения LSEEK(FD,OFFSET,ORIGIN); текущая позиция в файле с дескриптором FD передвигается напозицию OFFSET (смещение), которая отсчитывается от места,указываемого аргументом ORIGIN (начало отсчета). Последующеечтение или запись будут теперь начинаться с этой позиции.Аргумент OFFSET имеет тип LONG; FD и ORIGIN имеют тип INT.Аргумент ORIGIN может принимать значения 0,1 или 2, указываяна то, что величина OFFSET должна отсчитываться соответст-венно от начала файла, от текущей позиции или от конца фай-ла. Например, чтобы дополнить файл, следует перед записьюнайти его конец: LSEEK(FD,0L,2); чтобы вернуться к началу ("перемотать обратно"), можно напи-сать: LSEEK(FD,0L,0); обратите внимание на аргумент 0L; его можно было бы записатьи в виде (LONG) 0. Функция LSEEK позволяет обращаться с файлами примернотак же, как с большими массивами, правда ценой более медлен-ного доступа. следующая простая функция, например, считываетлюбое количество байтов, начиная с произвольного места вфайле. GET(FD,POS,BUF,N) /*READ N BYTES FROM POSITION POS*/ INT FD, N; LONG POS; CHAR *BUF; \( LSEEK(FD,POS,0); /*GET TO POS*/ RETURN(READ(FD,BUF,N)); \) В более ранних редакциях, чем редакция 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 и наоборот. напишите каждую функцию через другую.
Пример - реализация функций 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; 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; 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*/ 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. Упражнение 8-5 --------------- Стандартная библиотека содержит функцию FSEEK(FP, OFFSET, ORIGIN) которая идентична функции LSEEK, исключая то, что FP являет-ся указателем файла, а не дескриптором файла. НапишитеFSEEK. Убедитесь, что ваша FSEEK правильно согласуется с бу-феризацией, сделанной для других функций библиотеки.
Пример - распечатка справочников
Иногда требуется другой вид взаимодействия с системойфайлов - определение информации о файле, а не того, что внем содержится. Примером может служить команда 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этим типом оказывается 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*/ \( DEV_T ST_DEV; /* DEVICE OF INODE */ 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 */ #DEFINE S_IWRITE 0200 /* WRITE PERMISSION */ #DEFINE S_IEXEC 0100 /* EXECUTE PERMISSION */ Теперь мы в состоянии написать программу FSIZE. Если по-лученный от функции STAT режим указывает, что файл не явля-ется справочником, то его размер уже под рукой и может бытьнапечатан непосредственно. Если же он оказывается справочни-ком, то мы должны обрабатывать этот справочник отдельно длякаждого файла; так как справочник может в свою очередь со-держать подсправочники, этот процесс обработки является ре-курсивным. Как обычно, ведущая программа главным образом имеет делос командной строкой аргументов; она передает каждый аргументфункции FSIZE в большой буфер. #INCLUDE <STDIO.H.>#INCLUDE <SYS/TYPES.H> /*TYPEDEFS*/#INCLUDE <SYS/DIR.H> /*DIRECTORY ENTRY STRUCTURE*/#INCLUDE <SYS/STAT.H> /*STRUCTURE RETURNED BY STAT*/#DEFINE BUFSIZE 256MAIN(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. 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); 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, и что программы включают эти файлы, а не помещаютфактические описания внутрь самих программ.
Пример - распределитель памяти
В главе 5 мы написали бесхитростный вариант функцииALLOC. Вариант, который мы напишем теперь, не содержит огра-ничений: обращения к функциям ALLOC и FREE могут перемежать-ся в любом порядке; когда это необходимо, функция ALLOC об-ращается к операционной системе за дополнительной памятью.Кроме того, что эти процедуры полезны сами по себе, они так-же иллюстрируют некоторые соображения, связанные с написани-ем машинно-зависимых программ относительно машинно-независи-мым образом, и показывают практическое применение структур,объединений и конструкций TYPEDEF. Вместо того, чтобы выделять память из скомпилированноговнутри массива фиксированного размера, функция ALLOC будетпо мере необходимости обращаться за памятью к операционнойсистеме. Поскольку различные события в программе могут тре-бовать асинхронного выделения памяти, то память, управляемаяALLOC, не может быть непрерывной. В силу этого свободная па-мять хранится в виде цепочки свободных блоков. Каждый блоквключает размер, указатель следующего блока и саму свободнуюпамять. Блоки упорядочиваются в порядке возрастания адресовпамяти, причем последний блок (с наибольшим адресом) указы-вает на первый, так что цепочка фактически оказывается коль-цом. При поступлении запроса список свободных блоков просмат-ривается до тех пор, пока не будет найден достаточно большойблок. Если этот блок имеет в точности требуемый размер, тоон отцепляется от списка и передается пользователю. Если жеэтот блок слишком велик, то он разделяется, нужное количест-во передается пользователю, а остаток возвращается в свобод-ный список. Если достаточно большого блока найти не удается,то операционной системой выделяется новый блок, которыйвключается в список свободных блоков; затем поиск возобнов-ляется. Освобождение памяти также влечет за собой просмотр сво-бодного списка в поиске подходящего места для введения осво-божденного блока. Если этот освободившийся блок с какой-либостороны примыкает к блоку из списка свободных блоков, то ониобъединяются в один блок большего размера, так что память нестановится слишком раздробленной. Обнаружить смежные блокипросто, потому что свободный список содержится в порядкевозрастания адресов. Одна из проблем, о которой мы упоминали в главе 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; \) 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пользователь может в любое время добавлять в свободный спи-сок статический или внешний массив.
* 9. Приложение А: справочное руководство по языку 'C' *
