» Главная
eXcode.ru » Статьи » Другие
» Новости
» Опросы
» Файлы
» Журнал



Пользователей: 0
Гостей: 8





Среда разработки: библиотека базовых классов (продолжение)




Исключения

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

Начнем с базового класса Exception (исключение), обладающего несложным протоколом:

class Exception {
public:

Exception(const char* name, const char* who, const char* what);
void display() const;
const char* name() const;
const char* who() const;
const char* what() const;
protected:
...
};

Каждой особой ситуации можно сопоставить имя ее источника и причину возникновения. Кроме того, мы можем обеспечить скрытые от клиентов средства для вывода информации об ошибке в соответствующий поток.

Анализ различных классов нашей библиотеки подсказывает возможные типы исключений, которые можно оформить в виде подклассов базового класса Exception:

  • ContainerError
  • Duplicate
  • IllegalPattern
  • IsNull
  • LexicalError
  • MathError
  • NotFound
  • NotNull
  • NotRoot
  • Overflow
  • RangeError
  • StorageError
  • Underflow
Объявление класса overflow (переполнение) может выглядеть следующим образом:

class Overflow : public Exception {
public:

Overflow(const char* who, const char* what)
: Exception("Overflow", who, what) {}
};

Обязанность этого класса состоит лишь в знании своего имени, которое он передает конструктору суперкласса.

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

inline void _assert(int expression, const Exception& exception)
{

if (!expression)
throw(exception);
}

Для эффективности мы определили эту функцию как встроенную. Преимущество подобной схемы состоит в том, что она локализует все исключения (в C++ throw имеет синтаксис вызова функции). Так, для трансляторов, которые до сих пор не поддерживают исключений, можно использовать специальную директиву (-D для большинства трансляторов C++) для переопределения вызова throw в вызов другой функции-не-члена, выводящей сообщение на экран и останавливающей выполнение программы:

void _catch(const Exception& e)
{

cerr << "EXCEPTION: ";
e.display();
exit(1);
}

Рассмотрим реализацию функции insert класса Bounded:

template<class Item, unsigned int Size>
void Bounded<Item, Size>::insert(const Item& item)
{

unsigned int count = length();
_assert((count < Size), Overflow("Bounded::Insert", "structure is full"));
if (!count) start = stop = 1;
else
{ start--;
if (!start) start = Size;
}
rep[start - 1] = item;
}

Предусмотрено, что в процессе выполнения функции проверяется, что размер структуры не превосходит максимально допустимого. Если это не так, возбуждается исключение Overflow.

Важнейшим преимуществом этого подхода является гарантия того, что состояние объекта, возбудившего исключение, не будет нарушено (не считая случая исчерпания оперативной памяти, когда уже в принципе ничего нельзя поделать). Любая функция, прежде чем произвести действия, способные изменить состояние объекта, проверяет предположение. В приведенной выше функции insert, например, прежде, чем добавить элемент в массив, мы сначала вызываем селектор (который не может вызвать изменения состояния объекта), затем проверяем все предусловия функции и лишь затем изменяем состояние объекта. Мы скрупулезно придерживались подобного стиля при реализации всех функций и настоятельно советуем не отходить от него при конструировании подклассов, основанных на нашей библиотеке.

Рис. 9-8 иллюстрирует схему взаимодействия классов, обеспечивающих реализацию механизма обработки исключений.
 

Рис. 9-8. Классы обработки исключений.

Итерация

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

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

  • Наличие выделенного итератора классов позволяет одновременно проводить несколько просмотров одного и того же объекта.
  • Наличие итерационного механизма в самом классе несколько нарушает его инкапсуляцию; выделение итератора в качестве отдельного механизма поведения способствует достижению большей ясности в описании класса.
Для каждой структуры определены две формы итераций. Активный итератор требует каждый раз от клиента явного обращения к себе для перехода к следующему элементу. Пассивный итератор применяет функцию, предоставляемую клиентом, и, таким образом, требует меньшего участия клиента. Чтобы обеспечить безопасность типов, для каждой структуры создаются свои итераторы.

Рассмотрим в качестве примера активный итератор для класса Queue:

template <class Item>
class QueueActiveIterator {
public:

QueueActiveIterator(const Queue<Item>&);
~QueueActiveIterator();
Пассивный итератор реализует "применяемую" функцию. Эта идиома обычно используется в функциональных языках программирования.
void reset();
int next();
int isDone() const;
const Item* currentItem() const;
protected:
const Queue<Item>& queue;
int index;
};

Каждому итератору в момент создания ставится в соответствие определенный объект. Итерация начинается с "верха" структуры, что бы это ни значило для данной абстракции.

С помощью функции currentItem клиент может получить доступ к текущему элементу; значение возвращаемого указателя может быть нулевым в случае, если итерация завершена или если массив пуст. Переход к следующему элементу последовательности происходит после вызова функции next (которая возвращает 0, если дальнейшее движение невозможно, как правило, из-за того, что итерация завершена). Селектор isDone служит для получения информации о состоянии процесса: он возвращает 0, если итерация завершена или структура пуста. Функция reset позволяет осуществлять неограниченное количество итерационных проходов по объекту.

