5.4 Реализация суперкласса — Name

Поиск символов по имени является стандартной задачей. К сожалению, стандарт ANSI не определяет подходящую библиотечную функцию, чтобы её решить. bsearch() — бинарный поиск в отсортированной таблице — почти подходит, но если мы вставляем хотя бы один новый символ, то должны вызвать qsort(), чтобы подготовить почву для дальнейшего поиска.

Чтобы иметь дело с растущими таблицами, системы UNIX могут предоставить два или три семейства функций. lsearch() — линейный поиск в массиве и добавление в конец(!) — это совсем неэффективно. hsearch() — хэш-таблица для структур, состоящих из текста и информационного указателя — поддерживает только одну таблицу фиксированного размера и навязывает неудобную структуру для записей. tsearch() — бинарное дерево с произвольным сравнением и удалением — это наиболее универсальное семейство, но весьма неэффективное, если начальные символы устанавливаются из отсортированной последовательности.

В операционной системе UNIX tsearch(), вероятно, лучший компромисс. Исходный код для переносимой реализации с бинарно связанными деревьями можно найти в [Sch87]. Однако, если эта семейство недоступно или если нельзя гарантировать случайную инициализацию, следует поискать более простой способ реализации. Оказывается, что хорошая реализация bsearch() очень легко может быть расширена для поддержки вставки в отсортированный массив:

void * binary (const void * key,

    void * _base, size_t * nelp, size_t width,

    int (* cmp) (const void * key, const void * elt))

{

    size_t nel = * nelp;

#define base (* (char **) & _base)

    char * lim = base + nel * width, * high;

    if (nel > 0) {

        for (high = lim - width; base <= high; nel >>= 1) {

            char * mid = base + (nel >> 1) * width;

            int c = cmp(key, mid);

            if (c < 0)

                high = mid - width;

            else if (c > 0)

                base = mid + width, -- nel;

            else

                return (void *) mid;

        }

До этого места это стандартный бинарный поиск в произвольном массиве. key указывает на объект, который найден; base изначально стартовый адрес таблицы элементов *nelp, каждый из которых имеет размер width байтов; а cmp является функцией для сравнения ключа с элементом таблицы. На данный момент мы либо нашли элемент таблицы и вернули его адрес, либо base теперь адрес, где ключ должен быть в таблице. Мы продолжаем следующим образом:

        memmove(base + width, base, lim - base);

    }

    ++ *nelp;

    return memcpy(base, key, width);

#undef base

}

memmove() перемещает конец массива из пути (* memmove() копирует байты, даже если исходная и целевая области перекрываются; memcpy() не делает этого, но является более эффективной.), а memcpy() вставляет ключ. Мы предполагаем, что есть место за пределами массива и записываем через nelp, что добавили элемент — binary() отличается от стандартной функции bsearch() только тем, что требует адрес, а не значение переменной, содержащей число элементов в таблице.

Создав универсальные средства поиска и ввода, можно легко управлять нашей таблицей символов. Во-первых, надо сравнивать ключ с элементом таблицы:

static int cmp (const void * _key, const void * _elt) {

    const char * const * key = _key;

    const struct Name * const * elt = _elt;

    return strcmp(* key, (* elt) -> name);

}

В качестве ключа передаётся только адрес указателя на текст входного символа. Элементами таблицы являются, конечно же, структуры Name и мы посматриваем только их компонент .name.

Поиск или ввод осуществляется вызовом binary() с подходящими параметрами. Так как количество символов заранее неизвестно, мы всегда удостоверяемся, что есть место для расширения таблицы:

static struct Name ** search (const char ** name) {

    static const struct Name ** names; /* динамическая таблица */

    static size_t used, max;

    if (used >= max) {

        names = names

            ? realloc(names, (max *= 2) * sizeof * names)

            : malloc((max = NAMES) * sizeof * names);

        assert(names);

    }

    return binary(name, names, & used, sizeof * names, cmp);

}

NAMES это заданная постоянная с первоначальным количеством записей в таблице; каждый раз выйдя за границы мы удваиваем размер таблицы.

search() принимает адрес указателя на текст, который надо найти, и возвращает адрес записи в таблице. Если текст не может быть найден в таблице, binary() вставляет ключ — то есть только указатель на текст, а не struct Name — в таблицу. Такая стратегия реализована в интересах screen(), которая только создаёт новый элемент таблицы только если идентификатор из ввода действительно неизвестен:

int screen (const char * name) {

    struct Name ** pp = search(& name);

    if (* pp == (void *) name) /* введённое имя */

        * pp = new(Var, name);

    symbol = * pp;

    return (* pp) -> token;

}

screen() позволяет search() найти символ ввода для подмены. Если указатель на текст символа есть в таблице символов, мы должны заменить его на запись, описывающую новый идентификатор.

Для screen() новый идентификатор должен быть переменной. Мы предполагаем, что существует тип описания Var, который знает, как сконструировать структуры Name, описывающие переменные, и предоставляем new() сделать всё остальное. В любом случае, мы позволяем symbol указать на запись таблицы символов и возвращаем его значение .token.

void install (const void * np) {

    const char * name = ((struct Name *) np) -> name;

    struct Name ** pp = search(& name);

    if (* pp != (void *) name)

        error("cannot install name twice: %s", name);

    * pp = (struct Name *) np;

}

install() немного проще. Мы принимаем объект Name и предоставляем search() найти его в таблице символов. Предполагается, что install() имеет дело только с новыми символами, поэтому всегда должна происходить замена имени на объект. В противном случае, если search() действительно находит символ, у нас неприятность.