Why Linux is safer than Windows

Why Linux is safer than Windows.

Two ISIS suicide bombers board planes with laptops packed with explosives.
One has Windows on it with a GUI app, the other, Linux with a command line app…

**** Linux ****
Opens terminal.

$ explode
bash: explode: command not found…

$ Explode
bash: Explode: command not found…

$ bomb -explode
bash: bomb: command not found…

$ isisbmb -explode
Command line error: no such option:

$ isisbmb -h
Command line error: no such option:

$ isisbmb –help
Command line error: no such option:

$ isisbmb -e
Permission denied

$ sudo isisbmb -e
Fuse dependencey not found.

$ yum install Fuse
You need to be root to perform this command.

$ sudo yum install Fuse
No package Fuse available.
Error: Nothing to do

$ sudo yum install fuse
No package fuse available.
Error: Nothing to do

Realises that, as they are now in the air, there’s no network connection.

The plane lands and the disillusioned bomber turns himself in to the authorities.

**** Windows ****
Runs ‘Bomb’ app from start menu.
Clicks ‘Explode’ button.
KABOOM!!!

The Embedded Template Library

Why did I start it?

I wrote the Embedded Template Library (ETL), and all the others I have written over the years, because I’m lazy.
Yes, lazy! But in a good way I believe. See here.

Don’t Re-invent The Wheel

I hate having to code yet another variation of the same thing in a slightly different way time and and time again.
Reinventing the wheel every time is daft for many reasons.

Code bloat

Multiple instances of slight variations of a theme results in an increase in code size due to no commonality of functionality.

Testing, more testing or no testing

Are all the variants tested to the same degree? Are some even tested at all?

Variable functionality

Not all the variants are going to have the same level of functionality, or the same API. Ad-hoc solutions are invariably only going to solve the little bit of the problem that was needed at the time.

No collective knowledge base

Without commonality every new variant has to be learned. The underlying principles may be understood (i.e. Linked list), but each implementation has to be understood separately, along with its particular caveats and foibles. Documentation is likely to be patchy.

Octopus code

The application is liable to have a close coupling with the solution. For example, I’ve often seen code using linked lists directly accessing the node pointers. Ad-hoc solutions are liable to have lazy (the bad kind) implementations.

The Beginnings

I’ve been working with software that has had deterministic requirements for most of my programming career. Some of the latest ones involved image processing and feature extraction from objects passing a camera on a conveyor. The objects travelled fast and the gaps between them were small. For example, I once designed software for mail sorting machines where mail items could be travelling of speeds up to 4 metres per second with gaps of around 40mm. Finishing the processing on time was paramount, as a late result would cause the mail item to end up in the ‘hand sort’ bin. For a run of 30,000 mail items you don’t really want that sort of thing happening very often! As we were writing the application in C++ the STL was a very useful library to draw from, but one part of it has issues when used in conjunction with real-time applications.

The containers.

Virtually all of the containers in the STL, by default, get storage from the heap. This is a bit of a no-no for real-time software as the allocation and release of memory from the default heap is somewhat non-deterministic. There are a couple of tricks that can be done to try to alleviate the issues, such as reserving the size of vectors upfront, but it can only get you so far.

There are a few ways in which the programmer can try to get around them.

Create your own replacement for malloc/new

By writing a super optimised global malloc/new replacement you may be able to get the worst case times down to something acceptable for your application. You may have to address issues raised by multiple threads accessing the memory allocator concurrently. But what happens at run-time if the heap becomes too fragmented or you run out of heap space? In my experience it will crash during the demo in front of the customer.

Create your own STL allocator

One solution is to create an allocator similar to the malloc/new replacement, along with its threading, fragmentation and free space issues.

Another is to allow the allocator to contain its own fixed sized storage. This is a solution I used successfully for a while, but there turned out to be issues when porting between compilers, even versions of the same compiler. In the end I abandoned this idea.

Create a new set of STL like containers

Although a lot more work than custom STL allocators, creating a set of custom containers, specifically optimised for operating on internally declared contiguous blocks of memory, can bring great performance advantages. It also has the advantage of being more amenable to static analysis; All of the memory that may be used in a container is declared up front. This is very handy for allowing the application fail on the developer’s desk at compile time, instead in front of the customer at run-time.

Before I started to write the ETL I had built up a collection of ideas, sample code and early versions of containers, but they were not organised in any sort of library. Whenever I looked for the sort of library that met my specifications I could never find anything that really matched. All of the ones that I found were either limited in scope, or would drop back to using the heap when the initial reserved capacity was exceeded. I decided that the best course was to gather together all of my ideas and experiments and build them into the sort of library that I would want to find myself. I assumed that there were others out there that were also searching for the same sort of thing.

At the time, the chance of finding an embedded compiler that supported C++11 or above was fairly remote. I once talked to Keil back in 2014 about C++11 support and at the time the answer was basically “don’t hold your breath”. So I decided that the library must be compatible with C++03. As there were some very useful additions in C++11 I also decided to reverse engineer as many as were practical.

Requirements

MIT licence

Have you ever come across what looks like the perfect library, only to find it’s GPL and therefore unusable in your company? I want anyone to be able to use it, how they like.

Just don’t say you wrote it (unless you did).

Cross platform

I want it to work on all targets and platforms.

C++03 compatibilty

As I said before, C++11 and above was not always an option for embedded compilers back then. For many it still isn’t.

No dynamic memory allocation

All storage is allocated either at compile time or on the stack. The library should not use the heap at all.

No RTTI required

Lowers the overhead.

Very little use of virtual functions

I’m not one of those that thinks virtual functions are the root of all evil in embedded software. Sometimes they are extremely useful and the alternative would be clunky and awkward and sometimes just C++ virtuals in another form. At other times a slightly different technique can eliminate a lot of them with little pain. They should be used only when they are absolutely necessary for the required functionality.

A set of fixed capacity containers

A fixed capacity version of all of the standard containers, plus a few useful extra ones. As the storage for the container types is allocated as a contiguous block, they are extremely cache friendly.

Reduced container code size through use of base classes dependant on type only

A technique sometimes known as ‘hoisting’. There is a top level class that knows type and size. This inherits from a class that contains functionality that is only interested in the type. This may also inherit from a base class that is both type and size agnostic.

Templated compile time constants

Helper templates that calculate constants at compile time. Sometimes useful when included inside another template.
i.e. When an internal constant is Log2 of a non-type template parameter constant.

Templated design pattern base classes

I say, let the templated boiler plate code do the work.

Frameworks for message routing, finite state machines and task scheduling

When have you not needed something like this for any non-trivial application, especially for bare bones systems? Don’t reinvent the wheel every time.

Reverse engineered C++ 0x11 features (type traits, algorithms, containers etc.)

There’s some useful stuff in the later releases of the STL.

Type-safe smart enumerations

