std::function/bind like type-erasure without Standard C++ library

Question

I'm developing a simple event driven application in C++11 based on the publish/subscribe pattern. Classes have one or more onWhateverEvent() method invoked by the event loop (inversion of control). Since the application is in fact a firmware, where code size is critical and flexibility is not of high priority, the 'subscribe' part is a simple table with event id's and associated handlers.

Here's a very simplified code of the idea:

#include <functional>

enum Events {
    EV_TIMER_TICK,
    EV_BUTTON_PRESSED
};

struct Button {
    void onTick(int event) { /* publish EV_BUTTON_PRESSED */ }
};

struct Menu {
    void onButtonPressed(int event) { /* publish EV_SOMETHING_ELSE */ }
};

Button button1;
Button button2;
Menu mainMenu;

std::pair<int, std::function<void(int)>> dispatchTable[] = {
    {EV_TIMER_TICK, std::bind(&Button::onTick, &button1, std::placeholders::_1) },
    {EV_TIMER_TICK, std::bind(&Button::onTick, &button2, std::placeholders::_1) },
    {EV_BUTTON_PRESSED, std::bind(&Menu::onButtonPressed, &mainMenu, std::placeholders::_1) }
};

int main(void) 
{
    while(1) {
        int event = EV_TIMER_TICK; // msgQueue.getEventBlocking();
        for (auto& a : dispatchTable) {
            if (event == a.first) 
                a.second(event);
        }
    }
}

This compiles and runs fine with a desktop compiler, and std:function<void(int)>> fn = std::bind(&SomeClass::onSomething), &someInstance, std::placeholders::_1) elegantly implements type erasure so the event dispatch table can hold handlers of different classes, thus different types.

The problem comes with the embedded compiler (AVR-GCC 4.8.3) which supports C++11, but there's no Standard C++ Library: no <functional> header. I was thinking how can I re-create the above behavior with compiler features only. I evaluated a few options, but there are objections for each (by the compiler or me):

1. Create an interface with a virtual void Handler::onEvent(int event) method, and derive Button and Menu from it. The dispatch table can hold interface pointers, and virtual method calls do the rest. This is the most simple approach but I don't like the idea of limiting the number of event handler methods to one per class (with doing local if-else event dispatch), and having the overhead of a virtual method call per event.

2. My second idea still contains a virtual method call, but has no restrictions on the Button and Menu class. It's a virtual method call based type-erasure with functors:

   struct FunctBase {
       virtual void operator()(int event) = 0;
   };
   
   template<typename T>
   struct Funct : public FunctBase
   {
       T* pobj;                 //instance ptr
       void (T::*pmfn)(int);    //mem fun ptr
       Funct(T* pobj_, void (T::*pmfn_)(int)) : pobj(pobj_), pmfn(pmfn_) {}
   
       void operator()(int ev) override {
           (pobj->*pmfn)(ev);
       }
   };
   

   Funct can hold instance and method pointers, and the dispatch table can be constructed of FunctBase pointers. This way table is as flexible as with function/bind: can hold any class (type) and any number of handlers per class. My only problem that it still contains 1 virtual method call per event, it's just moved to the functor.

3. My third idea is a simple hack converting method pointers to function pointers:

   typedef void (*Pfn)(void*, int);
   Pfn pfn1 = reinterpret_cast<Pfn>(&Button::onTick);
   Pfn pfn2 = reinterpret_cast<Pfn>(&Menu::onButtonPressed);
   

   As far as I know this is Undefined Behavior and indeed makes the compiler emit a big fat warning. It's based on the assumption that c++ methods have an implicit 1st argument pointing to this. Nonetheless it works, it's lightweight (no virtual calls), and it's flexible.

So my question: Is it possible to do something like option 3 in clean C++ way? I know there's a void* based type-erasure technique (opposed to virtual method call in option 2), but I don't know how to implement it. Looking at desktop version with std::bind also gives me the impression that it binds the first implicit argument to be the instance pointer, but maybe that's just the syntax.

Answer 1

A solid, efficient, std::function<R(Args...)> replacement isn't hard to write.

As we are embedded, we want to avoid allocating memory. So I'd write a small_task< Signature, size_t sz, size_t algn >. It creates a buffer of size sz and alignment algn in which it stores its erased objects.

It also stores a mover, a destroyer, and an invoker function pointer. These pointers can either be locally within the small_task (maximal locality), or within a manual struct vtable { /*...*/ } const* table.

