Для иллюстрации дальнейших аспектов использования струк-тур в этом разделе мы напишем программу, представляющую со-бой содержимое пакета поиска в таблице. Эта программа явля-ется типичным представителем подпрограмм управления символь-ными таблицами макропроцессора или компилятора. Рассмотрим,например, оператор #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 , получается просто как остаток отделения суммы символьных значений строки на размер массива.(Это не самый лучший возможный алгоритм, но его достоинствосостоит в исключительной простоте). 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); \) Функция STRSAVE просто копирует строку, указанную в ка-честве аргумента, в место хранения, полученное в результатеобращения к функции ALLOC. Мы уже привели эту функцию в гла-ве 5. Так как обращение к функции ALLOC и FREE могут проис-ходить в любом порядке и в связи с проблемой выравнивания,простой вариант функции ALLOC из главы 5 нам больше не под-ходит; смотрите главы 7 и 8. Упражнение 6-7 --------------- Напишите процедуру, которая будет удалять имя и опреде-ление из таблицы, управляемой функциями LOOKUP и INSTALL. Упражнение 6-8 --------------- Разработайте простую, основанную на функциях этого раз-дела, версию процессора для обработки конструкций #DEFINE ,пригодную для использования с "C"-программами. Вам могуттакже оказаться полезными функции GETCHAR и UNGETCH.
Поля
Когда вопрос экономии памяти становится очень существен-ным, то может оказаться необходимым помещать в одно машинноеслово несколько различных объектов; одно из особенно расп-росраненных употреблений - набор однобитовых признаков вприменениях, подобных символьным таблицам компилятора. внеш-не обусловленные форматы данных, такие как интерфейсы аппа-ратных средств также зачастую предполагают возможность полу-чения слова по частям. Представьте себе фрагмент компилятора, который работаетс символьной таблицей. С каждым идентификатором программысвязана определенная информация, например, является он илинет ключевым словом, является ли он или нет внешним и/илистатическим и т.д. Самый компактный способ закодировать та-кую информацию - поместить набор однобитовых признаков в от-дельную переменную типа CHAR или INT. Обычный способ, которым это делается, состоит в опреде-лении набора "масок", отвечающих соответствущим битовым по-зициям, как в #DEFINE KEYWORD 01 #DEFINE EXTERNAL 02 #DEFINE STATIC 04 (числа должны быть степенями двойки). Тогда обработка битовсведется к "жонглированию битами" с помощью операций сдвига,маскирования и дополнения, описанных нами в главе 2. Некоторые часто встречающиеся идиомы: FLAGS \!= EXTERNAL \! STATIC; включает биты EXTERNAL и STATIC в FLAGS, в то время как FLAGS &= \^(еXTERNAL \! STATIC); их выключает, а 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. При работе с полями имеется ряд моментов, на которыеследует обратить внимание. По-видимому наиболее существеннымявляется то, что отражая природу различных аппаратных сред-ств, распределение полей на некоторых машинах осуществляетсяслева направо, а на некоторых справа налево. Это означает,что хотя поля очень полезны для работы с внутренне опреде-ленными структурами данных, при разделении внешне определяе-мых данных следует тщательно рассматривать вопрос о том, ка-кой конец поступает первым. Другие ограничения, которые следует иметь в виду: поляне имеют знака; они могут храниться только в переменных типаINT (или, что эквивалентно, типа UNSIGNED); они не являютсямассивами; они не имеют адресов, так что к ним не применимаоперация &.