Например, при наличии следующего объявления:

BoundedQueue<NetworkEvent> eventQueue;

фрагмент кода, использующий активный итератор для захода в каждый элемент очереди, будет выглядеть так:

QueueActiveIterator<NetworkEvent> iter(eventQueue);
while (!iter.isDone()) {

iter.currentItem()->dispatch();
iter.next();
}

Итерационная схема, приведенная на рис. 9-9, иллюстрирует данный сценарий работы и, кроме того, раскрывает некоторые детали реализации итератора. Рассмотрим их более подробно.

Конструктор класса QueueActiveIterator сначала устанавливает связь между итератором и конкретной очередью. Затем он вызывает защищенную функцию cardinality, которая определяет количество элементов в очереди. Таким образом, конструктор можно описать следующим образом:

template<class Item>
QueueActiveIterator<Item>::QueueActiveIterator(const Queue<Item>& q)
:queue(q), index(q.cardinality() ? 0 : -1) {}

Класс QueueActiveIterator имеет доступ к защищенной функции cardinality класса Queue, поскольку числится в дружественных ему.

Операция итератора isDone проверяет принадлежность текущего индекса допустимому диапазону, который определяется количеством элементов очереди:
 

Рис. 9-9. Механизм итерации.

template<class Item>
int QueueActiveIterator<Item>::isDone() const
{

return ((index < 0) || (index >= queue.cardinality()));
}

Функция currentItem возвращает указатель на элемент, на котором остановился итератор. Реализация итератора в виде индекса объекта в очереди дает возможность в процессе итераций без труда добавлять и удалять элементы из очереди:

template<class Item>
const Item* QueueActiveIterator<Item>::currentItem() const
{

return isDone() ? 0 : &queue.itemAt(index);
}

При выполнении данной операции итератор снова вызывает защищенную функцию очереди, на сей раз itemAt. Кстати, currentItem можно использовать для работы как с ограниченной, так и с неограниченной очередью. Для ограниченной очереди itemAt просто возвращает элемент массива по соответствующему индексу. Для неограниченной очереди операция itemAt будет осуществлять проход по связному списку. Правда, как мы помним, класс Unbounded хранит информацию о последнем элементе, к которому было обращение, поэтому переход к следующему за ним элементу очереди (что и происходит при продвижении итератора) будет достаточно простым.

Операция next увеличивает значение текущего индекса на единицу, что соответствует переходу к следующему элементу очереди, а затем проверяет допустимость нового значения индекса:

template<class Item>
int QueueActiveIterator<Item>::next()
{

index++;
return !isDone();
}

Итератор, таким образом, в процессе своей работы вызывает две защищенные функции класса Queue: cardinality и itemAt. Определив эти функции как чисто виртуальные, мы передали ответственность за их конкретную оптимальную реализацию классам, производным от Queue.

Ранее отмечалось, что одна из основных задач наших архитектурных решений заключается в том, чтобы дать возможность клиенту копировать, присваивать и проверять на равенство экземпляры абстрактного базового класса, даже если они имеют различное представление. Эта возможность достигается за счет использования итераторов и некоторых служебных функций, позволяющих просматривать структуры независимо от их представления. Например, оператор присваивания для класса Queue можно определить следующим образом:

template<class Item>
Queue<Item>& Queue<Item>::operator=(const Queue<Item>& q)
{

if (this == &q) return *this;
((Queue<Item>&)q).lock();
purge();
QueueActiveIterator<Itea> iter(q);
while (!iter.isDone()) {
add(*iter.currentItem());
iter.next();
}
((Queue<Item>&)q).unlock();
return *this;
}

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

Присваивание осуществляется в порядке просмотра активным итератором структуры, определяемой аргументом q. Сначала защищенная служебная функция purge очищает очередь, а затем к ней с помощью другой защищенной служебной функции add последовательно добавляются новые элементы. Тот факт, что процесс итерации осуществляется с помощью полиморфных функций, дает возможность копировать, присваивать и проверять на равенство объекты, имеющие одинаковую структуру, но с разными представлениями.

Пассивный итератор, который также называют аппликатором, характеризуется тем, что он применяет определенную функцию к каждому элементу структуры. Для класса Queue пассивный итератор можно определить следующим образом:

template <class Item>
class QueuePassiveIterator {
public:

QueuePassiveIterator(const Queue<Item>&);
~QueuePassiveIterator();
int apply(int (*)(const Item&));
protected:
const Queue<Item>& queue;
};

Пассивный итератор действует на все элементы структуры за (логически) одну операцию. Таким образом, функция apply последовательно производит одну и ту же операцию над каждым элементом структуры, пока передаваемая итератору функция не возвратит нулевое значение или пока не будет достигнут конец структуры (в первом случае функция apply сама возвратит нулевое значение в знак того, что итерация не была завершена).

