Thinking In C++. Volume 2: Practical Programming

The other way to get runtime information for an object is through the typeid operator. This operator returns an object of class type_info, which yields information about the type of object to which it was applied. If the type is polymorphic, it gives information about the most derived type that applies (the dynamic type); otherwise it yields static type information. One use of the typeid operator is to get the name of the dynamic type of an object as a const char*, as you can see in the following example^.

//: C08:TypeInfo.cpp

// Illustrates the typeid operator

#include

#include

using namespace std;

struct PolyBase {virtual ~PolyBase(){}};

struct PolyDer : PolyBase {};

struct NonPolyBase {};

struct NonPolyDer : NonPolyBase {NonPolyDer(int){}};

int main() {

// Test polymorphic Types

const PolyDer pd;

const PolyBase* ppb = &pd;

cout << typeid(ppb).name() << endl;

cout << typeid(*ppb).name() << endl;

cout << boolalpha << (typeid(*ppb) == typeid(pd))

<< endl;

cout << (typeid(PolyDer) == typeid(const PolyDer))

<< endl;

// Test non-polymorphic Types

const NonPolyDer npd(1);

const NonPolyBase* nppb = &npd;

cout << typeid(nppb).name() << endl;

cout << typeid(*nppb).name() << endl;

cout << (typeid(*nppb) == typeid(npd))

<< endl;

// Test a built-in type

int i;

cout << typeid(i).name() << endl;

} ///:~

The output from this program is

struct PolyBase const *

struct PolyDer

true

true

struct NonPolyBase const *

struct NonPolyBase

false

int

The first output line just echoes the static type of ppb because it is a pointer. To get RTTI to kick in, you need to look at the object a pointer or reference is connected to, which is illustrated in the second line. Notice that RTTI ignores top-level const and volatile qualifiers. With non-polymorphic types, you just get the static type (the type of the pointer itself). As you can see, built-in types are also supported^.

It turns out that you can’t store the result of a typeid operation in a type_info object, because there are no accessible constructors and assignment is disallowed; you must use it as we have shown. In addition, the actual string returned by type_info::name( ) is compiler dependent. Some compilers return "class C" instead of just "C", for instance, for a class named C. Applying typeid to an expression that dereferences a null pointer will cause a bad_typeid exception (also defined in ) to be thrown^.

The following example shows that the class name that type_info::name( ) returns is fully qualified^.

//: C08:RTTIandNesting.cpp

#include

#include

using namespace std;

class One {

class Nested {};

Nested* n;

public:

One() : n(new Nested) {}

~One() { delete n; }

Nested* nested() { return n; }

};

int main() {

One o;

cout << typeid(*o.nested()).name() << endl;

} ///:~

Since Nested is a member type of the One class, the result is One::Nested^.

You can also ask a type_info object if it precedes another type_info object in the implementation-defined "collation sequence" (the native ordering rules for text), using before(type_info&), which returns true or false. When you say,^.

if(typeid(me).before(typeid(you))) // ...

you’re asking if me occurs before you in the current collation sequence. This is useful should you use type_info objects as keys^.

Casting to intermediate levels

As you saw in the earlier program that used the hierarchy of Security classes, dynamic_cast can detect both exact types and, in an inheritance hierarchy with multiple levels, intermediate types. Here is another example.

//: C08:IntermediateCast.cpp

#include

#include

using namespace std;

class B1 {

public:

virtual ~B1() {}

};

class B2 {

public:

virtual ~B2() {}

};

class MI : public B1, public B2 {};

class Mi2 : public MI {};

int main() {

B2* b2 = new Mi2;

Mi2* mi2 = dynamic_cast(b2);

MI* mi = dynamic_cast(b2);

B1* b1 = dynamic_cast(b2);

assert(typeid(b2) != typeid(Mi2*));

assert(typeid(b2) == typeid(B2*));

delete b2;

} ///:~

This example has the extra complication of multiple inheritance (more on this later in this chapter). If you create an Mi2 and upcast it to the root (in this case, one of the two possible roots is chosen), the dynamic_cast back to either of the derived levels MI or Mi2 is successful^.

You can even cast from one root to the other:

B1* b1 = dynamic_cast(b2);

This is successful because B2 is actually pointing to an Mi2 object, which contains a subobject of type B1.

Casting to intermediate levels brings up an interesting difference between dynamic_cast and typeid. The typeid operator always produces a reference to a static typeinfo object that describes the dynamic type of the object. Thus, it doesn’t give you intermediate-level information. In the following expression (which is true), typeid doesn’t see b2 as a pointer to the derived type, like dynamic_cast does:

typeid(b2) != typeid(Mi2*)

The type of b2 is simply the exact type of the pointer:

typeid(b2) == typeid(B2*)

void pointers

RTTI only works for complete types, meaning that all class information must be available when typeid is used. In particular, it doesn’t work with void pointers:

//: C08:VoidRTTI.cpp

// RTTI & void pointers

//!#include

#include

using namespace std;

class Stimpy {

public:

virtual void happy() {}

virtual void joy() {}

virtual ~Stimpy() {}

};

int main() {

void* v = new Stimpy;

// Error:

//! Stimpy* s = dynamic_cast(v);

// Error:

//! cout << typeid(*v).name() << endl;

} ///:~

A void* truly means "no type information at all."[106]

Using RTTI with templates

Class templates work well with RTTI, since all they do is generate classes. As usual, RTTI provides a convenient way to obtain the name of the class you’re in. The following example prints the order of constructor and destructor calls^:

//: C08:ConstructorOrder.cpp

// Order of constructor calls

#include

#include

using namespace std;

template class Announce {

public:

Announce() {

cout << typeid(*this).name()

<< " constructor" << endl;

}

~Announce() {

cout << typeid(*this).name()

<< " destructor" << endl;

}

};

class X : public Announce<0> {

Announce<1> m1;

Announce<2> m2;

public:

X() { cout << "X::X()" << endl; }

~X() { cout << "X::~X()" << endl; }

};

int main() { X x; } ///:~

This template uses a constant int to differentiate one class from another, but type arguments would work as well. Inside both the constructor and destructor, RTTI information produces the name of the class to print. The class X uses both inheritance and composition to create a class that has an interesting order of constructor and destructor calls. The output is^:

Announce<0> constructor

Announce<1> constructor

Announce<2> constructor

X::X()

X::~X()

Announce<2> destructor

Announce<1> destructor

Announce<0> destructor

Because it allows you to discover type information from an anonymous polymorphic pointer, RTTI is ripe for misuse by the novice because RTTI may make sense before virtual functions do. For many people coming from a procedural background, it’s difficult not to organize programs into sets of switch statements. They could accomplish this with RTTI and thus lose the important value of polymorphism in code development and maintenance. The intent of C++ is that you use virtual functions throughout your code and that you only use RTTI when you must^.

However, using virtual functions as they are intended requires that you have control of the base-class definition because at some point in the extension of your program you may discover the base class doesn’t include the virtual function you need. If the base class comes from a library or is otherwise controlled by someone else, a solution to the problem is RTTI: you can derive a new type and add your extra member function. Elsewhere in the code you can detect your particular type and call that member function. This doesn’t destroy the polymorphism and extensibility of the program, because adding a new type will not require you to hunt for switch statements. However, when you add new code in the main body that requires your new feature, you’ll have to detect your particular type^.

Putting a feature in a base class might mean that, for the benefit of one particular class, all the other classes derived from that base require some meaningless stub for a pure virtual function. This makes the interface less clear and annoys those who must redefine pure virtual functions when they derive from that base class^.

Finally, RTTI will sometimes solve efficiency problems. If your code uses polymorphism in a nice way, but it turns out that one of your objects reacts to this general-purpose code in a horribly inefficient way, you can pick that type out using RTTI and write case-specific code to improve the efficiency^.

A trash recycler

To further illustrate a practical use of RTTI, the following program simulates a trash recycler. Different kinds of "trash" are inserted into a single container and then later sorted according to their dynamic types^.

//: C08:Recycle.cpp

// A Trash Recycler

#include

#include

#include

#include

#include

#include "../purge.h"

using namespace std;

class Trash {

float _weight;

public:

Trash(float wt) : _weight(wt) {}

virtual float value() const = 0;

float weight() const { return _weight; }

virtual ~Trash() { cout << "~Trash()\n"; }

};

class Aluminum : public Trash {

static float val;

public:

Aluminum(float wt) : Trash(wt) {}

float value() const { return val; }

static void value(float newval) {

val = newval;

}

};

float Aluminum::val = 1.67;

class Paper : public Trash {

static float val;

public:

Paper(float wt) : Trash(wt) {}

float value() const { return val; }

static void value(float newval) {

val = newval;

}

};

float Paper::val = 0.10;

class Glass : public Trash {

static float val;

public:

Glass(float wt) : Trash(wt) {}

float value() const { return val; }

static void value(float newval) {

val = newval;

}

};

float Glass::val = 0.23;

// Sums up the value of the Trash in a bin:

template

void sumValue(Container& bin, ostream& os) {

typename Container::iterator tally =

bin.begin();

float val = 0;

while(tally != bin.end()) {

val += (*tally)->weight() * (*tally)->value();

os << "weight of "

<< typeid(**tally).name()

<< " = " << (*tally)->weight() << endl;

tally++;

}

os << "Total value = " << val << endl;

}

int main() {

srand(time(0)); // Seed random number generator

vector bin;

// Fill up the Trash bin:

for(int i = 0; i < 30; i++)

switch(rand() % 3) {

case 0 :

bin.push_back(new Aluminum((rand() % 1000)/10.0));

break;

case 1 :

bin.push_back(new Paper((rand() % 1000)/10.0));

break;

case 2 :

bin.push_back(new Glass((rand() % 1000)/10.0));

break;

}

// Note: bins hold exact type of object, not base type:

vector glassBin;

vector paperBin;

vector alumBin;

vector::iterator sorter = bin.begin();

// Sort the Trash:

while(sorter != bin.end()) {

Aluminum* ap =

dynamic_cast(*sorter);

Paper* pp =

dynamic_cast(*sorter);

Glass* gp =

dynamic_cast(*sorter);

if(ap) alumBin.push_back(ap);

else if(pp) paperBin.push_back(pp);

else if(gp) glassBin.push_back(gp);

sorter++;

}

sumValue(alumBin, cout);

sumValue(paperBin, cout);

sumValue(glassBin, cout);

sumValue(bin, cout);

purge(bin);

} ///:~

The nature of this problem is that the trash is thrown unclassified into a single bin, so the specific type information is "lost." But later the specific type information must be recovered to properly sort the trash, and so RTTI is used^.

We can do even better by using a map that associates pointers to type_info objects with a vector of Trash pointers. Since a map requires an ordering predicate, we provide one named TInfoLess that calls type_info::before( ). As we insert Trash pointers into the map, they are associated automatically with their type_info key^.

//: C08:Recycle2.cpp

// A Trash Recycler

#include

#include

#include

#include

#include

#include

#include

#include "../purge.h"

using namespace std;

class Trash {

float wt;

public:

Trash(float wt) : wt(wt) {}

virtual float value() const = 0;

float weight() const { return wt; }

virtual ~Trash() { cout << "~Trash()\n"; }

};

class Aluminum : public Trash {

static float val;

public:

Aluminum(float wt) : Trash(wt) {}

float value() const { return val; }

static void value(float newval) {

val = newval;

}

};

float Aluminum::val = 1.67;

class Paper : public Trash {

static float val;

public:

Paper(float wt) : Trash(wt) {}

float value() const { return val; }

static void value(float newval) {

val = newval;

}

};

float Paper::val = 0.10;

class Glass : public Trash {

static float val;

public:

Glass(float wt) : Trash(wt) {}

float value() const { return val; }

static void value(float newval) {

val = newval;

}

};

float Glass::val = 0.23;

// Comparator for type_info pointers

struct TInfoLess {

bool operator()(const type_info* t1, const type_info* t2)

const {

return t1->before(*t2);

}

};

typedef map, TInfoLess>

TrashMap;

// Sums up the value of the Trash in a bin:

void sumValue(const TrashMap::value_type& p, ostream& os) {

vector::const_iterator tally = p.second.begin();

float val = 0;

while(tally != p.second.end()) {

val += (*tally)->weight() * (*tally)->value();

os << "weight of "

<< p.first->name() // type_info::name()

<< " = " << (*tally)->weight() << endl;

tally++;

}

os << "Total value = " << val << endl;

}

int main() {

srand(time(0)); // Seed random number generator

TrashMap bin;

// Fill up the Trash bin:

for(int i = 0; i < 30; i++) {

Trash* tp;

switch(rand() % 3) {

case 0 :

tp = new Aluminum((rand() % 1000)/10.0);

break;

case 1 :

tp = new Paper((rand() % 1000)/10.0);

break;

case 2 :

tp = new Glass((rand() % 1000)/10.0);

break;

}

bin[&typeid(*tp)].push_back(tp);

}

// Print sorted results

for(TrashMap::iterator p = bin.begin();

p != bin.end(); ++p) {

sumValue(*p, cout);

purge(p->second);

}

} ///:~

We’ve modified sumValue( ) to call type_info::name( ) directly, since the type_info object is now available there as the first member of the TrashMap::value_type pair. This avoids the extra call to typeid to get the name of the type of Trash being processed that was necessary in the previous version of this program^.

Possibly the simplest design pattern is the Singleton, which is a way to provide one and only one instance of a class. For example, if a class controls a Singleton resource, you only want to allow one instance of that class. The following program shows how to implement a Singleton object in C++:

//: C10:SingletonPattern.cpp

#include

using namespace std;

class Singleton {

static Singleton s;

int i;

Singleton(int x) : i(x) { }

Singleton& operator=(Singleton&); // Disallowed

Singleton(const Singleton&); // Disallowed

public:

static Singleton& instance() {

return s;

}

int getValue() { return i; }

void setValue(int x) { i = x; }

};

Singleton Singleton::s(47);

int main() {

Singleton& s = Singleton::instance();

cout << s.getValue() << endl;

Singleton& s2 = Singleton::instance();

s2.setValue(9);

cout << s.getValue() << endl;

} ///:~

The key to creating a Singleton is to prevent the client programmer from having any control over the lifetime of the object. To do this, declare all constructors private, and prevent the compiler from implicitly generating any constructors. Note that the copy constructor and assignment operator are declared private to prevent any sort of copies being made^.

You must also decide how you’re going to create the object. Here, it’s created statically, but you can also wait until the client programmer asks for one and create it on demand. This is called lazy initialization, and it only makes sense if your object is expensive to create and if it might not always be needed.

If you return a pointer instead of a reference, the user could inadvertently delete the pointer, so the implementation above is considered safest. In any case, the object should be stored privately.

You provide access through public member functions. Here, instance( ) produces a reference to the Singleton object. The rest of the interface (getValue( ) and setValue( )) is the regular class interface^.

