11.6 The Logarithmic Double Dispatcher

If you want to avoid the heavy dependencies accompanying the brute-force solution, you must look into a more dynamic approach. Instead of generating code at compile time, you must keep a runtime structure and use runtime algorithms that help in dynamically dispatching function calls depending on types.

RTTI (runtime type information) can be of further help here because it provides not only dynamic_cast and type identification, but also a runtime ordering of types, through the before member function of std::type_info. What before offers is an ordering relationship on all types in a program. We can use this ordering relationship for fast searches of types.

The implementation here is similar to the one found in Item 31 of Scott Meyers's More Effective C++ (1996a), with some improvements: The casting step when invoking a handler is automated, and the implementation herein aims at being generic.

We will avail ourselves of the OrderedTypeInfo class, described in Chapter 2. OrderedTypeInfo is a wrapper providing exactly the same functionality as std::type_info. In addition, OrderedTypeInfo provides value semantics and a caveat-free less-than operator. You can thus store OrderedTypeInfo objects in standard containers, which is of interest to this chapter.

Meyers's approach was simple: For each pair of std::type_info objects you want to dispatch upon, you register a pointer to a function with the double dispatcher. The double dispatcher stores the information in a std::map. At runtime, when invoked with two unknown objects, the double dispatcher performs a fast search (logarithmic time) for type discovery, and if it finds an entry, fires the appropriate pointer to a function.

Let's define the structure of a generic engine operating on these principles. We must templatize the engine with the base types of the two arguments (left-hand side and right-hand side). We call this engine BasicDispatcher, because we will use it as the base device for several more advanced double dispatchers.

template <class BaseLhs, class BaseRhs = BaseLhs,


   typename ResultType = void>


class BasicDispatcher


{


   typedef std::pair<OrderedTypeInfo, OrderedTypeInfo>


      KeyType;


   typedef ResultType (*CallbackType)(BaseLhs&, BaseRhs&);


   typedef CallbackType MappedType;


   typedef std::map<KeyType, MappedType> MapType;


   MapType callbackMap_;


public:


   ...


};

The key type in the map is a std::pair of two OrderedTypeInfo objects. The std::pair class supports ordering, so we don't have to provide a custom ordering functor.

BasicDispatcher can be more general if we templatize the callback type. In general, the callback does not have to be a function. It can be, for example, a functor (refer to the introduction of Chapter 5 for a discussion of functors). BasicDispatcher can accommodate functors by transforming its inner CallbackType type definition into a template parameter.

An important improvement is to change the std::map type to a more efficient structure. Matt Austern (2000) explains that the standard associative containers have a slightly narrower area of applicability than one might think. In particular, a sorted vector in combination with binary search algorithms (such as std::lower_bound) might perform much better, in both space and time, than an associative container. This happens when the number of accesses is much larger than the number of insertions. So we should take a close look at the typical usage pattern of a double-dispatcher object.

Most often, a double dispatcher is a write-once, read-many type of structure. Typically, a program sets the callbacks once and then uses the dispatcher many, many times. This is in keeping with the virtual functions mechanism, which double dispatchers extend. You decide, at compile time, which functions are virtual and which are not.

It seems as if we're better off with a sorted vector. The disadvantages of a sorted vector are linear-time insertions and linear-time deletions, and a double dispatcher is not typically concerned about the speed of either. In exchange, a vector offers about twice the lookup speed and a much smaller working set, so it is definitely a better choice for a double dispatcher.

Loki saves the trouble of maintaining a sorted vector by hand by defining an AssocVector class template. AssocVector is a drop-in replacement for std::map (it supports the same set of member functions), implemented on top of std::vector. AssocVector differs from a map in the behavior of its erase functions (AssocVector::erase invalidates all iterators into the object) and in the complexity guarantees of insert and erase (linear as opposed to constant). Because of the high degree of compatibility of AssocVector with std::map, we'll continue to use the term map to describe the data structure held by the double dispatcher.