A way of reducing many hard to find bugs where a constant from one enum is used where another was expected.

Type-safe typedefs + constants

See above.

8, 16, 32 & 64 bit CRC, checksums & hash functions

We’ve written them, so you don’t have to.

Variants (a type-safe union)

No more messing with unions and/or void*

Choice of asserts, exceptions, error handler or no checks on errors

How you repond to errors is up to you. The ETL does not dictate.

Many utilities for template support

Allowing you the ability to set types and constants according to the template parameters, allowing static asserts to perform concept checks.

Unit tested

So we can avoid accidently breaking anything.

Easy to read and documented source

But we all do this anyway don’t we?

Free email support

That’s what I would want, so that’s what you get.

Continuous integration testing

Every push is automatically unit tested, just in case we messed up and didn’t do our job properly (Perish the thought!)

Conclusion

The Embedded Template Library has been available on git for several years now and I’ve had great feedback from users and potential users from around the globe.
The ETL has been improved immeasurably by their input and I can’t thank them enough, especially Ryan Lindeman who did sterling work creating the map and set containers.

The ETL is at a good point at the moment, so I’m taking a little time off from adding any major new features (and I have several ideas in the pipeline) while I work on this blog and try to make a start at writing an ebook. I’ve not decided on a title as yet, but I intend it to be a sort of cook-book of C++ template techniques, especially tailored towards embedded and real-time platforms. A lot of the information in it will draw from the work in the ETL.

There are four types of programmer

Their is a story about a German general that declared that there were four kinds of people, only three of which he wanted in his army.

Here’s my take on it from a programmer’s angle.
 
Intelligent Lazy
Intelligent lazy people hate having to reinvent a solution to a problem that has already been solved. Moreover they don’t always go for the first solution that comes to mind. They would prefer the best solution; the one that means you don’t have to go through all of the problem solving work all over again when a slight variation turns up. They’re the ones that build a generic library with built-in extensibility. It will probably conform to SOLID principles. Their downside is that they may have a tendency to over engineer things at times.
 
Intelligent Active
These people are productive and can come up with working solutions in a short amount of time. They’re great when you need a quick and dirty solution. The downside is that that’s what you may get a lot of the time. A mixture of Intelligent Lazy & Intelligent Active in some proportion may be useful as they will tend to temper each other’s excesses.
Or they may just annoy each other like crazy.
 
Stupid Lazy
These sort of people aren’t really smart enough to be superstar programmers, but, given clear enough instructions, can be fairly productive. Just don’t ask them to design a new framework. They won’t design one on their own as they don’t tend to take the initiative.
 
Stupid Active
These are the dangerous ones! They don’t really know what they’re doing, but either they think they do or just have a go anyway. These are the ones that make you groan with despair at code review time. They write brittle code, they write complex code with subtle bugs. They leave chaos in the code base they persists for years, if not forever.
 
I like to think that I come under the Intelligent Lazy label. One of the things I really hate when writing software is having to do the same, or something almost the same, over and over again. The first thing I think when presented with a problem that requires a specific set of functionality is “Is this a specific case of a more generic problem?”. Surprisingly, I can say “yes” more often than you would expect. Even if not all of the problem can be seen as generic, there are almost certainly parts that are. In every job I’ve had I’ve left an extensive code library behind me.

Largest / Smallest. Part 2

In the last post i showed you how to implement a ‘Largest’ traits template using pre-C++11.
In this post I will show you how to do the same using variadic templates.

First we declare the ‘bare’ template. It tells the compiler that ‘Largest’ take an unknown number of template parameters.

template <typename... Types>
struct Largest {};

Next, we create helper templates as we did before. In fact they are identical.

// Declaration.
template <const bool Boolean, typename TrueType, typename FalseType>
struct ChooseType;

// Specialisation for 'true'.
// Defines 'type' as 'TrueType'.
template <typename TrueType, typename FalseType>
struct ChooseType<true, TrueType, FalseType>
{
  typedef TrueType type;
};

// Specialisation for 'false'. 
// Defines 'type' as 'FalseType'.
template <typename TrueType, typename FalseType>
struct ChooseType<false, TrueType, FalseType>
{
  typedef FalseType type;
};

The main part of the template is very similar to before, but this time we just use the ellipsis as the type list.

typedef typename ChooseType<(sizeof(T1) > sizeof(typename Largest<Types...>::type)), // Boolean
                             T1,                                                     // TrueType
                             typename Largest<Types...>::type>                       // FalseType
                             ::type type;                                            // The largest type of the two.

Finally, as before we need a ‘stopper’ definition to tell the compiler when we’ve reached the end.

template <typename T1>
struct Largest<T1>
{
  typedef T1 type;
};

Putting it all together again we get…

template <typename... Types>
struct Largest {};

template <typename T1, typename... Types>
struct Largest<T1, Types...>
{
private:

  // Declaration.
  template <const bool Boolean, typename TrueType, typename FalseType>
  struct ChooseType;

  // Specialisation for 'true'.
  // Defines 'type' as 'TrueType'.
  template <typename TrueType, typename FalseType>
  struct ChooseType<true, TrueType, FalseType>
  {
    typedef TrueType type;
  };

  // Specialisation for 'false'. 
  // Defines 'type' as 'FalseType'.
  template <typename TrueType, typename FalseType>
  struct ChooseType<false, TrueType, FalseType>
  {
    typedef FalseType type;
  };

public:

  // Set 'type' to be the largest of the first parameter and any of the others.
  // This is recursive.
  typedef typename ChooseType<(sizeof(T1) > sizeof(typename Largest<Types...>::type)), // Boolean
                               T1,                                                     // TrueType
                               typename Largest<Types...>::type>                       // FalseType
                               ::type type;                                            // The largest type of the two.                                        
};

template <typename T1>
struct Largest<T1>
{
  typedef T1 type;
};

How It’s Used

template typename T1, typename T2, typename T3>
struct Buffer
{
  char buffer[sizeof(typename Largest<T1, T2, T3>::type)];
};

This variation has the advantage that it can handle any number of type, up to the capacity of the compiler.

You no doubt see that an additional template to handle smallest should be a trivial task.
Other additions to the templates could include the min/max size and alignment as traits.

Largest / Smallest. Part 1

Sometimes, when multiple types are sent as template parameters, some information about the types needs to be interrogated to be able to configure another property of the template. The STL’s type traits header does a good job of supplying many of the more useful ones, but there is room for extension. Say, for instance, the template implements a type of variant container; a type of smart union. The container may store one of several types declared in the template parameter list. We need to allocate storage for this, but how determine the size?

template typename T1, typename T2, typename T3>
struct Buffer
{
	char buffer[???]; // Wouldn't it be nice to have something simple here,
	                  // rather than manually typing a lot of nested sizeof() boilerplate?
};

We can use template meta programming to help us here.