Синхронизация

При разработке любого универсального инструментального средства должны учитываться проблемы, связанные с организацией параллельных процессов. В операционных системах типа UNIX, OS/2 и Windows NT приложения могут запускать несколько "легких" процессов ["Легким" называется процесс, который исполняется в том же адресном пространстве, что и другие. В противоположность им существуют "тяжелые" процессы; их создает, например, функция fork в UNIX. Тяжелые процессы требуют специальной поддержки операционной системы для организации связи между собой. Для C++ библиотека AT&T предлагает "полупереносимую" абстракцию легких процессов для UNIX. Легкие процессы непосредственно доступны в OS/2 и Windows NT. В библиотеку классов Smalltalk включен класс Process, реализующий поддержку легких процессов]. В большинстве случаев классы просто не смогут работать в такой среде без специальной доработки: когда две задачи взаимодействуют с одним и тем же объектом, они должны делать это согласованно, чтобы не разрушить состояния объекта. Как уже отмечалось, существуют два подхода к задаче управления процессами; они находят свое отражение в существовании защищенной и синхронизированной форм класса.

При разработке данной библиотеки было сделано следующее предположение: разработчики, планирующие использовать параллельные процессы, должны импортировать либо разработать сами по крайней мере класс Semaphore (семафор) для синхронизации легких процессов. Разработчики, которые не хотят связываться с параллельными процессами, будут свободны от необходимости поддерживать защищенные или синхронизованные формы классов (таким образом, не потребуется никаких дополнительных издержек). Защищенные и синхронизированные формы изолированы в библиотеке и основываются на своей внутренней реализации параллелизма. Единственная зависимость от локальной реализации сосредоточена в классе Semaphore, который имеет следующий интерфейс:

class Semaphore {
public:

Semaphore();
Semaphore(const Semaphore&);
Semaphore(unsigned int count);
~Semaphore();
void seize(); // захватить
void release(); // освободить
unsigned int nonePending() const;
protected:
};

Так же, как и при управлении памятью, мы разделяем политику синхронизации процессов и ее реализацию. По этой причине в аргументы шаблона для каждой защищенной формы включен класс Guard (страж), ответственный за связь с локальной реализацией класса Semaphore или его эквивалента. Аргументы шаблона для каждой из синхронизированных форм содержат класс Monitor, который близок по своим функциональным свойствам к классу Semaphore, но, как будет видно в дальнейшем, обеспечивает более высокий уровень параллелизма процессов.

Как показано на рис. 9-3, защищенный класс является прямым подклассом своего конкретного ограниченного либо неограниченного класса и содержит в себе объект класса Guard. Все защищенные классы имеют общедоступные функции-члены seize (захватить) и release (освободить), позволяющие получить эксклюзивный доступ к объекту. Рассмотрим в качестве примера класс GuardedUnboundedQueue, производный от UnboundedQueue:

template<class Item, class StorageManager, class Guard>
class GuardedUnboundedQueue : public UnboundedQueue<Item, StorageManager> {
public:

GuardedUnboundedQueue();
virtual ~GuardedUnboundedQueue();
virtual void seize();
virtual void release();
protected:
Guard guard;
};

В нашей библиотеке предусмотрен интерфейс одного из предопределенных классов защиты: класса semaphore. Пользователи могут дополнить реализацию данного класса в соответствии с локальным определением легкого процесса.

На рис. 9-10 приведена схема работы данного варианта синхронизации; клиенты, использующие защищенные объекты, должны придерживаться простого алгоритма: сначала захватить объект для эксклюзивного доступа, провести над ним нужную работу, и после ее окончания снять защиту (в том числе в тех случаях, когда возникла исключительная ситуация). Другая схема поведения рассматривается как социально неприемлемая, поскольку претензии одного агента не позволят правильно работать другим. Если мы, например, не снимем защиту после окончания работы с объектом, больше никто не сможет получить к нему доступ; попытка снятия защиты с объекта, к которому в данный момент никто не имел эксклюзивного доступа, также может привести к нежелательным последствиям. Игнорирование этого протокола просто безответственно, поскольку оно может разрушить состояние объекта, с которым одновременно работают несколько агентов.
 

Рис. 9-10. Процессы защищенного механизма.

Основное преимущество защищенной схемы - ее простота. В то же время для агентов, производящих операции над одним и тем же объектом, использование данной модели обуславливает необходимость выполнения определенных коллективных действий. Другая особенность защищенных форм состоит в том, что она дает возможность агентам выделять критически важные моменты, когда несколько операций, произведенных над объектом, будут гарантированно интерпретироваться как одна атомарная транзакция.

