Реферат: Язык С 
обеспечив то, чтобы распределитель
памяти всегда возвращал
указатель, удовлетворяющий всем
ограничениям выравнивания.
Например, на PDP-11 достаточно,
чтобы функция ALLOC всегда
возвращала четный указатель,
поскольку в четный адрес можно
поместить любой тип объекта.
единственный расход при этом -
лишний символ при запросе на
нечетную длину. Аналогичные
действия предпринимаются на других
машинах. Таким образом,
реализация ALLOC может не оказаться
переносимой, но ее ис-
пользование будет переносимым.
Функция ALLOC из главы 5 не
предусматривает никакого определенного
выравнивания; в главе
8 мы продемонстрируем, как
правильно выполнить эту задачу.
Вопрос описания типа функции
ALLOC является мучительным
для любого языка, который серьезно
относится к проверке ти-
пов. Лучший способ в языке “C” -
объявить, что ALLOC возвра-
щает указатель на переменную типа
CHAR, а затем явно преоб-
разовать этот указатель к желаемому
типу с помощью операции
перевода типов. Таким образом, если
описать P в виде
CHAR *P;
то
(STRUCT TNODE *) P
преобразует его в выражениях в
указатель на структуру типа TNODE . Следовательно, функцию TALLOC можно
записать в виде:
STRUCT TNODE *TALLOC()
\(
CHAR *ALLOC();
RETURN ((STRUCT TNODE *)
ALLOC(SIZEOF(STRUCT TNODE)));
\)
это более чем достаточно для
работающих в настоящее время
компиляторов, но это и самый
безопасный путь с учетом будую-
щего.
Упражнение 6-4.
Напишите программу, которая
читает “C”-программу и печа-
тает в алфавитном порядке каждую
группу имен переменных, ко-
торые совпадают в первых семи
символах, но отличаются где-то
дальше. (Сделайте так, чтобы 7 было
параметром).
Упражнение 6-5.
Напишите программу выдачи
перекрестных ссылок, т.е.
Программу, которая печатает список
всех слов документа и для
каждого из этих слов печатает
список номеров строк, в кото-
рые это слово входит.
Упражнение 6-6.
Напишите программу, которая
печатает слова из своего
файла ввода, расположенные в
порядке убывания частоты их по-
явления. Перед каждым словом
напечатайте число его появле-
ний.
·
143 -
6.6. Поиск в таблице.
Для иллюстрации дальнейших
аспектов использования струк-
тур в этом разделе мы напишем
программу, представляющую со-
бой содержимое пакета поиска в
таблице. Эта программа явля-
ется типичным представителем
подпрограмм управления символь-
ными таблицами макропроцессора или компилятора.
Рассмотрим,
например, оператор #DEFINE языка
“C”. Когда встречается
строка вида
#DEFINE YES 1
то имя YES и заменяющий текст 1
помещаются в таблицу. Позд-
нее, когда имя YES появляется в
операторе вида
INWORD = YES;
Oно должно быть замещено на 1.
Имеются две основные
процедуры, которые управляют имена-
ми и заменяющими их текстами.
Функция INSTALL(S,T) записыва-
ет имя S и заменяющий текст T в
таблицу; здесь S и T просто
символьные строки. Функция
LOOKUP(S) ищет имя S в таблице и
возвращает либо указатель того
места, где это имя найдено,
либо NULL, если этого имени в
таблице не оказалось.
При этом используется поиск по
алгоритму хеширования -
поступающее имя преобразуется в
маленькое положительное чис-
ло, которое затем используется для
индексации массива указа-
телей. Элемент массива указывает на
начало цепочных блоков,
описывающих имена, которые имеют
это значение хеширования.
Если никакие имена при хешировании
не получают этого значе-
ния, то элементом массива будет
NULL.
Блоком цепи является
структура, содержащая указатели на
соответствующее имя, на заменяющий
текст и на следующий блок
в цепи. Нулевой указатель
следующего блока служит признаком
конца данной цепи.
STRUCT NLIST \( /* BASIC TABLE
ENTRY */
CHAR *NAME;
CHAR *DEF;
STRUCT NLIST NEXT; / NEXT ENTRY
IN CHAIN */
\);
Массив указателей это просто
DEFINE HASHSIZE 100
TATIC STRUCT NLIST HASHTAB[HASHSIZE]
/ POINTER TABLE */
Значение функции хеширования,
используемой обеими функ-
циями LOOKUP и INSTALL , получается
просто как остаток от
деления суммы символьных значений
строки на размер массива.
(Это не самый лучший возможный
алгоритм, но его достоинство
состоит в исключительной простоте).
·
144 -
HASH(S) /* FORM HASH VALUE FOR
STRING */
CHAR *S;
\(
INT HASHVAL;
FOR (HASHVAL = 0; *S != '\0'; )
HASHVAL += *S++;
RETURN(HASHVAL % HASHSIZE);
\)
В результате процесса
хеширования выдается начальный ин-
декс в массиве HASHTAB ; если
данная строка может быть
где-то найдена, то именно в цепи
блоков, начало которой ука-
зано там. Поиск осуществляется
функцией LOOKUP. Если функция
LOOKUP находит, что данный элемент
уже присутствует, то она
возвращает указатель на него; если
нет, то она возвращает
NULL.
STRUCT NLIST LOOKUP(S) /
LOOK FOR S IN HASHTAB */
CHAR *S;
\(
STRUCT NLIST *NP;
FOR (NP = HASHTAB[HASH(S)]; NP !=
NULL;NP=NP->NEXT)
IF (STRCMP(S, NP->NAME) == 0)
RETURN(NP); /* FOUND IT */
RETURN(NULL); /* NOT FOUND */
Функция INSTALL использует
функцию LOOKUP для определе-
ния, не присутствует ли уже вводимое
в данный момент имя;
если это так, то новое определение
должно вытеснить старое.
В противном случае создается
совершенно новый элемент. Если
по какой-либо причине для нового
элемента больше нет места,
то функция INSTALL возвращает NULL.
STRUCT NLIST INSTALL(NAME,
DEF) / PUT (NAME, DEF) */
CHAR *NAME, *DEF;
\(
STRUCT NLIST *NP, *LOOKUP();
CHAR *STRSAVE(), *ALLOC();
INT HASHVAL;
IF((NP = LOOKUP(NAME)) == NULL)
\( /* NOT FOUND */
NP = (STRUCT NLIST *)
ALLOC(SIZEOF(*NP));
IF (NP == NULL)
RETURN(NULL);
IF ((NP->NAME = STRSAVE(NAME)) ==
NULL)
RETURN(NULL);
HASHVAL = HASH(NP->NAME);
NP->NEXT = HASHTAB[HASHVAL];
HASHTAB[HASHVAL] = NP;
\) ELSE /* ALREADY THERE
*/
FREE((NP->DEF);/* FREE PREVIOUS
DEFINITION */
IF ((NP->DEF = STRSAVE(DEF))
== NULL)
RETURN (NULL);
RETURN(NP);
\)
·
145 -
Функция STRSAVE просто
копирует строку, указанную в ка-
честве аргумента, в место хранения,
полученное в результате
обращения к функции ALLOC. Мы уже
привели эту функцию в гла-
ве 5. Так как обращение к функции
ALLOC и FREE могут проис-
ходить в любом порядке и в связи с
проблемой выравнивания,
простой вариант функции ALLOC из
главы 5 нам больше не под-
ходит; смотрите главы 7 и 8.
Упражнение 6-7.
Напишите процедуру, которая
будет удалять имя и опреде-
ление из таблицы, управляемой
функциями LOOKUP и INSTALL.
Упражнение 6-8.
Разработайте простую,
основанную на функциях этого раз-
дела, версию процессора для
обработки конструкций #DEFINE ,
пригодную для использования с
“C”-программами. Вам могут
также оказаться полезными функции
GETCHAR и UNGETCH.
6.7. Поля.
Когда вопрос экономии
памяти становится очень существен-
ным, то может оказаться необходимым
помещать в одно машинное
слово несколько различных объектов;
одно из особенно расп-
росраненных употреблений - набор
однобитовых признаков в
применениях, подобных символьным
таблицам компилятора. внеш-
не обусловленные форматы данных,
такие как интерфейсы аппа-
ратных средств также зачастую
предполагают возможность полу-
чения слова по частям.
Представьте себе фрагмент
компилятора, который работает
с символьной таблицей. С каждым
идентификатором программы
связана определенная информация,
например, является он или
нет ключевым словом, является ли он
или нет внешним и/или
статическим и т.д. Самый компактный
способ закодировать та-
кую информацию - поместить набор
однобитовых признаков в от-
дельную переменную типа CHAR или
INT.
Обычный способ, которым это
делается, состоит в опреде-
лении набора “масок”, отвечающих
соответствущим битовым по-
зициям, как в
#DEFINE
KEYWORD 01
#DEFINE
EXTERNAL 02
#DEFINE
STATIC 04
(числа должны быть степенями
двойки). Тогда обработка битов
сведется к “жонглированию битами” с
помощью операций сдвига,
маскирования и дополнения,
описанных нами в главе 2.
Некоторые часто встречающиеся
идиомы:
FLAGS \!= EXTERNAL \! STATIC;
включает биты EXTERNAL и STATIC
в FLAGS, в то время как
FLAGS &= \^(еXTERNAL \!
STATIC);
·
146 -
их выключает, а
IF ((FLAGS & (EXTERNAL \!
STATIC)) == 0) ...
истинно, если оба бита
выключены.
Хотя этими идиомами легко
овладеть, язык “C” в качестве
альтернативы предлагает возможность
определения и обработки
полей внутри слова непосредственно,
а не посредством побито-
вых логических операций. Поле - это
набор смежных битов
внутри одной переменной типа INT.
Синтаксис определения и
обработки полей основывается на
структурах. Например, сим-
вольную таблицу конструкций
#DEFINE, приведенную выше, можно
бы было заменить определением
трех полей:
STRUCT \(
UNSIGNED IS_KEYWORD : 1;
UNSIGNED IS_EXTERN : 1;
UNSIGNED IS_STATIC : 1;
\) FLAGS;
Здесь определяется переменная с
именем FLAGS, которая содер-
жит три 1-битовых поля. Следующее
за двоеточием число задает
ширину поля в битах. Поля описаны
как UNSIGNED, чтобы под-
черкнуть, что они действительно
будут величинами без знака.
На отдельные поля можно
ссылаться, как FLAGS.IS_STATIE,
FLAGS. IS_EXTERN, FLAGS.IS_KEYWORD
И т.д., то есть точно так
же, как на другие члены структуры.
Поля ведут себя подобно
небольшим целым без знака и могут
участвовать в арифметичес-
ких выражениях точно так же, как и
другие целые. Таким обра-
зом, предыдущие примеры более
естественно переписать так:
FLAGS.IS_EXTERN =
FLAGS.IS_STATIC = 1;
для включения битов;
FLAGS.IS_EXTERN =
FLAGS.IS_STATIC = 0;
для выключения битов;
IF (FLAGS.IS_EXTERN == 0
&&FLAGS.IS_STATIC == 0)...
для их проверки.
Поле не может перекрывать
границу INT; если указанная
ширина такова, что это должно
случиться, то поле выравнива-
ется по границе следующего INT.
Полям можно не присваивать
имена; неименованные поля (только
двоеточие и ширина) ис-
пользуются для заполнения
свободного места. Чтобы вынудить
выравнивание на границу следующего
INT, можно использовать
специальную ширину 0.
·
147 -
При работе с полями имеется
ряд моментов, на которые
следует обратить внимание.
По-видимому наиболее существенным
является то, что отражая природу
различных аппаратных сред-
ств, распределение полей на
некоторых машинах осуществляется
слева направо, а на некоторых
справа налево. Это означает,
что хотя поля очень полезны для
работы с внутренне опреде-
ленными структурами данных, при
разделении внешне определяе-
мых данных следует тщательно
рассматривать вопрос о том, ка-
кой конец поступает первым.
Другие ограничения, которые
следует иметь в виду: поля
не имеют знака; они могут храниться
только в переменных типа
INT (или, что эквивалентно, типа
UNSIGNED); они не являются
массивами; они не имеют адресов,
так что к ним не применима
операция &.
6.8. Объединения.
Oбъединения - это
переменная, которая в различные момен-
ты времени может содержать объекты
разных типов и размеров,
причем компилятор берет на себя
отслеживание размера и тре-
бований выравнивания. Объединения
представляют возможность
работать с различными видами данных
в одной области памяти,
не вводя в программу никакой
машинно-зависимой информации.
В качестве примера, снова из
символьной таблицы компиля-
тора, предположим, что константы
могут быть типа INT , FLOAT
или быть указателями на символы.
значение каждой конкретной
константы должно храниться в
переменной соотвествующего ти-
па, но все же для управления
таблицей самым удобным было бы,
если это значение занимало бы один
и тот же объем памяти и
хранилось в том же самом месте
независимо от его типа. это и
является назначением объединения -
выделить отдельную пере-
менную, в которой можно законно
хранить любую одну из пере-
менных нескольких типов. Как и в
случае полей, синтаксис ос-
новывается на структурах.
UNION U_TAG \(
INT IVAL;
FLOAT FVAL;
CHAR *PVAL;
\) UVAL;
Переменная UVAL будет иметь
достаточно большой размер,чтобы
хранить наибольший из трех типов,
независимо от машины, на
которой осуществляется компиляция,
- программа не будет за-
висить от характеристик аппаратных
средств. Любой из этих
трех типов может быть присвоен UVAR
и затем использован в
выражениях, пока такое
использование совместимо: извлекаемый
тип должен совпадать с последним
помещенным типом. Дело
программиста - следить за тем,
какой тип хранится в объеди-
нении в данный момент; если
что-либо хранится как один тип,
а извлекается как другой, то
результаты будут зависеть от
используемой машины.
·
149 -
Синтаксически доступ к членам
объединения осуществляется
следующим образом:
имя объединения.член
или
указатель объединения ->член
то есть точно так же, как и в
случае структур. если для отс-
леживания типа, хранимого в данный
момент в UVAL, использу-
ется переменная UTYPE, то можно
встретить такой участок
программы:
IF (UTYPE == INT)
PRINTF(“%D\N”, UVAL.IVAL);
ELSE IF (UTYPE == FLOAT)
PRINTF(“%F\N”, UVAL.FVAL);
ELSE IF (UTYPE == STRING)
PRINTF(“%S\N”, UVAL.PVAL);
ELSE
PRINTF(“BAD TYPE %D IN UTYPE\N”, UTYPE);
Объединения могут появляться
внутри структур и массивов
и наоборот. Запись для обращения к
члену объединения в
структуре (или наоборот) совершенно
идентична той, которая
используется во вложенных
структурах. например, в массиве
структур, определенным следующим
образом
STRUCT \(
CHAR *NAME;
INT FLAGS;
INT UTYPE;
UNION \(
INT IVAL;
FLOAT FVAL;
CHAR *PVAL;
\) UVAL;
\) SYMTAB[NSYM];
на переменную IVAL можно
сослаться как
SYMTAB[I].UVAL.IVAL
а на первый символ строки PVAL
как
*SYMTAB[I].UVAL.PVAL
В сущности объединение
является структурой, в которой все
члены имеют нулевое смещение. Сама
структура достаточно ве-
лика, чтобы хранить “самый широкий”
член, и выравнивание
пригодно для всех типов, входящих в
объединение. Как и в
случае структур, единственными
операциями, которые в настоя-
щее время можно проводить с
объединениями, являются доступ к
·
150 -
члену и извлечение адреса;
объединения не могут быть присво-
ены, переданы функциям или
возвращены ими. указатели объеди-
нений можно использовать в точно
такой же манере, как и ука-
затели структур.
Программа распределения
памяти, приводимая в главе 8 ,
показывает, как можно использовать
объединение, чтобы сде-
лать некоторую переменную
выровненной по определенному виду
границы памяти.
6.9. Определение типа
В языке “C” предусмотрена
возможность, называемая TYPEDEF
для введения новых имен для
типов данных. Например, описание
TYPEDEF INT LENGTH;
делает имя LENGTH синонимом для
INT. “Тип” LENGTH может быть использован в описаниях, переводов типов и т.д.
Точно таким же образом, как и тип INT:
LENGTH
LEN, MAXLEN;
LENGTH
*LENGTHS[];
Аналогично описанию
TYPEDEF CHAR *STRING;
делает STRING синонимом для CHAR*,
то есть для указателя на
символы, что затем можно
использовать в описаниях вида
STRING P, LINEPTR[LINES],
ALLOC();
Обратите внимание, что
объявляемый в конструкции TYPEDEF
тип появляется в позиции имени
переменной, а не сразу за
словом TYPEDEF. Синтаксически
конструкция TYPEDEF подобна
описаниям класса памяти EXTERN,
STATIC и т. Д. мы также ис-
пользовали прописные буквы, чтобы
яснее выделить имена.
В качестве более сложного
примера мы используем конст-
рукцию TYPEDEF для описания
узлов дерева, рассмотренных ра-
нее в этой главе:
TYPEDEF STRUCT TNODE \( /* THE
BASIC NODE */
CHAR WORD; / POINTS TO THE
TEXT */
INT COUNT; /* NUMBER OF OCCURRENCES
*/
STRUCT TNODE
LEFT; / LEFT CHILD */
STRUCT TNODE
RIGHT; / RIGHT CHILD */
\) TREENODE, *TREEPTR;
В результате получаем два новых
ключевых слова: TREENODE
(структура) и TREEPTR (указатель на
структуру). Тогда функ-
цию TALLOC можно записать в виде
·
151 -
TREEPTR TALLOC()
\(
CHAR *ALLOC();
RETURN((TREEPTR)
ALLOC(SIZEOF(TREENODE)));
\)
Необходимо подчеркнуть, что
описание TYPEDEF не приводит
к созданию нового в каком-либо
смысле типа; оно только до-
бавляет новое имя для некоторого
существующего типа. при
этом не возникает и никакой новой
семантики: описанные таким
Страницы: 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
|