Here I will show you two variations; one for pre C++11 compilers that don’t support variadic templates and one for those that do.

Let’s say that we want to be able to handle up to four types. The ‘= void’ allows one, two, three or four types to be specified.

template <typename T1, typename T2 = void, typename T3 = void, typename T4 = void>
strut Largest
{
};

First, let’s create a helper template to determine the largest of two types.

// Declaration.
template <const bool Boolean, typename TrueType, typename FalseType>
struct ChooseType;

// Specialisation for 'true'.
// Defines 'type' as 'TrueType'.
template <typename TrueType, typename FalseType>
struct ChooseType<true, TrueType, FalseType>
{
  typedef TrueType type;
};

// Specialisation for 'false'. 
// Defines 'type' as 'FalseType'.
template <typename TrueType, typename FalseType>
struct ChooseType<false, TrueType, FalseType>
{
  typedef FalseType type;
};

These templates will define their ‘type’ to either that of TrueType or FalseType dependent on the condition supplied.

Next we create a recursive typedef that chooses the largest type between the first template parameter type and all of the rest. We typedef ‘all of the rest’ for clarity.

// Define 'LargestOther' as 'Largest' with all but the first parameter. 
typedef typename Largest<T2, T3, T4>::type LargestOther;

Now the recursive bit.

typedef typename ChooseType<(sizeof(T1) > sizeof(LargestOther)), // Boolean
                             T1,                                 // TrueType
                             LargestOther>                       // FalseType
                             ::type type;                        // The largest type of the two.

The compiler will recursively parse the template until there is one type to test. Here we need something to stop the compiler attempting to parse any further.
What we do is to add a specialisation for the final single type.

//***************************************************************************
// Specialisation for one template parameter.
//***************************************************************************
template <typename T1>
struct Largest<T1,   void, void, void>
{
  typedef T1 type;

  enum
  {
    size = sizeof(type)
  };
};

Putting this all together we get…

template <typename T1, typename T2 = void, typename T3 = void, typename T4 = void>
  struct Largest
{
private:

  // Declaration.
  template <const bool Boolean, typename TrueType, typename FalseType>
  struct ChooseType;

  // Specialisation for 'true'.
  // Defines 'type' as 'TrueType'.
  template <typename TrueType, typename FalseType>
  struct ChooseType<true, TrueType, FalseType>
  {
    typedef TrueType type;
  };

  // Specialisation for 'false'. 
  // Defines 'type' as 'FalseType'.
  template <typename TrueType, typename FalseType>
  struct ChooseType<false, TrueType, FalseType>
  {
    typedef FalseType type;
  };

public:

  // Define 'LargestOther' as 'Largest' with all but the first parameter. 
  typedef typename Largest<T2, T3, T4>::type LargestOther;

  // Set 'type' to be the largest of the first parameter and any of the others.
  // This is recursive.
  typedef typename ChooseType<(sizeof(T1) > sizeof(LargestOther)), // Boolean
                               T1,                                 // TrueType
                               LargestOther>                       // FalseType
                               ::type type;                        // The largest type of the two.
};

//***************************************************************************
// Specialisation for one template parameter.
//***************************************************************************
template <typename T1>
struct Largest<T1, void, void, void>
{
  typedef T1 type;
};

How It’s Used

template typename T1, typename T2, typename T3>
struct Buffer
{
	char buffer[sizeof(typename Largest<T1, T2, T3>::type)];
};

The number of types that can be handled is easily increased.

This is the technique used in the Embedded Template Library to implement largest/smallest traits.

In the next post I’ll show you how to achieve the same with variadic templates.

Templated implementation of the Observer Pattern

The purpose of this template is to simplify the creation of classes that implement the Observer Pattern and attempt to eliminate certain runtime errors by turning them into compile time errors. The pattern consists of two template classes. Observer and Observable.

Observable

The class derived from this will be observed by classes derived from Observer. It keeps a list of registered observers and will notify all of them with the raised notifications.
It is parameterised by a supplied observer type.

void AddObserver(TObserver& observer)
Registers an observer with the observable class.

void RemoveObserver(TObserver& observer)
Unregisters an observer.

void ClearObservers()
Unregister all of the observers.

size_type NumberOfObservers()
Gets the number of registered observers.

template <typename TNotification>
void NotifyObservers(TNotification n)

Notifies all of the registered observers with the notification ‘n’.

  template <typename TObserver>
  class observable
  {
  public:

    typedef size_t size_type;

    typedef std::vector<TObserver*> ObserverList;

    //*****************************************************************
    /// Add an observer to the list.
    //*****************************************************************
    void AddObserver(TObserver& observer)
    {
		  // See if we already have it in our list.
      typename ObserverList::const_iterator i_observer = std::find(observer_list.begin(),
                                                                   observer_list.end(),
                                                                   &observer);

		  // Not there?
      if (i_observer == observer_list.end())
      {
        // Add it.
        observer_list.push_back(&observer);
      }
    }

    //*****************************************************************
    /// Remove a particular observer from the list.
    //*****************************************************************
    void RemoveObserver(TObserver& observer)
    {
      // See if we have it in our list.
      typename ObserverList::iterator i_observer = std::find(observer_list.begin(),
                                                             observer_list.end(),
                                                             &observer);

      // Found it?
      if (i_observer != observer_list.end())
      {
        // Erase it.
        observer_list.erase(i_observer);
      }
    }

    //*****************************************************************
    /// Clear all observers from the list.
    //*****************************************************************
    void ClearObservers()
    {
      observer_list.clear();
    }

    //*****************************************************************
    /// Returns the number of observers.
    //*****************************************************************
    size_type NumberOfObservers() const
    {
      return observer_list.size();
    }

    //*****************************************************************
    /// Notify all of the observers, sending them the notification.
    /// TNotification is the notification type.
    //*****************************************************************
    template <typename TNotification>
    void NotifyObservers(TNotification n)
    {
      for (size_t i = 0; i < observer_list.size(); ++i)
      {
        observer_list[i]->Notification(n);
      }
    }

  private:

    /// The list of observers.
    ObserverList observer_list;
  };

Observer

This template may take up to N notification types.
Each notification type will generate a pure virtual ‘notification’ function. The class that inherits from this must define all of the ‘Notification’ function overloads otherwise the object will remain abstract and will not compile. This ensures that no notification overload can be omitted.

The example below gives the derived observer class the capacity to handle four notification types. A script may be used to generate code that can handle any number of types.
The method that the notification parameter is passed to the notification handler is specified in the template type parameter.
i.e. If the notification is to be passed as const reference to a strut called ‘Info’ then the template type parameter would be declared as const Info&.

