1.7 Реализация — Set

main.c будет успешно компилироваться, но прежде чем станет возможным скомпоновать и выполнить программу, надо написать код абстрактных типов данных и менеджера памяти. Если объект не хранит никакой информации и если каждый объект принадлежит только одному набору, можно представить каждый объект и каждый набор как небольшие, уникальные, целые положительные значения, используемые в качестве указателей внутри массива heap[]. Если объект является членом набора, его элемент массива содержит целое значение, представляющее набор. Объекты, следовательно, указывают на набор, содержащих их.

Это первое решение настолько простое, что мы объединяем все модули в одном файле Set.c. Наборы и объекты имеют одинаковое представление, поэтому new() не обращает внимания на описание типа. Она просто возвращает элемент в heap[] с нулевым значением:

#if ! defined MANY || MANY < 1

#define MANY    10

#endif

static int heap [MANY];

void * new (const void * type, ...) {

    int * p; /* & heap[1..] */

    for (p = heap + 1; p < heap + MANY; ++ p)

        if (! * p)

            break;

    assert(p < heap + MANY);

    * p = MANY;

    return p;

}

Мы используем ноль, чтобы пометить доступные элементы heap[]; таким образом, невозможно вернуть ссылку на heap[0] — если бы он был набором, его элементы не содержали бы нулевое значение индекса.

Перед тем как добавить объект в набор, мы присваиваем ему невозможное значение индекса MANY, так что new() не сможет найти его снова, а мы всё же не сможем ошибиться, приняв его за члена какого-либо набора.

new() может не хватить памяти. Это первая из многих ошибок, которые "не могут произойти". Чтобы отметить такие точки, мы будем просто использовать макрос ANSI-C assert(). Более реалистичная реализация должна по крайней мере вывести разумное сообщение об ошибке или использовать общую функцию обработки ошибок, которую пользователь может переопределить. Однако, для цели разработки методики кодирования мы предпочитаем сохранять код лаконичным. Мы рассмотрим общую технику обработки исключений в главе 13.

delete() должна правильно работать с нулевыми указателями. Элемент heap[] освобождает своё место после установке его равным нулю:

void delete (void * _item) {

    int * item = _item;

    if (item) {

        assert(item > heap && item < heap + MANY);

        * item = 0;

    }

}

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

Набор представлен в своих объектах: каждый элемент указывает на данный набор. Если элемент содержит MANY, он может быть добавлен к набору, в противном случае, он уже должен быть в наборе, поскольку мы не позволяем объекту принадлежать более чем одному набору.

void * add (void * _set, const void * _element) {

    int * set = _set;

    const int * element = _element;

    assert(set > heap && set < heap + MANY);

    assert(* set == MANY);

    assert(element > heap && element < heap + MANY);

    if (* element == MANY)

        * (int *) element = set — heap;

    else

        assert(* element == set — heap);

    return (void *) element;

}

assert() берёт на себя страховку: мы хотели бы иметь дело только с указателями в пределах heap[] и данный набор не должен принадлежать какому-то другому набору, то есть значение элемента его массива должно быть MANY.

Другие функции такие же простые. find() просто проверят, содержит ли элемент правильный индекс для данного набора:

void * find (const void * _set, const void * _element) {

    const int * set = _set;

    const int * element = _element;

    assert(set > heap && set < heap + MANY);

    assert(* set == MANY);

    assert(element > heap && element < heap + MANY);

    assert(* element);

    return * element == set — heap ? (void *) element : 0;

}

contains() преобразует результат работы find() в значение истинности:

int contains (const void * _set, const void * _element) {

    return find(_set, _element) != 0;

}

Чтобы проверить, на самом ли деле отбрасываемый элемент принадлежит набору, drop() может рассчитывать на find(). Если да, объекту возвращается его к статус с помощью метки MANY:

void * drop (void * _set, const void * _element) {

    int * element = find(_set, _element);

    if (element)

        * element = MANY;

    return element;

}

Если бы мы более придирчивы, то могли бы настоять, чтобы такой отбрасываемый элемент не принадлежал к другому набору. В таком случае, однако, в drop() была бы повторена большая часть кода find().

Наша реализация весьма нетрадиционная. Оказывается, что для реализации набора нет необходимости в differ(). Однако всё же надо предоставить эту функцию, потому что эту функцию использует наше приложение.

int differ (const void * a, const void * b) {

    return a != b;

}

Объекты отличаются ровно тогда, когда индексы массива, представляющие их, различаются, то есть достаточно простого сравнения указателя.

Работа завершена — для этого решения мы не использовали дескрипторы Set и Object, но необходимо определить их, чтобы доставить счастье нашему компилятору C:

const void * Set;

const void * Object;

Мы использовали эти указатели в main() для создания новых наборов и объектов.