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