//*********************************************************************
  /// The Observer interface for four notification types.
  ///\ingroup Observer
  //*********************************************************************
  template <typename T1, typename T2  = void, typename T3  = void, typename T4  = void>
  class Observer
  {
  public:
    virtual ~Observer() {}
    virtual void Notification(T1) = 0;
    virtual void Notification(T2) = 0;
    virtual void Notification(T3) = 0;
    virtual void Notification(T4) = 0;
  };

  //*********************************************************************
  /// The Observer interface for three notification types.
  ///\ingroup Observer
  //*********************************************************************
  template <typename T1, typename T2, typename T3>
  class Observer<T1, T2, T3>
  {
  public:

    virtual ~Observer() {}
    virtual void Notification(T1) = 0;
    virtual void Notification(T2) = 0;
    virtual void Notification(T3) = 0;
  };

  //*********************************************************************
  /// The Observer interface for two notification types.
  ///\ingroup Observer
  //*********************************************************************
  template <typename T1, typename T2>
  class Observer<T1, T2>
  {
  public:

    virtual ~Observer() {}
    virtual void Notification(T1) = 0;
    virtual void Notification(T2) = 0;
  };

  //*********************************************************************
  /// The Observer interface for one notification type.
  ///\ingroup Observer
  //*********************************************************************
  template <typename T1>
  class Observer<T1>
  {
  public:

    virtual ~Observer() {}
    virtual void Notification(T1) = 0;
  };

In use

First we define three different notification types.

//*****************************************************************************
// Notification1
//*****************************************************************************
struct Notification1
{
  // Some data.
};

//*****************************************************************************
// Notification2
//*****************************************************************************
struct Notification2
{
  // Some data.
};

//*****************************************************************************
// Notification3
//*****************************************************************************
struct Notification3
{
  // Some data.
};

Next we declare the base observer type.
Note that Notification1 is passed by value, Notification2 is passed by reference and Notification3 is passed by const reference.

//*****************************************************************************
// The observer base type.
// Declare what notifications you want to observe and how they are passed to 'notification'.
// Notification1 is passed by value.
// Notification2 is passed by reference.
// Notification3 is passed by const reference.
//*****************************************************************************
typedef Observer<Notification1, Notification2&, const Notification3&> ObserverType;

Now we define an observable class that that can be observed by classes derived from ObserverType

//*****************************************************************************
// The concrete observable class.
//*****************************************************************************
class Observable1 : public Observable<ObserverType>
{
public:
  
  Notification1 data1;
  Notification2 data2;
  Notification3 data3;

  //*********************************
  // Notify all of the observers.
  //*********************************
  void SendNotifications()
  {
    notify_observers(data1);
    notify_observers(data2);
    notify_observers(data3);
  }
};

Let’s now define two observer classes. Both are able to accept notifications Notification1, Notification2 and Notification3.

//*****************************************************************************
// The first observer type.
// If any one of the overloads is missing or a parameter declaration is incorrect
// then the class will be 'abstract' and will not compile.
//*****************************************************************************
class Observer1 : public ObserverType
{
public:

  //*******************************************
  // Notification1 is passed by value.
  //*******************************************
  void notification(Notification1 n)
  {
    // Do something with n.
  }

  //*******************************************
  // Notification2 is passed by reference.
  //*******************************************
  void notification(Notification2& n)
  {
    // Do something with n.
  }

  //*******************************************
  // Notification3 is passed by const reference.
  //*******************************************
  void notification(const Notification3&)
  {
    // Do something with n.
  }
};

//*****************************************************************************
// The second observer type.
// If any one of the overloads is missing or a parameter declaration is incorrect
// then the class will be 'abstract' and will not compile.
//*****************************************************************************
class Observer2 : public ObserverType
{
public:

  //*******************************************
  // Notification1 is passed by value.
  //*******************************************
  void notification(Notification1 n)
  {
    // Do something with n.
  }

  //*******************************************
  // Notification2 is passed by reference.
  //*******************************************
  void notification(Notification2& n)
  {
    // Do something with n.
  }

  //*******************************************
  // Notification3 is passed by const reference.
  //*******************************************
  void notification(const Notification3&)
  {
    // Do something with n.
  }
};

Now the test code.

// The observable objects.
Observable1 observable1;

// The observer objects.
Observer1 observer1;
Observer2 observer2;

observable1.AddObserver(observer1);
observable1.AddObserver(observer2);

// Send the notifications.
observable1.SendNotifications();

A version of this framework can be found as part of the Embedded Template Library, an open source C++ library distributed under the MIT licence.

Templated implementation of the Visitor Pattern

Introduction

There are probably many of you out there who, like me, have investigated the possibilities that templates and template meta-programming can bring to your code.

After having some success with templated image and image algorithm classes, I turned my attention to seeing whether some of the design patterns I use could be encapsulated in the same way. Investigation on the web revealed that template meta-programming could play a part in achieving this.

An article on Dr Dobbs introduced me to typelists and some of the meta-programming techniques, with the Visitor pattern used as an example.

Unfortunately, I soon found that Visual C++ was not entirely happy with the syntax used and it took some time before I managed to get a version that didn’t give the compiler indigestion! That didn’t last long, though. Instantiating my first Visitor object caused the compiler to generate the dreaded “Internal compiler error. Try simplifying your code”. Well, I gave up at that point, deciding I had better things to do with my life than battling my compiler. So, I decided to try and achieve the similar objective to the Visitor example without meta-programming.

Anyone unfamiliar with the Visitor pattern should read this first.

The objective of the Dr Dobbs example was merely to remove a small amount of boilerplate code and ensure that all handling omissions in all code would be flagged at compile time.

The use of this technique in the Visitor pattern may seem somewhat trivial, but I hope that you may find the methods used useful in more complex situations, despite it not being as ‘cool’ as using typelists and meta-programming.

How It Works

The purpose of these classes is to create a Visitor base class with pure virtual Visit functions for each supplied type. Any derived class that tries to instantiate an object from it will then be forced to supply an overridden version for each and every Visit function.

Similarly the Visitable class defines pure virtual Accept function for each supplied visitor type.

The framework is based on two template classes; Visitor & Visitable.

Visitable

Classes that should be visitable should derive from the Visitable template class. The classes that may visit should be defined in the template type parameter list.
Here I have defined a template and specialisations to accept up to 4 visitor types.

//*****************************************************************
/// The visitable base class for four visitor types.
//*****************************************************************
template <typename T1, typename T2 = void, typename T3 = void, typename T4 = void>
class Visitable
{
public:

  virtual void Accept(T1&) = 0;
  virtual void Accept(T2&) = 0;
  virtual void Accept(T3&) = 0;
  virtual void Accept(T4&) = 0;
};

//*****************************************************************
/// The visitable base class for three visitor types.
//*****************************************************************
template <typename T1, typename T2, typename T3>
class Visitable<T1, T2, T3>
{
public:

  virtual void Accept(T1&) = 0;
  virtual void Accept(T2&) = 0;
  virtual void Accept(T3&) = 0;
};