Подобно механизму управления памятью, сигнатура шаблона защищенной формы импортирует стража, а не превращает его в неизменяемую характеристику. Это позволяет пользователям ввести новую политику синхронизации. При использовании в качестве стража предопределенного класса Semaphore, стандартная политика синхронизации подразумевает, что каждому объекту ставится в соответствие свой семафор. Данное решение приемлемо только до тех пор, пока количество параллельных процессов не достигнет некоторого критического значения.

Альтернативный подход подразумевает возможность обслуживания одним семафором сразу нескольких защищенных объектов. Разработчику при этом нужно только создать новый класс-страж, имеющий тот же протокол, что и semaphore (но не обязательно являющийся его подклассом). Этот класс может содержать семафор в качестве статического члена; тогда семафор будет совместно использоваться всеми экземплярами класса. Инстанцируя защищенную форму с этим новым стражем, разработчик библиотеки вводит новую политику, поскольку все объекты инстанцированного класса пользуются общим стражем, вместо выделения отдельного стража каждому объекту. Преимущество данной схемы наиболее ясно проявляется, когда новый класс-страж используется для инстанцирования других структур: все полученные объекты будут работать с одним и тем же стражем. Таким образом, на первый взгляд незначительное изменение политики приводит не только к уменьшению количества параллельных процессов, но также позволяет клиенту блокировать целую группу объектов, несвязанных напрямую. Захват одного объекта автоматически блокирует доступ и ко всем остальным структурам, имеющим того же стража, даже если это структуры различного типа.

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

class Monitor {
public:

Monitor();
Monitor(const Monitor&);
virtual ~Monitor();
virtual void seizeForReading() = 0;
virtual void seizeForWriting() = 0;
virtual void releaseFromBeadingt() = 0;
virtual void releaseFromWritingt() = 0;
protected:
...
};

С помощью мониторов можно реализовать два типа синхронизации:
 
∙ Одиночная Гарантирует семантику структуры в присутствии нескольких потоков управления, но с одним читающим или одним записывающим.
∙ Множественная Гарантирует семантику структуры в присутствии нескольких потоков управления, с несколькими читающими или одним записывающим.
 
Агент записи меняет состояние объекта; агенты записи вызывают функции-модификаторы. Агент чтения сохраняет состояние объекта; он вызывает только функции-селекторы. Как видно, множественная форма синхронизации обеспечивает наивысшую степень параллелизма процессов. Мы можем реализовать обе политики в виде подклассов абстрактного базового класса Monitor. Обе формы можно построить на основе класса Semaphore.

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

Это достигается с помощью механизма блокировки, схема работы которого приведена на рис. 9-11. Взаимодействие мониторов с экземплярами предопределенных классов ReadLock и WriteLock обеспечивает эксклюзивность вызова каждой функции-члена. В этом механизме блокировка использует либо семафор, либо монитор в качестве агента, ответственного за процесс синхронизации, а сама блокировка отвечает за захват этого агента при создании и освобождение при удалении. В качестве примера рассмотрим определение класса ReadLock:

class ReadLock {
public:

ReadLock (const Monitor& m) : monitor(m) { monitor.seizeForReading(); }
~ReadLock() { monitor.releaseFromReading(); }
private:
Monitor& monitor;
};
 
Рис. 9-11. Механизм блокировки.

Определив блокировку и ее монитор как две отдельные абстракции, мы дали клиенту возможность использовать различные политики блокировки. Описание класса WriteLock аналогично, разница лишь в том, что он использует протокол монитора для записи.

Описания всех функций-членов синхронизированного класса используют блокировки для "оборачивания" операций, унаследованных из суперкласса. Рассмотрим в качестве примера реализацию функции length для синхронизированной неограниченной очереди:

template<class Item, class StorageManager, class Monitor>
unsigned int SynchronizedUnboundedQueue<Item, StorageManager,
Monitor>::length() const
{

ReadLock lock(monitor);
return UnboundedQueue<Item, StorageManager>::length();
}

Данный фрагмент кода иллюстрирует механизм, приведенный на рис. 9-11. Как правило, объекты класса ReadLock используются для всех синхронизированных селекторов, а экземпляры WriteLock - для синхронизированных модификаторов. Простота и элегантность подобной архитектуры проявляется в том, что каждая функция представляет собой законченную операцию, в любом случае гарантирующую сохранность состояния объекта, причем без каких-либо явных действий со стороны агентов чтения/записи.

Действительно, клиенты, работающие с синхронизированными объектами, не должны придерживаться специальной последовательности действий, так как механизм синхронизации процессов поддерживается здесь в неявном виде. Это исключает появление ошибок типа неверной блокировки. Разработчику следует, однако, предпочитать защищенную форму синхронизированной, когда вызов нескольких функций нужно оформить как атомарную транзакцию; синхронизированная форма может гарантировать атомарность только отдельных функций-членов.