template<class Sig, size_t sz, size_t algn>
struct small_task;

template<class R, class...Args, size_t sz, size_t algn>
struct small_task<R(Args...), sz, algn>{
  struct vtable_t {
    void(*mover)(void* src, void* dest);
    void(*destroyer)(void*);
    R(*invoke)(void const* t, Args&&...args);
    template<class T>
    static vtable_t const* get() {
      static const vtable_t table = {
        [](void* src, void*dest) {
          new(dest) T(std::move(*static_cast<T*>(src)));
        },
        [](void* t){ static_cast<T*>(t)->~T(); },
        [](void const* t, Args&&...args)->R {
          return (*static_cast<T const*>(t))(std::forward<Args>(args)...);
        }
      };
      return &table;
    }
  };
  vtable_t const* table = nullptr;
  std::aligned_storage_t<sz, algn> data;
  template<class F,
    class dF=std::decay_t<F>,
    // don't use this ctor on own type:
    std::enable_if_t<!std::is_same<dF, small_task>{}>* = nullptr,
    // use this ctor only if the call is legal:
    std::enable_if_t<std::is_convertible<
      std::result_of_t<dF const&(Args...)>, R
    >{}>* = nullptr
  >
  small_task( F&& f ):
    table( vtable_t::template get<dF>() )
  {
    // a higher quality small_task would handle null function pointers
    // and other "nullable" callables, and construct as a null small_task

    static_assert( sizeof(dF) <= sz, "object too large" );
    static_assert( alignof(dF) <= algn, "object too aligned" );
    new(&data) dF(std::forward<F>(f));
  }
  // I find this overload to be useful, as it forces some
  // functions to resolve their overloads nicely:
  // small_task( R(*)(Args...) )
  ~small_task() {
    if (table)
      table->destroyer(&data);
  }
  small_task(small_task&& o):
    table(o.table)
  {
    if (table)
      table->mover(&o.data, &data);
  }
  small_task(){}
  small_task& operator=(small_task&& o){
    // this is a bit rude and not very exception safe
    // you can do better:
    this->~small_task();
    new(this) small_task( std::move(o) );
    return *this;
  }
  explicit operator bool()const{return table;}
  R operator()(Args...args)const{
    return table->invoke(&data, std::forward<Args>(args)...);
  }
};

template<class Sig>
using task = small_task<Sig, sizeof(void*)*4, alignof(void*) >;

live example.

Another thing missing is a high quality void(Args...) that doesn't care if the passed-in callable has a return value.

The above task supports move, but not copy. Adding copy means that everything stored must be copyable, and requires another function in the vtable (with an implementation similar to move, except src is const and no std::move).

A small amount of C++14 was used, namely the enable_if_t and decay_t aliases and similar. They can be easily written in C++11, or replaced with typename std::enable_if<?>::type.

bind is best replaced with lambdas, honestly. I don't use it even on non-embedded systems.

Another improvement would be to teach it how to deal with small_tasks that are smaller/less aligned by storing their vtable pointer rather than copying it into the data buffer, and wrapping it in another vtable. That would encourage using small_tasks that are just barely large enough for your problem set.

---

Converting member functions to function pointers is not only undefined behavior, often the calling convention of a function is different than a member function. In particular, this is passed in a particular register under some calling conventions.

Such differences can be subtle, and can crop up when you change unrelated code, or the compiler version changes, or whatever else. So I'd avoid that unless you have little other choice.

---

As noted, the platform lacks libraries. Every use of std above is tiny, so I'll just write them:

template<class T>struct tag{using type=T;};
template<class Tag>using type_t=typename Tag::type;
using size_t=decltype(sizeof(int));

move

template<class T>
T&& move(T&t){return static_cast<T&&>(t);}

forward

template<class T>
struct remove_reference:tag<T>{};
template<class T>
struct remove_reference<T&>:tag<T>{};
template<class T>using remove_reference_t=type_t<remove_reference<T>>;

template<class T>
T&& forward( remove_reference_t<T>& t ) {
  return static_cast<T&&>(t);
}
template<class T>
T&& forward( remove_reference_t<T>&& t ) {
  return static_cast<T&&>(t);
}

decay

template<class T>
struct remove_const:tag<T>{};
template<class T>
struct remove_const<T const>:tag<T>{};

template<class T>
struct remove_volatile:tag<T>{};
template<class T>
struct remove_volatile<T volatile>:tag<T>{};

