Std :: function / bind as type erasure without C ++ standard library

Question

I am developing an event driven application in C ++ 11 based on a publish / sign template. Classes have one or more onWhateverEvent() methods called by the event loop (inverse of the control). Since the application is actually firmware, where the code size is critical and flexibility is not a high priority, the subscribe part is a simple table with an event identifier and associated handlers.

Here's a very simplified idea code:

 #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 works fine with the compiler on the desktop, and std:function<void(int)>> fn = std::bind(&SomeClass::onSomething), &someInstance, std::placeholders::_1) elegantly erases the styles, therefore, the event distribution table may contain handlers of different classes, therefore different types.

The problem is with the built-in compiler (AVR-GCC 4.8.3), which supports C ++ 11, but there is no standard C ++ library: no <functional> . I was thinking how I can recreate the behavior described above only with compiler functions. I appreciated several options, but there are objections for each (by the compiler or me):

• Create an interface using the virtual void Handler::onEvent(int event) method and derive Button and Menu from it. The distribution table can contain interface pointers, and the rest are calls to virtual methods. This is the simplest approach, but I don’t like the idea of ​​limiting the number of event handler methods to one class (with local if-else distribution) and having the overhead of invoking a virtual method on an event.

• My second idea still contains a call to the virtual method, but has no restrictions on the Button and Menu class. This is a virtual method based on the erase type 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 contain instance and method pointers, and a distribution table can be constructed from FunctBase pointers. This table is as flexible as the / bind function: it can contain any class (type) and any number of handlers in the class. My only problem is that it still contains 1 virtual method call for each event, it just went to the functor.

• My third idea is a simple pointer to a method for converting hack 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 really forces the compiler to issue a big thick warning. It is based on the assumption that C ++ methods have an implicit 1st argument pointing to this . Nevertheless, it works, it is lightweight (without virtual calls), and it is flexible.

So my question is: is it possible to do something like option 3 in pure form in C ++? I know that there is a void * -based erase method (against invoking the virtual method in option 2), but I don't know how to implement it. Looking at the desktop version with std :: bind also gives the impression that it binds the first implicit argument as an instance pointer, but maybe it's just the syntax.

Answer 1

A complex, efficient replacement for std::function<R(Args...)> not difficult to write.

Since we are rooted, we want to avoid memory allocation. Therefore, I will write small_task< Signature, size_t sz, size_t algn > . It creates an sz sized buffer and algn alignment in which it stores its erased objects.

It also stores the engine, destroyer, and pointer to the invoker function. These pointers can be locally within small_task (maximum locality) or in the struct vtable { /*...*/ } const* table manual.

 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*) >; 

living example .

Another thing that is missing is the high quality void(Args...) , which doesn't care if the return value is pass-in callable.

The above task supports moving but not copying. Adding a copy means that everything saved must be copied and requires a different function in the vtable (with an implementation similar to move , except for src is const and no std::move ).

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

bind best replaced with lambdas, honestly. I do not use it even on non-embedded systems.

Another improvement is to teach him how to handle small_task , which are less / less aligned, keeping their vtable pointer and not copying it to the data buffer, and wrapping it in another vtable . This will facilitate the use of small_tasks , which are hardly large enough for your problem.

---

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

Such differences can be subtle and can occur when changing unrelated code or changing the version of the compiler or something else. Therefore, I would avoid this if you have few other choices.

---

As already noted, the platform lacks libraries. Each use of std above is tiny, so I just write:

 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

 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{}; 

living example , about a dozen lines on the std library template that I need.

I would put this “reimplementation of the std library” in the namespace notstd to make it clear what was going on.

If you can, use a linker that combines identical functions together, such as a gold linker. template metaprogramming can cause binary bloat without a solid linker to strip it.

Answer 2

Your first idea is your typical object-oriented solution to a problem. This is fine, but a little heavy - not quite as useful as std::function . Your 3rd idea is undefined behavior. No no.

Your second idea is that now we can work with something! This is close to how std::function actually implemented. We can write a class that can accept any object called 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); } }; 

However, you basically have std::function<void(int)> in a useful, general way.

Now the idea of 4th may be to simply expand your third idea to something useful. Actually use function pointers:

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

And then use lambdas to create things like this:

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

But then you need to hold onto the contexts somehow, which adds extra work.

Answer 3

Before I try to write all the STL materials manually, I try to use the STL, which I already have from the compiler itself. Since most of the STL code you use is just a header, I just turn it on and do some minor hacks to compile them. In fact, id took 10 minutes to prepare it for the link!

I used avr-gcc-5.2.0 version without any problem for the task. I do not have an old installation, and I find it easier to install the actual version in a few minutes instead of fixing problems with the old one.

After compiling your example code for avr, I got link errors:

 build-check-std-a520-nomemdbg-os-dynamic-noncov/main.o: In function `std::__throw_bad_function_call()': /home/krud/own_components/avr_stl/avr_stl009/testing/main.cpp:42: undefined reference to `operator delete(void*, unsigned int)' /home/krud/own_components/avr_stl/avr_stl009/testing/main.cpp:42: undefined reference to `operator delete(void*, unsigned int)' collect2: error: ld returned 1 exit status 

Just write your own __throw_bad_function_call and get rid of the link problem.

It makes no sense for me to write my own implementation of STL. Here I just used the headers that come from the compiler installation (gcc 5.2.0).