Lecture
In accordance with Coggins's law of program development, "pragmatism must always be preferred to elegance, for Nature cannot be surprised by anything anyway." A corollary: design will never be completely independent of the project's implementation language. The features of the language will inevitably leave their mark on one or another architectural decision, and ignoring them may lead to our having to work henceforth with abstractions that do not fully take into account the advantages and drawbacks of the particular implementation language.
As was noted in Chapter 3, object-oriented languages provide three basic mechanisms for organizing a large number of classes: inheritance, aggregation, and parameterization. Inheritance is the most popular property of object-oriented technology, but it is by no means the only principle of structuring. As we shall see, combining parameterization with inheritance and aggregation helps to create a sufficiently powerful and at the same time compact architecture.
Let us consider an abridged description of a domain-dependent queue class in C++:
class NetworkEvent... // network event
class EventQueue { // event queue
public:
EventQueue();
virtual ~EventQueue();
virtual void clear(); // clear
virtual void add(const NetworkEvent&); // add
virtual void pop(); // advance
virtual const NetworkEvent& front() const; // first element
...
};
Before us is an abstraction embodying a queue of events: a structure to which we can add new elements at the end of the queue and from which we can remove elements at the front of the queue. C++ makes it possible to hide the internal details of the implementation of the queue class behind its external interface (the operations clear, add, pop and front ).
We may also need certain other variants of a queue, for example a priority queue, where events are arranged in accordance with their urgency. It is reasonable to take advantage of work already done and to organize the new class on the basis of the previously defined one:
class PriorityEventQueue : public EventQueue {
public:
PriorityEventQueue();
virtual ~PriorityEventQueue();
virtual void add(const NetworkEvent&);
...
};
The virtuality of the functions (for example, the function add) encourages the redefinition of operations in subclasses.
Combining inheritance with parameterized classes makes it possible to create even more general abstractions. The semantics of the queue class do not depend on what is in it: wolves or sheep. Using template classes, we can redefine our base class as follows:
template
class Queue {
public:
Queue();
virtual ~Queue();
virtual void clear();
virtual void add(const Item&);
virtual void pop();
virtual const Item& front() const;
...
};
This is the most common way of using parameterized classes: take an existing concrete class, extract from it that which does not depend on the elements it operates upon, and make those elements arguments of the template.
Inheritance and parameterization combine very well. Our subclass PriorityQueue can, for example, be generalized as follows:
template
class PriorityQueue : public Queue {
public:
PriorityQueue();
virtual ~PriorityQueue();
virtual void add(const Item&);
...
};
Type safety is a key advantage of this approach. We can create a whole series of different concrete queue classes:
Queue characterQueue;
typedef Queue EventQueue;
typedef PriorityQueue PriorityEventQueue;
Figure 9-1. Inheritance and parameterization.
At the same time the implementation language will not allow us to attach an event to a queue of characters, or a floating-point number to a queue of events.
Figure 9-1 illustrates the relationships between a parameterized class (Queue), its subclass (PriorityQueue), an instantiation of this subclass (PriorityEventQueue) and one of its instances (mailQueue).
This example confirms the correctness of one of our very first architectural decisions: almost all the classes of our library must be parameterized. Then the requirement of safety will also be fulfilled.
Macro organization
As was already noted in previous chapters, classes are a necessary but not a sufficient means of decomposing a system. This remark applies fully to a class library as well. An unordered set of classes in which developers rummage in search of something useful is very nearly the worst of the possible solutions. It is better to divide the classes into separate categories (Figure 9-2). Such a solution makes it possible to satisfy the requirement of simplicity of the library.
At first glance at the problem domain it is easy to notice that we could take advantage of functional properties common to the classes. We will therefore establish a publicly available category Support for low-level abstractions and classes supporting the common mechanisms of the library.
This observation leads us to the second principle of the library's architecture: a clear separation between policy and implementation. Such abstractions as queues, sets, and rings reflect the policy of using low-level structures: linked lists or arrays. A queue, for example, expresses a policy under which one may only remove elements from the beginning of the structure and add elements to its end. A set, on the other hand, represents no policy requiring any ordering of the elements. A ring requires ordering, but presupposes that the first and last elements are joined. To the category Support we will assign simple abstractions - those on top of which policy is built.
By placing this category of classes in the code of the library, we support the library requirement of extensibility. The bulk of developers may well not use the classes from Support. However, library developers and more advanced programmers will be able to employ the basic abstractions from Support to construct new classes or modify the behavior of existing ones.
Figure 9-2. Categories of classes in the library.
As can be seen from Figure 9-2, the library is organized not as a tree but as a forest of classes; there is no single base class here, as languages of the Smalltalk type require.
This is not visible in the figure, but in fact the classes of the categories Graphs, Lists and Trees differ somewhat from the other structural classes. Earlier we noted that abstractions of the deque and stack type are monolithic. A monolithic structure can be dealt with only as a single whole: it cannot be broken up into separate identifiable components, and thus referential integrity is guaranteed. On the other hand, in a composite structure (such as a graph) structural sharing is permitted. In it we can, for example, gain access to sublists, branches of a tree, individual vertices or edges of a graph. The fundamental difference between these two categories of structures lies in the semantics of the operations of copying, assignment, and comparison. For monolithic abstractions such operations may be called "deep," and for composite abstractions "shallow," in the sense that copying passes a reference to a part of the shared structure.
Families of classes
The third basic principle of designing the library consists in building families of classes connected by the inheritance relationship. For each type of structure we will create several different classes united by a single interface (as in the case of the abstract class Queue), but with different concrete subclasses having somewhat different representations and therefore differing in their internal organization and their "time/memory" characteristics. In this way we will provide for the library requirement of completeness. A developer will be able to choose the concrete class that is better suited to solving his problem. At the same time this class possesses the same interface as the remaining classes of the family. A deliberate, clear separation of the abstract base class from its concrete subclasses allows the user of the system to choose, say, at the first stage of design, one of the classes as a working one, and then, in the course of refining the application, to replace it with another, somewhat different class of the same family, expending a minimum of time and effort on this (the only thing he will need is to recompile his program). In doing so the developer will be confident of the normal functioning of the program, since all the classes belonging to one family possess an identical external interface and similar behavior. The point of such an organization of classes also consists in the possibility of copying, assigning, and comparing objects of one family even in the case where their representations are completely different.
One may say that the abstract base class contains, as it were, all the important features of the abstraction. Another important application of abstract base classes is the caching of common state that is expensive to recompute. In this way one can turn an O(n) computation into an operation of order O(1) - a simple reading of data. In doing so, naturally, it is necessary to provide an appropriate mechanism of interaction between the abstract base class and its subclasses, in order to guarantee the currency of the cached value.
The elements of a family of classes represent different forms of an abstraction. Experience shows that there are two basic forms of abstraction that a developer should use when creating serious applications. First, there is the form of the concrete representation of the abstraction in the machine's main memory. There are two variants of such a representation: allocating memory for the structure from the stack, or allocating main memory from the heap. Two forms of abstraction correspond to them: bounded and unbounded:
| ® Bounded | The structure is stored on the stack and thus has a static size (known at the moment the object is created). |
| ® Unbounded | The structure is stored on the heap and its size can change dynamically. |
Since the bounded and unbounded forms of an abstraction have a common interface and behavior, both of them can be represented as direct subclasses of the abstract base class for each structure. We will discuss these and other features of data organization in the following sections.
The second variant is connected with synchronization. As was noted in Chapter 2, many useful applications make do with a single process. They are called sequential systems, because they use a single thread of control. Other applications (this concerns real-time systems especially) require providing synchronization of several simultaneously executing threads. Such systems are called concurrent, and in them mutual exclusion of processes competing for one and the same resource must somehow be ensured. Clearly, one cannot allow several threads to control one and the same object simultaneously; this will in the end lead to the corruption of its state. Consider, for example, the behavior of two agents that simultaneously try to add an element to one and the same object of the class Queue. The first agent, having begun adding an element, may be interrupted before it finishes this operation, and will leave the object to the second agent in an incomplete state.
Figure 9-3. Families of classes.
As was noted in Chapter 3, in this case there are only three possible design alternatives, each of which requires providing a different level of interaction between the agents that operate on shared objects:
We will consider each of these variants in more detail in the next section. Providing interaction between the abstract base class, the forms of its representation, and the forms of synchronization gives rise, for each structure, to a family of classes like the one shown in Figure 9-3. Now it is possible to understand why we decided at the time to organize the library precisely as families of classes, and not as a single tree. This was done because such an architecture:
Micro organization
In order to ensure simplicity of working with the system, let us choose one common style of laying out the structures and mechanisms of the library:
template<...>
class Name : public Superclass {
public:
// constructors
// virtual destructor
// operators
// modifiers
// selectors
protected:
// data
// functions
private:
// friends
};
The description of the abstract base class Queue begins as follows:
template class Queue {
The template signature template serves to specify the arguments of the parameterized class. Note that in C++ templates were deliberately introduced in such a way as to place sufficient flexibility (and responsibility) in the hands of the developer who instantiates the template in his application.
Next let us define the usual list of constructors and destructors:
Queue();
Queue(const Queue&);
virtual ~Queue();
Note that we declared the destructor virtual in order to ensure polymorphic behavior when objects of the class are destroyed. Next let us declare all the operators:
virtual Queue& operator=(const Queue&);
virtual int operator==(const Queue&) const;
int operator!=(const Queue&) const;
We defined the assignment operator (operator==) and the comparison operator (operator==) as virtual in order to ensure type safety. Redefining these operators is the responsibility of the subclasses. They will use functions whose argument is an object of their own specialized class. In this sense subclasses have the advantage that they know the representation of their instances and can provide a very efficient implementation. When the concrete subclass of the queue is unknown (for example, if we pass an object by reference to its base class), the operator of the base class is invoked, using algorithms that may be less efficient but are more universal. This idiom has a side effect: the ability of one and the same function to work with queues having different internal implementations, without violating typing.
If we want to restrict access to the copying, assignment, or comparison of certain objects, we have to declare these operators protected or private.
Let us now define the modifiers that make it possible to change the state of an object:
virtual void clear() = 0;
virtual void append(const Item&) = 0;
virtual void pop() =0;
virtual void remove (unsigned int at) = 0;
These operations are declared as pure virtual, and this means that describing them is the responsibility of the subclasses. The presence of pure virtual functions makes the class Queue abstract.
The specifier const indicates (and the compiler can check this) the use of selector functions, that is, functions intended exclusively for obtaining information about the state of an object, but not for changing that state:
virtual unsigned int length() const = 0;
virtual int isEmpty() const = 0;
virtual const Item& front() const =0;
virtual int location(const Item&) const = 0;
These operations too are defined as pure virtual, because the class Queue does not possess enough information to describe them fully.
The protected part of each class begins with the description of those elements that form the basis of its structure and must be accessible to subclasses [Everywhere that weighty reasons do not compel us to act otherwise, we declare the members of a class private. Here, however, there is a weighty reason to declare these fragments protected: subclasses will require access to them]. The abstract class Queue, unlike its subclasses (see below), has no such members.
The protected part of the base class continues with the definition of the utility functions that will be polymorphically implemented in the concrete subclasses. The class Queue contains a fairly typical list of such functions:
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();
The reasons why we introduced precisely these functions will be considered in the next section.
And finally, let us define the private part, usually containing declarations of friend classes and those members that we want to make inaccessible even to subclasses. The class Queue contains only friend declarations:
friend class QueueActiveIterator;
friend class QueuePassiveIterator;
As we shall see later, these friend declarations will be needed to support the iterator idioms.
The semantics of time and memory
Of the five basic principles of the construction of a foundation class library, perhaps the most important is the mechanism that provides the client with alternative space/time semantics within each family of classes.
Let us consider the spectrum of requirements that must be taken into account when developing a general-purpose library. On a workstation possessing a large virtual address space, the user will most likely squander memory for the sake of higher performance. On the other hand, in some embedded systems, such as a satellite or an automobile engine, memory resources are often limited, and the developer is forced to choose as his working abstractions those that use less memory (for example, allocating space for data on the stack rather than in the "heap"). Earlier we distinguished these two possibilities as the bounded and unbounded forms respectively.
Unbounded forms are applicable in those cases where the size of the structure cannot be predicted, and where allocating and reclaiming memory from the heap leads neither to a loss of time nor to a reduction in reliability (as happens in some time-critical applications) [Certain requirements on a system may prohibit the use of dynamically allocated memory. Consider a cardiac pacemaker and the possible fatal results that a garbage collector "waking up" at an inopportune moment could bring about. There are systems with a long duty cycle: in them even a minimal memory leak can produce a serious cumulative effect; a forced restart of the system because of a lack of memory can lead to an unacceptable loss of functionality]. Bounded forms are better suited for working with small structures whose size is fairly well predictable. Let us also take into account that dynamic memory allocation is less tolerant of programmer errors.
Thus, all the structures of this library must be present in alternative variants; therefore we will have to create two low-level support classes, Unbounded and Bounded. The task of the class unbounded is to support a fast linked list whose elements are placed in memory allocated from the "heap." This representation is efficient in speed but not in memory, since each element of the list must, besides its value, additionally contain a pointer to the next element of the same list. The task of the class Bounded consists in organizing structures on the basis of an array, which is efficient from the standpoint of memory, but it is difficult to achieve high performance, since, for example, when adding an element in the middle of the list one has to copy sequentially all the subsequent (or preceding) elements of the array.
As can be seen from Figure 9-4, to incorporate these low-level classes into the hierarchy of the main abstractions we use aggregation. More precisely, the diagram shows that we use physical containment by value with protected access, which means that this low-level representation is accessible only to subclasses and friends. At an early stage of design we wanted to make use of mixins and make unbounded and Bounded protected superclasses.
Figure 9-4. Bounded and unbounded forms.
In the end we rejected such a variant, since it is fairly hard to understand and, moreover, violates the litmus test of inheritance: BoundedQueue, at least from the standpoint of data type, is not a special case of the class Bounded.
Let us also note that working with the two forms requires the presence of a second argument in their template. For the bounded form it is the unsigned integer Size, denoting the static size of the object. For the unbounded form it is the class StorageManager, responsible for the memory allocation policy. We will consider its operation in the next section.
The protocol of both support classes must be, on the one hand, sufficient to make the concrete subclasses work, and on the other hand universal, so as to guarantee that the responsibilities of all the other structures in the library are fulfilled. For the sake of compactness and speed we did not include a single virtual function in the descriptions of the classes Unbounded and Bounded. For this reason we cannot unite them under a single superclass, despite the fact that they have a common protocol; in addition, we cannot properly build a hierarchy of subclasses on their basis. In this case flexibility is sacrificed to performance. For the same reason we decide to make a number of functions inline; good candidates for this are usually selectors, especially those that return simple variables.
Consider, for example, the description of the class Bounded:
template
class Bounded {
public:
Bounded();
Bounded(const Bounded&);
~Bounded();
Bounded& operator=(const Bounded&);
int operator==(const Bounded&) const;
int operator!=(const Bounded&) 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);
};
The declaration of the class follows the scheme described earlier. How did we arrive at precisely this solution? To be honest, 80% of it is the result of the pure class design that was considered in Chapter 6. Then the interface was refined in accordance with the results of trial use of the class together with a number of the main abstractions of the system. The main difficulty during the evolution consisted in identifying suitable primitive operations that should be used when working with a set of different structures.
The heart of the class is the protected array rep of constant size Size. Consider the following declaration:
Bounded charSequence;
When the corresponding object is created, an array of constant size of 100 elements is formed on the stack. The protected members of the class, start and stop (indices into this array), indicate the beginning and end of the sequence. We have thereby used a circular data buffer. Adding a new element at the beginning or at the end of the sequence will not require moving data, while adding an element in the middle of the array leads to copying no more than half of its elements.
The design of the bounded and unbounded support classes also touches on certain subtle questions concerning the use of references (we mentioned them in Chapter 3). We will have to touch on this topic once more, and not only because it bears directly on the development of the interface of parameterized classes, but also because these questions are in themselves of considerable interest to the designer of any more or less nontrivial library.
In C++ references are a mechanism that makes it possible to improve performance. However, they should be used with extreme care so as to avoid violating correct access to main memory. In this library we use references to speed up work when passing arguments to member functions. This concerns, for example, the class Bounded, where references to objects of the classes Bounded and Item are passed in this way. References are, as a rule, not used for passing primitive objects (for example, integers in the description of the member function itemAt) - the program will only run more slowly for it. In addition, the semantics of the C++ language give rise to certain dangers when manipulating temporary objects.
All of our structures, however, contain as elements not references but values, which precludes the appearance of references to temporary objects on the stack while the program is running. For the same reason we declined to store pointers to the elements of the structures, since this causes extremely unstable behavior of the system when the template is instantiated with built-in data types. Such questions are exceptionally significant when designing frameworks that include parameterized classes, since the user may instantiate the template with an arbitrary data type. When using references there are, generally speaking, three cases, and in creating the library we will have to try to find a certain balance among them.
First, built-in data types can be passed by reference and copied without difficulty. By declaring the argument types to be constant references, one can avoid the unpleasantness associated with the appearance of temporary structures arising from type conversions [12].
Second, user-defined data types can also be passed by reference and copied, but only in the case where a copy constructor and an assignment operator are defined for them. References can be used in polymorphic operations (passing an object of a derived class instead of the one declared at instantiation), but copying will not be polymorphic. As a result the object will be "sliced" down to the size of its base class.
Third, in polymorphic use of the library one will encounter the instantiation of templates with pointers to a base class. Although passing pointers by reference may not improve performance, copying pointers into the representation preserves the polymorphism of the derived objects.
For example, for the class BoundedQueue we can write the following:
class Event ... typedef Event* EventPtr;
BoundedQueue intQueue;
BoundedQueue eventQueue1;
BoundedQueue eventQueue2;
With the help of the object of class eventQueue1 one can safely create queues of events, but when an instance of any subclass of Event is added to the queue, "slicing" will occur, and the polymorphic behavior of such an instance will be lost. On the other hand, the object of class eventQueue2 contains pointers to objects of class Event, and therefore the problem of "slicing" does not arise.
Our decision concerning the storing of values rather than references inside the structures imposes certain requirements on the constructors and destructors of the elements. In particular, the classes used to instantiate a structure must, at a minimum, have a default constructor, a copy constructor, and an assignment operator. In addition, in some cases elements cannot be destroyed immediately after being removed from the structure. In the bounded form, for example, the elements (stored in arrays) are not destroyed until the entire structure is destroyed.
Let us see how the class Bounded can be used in forming the concrete class BoundedQueue. Note that the abstraction BoundedQueue contains a protected member rep of class Bounded.
template
class BoundedQueue : public Queue {
public:
BoundedQueue();
BoundedQueue(const BoundedQueue&);
virtual ~BoundedQueue();
virtual Queue& operator=(const Queue&);
virtual Queue& operator=(const BoundedQueue Size>&);
virtual int operator==(const Queue&) const;
virtual int operator=(const BoundedQueue&) 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 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);
};
The main task of this class is to complete the protocol defined in the base class. Often this means little more than simply passing the responsibility on to the lower-level class Bounded, as is suggested in the following implementation:
template
unsigned int BoundedQueue::length() const
{
return rep.length();
}
Note that the description of the class BoundedQueue includes some additional operations that are not present in its superclass. The selector available has been added, returning the number of free elements in the structure (computed as the difference Size - length()). This operation is not included in the description of the base class mainly because for the unbounded model computing the free space is not very meaningful. We have also redefined the assignment operator and the equality test. As was already noted earlier, this makes it possible to apply more efficient algorithms compared with the base class, since subclasses know better what to do and how. The added operators new and delete are defined in the protected part of the class in order to deprive clients of the ability to allocate instances of BoundedQueue dynamically at will (which is consistent with the static semantics of this particular form).
The class Unbounded has, in essence, the same protocol as the class Bounded, but its implementation is completely different.
template
class Unbounded {
public:
...
protected:
Node* rep;
Node* last;
unsigned int size;
Node* cache;
unsigned int cacheIndex;
};
The Unbounded form implements a queue as a linked list of nodes, where a node (Node) is implemented as follows:
template
class Node {
public:
Node(const Item& i,
Node* previous, Node* next);
Item item;
Node* previous;
Node* next;
static void* operator new(size_t);
static void operator delete(void*, size_t);
};
The main task of this class is to manage one element of the list and the pointers to the previous and next nodes. This abstraction is assigned to the category of support classes, external users do not have access to it, and therefore we decided to relax somewhat our traditional strict requirements for encapsulation by making all the members of the class public, thus sacrificing safety for the sake of efficiency.
Bearing in mind that the classes Bounded and Unbounded have practically identical external protocols, and hence that their functional properties are in many respects similar, one might suppose that the implementation would also be similar. However, the difference in the internal representation of the classes leads to substantially different space/time semantics. Manipulations with the nodes of a linked list, for example, are carried out very quickly, but the procedure of finding the required element will take time of order O(n). Therefore our representation caches the last node that was accessed, in the hope that the next access will be either to this same node or to its neighbors. The scheme based on arrays, on the other hand, gives low performance (in the worst case of order O(n/2) if the element is located in the middle of the array) when adding or removing elements, but ensures a high search speed (of order O(1)).
Memory management
The problem of memory management arises for the unbounded forms of implementation. In this case the developer of the library must define the policy for allocating and freeing memory from the heap when carrying out operations on nodes. The naive approach simply uses the global functions new and delete, which cannot ensure sufficient performance of the system. In addition, on some computer platforms memory management is extremely complicated (for example, in the presence of a segmented address space in some personal computer operating systems) and requires the development of a special strategy tightly bound to a particular operating environment. For our library we must clearly single out a memory management subsystem.
Figure 9-5 shows the memory management mechanism chosen for this library [A historical note: it took about four iterations of the library's architecture to arrive at precisely this mechanism, which - not surprisingly - turned out to be the simplest. The previous variants, which we ultimately rejected, were insufficiently flexible, hard to explain, and tended to impose implementation details on clients that were indifferent to them]. Let us consider the scenario that this diagram illustrates:
Figure 9-5. The memory management mechanism.
By passing StorageManager as an argument to all the unbounded structures, we clearly separate the policy of organizing access to memory from its implementation and give users the ability to add their own memory management concepts to a program without changing the content of the library. This is a classic example of how openness of a software system can be achieved through instantiation, without resorting to inheritance.
The only requirement imposed on the variants of StorageManager consists in the necessity of preserving a single protocol. In particular, they must all contain the public member functions allocate and deallocate, intended respectively for allocating and freeing memory. Let us consider as an example the simplest variant of such a class:
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&) {}
};
Note the idiom that is used so that the user cannot copy, assign, and compare instances of this class.
The protocol of the class Unmanaged is implemented through inline calls to the global operators new and delete. We named this abstraction Unmanaged, requiring no management, since it in fact represents nothing new but simply repeats an already existing system mechanism. Another abstraction, implementing a far more efficient algorithm, is called managed. In accordance with this algorithm, memory for nodes is allocated from a certain common pool of memory. If a node is not in use, it is marked as free. If the need arises for a new node, one from the free list is used. The allocation of new memory from the heap occurs only in the case where this list is empty. In this way it is often possible to avoid calling on the operating system's service functions: allocating memory reduces merely to manipulating pointers, which is far faster [In the C++ language the global operator new one way or another calls some variant of the function malloc - a rather expensive operation].
If desired, our mechanism can be improved further, for example by introducing a new operation for allocating memory in advance, before it is needed. And conversely, in certain situations, when there become too many unused areas, one can defragment the pool and return the freed memory to the heap. One can provide an operation allowing the user to define the size of the memory cluster and thus tune the class to a particular application.
In accordance with the considerations given above, the corresponding support class can be defined as follows:
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* head;
Chunk* unusedChunks;
size_t repChunkSize;
size_t usableChunkSize;
Chunk* getChunk(size_t s);
};
The declaration contains two nested classes, Element and Chunk. Each instance of the class Pool manages a linked list of Chunk objects, which represent chunks of "raw" memory but are treated as linked lists of Element instances (this is one of the important aspects managed by the class Pool). Each chunk may be allocated to elements of different sizes, and for efficiency we sort the list of chunks in order of increasing size. The memory manager may be defined as follows:
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&) {}
};
This class has the same external protocol as Unmanaged. Because templates in C++ are deliberately underspecified, conformance to this protocol is checked only when an instantiated class of type UnboundedQueue is compiled, at the moment when a concrete class is matched against the formal argument StorageManager.
The Pool object belonging to the class Managed is static. This allows several concrete structures (that require management) to share a single memory pool among themselves. Various structures that do not require management may, of course, define their own manager and their own memory pool, thus giving the developer full control over the memory allocation policy.
Figure 9-6. Memory management classes.
Figure 9-6 shows a class diagram illustrating how the various classes that provide memory management collaborate. We have shown only the association between the class Managed and its clients Unbounded and UnboundedQueue; this association will be refined when the classes are actually instantiated.
The physical layout of the support classes is also part of the architectural decision. Figure 9-7 illustrates their module architecture. We chose this particular scheme in order to isolate the classes that are apparently most likely to change.
Figure 9-7. Memory management modules.
Exceptions
Although C++ can be made to enforce many static assumptions (whose violation results in a compilation error), other mechanisms must be used to detect dynamic violations (such as an attempt to add an element to a completely full bounded queue, or to remove an element from an empty list). This library uses the exception handling facilities provided by C++ [14]. Our architecture includes a hierarchy of exception classes and, separately from it, a number of mechanisms for detecting such situations.
Let us begin with the base class Exception, which has a simple protocol:
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:
...
};
Each exceptional situation can be associated with the name of its source and the reason it arose. In addition, we can provide facilities, hidden from clients, for writing information about the error to an appropriate stream.
An analysis of the various classes of our library suggests the possible kinds of exceptions, which can be cast as subclasses of the base class Exception:
The declaration of the class overflow may look as follows:
class Overflow : public Exception {
public:
Overflow(const char* who, const char* what)
: Exception("Overflow", who, what) {}
};
The only responsibility of this class is to know its own name, which it passes to the constructor of its superclass.
In this mechanism, the member functions of the library classes only raise exceptions; they are not in a position to catch an exception, mainly because none of them can respond meaningfully to the situation. By convention, we raise an exception when the conditions assumed about some state are violated. A condition is an ordinary Boolean expression that must be true under normal circumstances. To simplify the library, we introduced the following function, which does not belong to any of the classes:
inline void _assert(int expression, const Exception& exception)
{
if (!expression)throw(exception);
}
For efficiency we defined this function as inline. The advantage of such a scheme is that it localizes all exceptions (in C++ throw has the syntax of a function call). Thus, for compilers that still do not support exceptions, one can use a special directive (-D for most C++ compilers) to redefine the call to throw into a call to another non-member function that writes a message to the screen and halts execution of the program:
void _catch(const Exception& e)
{
cerr << "EXCEPTION: ";
e.display();
exit(1);
}
Consider the implementation of the function insert of the class Bounded:
template
void Bounded::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;
}
Provision is made for the function to check during execution that the size of the structure does not exceed the maximum allowed. If it does, the Overflow exception is raised.
The most important advantage of this approach is the guarantee that the state of the object that raised the exception will not be corrupted (apart from the case of running out of main memory, when nothing can be done anyway). Every function, before performing actions capable of changing the state of the object, checks the assumption. In the insert function shown above, for example, before adding an element to the array we first call a selector (which cannot cause a change in the object's state), then check all of the function's preconditions, and only then change the state of the object. We have scrupulously adhered to this style in implementing all functions, and we strongly advise not departing from it when constructing subclasses based on our library.
Figure 9-8 illustrates how the classes that implement the exception handling mechanism collaborate.
Figure 9-8. Exception handling classes.
Iteration
Iteration is yet another architectural pattern of our library. In Chapter 3 it was already noted that an iterator is an operation that provides sequential access to all the parts of an object. It turns out that such a mechanism is needed not only by users; it is also necessary in the implementation of the library itself, in particular of its base classes.
Here we faced a choice: we could define iteration as part of the protocol of the objects, or create separate objects responsible for iteratively traversing other structures. We chose the second approach for two reasons:
Two forms of iteration are defined for each structure. An active iterator requires the client to explicitly invoke it each time in order to advance to the next element. A passive iterator applies a function supplied by the client and thus requires less participation from the client. To ensure type safety, each structure has its own iterators.
Consider as an example the active iterator for the class Queue:
template
class QueueActiveIterator {
public:
QueueActiveIterator(const Queue&);
~QueueActiveIterator();
The passive iterator implements an "apply" function. This idiom is commonly used in functional programming languages.
void reset();
int next();
int isDone() const;
const Item* currentItem() const;
protected:
const Queue& queue;
int index;
};
Each iterator is associated with a particular object at the moment it is created. Iteration begins at the "top" of the structure, whatever that means for the given abstraction.
Using the function currentItem, the client can gain access to the current element; the returned pointer may be null if the iteration has completed or if the array is empty. Advancing to the next element of the sequence happens after calling the function next (which returns 0 if further movement is impossible, as a rule because the iteration has completed). The selector isDone serves to obtain information about the state of the process: it returns 0 if the iteration has completed or the structure is empty. The function reset makes it possible to perform an unlimited number of iteration passes over the object.
For example, given the following declaration:
BoundedQueue eventQueue;
a fragment of code that uses an active iterator to visit every element of the queue would look like this:
QueueActiveIterator iter(eventQueue);
while (!iter.isDone()) {
iter.currentItem()->dispatch();
iter.next();
}
The iteration diagram shown in Figure 9-9 illustrates this scenario and, in addition, reveals some details of the iterator's implementation. Let us examine them more closely.
The constructor of the class QueueActiveIterator first establishes the connection between the iterator and a particular queue. It then calls the protected function cardinality, which determines the number of elements in the queue. Thus, the constructor may be described as follows:
template
QueueActiveIterator::QueueActiveIterator(const Queue& q)
:queue(q), index(q.cardinality() ? 0 : -1) {}
The class QueueActiveIterator has access to the protected function cardinality of the class Queue because it is among its friends.
The iterator operation isDone checks whether the current index falls within the allowable range, which is determined by the number of elements in the queue:
Figure 9-9. The iteration mechanism.
template
int QueueActiveIterator::isDone() const
{
return ((index < 0) || (index >= queue.cardinality()));
}
The function currentItem returns a pointer to the element at which the iterator has stopped. Implementing the iterator as an index of the object within the queue makes it easy to add and remove elements from the queue during iteration:
template
const Item* QueueActiveIterator::currentItem() const
{
return isDone() ? 0 : &queue.itemAt(index);
}
In performing this operation the iterator again calls a protected function of the queue, this time itemAt. Incidentally, currentItem can be used to work with both bounded and unbounded queues. For a bounded queue, itemAt simply returns the array element at the corresponding index. For an unbounded queue, the operation itemAt will traverse the linked list. However, as we recall, the class Unbounded stores information about the last element that was accessed, so moving to the element following it (which is what happens as the iterator advances) will be quite simple.
The operation next increments the value of the current index by one, which corresponds to advancing to the next element of the queue, and then checks whether the new index value is valid:
template
int QueueActiveIterator::next()
{
index++;
return !isDone();
}
Thus, in the course of its work the iterator calls two protected functions of the class Queue: cardinality and itemAt. By defining these functions as pure virtual, we delegated responsibility for their specific optimal implementation to the classes derived from Queue.
It was noted earlier that one of the main goals of our architectural decisions is to enable the client to copy, assign, and test for equality instances of an abstract base class, even if they have different representations. This capability is achieved through the use of iterators and certain utility functions that make it possible to traverse structures independently of their representation. For example, the assignment operator for the class Queue can be defined as follows:
template
Queue& Queue::operator=(const Queue& q)
{
if (this == &q) return *this;
((Queue&)q).lock();
purge();
QueueActiveIterator iter(q);
while (!iter.isDone()) {add(*iter.currentItem());}
iter.next();
((Queue&)q).unlock();
return *this;
}
This algorithm uses the locking idiom, which is examined in more detail in the following section.
Assignment is carried out in the order in which the active iterator traverses the structure denoted by the argument q. First the protected utility function purge empties the queue, and then new elements are added to it one after another with the help of another protected utility function, add. The fact that the iteration process is carried out by means of polymorphic functions makes it possible to copy, assign, and test for equality objects that have the same structure but different representations.
A passive iterator, also called an applicator, is characterized by the fact that it applies a particular function to each element of the structure. For the class Queue, a passive iterator can be defined as follows:
template
class QueuePassiveIterator {
public:
QueuePassiveIterator(const Queue&);
~QueuePassiveIterator();
int apply(int (*)(const Item&));
protected:
const Queue& queue;
};
A passive iterator acts on all the elements of the structure in (logically) a single operation. Thus, the function apply performs the same operation on each element of the structure in turn, until the function passed to the iterator returns zero or until the end of the structure is reached (in the first case the function apply will itself return zero to indicate that the iteration was not completed).
In developing any general-purpose tool, the problems associated with organizing concurrent processes must be taken into account. In operating systems such as UNIX, OS/2, and Windows NT, applications can start several "lightweight" processes [A "lightweight" process is one that executes in the same address space as others. In contrast to them there exist "heavyweight" processes; these are created, for example, by the fork function in UNIX. Heavyweight processes require special operating system support to organize communication among themselves. For C++, the AT&T library offers a "semi-portable" abstraction of lightweight processes for UNIX. Lightweight processes are directly available in OS/2 and Windows NT. The Smalltalk class library includes a class Process that implements support for lightweight processes]. In most cases classes simply will not be able to work in such an environment without special reworking: when two tasks interact with the same object, they must do so in a coordinated way so as not to corrupt the object's state. As already noted, there are two approaches to the task of managing processes; they are reflected in the existence of the guarded and synchronized forms of a class.
In developing this library the following assumption was made: developers who plan to use concurrent processes must import or develop themselves at least a class Semaphore for synchronizing lightweight processes. Developers who do not want to get involved with concurrent processes will be free of the need to support guarded or synchronized forms of classes (so no additional overhead will be required). The guarded and synchronized forms are isolated within the library and rely on their own internal implementation of concurrency. The only dependency on the local implementation is concentrated in the class Semaphore, which has the following interface:
class Semaphore {
public:
Semaphore();
Semaphore(const Semaphore&);
Semaphore(unsigned int count);
~Semaphore();
void seize(); // seize
void release(); // release
unsigned int nonePending() const;
protected:
};
Just as with memory management, we separate the process synchronization policy from its implementation. For this reason, the template arguments for each guarded form include a class Guard, which is responsible for the connection with the local implementation of the class Semaphore or its equivalent. The template arguments for each of the synchronized forms contain a class Monitor, which is close in its functional properties to the class Semaphore but, as will be seen later, provides a higher degree of process concurrency.
As shown in Figure 9-3, a guarded class is a direct subclass of its concrete bounded or unbounded class and contains within itself an object of the class Guard. All guarded classes have the public member functions seize and release, which make it possible to obtain exclusive access to the object. Consider as an example the class GuardedUnboundedQueue, derived from UnboundedQueue:
template
class GuardedUnboundedQueue : public UnboundedQueue {
public:
GuardedUnboundedQueue();
virtual ~GuardedUnboundedQueue();
virtual void seize();
virtual void release();
protected:
Guard guard;
};
Our library provides the interface of one of the predefined guard classes: the class Semaphore. Users can supplement the implementation of this class in accordance with the local definition of a lightweight process.
Figure 9-10 shows how this variant of synchronization works; clients that use guarded objects must follow a simple algorithm: first seize the object for exclusive access, perform the required work on it, and when finished release the guard (including in those cases where an exceptional situation has arisen). Any other behavior is regarded as socially unacceptable, since the claims of one agent will prevent others from working correctly. If, for example, we fail to release the guard after finishing work with the object, no one else will be able to gain access to it; an attempt to release the guard on an object to which no one currently had exclusive access may also lead to undesirable consequences. Ignoring this protocol is simply irresponsible, since it may corrupt the state of an object with which several agents are working simultaneously.
Figure 9-10. Processes of the guarded mechanism.
The main advantage of the guarded scheme is its simplicity. At the same time, for agents performing operations on the same object, using this model entails the need to carry out certain collective actions. Another feature of the guarded forms is that they give agents the ability to mark out critical moments, when several operations performed on an object will be guaranteed to be interpreted as one atomic transaction.
Like the memory management mechanism, the template signature of the guarded form imports the guard rather than making it an immutable characteristic. This allows users to introduce a new synchronization policy. When the predefined class Semaphore is used as the guard, the standard synchronization policy implies that each object is associated with its own semaphore. This solution is acceptable only as long as the number of concurrent processes does not reach some critical value.
An alternative approach implies the possibility of a single semaphore serving several guarded objects at once. To do this the developer need only create a new guard class having the same protocol as Semaphore (but not necessarily being its subclass). This class may contain a semaphore as a static member; the semaphore will then be shared by all instances of the class. By instantiating a guarded form with this new guard, the library developer introduces a new policy, since all objects of the instantiated class use a common guard instead of each object being allotted a separate guard. The advantage of this scheme becomes most apparent when the new guard class is used to instantiate other structures: all the resulting objects will work with one and the same guard. Thus a seemingly insignificant change of policy leads not only to a reduction in the number of concurrent processes, but also allows the client to lock an entire group of objects that are not directly related. Seizing one object automatically blocks access to all the other structures that have the same guard, even if these are structures of different types.
A synchronized class, being a direct subclass of some concrete bounded or unbounded class, contains within itself a monitor object, whose protocol can be described by the following abstract base class:
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:
...
};
With monitors, two kinds of synchronization can be implemented:
| ® Single | Guarantees the semantics of the structure in the presence of several threads of control, but with one reader or one writer. |
| ® Multiple | Guarantees the semantics of the structure in the presence of several threads of control, with several readers or one writer. |
A writing agent changes the state of the object; writing agents call modifier functions. A reading agent preserves the state of the object; it calls only selector functions. As can be seen, the multiple form of synchronization provides the highest degree of process concurrency. We can implement both policies as subclasses of the abstract base class Monitor. Both forms can be built on the basis of the class Semaphore.
Unlike the guarded forms, synchronized classes contain no additional member functions compared with their superclass: they simply override all the virtual functions of the superclass. The semantics introduced by a synchronized class causes each such function to be treated as an atomic transaction. Whereas clients of a guarded object must explicitly seize and release access each time in order to obtain exclusive access, synchronized forms provide exclusivity of access without requiring any special actions on the part of their clients.
This is achieved with the help of a locking mechanism, whose operation is shown in Figure 9-11. The collaboration of monitors with instances of the predefined classes ReadLock and WriteLock ensures the exclusivity of every member function call. In this mechanism the lock uses either a semaphore or a monitor as the agent responsible for the synchronization process, while the lock itself is responsible for seizing this agent upon creation and releasing it upon destruction. As an example, consider the definition of the class ReadLock:
class ReadLock {
public:
ReadLock (const Monitor& m) : monitor(m) { monitor.seizeForReading(); }
~ReadLock() { monitor.releaseFromReading(); }
private:
Monitor& monitor;
};
Figure 9-11. The locking mechanism.
By defining the lock and its monitor as two separate abstractions, we gave the client the ability to use different locking policies. The description of the class WriteLock is analogous, the only difference being that it uses the monitor's protocol for writing.
The definitions of all the member functions of a synchronized class use locks to "wrap" the operations inherited from the superclass. Consider as an example the implementation of the function length for a synchronized unbounded queue:
template
unsigned int SynchronizedUnboundedQueue
Monitor>::length() const
{
ReadLock lock(monitor);
return UnboundedQueue::length();
}
This fragment of code illustrates the mechanism shown in Figure 9-11. As a rule, objects of the class ReadLock are used for all synchronized selectors, and instances of WriteLock for synchronized modifiers. The simplicity and elegance of such an architecture is manifested in the fact that each function represents a complete operation that in any case guarantees the integrity of the object's state, and does so without any explicit actions on the part of the reading/writing agents.
Indeed, clients working with synchronized objects need not follow any special sequence of actions, since the process synchronization mechanism is supported here implicitly. This eliminates the appearance of errors such as incorrect locking. The developer should, however, prefer the guarded form to the synchronized one when several function calls must be cast as an atomic transaction; the synchronized form can guarantee atomicity only of individual member functions.
Our architecture ensures that synchronized forms are free of "deadly embrace" situations. For example, assigning an object to itself or comparing it with itself is potentially dangerous, since it requires locking both the left and the right elements of the expression, which in this case are one and the same object. Once created, an object cannot change its identity, so tests for self-identity are performed before any object is locked. That is precisely why the assignment operator operator= described earlier included such a check, as the following abbreviated listing shows:
template
Queue& Queue::operator=(const Queue& q)
{
if (this == &q) return *this;
}
Any member functions among whose arguments there are instances of the class to which they belong must be designed so that a correct locking scheme for these arguments is ensured. Our solution is based on the polymorphism of two utility functions, lock and unlock, defined in every abstract base class. By default, every abstract base class contains a stub for these two functions; the synchronized forms provide the seizing and releasing of the argument. That is why the assignment operator operator= described earlier included calls to these two functions, as the following abbreviated listing shows:
template
Queue& Queue::operator=(const Queue& q)
{
((Queue&)q).lock();
((Queue&)q).unlock();
return *this;
}
An explicit type cast is used in this case in order to get rid of the const restriction on the argument.
Comments