6.6. Просмотр таблиц

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