Here is the revised definition of BasicDispatcher:

template


<


   class BaseLhs,


   class BaseRhs = BaseLhs,


   typename ResultType = void,


   typename CallbackType = ResultType (*)(BaseLhs&, BaseRhs&)


>


class BasicDispatcher


{


   typedef std::pair<TypeInfo, TypeInfo>


      KeyType;


   typedef CallbackType MappedType;


   typedef AssocVector<KeyType, MappedType> MapType;


   MapType callbackMap_;


public:


   ...


};

The registration function is easy to define. This is all we need:

template <...>


class BasicDispatcher


{


   ... as above ...


   template <class SomeLhs, SomeRhs>


   void Add(CallbackType fun)


   {


      const KeyType key(typeid(SomeLhs), typeid(SomeRhs));


      callbackMap_[key] = fun;


   }


};

The types SomeLhs and SomeRhs are the concrete types for which you need to dispatch the call. Just like std::map, AssocVector overloads operator[] to find a key's corresponding mapped type. If the entry is missing, a new element is inserted. Then operator[] returns a reference to that new or found element, and Add assigns fun to it.

The following is an example of using Add:

typedef BasicDispatcher<Shape> Dispatcher;


// Hatches the intersection between a rectangle and a polygon


void HatchRectanglePoly(Shape& lhs, Shape& rhs)


{


   Rectangle& rc = dynamic_cast<Rectangle&>(lhs);


   Poly& pl = dynamic_cast<Poly&>(rhs);


   ... use rc and pl ...


}


...


Dispatcher disp;


disp.Add<Rectangle, Poly>(HatchRectanglePoly);

The member function that does the search and invocation is simple:

template <...>


class BasicDispatcher


{


   ... as above ...


   ResultType Go(BaseLhs& lhs, BaseRhs& rhs)