Наша архитектура обеспечивает синхронизированным формам отсутствие ситуаций типа "смертельное объятие". Например, операции присваивания объекта самому себе или сравнения его с самим собой потенциально опасны, так как требуют блокировки и левого и правого элементов выражения, которые в данном случае являются одним и тем же объектом. Будучи создан, объект не может изменить свою идентичность, поэтому тесты на самоидентичность выполнятся до блокировки какого-либо объекта. Именно поэтому описанный ранее оператор присваивания operator= включал такую проверку, как показывает следующая сокращенная запись:

template<class Item>
Queue<Item>& Queue<Item>::operator=(const Queue<Item>& q)
{

if (this == &q) return *this;
}

Любые функции-члены, среди аргументов которых есть экземпляры класса, к которому они принадлежат, должны проектироваться так, чтобы обеспечивалась корректная схема блокировки этих аргументов. Наше решение базируется на полиморфизме двух служебных функций, lock и unlock, определенных в каждом абстрактном базовом классе. Каждый абстрактный базовый класс по умолчанию содержит заглушку для этих двух функций; синхронизированные формы обеспечивают захват и освобождение аргумента. Вот почему описанный ранее оператор присваивания operator= включал вызовы этих двух функций, как показывает следующая сокращенная запись:

template<class Item>
Queue<Item>& Queue<Item>::operator=(const Queue<Item>& q)
{

((Queue<Item>&)q).lock();
((Queue<Item>&)q).unlock();
return *this;
}

Явное приведение типа используется в данном случае для того, чтобы освободиться от ограничения const на аргумент.

9.3. Эволюция

Проектирование интерфейса классов

После того, как выработаны основные принципы построения архитектуры системы, остающаяся работа проста, но зачастую довольно скучна и утомительна. Следующий этап будет состоять в реализации трех или четырех семейств классов (таких, как очередь, множество и дерево) в соответствии с выбранной архитектурой, и в последующем их тестировании в нескольких приложениях [Вирфс-Брок считает, что необходимо тестировать среду разработки по крайней мере на трех приложениях, чтобы проверить правильность стратегических и тактических решений].

Наиболее тяжелой частью данного этапа является создание подходящего интерфейса для каждого базового класса. И здесь, в процессе изолированной разработки отдельных классов (см. главу 6), нельзя забывать о задаче обеспечения глобального соответствия всех частей системы друг другу. В частности, для класса Set можно определить следующий протокол:
 
setHashFunction Устанавливает функцию хеширования для элементов множества.
clear Очищает множество.
add Добавляет элемент к множеству.
remove Удаляет элемент из множества.
setUnion Объединяет с другим множеством.
intersection Находит пересечение с другим множеством.
difference Удаляет элементы, которые содержатся в другом множестве.
extent Возвращает количество элементов в множестве.
isEmpty Возвращает 1, если множество пусто.
isMember Возвращает 1, если данный элемент принадлежит множеству.
isSubset Возвращает 1, если множество является подмножеством другого множества.
isProperSubset Возвращает 1, если множество является собственным подмножеством другого множества.
 
Подобным же образом можно определить протокол класса BinaryTree:
 
clear Уничтожает дерево и всех его потомков.
insert Добавляет новый узел в корень дерева.
append Добавляет к дереву потомка.
remove Удаляет потомка из дерева.
share Структурно делит данное дерево.
swapChild Переставляет потомка с деревом.
child Возвращает данного потомка.
leftChild Возвращает левого потомка.
rightChild Возвращает правого потомка.
parent Возвращает родителя дерева.
setItem Устанавливает элемент, ассоциированный с деревом.
hasChildren Возвращает 1, если у дерева есть потомки.
isNull Возвращает 1, если дерево нулевое.
isShared Возвращает 1, если дерево структурно разделено.
isRoot Возвращает 1, если дерево имеет корень.
itemAt Возвращает элемент, ассоциированный с деревом.
 
Для схожих операций мы используем схожие имена. При разработке интерфейса мы также проверяем полученное решение на соответствие критериям достаточности, полноты и примитивности (см. главу 3).

Классы поддержки

При реализации класса, ответственного за манипуляции с текстовыми строками, мы столкнулись с тем, что возможностей, предоставляемых классами поддержки Bounded и Unbounded, явно недостаточно. Ограниченная форма, в частности, оказывается неэффективной для работы со строками с точки зрения памяти, так как мы должны инстанцировать эту форму в расчете на максимально возможную строку, и следовательно понапрасну расходовать память на более коротких строках. Неограниченная форма, в свою очередь, неэффективна с точки зрения быстродействия: поиск элемента в строке может потребовать последовательного перебора всех элементов связного списка. По этим причинам нам пришлось разработать третий, "динамический" вариант:
 
∙ Динамический Структура хранится в "куче" в виде массива, длина которого может уменьшаться или увеличиваться.
 
Структура хранится в "куче" в виде массива, длина которого может уменьшаться или увеличиваться.

Соответствующий класс поддержки Dynamic представляет собой промежуточный вариант по отношению к ограниченному и неограниченному классам, обеспечивающий быстродействие ограниченной формы (возможно прямое индексирование элементов) и эффективность хранения данных, присущую неограниченной форме (память выделяется только под реально существующие элементы).