//*****************************************************************
/// The visitable base class for two visitor types.
//*****************************************************************
template <typename T1, typename T2>
class Visitable<T1, T2>
{
public:

  virtual void Accept(T1&) = 0;
  virtual void Accept(T2&) = 0;
};

//*****************************************************************
/// The visitable base class for one visitor type.
//*****************************************************************
template <typename T1>
class Visitable<T1>
{
public:

  virtual void Accept(T1&) = 0;
};

Visitor

Classes that should be able to visit visitable classes should derive from the Visitor template class. The types that the visitor expects to support should be defined in the template type parameter list.

Here I have defined a template and specialisations to accept up to 16 types types. It may seem like it would be an onerous task to modify this to accept any N types, but the repetitive nature of the code lends itself perfectly to generation via a script.

//*****************************************************************
/// The visitor base class for sixteen types.
//*****************************************************************
template <typename T1,         typename T2  = void, typename T3  = void, typename T4  = void,
          typename T5  = void, typename T6  = void, typename T7  = void, typename T8  = void,
          typename T9  = void, typename T10 = void, typename T11 = void, typename T12 = void,
          typename T13 = void, typename T14 = void, typename T15 = void, typename T16 = void>
  class Visitor
{
public:

  virtual void Visit(T1&) = 0;
  virtual void Visit(T2&) = 0;
  virtual void Visit(T3&) = 0;
  virtual void Visit(T4&) = 0;
  virtual void Visit(T5&) = 0;
  virtual void Visit(T6&) = 0;
  virtual void Visit(T7&) = 0;
  virtual void Visit(T8&) = 0;
  virtual void Visit(T9&) = 0;
  virtual void Visit(T10&) = 0;
  virtual void Visit(T11&) = 0;
  virtual void Visit(T12&) = 0;
  virtual void Visit(T13&) = 0;
  virtual void Visit(T14&) = 0;
  virtual void Visit(T15&) = 0;
  virtual void Visit(T16&) = 0;
};

//*****************************************************************
/// The visitor base class for fifteen types.
//*****************************************************************
template <typename T1,  typename T2,  typename T3,  typename T4,
          typename T5,  typename T6,  typename T7,  typename T8,
          typename T9,  typename T10, typename T11, typename T12,
          typename T13, typename T14, typename T15>
  class Visitor<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15>
{
public:

  virtual void Visit(T1&) = 0;
  virtual void Visit(T2&) = 0;
  virtual void Visit(T3&) = 0;
  virtual void Visit(T4&) = 0;
  virtual void Visit(T5&) = 0;
  virtual void Visit(T6&) = 0;
  virtual void Visit(T7&) = 0;
  virtual void Visit(T8&) = 0;
  virtual void Visit(T9&) = 0;
  virtual void Visit(T10&) = 0;
  virtual void Visit(T11&) = 0;
  virtual void Visit(T12&) = 0;
  virtual void Visit(T13&) = 0;
  virtual void Visit(T14&) = 0;
  virtual void Visit(T15&) = 0;
};

//*****************************************************************
// The same pattern is repeated for each decreasing number of parwameters until...
//*****************************************************************

//*****************************************************************
/// The visitor base class for one type.
//*****************************************************************
template <typename T1>
class Visitor<T1>
{
public:

  virtual void Visit(T1&) = 0;
};

How It’s Used

I’ll use the good old ‘Shape’ example so loved by many.

First, you create the base for your ‘Shape’ visitor.

//*****************************************************************
// Pre-declare the shapes.
//*****************************************************************
class Square;
class Circle;
class Triangle;

//*****************************************************************
// The shape visitor base class.
// Pure virtual 'Visit' functions will be defined for the Square,
// Circle, and Triangle types.
//*****************************************************************
class ShapeVisitor : public Visitor<Square, Circle, Triangle>
{
};

Then, you define the ‘Shape’ base class. It derives from the Visitable class that defines a pure virtual ‘Accept’ function that accepts a ShapeVisitor.

//*****************************************************************
// The shape base class.
//*****************************************************************
class Shape : public Visitable<ShapeVisitor>
{
};

Next, you define the shapes ‘Square’, ‘Circle’, and ‘Triangle’. Each overrides the ‘Accept’ function that calls the visitor with itself as a parameter.

//*****************************************************************
// The square class
//*****************************************************************
class Square : public Shape
{
  void Accept(ShapeVisitor& visitor)
  {
    visitor.Visit(*this);
  }
};

//*****************************************************************
// The circle class
//*****************************************************************
class Circle : public Shape
{
  void Accept(ShapeVisitor& visitor)
  {
    visitor.Visit(*this);
  }
};

//*****************************************************************
// The triangle class
//*****************************************************************
class Triangle : public Shape
{
  void Accept(ShapeVisitor& visitor)
  {
    visitor.Visit(*this);
  }
};

Now that you have the framework in place, you can do something with it. Here’s an example that creates ‘Draw’ and ‘Serialise’ visitors and applies them to a vector of Shape objects.

//*****************************************************************
// The 'draw' visitor.
//*****************************************************************
class DrawVisitor : public ShapeVisitor
{
public:
    void Visit(Square& square)
    {
        std::cout << "Draw the square\n";
    }

    void Visit(Circle& circle)
    {
        std::cout << "Draw the circle\n";
    }

    void Visit(Triangle& triangle)
    {
        std::cout << "Draw the triangle\n";
    }
};

//*****************************************************************
// The 'serialise' visitor.
//*****************************************************************
class SerialiseVisitor : public ShapeVisitor
{
public:
    void Visit(Square& square)
    {
        std::cout << "Serialise the square\n";
    }

    void Visit(Circle& circle)
    {
        std::cout << "Serialise the circle\n";
    }

    void Visit(Triangle& triangle)
    {
        std::cout << "Serialise the triangle\n";
    }
};

Now we define the actual visitors and a container for shapes.

//*****************************************************************
// The actual visitors.
//*****************************************************************
DrawVisitor      draw_visitor;
SerialiseVisitor serialise_visitor;

//*****************************************************************
// The list of shapes.
//*****************************************************************
std::vector<Shape*> shape_list;

The following is a utility function to apply a visitor to the list of shapes.

//*****************************************************************
// The Apply a visitor.
//*****************************************************************
void Apply(ShapeVisitor &visitor)
{
  for (std::vector<Shape*>::size_type i = 0; i < shape_list.size(); ++i)
  {
    // Send the visitor to the shape.
    shape_list[i]->Accept(visitor);
  }  
}

And now the code to test in all.


//*****************************************************************
// Main
//*****************************************************************
int main()
{
  // Create some shapes.
  Square   square;
  Circle   circle;
  Triangle triangle;

  // Add them to the vector
  shape_list.push_back(&square);
  shape_list.push_back(&circle);
  shape_list.push_back(&triangle);

  // Apply the visitors.
  Apply(draw_visitor);
  Apply(serialise_visitor);

  return 0;
}

