Просмотр таблиц
В этом параграфе, чтобы проиллюстрировать новые аспекты применения структур, мы напишем ядро пакета программ, осуществляющих вставку элементов в таблицы и их поиск внутри таблиц. Этот пакет - типичный набор программ, с помощью которых работают с таблицами имен в любом макропроцессоре или компиляторе. Рассмотрим, например, инструкцию #define. Когда встречается строка вида
#define IN 1
имя IN и замещающий его текст 1 должны запоминаться в таблице. Если затем имя IN встретится в инструкции, например в
state = IN;
это должно быть заменено на 1.
Существуют две программы, манипулирующие с именами и замещающими их текстами. Это install(s,t), которая записывает имя s и замещающий его текст t в таблицу, где s и t - строки, и lookup(s), осуществляющая поиск s в таблице и возвращающая указатель на место, где имя s было найдено, или NULL, если s в таблице не оказалось.
Алгоритм основан на хэш-поиске: поступающее имя свертывается в неотрицательное число (хэш-код), которое затем используется в качестве индекса в массиве указателей. Каждый элемент этого массива является указателем на начало связанного списка блоков, описывающих имена с данным хэш-кодом. Если элемент массива равен NULL, это значит, что имен с соответствующим хэш-кодом нет.
Блок в списке - это структура, содержащая указатели на имя, на замещающий текст и на следующий блок в списке; значение NULL в указателе на следующий блок означает конец списка.
struct nlist { /* элемент таблицы */ struct nlist *next; /* указатель на следующий элемент */ char *name; /* определенное имя */ char *defn; /* замещающий текст */ };
А вот как записывается определение массива указателей:
#define HASHSIZE 101 static struct nlist *hashtab[HASHSIZE]; /* таблица указателей */
Функция хэширования, используемая в lookup и install, суммирует коды символов в строке и в качестве результата выдаст остаток от деления полученной суммы на размер массива указателей. Это не самая лучшая функция хэширования, но достаточно лаконичная и эффективная.
/* hash: получает хэш-код для строки s */ unsigned hash(char *s) { unsigned hashval;
for (hashval = 0; *s != '\0'; s++) hashval = *s + 31 * hashval; return hashval % HASHSIZE; }
Беззнаковая арифметика гарантирует, что хэш-код будет неотрицательным.
Хэширование порождает стартовый индекс для массива hashtab; если соответствующая строка в таблице есть, она может быть обнаружена только в списке блоков, на начало которого указывает элемент массива hashtab с этим индексом. Поиск осуществляется с помощью lookup. Если lookup находит элемент с заданной строкой, то возвращает указатель на нее, если не находит, то возвращает NULL.
/* lookup: ищет s */ struct nlist *lookup(char *s) { struct nlist *np;
for (np = hashtab[hash(s)]; np != NULL; np = np->next) if (strcmp(s, np->name) == 0) return np; /* нашли */ return NULL; /* не нашли */ }
В for-цикле функции lookup для просмотра списка используется стандартная конструкция
for (ptr = head; ptr != NULL; ptr = ptr->next) ...
Функция install обращается к lookup, чтобы определить, имеется ли уже вставляемое имя. Если это так, то старое определение будет заменено новым. В противном случае будет образован новый элемент. Если запрос памяти для нового элемента не может быть удовлетворен, функция install выдает NULL.
struct nlist *lookup(char *); char *strdup(char *);
/* install: заносит имя и текст (name, defn) в таблицу */ struct nlist *install(char *name, char *defn) { struct nlist *np; unsigned hashval;
if ((np = lookup(name)) == NULL) { /* не найден */ np = (struct nlist *) malloc(sizeof(*np)); if (np == NULL || (np->name = strdup(name)) == NULL) return NULL; hashval = hash(name); np->next = hashtab[hashval]; hashtab[hashval] = np; } else /* уже имеется */ free((void *) np->defn); /* освобождаем прежний defn */ if ((np->defn = strdup(defn)) == NULL) return NULL; return np; }
Упражнение 6.5. Напишите функцию undef, удаляющую имя и определение из таблицы, организация которой поддерживается функциями lookup и install.
Упражнение 6.6. Реализуйте простую версию #define-npoцeccopa (без аргументов), которая использовала бы программы этого параграфа и годилась бы для Си-программ. Вам могут помочь программы getch и ungetch.