Note that you aren’t restricted to creating only one object. This technique easily supports the creation of a limited pool of objects. In that situation, however, you can be confronted with the problem of sharing objects in the pool. If this is an issue, you can create a solution involving a check-out and check-in of the shared objects^.

Variations on Singleton

Any static member object inside a class is an expression of Singleton: one and only one will be made. So in a sense, the language has direct support for the idea; we certainly use it on a regular basis. However, a problem is associated with static objects (member or not), and that’s the order of initialization, as described in Volume 1 of this book. If one static object depends on another, it’s important that the objects are initialized in the correct order^.

In Volume 1, you were shown how to control initialization order by defining a static object inside a function. This delays the initialization of the object until the first time the function is called. If the function returns a reference to the static object, it gives you the effect of a Singleton while removing much of the worry of static initialization. For example, suppose you want to create a log file upon the first call to a function that returns a reference to that log file. This header file will do the trick^:

//: C10:LogFile.h

#ifndef LOGFILE_H

#define LOGFILE_H

#include

std::ofstream& logfile();

#endif // LOGFILE_H ///:~

The implementation must not be inlined, because that would mean that the whole function, including the static object definition within, could be duplicated in any translation unit where it’s included, which violates C++’s one-definition rule.[117] This would most certainly foil the attempts to control the order of initialization (but potentially in a subtle and hard-to-detect fashion). So the implementation must be separate^:

//: C10:LogFile.cpp {O}

#include "LogFile.h"

std::ofstream& logfile() {

static std::ofstream log("Logfile.log");

return log;

} ///:~

Now the log object will not be initialized until the first time logfile( ) is called. So if you create a function^:

//: C10:UseLog1.h

#ifndef USELOG1_H

#define USELOG1_H

void f();

#endif // USELOG1_H ///:~

that uses logfile() in its implementation:

//: C10:UseLog1.cpp {O}

#include "UseLog1.h"

#include "LogFile.h"

void f() {

logfile() << __FILE__ << std::endl;

} ///:~

And you use logfile() again in another file:

//: C10:UseLog2.cpp

//{L} LogFile UseLog1

#include "UseLog1.h"

#include "LogFile.h"

using namespace std;

void g() {

logfile() << __FILE__ << endl;

}

int main() {

f();

g();

} ///:~

the log object doesn’t get created until the first call to f( ).

You can easily combine the creation of the static object inside a member function with the Singleton class. SingletonPattern.cpp can be modified to use this approach:[118]

//: C10:SingletonPattern2.cpp

// Meyers’ Singleton

#include

using namespace std;

class Singleton {

int i;

Singleton(int x) : i(x) { }

void operator=(Singleton&);

Singleton(const Singleton&);

public:

static Singleton& instance() {

static Singleton s(47);

return s;

}

int getValue() { return i; }

void setValue(int x) { i = x; }

};

int main() {

Singleton& s = Singleton::instance();

cout << s.getValue() << endl;

Singleton& s2 = Singleton::instance();

s2.setValue(9);

cout << s.getValue() << endl;

} ///:~

An especially interesting case occurs if two Singletons depend on each other, like this:

//: C10:FunctionStaticSingleton.cpp

class Singleton1 {

Singleton1() {}

public:

static Singleton1& ref() {

static Singleton1 single;

return single;

}

};

class Singleton2 {

Singleton1& s1;

Singleton2(Singleton1& s) : s1(s) {}

public:

static Singleton2& ref() {

static Singleton2 single(Singleton1::ref());

return single;

}

Singleton1& f() { return s1; }

};

int main() {

Singleton1& s1 = Singleton2::ref().f();

} ///:~

When Singleton2::ref( ) is called, it causes its sole Singleton2 object to be created. In the process of this creation, Singleton1::ref( ) is called, and that causes the sole Singleton1 object to be created. Because this technique doesn’t rely on the order of linking or loading, the programmer has much better control over initialization, leading to fewer problems^.

Yet another variation on Singleton allows you to separate the "Singleton-ness" of an object from its implementation. This is achieved through templates, using the Curiously Recurring Template Pattern mentioned in Chapter 5^.

//: C10:CuriousSingleton.cpp

// Separates a class from its Singleton-ness (almost)

#include

using namespace std;

template

class Singleton {

public:

static T& instance() {

static T theInstance;

return theInstance;

}

protected:

Singleton() {}

virtual ~Singleton() {}

private:

Singleton(const Singleton&);

Singleton& operator=(const Singleton&);

};

// A sample class to be made into a Singleton

class MyClass : public Singleton {

int x;

protected:

friend class Singleton;

MyClass(){x = 0;}

public:

void setValue(int n) { x = n; }

int getValue() const { return x; }

};

int main() {

MyClass& m = MyClass::instance();

cout << m.getValue() << endl;

m.setValue(1);

cout << m.getValue() << endl;

} ///:~

MyClass is made a Singleton by:

1. Making its constructor private or protected.

2. Making Singleton a friend.

3. Deriving MyClass from Singleton.

The self-referencing in step 3 may sound implausible, but as we explained in Chapter 5, it works because there is only a static data dependency on the template argument in the Singleton template. In other words, the code for the class Singleton can be instantiated by the compiler because it is not dependent on the size of MyClass. It’s only later, when Singleton::instance( ) is first called, that the size of MyClass is needed, and of course by then compilation of MyClass is complete and its size is known.[119]

It’s interesting how intricate implementing such a simple pattern as Singleton can be. We haven’t even addressed issues of thread safety, and yet many pages have elapsed since the beginning of this section. The last thing we wish to say about Singleton is that it should be used sparingly. True Singleton objects arise rarely, and the last thing a Singleton should be used for is to replace a global variable.[120]

Design Patterns discusses 23 patterns, classified under three purposes (all of which revolve around the particular aspect that can vary):

1.Creational: how an object can be created. This often involves isolating the details of object creation so your code isn’t dependent on what types of objects there are and thus doesn’t have to be changed when you add a new type of object. The aforementioned Singleton is classified as a creational pattern, and later in this chapter you’ll see examples of Factory Method^.

2.Structural: designing objects to satisfy particular project constraints. These affect the way objects are connected with other objects to ensure that changes in the system don’t require changes to those connections^.

3.Behavioral: objects that handle particular types of actions within a program. These encapsulate processes that you want to perform, such as interpreting a language, fulfilling a request, moving through a sequence (as in an iterator), or implementing an algorithm. This chapter contains examples of the Observer and the Visitor patterns^.

Design Patterns includes a section on each of its 23 patterns along with one or more examples for each, typically in C++ but sometimes in Smalltalk. This book will not repeat all the details of the patterns shown in Design Patterns since that book stands on its own and should be studied separately. The catalog and examples provided here are intended to rapidly give you a grasp of the patterns, so you can get a decent feel for what patterns are about and why they are so important^.

Features, idioms, patterns

Work is continuing beyond what is in the GoF book, of course; hence, there are more patterns and a more refined process on defining design patterns in general.[121] This is important because it is not easy to identify new patterns or to properly describe them. There is some confusion in the popular literature on what a design pattern is, for example. Patterns are not trivial nor are they typically represented by features that are built into a programming language. Constructors and destructors, for example, could be called the "guaranteed initialization and cleanup design pattern." These are important and essential constructs, but they’re routine language constructs and are not rich enough to be considered a design pattern^.

Another non-example comes from various forms of aggregation. Aggregation is a completely fundamental principle in object-oriented programming: you make objects out of other objects. Yet sometimes this idea is erroneously classified as a pattern. This is unfortunate because it pollutes the idea of the design pattern and suggests that anything that surprises you the first time you see it should be made into a design pattern^.

Yet another misguided example is found in the Java language; the designers of the JavaBeans specification decided to refer to the simple "get/set" naming convention as a design pattern (for example, getInfo( ) returns an Info property and setInfo( ) changes it). This is just a commonplace naming convention and in no way constitutes a design pattern^.

When you discover that you need to add new types to a system, the most sensible first step is to use polymorphism to create a common interface to those new types. This separates the rest of the code in your system from the knowledge of the specific types that you are adding. New types can be added without disturbing existing code … or so it seems. At first it would appear that you need to change the code in such a design only in the place where you inherit a new type, but this is not quite true. You must still create an object of your new type, and at the point of creation you must specify the exact constructor to use. Thus, if the code that creates objects is distributed throughout your application, you have the same problem when adding new types—you must still chase down all the points of your code where type matters. It happens to be the creation of the type that matters in this case rather than the use of the type (which is taken care of by polymorphism), but the effect is the same: adding a new type can cause problems^.

The solution is to force the creation of objects to occur through a common factory rather than to allow the creational code to be spread throughout your system. If all the code in your program must go through this factory whenever it needs to create one of your objects, all you must do when you add a new object is modify the factory. This design is a variation of the pattern commonly known as Factory Method. Since every object-oriented program creates objects, and since it’s likely you will extend your program by adding new types, factories may be the most useful of all design patterns^.

As an example, let’s revisit the Shape system. One approach to implementing a factory is to define a static member function in the base class:

//: C10:ShapeFactory1.cpp

#include

#include

#include

#include

#include "../purge.h"

using namespace std;

class Shape {

public:

virtual void draw() = 0;

virtual void erase() = 0;

virtual ~Shape() {}

class BadShapeCreation : public logic_error {

public:

BadShapeCreation(string type)

: logic_error("Cannot create type " + type)

{}

};

static Shape* factory(const string& type)

throw(BadShapeCreation);

};

class Circle : public Shape {

Circle() {} // Private constructor

friend class Shape;

public:

void draw() { cout << "Circle::draw\n"; }

void erase() { cout << "Circle::erase\n"; }

~Circle() { cout << "Circle::~Circle\n"; }

};

class Square : public Shape {

Square() {}

friend class Shape;

public:

void draw() { cout << "Square::draw\n"; }

void erase() { cout << "Square::erase\n"; }

~Square() { cout << "Square::~Square\n"; }

};

Shape* Shape::factory(const string& type)

throw(Shape::BadShapeCreation) {

if(type == "Circle") return new Circle;

if(type == "Square") return new Square;

throw BadShapeCreation(type);

}

char* shlist[] = { "Circle", "Square", "Square",

"Circle", "Circle", "Circle", "Square", "" };

int main() {

vector shapes;

try {

for(char** cp = shlist; **cp; cp++)

shapes.push_back(Shape::factory(*cp));

} catch(Shape::BadShapeCreation e) {

cout << e.what() << endl;

purge(shapes);

return 1;

}

for(size_t i = 0; i < shapes.size(); i++) {

shapes[i]->draw();

shapes[i]->erase();

}

purge(shapes);

} ///:~

