9.2. Проектирование
9.2. Проектирование
Тактические вопросы
В соответствии с законом разработки программ Коггинса "прагматизм всегда должен быть предпочтительней элегантности, ведь Природу все равно ничем не удивить". Следствие: проектирование никогда не будет полностью независимым от языка реализации проекта. Особенности языка неизбежно наложат отпечаток на те или иные архитектурные решения, и их игнорирование может привести к тому, что нам придется работать в дальнейшем с абстракциями, не в полной мере учитывающими преимущества и недостатки конкретного языка реализации.
Как было отмечено в главе 3, объектно-ориентированные языки предоставляют три основных механизма упорядочения большего числа классов: наследование, агрегацию и параметризацию. Наследование является наиболее популярным свойством объектно-ориентированной технологии, однако далеко не единственным принципом структурирования. Как мы увидим, сочетание параметризации с наследованием и агрегацией помогает создать достаточно мощную и в то же время компактную архитектуру.
Рассмотрим усеченное описание предметно-зависимого класса очереди в C++:
class NetworkEvent... // сетевое событие
class EventQueue { // очередь событий public:
EventQueue(); virtual ~EventQueue(); virtual void clear(); // очистить virtual void add(const NetworkEvent&); // добавить virtual void pop(); // продвинуть virtual const NetworkEvent& front() const; // первый элемент
... };
Перед нами абстракция, олицетворяющая очередь событий: структура, в которую мы можем добавлять новые элементы в конец очереди и удалять элементы из начала очереди. C++ позволяет скрыть внутренние детали реализации класса очереди за его внешним интерфейсом (операциями clear, add, pop и front ).
Нам могут потребоваться также некоторые другие варианты очереди, например, приоритетная очередь, где события выстраиваются в соответствии с их срочностью. Разумно воспользоваться результатами уже проделанной работы и организовать новый класс на базе ранее определенного:
class PriorityEventQueue : public EventQueue { public:
PriorityEventQueue(); virtual ~PriorityEventQueue(); virtual void add(const NetworkEvent&);
... };
Виртуальность функций (например функции add) поощряет переопределение операций в подклассах.
Комбинация наследования с параметризованными классами позволяет создавать еще более общие абстракции. Семантика класса очереди не зависит от того, что в ней: волки или овцы. Используя классы-шаблоны, можно переопределить наш базовый класс следующим образом:
template<class Item> class Queue { public:
Queue(); virtual ~Queue(); virtual void clear(); virtual void add(const Item&); virtual void pop(); virtual const Item& front() const;
... };
Это наиболее распространенный способ использования параметризованных классов: взять существующий конкретный класс, выделить в нем то, что не зависит от элементов, с которыми он оперирует, и сделать эти элементы аргументами шаблона.
Наследование и параметризация очень хорошо сочетаются. Наш подкласс PriorityQueue можно, например, обобщить следующим образом:
template<class Item> class PriorityQueue : public Queue<Item> { public:
PriorityQueue(); virtual ~PriorityQueue(); virtual void add(const Item&);
... };
Безопасность с точки зрения типов - ключевое преимущество данного подхода. Мы можем создать целый ряд различных классов конкретных очередей:
Queue<char> characterQueue; typedef Queue<MetworkEvent> EventQueue; typedef PriorityQueue<NetworkEvent> PriorityEventQueue;
Рис. 9-1. Наследование и параметризация.
При этом язык реализации не позволит нам присоединить событие к очереди символов, а вещественное число - к очереди событий.
Рис. 9-1 иллюстрирует отношения между параметризованным классом (Queue), его подклассом (PriorityQueue), примером этого подкласса (PriorityEventQueue) и одним из его экземпляров (mailQueue).
Этот пример подтверждает правильность одного из самых первых наших архитектурных решений: почти все классы нашей библиотеки должны быть параметризованными. Тогда будет выполнено и требование защищенности.
Макроорганизация
Как уже отмечалось в предыдущих главах, классы есть необходимое, но не достаточное средство декомпозиции системы. Это замечание в полной мере касается и библиотеки классов. Неупорядоченный набор классов, в котором разработчики копаются в поисках чего-либо полезного, - едва ли не худшее из возможных решений. Лучше разбить классы на отдельные категории (рис. 9-2). Такое решение позволяет удовлетворить требованию простоты библиотеки.
При первом взгляде на проблемную область легко заметить, что мы могли бы воспользоваться общими функциональными свойствами классов. Поэтому заведем общедоступную категорию Support (поддержка) для абстракций низкого уровня и классов, поддерживающих общие механизмы библиотеки.
Это наблюдение приводит нас ко второму принципу архитектуры библиотеки: четкое разделение между политикой и реализацией. Такие абстракции, как очереди, множества и кольца, отражают политику использования низкоуровневых структур: связных списков или массивов. Очередь, например, выражает политику, при которой можно только удалять элементы из начала структуры и добавлять элементы к ее концу. Множество, с другой стороны, не представляет никакой политики, требующей упорядочения элементов. Кольцо требует упорядочения, но предполагает, что начальный и конечный элемент соединены. К категории Support мы будем относить простые абстракции - те, над которыми надстраивается политика.
Поместив эту категорию классов в код библиотеки, мы поддерживаем библиотечное требование расширяемости. Основная масса разработчиков, может быть, и не будет использовать классы из Support. Однако разработчики библиотек и более продвинутые программисты смогут задействовать базовые абстракции из Support для конструирования новых классов или модификации поведения существующих.
Рис. 9-2. Категории классов в библиотеке.
Как видно из рис. 9-2, библиотека организована не в виде дерева, а в виде леса классов; здесь не существует единого базового класса, как этого требуют языки типа Smalltalk.
На рисунке этого не видно, но на самом деле классы категорий Graphs, Lists и Trees несколько отличаются от других структурных классов. Еще раньше мы отмечали, что абстракции типа деки и стека являются монолитными. С монолитной структурой можно иметь дело только как с единым целым: ее нельзя разбить на отдельные идентифицируемые компоненты, и таким образом гарантируется ссылочная целостность. С другой стороны, в композитной структуре (такой как граф) структурное разделение допускается. В ней мы можем, например, получать доступ к подспискам, ветвям дерева, отдельным вершинам или ребрам графа. Фундаментальное различие между этими двумя категориями структур лежит в семантике операций копирования, присваивания и сравнения. Для монолитных абстракций подобные операции можно назвать "глубокими", а для композитных абстракций - "поверхностными", в том смысле, что при копировании происходит передача ссылки на часть общей структуры.
Семейства классов
Третий основной принцип проектирования библиотеки заключается в построении семейств классов, связанных отношением наследования. Для каждого типа структур мы создадим несколько различных классов, объединенных единым интерфейсом (как в случае с абстрактным классом Queue), но с разными конкретными подклассами, имеющими несколько различные представления и поэтому отличающимися Своим устройством и характеристиками "время/память". Таким образом мы обеспечим библиотечное требование полноты. Разработчик сможет выбрать тот конкретный класс, который в большей степени подходит для решения его задачи. В то же время этот класс обладает тем же интерфейсом, что и остальные классы семейства. Сознательное четкое разделение абстрактного базового класса и его конкретных подклассов позволяет пользователю системы выбрать, скажем, на первом этапе проектирования один из классов в качестве рабочего, а затем, в процессе доводки приложения, заменить его на другой, чем-то отличающийся класс того же семейства, затратив на это минимум времени и усилий (единственное, что ему потребуется, - это заново оттранслировать свою программу). При этом разработчик будет уверен в нормальном функционировании программы, так как все классы, принадлежащие одному семейству, обладают идентичным внешним интерфейсом и схожим поведением. Смысл в такой организации классов состоит еще и в возможности копирования, присваивания и сравнения объектов одного семейства даже в том случае, если их представления совершенно разнятся.
Можно сказать, что базовый абстрактный класс как бы содержит в себе все важные черты абстракции. Другое важное применение абстрактных базовых классов - это кэширование общего состояния, которое дорого вычислять заново. Так можно перевести вычисление O(n) в операцию порядка O(1) - простое считывание данных. При этом, естественно, требуется обеспечить соответствующий механизм взаимодействия между абстрактным базовым классом и его подклассами, чтобы гарантировать актуальность кэшируемого значения.
Элементы семейства классов представляют собой различные формы абстракции. Опыт показывает, что существуют две основные формы абстракций, которыми следует пользоваться разработчику при создании серьезных приложений. Во-первых, это форма конкретного представления абстракции в оперативной памяти машины. Существует два варианта такого представления: выделение памяти для структуры из стека или выделение оперативной памяти из кучи. Им соответствуют две формы абстракций: ограниченная и неограниченная:
? Ограниченная Структура хранится в стеке и, таким образом, имеет статический размер (известный в момент создания объекта).
? Неограниченная Структура хранится в куче и ее размеры могут динамически изменяться.
Так как ограниченная и неограниченная формы абстракции имеют общие интерфейс и поведение, их обе можно представить в виде прямых подклассов абстрактного базового класса для каждой структуры. Мы обсудим эти и другие особенности организации данных в следующих разделах.
Второй вариант связан с синхронизацией. Как было отмечено в главе 2, множество полезных приложений обходятся одним процессом. Их называют последовательными системами, потому что они используют один поток управления. Для других приложений (особенно это касается систем реального времени) требуется обеспечить синхронизацию нескольких одновременно выполняемых потоков. Такие системы называются параллельными, и в них каким-то образом должно обеспечиваться взаимное исключение процессов, конкурирующих за один и тот же ресурс. Ясно, что нельзя дать возможность управлять одним и тем же объектом одновременно нескольким потокам, это в конце концов приведет к нарушению его состояния. Рассмотрим, например, поведение двух агентов, которые одновременно пытаются добавить элемент одному и тому же объекту класса Queue. Первый агент, начавший добавление элемента, может быть прерван раньше, чем окончит данную операцию, и оставит объект второму агенту в незавершенном состоянии.
Рис. 9-3. Семейства классов.
Как отмечалось в главе 3, в данном случае при проектировании существуют всего три возможных альтернативы, каждая из которых требует обеспечения различного уровня взаимодействия между агентами, оперирующими с общими объектами:
• последовательный;
• защищенный;
• синхронизированный.
Мы рассмотрим каждый из этих вариантов более подробно в следующем разделе. Обеспечение взаимодействия между абстрактным базовым классом, формами его представления и формами синхронизации порождает для каждой структуры семейство классов, подобное тому, которое приведено на рис. 9-3. Теперь можно понять, почему мы в свое время решили организовать библиотеку именно в виде семейств классов, а не в виде единого дерева. Это было сделано из-за того, что такая архитектура:
• Отражает общность различных форм.
• Позволяет осуществлять более простой доступ к элементам библиотеки.
• Позволяет избежать бесконечных метафизических споров о "чистом объектно-ориентированном подходе".
• Упрощает интеграцию системы с другими библиотеками.
Микроорганизация
В целях обеспечения простоты работы с системой выберем один общий стиль оформления структур и механизмов библиотеки:
template<...> class Name : public Superclass { public:
// конструкторы // виртуальный деструктор // операторы // модификаторы // селекторы
protected:
// данные // функции
private:
// друзья
};
Описание абстрактного базового класса Queue начинается следующим образом:
template<class Item> class Queue {
Сигнатура шаблона template служит для задания аргументов параметризованного класса. Отметим, что в C++ шаблоны сознательно введены таким образом, чтобы передать достаточную гибкость (и ответственность) в руки разработчика, инстанцирующего шаблон в своем приложении.
Далее определим обычный список конструкторов и деструкторов:
Queue(); Queue(const Queue<Item>&); virtual ~Queue();
Отметим, что мы описали деструктор виртуальным, чтобы обеспечить полиморфное поведение при уничтожении объектов класса. Далее объявим все операторы:
virtual Queue<Item>& operator=(const Queue<Item>&); virtual int operator==(const Queue<Item>&) const; int operator!=(const Queue<Item>&) const;
Мы определили оператор присваивания (operator==) и оператор сравнения (operator==) как виртуальные для того, чтобы обеспечить безопасность типов. Переопределение этих операторов входит в обязанности подклассов. В них будут использоваться функции, аргументом которых является объект собственного специализированного класса. В этом смысле подклассы имеют то преимущество, что они знают представление своих экземпляров и могут обеспечить очень эффективную реализацию. Когда конкретный подкласс очереди неизвестен (например, если мы передаем объект по ссылке на его базовый класс), вызывается оператор базового класса, использующий может быть менее эффективные, но более универсальные алгоритмы. Эта идиома имеет побочный эффект: возможность работы одной и той же функции с очередями, имеющими различную внутреннюю реализацию, без нарушения типизации.
Если мы хотим ограничить доступ к копированию, присваиванию или сравнению некоторых объектов, нам надо объявить эти операторы защищенными или закрытыми.
Определим теперь модификаторы, позволяющие менять состояние объекта:
virtual void clear() = 0; virtual void append(const Item&) = 0; virtual void pop() =0; virtual void remove (unsigned int at) = 0;
Данные операции объявлены как чисто виртуальные, а это значит, что их описание является обязанностью подклассов. Наличие чисто виртуальных функций делает класс Queue абстрактным.
Спецификатор const указывает (компилятор может это проверить) на использование функций-селекторов, то есть функций, предназначенных исключительно для получения информации о состоянии объекта, но не для изменения состояния:
virtual unsigned int length() const = 0; virtual int isEmpty() const = 0; virtual const Item& front() const =0; virtual int location(const Item&) const = 0;
Эти операции тоже определены как чисто виртуальные, потому что класс Queue не обладает достаточной информацией для их полного описания.
Защищенная часть каждого класса начинается с описания тех элементов, которые формируют основу его структуры и должны быть доступны подклассам [Всюду, где веские причины не заставляют нас действовать по-другому, мы объявляем элементы класса закрытыми. Здесь, однако, существует веская причина объявить эти фрагменты защищенными: доступ к ним потребуется подклассам]. Абстрактный класс Queue, в. отличие от своих подклассов (см. ниже), подобных элементов не имеет.
Продолжит защищенную часть базового класса определение служебных функций, которые будут полиморфно реализованы в конкретных подклассах. Класс Queue содержит довольно типичный список таких функций:
virtual void purge() = 0; virtual void add(const Item&) = 0; virtual unsigned int cardinality() const = 0; virtual const Item& itemAt (unsigned int) const = 0; virtual void lock(); virtual void unlock();
Причины, по которым мы ввели именно эти функции, будут рассмотрены в следующем разделе.
И, наконец, определим закрытую часть, обычно содержащую объявления о классах-друзьях и те элементы, которые мы хотим сделать недоступными даже для подклассов. Класс Queue содержит только декларации о друзьях:
friend class QueueActiveIterator<Item>; friend class QueuePassiveIterator<Item>;
Как мы увидим в дальнейшем, эти объявления друзей понадобятся для поддержки идиом итератора.
Семантика времени и памяти
Из пяти основных принципов строения библиотеки базовых классов, возможно, наиболее важен механизм, обеспечивающий клиента альтернативной простанственно-временной семантикой внутри каждого семейства классов.
Рассмотрим тот спектр требований, который должен учитываться при разработке библиотеки общего назначения. На рабочей станции, обладающей большим виртуальным адресным пространством, пользователь скорее всего будет расточать память ради более высокого быстродействия. С другой стороны, в некоторых встроенных системах, таких, как спутник или автомобильный мотор, ресурсы памяти часто ограничены, и разработчик вынужден выбирать в качестве рабочих те абстракции, которые используют меньше памяти (например, выделяя место под данные в стеке, а не в "куче"). Ранее мы различили эти две возможности как ограниченную и неограниченную формы соответственно.
Неограниченные формы применимы в тех случаях, когда размер структуры не может быть предсказан, а выделение и утилизация памяти из кучи не приводит ни к потере времени, ни к снижению надежности (как это бывает в некоторых приложениях, критичных по времени) [Некоторые требования к системе могут запретить использование динамически распределяемой памяти. Рассмотрим сердечный импульсный регулятор и возможные фатальные результаты, которые может вызвать сборщик мусора, "проснувшийся" в неподходящий момент. Есть системы с длительным рабочим циклом: в них даже минимальная утечка памяти может дать серьезный кумулятивный эффект; вынужденная перезагрузка системы из-за недостатка памяти может привести к неприемлемой потере функциональности]. Ограниченные формы лучше подходят для работы с небольшими структурами, размер которых достаточно хорошо предсказуем. Учтем также, что динамическое выделение памяти менее терпимо к ошибкам программиста.
Таким образом, все структуры данной библиотеки должны присутствовать в альтернативных вариантах; поэтому нам придется создать два низкоуровневых класса поддержки, Unbounded (неограниченный) и Bounded (ограниченный). Задачей класса unbounded является поддержка быстро работающего связного списка, элементы которого размещаются в памяти, выделенной из "кучи". Это представление эффективно по скорости, но не по памяти, так как каждый элемент списка должен, кроме своего значения, дополнительно содержать указатель на следующий элемент того же списка. Задача класса Bounded состоит в организации структур на базе массива, что эффективно с точки зрения памяти, но добиться большой производительности трудно, так как, например, при добавлении элемента в середину списка приходится последовательно копировать все последующие (или предыдущие) элементы массива.
Как видно из рис. 9-4, для включения этих классов нижнего уровня в иерархию основных абстракций мы используем агрегацию. Более точно, диаграмма показывает, что мы используем физическое включение по значению с защищенным Доступом, которое означает, что это низкоуровневое представление доступно только подклассам и друзьям. На раннем этапе проектирования мы хотели воспользоваться примесями и сделать unbounded и Bounded защищенными суперклассами.
Рис. 9-4. Ограниченная и неограниченная формы.
Мы в конце концов отказались от такого варианта, так как он достаточно труден для понимания, и к тому же нарушает лакмусов принцип наследования: BoundedQueue, по крайней мере, с точки зрения типа данных, не является частным случаем класса Bounded.
Отметим также, что работа с двумя формами требует присутствия второго аргумента в их шаблоне. Для ограниченной формы - это беззнаковое целое число Size, обозначающее статический размер объекта. Для неограниченной формы - это класс StorageManager, ответственный за политику размещения в памяти. Мы рассмотрим его работу в следующем разделе.
Протокол обоих классов поддержки должен быть, с одной стороны, достаточным для обеспечения работы конкретных подклассов, а с другой стороны, универсальным, чтобы гарантировать выполнение ответственности всех других структур в библиотеке. В целях компактности и быстродействия мы не включили в описание классов Unbounded и Bounded ни одной виртуальной функции. По этой причине мы не можем объединить их одним суперклассом, несмотря на то, что они имеют общий протокол; кроме того, мы не можем надлежащим образом построить на их базе иерархию подклассов. В данном случае гибкость приносится в жертву производительности. По той же причине мы решаем сделать ряд функций встроенными; хорошими кандидатами на это обычно являются селекторы, особенно те, которые возвращают простые переменные.
Рассмотрим, например, описание класса Bounded:
template<class Item, unsigned int Size> class Bounded { public:
Bounded(); Bounded(const Bounded<Item, Size>&); ~Bounded(); Bounded<Item, Size>& operator=(const Bounded<Item, Size>&); int operator==(const Bounded<Item, Size>&) const; int operator!=(const Bounded<Item, Size>&) const; const Item& operator[](unsigned int index) const; Item& operator[](unsigned int index); void clear(); void insert(const Item&); void insert(const Item&, unsigned int before); void append(const Item&); void append(const Item&, unsigned int after); void remove(unsigned int at); void replace(unsigned int at, const Item&); unsigned int available() const; unsigned int length() const; const Item& first() const; const Item& last() const; const Item& itemAt(unsigned int) const; Item& itemAt(unsigned int); int location(const Item&) const; static void* operator new(size_t); static void operator delete(void*, size_t);
protected:
Item rep[Size]; unsigned int start; unsigned int stop; unsigned int expandLeft(unsigned int from); unsigned int expandRight(unsigned int from); void shrinkLeft(unsigned int from); void shrinkRight(unsigned int from);
};
Объявление класса следует схеме, описанной ранее. Каким образом мы пришли именно к такому решению? Если честно, то на 80% это результат чистого проектирования классов, которое рассматривалось в главе 6. Затем интерфейс дорабатывался в соответствии с результатами пробного использования класса совместно с рядом основных абстракций системы. Основная трудность при эволюции состояла в идентификации подходящих примитивных операций, которые должны использоваться при работе с набором различных структур.
Сердцем класса является защищенный массив rep постоянного размера Size. Рассмотрим следующее объявление:
Bounded<char, 100U> charSequence;
При создании соответствующего объекта в стеке образуется массив постоянного размера из 100 элементов. Защищенные члены класса start и stop (индексы в этом массиве) указывают начало и конец последовательности. Тем самым мы использовали кольцевой буфер данных. Добавление нового элемента в начало или в конец последовательности не потребует перемещения данных, а добавление элемента в середину массива приводит к копированию не более чем половины его элементов.
Проектирование ограниченного и неограниченного классов поддержки затрагивает также некоторые тонкие вопросы, касающиеся использования ссылок (мы упоминали о них в главе 3). Нам придется еще раз коснуться этой темы, и не только потому, что она имеет прямое отношение к разработке интерфейса параметризованных классов, но и потому, что данные вопросы сами по себе представляют значительный интерес для проектировщика любой более или менее нетривиальной библиотеки.
В C++ ссылки являются механизмом, позволяющим улучшить производительность. Однако пользоваться ими следует предельно осторожно во избежание нарушения корректного доступа к оперативной памяти. В данной библиотеке мы используем ссылки для ускорения работы при передаче аргументов функциям-членам. Это касается, например, класса Bounded, где подобным образом передаются ссылки на объекты классов Bounded и Item. Ссылки, как правило, не используются для передачи примитивных объектов (например, целых чисел в описании функции-члена itemAt) - программа от этого будет работать только медленнее. Кроме того, семантика языка C++ порождает некоторые опасности при манипулировании с временными объектами.
Все наши структуры, однако, содержат в качестве элементов не ссылки, а значения, что исключает возникновение ссылок на временные объекты в стеке при работе программы. По той же причине мы отказались от хранения указателей на элементы структур, так как это вызывает крайне нестабильное поведение системы при инстанцировании шаблона встроенными типами данных. Подобные вопросы чрезвычайно существенны при проектировании сред разработки, включающих в себя параметризованные классы, так как пользователь может инстанцировать шаблон произвольным типом данных. При использовании ссылок существуют, вообще говоря, три случая, и нам придется при создании библиотеки постараться найти определенный баланс между ними.
Во-первых, встроенные типы данных можно без труда передавать по ссылке и копировать. Объявив типы аргумента постоянными ссылками, можно избежать неприятностей, связанных с появлением временных структур, возникающих при приведении типов [12].
Во-вторых, типы данных, определенные пользователем, также можно передавать по ссылке и копировать, но только в том случае, когда для них определены копирующий конструктор и оператор присваивания. Ссылки можно использовать в полиморфных операциях (передавая объект производного класса вместо объявленного при инстанцировании), но копирование не будет полиморфным. В результате объект будет "срезан" до размеров своего базового класса.
В-третьих, при полиморфном использовании библиотеки встретится инстанцирование шаблонов указателями на базовый класс. Хотя передача указателей по ссылке может и не улучшить производительность, но копирование указателей в представление сохраняет полиморфизм производных объектов.
Например, для класса BoundedQueue мы можем написать следующее:
class Event ... typedef Event* EventPtr; BoundedQueue<int, 10U> intQueue; BoundedQueue<Event, 50U> eventQueue1; BoundedQueue<EventPtr, 100U> eventQueue2;
С помощью объекта класса eventQueue1 можно спокойно создавать очереди событий, однако при добавлении в очередь экземпляра любого подкласса Event произойдет "срезка", и полиморфное поведение такого экземпляра будет потеряно. С другой стороны, объект класса eventQueue2 содержит указатели на объекты класса Event, поэтому проблема "срезки" не возникает.
Наше решение, касающееся хранения внутри структур значений, а не ссылок, предъявляет определенные требования к конструкторам и деструкторам элементов. В частности, классы, используемые для инстанцирования структуры, должны, по крайней мере, иметь конструктор по умолчанию, копирующий конструктор и оператор присваивания. Кроме того, в некоторых случаях элементы не могут быть уничтожены сразу после удаления из структуры. В ограниченной форме, например, элементы (хранящиеся в массивах) не уничтожаются до уничтожения всей структуры.
Посмотрим, как можно использовать класс Bounded при формировании конкретного класса BoundedQueue. Отметим, что абстракция BoundedQueue содержит защищенный элемент rep класса Bounded.
template<class Item, unsigned int Size> class BoundedQueue : public Queue<Item> { public:
BoundedQueue(); BoundedQueue(const BoundedQueue<Item, Size>&); virtual ~BoundedQueue(); virtual Queue<Item>& operator=(const Queue<Item>&); virtual Queue<Item>& operator=(const BoundedQueue<Item, Size>&); virtual int operator==(const Queue<Item>&) const; virtual int operator=(const BoundedQueue<Item, Size>&) const; int operator!=(const BoundedQueue< Item, Size>&) const; virtual void clear(); virtual void append(const Item&); virtual void pop(); virtual void remove(unsigned int at); virtual unsigned int available() const; virtual unsigned int length() const; virtual int isEmpty() const; virtual const Item& front() const; virtual int location(const Item&) const;
protected:
Bounded<Item, Size> rep; virtual void purge(); virtual void add(const Item&); virtual unsigned int cardinality() const; virtual const Item& itemAt(unsigned int) const; static void* operator new(size_t); static void operator delete(void*, size_t);
};
Основная задача данного класса - завершить протокол, определенный в базовом классе. Часто это означает немного больше, чем простая передача обязанности классу более низкого уровня Bounded, как предлагается в следующей реализации:
template<class Item, unsigned int Size>
unsigned int BoundedQueue<Item, Size>::length() const {
return rep.length();
}
Отметим, что в описание класса BoundedQueue включены некоторые дополнительные операции, которых нет в его суперклассе. Добавлен селектор available, возвращающий количество свободных элементов в структуре (вычисляется как разность Size - length()). Эта операция не включена в описание базового класса главным образом из-за того, что для неограниченной модели вычисление свободного места не очень осмысленно. Мы также переопределили оператор присваивания и проверку равенства. Как уже отмечалось ранее, это позволяет применить более эффективные алгоритмы по сравнению с базовым классом, так как подклассы лучше знают, что и как делать. Добавленные операторы new и delete определены в защищенной части класса, чтобы лишить клиентов возможности произвольно динамически размещать экземпляры BoundedQueue (что согласуется со статической семантикой этой конкретной формы).
Класс Unbounded имеет, в существенном, тот же протокол, что и класс Bounded, однако его реализация совершенно другая.
template<class Item, class StorageManager> class Unbounded { public: ... protected:
Node<Item, StorageManager>* rep; Node<Item, StorageManager>* last; unsigned int size; Node<Item, StorageManager>* cache; unsigned int cacheIndex;
};
Форма Unbounded реализует очередь как связный список узлов, где узел (Node) реализован следующим образом:
template<class Item, class StorageManager> class Node { public:
Node(const Item& i, Node<Item, StorageManager>* previous, Node<Item, StorageManager>* next); Item item; Node<Item, StorageManager>* previous; Node<Item, StorageManager>* next; static void* operator new(size_t); static void operator delete(void*, size_t);
};
Основная задача этого класса - управлять одним элементом списка и указателями на предыдущий и следующий узлы. Данная абстракция отнесена к категории классов поддержки, к ней не имеют доступ внешние пользователи, и поэтому мы решили несколько ослабить наши традиционные строгие требования к инкапсуляции, сделав все элементы класса открытыми и жертвуя таким образом безопасностью ради эффективности.
Помня, что классы Bounded и Unbounded имеют практически идентичный внешний протокол, а, значит, их функциональные свойства во многом подобны, можно предположить, что и реализация будет схожей. Однако различие во внутреннем представлении классов приводит к существенно различной пространственно-временной семантике. Манипуляции с узлами связанного списка, например, осуществляются очень быстро, однако процедура нахождения нужного элемента будет занимать время порядка O(n). Поэтому наше представление кэширует последний узел, к которому было обращение, в надежде, что следующее обращение будет либо к этому же узлу, либо к его соседям. Схема же, базирующаяся на массивах, дает низкое быстродействие (в худшем случае порядка O(n/2) если элемент расположен в середине массива) при добавлении или удалении элементов, однако обеспечивает высокую скорость поиска (порядка O(1)).
Управление памятью
Задача управления памятью возникает для неограниченных форм реализации. В этом случае разработчик библиотеки должен определить политику выделения и освобождения памяти из кучи при осуществлении операций над узлами. Наивный подход просто использует глобальные функции new и delete, что не может обеспечить достаточной производительности системы. Кроме того, на некоторых компьютерных платформах управление памятью крайне усложнено (например, при наличии сегментированного адресного пространства в некоторых операционных системах персональных компьютеров) и требует разработки специальной стратегии, жестко привязанной к определенной операционной среде. Для нашей библиотеки надо четко выделить подсистему управления памятью.
На рис. 9-5 приведен выбранный для данной библиотеки механизм управления памятью [Историческое замечание: потребовалось около четырех итераций архитектуры библиотеки, чтобы придти именно к этому механизму, который - что не удивительно - оказался самым простым. Предыдущие варианты, от которых мы в конце концов отказались, были недостаточно гибкими, трудными для объяснения и стремились навязать особенности реализации безразличным к ней клиентам]. Рассмотрим сценарий, иллюстрацией которого служит данная диаграмма:
• Клиент (aClient) вызывает операцию добавления (append) для экземпляра класса UnboundedQueue (более точно, экземпляра класса, инстанцированного из UnboundedQueue).
• UnboundedQueue, в свою очередь, передает выполнение операции своему элементу rep, который является экземпляром класса unbounded.
• Unbounded, вызывая свою статическую функцию new, выделяет необходимый объем адресного пространства для размещения нового экземпляра Node.
• Этот экземпляр Node, в свою очередь, делегирует ответственность за выделение памяти своему StorageManager, который доступен классу, инстанцируемому из UnboundedQueue (и, следовательно, классам Unbounded и Node), как аргумент шаблона. StorageManager разделяется всеми экземплярами и служит для обеспечения последовательной политики выделения памяти на уровне класса.
Рис. 9-5. Механизм управления памятью.
Передавая StorageManager в качестве аргумента всем неограниченным структурам, мы четко отделяем политику организации доступа к памяти от ее реализации и даем пользователям возможность добавлять в программу свои собственные концепции управления памятью, не меняя при этом содержания библиотеки. Это классический пример того, как можно добиться открытости программной системы через инстанцирование, не прибегая к наследованию.
Единственное требование, предъявляемое к вариантам StorageManager, заключается в необходимости сохранения единого протокола. В частности, все они должны содержать открытые функции-члены allocate и deallocate, предназначенные соответственно для выделения и освобождения памяти. Рассмотрим в качестве примера простейший вариант такого класса:
class Unmanaged { public:
static void* allocate(size_t s) {return ::operator new(s);} static void deallocate(void* p, size_t) {::operator delete(p);}
private:
Unmanaged() {} Unmanaged(Unmanaged&) {} void operator=(Unmanaged&) {} void operator==(Unmanaged&) {} void operator!=(Unmanaged&) {}
};
Обратите внимание на идиому, которая применяется, чтобы пользователь не мог копировать, присваивать и сравнивать экземпляры данного класса.
Протокол класса Unmanaged реализован через встроенные вызовы глобальных операторов new и delete. Мы назвали данную абстракцию Unmanaged, не требующей управления, так как она фактически не представляет собой ничего нового, а просто повторяет уже существующий системный механизм. Требующей управления названа другая абстракция, реализующая гораздо более эффективный алгоритм. В соответствии с этим алгоритмом память под узлы выделяется из некоего общего пула памяти. Если узел не используется, он помечается как свободный. Если возникает необходимость в новом узле, используется один из списка свободных. Выделение новой памяти из кучи происходит только в случае, если этот список пуст. Таким образом, часто удается избежать обращения к сервисным функциям операционной системы: выделение памяти сводится лишь к манипулированию указателями, что гораздо быстрее [В языке C++ глобальный оператор new так или иначе вызывает какой-либо вариант функции malloc - операции довольно дорогой].
При желании можно еще улучшить наш механизм, например, введя новую операцию для выделения памяти заранее, до того, как она понадобится. И наоборот, в определенных ситуациях, когда неиспользованных участков становится слишком много, можно дефрагментировать пул, и вернуть освободившуюся память в кучу. Можно предусмотреть операцию, позволяющую пользователю определить размер кластера памяти, и, таким образом, настроить класс под конкретное приложение.
В соответствии с приведенными выше соображениями, соответствующий класс поддержки можно определить следующим образом:
class Pool { public:
Pool(size_t chunkSize); ~Pool(); void* allocate(size_t); void deallocate(void*, size_t); void preallocate(unsigned int numberOfChunks); void reclaimUnusedChunks(); void purgeUnusedChunks(); size_t chunkSize() const; unsigned int totalChunks() const; unsigned int numberOfDirtyChunks() const; unsigned int numberOfUnusedChunks() const;
protected:
struct Element ... struct Chunk ... Chunk* unusedChunks; size_t repChunkSize; size_t usableChunkSize; Chunk* getChunk(size_t s);
};
Описание содержит два вложенных класса Element и chunk (отрезок). Каждый экземпляр класса Pool управляет связным списком объектов chunk, представляющих собой отрезки "сырой" памяти, но трактуемых как связные списки экземпляров класса Element (это один из важных аспектов, управляемых классом pool). Каждый отрезок может отводиться элементам разного размера и для эффективности мы сортируем список отрезков в порядке возрастания их размеров. Менеджер памяти может быть определен следующим образом:
class Managed { public:
static Pool& pool; static void* allocate(size_t s) {return pool.allocate(s); } static void deallocate(void* p, size_t s) {pool.deallocate(p, s);}
private:
Managed() {} Managed(Managed&) {} void operator=(Managed&) {} void operator==(Managed&) {} void operator!=(Managed&) {}
};
Этот класс имеет тот же внешний протокол, что и Unmanaged. Из-за того, что в C++ шаблоны сознательно недостаточно четко определены, соответствие данному протоколу проверяется только при трансляции инстанцированного класса типа UnboundedQueue, в тот момент, когда конкретный класс сопоставляется с формальным аргументом StorageManager.
Объект класса Pool, принадлежащий классу Managed, является статическим. Это позволяет нескольким конкретным структурам (требующим управления) делить между собой единый пул памяти. Различные структуры, не требующие управления, могут, конечно, определить своего менеджера и свой пул памяти, предоставляя таким образом разработчику полный контроль над политикой выделения памяти.
Рис. 9-6. Классы управления памятью.
На рис. 9-6 приведена диаграмма классов, иллюстрирующая схему взаимодействия различных классов, обеспечивающих управление памятью. Мы показали только ассоциативную связь между классом Managed и его клиентами Unbounded и UnboundedQueue; эта ассоциация будет уточнена при конкретном инстанцировании классов.
Физическая компоновка классов поддержки тоже является частью архитектурного решения. Рис. 9-7 иллюстрирует их модульную архитектуру. Мы выбрали именно такую схему, чтобы изолировать классы, которые, по-видимому, будут чаще всего подвергаться изменениям.
Рис. 9-7. Модули управления памятью.
Исключения
Несмотря на то, что язык C++ можно заставить соблюдать многие статические предположения (нарушение которых повлечет ошибку компиляции), для выявления динамических нарушений (таких, как попытка добавить элемент к полностью заполненной ограниченной очереди или удалить элемент из пустого списка) приходится использовать и другие механизмы. В данной библиотеке используются средства обработки исключений, предоставляемые C++ [14]. Наша архитектура включает в себя иерархию классов исключений и, отдельно от нее, ряд механизмов по выявлению таких ситуаций.
Начнем с базового класса 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();