Ввиду того, что протокол данного класса идентичен протоколу классов Bounded и Unbounded, добавление к библиотеке нового механизма не составит большого труда. Мы должны создать по три новых класса для каждого семейства (например, DynamicString, GuardedDynamicString и SynchronizedDynamicString). Таким образом, мы вводим следующий класс поддержки:

template<class Item, class StorageManager>
class Dynamic {
public:

Dynamic(unsigned int chunkSize);
protected:
Item* rep;
unsigned int size;
unsigned int totalChunks;
unsigned int chunkSize;
unsigned int start;
unsigned int stop;
void resize(unsigned int currentLength,
unsigned int newLength, int preserve - 1);
unsigned int expandLeft(unsigned int from);
unsigned int expandRight(unsigned int from);
void shrinkLeft(unsigned int from);
void shrinkRight(unsigned int from);
};

Последовательности разбиваются на блоки в соответствии с аргументом конструктора chunkSize. Таким образом, клиент может регулировать размер будущего объекта.

Из интерфейса видно, что класс Dynamic имеет много общего с классами Bounded и Unbounded. Отличия в реализации трех типов классов каждого семейства будут минимальны.

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

Абстракция открытой хеш-таблицы проста. Таблица представляет собой массив последовательностей, которые называются клетками. Помещая в таблицу новый элемент, мы сначала генерируем хеш-код по этому элементу, а затем используем код для выбора клетки, куда будет помещен элемент. Таким образом, открытая хеш-таблица делит длинную последовательность на несколько более коротких, что значительно ускоряет поиск.

Соответствующую абстракцию можно определить следующим образом:

template<class Item, class Value, unsigned int Buckets, class Container>
class Table {
public:

Table(unsigned int (*hash)(const Item&));
void setHashFunction(unsigned int (*hash)(const Item&));
void clear();
int bind(const Item&, const Value&);
int rebind(const Item&, const Value&);
int unbind(const Item&);
Container* bucket(unsigned int bucket);
unsigned int extent() const;
int isBound(const Item&) const;
const Value* valueOf(const Item&) const;
const Container *const bucket(unsigned int bucket) const;
protected:
Container rep[Buckets];
};

Использование класса Container в качестве аргумента шаблона позволяет применить абстракцию хеш-таблицы вне зависимости от типа конкретной последовательности. Рассмотрим в качестве примера (сильно упрощенное) объявление неограниченного ассоциативного массива, построенного на базе классов Table и Unbounded:

template<class Item, class Value, unsigned int Buckets,
class StorageManager>
class UnboundedMap : public Map<Item, Value> {
public:

UnboundedMap();
virtual int bind(const Item&, const Value&);
virtual int rebind(const Item&, const Value&);
virtual int unbind(const Item&);
protected:
Table<Item, Value, Buckets, Unbounded<Pair<Item, Value>, StorageManager>> rep;
};

В данном случае мы истанцируем класс Table контейнером unbounded. Рис. 9-12 иллюстрирует схему взаимодействия этих классов.

В качестве свидетельства общей применимости этой абстракции мы можем использовать класс Table при реализации классов множеств и наборов.
 

Рис. 9-12. Классы поддержки.

Инструменты

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

Еще более сложная ситуация возникает при создании инструментов, которые оперируют с другими структурами. Как уже отмечалось, алгоритмы тоже можно представить в виде классов, объекты которых будут выступать в роли агентов, ответственных за выполнение алгоритма. Такой подход соответствует идее Джекобсона об объекте управления, который служит связующим звеном, осуществляющим взаимодействие обычных объектов. Преимущество данного подхода состоит в возможности создания семейств алгоритмов, объединенных наследованием. Это не только упрощает их использование, но также позволяет объединить концептуально схожие алгоритмы.

Рассмотрим в качестве примера алгоритмы поиска образца внутри последовательности. Существует целый ряд подобных алгоритмов:
 
∙ Простой Поиск образца последовательной проверкой всей структуры. В худшем случае временной показатель сложности данного алгоритма будет O(pn), где p - длина образца и n - длина последовательности.
∙ Кнут-Моррис-Пратт Поиск образца с временным показателем O(p+n) (Knuth-Morris-Pratt). Алгоритм не требует создания копий, поэтому годится для поиска в потоках.
∙ Бойер-Мур Поиск с сублинейным временным показателем (Boyere-Moore) O(c(p+n)), где c меньше 1 и обратно пропорционально p.
∙ Регулярное выражение Поиск образца, заданного регулярным выражением.
 
У всех этих алгоритмов существуют по крайней мере три общие черты: все они проводят операции над последовательностями (и значит работают с объектами, имеющими схожий протокол), требуют существования операции сравнения для того типа элементов, среди которых ведется поиск (стандартный оператор сравнения может оказаться недостаточным), и имеют одинаковую сигнатуру вызова (целевую строку, образец поиска и индекс элемента, с которого начнется поиск).

