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
или быть указателями на символы. значение каждой конкретной
константы должно храниться в переменной соотвествующего ти-