The output from the example is as follows…

Draw the square
Draw the circle
Draw the triangle
Serialise the square
Serialise the circle
Serialise the triangle

A version of this framework can be found as part of the Embedded Template Library, an open source C++ library distributed under the MIT licence.

Designing an efficient and low resource messaging framework. Part 3

In the last post I showed how to shrink the vtable overhead and reduce the coupling of the framework.
This time I shall show how to reduce the vtable hit even further using another technique called the Curiously Recurring Template Pattern or CRTP. This oddly name pattern is a way of replacing runtime virtual calls with compile time dispatch. It achieves this by passing the derived class type as a template type parameter to the base class.

template <typename TDerived>
class Base
{
};

class Derived : public Base<Derived>
{
};

By the use of this technique, the base class can be informed of its concrete type at compile time. This allows the base type to directly call member functions in the derived type thereby avoiding an indirect call though the vtable. If the called functions are deemed suitable by the compiler, then they may well be inlined too.

template <typename TDerived>
class Base
{
  void FunctionBase()
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    derived.FunctionDerived()
  }
};

class Derived : public Base<Derived>
{
  void FunctionDerived()
  {
  }
};

This is the technique that we will use for the third version of the messaging framework.
The messages are defined in the same way as before.

class IMessage
{
public:

  IMessage(int id)
    : messageId(id)
  {
  }

  int GetMessageId() const
  {
    return messageId;
  }

private:

  const int messageId;
};

template <int ID_>
class Message : public IMessage
{
public:

  Message()
    : IMessage(ID_)
  {
  }

  enum
  {
    ID = ID_
  };
};

// Message 1.
class Message1 : public Message<1>
{
};

// Message 2.
class Message2 : public Message<2>
{
};

// Message 3.
class Message3 : public Message<3>
{
};

// Message 4.
class Message4 : public Message<4>
{
};

As is the base message processor interface.

class IMessageProcessor
{
public:

  virtual void Receive(const IMessage& msg) = 0;
};

The difference now is in the definitions of the templated message handlers. The derived message processor type is passed as a template type parameter and used to cast the ‘this’ pointer to the true concrete type, allowing direct calls to the handler functions.

template <typename TDerived, typename T1, typename T2 = void, typename T3 = void, typename T4 = void>
class MessageProcessor : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    switch (msg.GetMessageId())
    {
      case T1::ID: derived.Handle(static_cast<const T1&>(msg)); break;
      case T2::ID: derived.Handle(static_cast<const T2&>(msg)); break;
      case T3::ID: derived.Handle(static_cast<const T3&>(msg)); break;
      case T4::ID: derived.Handle(static_cast<const T4&>(msg)); break;
      default: derived.Unhandled(msg); break;
    }
  }
};

template <typename TDerived, typename T1, typename T2, typename T3>
class MessageProcessor<TDerived, T1, T2, T3, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    switch (msg.GetMessageId())
    {
    case T1::ID: derived.Handle(static_cast<const T1&>(msg)); break;
    case T2::ID: derived.Handle(static_cast<const T2&>(msg)); break;
    case T3::ID: derived.Handle(static_cast<const T3&>(msg)); break;
    default: derived.Unhandled(msg); break;
    }
  }
};

template <typename TDerived, typename T1, typename T2>
class MessageProcessor<TDerived, T1, T2, void, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    switch (msg.GetMessageId())
    {
    case T1::ID: derived.Handle(static_cast<const T1&>(msg)); break;
    case T2::ID: derived.Handle(static_cast<const T2&>(msg)); break;
    default: derived.Unhandled(msg); break;
    }
  }
};

template <typename TDerived, typename T1>
class MessageProcessor<TDerived, T1, void, void, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    switch (msg.GetMessageId())
    {
    case T1::ID: derived.Handle(static_cast<const T1&>(msg)); break;
    default: derived.Unhandled(msg); break;
    }
  }
};

The derived message processors are very similar to before, with the exception that the derived class is passed as template type parameter to the base.

class Processor1 : public MessageProcessor<Processor1, Message4, Message2, Message1, Message3>
{
public:

  void Handle(const Message1& msg)
  {
    std::cout << "Processor1 : Message1\n";
  }

  void Handle(const Message2& msg)
  {
    std::cout << "Processor1 : Message2\n";
  }

  void Handle(const Message3& msg)
  {
    std::cout << "Processor1 : Message3\n";
  }

  void Handle(const Message4& msg)
  {
    std::cout << "Processor1 : Message4\n";
  }

  void Unhandled(const IMessage& msg)
  {
    std::cout << "Processor1 : Unhandled IMessage\n";
  }
};

class Processor2 : public MessageProcessor<Processor2, Message3, Message1>
{
public:

  void Handle(const Message1& msg)
  {
    std::cout << "Processor2 : Message1\n";
  }

  void Handle(const Message3& msg)
  {
    std::cout << "Processor2 : Message3\n";
  }

  void Unhandled(const IMessage& msg)
  {
    std::cout << "Processor2 : Unhandled IMessage\n";
  }
};

We now have a message framework where the processor classes contain just one virtual function and where calls to the handler functions are direct.

The tests are defined exactly as in every previous version of the framework, as is the output.

int main()
{
  Processor1 p1;
  Processor2 p2;

  Message1 m1;
  Message2 m2;
  Message3 m3;
  Message4 m4;

  p1.Receive(m1); // "Processor1 : Message1"
  p1.Receive(m2); // "Processor1 : Message2"
  p1.Receive(m3); // "Processor1 : Message3"
  p1.Receive(m4); // "Processor1 : Message4"

  p2.Receive(m1); // "Processor2 : Message1"
  p2.Receive(m2); // "Processor2 : Unhandled IMessage"
  p2.Receive(m3); // "Processor2 : Message3"
  p2.Receive(m4); // "Processor2 : Unhandled IMessage"

  return 0;
}
Processor1 : Message1
Processor1 : Message2
Processor1 : Message3
Processor1 : Message4
Processor2 : Message1
Processor2 : Unhandled IMessage
Processor2 : Message3
Processor2 : Unhandled IMessage

Chain Of Responsibility

If the ability to set a successor message processor is added to IMessageProcessor, the framework is then able to implement the Chain Of Responsibility design pattern.


// IMessageProcessor base class
IMessageProcessor* pSuccessor;

void SetSuccessor(IMessageProcessor& successor)
{
  pSuccessor = &successor;
}

// Derived message processor class
template <typename TDerived, typename T1>
class MessageProcessor<TDerived, T1, void, void, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    switch (msg.GetMessageId())
    {
    case T1::ID: derived.Handle(static_cast<const T1&>(msg)); break;
    default:
	{
	  if (pSuccessor)
	  {
	    pSuccessor->Receive(msg);
      }
	  else
	  {
	    derived.Unhandled(msg); break;
	  }
    }
  }
};

