Home » Embedded Template Library

Category Archives: Embedded Template Library

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.

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