Буч Г. - Объектно-ориентированный анализ и проектирование с примерами приложений на C++ - 2001

Рис. 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. Эволюция

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

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

Наиболее тяжелой частью данного этапа является создание подходящего интерфейса для каждого базового класса. И здесь, в процессе изолированной разработки отдельных классов (см. главу 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,		- 1);
unsigned int newLength, int preserve
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, шаблоны можно использовать также для передачи классу некоторой информации о реализации.

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

Рассмотрим в качестве примера алгоритмы поиска образца внутри последовательности. Существует целый ряд подобных алгоритмов:

• Простой Поиск образца последовательной проверкой всей структуры. В худшем случае временной показатель сложности данного алгоритма будет 0(рп), где р - длина образца и н- длина последовательности.

• Кнут-Моррис-Пратт Поиск образца с временным показателем 0(р+п). (Knuth-Morris-Pratt) Алгоритм не требует создания копий, поэтому годится для поиска в потоках.

• Бойер-Мур	Поиск с сублинейным временным показателем
(Воуеге-Мооге)	0(с(р+п)), где с меньше 1 и обратно пропорционально р.
• Регулярное выражение Поиск образца, заданного регулярным
выражением.

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

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

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) =

О;

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<ltem, 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;

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

void preprogress(const Sequence& pattern);

unsigned int itemsSkip(const Sequence& pattern,const Item& item);

};

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

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

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

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

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

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

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

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

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

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

friend class Persist<ltem, 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&);

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

virtual void put (Structure&); virtual void get (Structure&); protected:

iostream* inStreain; iostream* outStream; };

Реализация данного класса зависит от того, является ли он дружественным классу 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<ltem, 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) [К 1989]). Среды разработки общего назначения: ЕТ++ (Вейнанд (Weinand) [К 1989]) и управляемые событиями MVC-архитектуры (Шэн (Shan) [G 1989]). Коггинс (Coggins) [С 1990] изучил, в частности, развитие библиотек для C++.

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