A version of this framework can be found as part of the Embedded Template Library, an open source C++ library distributed under the MIT licence.

Download the example code

Designing an efficient and low resource messaging framework. Part 2

In the last part I showed a pure C++ scheme for creating a simple message processing framework using ‘double dispatch’ or the Visitor Pattern.

In this part I’m going to show you how we can mitigate some of the issues that were raised by using templates and template specialisation. We will be moving away from a pure C++ solution and partly using an old style C idiom.

This issue we are going to address is the requirement for the message processor interface to not only have to know about all of the messages in existence, but also the fact that the interface will have to be modified each a new one is added.

There is an old C technique for implementing a type of polymorphism. It requires that the ‘base’ type contains an id that specifies what concrete type it actually is. We are going to use this technique (C++ purists will be choking on their breakfast about now).

Like before, there is a base message type.

class IMessage
{
public:

  IMessage(int id)
    : messageId(id)
  {
  }

  int GetMessageId() const
  {
    return messageId;
  }

private:

  const int messageId;
};

Unlike before, there is also an intermediate template type.

template <int ID_>
class Message : public IMessage
{
public:

  Message()
    : IMessage(ID_)
  {
  }

  enum
  {
    ID = ID_
  };
};

Now let’s define the four message types again. You will notice that each message has a unique id.
I’ve used hard coded numbers here, but you would probably use named constants or enums in production code.

Messages
// Message 1.
class Message1 : public Message<1>
{
};

// Message 2.
class Message2 : public Message<2>
{
};

// Message 3.
class Message3 : public Message<3>
{
};

// Message 4.
class Message4 : public Message<4>
{
};

The message processor interface is similar to the previous framework except this time Receive is now pure virtual.

class IMessageProcessor
{
public:

  virtual void Receive(const IMessage& msg) = 0;

protected:

  virtual void Unhandled(const IMessage& msg) = 0;
};

There are now intermediate message processor templates. There is one master template and N specialisations. The value of N depends on the maximum number of messages that a particular processor will be expected to handle. This may seem like a bit of a downside, but the repetitive nature of the code lends itself to automatic code generation from a script.

The master message processor template is defined for the maximum number of messages that a processor may handle. C++ purists who have just recovered from their initial chocking episode may succumb to another when they see the static casts, but they are safe as the lines in question will tend to be written and tested at the creation of the framework. Once proven correct they will be so for all instances. The margin for error will be even less if the code generation is scripted.

// Handle the maximum number of messages
template <typename T1, typename T2 = void, typename T3 = void, typename T4 = void>
class MessageProcessor : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    switch (msg.GetMessageId())
    {
      case T1::ID: Handle(static_cast<const T1&>(msg)); break;
      case T2::ID: Handle(static_cast<const T2&>(msg)); break;
      case T3::ID: Handle(static_cast<const T3&>(msg)); break;
      case T4::ID: Handle(static_cast<const T4&>(msg)); break;
      default: Unhandled(msg); break;
    }
  }

protected:

  virtual void Handle(const T1& msg) = 0;
  virtual void Handle(const T2& msg) = 0;
  virtual void Handle(const T3& msg) = 0;
  virtual void Handle(const T4& msg) = 0;
};

The specialisations are defined for all of the other instances.

// Three messages
template <typename T1, typename T2, typename T3>
class MessageProcessor<T1, T2, T3, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    switch (msg.GetMessageId())
    {
    case T1::ID: Handle(static_cast<const T1&>(msg)); break;
    case T2::ID: Handle(static_cast<const T2&>(msg)); break;
    case T3::ID: Handle(static_cast<const T3&>(msg)); break;
    default: Unhandled(msg); break;
    }
  }

protected:

  virtual void Handle(const T1& msg) = 0;
  virtual void Handle(const T2& msg) = 0;
  virtual void Handle(const T3& msg) = 0;
};

// Two messages
template <typename T1, typename T2>
class MessageProcessor<T1, T2, void, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    switch (msg.GetMessageId())
    {
    case T1::ID: Handle(static_cast<const T1&>(msg)); break;
    case T2::ID: Handle(static_cast<const T2&>(msg)); break;
    default: Unhandled(msg); break;
    }
  }

protected:

  virtual void Handle(const T1& msg) = 0;
  virtual void Handle(const T2& msg) = 0;
};

// One message
template <typename T1>
class MessageProcessor<T1, void, void, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    switch (msg.GetMessageId())
    {
    case T1::ID: Handle(static_cast<const T1&>(msg)); break;
    default: Unhandled(msg); break;
    }
  }

protected:

  virtual void Handle(const T1& msg) = 0;
};

Now all a concrete message processor has to do is to specify which messages it would like to handle. This has the advantage in that if a message is specified in the template parameter list, but a handler is not implemented, then a compiler error will result.

Processor1 is configured to handle Message1, Message2, Message3 and Message4. Note that the order of the message types is not important.

class Processor1 : public MessageProcessor<Message4, Message2, Message1, Message3>
{
public:

  void Handle(const Message1& msg)
  {
    std::cout << "Processor1 : Message1\n";
  }

  void Handle(const Message2& msg)
  {
    std::cout << "Processor1 : Message2\n";
  }

  void Handle(const Message3& msg)
  {
    std::cout << "Processor1 : Message3\n";
  }

  void Handle(const Message4& msg)
  {
    std::cout << "Processor1 : Message4\n";
  }

  void Unhandled(const IMessage& msg)
  {
    std::cout << "Processor1 : Unhandled IMessage\n";
  }
};

Processor2 will handle Message1 and Message3.

class Processor2 : public MessageProcessor<Message3, Message1>
{
public:

  void Handle(const Message1& msg)
  {
    std::cout << "Processor2 : Message1\n";
  }

  void Handle(const Message3& msg)
  {
    std::cout << "Processor2 : Message3\n";
  }

  void Unhandled(const IMessage& msg)
  {
    std::cout << "Processor2 : Unhandled IMessage\n";
  }
};

Although it may look as though we have considerably increased the amount of code we have to write there are a number important things to note.
The first is that each concrete message processor’s vtable will only be as large as it needs to be. It is not dependent on the total number of messages in the system; only on the number of messages that it must handle.
The second is that the introduction of a new message will not require any of the processor interfaces to be modified.
Another is that the templates do not have to be rewritten every time a message processor framework is required. The base classes and templates may be part of a shared source code library.
One other advantage is that the messages do not have to be able to access any members of the processor interface meaning that the handlers may now be ‘protected’.

The framework is used in exactly the same way as before.