The factory( ) function takes an argument that allows it to determine what type of Shape to create; it happens to be a string in this case, but it could be any set of data. The factory( ) is now the only other code in the system that needs to be changed when a new type of Shape is added. (The initialization data for the objects will presumably come from somewhere outside the system and will not be a hard-coded array as in the previous example.⁾

To ensure that the creation can only happen in the factory( ), the constructors for the specific types of Shape are made private, and Shape is declared a friend so that factory( ) has access to the constructors. (You could also declare only Shape::factory( ) to be a friend, but it seems reasonably harmless to declare the entire base class as a friend.⁾

Polymorphic factories

The static factory( ) member function in the previous example forces all the creation operations to be focused in one spot, so that’s the only place you need to change the code. This is certainly a reasonable solution, as it nicely encapsulates the process of creating objects. However, Design Patterns emphasizes that the reason for the Factory Method pattern is so that different types of factories can be derived from the basic factory. Factory Method is in fact a special type of polymorphic factory. However, Design Patterns does not provide an example, but instead just repeats the example used for the Abstract Factory. Here is ShapeFactory1.cpp modified so the Factory Methods are in a separate class as virtual functions^:

//: C10:ShapeFactory2.cpp

// Polymorphic Factory Methods

#include

#include

#include

#include

#include

#include "../purge.h"

using namespace std;

class Shape {

public:

virtual void draw() = 0;

virtual void erase() = 0;

virtual ~Shape() {}

};

class ShapeFactory {

virtual Shape* create() = 0;

static map factories;

public:

virtual ~ShapeFactory() {}

friend class ShapeFactoryInitializer;

class BadShapeCreation : public logic_error {

public:

BadShapeCreation(string type)

: logic_error("Cannot create type " + type)

{}

};

static Shape*

createShape(const string& id) throw(BadShapeCreation){

if(factories.find(id) != factories.end())

return factories[id]->create();

else

throw BadShapeCreation(id);

}

};

// Define the static object:

map

ShapeFactory::factories;

class Circle : public Shape {

Circle() {} // Private constructor

public:

void draw() { cout << "Circle::draw\n"; }

void erase() { cout << "Circle::erase\n"; }

~Circle() { cout << "Circle::~Circle\n"; }

private:

friend class ShapeFactoryInitializer;

class Factory;

friend class Factory;

class Factory : public ShapeFactory {

public:

Shape* create() { return new Circle; }

friend class ShapeFactoryInitializer;

};

};

class Square : public Shape {

Square() {}

public:

void draw() { cout << "Square::draw\n"; }

void erase() { cout << "Square::erase\n"; }

~Square() { cout << "Square::~Square\n"; }

private:

friend class ShapeFactoryInitializer;

class Factory;

friend class Factory;

class Factory : public ShapeFactory {

public:

Shape* create() { return new Square; }

friend class ShapeFactoryInitializer;

};

};

// Singleton to initialize the ShapeFactory:

class ShapeFactoryInitializer {

static ShapeFactoryInitializer si;

ShapeFactoryInitializer() {

ShapeFactory::factories["Circle"] =

new Circle::Factory;

ShapeFactory::factories["Square"] =

new Square::Factory;

}

~ShapeFactoryInitializer() {

delete ShapeFactory::factories["Circle"];

delete ShapeFactory::factories["Square"];

}

};

// Static member definition:

ShapeFactoryInitializer

ShapeFactoryInitializer::si;

char* shlist[] = { "Circle", "Square", "Square",

"Circle", "Circle", "Circle", "Square", "" };

int main() {

vector shapes;

try {

for(char** cp = shlist; **cp; cp++)

shapes.push_back(

ShapeFactory::createShape(*cp));

} catch(ShapeFactory::BadShapeCreation e) {

cout << e.what() << endl;

return 1;

}

for(size_t i = 0; i < shapes.size(); i++) {

shapes[i]->draw();

shapes[i]->erase();

}

purge(shapes);

} ///:~

Now the Factory Method appears in its own class, ShapeFactory, as the virtual create( ). This is a private member function, which means it cannot be called directly but can be overridden. The subclasses of Shape must each create their own subclasses of ShapeFactory and override the create( ) member function to create an object of their own type. These factories are private, so that they are only accessible from the main Factory Method. This way, all client code must go through the Factory Method in order to create objects^.

The actual creation of shapes is performed by calling ShapeFactory::createShape( ), which is a static member function that uses the map in ShapeFactory to find the appropriate factory object based on an identifier that you pass it. The factory is immediately used to create the shape object, but you could imagine a more complex problem in which the appropriate factory object is returned and then used by the caller to create an object in a more sophisticated way. However, it seems that much of the time you don’t need the intricacies of the polymorphic Factory Method, and a single static member function in the base class (as shown in ShapeFactory1.cpp) will work fine^.

Notice that the ShapeFactory must be initialized by loading its map with factory objects, which takes place in the Singleton ShapeFactoryInitializer. So to add a new type to this design you must define the type, create a factory, and modify ShapeFactoryInitializer so that an instance of your factory is inserted in the map. This extra complexity again suggests the use of a static Factory Method if you don’t need to create individual factory objects^.

Abstract factories

The Abstract Factory pattern looks like the factory objects we’ve seen previously, with not one but several Factory Methods. Each of the Factory Methods creates a different kind of object. The idea is that when you create the factory object, you decide how all the objects created by that factory will be used. The example in Design Patterns implements portability across various graphical user interfaces (GUIs): you create a factory object appropriate to the GUI that you’re working with, and from then on when you ask it for a menu, a button, a slider, and so on, it will automatically create the appropriate version of that item for the GUI. Thus, you’re able to isolate, in one place, the effect of changing from one GUI to another^.

As another example, suppose you are creating a general-purpose gaming environment and you want to be able to support different types of games. Here’s how it might look using an Abstract Factory^:

//: C10:AbstractFactory.cpp

// A gaming environment

#include

using namespace std;

class Obstacle {

public:

virtual void action() = 0;

};

class Player {

public:

virtual void interactWith(Obstacle*) = 0;

};

class Kitty: public Player {

virtual void interactWith(Obstacle* ob) {

cout << "Kitty has encountered a ";

ob->action();

}

};

class KungFuGuy: public Player {

virtual void interactWith(Obstacle* ob) {

cout << "KungFuGuy now battles against a ";

ob->action();

}

};

class Puzzle: public Obstacle {

public:

void action() { cout << "Puzzle\n"; }

};

class NastyWeapon: public Obstacle {

public:

void action() { cout << "NastyWeapon\n"; }

};

// The abstract factory:

class GameElementFactory {

public:

virtual Player* makePlayer() = 0;

virtual Obstacle* makeObstacle() = 0;

};

// Concrete factories:

class KittiesAndPuzzles :

public GameElementFactory {

public:

virtual Player* makePlayer() {

return new Kitty;

}

virtual Obstacle* makeObstacle() {

return new Puzzle;

}

};

class KillAndDismember :

public GameElementFactory {

public:

virtual Player* makePlayer() {

return new KungFuGuy;

}

virtual Obstacle* makeObstacle() {

return new NastyWeapon;

}

};

class GameEnvironment {

GameElementFactory* gef;

Player* p;

Obstacle* ob;

public:

GameEnvironment(GameElementFactory* factory) :

gef(factory), p(factory->makePlayer()),

ob(factory->makeObstacle()) {}

void play() {

p->interactWith(ob);

}

~GameEnvironment() {

delete p;

delete ob;

delete gef;

}

};

int main() {

GameEnvironment

g1(new KittiesAndPuzzles),

g2(new KillAndDismember);

g1.play();

g2.play();

}

/* Output:

Kitty has encountered a Puzzle

KungFuGuy now battles against a NastyWeapon */ ///:~

In this environment, Player objects interact with Obstacle objects, but the types of players and obstacles depend on the game. You determine the kind of game by choosing a particular GameElementFactory, and then the GameEnvironment controls the setup and play of the game. In this example, the setup and play are simple, but those activities (the initial conditions and the state change) can determine much of the game’s outcome. Here, GameEnvironment is not designed to be inherited, although it could possibly make sense to do that^.

This example also illustrates double dispatching, which will be explained later.

Virtual constructors

The Observer pattern solves a fairly common problem: what if a group of objects needs to update themselves when some other object changes state? This can be seen in the "model-view" aspect of Smalltalk’s MVC (model-view-controller) or the almost-equivalent "Document-View Architecture." Suppose that you have some data (the "document") and more than one view, say a plot and a textual view. When you change the data, the two views must know to update themselves, and that’s what the observer facilitates^.

Two types of objects are used to implement the observer pattern in the following code. The Observable class keeps track of everybody who wants to be informed when a change happens. The Observable class calls the notifyObservers( ) member function for each observer on the list. The notifyObservers( ) member function is part of the base class Observable^.

There are actually two "things that change" in the observer pattern: the quantity of observing objects and the way an update occurs. That is, the observer pattern allows you to modify both of these without affecting the surrounding code^.

You can implement the observer pattern in a number of ways, but the code shown here will create a framework from which you can build your own observer code, following the example. First, this interface describes what an observer looks like^:

//: C10:Observer.h

// The Observer interface

#ifndef OBSERVER_H

#define OBSERVER_H

class Observable;

class Argument {};

class Observer {

public:

// Called by the observed object, whenever

// the observed object is changed:

virtual void

update(Observable* o, Argument * arg) = 0;

};

#endif // OBSERVER_H ///:~

Since Observer interacts with Observable in this approach, Observable must be declared first. In addition, the Argument class is empty and only acts as a base class for any type of argument you want to pass during an update. If you want, you can simply pass the extra argument as a void*. You’ll have to downcast in either case^.

The Observer type is an "interface" class that only has one member function, update( ). This function is called by the object that’s being observed, when that object decides it’s time to update all its observers. The arguments are optional; you could have an update( ) with no arguments, and that would still fit the observer pattern. However this is more general—it allows the observed object to pass the object that caused the update (since an Observer may be registered with more than one observed object) and any extra information if that’s helpful, rather than forcing the Observer object to hunt around to see who is updating and to fetch any other information it needs^.

The "observed object" will be of type Observable:

//: C10:Observable.h

// The Observable class

#ifndef OBSERVABLE_H

#define OBSERVABLE_H

#include "Observer.h"

#include

class Observable {

bool changed;

std::set observers;

protected:

virtual void setChanged() { changed = true; }

virtual void clearChanged(){ changed = false; }

public:

virtual void addObserver(Observer& o) {

observers.insert(&o);

}

virtual void deleteObserver(Observer& o) {

observers.erase(&o);

}

virtual void deleteObservers() {

observers.clear();

}

virtual int countObservers() {

return observers.size();

}

virtual bool hasChanged() { return changed; }

// If this object has changed, notify all

// of its observers:

virtual void notifyObservers(Argument* arg = 0) {

if(!hasChanged()) return;

clearChanged(); // Not "changed" anymore

std::set::iterator it;

for(it = observers.begin();

it != observers.end(); it++)

(*it)->update(this, arg);

}

};

#endif // OBSERVABLE_H ///:~

Again, the design here is more elaborate than is necessary; as long as there’s a way to register an Observer with an Observable and a way for the Observable to update its Observers, the set of member functions doesn’t matter. However, this design is intended to be reusable. (It was lifted from the design used in the Java standard library.)[123]

The Observable object has a flag to indicate whether it’s been changed. In a simpler design, there would be no flag; if something happened, everyone would be notified. Notice, however, that the control of the flag’s state is protected so that only an inheritor can decide what constitutes a change, and not the end user of the resulting derived Observer class^.

The collection of Observer objects is kept in a set to prevent duplicates; the set insert( ), erase( ), clear( ), and size( ) functions are exposed to allow Observers to be added and removed at any time, thus providing runtime flexibility^.

Most of the work is done in notifyObservers( ). If the changed flag has not been set, this does nothing. Otherwise, it first clears the changed flag so that repeated calls to notifyObservers( ) won’t waste time. This is done before notifying the observers in case the calls to update( ) do anything that causes a change back to this Observable object. It then moves through the set and calls back to the update( ) member function of each Observer^.

At first it may appear that you can use an ordinary Observable object to manage the updates. But this doesn’t work; to get an effect, you must derive from Observable and somewhere in your derived-class code call setChanged( ). This is the member function that sets the "changed" flag, which means that when you call notifyObservers( ) all the observers will, in fact, get notified. Where you call setChanged( ) depends on the logic of your program^.

Now we encounter a dilemma. Objects that are being observed may have more than one such item of interest. For example, if you’re dealing with a GUI item—a button, say—the items of interest might be the mouse clicked the button, the mouse moved over the button, and (for some reason) the button changed its color. So we’d like to be able to report all these events to different observers, each of which is interested in a different type of event^.

The problem is that we would normally reach for multiple inheritance in such a situation: "I’ll inherit from Observable to deal with mouse clicks, and I’ll … er … inherit from Observable to deal with mouse-overs, and, well, … hmm, that doesn’t work."

The "inner class" idiom

Here’s a situation in which we do actually need to (in effect) upcast to more than one type, but in this case we need to provide several different implementations of the same base type. The solution is something we’ve lifted from Java, which takes C++’s nested class one step further. Java has a built-in feature called an inner class, which is like a nested class in C++, but it has access to the nonstatic data of its containing class by implicitly using the "this" pointer of the class object it was created within.[124]

To implement the inner class idiom in C++, we must obtain and use a pointer to the containing object explicitly. Here’s an example:

//: C10:InnerClassIdiom.cpp

// Example of the "inner class" idiom

#include

#include

using namespace std;

class Poingable {

public:

virtual void poing() = 0;

};

void callPoing(Poingable& p) {

p.poing();

}

class Bingable {

public:

virtual void bing() = 0;

};

void callBing(Bingable& b) {

b.bing();

}

class Outer {

string name;

// Define one inner class:

class Inner1;

friend class Outer::Inner1;

class Inner1 : public Poingable {

Outer* parent;

public:

Inner1(Outer* p) : parent(p) {}

void poing() {

cout << "poing called for "

<< parent->name << endl;

// Accesses data in the outer class object

}

} inner1;

// Define a second inner class:

class Inner2;

friend class Outer::Inner2;

class Inner2 : public Bingable {

Outer* parent;

public:

Inner2(Outer* p) : parent(p) {}

void bing() {

cout << "bing called for "

<< parent->name << endl;

}

} inner2;

public:

Outer(const string& nm) : name(nm),

inner1(this), inner2(this) {}

// Return reference to interfaces

// implemented by the inner classes:

operator Poingable&() { return inner1; }

operator Bingable&() { return inner2; }

};

int main() {

Outer x("Ping Pong");

// Like upcasting to multiple base types!:

callPoing(x);

callBing(x);

} ///:~

The example begins with the Poingable and Bingable interfaces, each of which contain a single member function. The services provided by callPoing( ) and callBing( ) require that the object they receive implement the Poingable and Bingable interfaces, respectively, but they put no other requirements on that object so as to maximize the flexibility of using callPoing( ) and callBing( ). Note the lack of virtual destructors in either interface—the intent is that you never perform object destruction via the interface^.

The Outer constructor contains some private data (name), and it wants to provide both a Poingable interface and a Bingable interface so it can be used with callPoing( ) and callBing( ). Of course, in this situation we could simply use multiple inheritance. This example is just intended to show the simplest syntax for the idiom; you’ll see a real use shortly. To provide a Poingable object without deriving Outer from Poingable, the inner class idiom is used. First, the declaration class Inner says that, somewhere, there is a nested class of this name. This allows the friend declaration for the class, which follows. Finally, now that the nested class has been granted access to all the private elements of Outer, the class can be defined. Notice that it keeps a pointer to the Outer which created it, and this pointer must be initialized in the constructor. Finally, the poing( ) function from Poingable is implemented. The same process occurs for the second inner class which implements Bingable. Each inner class has a single private instance created, which is initialized in the Outer constructor. By creating the member objects and returning references to them, issues of object lifetime are eliminated^.

Notice that both inner class definitions are private, and in fact the client code doesn’t have any access to details of the implementation, since the two access functions operator Poingable&( ) and operator Bingable&( ) only return a reference to the upcast interface, not to the object that implements it. In fact, since the two inner classes are private, the client code cannot even downcast to the implementation classes, thus providing complete isolation between interface and implementation^.

Just to push a point, we’ve taken the extra liberty here of defining the automatic type conversion operators operator Poingable&( ) and operator Bingable&( ). In main( ), you can see that these actually allow a syntax that looks like Outer multiply inherits from Poingable and Bingable. The difference is that the casts in this case are one way. You can get the effect of an upcast to Poingable or Bingable, but you cannot downcast back to an Outer. In the following example of observer, you’ll see the more typical approach: you provide access to the inner class objects using ordinary member functions, not automatic type conversion operations^.

The observer example

Armed with the Observer and Observable header files and the inner class idiom, we can look at an example of the Observer pattern:

//: C10:ObservedFlower.cpp

// Demonstration of "observer" pattern

#include

#include

#include

#include

#include "Observable.h"

using namespace std;

class Flower {

bool isOpen;

public:

Flower() : isOpen(false),

openNotifier(this), closeNotifier(this) {}

void open() { // Opens its petals

isOpen = true;

openNotifier.notifyObservers();

closeNotifier.open();

}

void close() { // Closes its petals

isOpen = false;

closeNotifier.notifyObservers();

openNotifier.close();

}

// Using the "inner class" idiom:

class OpenNotifier;

friend class Flower::OpenNotifier;

class OpenNotifier : public Observable {

Flower* parent;

bool alreadyOpen;

public:

OpenNotifier(Flower* f) : parent(f),

alreadyOpen(false) {}

void notifyObservers(Argument* arg = 0) {

if(parent->isOpen && !alreadyOpen) {

setChanged();

Observable::notifyObservers();

alreadyOpen = true;

}

}

void close() { alreadyOpen = false; }

} openNotifier;

class CloseNotifier;

friend class Flower::CloseNotifier;

class CloseNotifier : public Observable {

Flower* parent;

bool alreadyClosed;

public:

CloseNotifier(Flower* f) : parent(f),

alreadyClosed(false) {}

void notifyObservers(Argument* arg = 0) {

if(!parent->isOpen && !alreadyClosed) {

setChanged();

Observable::notifyObservers();

alreadyClosed = true;

}

}

void open() { alreadyClosed = false; }

} closeNotifier;

};

class Bee {

string name;

// An "inner class" for observing openings:

class OpenObserver;

friend class Bee::OpenObserver;

class OpenObserver : public Observer {

Bee* parent;

public:

OpenObserver(Bee* b) : parent(b) {}

void update(Observable*, Argument *) {

cout << "Bee " << parent->name

<< "'s breakfast time!\n";

}

} openObsrv;

// Another "inner class" for closings:

class CloseObserver;

friend class Bee::CloseObserver;

class CloseObserver : public Observer {

Bee* parent;

public:

CloseObserver(Bee* b) : parent(b) {}

void update(Observable*, Argument *) {

cout << "Bee " << parent->name

<< "'s bed time!\n";

}

} closeObsrv;

public:

Bee(string nm) : name(nm),

openObsrv(this), closeObsrv(this) {}

Observer& openObserver() { return openObsrv; }

Observer& closeObserver() { return closeObsrv;}

};

class Hummingbird {

string name;

class OpenObserver;

friend class Hummingbird::OpenObserver;

class OpenObserver : public Observer {

Hummingbird* parent;

public:

OpenObserver(Hummingbird* h) : parent(h) {}

void update(Observable*, Argument *) {

cout << "Hummingbird " << parent->name

<< "'s breakfast time!\n";

}

} openObsrv;

class CloseObserver;

friend class Hummingbird::CloseObserver;

class CloseObserver : public Observer {

Hummingbird* parent;

public:

CloseObserver(Hummingbird* h) : parent(h) {}

void update(Observable*, Argument *) {

cout << "Hummingbird " << parent->name

<< "'s bed time!\n";

}

} closeObsrv;

public:

Hummingbird(string nm) : name(nm),

openObsrv(this), closeObsrv(this) {}

Observer& openObserver() { return openObsrv; }

Observer& closeObserver() { return closeObsrv;}

};

int main() {

Flower f;

Bee ba("A"), bb("B");

Hummingbird ha("A"), hb("B");

f.openNotifier.addObserver(ha.openObserver());

f.openNotifier.addObserver(hb.openObserver());

f.openNotifier.addObserver(ba.openObserver());

f.openNotifier.addObserver(bb.openObserver());

f.closeNotifier.addObserver(ha.closeObserver());

f.closeNotifier.addObserver(hb.closeObserver());

f.closeNotifier.addObserver(ba.closeObserver());

f.closeNotifier.addObserver(bb.closeObserver());

// Hummingbird B decides to sleep in:

f.openNotifier.deleteObserver(hb.openObserver());

// Something changes that interests observers:

f.open();

f.open(); // It's already open, no change.

// Bee A doesn't want to go to bed:

f.closeNotifier.deleteObserver(

ba.closeObserver());

f.close();

f.close(); // It's already closed; no change

f.openNotifier.deleteObservers();

f.open();

f.close();

} ///:~

The events of interest are that a Flower can open or close. Because of the use of the inner class idiom, both these events can be separately observable phenomena. The OpenNotifier and CloseNotifier classes both derive from Observable, so they have access to setChanged( ) and can be handed to anything that needs an Observable. You’ll notice that, contrary to InnerClassIdiom.cpp, the Observable descendants are public. This is because some of their member functions must be available to the client programmer. There’s nothing that says that an inner class must be private; in InnerClassIdiom.cpp we were simply following the design guideline "make things as private as possible." You could make the classes private and expose the appropriate member functions by proxy in Flower, but it wouldn’t gain much^.

The inner class idiom also comes in handy to define more than one kind of Observer, in Bee and Hummingbird, since both those classes may want to independently observe Flower openings and closings. Notice how the inner class idiom provides something that has most of the benefits of inheritance (the ability to access the private data in the outer class, for example)^.

In main( ), you can see one of the primary benefits of the Observer pattern: the ability to change behavior at runtime by dynamically registering and unregistering Observers with Observables^.

If you study the previous code, you’ll see that OpenNotifier and CloseNotifier use the basic Observable interface. This means that you could derive from other completely different Observer classes; the only connection the Observers have with Flowers is the Observer interface^.

When dealing with multiple types that are interacting, a program can get particularly messy. For example, consider a system that parses and executes mathematical expressions. You want to be able to say Number + Number, Number * Number, and so on, where Number is the base class for a family of numerical objects. But when you say a + b, and you don’t know the exact type of either a or b, how can you get them to interact properly?

The answer starts with something you probably don’t think about: C++ performs only single dispatching. That is, if you are performing an operation on more than one object whose type is unknown, C++ can invoke the dynamic binding mechanism on only one of those types. This doesn’t solve the problem, so you end up detecting some types manually and effectively producing your own dynamic binding behavior^.

The solution is called multiple dispatching. Remember that polymorphism can occur only via member function calls, so if you want double dispatching to occur, there must be two member function calls: the first to determine the first unknown type, and the second to determine the second unknown type. With multiple dispatching, you must have a virtual call for each of the types. Generally, you’ll set up a configuration such that a single member function call produces more than one dynamic member function call and thus services more than one type in the process. To get this effect, you need to work with more than one virtual function: you’ll need a virtual function call for each dispatch. The virtual functions in the following example are called compete( ) and eval( ) and are both members of the same type. (In this case, there will be only two dispatches, which is referred to as double dispatching.) If you are working with two different type hierarchies that are interacting, you’ll need a virtual call in each hierarchy^.

Here’s an example of multiple dispatching:

//: C10:PaperScissorsRock.cpp

// Demonstration of multiple dispatching

#include

#include

#include

#include

#include

#include

#include "../purge.h"

using namespace std;

class Paper;

class Scissors;

class Rock;

enum Outcome { win, lose, draw };

ostream&

operator<<(ostream& os, const Outcome out) {

switch(out) {

default:

case win: return os << "win";

case lose: return os << "lose";

case draw: return os << "draw";

}

}

class Item {

public:

virtual Outcome compete(const Item*) = 0;

virtual Outcome eval(const Paper*) const = 0;

virtual Outcome eval(const Scissors*) const= 0;

virtual Outcome eval(const Rock*) const = 0;

virtual ostream& print(ostream& os) const = 0;

virtual ~Item() {}

friend ostream&

operator<<(ostream& os, const Item* it) {

return it->print(os);

}

};

class Paper : public Item {

public:

Outcome compete(const Item* it) {

return it->eval(this);

}

Outcome eval(const Paper*) const {

return draw;

}

Outcome eval(const Scissors*) const {

return win;

}

Outcome eval(const Rock*) const {

return lose;

}

ostream& print(ostream& os) const {

return os << "Paper ";

}

};

class Scissors : public Item {

public:

Outcome compete(const Item* it) {

return it->eval(this);

}

Outcome eval(const Paper*) const {

return lose;

}

Outcome eval(const Scissors*) const {

return draw;

}

Outcome eval(const Rock*) const {

return win;

}

ostream& print(ostream& os) const {

return os << "Scissors";

}

};

class Rock : public Item {

public:

Outcome compete(const Item* it) {

return it->eval(this);

}

Outcome eval(const Paper*) const {

return win;

}

Outcome eval(const Scissors*) const {

return lose;

}

Outcome eval(const Rock*) const {

return draw;

}

ostream& print(ostream& os) const {

return os << "Rock ";

}

};

struct ItemGen {

ItemGen() { srand(time(0)); }

Item* operator()() {

switch(rand() % 3) {

default:

case 0:

return new Scissors;

case 1:

return new Paper;

case 2:

return new Rock;

}

}

};

struct Compete {

Outcome operator()(Item* a, Item* b) {

cout << a << "\t" << b << "\t";

return a->compete(b);

}

};

int main() {

const int sz = 20;

vector v(sz*2);

generate(v.begin(), v.end(), ItemGen());

transform(v.begin(), v.begin() + sz,

v.begin() + sz,

ostream_iterator(cout, "\n"),

Compete());

purge(v);

} ///:~

Multiple dispatching with Visitor

The assumption is that you have a primary class hierarchy that is fixed; perhaps it’s from another vendor and you can’t make changes to that hierarchy. However, you’d like to add new polymorphic member functions to that hierarchy, which means that normally you’d have to add something to the base class interface. So the dilemma is that you need to add member functions to the base class, but you can’t touch the base class. How do you get around this?

The design pattern that solves this kind of problem is called a "visitor" (the final one in Design Patterns), and it builds on the double-dispatching scheme shown in the previous section^.

The Visitor pattern allows you to extend the interface of the primary type by creating a separate class hierarchy of type Visitor to "virtualize" the operations performed on the primary type. The objects of the primary type simply "accept" the visitor and then call the visitor’s dynamically-bound member function^.

//: C10:BeeAndFlowers.cpp

// Demonstration of "visitor" pattern

#include

#include

#include

#include

#include

#include

#include "../purge.h"

using namespace std;

class Gladiolus;

class Renuculus;

class Chrysanthemum;

class Visitor {

public:

virtual void visit(Gladiolus* f) = 0;

virtual void visit(Renuculus* f) = 0;

virtual void visit(Chrysanthemum* f) = 0;

virtual ~Visitor() {}

};

class Flower {

public:

virtual void accept(Visitor&) = 0;

virtual ~Flower() {}

};

class Gladiolus : public Flower {

public:

virtual void accept(Visitor& v) {

v.visit(this);

}

};

class Renuculus : public Flower {

public:

virtual void accept(Visitor& v) {

v.visit(this);

}

};

class Chrysanthemum : public Flower {

public:

virtual void accept(Visitor& v) {

v.visit(this);

}

};

// Add the ability to produce a string:

class StringVal : public Visitor {

string s;

public:

operator const string&() { return s; }

virtual void visit(Gladiolus*) {

s = "Gladiolus";

}

virtual void visit(Renuculus*) {

s = "Renuculus";

}

virtual void visit(Chrysanthemum*) {

s = "Chrysanthemum";

}

};

// Add the ability to do "Bee" activities:

class Bee : public Visitor {

public:

virtual void visit(Gladiolus*) {

cout << "Bee and Gladiolus\n";

}

virtual void visit(Renuculus*) {

cout << "Bee and Renuculus\n";

}

virtual void visit(Chrysanthemum*) {

cout << "Bee and Chrysanthemum\n";

}

};

struct FlowerGen {

FlowerGen() { srand(time(0)); }

Flower* operator()() {

switch(rand() % 3) {

default:

case 0: return new Gladiolus;

case 1: return new Renuculus;

case 2: return new Chrysanthemum;

}

}

};

int main() {

vector v(10);

generate(v.begin(), v.end(), FlowerGen());

vector::iterator it;

// It's almost as if I added a virtual function

// to produce a Flower string representation:

StringVal sval;

for(it = v.begin(); it != v.end(); it++) {

(*it)->accept(sval);

cout << string(sval) << endl;

}

// Perform "Bee" operation on all Flowers:

Bee bee;

for(it = v.begin(); it != v.end(); it++)

(*it)->accept(bee);

purge(v);

} ///:~

When the C++ standards committee was creating the initial C++ standard, a concurrency mechanism was explicitly excluded, because C didn’t have one and also because there were a number of competing approaches to implementing concurrency. It seemed too much of a constraint to force programmers to use only one of these.

The alternative turned out to be worse, however. To use concurrency, you had to find and learn a library and deal with its idiosyncrasies and the uncertainties of working with a particular vendor. In addition, there was no guarantee that such a library would work on different compilers or across different platforms. Also, since concurrency was not part of the standard language, it was more difficult to find C++ programmers that also understood concurrent programming.

Another influence may have been the Java language, which included concurrency in the core language. Although multithreading is still complicated, Java programmers tend to start learning and using it from the beginning.

The C++ standards committee is seriously considering the addition of concurrency support to the next iteration of C++, but at the time of this writing it is unclear what the library will look like. Therefore, we decided to use the ZThread library as the basis for this chapter. We preferred the design, and it is open-source and freely available at http://zthread.sourceforge.net. Eric Crahen of IBM, the author of the ZThread library, was instrumental in creating this chapter.[125]

This chapter uses only a subset of the ZThread library, in order to convey the fundamental ideas of threading. The ZThread library contains significantly more sophisticated thread support than is shown here, and you should study that library further in order to fully understand its capabilities.

Installing ZThreads

Please note that the ZThread library is an independent project and is not supported by the authors of this book; we are simply using the library in this chapter and cannot provide technical support for installation issues. See the ZThread web site for installation support and error reports.

The ZThread library is distributed as source code. After downloading it from the ZThread web site, you must first compile the library, and then configure your project to use the library.

The preferred method for compiling ZThreads for most flavors of UNIX (Linux, SunOS, Cygwin, etc.) is to use the configure script. After unpacking the files (using tar), simply execute:

./configure && make install

from the main directory of the ZThreads archive to compile and install a copy of the library in the /usr/local directory. You can customize a number of options when using this script, including the locations of files. For details, use this command:

./configure –help

The ZThreads code is structured to simplify compilation for other platforms and compilers (such as Borland, Microsoft, and Metrowerks). To do this, create a new project and add all the .cxx files in the src directory of the ZThreads archive to the list of files to be compiled. Also, be sure to include the include directory of the archive in the header search path for your project. The exact details will vary from compiler to compiler so you’ll need to be somewhat familiar with your toolset to be able to use this option.

Once the compilation has succeeded, the next step is to create a project that uses the newly compiled library. First, let the compiler know where the headers are located so that your #include statements will work properly. Typically, you will add an option such as the following to your project:

-I/path/to/installation/include

If you used the configure script, the installation path will be whatever you selected for the prefix (which defaults to /usr/local). If you used one of the project files in the build directory, the installation path would simply be the path to the main directory of the ZThreads archive.

Next, you’ll need to add an option to your project that will let the linker know where to find the library. If you used the configure script, this will look like:

-L/path/to/installation/lib –lZThread

If you used one of the project files provided, this will look like:

-L/path/to/installation/Debug ZThread.lib

Again, if you used the configure script, the installation path will be whatever you selected for the prefix. If you used a provided project file, the path will be the path to the main directory of the ZThreads archive.

Note that if you’re using Linux, or if you are using Cygwin (www.cygwin.com) under Windows, you may not need to modify your include or library path; the installation process and defaults will often take care of everything for you.

Under Linux, you will probably need to add the following to your .bashrc so that the runtime system can find the shared library file LibZThread-x.x.so.O when it executes the programs in this chapter:

export LD_LIBRARY_PATH=/usr/local/lib:${LD_LIBRARY_PATH}

(Assuming you used the default installation process and the shared library ended up in /user/local/lib; otherwise, change the path to your location).

To drive a Runnable object with a thread, you create a separate Thread object and hand a Runnable pointer to the Thread’s constructor. This performs the thread initialization and then calls the Runnable’s run( ) as an interruptible thread. By driving LiftOff with a Thread, the example below shows how any task can be run in the context of another thread:

//: C11:BasicThreads.cpp

// The most basic use of the Thread class.

//{L} ZThread

#include "LiftOff.h"

#include "zthread/Thread.h"

using namespace ZThread;

using namespace std;

int main() {

try {

Thread t(new LiftOff(10));

cout << "Waiting for LiftOff" << endl;

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

} ///:~

Synchronization_Exception is part of the ZThread library and is the base class for all ZThread exceptions. It will be thrown if there is an error starting or using a thread.

A Thread constructor only needs a pointer to a Runnable object. It will perform the necessary initialization, call that Runnable’s run( ) member function to start the task, and then return to the calling thread, which in this case is the thread for main( ). In effect, you have made a member function call to LiftOff::run( ), and that function has not yet finished, but you can still perform other operations in the main( ) thread. (This ability is not restricted to the main( ) thread—any thread can start another thread.) You can see this by running the program. Even though LiftOff::run( ) has been called, the "Waiting for LiftOff" message will appear before the countdown has completed. Thus, the program is running two functions at once—LiftOff::run( ) and main( ).

You can easily add more threads to drive more tasks. Here, you can see how all the threads run in concert with one another:

//: C11:MoreBasicThreads.cpp

// Adding more threads.

//{L} ZThread

#include "LiftOff.h"

#include "zthread/Thread.h"

using namespace ZThread;

using namespace std;

int main() {

const int sz = 5;

try {

for(int i = 0; i < sz; i++)

Thread t(new LiftOff(10, i));

cout << "Waiting for LiftOff" << endl;

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

} ///:~

The second argument for the LiftOff constructor identifies each task. When you run the program, you’ll see that the execution of the different tasks is mixed together as the threads are swapped in and out. This swapping is automatically controlled by the thread scheduler. If you have multiple processors on your machine, the thread scheduler will quietly distribute the threads among the processors.

The for loop can seem a little strange at first, because t is being created locally inside the for loop and then immediately goes out of scope and is therefore destroyed. This makes it appear that the thread itself might be immediately lost, but you can see from the output that the threads are indeed running to conclusion. When you create a Thread object, the associated thread is registered with the threading system, which keeps it alive. Even though the stack-based Thread object is lost, the thread itself lives on until its associated task completes. Although this may be counterintuitive from a C++ standpoint, the concept of threads is a departure from the norm: a thread creates a separate thread of execution that persists after the function call ends. This departure is reflected in the persistence of the underlying thread after the object vanishes.

Creating responsive user interfaces

As stated earlier, one of the motivations for using threading is to create a responsive user interface. Although we don’t cover graphical user interfaces in this book, you can still see a simple example of a console-based user interface.

The following example reads lines from a file and prints them to the console, sleeping (suspending the current thread) for a second after each line is displayed. (You’ll learn more about sleeping later in the chapter). During this process, the program doesn’t look for user input, so the UI is unresponsive:

//: C11:UnresponsiveUI.cpp

// Lack of threading produces an unresponsive UI.

//{L} ZThread

#include "zthread/Thread.h"

#include

#include

using namespace std;

using namespace ZThread;

int main() {

const int sz = 100; // Buffer size;

char buf[sz];

cout << "Press to quit:" << endl;

ifstream file("UnresponsiveUI.cpp");

while(file.getline(buf, sz)) {

cout << buf << endl;

Thread::sleep(1000); // Time in milliseconds

}

// Read input from the console

cin.get();

cout << "Shutting down..." << endl;

} ///:~

To make the program responsive, you can execute a task that displays the file in a separate thread. The main thread can then watch for user input so the program becomes responsive:

//: C11:ResponsiveUI.cpp

// Threading for a responsive user interface.

//{L} ZThread

#include "zthread/Thread.h"

#include

#include

using namespace ZThread;

using namespace std;

class DisplayTask : public Runnable {

ifstream in;

static const int sz = 100;

char buf[sz];

bool quitFlag;

public:

DisplayTask(const string& file) : quitFlag(false) {

in.open(file.c_str());

}

~DisplayTask() { in.close(); }

void run() {

while(in.getline(buf, sz) && !quitFlag) {

cout << buf << endl;

Thread::sleep(1000);

}

}

void stop() { quitFlag = true; }

};

int main() {

try {

cout << "Press to quit:" << endl;

DisplayTask* dt = new DisplayTask("ResponsiveUI.cpp");

Thread t(dt);

cin.get();

dt->stop();

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

cout << "Shutting down..." << endl;

} ///:~

Now the main thread can respond immediately when you press and call stop( ) on the DisplayTask.

This example also shows the need for communication between tasks—the task in the main thread needs to tell the DisplayTask to shut down. Of course, since we have a pointer to the DisplayTask, you might think of just calling delete on that pointer to kill the task, but this produces unreliable programs. The problem is that the task could be in the middle of something important when you destroy it, and so you are likely to put the program in an unstable state. Here, the task itself decides when it’s safe to shut down. The easiest way to do this is by simply notifying the task that you’d like it to stop by setting a Boolean flag. When the task gets to a stable point it can check that flag and do whatever is necessary to clean up before returning from run( ). When the task returns from run( ), the Thread knows that the task has completed.

Although this program is simple enough that it should not have any problems, there are some small flaws regarding inter-task communication. This is an important topic that will be covered later in this chapter.

Simplifying with Executors

You can simplify your coding overhead by using ZThread Executors. Executors provide a layer of indirection between a client and the execution of a task; instead of a client executing a task directly, an intermediate object executes the task.

We can show this by using an Executor instead of explicitly creating Thread objects in MoreBasicThreads.cpp. A LiftOff object knows how to run a specific task; like the Command Pattern, it exposes a single function to be executed. An Executor object knows how build the appropriate context to execute Runnable objects. In the following example, the ThreadedExecutor creates one thread per task:

//: c11:ThreadedExecutor.cpp

//{L} ZThread

#include "zthread/ThreadedExecutor.h"

#include "LiftOff.h"

using namespace ZThread;

using namespace std;

int main() {

try {

ThreadedExecutor executor;

for(int i = 0; i < 5; i++)

executor.execute(new LiftOff(10, i));

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

} ///:~

Note that in some cases a single Executor can be used to create and manage all the threads in your system. You must still place the threading code inside a try block because an Executor’s execute( ) function may throw Synchronization_Exceptions if something goes wrong. This is true for any function that involves changing the state of a synchronization object (starting threads, acquiring mutexes, waiting on conditions, etc.), as you will learn later in this chapter.

The program will exit as soon as all the tasks in the Executor complete.

In the previous example, the ThreadedExecutor creates a thread for each task that you want to run, but you can easily change the way these tasks are executed by replacing the ThreadedExecutor with a different type of Executor. In this chapter, using a ThreadedExecutor is fine, but in production code it might result in excessive costs from the creation of too many threads. In that case, you can replace it with a PoolExecutor, which will use a limited set of threads to execute the submitted tasks in parallel:

//: C11:PoolExecutor.cpp

//{L} ZThread

#include "zthread/PoolExecutor.h"

#include "LiftOff.h"

using namespace ZThread;

using namespace std;

int main() {

try {

// Constructor argument is minimum number of threads:

PoolExecutor executor(5);

for(int i = 0; i < 5; i++)

executor.execute(new LiftOff(10, i));

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

} ///:~

With the PoolExecutor, you do expensive thread allocation once, up front, and the threads are reused when possible. This saves time because you aren’t constantly paying for thread creation overhead for every single task. Also, in an event-driven system, events that require threads to handle them can be generated as quickly as you want by simply fetching them from the pool. You don’t overrun the available resources because the PoolExecutor uses a bounded number of Thread objects. Thus, although this book will use ThreadedExecutors, consider using PoolExecutors in production code.

A ConcurrentExecutor is like a PoolExecutor with a fixed size of one thread. This is useful for anything you want to run in another thread continually (a long-lived task), such as a task that listens to incoming socket connections. It is also handy for short tasks that you want to run in a thread, for example, small tasks that update a local or remote log, or for an event-dispatching thread.

If more than one task is submitted to a ConcurrentExecutor, each task will run to completion before the next task is begun, all using the same thread. In the following example, you’ll see each task completed, in the order that it was submitted, before the next one is begun. Thus, a ConcurrentExecutor serializes the tasks that are submitted to it.

//: C11:ConcurrentExecutor.cpp

//{L} ZThread

#include "zthread/ConcurrentExecutor.h"

#include "LiftOff.h"

using namespace ZThread;

using namespace std;

int main() {

try {

ConcurrentExecutor executor;

for(int i = 0; i < 5; i++)

executor.execute(new LiftOff(10, i));

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

} ///:~

Like a ConcurrentExecutor, a SynchronousExecutor is used when you want only one task at a time to run, serially instead of concurrently. Unlike ConcurrentExecutor, a SynchronousExecutor doesn’t create or manage threads on it own. It uses the thread that submits the task and thus only acts as a focal point for synchronization. If you have n threads submitting tasks to a SynchronousExecutor, those threads are all blocked on execute( ). One by one they will be allowed to continue as the previous tasks in the queue complete, but no two tasks are ever run at once.

For example, suppose you have a number of threads running tasks that use the file system, but you are writing portable code so you don’t want to use flock( ) or another OS-specific call to lock a file. You can run these tasks with a SynchronousExecutor to ensure that only one task at a time is running from any thread. This way, you don’t have to deal with synchronizing on the shared resource (and you won’t clobber the file system in the meantime). A better solution is to actually synchronize on the resource (which you’ll learn about later in this chapter), but a SynchronousExecutor lets you skip the trouble of getting coordinated properly just to prototype something.

//: C11:SynchronousExecutor.cpp

//{L} ZThread

#include "zthread/SynchronousExecutor.h"

#include "LiftOff.h"

using namespace ZThread;

using namespace std;

int main() {

try {

SynchronousExecutor executor;

for(int i = 0; i < 5; i++)

executor.execute(new LiftOff(10, i));

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

} ///:~

When you run the program, you’ll see that the tasks are executed in the order they are submitted, and each task runs to completion before the next one starts. What you don’t see is that no new threads are created—the main( ) thread is used for each task, since in this example, that’s the thread that submits all the tasks. Because SynchronousExecutor is primarily for prototyping, you may not use it much in production code.

Yielding

If you know that you’ve accomplished what you need to during one pass through a loop in your run( ) function (most run( ) functions involve a long-running loop), you can give a hint to the thread scheduling mechanism that you’ve done enough and that some other thread might as well have the CPU. This hint (and it is a hint—there’s no guarantee your implementation will listen to it) takes the form of the yield( ) function.

We can make a modified version of the LiftOff examples by yielding after each loop:

//: C11:YieldingTask.cpp

// Suggesting when to switch threads with yield().

//{L} ZThread

#include

#include "zthread/Thread.h"

#include "zthread/ThreadedExecutor.h"

using namespace ZThread;

using namespace std;

class YieldingTask : public Runnable {

int countDown;

int id;

public:

YieldingTask(int ident = 0) : countDown(5), id(ident) {}

~YieldingTask() {

cout << id << " completed" << endl;

}

friend ostream&

operator<<(ostream& os, const YieldingTask& yt) {

return os << "#" << yt.id << ": " << yt.countDown;

}

void run() {

while(true) {

cout << *this << endl;

if(--countDown == 0) return;

Thread::yield();

}

}

};

int main() {

try {

ThreadedExecutor executor;

for(int i = 0; i < 5; i++)

executor.execute(new YieldingTask(i));

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

} ///:~

You can see that the task’s run( ) member function consists entirely of an infinite loop. By using yield( ), the output is evened up quite a bit over that without yielding. Try commenting out the call to Thread::yield( ) to see the difference. In general, however, yield( ) is useful only in rare situations, and you can’t rely on it to do any serious tuning of your application.

Sleeping

Another way you can control the behavior of your threads is by calling sleep( ) to cease execution of that thread for a given number of milliseconds. In the preceding example, if you replace the call to yield( ) with a call to sleep( ), you get the following:

//: C11:SleepingTask.cpp

// Calling sleep() to pause for awhile.

//{L} ZThread

#include

#include "zthread/Thread.h"

#include "zthread/ThreadedExecutor.h"

using namespace ZThread;

using namespace std;

class SleepingTask : public Runnable {

int countDown;

int id;

public:

SleepingTask(int ident = 0) : countDown(5), id(ident) {}

~SleepingTask() {

cout << id << " completed" << endl;

}

friend ostream&

operator<<(ostream& os, const SleepingTask& st) {

return os << "#" << st.id << ": " << st.countDown;

}

void run() {

while(true) {

try {

cout << *this << endl;

if(--countDown == 0) return;

Thread::sleep(100);

} catch(Interrupted_Exception& e) {

cerr << e.what() << endl;

}

}

}

};

int main() {

try {

ThreadedExecutor executor;

for(int i = 0; i < 5; i++)

executor.execute(new SleepingTask(i));

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

} ///:~

Thread::sleep( ) can throw an Interrupted_Exception (you’ll learn about interrupts later), and you can see that this is caught in run( ). But the task is created and executed inside a try block in main( ) that catches Synchronization_Exception (the base class for all ZThread exceptions), so wouldn’t it be possible to just ignore the exception in run( ) and assume that it will propagate to the handler in main( )? This won’t work because exceptions won’t propagate across threads back to main( ). Thus, you must handle any exceptions locally that may arise within a task.

You’ll notice that the threads tend to run in any order, which means that sleep( ) is also not a way for you to control the order of thread execution. It just stops the execution of the thread for awhile. The only guarantee that you have is that the thread will sleep at least 100 milliseconds (in this example), but it may take longer before the thread resumes execution, because the thread scheduler still has to get back to it after the sleep interval expires.

If you must control the order of execution of threads, your best bet is to use synchronization controls (described later) or, in some cases, not to use threads at all, but instead to write your own cooperative routines that hand control to each other in a specified order.

Priority

The priority of a thread tells the scheduler how important this thread is. Although the order that the CPU runs a set of threads is indeterminate, the scheduler will lean toward running the waiting thread with the highest priority first. However, this doesn’t mean that threads with lower priority aren’t run (that is, you can’t get deadlocked because of priorities). Lower priority threads just tend to run less often.

Here’s MoreBasicThreads.cpp modified so that the priority levels are demonstrated. The priorities are adjusting by using Thread’s setPriority( ) function.

//: C11:SimplePriorities.cpp

// Shows the use of thread priorities.

//{L} ZThread

#include "zthread/Thread.h"

#include

#include

using namespace ZThread;

using namespace std;

class SimplePriorities : public Runnable {

int countDown;

volatile double d; // No optimization

int id;

public:

SimplePriorities(int ident = 0): countDown(5),id(ident){}

~SimplePriorities() throw() {

cout << id << " completed" << endl;

}

friend ostream&

operator<<(ostream& os, const SimplePriorities& sp) {

return os << "#" << sp.id << " priority: "

<< Thread().getPriority()

<< " count: "<< sp.countDown;

}

void run() {

while(true) {

// An expensive, interruptable operation:

for(int i = 1; i < 100000; i++)

d = d + (M_PI + M_E) / (double)i;

cout << *this << endl;

if(--countDown == 0) return;

}

}

};

int main() {

try {

Thread high(new SimplePriorities);

high.setPriority(High);

for(int i = 0; i < 5; i++) {

Thread low(new SimplePriorities(i));

low.setPriority(Low);

}

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

} ///:~

Here, operator<<( ) is overridden to display the identifier, priority, and countDown value of the task.

You can see that the priority level of thread high is at the highest level, and all the rest of the threads are at the lowest level. We are not using an Executor in this example because we need direct access to the threads in order to set their priorities.

Inside SimplePriorities::run( ), 100,000 repetitions of a rather expensive floating-point calculation are performed, involving double addition and division. The variable d is volatile to ensure that no optimization is performed. Without this calculation, you don’t see the effect of setting the priority levels. (Try it: comment out the for loop containing the double calculations.) With the calculation, you see that thread high is given a higher preference by the thread scheduler. (At least, this was the behavior on a Windows machine.) The calculation takes long enough that the thread scheduling mechanism jumps in, changes threads, and pays attention to the priorities so that thread h gets preference.

You can also read the priority of an existing thread with getPriority( ) and change it at any time (not just before the thread is run, as in SimplePriorities.cpp) with setPriority( ).

Mapping priorities to operating systems is problematic. For example, Windows 2000 has seven priority levels that are not fixed, so the mapping is indeterminate; Sun’s Solaris has 2³¹ levels. The only portable approach is to stick to very large priority granulations, such as the Low, Medium, and High used in the ZThread library.

You can think of a single-threaded program as one lonely entity moving around through your problem space and doing one thing at a time. Because there’s only one entity, you never have to think about the problem of two entities trying to use the same resource at the same time: problems such as two people trying to park in the same space, walk through a door at the same time, or even talk at the same time.

With multithreading, things aren’t lonely anymore, but you now have the possibility of two or more threads trying to use the same resource at once. This can cause two different kinds of problems. The first is that the necessary resources may not exist. In C++, the programmer has complete control over the lifetime of objects, and it’s easy to create threads that try to use objects that get destroyed before those threads complete.

The second problem is that two or more threads may collide when they try to access the same resource at the same time. If you don’t prevent such a collision, you’ll have two threads trying to access the same bank account at the same time, print to the same printer, adjust the same valve, and so on.

This section introduces the problem of objects that vanish while tasks are still using them and the problem of tasks colliding over shared resources. You’ll learn about the tools that are used to solve these problems.

Ensuring the existence of objects

Memory and resource management are major concerns in C++. When you create any C++ program, you have the option of creating objects on the stack or on the heap (using new). In a single-threaded program, it’s usually easy to keep track of object lifetimes so that you don’t try to use objects that are already destroyed.

The examples shown in this chapter create Runnable objects on the heap using new, but you’ll notice that these objects are never explicitly deleted. However, you can see from the output when you run the programs that the thread library keeps track of each task and eventually deletes it, because the destructors for the tasks are called. This happens when the Runnable::run( ) member function completes—returning from run( ) tells the thread that the task is finished.

Burdening the thread with deleting a task is a problem. That thread doesn’t necessarily know if another thread still needs to make a reference to that Runnable, and so the Runnable may be prematurely destroyed. To deal with this problem, tasks in ZThreads are automatically reference-counted by the ZThread library mechanism. A task is maintained until the reference count for that task goes to zero, at which point the task is deleted. This means that tasks must always be deleted dynamically, and so they cannot be created on the stack. Instead, tasks must always be created using new, as you see in all the examples in this chapter.

Often you must also ensure that non-task objects stay alive as long as tasks need them. Otherwise, it’s easy for objects that are used by tasks to go out of scope before those tasks are completed. If this happens, the tasks will try to access illegal storage and will cause program faults. Here’s a simple example:

//: C11:Incrementer.cpp

// Destroying objects while threads are still

// running will cause serious problems.

//{L} ZThread

#include "zthread/Thread.h"

#include "zthread/ThreadedExecutor.h"

#include

using namespace ZThread;

using namespace std;

class Count {

static const int sz = 100;

int n[sz];

public:

void increment() {

for(int i = 0; i < sz; i++)

n[i]++;

}

};

class Incrementer : public Runnable {

Count* count;

public:

Incrementer(Count* c) : count(c) {}

void run() {

for(int n = 100; n > 0; n--) {

Thread::sleep(250);

count->increment();

}

}

};

int main() {

cout << "This will cause a segmentation fault!" << endl;

Count count;

try {

Thread t0(new Incrementer(&count));

Thread t1(new Incrementer(&count));

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

} ///:~

The Count class may seem like overkill at first, but if n is only a single int (rather than an array), the compiler can put it into a register and that storage will still be available (albeit technically illegal) after the Count object goes out of scope. It’s difficult to detect the memory violation in that case. Your results may vary depending on your compiler and operating system, but try making it n single int and see what happens. In any event, if Count contains an array of ints as above, the compiler is forced to put it on the stack and not in a register.

Incrementer is a simple task that uses a Count object. In main( ), you can see that the Incrementer tasks are running for long enough that the Count object will go out of scope, and so the tasks try to access an object that no longer exists. This produces a program fault.

To fix the problem, we must guarantee that any objects shared between tasks will be around as long as those tasks need them. (If the objects were not shared, they could be composed directly into the task’s class and thus tie their lifetime to that task.) Since we don’t want the static program scope to control the lifetime of the object, we put the object on the heap. And to make sure that the object is not destroyed until there are no other objects (tasks, in this case) using it, we use reference counting.

Reference counting was explained thoroughly in volume one of this book and further revisited in this volume. The ZThread library includes a template called CountedPtr that automatically performs reference counting and deletes an object when the reference count goes to zero. Here’s the above program modified to use CountedPtr to prevent the fault:

//: C11:ReferenceCounting.cpp

// A CountedPtr prevents too-early destruction.

//{L} ZThread

#include "zthread/Thread.h"

#include "zthread/CountedPtr.h"

#include

using namespace ZThread;

using namespace std;

class Count {

static const int sz = 100;

int n[sz];

public:

void increment() {

for(int i = 0; i < sz; i++)

n[i]++;

}

};

class Incrementer : public Runnable {

CountedPtr count;

public:

Incrementer(const CountedPtr& c ) : count(c) {}

void run() {

for(int n = 100; n > 0; n--) {

Thread::sleep(250);

count->increment();

}

}

};

int main() {

CountedPtr count(new Count);

try {

Thread t0(new Incrementer(count));

Thread t1(new Incrementer(count));

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

} ///:~

Incrementer now contains a CountedPtr object, which manages a Count. In main( ), the CountedPtr objects are passed into the two Incrementer objects by value, so the copy-constructor is called, increasing the reference count. As long as the tasks are still running, the reference count will be nonzero, and so the Count object managed by the CountedPtr will not be destroyed. Only when all the tasks using the Count are completed will delete be called (automatically) on the Count object by the CountedPtr.

Whenever you have objects that are used by more than one task, you’ll almost always need to manage those objects using the CountedPtr template in order to prevent problems arising from object lifetime issues.

Improperly accessing resources

Consider the following example in which one task generates even numbers and other tasks consume those numbers. In this case, the only job of the consumer threads is to check the validity of the even numbers.

We’ll first define EvenChecker, the consumer thread, since it will be reused in all the subsequent examples. To decouple EvenChecker from the various types of generators that we will experiment with, we’ll create an interface called Generator, which contains the minimum necessary functions that EvenChecker must know about: that it has a nextValue( ) function and that it can be canceled.

//: C11:EvenChecker.h

#ifndef EVENCHECKER_H

#define EVENCHECKER_H

#include "zthread/CountedPtr.h"

#include "zthread/Thread.h"

#include "zthread/Cancelable.h"

#include "zthread/ThreadedExecutor.h"

#include

class Generator : public ZThread::Cancelable {

bool canceled;

public:

Generator() : canceled(false) {}

virtual int nextValue() = 0;

void cancel() { canceled = true; }

bool isCanceled() { return canceled; }

};

class EvenChecker : public ZThread::Runnable {

ZThread::CountedPtr generator;

int id;

public:

EvenChecker(ZThread::CountedPtr& g, int ident)

: generator(g), id(ident) {}

~EvenChecker() {

std::cout << "~EvenChecker " << id << std::endl;

}

void run() {

while(!generator->isCanceled()) {

int val = generator->nextValue();

if(val % 2 != 0) {

std::cout << val << " not even!" << std::endl;

generator->cancel(); // Cancels all EvenCheckers

}

}

}

// Test any type of generator:

template static void test(int n = 10) {

std::cout << "Press Control-C to exit" << std::endl;

try {

ZThread::ThreadedExecutor executor;

ZThread::CountedPtr gp(new GenType);

for(int i = 0; i < n; i++)

executor.execute(new EvenChecker(gp, i));

} catch(ZThread::Synchronization_Exception& e) {

std::cerr << e.what() << std::endl;

}

}

};

#endif // EVENCHECKER_H ///:~

The Generator class introduces the pure abstract Cancelable class, which is part of the ZThread library. The goal of Cancelable is to provide a consistent interface to change the state of an object via the cancel( ) function and to see whether the object has been canceled with the isCanceled( ) function. Here, the simple approach of a bool canceled flag is used, similar to the quitFlag previously seen in ResponsiveUI.cpp. Note that in this example the class that is Cancelable is not Runnable. Instead, all the EvenChecker tasks that depend on the Cancelable object (the Generator) test it to see if it’s been canceled, as you can see in run( ). This way, the tasks that share the common resource (the Cancelable Generator) watch that resource for the signal to terminate. This eliminates the so-called race condition, in which two or more tasks race to respond to a condition and thus collide or otherwise produce inconsistent results. You must be careful to think about and protect against all the possible ways a concurrent system can fail. For example, a task cannot depend on another task, because there’s no guarantee of the order in which tasks will be shut down. Here, by making tasks depend on non-task objects, we eliminate the potential race condition.

In later sections, you’ll see that the ZThread library contains more general mechanisms for termination of threads.

Since multiple EvenChecker objects may end up sharing a Generator, the CountedPtr template is used to reference count the Generator objects.

The last member function in EvenChecker is a static member template that sets up and performs a test of any type of Generator by creating one inside a CountedPtr and then starting a number of EvenCheckers that use that Generator. If the Generator causes a failure, test( ) will report it and return; otherwise, you must press Control-C to terminate it.

EvenChecker tasks constantly read and test the values from their associated Generator. Note that if generator->isCanceled( ) is true, run( ) returns, which tells the Executor in EvenChecker::test( ) that the task is complete. Any EvenChecker task can call cancel( ) on its associated Generator, which will cause all other EvenCheckers using that Generator to gracefully shut down.

The EvenGenerator is simple –nextValue( ) produces the next even value:

//: C11:EvenGenerator.cpp

// When threads collide.

//{L} ZThread

#include "EvenChecker.h"

#include "zthread/ThreadedExecutor.h"

#include

using namespace ZThread;

using namespace std;

class EvenGenerator : public Generator {

int currentEvenValue;

public:

EvenGenerator() { currentEvenValue = 0; }

~EvenGenerator() { cout << "~EvenGenerator" << endl; }

int nextValue() {

currentEvenValue++; // Danger point here!

currentEvenValue++;

return currentEvenValue;

}

};

int main() {

EvenChecker::test();

} ///:~

It’s possible for one thread to call nextValue( ) after the first increment of currentEvenValue and before the second (at the place in the code commented "Danger point here!"), in which case the value would be in an "incorrect" state. To prove that this can happen, EvenChecker::test( ) creates a group of EvenChecker objects to continually read the output of an EvenGenerator and test to see if each one is even. If not, the error is reported and the program is shut down.

This program may not detect the problem until the EvenGenerator has completed many cycles, depending on the particulars of your operating system and other implementation details. If you want to see it fail much faster, try putting a call to yield( ) between the first and second increments. In any event, it will eventually fail because the EvenChecker threads are able to access the information in EvenGenerator while it’s in an "incorrect" state.

Controlling access

The previous example shows a fundamental problem when using threads: You never know when a thread might be run. Imagine sitting at a table with a fork, about to spear the last piece of food on your plate, and as your fork reaches for it, the food suddenly vanishes (because your thread was suspended and another task came in and stole the food). That’s the problem you’re dealing with when writing concurrent programs.

Sometimes you don’t care if a resource is being accessed at the same time you’re trying to use it (the food is on some other plate). But for multithreading to work, you need some way to prevent two threads from accessing the same resource, at least during critical periods.

Preventing this kind of collision is simply a matter of putting a lock on a resource when one thread is using it. The first thread that accesses a resource locks it, and then the other threads cannot access that resource until it is unlocked, at which time another thread locks and uses it, and so on. If the front seat of the car is the limited resource, the child who shouts "Dibs!" acquires the lock.

Thus, we need to be able to prevent any other tasks from accessing the storage when that storage is not in a proper state. That is, we need to have a mechanism that excludes a second task from accessing the storage when a first task is already using it. This idea is fundamental to all multithreading systems and is called mutual exclusion; the mechanism used abbreviates this to mutex. The ZThread library contains a mutex mechanism declared in the header Mutex.h.

To solve the problem in the above program, we identify the critical sections in which mutual exclusion must apply; then we acquire the mutex before entering the critical section and release it at the end of the critical section. Only one thread can acquire the mutex at any time, so mutual exclusion is achieved:

//: C11:MutexEvenGenerator.cpp

// Preventing thread collisions with mutexes.

//{L} ZThread

#include "EvenChecker.h"

#include "zthread/ThreadedExecutor.h"

#include "zthread/Mutex.h"

#include

using namespace ZThread;

using namespace std;

class MutexEvenGenerator : public Generator {

int currentEvenValue;

Mutex lock;

public:

MutexEvenGenerator() { currentEvenValue = 0; }

~MutexEvenGenerator() {

cout << "~MutexEvenGenerator" << endl;

}

int nextValue() {

lock.acquire();

currentEvenValue++;

Thread::yield();

currentEvenValue++;

int rval = currentEvenValue;

lock.release();

return rval;

}

};

int main() {

EvenChecker::test();

} ///:~

The only changes here are in MutexEvenGenerator, which adds a Mutex called lock and uses acquire( ) and release( ) in nextValue( ). Note that nextValue( ) must capture the return value inside the critical section, because if you return from inside the critical section, you won’t release the lock and will thus prevent it from being acquired again. (This usually leads to deadlock, which you’ll learn about at the end of this chapter.)

The first thread that enters nextValue( ) acquires the lock, and any further threads that try to acquire the lock are blocked from doing so until the first thread releases the lock. At that point, the scheduling mechanism selects another thread that is waiting on the lock. This way, only one thread at a time can pass through the code that is guarded by the mutex.

Simplified coding with Guards

Thread local storage

A second way to eliminate the problem of tasks colliding over shared resources is to eliminate the sharing of variables, which can be done by creating different storage for the same variable, for each different thread that uses an object. Thus, if you have five threads using an object with a variable x, thread local storage automatically generates five different pieces of storage for x. Fortunately, the creation and management of thread local storage is taken care of automatically by ZThread’s ThreadLocal template, as seen here:

//: C11:ThreadLocalVariables.cpp

// Automatically giving each thread its own storage.

//{L} ZThread

#include "zthread/Thread.h"

#include "zthread/Mutex.h"

#include "zthread/Guard.h"

#include "zthread/ThreadedExecutor.h"

#include "zthread/Cancelable.h"

#include "zthread/ThreadLocal.h"

#include "zthread/CountedPtr.h"

#include

using namespace ZThread;

using namespace std;

class ThreadLocalVariables : public Cancelable {

ThreadLocal value;

bool canceled;

Mutex lock;

public:

ThreadLocalVariables() : canceled(false) {

value.set(0);

}

void increment() { value.set(value.get() + 1); }

int get() { return value.get(); }

void cancel() {

Guard g(lock);

canceled = true;

}

bool isCanceled() {

Guard g(lock);

return canceled;

}

};

class Accessor : public Runnable {

int id;

CountedPtr tlv;

public:

Accessor(CountedPtr& tl, int idn)

: id(idn), tlv(tl) {}

void run() {

while(!tlv->isCanceled()) {

tlv->increment();

cout << *this << endl;

}

}

friend ostream&

operator<<(ostream& os, Accessor& a) {

return os << "#" << a.id << ": " << a.tlv->get();

}

};

int main() {

cout << "Press to quit" << endl;

try {

CountedPtr

tlv(new ThreadLocalVariables);

const int sz = 5;

ThreadedExecutor executor;

for(int i = 0; i < sz; i++)

executor.execute(new Accessor(tlv, i));

cin.get();

tlv->cancel(); // All Accessors will quit

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

} ///:~

When you create a ThreadLocal object by instantiating the template, you are only able to access the contents of the object using the get( ) and set( ) functions. The get( ) function returns a copy of the object that is associated with that thread, and set( ) inserts its argument into the object stored for that thread, returning the old object that was in storage. You can see this is use in increment( ) and get( ) in ThreadLocalVariables.

Since tlv is shared by multiple Accessor objects, it is written as Cancelable so that the Accessors can be signaled when we want to shut the system down.

When you run this program, you’ll see evidence that the individual threads are each allocated their own storage.

In previous examples, we have seen the use of a "quit flag" or the Cancelable interface in order to terminate a task. This is a reasonable approach to the problem. However, in some situations the task must be terminated more abruptly. In this section, you’ll learn about the issues and problems of such termination.

First, let’s look at an example that not only demonstrates the termination problem but is also an additional example of resource sharing. To present this example, we’ll first need to solve the problem of iostream collision

Preventing iostream collision

You may have noticed in previous examples that the output is sometimes garbled. The problem is that C++ iostreams were not created with threading in mind, and so there’s nothing to keep one thread’s output from interfering with another thread’s output.

To solve the problem, we need to create the entire output packet first and then explicitly decide when to try to send it to the console. One simple solution is to write the information to an ostringstream and then use a single object with a mutex as the point of output among all threads, to prevent more than one thread from writing at the same time:

//: C11:Display.h

// Prevents ostream collisions

#ifndef DISPLAY_H

#define DISPLAY_H

#include "zthread/Mutex.h"

#include "zthread/Guard.h"

#include

#include

class Display { // Share one of these among all threads

ZThread::Mutex iolock;

public:

void output(std::ostringstream& os) {

ZThread::Guard g(iolock);

std::cout << os.str();

}

};

#endif // DISPLAY_H ///:~

This way, all of the standard operator<<( ) functions are predefined for us and the object can be built in memory using familiar ostream operators. When a task wants to display output, it creates a temporary ostringstream object that it uses to build up the desired output message. When it calls output( ), the mutex prevents multiple threads from writing to this Display object. (You must use only one Display object in your program, as you’ll see in the following examples.)

This just shows the basic idea, but if necessary, you can build a more elaborate framework. For example, you could enforce the requirement that there be only one Display object in a program by making it a Singleton. (The ZThread library has a Singleton template to support Singletons.)

The ornamental garden

Terminating when blocked

Interruption

As you’ve seen, when you use threads to run more than one task at a time, you can keep one task from interfering with another task’s resources by using a mutex to synchronize the behavior of the two tasks. That is, if two tasks are stepping on each other over a shared resource (usually memory), you use a mutex to allow only one task at a time to access that resource.

With that problem solved, you can move on to the issue of getting threads to cooperate, so that multiple threads can work together to solve a problem. Now the issue is not about interfering with one another, but rather about working in unison, since portions of such problems must be solved before other portions can be solved. It’s much like project planning: the footings for the house must be dug first, but the steel can be laid and the concrete forms can be built in parallel, and both of those tasks must be finished before the concrete foundation can be poured. The plumbing must be in place before the concrete slab can be poured, the concrete slab must be in place before you start framing, and so on. Some of these tasks can be done in parallel, but certain steps require all tasks to be completed before you can move ahead.

The key issue when tasks are cooperating is handshaking between those tasks. To accomplish this handshaking, we use the same foundation: the mutex, which in this case guarantees that only one task can respond to a signal. This eliminates any possible race conditions. On top of the mutex, we add a way for a task to suspend itself until some external state changes ("the plumbing is now in place"), indicating that it’s time for that task to move forward. In this section, we’ll look at the issues of handshaking between tasks, the problems that can arise, and their solutions.

Wait and signal

In ZThreads, the basic class that uses a mutex and allows task suspension is the Condition, and you can suspend a task by calling wait( ) on a Condition. When external state changes take place that might mean that a task should continue processing, you notify the task by calling signal( ), to wake up one task, or broadcast( ), to wake up all tasks that have suspended themselves on that Condition object.

There are two forms of wait( ). The first takes an argument in milliseconds that has the same meaning as in sleep( ): "pause for this period of time." The difference is that in a timed wait( ):

1. The Mutex that is controlled by the Condition object is released during the wait( ).

2. You can come out of the wait( ) due to a signal( ) or a broadcast( ), as well as by letting the clock run out.

The second form of wait( ) takes no arguments; this version is more commonly used. It also releases the mutex, but this wait( ) suspends the thread indefinitely until that Condition object receives a signal( ) or broadcast( ).

Typically, you use wait( ) when you’re waiting for some condition to change that is under the control of forces outside the current function. (Often, this condition will be changed by another thread.) You don’t want to idly loop while testing the condition inside your thread; this is called a "busy wait," and it’s a bad use of CPU cycles. Thus, wait( ) allows you to suspend the thread while waiting for the world to change, and only when a signal( ) or broadcast( ) occurs (suggesting that something of interest may have happened), does the thread wake up and check for changes. Therefore, wait( ) provides a way to synchronize activities between threads.

Let’s look at a simple example. WaxOMatic.cpp applies wax to a Car and polishes it using two separate processes. The polishing process cannot do its job until the application process is finished, and the application process must wait until the polishing process is finished before it can put on another coat of wax. Both WaxOn and WaxOff use the Car object, which contains a Condition that it uses to suspend a thread inside waitForWaxing( ) or waitForBuffing( ):

//: C11:WaxOMatic.cpp

// Basic thread cooperation.

//{L} ZThread

#include "zthread/Thread.h"

#include "zthread/Mutex.h"

#include "zthread/Guard.h"

#include "zthread/Condition.h"

#include "zthread/ThreadedExecutor.h"

#include

#include

using namespace ZThread;

using namespace std;

class Car {

Mutex lock;

Condition condition;

bool waxOn;

public:

Car() : condition(lock), waxOn(false) {}

void waxed() {

Guard g(lock);

waxOn = true; // Ready to buff

condition.signal();

}

void buffed() {

Guard g(lock);

waxOn = false; // Ready for another coat of wax

condition.signal();

}

void waitForWaxing() {

Guard g(lock);

while(waxOn == false)

condition.wait();

}

void waitForBuffing() {

Guard g(lock);

while(waxOn == true)

condition.wait();

}

};

class WaxOn : public Runnable {

CountedPtr car;

public:

WaxOn(CountedPtr& c) : car(c) {}

void run() {

try {

while(!Thread::interrupted()) {

cout << "Wax On!" << endl;

Thread::sleep(200);

car->waxed();

car->waitForBuffing();

}

} catch(Interrupted_Exception&) { /* Exit */ }

cout << "Ending Wax On process" << endl;

}

};

class WaxOff : public Runnable {

CountedPtr car;

public:

WaxOff(CountedPtr& c) : car(c) {}

void run() {

try {

while(!Thread::interrupted()) {

car->waitForWaxing();

cout << "Wax Off!" << endl;

Thread::sleep(200);

car->buffed();

}

} catch(Interrupted_Exception&) { /* Exit */ }

cout << "Ending Wax Off process" << endl;

}

};

int main() {

cout << "Press to quit" << endl;

try {

CountedPtr car(new Car);

ThreadedExecutor executor;

executor.execute(new WaxOff(car));

executor.execute(new WaxOn(car));

cin.get();

executor.interrupt();

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

} ///:~

In Car’s constructor, a single Mutex is wrapped in a Condition object so that it can be used to manage inter-task communication. However, the Condition object contains no information about the state of your process, so you need to manage additional information to indicate process state. Here, Car has a single bool waxOn, which indicates the state of the waxing-polishing process.

In waitForWaxing( ), the waxOn flag is checked, and if it is false, the calling thread is suspended by calling wait( ) on the Condition object. It’s important that this occur inside a guarded clause, in which the thread has acquired the lock (here, by creating a Guard object). When you call wait( ), the thread is suspended and the lock is released. It is essential that the lock be released because, to safely change the state of the object (for example, to change waxOn to true, which must happen if the suspended thread is to ever continue), that lock must be available to be acquired by some other task. In this example, when another thread calls waxed( ) to tell it that it’s time to do something, the mutex must be acquired in order to change waxOn to true. Afterward, waxed( ) sends a signal( ) to the Condition object, which wakes up the thread suspended in the call to wait( ). Although signal( ) may be called inside a guarded clause—as it is here—you are not required to do this.[127]

In order for a thread to wake up from a wait( ), it must first reacquire the mutex that it released when it entered the wait( ). The thread will not wake up until that mutex becomes available.

The call to wait( ) is placed inside a while loop that checks the condition of interest. This is important for two reasons:

· It is possible that when the thread gets a signal( ), some other condition has changed that is not associated with the reason that we called wait( ) here. If that is the case, this thread should be suspended again until its condition of interest changes.

· By the time this thread awakens from its wait( ), it’s possible that some other task has changed things such that this thread is unable or uninterested in performing its operation at this time. Again, it should be re-suspended by calling wait( ) again.

Because these two reasons are always present when you are calling wait( ), always write your call to wait( ) inside a while loop that tests for your condition(s) of interest.

WaxOn::run( ) represents the first step in the process of waxing the car, so it performs its operation (a call to sleep( ) to simulate the time necessary for waxing). It then tells the car that waxing is complete, and calls waitForBuffing( ), which suspends this thread with a wait( ) until the WaxOff process calls buffed( ) for the car, changing the state and calling notify( ). WaxOff::run( ), on the other hand, immediately moves into waitForWaxing( ) and is thus suspended until the wax has been applied by WaxOn and waxed( ) is called. When you run this program, you can watch this two-step process repeat itself as control is handed back and forth between the two threads. When you press the key, interrupt( ) halts both threads—when you call interrupt( ) for an Executor, it calls interrupt( ) for all the threads it is controlling.

Producer-consumer relationships

A common situation in threading problems is the producer-consumer relationship, in which one task is creating objects and other tasks are consuming them. In such a situation, make sure that (among other things) the consuming tasks do not accidentally skip any of the produced objects.

To show this problem, consider a machine that has three tasks: one to make toast, one to butter the toast, and one to put jam on the buttered toast.

//: C11:ToastOMatic.cpp

// Problems with thread cooperation.

//{L} ZThread

#include "zthread/Thread.h"

#include "zthread/Mutex.h"

#include "zthread/Guard.h"

#include "zthread/Condition.h"

#include "zthread/ThreadedExecutor.h"

#include

#include

#include

using namespace ZThread;

using namespace std;

// Apply jam to buttered toast:

class Jammer : public Runnable {

Mutex lock;

Condition butteredToastReady;

bool gotButteredToast;

int jammed;

public:

Jammer(): butteredToastReady(lock) {

gotButteredToast = false;

jammed = 0;

}

void moreButteredToastReady() {

Guard g(lock);

gotButteredToast = true;

butteredToastReady.signal();

}

void run() {

try {

while(!Thread::interrupted()) {

{

Guard g(lock);

while(!gotButteredToast)

butteredToastReady.wait();

jammed++;

}

cout << "Putting jam on toast " << jammed << endl;

{

Guard g(lock);

gotButteredToast = false;

}

}

} catch(Interrupted_Exception&) { /* Exit */ }

cout << "Jammer off" << endl;

}

};

// Apply butter to toast:

class Butterer : public Runnable {

Mutex lock;

Condition toastReady;

CountedPtr jammer;

bool gotToast;

int buttered;

public:

Butterer(CountedPtr& j)

: jammer(j), toastReady(lock) {

gotToast = false;

buttered = 0;

}

void moreToastReady() {

Guard g(lock);

gotToast = true;

toastReady.signal();

}

void run() {

try {

while(!Thread::interrupted()) {

{

Guard g(lock);

while(!gotToast)

toastReady.wait();

buttered++;

}

cout << "Buttering toast " << buttered << endl;

jammer->moreButteredToastReady();

{

Guard g(lock);

gotToast = false;

}

}

} catch(Interrupted_Exception&) { /* Exit */ }

cout << "Butterer off" << endl;

}

};

class Toaster : public Runnable {

CountedPtr butterer;

int toasted;

public:

Toaster(CountedPtr& b) : butterer(b) {

toasted = 0;

srand(time(0)); // Seed the random number generator

}

void run() {

try {

while(!Thread::interrupted()) {

Thread::sleep(rand()/(RAND_MAX/5)*100);

// ...

// Create new toast

// ...

cout << "New toast " << ++toasted << endl;

butterer->moreToastReady();

}

} catch(Interrupted_Exception&) { /* Exit */ }

cout << "Toaster off" << endl;

}

};

int main() {

try {

cout << "Press to quit" << endl;

CountedPtr jammer(new Jammer);

CountedPtr butterer(new Butterer(jammer));

ThreadedExecutor executor;

executor.execute(new Toaster(butterer));

executor.execute(butterer);

executor.execute(jammer);

cin.get();

executor.interrupt();

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

} ///:~

The classes are defined in the reverse order that they operate to simplify forward-referencing issues.

Jammer and Butterer both contain a Mutex, a Condition, and some kind of internal state information that changes to indicate that the process should suspend or resume. (Toaster doesn’t need these since it is the producer and doesn’t have to wait on anything.) The two run( ) functions perform an operation, set a state flag, and then call wait( ) to suspend the task. The moreToastReady( ) and moreButteredToastReady( ) functions change their respective state flags to indicate that something has changed and the process should consider resuming and then call signal( ) to wake up the thread.

The difference between this example and the previous one is that, at least conceptually, something is being produced here: toast. The rate of toast production is randomized a bit, to add some uncertainty. And you’ll see that when you run the program, things aren’t going right, because many pieces of toast appear to be getting dropped on the floor—not buttered, not jammed.

Solving threading problems with queues

Broadcast

The signal( ) function wakes up a single thread that is waiting on a Condition object. However, multiple threads may be waiting on the same condition object, and in that case you’ll want to wake them all up using broadcast( ) instead of signal( ).

As an example that brings together many of the concepts in this chapter, consider a hypothetical robotic assembly line for automobiles. Each Car will be built in several stages, and in this example we’ll look at a single stage: after the chassis has been created, at the time when the engine, drive train, and wheels are attached. The Cars are transported from one place to another via a CarQueue, which is a type of TQueue. A Director takes each Car (as a raw chassis) from the incoming CarQueue and places it in a Cradle, which is where all the work is done. At this point, the Director tells all the waiting robots (using broadcast( )) that the Car is in the Cradle ready for the robots to work on it. The three types of robots go to work, sending a message to the Cradle when they finish their tasks. The Director waits until all the tasks are complete and then puts the Car onto the outgoing CarQueue to be transported to the next operation. In this case, the consumer of the outgoing CarQueue is a Reporter object, which just prints the Car to show that the tasks have been properly completed.

//: C11:CarBuilder.cpp

// How broadcast() works.

//{L} ZThread

#include "zthread/Thread.h"

#include "zthread/Mutex.h"

#include "zthread/Guard.h"

#include "zthread/Condition.h"

#include "zthread/ThreadedExecutor.h"

#include "TQueue.h"

#include

#include

using namespace ZThread;

using namespace std;

class Car {

bool engine, driveTrain, wheels;

int id;

public:

Car(int idn) : id(idn), engine(false),

driveTrain(false), wheels(false) {}

// Empty Car object:

Car() : id(-1), engine(false),

driveTrain(false), wheels(false) {}

// Unsynchronized -- assumes atomic bool operations:

int getId() { return id; }

void addEngine() { engine = true; }

bool engineInstalled() { return engine; }

void addDriveTrain() { driveTrain = true; }

bool driveTrainInstalled() { return driveTrain; }

void addWheels() { wheels = true; }

bool wheelsInstalled() { return wheels; }

friend ostream& operator<<(ostream& os, const Car& c) {

return os << "Car " << c.id << " ["

<< " engine: " << c.engine

<< " driveTrain: " << c.driveTrain

<< " wheels: " << c.wheels << " ]";

}

};

typedef CountedPtr< TQueue > CarQueue;

class ChassisBuilder : public Runnable {

CarQueue carQueue;

int counter;

public:

ChassisBuilder(CarQueue& cq) : carQueue(cq), counter(0){}

void run() {

try {

while(!Thread::interrupted()) {

Thread::sleep(1000);

// Make chassis:

Car c(counter++);

cout << c << endl;

// Insert into queue

carQueue->put(c);

}

} catch(Interrupted_Exception&) { /* Exit */ }

cout << "ChassisBuilder off" << endl;

}

};

class Cradle {

Car c; // Holds current car being worked on

bool occupied;

Mutex workLock, readyLock;

Condition workCondition, readyCondition;

bool engineBotHired, wheelBotHired, driveTrainBotHired;

public:

Cradle()

: workCondition(workLock), readyCondition(readyLock) {

occupied = false;

engineBotHired = true;

wheelBotHired = true;

driveTrainBotHired = true;

}

void insertCar(Car chassis) {

c = chassis;

occupied = true;

}

Car getCar() { // Can only extract car once

if(!occupied) {

cerr << "No Car in Cradle for getCar()" << endl;

return Car(); // "Null" Car object

}

occupied = false;

return c;

}

// Access car while in cradle:

Car* operator->() { return &c; }

// Allow robots to offer services to this cradle:

void offerEngineBotServices() {

Guard g(workLock);

while(engineBotHired)

workCondition.wait();

engineBotHired = true; // Accept the job

}

void offerWheelBotServices() {

Guard g(workLock);

while(wheelBotHired)

workCondition.wait();

wheelBotHired = true; // Accept the job

}

void offerDriveTrainBotServices() {

Guard g(workLock);

while(driveTrainBotHired)

workCondition.wait();

driveTrainBotHired = true; // Accept the job

}

// Tell waiting robots that work is ready:

void startWork() {

Guard g(workLock);

engineBotHired = false;

wheelBotHired = false;

driveTrainBotHired = false;

workCondition.broadcast();

}

// Each robot reports when their job is done:

void taskFinished() {

Guard g(readyLock);

readyCondition.signal();

}

// Director waits until all jobs are done:

void waitUntilWorkFinished() {

Guard g(readyLock);

while(!(c.engineInstalled() && c.driveTrainInstalled()

&& c.wheelsInstalled()))

readyCondition.wait();

}

};

typedef CountedPtr CradlePtr;

class Director : public Runnable {

CarQueue chassisQueue, finishingQueue;

CradlePtr cradle;

public:

Director(CarQueue& cq, CarQueue& fq, CradlePtr cr)

: chassisQueue(cq), finishingQueue(fq), cradle(cr) {}

void run() {

try {

while(!Thread::interrupted()) {

// Blocks until chassis is available:

cradle->insertCar(chassisQueue->get());

// Notify robots car is ready for work

cradle->startWork();

// Wait until work completes

cradle->waitUntilWorkFinished();

// Put car into queue for further work

finishingQueue->put(cradle->getCar());

}

} catch(Interrupted_Exception&) { /* Exit */ }

cout << "Director off" << endl;

}

};

class EngineRobot : public Runnable {

CradlePtr cradle;

public:

EngineRobot(CradlePtr cr) : cradle(cr) {}

void run() {

try {

while(!Thread::interrupted()) {

// Blocks until job is offered/accepted:

cradle->offerEngineBotServices();

cout << "Installing engine" << endl;

(*cradle)->addEngine();

cradle->taskFinished();

}

} catch(Interrupted_Exception&) { /* Exit */ }

cout << "EngineRobot off" << endl;

}

};

class DriveTrainRobot : public Runnable {

CradlePtr cradle;

public:

DriveTrainRobot(CradlePtr cr) : cradle(cr) {}

void run() {

try {

while(!Thread::interrupted()) {

// Blocks until job is offered/accepted:

cradle->offerDriveTrainBotServices();

cout << "Installing DriveTrain" << endl;

(*cradle)->addDriveTrain();

cradle->taskFinished();

}

} catch(Interrupted_Exception&) { /* Exit */ }

cout << "DriveTrainRobot off" << endl;

}

};

class WheelRobot : public Runnable {

CradlePtr cradle;

public:

WheelRobot(CradlePtr cr) : cradle(cr) {}

void run() {

try {

while(!Thread::interrupted()) {

// Blocks until job is offered/accepted:

cradle->offerWheelBotServices();

cout << "Installing Wheels" << endl;

(*cradle)->addWheels();

cradle->taskFinished();

}

} catch(Interrupted_Exception&) { /* Exit */ }

cout << "WheelRobot off" << endl;

}

};

class Reporter : public Runnable {

CarQueue carQueue;

public:

Reporter(CarQueue& cq) : carQueue(cq) {}

void run() {

try {

while(!Thread::interrupted()) {

cout << carQueue->get() << endl;

}

} catch(Interrupted_Exception&) { /* Exit */ }

cout << "Reporter off" << endl;

}

};

int main() {

cout << "Press to quit" << endl;

try {

CarQueue chassisQueue(new TQueue),

finishingQueue(new TQueue);

CradlePtr cradle(new Cradle);

ThreadedExecutor assemblyLine;

assemblyLine.execute(new EngineRobot(cradle));

assemblyLine.execute(new DriveTrainRobot(cradle));

assemblyLine.execute(new WheelRobot(cradle));

assemblyLine.execute(

new Director(chassisQueue, finishingQueue, cradle));

assemblyLine.execute(new Reporter(finishingQueue));

// Start everything running by producing chassis:

assemblyLine.execute(new ChassisBuilder(chassisQueue));

cin.get();

assemblyLine.interrupt();

} catch(Synchronization_Exception& e) {

cerr << e.what() << endl;

}

} ///:~

You’ll notice that Car takes a shortcut: it assumes that bool operations are atomic, which, as previously discussed, is generally a safe assumption but one to consider carefully. Each Car begins as an unadorned chassis, and different robots will attach different parts to it, calling the appropriate "add" function when they do.

A ChassisBuilder simply creates a new Car every second and places it into the chassisQueue. A Director manages the build process by taking the next Car off the chassisQueue, putting it into the Cradle, telling all the robots to startWork( ), and suspending itself by calling waitUntilWorkFinished( ). When the work is done, the Director takes the Car out of the Cradle and puts in into the finishingQueue.

The Cradle is the crux of the signaling operations. A Mutex and a Condition object control both the working of the robots and indicate whether all the operations are finished. A particular type of robot can offer its services to the Cradle by calling the "offer" function appropriate to its type. At this point, that robot thread is suspended until the Director calls startWork( ), which changes the hiring flags and calls broadcast( ) to tell all the robots to show up for work. Although this system allows any number of robots to offer their services, each one of those robots has its thread suspended by doing so. You could imagine a more sophisticated system in which the robots register themselves with many different Cradles without being suspended by that registration process and then reside in a pool waiting for the first Cradle that needs a task completed.

After each robot finishes its task (changing the state of the Car in the process), it calls taskFinished( ), which sends a signal( ) to the readyCondition, which is what the Director is waiting on in waitUntilWorkFinished( ). Each time the director thread awakens, the state of the Car is checked, and if it still isn’t finished, that thread is suspended again.

When the Director inserts a Car into the Cradle, you can perform operations on that Car via the operator->( ). To prevent multiple extractions of the same car, a flag causes an error report to be generated. (Exceptions don’t propagate across threads in the ZThread library.)

In main( ), all the necessary objects are created and the tasks are initialized, with the ChassisBuilder begun last to start the process. (However, because of the behavior of the TQueue, it wouldn’t matter if it were started first.) Note that this program follows all the guidelines regarding object and task lifetime presented in this chapter, and so the shutdown process is safe.

The C++ Programming Language, 3^rd edition, by Bjarne Stroustrup (Addison-Wesley 1997). To some degree, the goal of the book that you’re currently holding is to allow you to use Bjarne’s book as a reference. Since his book contains the description of the language by the author of that language, it’s typically the place where you’ll go to resolve any uncertainties about what C++ is or isn’t supposed to do. When you get the knack of the language and are ready to get serious, you’ll need it.

C++ Primer, 3^rd Edition, by Stanley Lippman and Josee Lajoie (Addison-Wesley 1998). Not that much of a primer anymore; it’s evolved into a thick book filled with lots of detail, and the one that I reach for along with Stroustrup’s when trying to resolve an issue. Thinking in C++ should provide a basis for understanding the C++ Primer as well as Stroustrup’s book.

Accelerated C++, by Andrew Koenig and Barbara Moo (Addison-Wesley, 2000). Takes you through C++ by programming topic instead of language feature. Excellent introductory book.

The C++ Standard Library, by Nicolai Josuttis (Addison-Wesley, 1999). Readable tutorial and reference for the entire C++ library, including STL. Assumes familiarity with language concepts.

STL Tutorial and Reference Guide, 2nd Edition, by David R. Musser et al (Addison-Wesley, 2001). Gentle but thorough introduction to the concepts underlying STL. Contains an STL reference manual.

The C++ ANSI/ISO Standard. This is not free, unfortunately (I certainly didn’t get paid for my time and effort on the Standards Committee—in fact, it cost me a lot of money). But at least you can buy the electronic form in PDF for only $18 at http://www.cssinfo.com.

Bruce’s books

Listed in order of publication. Not all these are currently available.

Computer Interfacing with Pascal & C, (Self-published via the Eisys imprint, 1988. Only available via www.BruceEckel.com). An introduction to electronics from back when CP/M was still king and DOS was an upstart. I used high-level languages and often the parallel port of the computer to drive various electronic projects. Adapted from my columns in the first and best magazine I wrote for, Micro Cornucopia. (To paraphrase Larry O’Brien, long-time editor of Software Development Magazine: The best computer magazine ever published—they even had plans for building a robot in a flower pot!) Alas, Micro C became lost long before the Internet appeared. Creating this book was an extremely satisfying publishing experience.

Using C++, (Osborne/McGraw-Hill, 1989). One of the first books out on C++. This is out of print and replaced by its second edition, the renamed C++ Inside & Out.

C++ Inside & Out, (Osborne/McGraw-Hill, 1993). As noted, actually the second edition of Using C++. The C++ in this book is reasonably accurate, but it's circa 1992 and Thinking in C++ is intended to replace it. You can find out more about this book and download the source code at www.BruceEckel.com.

Thinking in C++, 1^st Edition, (Prentice Hall, 1995). Winner of the Software Development Magazine Jolt Award for best book of 1995.

Thinking in C++, 2^nd Edition, Volume 1, (Prentice Hall, 2000). Downloadable from www.BruceEckel.com.

Black Belt C++: the Master’s Collection, Bruce Eckel, editor (M&T Books, 1994). Out of print (often available through out-of-print services on the Web). A collection of chapters by various C++ luminaries based on their presentations in the C++ track at the Software Development Conference, which I chaired. The cover on this book stimulated me to gain control over all future cover designs.

Thinking in Java, 1^st Edition, (Prentice Hall, 1998). The first edition of this book won the Software Development Magazine Productivity Award, the Java Developer’s Journal Editor’s Choice Award, and the JavaWorld Reader’s Choice Award for best book. On the CD ROM in the back of this book, and downloadable from www.BruceEckel.com.

Thinking in Java, 2^nd Edition, (Prentice Hall, 2000). This edition won the JavaWorld Editor’s Choice Award for best book. On the CD ROM in the back of this book, and downloadable from www.BruceEckel.com.

Thinking in Java, 3^rd Edition, (Prentice Hall, 2002). This edition won the Software Development Magazine Jolt Award for best book of 2002, and the Java Developer’s Journal Editor’s Choice Award. The new CD ROM in the back of this book now includes the first seven lectures from the 2^nd edition of the Hands-On Java CD ROM.

The Hands-On Java CD ROM, 3^rd edition (MindView, 2003). Over 15 hours of lectures and slides covering the basics of the Java language, based on Thinking in Java, 3^rd Edition. Available only at www.MindView.net.

Chuck’s books

C & C++ Code Capsules, by Chuck Allison (Prentice-Hall, 1998). Assumes that you already know C and C++, and covers some of the issues that you may be rusty on, or that you may not have gotten right the first time. This book fills in C gaps as well as C++ gaps.[ ]

Thinking in C: Foundations for Java & C++, by Chuck Allison (not actually a book, but a MindView, Inc. Seminar on CD ROM, 1999, bundled with Thinking in Java and Thinking in C++, Volume 1). A multimedia course including lectures and slides in the foundations of the C Language to prepare you to learn Java or C++. This is not an exhaustive course in C; only the necessities for moving on to the other languages are included. An extra section covering features for the C++ programmer is included. Prerequisite: experience with a high-level programming language, such as Pascal, BASIC, FORTRAN, or LISP.