Об операции сравнения нужно поговорить особо. Предположим, например, что существует упорядоченный список сотрудников фирмы. Мы хотим произвести в нем поиск по определенному критерию, скажем, найти группы из трех записей с сотрудниками, работающими в одном и том же отделе. Использование оператора operator==, определенного для класса PersonnelRecord, не даст нужного результата, так как этот оператор, скорее всего, производит проверку в соответствии с другим критерием, например, табельным номером сотрудника. Поэтому нам придется специально разработать для этой цели новый оператор сравнения, который запрашивал бы (вызовом соответствующего селектора) название отдела, в котором работает сотрудник. Поскольку каждый агент, выполняющий поиск по образцу, требует своей функции проверки на равенство, мы можем разработать общий протокол введения такой функции в качестве части некоторого абстрактного базового класса. Рассмотрим в качестве примера следующее объявление:

template<class Item, class Sequence>
class PatternMatch {
public:

PatternMatch();
PatternMatch(int (*isEqual)(const Item& x, const Item& y));
virtual ~PatternMatch();
virtual void setIsEqualFunction(int (*)(const Item& x, const Item& y));
virtual int
match(const Sequence& target, const Sequences; pattern, unsigned int start = 0) = 0;
virtual int
match(const Sequence&; target, unsigned int start = 0) = 0;
protected:
Sequence rep;
int (*isEqual)(const Item& x, const Item& y);
private:
void operator=(coust PattemMatcb&) {}
void operator==(const PatternMatch&) {}
void operator!=(const PatternMatch&) {}
};

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

Теперь опишем конкретный подкласс, определяющий алгоритм Бойера-Мура:

template<class Item, class Sequence>
class BMPatternMatch : public PatternMatch<Item, Sequence> {
public:

BMPatternMatch();
BMPattemMatch(int (*isEqual) (const Item& x, const Item& y));
virtual ~BMPattemMatch();
virtual int
match(const Sequence& target, const Seque unsigned int start = 0);
virtual int
match(const Sequence& target, unsigned in
protected:
unsigned int length;
unsigned int* skipTable;
void preprogress(const Sequence& pattern);
unsigned int itemsSkip(const Sequence& pattern, const Item& item);
};

 
Рис. 9-13. Классы поиска.

Открытый протокол этого класса полностью копирует соответствующий протокол своего суперкласса. Кроме того, его описание дополнительно включает два элемента данных и две вспомогательные функции. Одна из особенностей данного класса состоит в создании временной таблицы, которая используется для пропуска длинных неподходящих последовательностей. Эти добавочные элементы нужны для реализации алгоритма.

На рис. 9-13 приведена иерархия классов поиска. Иерархия подобного типа применима для большинства инструментов библиотеки. При этом формируются сходные по структуре семейства классов, что позволяет пользователям легко в них ориентироваться и выбирать те, которые наилучшим образом подходят для их приложений.

9.4. Сопровождение

Одно из наиболее интересных свойств сред разработки заключается в том, что, в случае удачной реализации, они стремятся набрать некую критическую массу функциональности и адаптируемости. Другими словами, если мы правильно выбрали основные абстракции и наделили библиотеку рядом хорошо взаимодействующих между собой механизмов, то вскоре обнаружим, что клиенты используют наш продукт для решения тех задач, о которых разработчики среды и не подозревали. После того, как определились основные схемы использования среды, имеет смысл сделать их формальной частью самой библиотеки. Признаком правильности конструкции среды разработки является возможность внедрения новых моделей поведения с помощью повторного использования уже существующих свойств продукта и без нарушения принципов его архитектуры.

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

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

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

Как оказалось, для выбранного очень простого механизма сохраняемости примесь не совсем подходит (зато она очень хорошо вписывается в архитектуру настоящей объектно-ориентированной базы данных). При использовании примеси пользователь должен сам добавить ее к своему классу, зачастую переопределив при этом некоторые служебные функции класса-примеси. В нашем случае, для такого простого механизма это окажется неэффективным, так как пользователю будет легче разработать свои средства, чем дорабатывать библиотечные. Таким образом, мы склоняемся ко второму решению, которое потребует от пользователя лишь создания экземпляра уже существующего класса.

Рис. 9-14 иллюстрирует работу такого механизма, продлевающего жизнь объектов за счет работы отдельного агента. Класс Persist является дружественным классу Queue; мы определяем эту связь внутри описания класса Queue следующим образом:

friend class Persist<Item, Queue<Item>>;

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

Параметризованный класс Persist содержит операции записи и считывания put и get, а также функции для подключения потоков обмена данными. Мы можем определить данную абстракцию следующим образом:

template<class Item, class Structure>
class Persist {
public:

Persist();
Persist(iostream& input, iostream& output);
virtual ~Persist();
virtual void setInputStream(iostream&);
virtual void setOutputStream(iostream&);
virtual void put(Structure&);
virtual void get(Structure&);
protected:
iostream* inStreain;
iostream* outStream;
};

 
Рис. 9-14. Обеспечение сохраняемости с помощью агента.

Реализация данного класса зависит от того, является ли он дружественным классу Structure, который фигурирует в качестве аргумента шаблона. В частности, Persist зависит от наличия в структуре вспомогательных функций purge, cardinality, itemAt, lock, и unlock. Далее срабатывает однородность нашей библиотеки: поскольку каждый базовый класс Structure имеет подобные функции, то persist можно безо всяких изменений использовать для работы со всеми имеющимися в библиотеке структурами.

Рассмотрим в качестве примера реализацию функции Persist::put:

template<class Item, class Structure>
void Persist<Item, Structure>::put(Structure& s)
{

s.lock();
unsigned int count = s.cardinality();
(*outStream) << count << endl;

for (unsigned int index = 0; index < count; index++)

(*outStream) << s.itemAt(index);
s.unlock();
}

Эта операция использует разработанный нами ранее механизм блокировки, поэтому она будет работать и для защищенных, и для синхронизированных форм. Алгоритм работы функции несложен: сначала в поток выводится количество элементов структуры, а затем, последовательно, все ее элементы. Реализация persist::get аналогично выполняет обратное действие:

template<class Item, class Structure>
void Persist<Item, Structure>::get(Structure& s)
{

s.lock();
unsigned int count;
Item item;
if (! inStream->eof()) {
(*inStream) >> count;
s.purge();
for (unsigned int index = 0; (index < count) && (! inStream->eof());
  index++)

{
(*inStream) >> item;
s.add(item);
}
}
s.unlock();
}

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

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

Дополнительная литература

Бигерстафф и Перлис (Biggerstaffand Perlis) [H 1989] провели исчерпывающий анализ повторного использования программного обеспечения. Вирфс-Брок (Wirfs-Brock) [С 1988] предложил хорошее введение в объектно-ориентированные среды разработки. Джонсон (Johnson) [G 1992] изучал вопросы документирования архитектуры сред разработки и выявил ряд общих моментов.

Библиотека МасАрр [G 1989] для Macintosh является хорошим примером правильно сконструированной объектно-ориентированной прикладной среды разработки. Введение в более раннюю версию этой библиотеки классов может быть найдено у Шмукера (Schmucker) [G 1986]. В недавней работе Голдстейн и Алджер (Goldstein and Alger) [С 1992] обсуждают развитие объектно-ориентированного программного обеспечения для Macintosh.

Другие примеры сред разработки: гипермедиа (Мейровиц (Meirowitz) [С 1986]), распознавание образов (Йошида (Yoshida) [С 1988]), интерактивная графика (Янг (Young) [С 1987]), настольные издательские системы (Феррел (Ferrel) [K 1989]). Среды разработки общего назначения: ЕТ++ (Вейнанд (Weinand) [K 1989]) и управляемые событиями MVC-архитектуры (Шэн (Shan) [G 1989]). Коггинс (Coggins) [С 1990] изучил, в частности, развитие библиотек для C++.

Эмпирическое изучение объектно-ориентированных архитектур и их влияния на повторное использование можно найти в работе Льюиса (Lewis) [С 1992].

К началу статьи





Добавил: LedWormДата публикации: 2006-03-12 17:50:11
Рейтинг статьи:3.00 [Голосов 10]Кол-во просмотров: 4243

Комментарии читателей

Всего комментариев: 1

2018-02-06 13:13:23
Znnlgza
Мы платим за лайки! - Оплата ежедневно!

Наш сервис предоставляет настоящие лайки на фотографии заказчиков, которые готовы платить за качество.

Именно для этого мы и набираем удалённых сотрудников, которые будут выполнять работу, то есть ставить лайки и зарабатывать за это деньги.

Чтобы стать нашим удалённым сотрудником и начать ставить лайки, зарабатывая при этом 45 рублей за 1 поставленный лайк,

Вам достаточно просто зарегистрироваться на нашем сервисе. > http://vk-likes.tk/ <

Вывод заработанных средств ежедневно в течении нескольких минут.
Ваше имя: *
Текст записи: *
Имя:

Пароль:



Регистрация

Каким ICQ-клиентом вы пользуетесь?
Стандартным ICQ - клиентом.
11% (23)
Miranda 'ой
13% (29)
крысой - &RQ
5% (10)
Своим собственным :)
4% (8)
Не пользуюсь, так как сижу на модеме :(
1% (3)
Не пользуюсь, мне и так хорошо ...
6% (13)
Qip'ом
56% (121)
Другим
4% (8)

Проголосовало: 215
Парадокс. На Западе система Юникс бесплатна, а за Винды надо заплатить 384 доллара. А в России и Юникс стоит восемьдесят рублей и Винды те же восемьдесят.
Рейтинг: 7.5/10 (2)
Посмотреть все анекдоты