int main()
{
  Processor1 p1;
  Processor2 p2;

  Message1 m1;
  Message2 m2;
  Message3 m3;
  Message4 m4;

  p1.Receive(m1); // "Processor1 : Message1"
  p1.Receive(m2); // "Processor1 : Message2"
  p1.Receive(m3); // "Processor1 : Message3"
  p1.Receive(m4); // "Processor1 : Message4"

  p2.Receive(m1); // "Processor2 : Message1"
  p2.Receive(m2); // "Processor2 : Unhandled IMessage"
  p2.Receive(m3); // "Processor2 : Message3"
  p2.Receive(m4); // "Processor2 : Unhandled IMessage"

  return 0;
}

The output of the example is also the same as before.

Processor1 : Message1
Processor1 : Message2
Processor1 : Message3
Processor1 : Message4
Processor2 : Message1
Processor2 : Unhandled IMessage
Processor2 : Message3
Processor2 : Unhandled IMessage

In the next post I will show how to improve efficiency a little more by eliminating most of the virtual functions.

Download the example code

Designing an efficient and low resource messaging framework. Part 1

I am going to show you three ways in which a messaging framework might be implemented; the first is the ‘proper’ idiomatic C++ way; in the second and third parts, a more efficient blending of C & C++ styles (but may make C++ purists choke on their breakfast).

The specification

  1. There are a set of N messages that can be passed around the application.
  2. The messages are all derived from a base message class.
  3. Objects in the application must be able to receive and process messages.
  4. Objects receiving messages are derived from a base message processor class.
  5. Message processors receive messages as references to the base message class.
  6. They will not all processes the same number or combination of messages.

Let’s start off with the pure object orientated C++ version.

It is usually deemed a ‘code smell’ in C++ programming if code has to interrogate a base object to determine its concrete derived type. As messages are passed to message processors as references to the base message type, some way must be created to steer the message to the correct handler. One way of doing this is to use ‘double dispatch’ or the Visitor Pattern.

Is you are not familiar with this pattern, then hopefully this metaphor will give you the basic idea.

Imagine a salesman visits a company. He meets management, sales, marketing and engineering. He gives out business cards to each person he meets. There is a different telephone help line for each type of recipient, one for management, one for sales etc. Now, he could have a different card for each type of recipient, which would require him to know the job title of each person he meets. He would have to ask them what they did and choose the correct card for each one.

Alternatively, he could have one card with all of the telephone numbers on it and tell each recipient to “call the help line appropriate to your job title”.

This is effectively what the visitor pattern achieves. It says to the message “Here is an interface of overloaded functions that can accept all of the messages. Call the one that matches your concrete type”.

An interface is created that defines a virtual handler function for every message. The handlers in the interface may have default bodies, maybe logging an unhandled message. The concrete message processor inherits from this and implements each of the message handlers it is interested in. When a reference to a base message object is received it will pass itself to the message and the message will call the correct handler in the message processor.
Neat!

Let’s show a little bit of code as an example.

The code below defines a visitor interface that defines virtual handlers for four message types. The virtual handlers have default bodies that send control to an ‘Unhandled’ member (pure virtual). Two message processors are defined, one handling all of the messages, the other just Message1 and Message3.

class IMessageProcessor;

struct IMessage
{
  virtual void Accept(IMessageProcessor& processor) const = 0;
};

struct Message1 : public IMessage
{
  void Accept(IMessageProcessor& processor) const;
};

struct Message2 : public IMessage
{
  void Accept(IMessageProcessor& processor) const;
};

struct Message3 : public IMessage
{
  void Accept(IMessageProcessor& processor) const;
};

struct Message4 : public IMessage
{
  void Accept(IMessageProcessor& processor) const;
};
class IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    msg.Accept(*this);
  }

  virtual void Handle(const Message1& msg) { Unhandled(msg); }
  virtual void Handle(const Message2& msg) { Unhandled(msg); }
  virtual void Handle(const Message3& msg) { Unhandled(msg); }
  virtual void Handle(const Message4& msg) { Unhandled(msg); }

  virtual void Unhandled(const IMessage& msg) = 0;
};
void Message1::Accept(IMessageProcessor& processor) const
{
  processor.Handle(*this);
}

void Message2::Accept(IMessageProcessor& processor) const
{
  processor.Handle(*this);
}

void Message3::Accept(IMessageProcessor& processor) const
{
  processor.Handle(*this);
}

void Message4::Accept(IMessageProcessor& processor) const
{
  processor.Handle(*this);
}
class Processor1 : public IMessageProcessor
{
public:

  void Handle(const Message1& msg)
  {
    std::cout << "Processor1 : Message1\n";
  }

  void Handle(const Message2& msg)
  {
    std::cout << "Processor1 : Message2\n";
  }

  void Handle(const Message3& msg)
  {
    std::cout << "Processor1 : Message3\n";
  }

  void Handle(const Message4& msg)
  {
    std::cout << "Processor1 : Message4\n";
  }

  void Unhandled(const IMessage& msg)
  {
    std::cout << "Processor1 : Unhandled IMessage\n";
  }
};
class Processor2 : public IMessageProcessor
{
public:

  void Handle(const Message1& msg)
  {
    std::cout << "Processor2 : Message1\n";
  }

  void Handle(const Message3& msg)
  {
    std::cout << "Processor2 : Message3\n";
  }

  void Unhandled(const IMessage& msg)
  {
    std::cout << "Processor2 : Unhandled IMessage\n";
  }
};

Lets exercise this code.

int main()
{
  Processor1 p1;
  Processor2 p2;

  Message1 m1;
  Message2 m2;
  Message3 m3;
  Message4 m4;

  p1.Receive(m1); // "Processor1 : Message1"
  p1.Receive(m2); // "Processor1 : Message2"
  p1.Receive(m3); // "Processor1 : Message3"
  p1.Receive(m4); // "Processor1 : Message4"

  p2.Receive(m1); // "Processor2 : Message1"
  p2.Receive(m2); // "Processor2 : Unhandled IMessage"
  p2.Receive(m3); // "Processor2 : Message3"
  p2.Receive(m4); // "Processor2 : Unhandled IMessage"

  return 0;
}

The output of this test will be…

Processor1 : Message1
Processor1 : Message2
Processor1 : Message3
Processor1 : Message4
Processor2 : Message1
Processor2 : Unhandled IMessage
Processor2 : Message3
Processor2 : Unhandled IMessage

This is a neat solution and does not require any message processor to interrogate the received message to determine its type.

There an issue with this scheme that may impact the implementation on a resource limited embedded platform. The visitor interface IMessageProcessor must contain a virtual handler function for every message that exists. The vtable for this may become prohibitively large when there are a substantial number of message types. Each derived message processor will have its own copy of the vtable. This will be true even if the derived message processor only handles one message! This may invoke an unacceptable resource overhead.

Also there is the coupling between the visitor interface and the message types. It would be nice if we could make things a little more decoupled.

In part 2 I will describe the first alternative that uses templates and template specialisation to address some of these issues.

Download the example code