template<class T>
struct remove_cv:remove_const<type_t<remove_volatile<T>>>{};


template<class T>
struct decay3:remove_cv<T>{};
template<class R, class...Args>
struct decay3<R(Args...)>:tag<R(*)(Args...)>{};
template<class T>
struct decay2:decay3<T>{};
template<class T, size_t N>
struct decay2<T[N]>:tag<T*>{};

template<class T>
struct decay:decay2<remove_reference_t<T>>{};

template<class T>
using decay_t=type_t<decay<T>>;

is_convertible

template<class T>
T declval(); // no implementation

template<class T, T t>
struct integral_constant{
  static constexpr T value=t;
  constexpr integral_constant() {};
  constexpr operator T()const{ return value; }
  constexpr T operator()()const{ return value; }
};
template<bool b>
using bool_t=integral_constant<bool, b>;
using true_type=bool_t<true>;
using false_type=bool_t<false>;

template<class...>struct voider:tag<void>{};
template<class...Ts>using void_t=type_t<voider<Ts...>>;

namespace details {
  template<template<class...>class Z, class, class...Ts>
  struct can_apply:false_type{};
  template<template<class...>class Z, class...Ts>
  struct can_apply<Z, void_t<Z<Ts...>>, Ts...>:true_type{};
}
template<template<class...>class Z, class...Ts>
using can_apply = details::can_apply<Z, void, Ts...>;

namespace details {
  template<class From, class To>
  using try_convert = decltype( To{declval<From>()} );
}
template<class From, class To>
struct is_convertible : can_apply< details::try_convert, From, To > {};
template<>
struct is_convertible<void,void>:true_type{};

enable_if

template<bool, class=void>
struct enable_if {};
template<class T>
struct enable_if<true, T>:tag<T>{};
template<bool b, class T=void>
using enable_if_t=type_t<enable_if<b,T>>;

result_of

namespace details {
  template<class F, class...Args>
  using invoke_t = decltype( declval<F>()(declval<Args>()...) );

  template<class Sig,class=void>
  struct result_of {};
  template<class F, class...Args>
  struct result_of<F(Args...), void_t< invoke_t<F, Args...> > >:
    tag< invoke_t<F, Args...> >
  {};
}
template<class Sig>
using result_of = details::result_of<Sig>;
template<class Sig>
using result_of_t=type_t<result_of<Sig>>;

aligned_storage

template<size_t size, size_t align>
struct alignas(align) aligned_storage_t {
  char buff[size];
};

is_same

template<class A, class B>
struct is_same:false_type{};
template<class A>
struct is_same<A,A>:true_type{};

live example, about a dozen lines per std library template I needed.

I would put this "std library reimplementation" into namespace notstd to make it clear what is going on.

If you can, use a linker that folds identical functions together, like the gold linker. template metaprogramming can cause binary bloat without a solid linker to strip it.

Answer 2

Your 1st idea is your typical object oriented solution to the problem. It's perfectly fine, but a bit heavy-handed - not quite as usable as std::function. Your 3rd idea is undefined behavior. Nope nope nope.

Your 2nd idea - now there's something we can work with! This is close to how std::function is actually implemented. We can write a class that can take any object that is callable with int and returns void:

class IntFunc {
private:
    struct placeholder {
        virtual ~placeholder() = default;
        virtual void call(int ) = 0;
    };

    template <typename F>
    struct holder : placeholder {
        holder(F f) : func(f) { }
        void call(int i) override { func(i); }
        F func;
    };


    // if you wrote your own unique_ptr, use it here
    // otherwise, will have to add rule of 5 stuff
    placeholder* p;
public:
    template <typename F>
    IntFunc(F f)
    : placeholder(new holder<F>(f))
    { }

    template <typename Cls>
    IntFunc(Cls* instance, void (Cls::*method)(int )) {
        auto lambda = [=](int i){ (instance->*method)(i); };
        placeholder = new holder<decltype(lambda)>(lambda);
    }

    void operator()(int i) {
        p->call(i);
    }
};

With that, you basically have std::function<void(int)> in a usable, generic way.

Now a 4th idea might be to just extend your 3rd idea to something usable. Actually use function pointers:

using Pfn = void (*)(void*, int);

And then use lambdas to make such things:

Pfn buttonOnTick = [](void* ctxt, int i){
    static_cast<Button*>(ctxt)->onTick(i);
};

But then you have to hold on to the contexts somehow - which adds extra work.