Поиск в таблице

Для иллюстрации дальнейших аспектов использования струк-

тур в этом разделе мы напишем программу, представляющую со-

бой содержимое пакета поиска в таблице. Эта программа явля-

ется типичным представителем подпрограмм управления символь-

ными таблицами макропроцессора или компилятора. Рассмотрим,

например, оператор #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.