   {


      MapType::iterator i = callbackMap_.find(


         KeyType(typeid(lhs), typeid(rhs));


      if (i == callbackMap_.end())


      {


         throw std::runtime_error("Function not found");


      }


      return (i->second)(lhs, rhs);


   }


};

11.6.1 The Logarithmic Dispatcher and Inheritance

BasicDispatcher does not work correctly with inheritance. If you register only HatchRectanglePoly(Shape& lhs, Shape& rhs) with BasicDispatcher, you get proper dispatching only for objects of type Rectangle and Poly—nothing else. If, for instance, you pass references to a RoundedRectangle and a Poly to BasicDispatcher::Go, BasicDispatcher will reject the call.

The behavior of BasicDispatcher is not in keeping with inheritance rules, according to which derived types must by default act like their base types. It would be nice if BasicDispatcher accepted calls with objects of derived classes, as long as these calls were unambiguous per C++'s overloading rules.

There are quite a few things you can do to correct this problem, but to date there is no complete solution. You must be careful to register all the pairs of types with Basic Dispatcher.^[4]

^[4] I am convinced there is a solution to the inheritance problem. But, alas, writers of books have deadlines, too.

11.6.2 The Logarithmic Dispatcher and Casts

BasicDispatcher is usable, but not quite satisfactory. Although you register a function that handles the intersection between a Rectangle and a Poly, that function must accept arguments of the base type, Shape&. It is awkward and error-prone to ask client code (HatchRectanglePoly's implementation) to cast the Shape references back to the correct types.

On the other hand, the callback map cannot hold a different function or functor type for each element, so we must stick to a uniform representation. Item 31 in More Effective C++ (Meyers 1996a) discusses this issue, too. No function-pointer-to-function-pointer cast helps because after you exit FnDoubleDispatcher::Add, you've lost the static type information, so you don't know what to cast to. (If this sounds confusing, try spinning some code and you'll immediately figure it out.)

We will implement a solution to the casting problem in the context of simple callback functions (not functors). That is, the CallbackType template argument is a pointer to a function.

An idea that could help is using a trampoline function, also known as a thunk. Trampoline functions are small functions that perform little adjustments before calling other functions. They are commonly used by C++ compiler writers to implement features such as covariant return types and pointer adjustments for multiple inheritance.

We can use a trampoline function that performs the appropriate cast and then calls a function of the proper signature, thus making life much easier for the client. The problem, however, is that callbackMap_ must now store two pointers to functions: one to the pointer provided by the client, and one to the pointer to the trampoline function. This is worrisome in terms of speed. Instead of an indirect call through a pointer, we have two. In addition, the implementation becomes more complicated.

An interesting bit of wizardry saves the day. A template can accept a pointer to a function as a nontype template parameter. (Most often in this book, nontype template parameters are integral values.) A template is allowed to accept pointers to global objects, including functions, as nontype template parameters. The only condition is that the function whose address is used as a template argument must have external linkage. You can easily transform static functions in functions with external linkage by removing static and putting them into unnamed namespaces. For example, what you would write as

static void Fun();

in pre-namespace C++, you can write using an anonymous namespace as

namespace


{


   void Fun();


}

Using a pointer to a function as a nontype template argument means that we no longer need to store it in the map. This essential aspect needs thorough understanding. The reason we don't need to store the pointer to a function is that the compiler has static knowledge about it. Thus, the compiler can hardcode the function address in the trampo line code.

We implement this idea in a new class that uses BasicDispatcher as its back end. The new class, FnDispatcher, is tuned for dispatching to functions only—not to functors. FnDispatcher aggregates BasicDispatcher privately and provides appropriate forwarding functions.

The FnDispatcher::Add template function accepts three template parameters. Two represent the left-hand-side and the right-hand-side types for which the dispatch is registered (ConcreteLhs and ConcreteRhs). The third template parameter (callback) is the pointer to a function. The added FnDispatcher::Add overloads the template Add with only two template parameters, defined earlier.

template <class BaseLhs, class BaseRhs = BaseLhs,


   ResultType = void>


class FnDispatcher


{


   BaseDispatcher<BaseLhs, BaseRhs, ResultType> backEnd_;


   ...


public:


   template <class ConcreteLhs, class ConcreteRhs,


      ResultType (*callback)(ConcreteLhs&, ConcreteRhs&)>


   void Add()


   {


      struct Local // see Chapter 2


      {


         static ResultType Trampoline(BaseLhs& lhs, BaseRhs& rhs)


         {


            return callback(


               dynamic_cast<ConcreteLhs&>(lhs),


               dynamic_cast<ConcreteRhs&>(rhs));


         }


        };


        return backEnd_.Add<ConcreteLhs, ConcreteRhs>(


           &Local::Trampoline);


   }


};

Using a local structure, we define the trampoline right inside Add. The trampoline casts the arguments to the right types and then forwards to callback. Then, the Add function uses backEnd_'s Add function (defined by BaseDispatcher) to add the trampoline to callbackMap_.

As far as speed is concerned, the trampoline does not incur additional overhead. Although it looks like an indirect call, the call to callback is not. As explained before, the compiler hardwires callback's address right into Trampoline so there is no second indirection. A clever compiler can even inline the call to callback if possible.

Using the newly defined Add function is simple:

typedef FnDispatcher<Shape> Dispatcher;





// Possibly in an unnamed namespace


void HatchRectanglePoly(Rectangle& lhs, Poly& rhs)


{


   ...


}





Dispatcher disp;


disp.Add<Rectangle, Poly, Hatch>();

Because of its Add member function, FnDispatcher is easy to use. FnDispatcher also exposes an Add function similar to the one defined by BaseDispatcher, so you still can use this function if you need to.^[5]

^[5] One case in which you cannot use FnDispatcher::Add is when you need to register dynamically loaded functions. Even in this case, however, you can make slight changes to your design so that you can take advantage of trampolines.