Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
PrevUpHomeNext

Annex: Implementation

This section gives an overview of the key programming techniques used to implement this library.

[Note] Note

The code listed here can be used by curious readers and library maintainers as a reference in trying to understand the library source code. There is absolutely no guarantee that the library implementation uses the exact code listed here.

Local Classes as Template Parameters

This library uses a local class to implement the local function object. However, in C++03 local classes (and therefore the local function objects they implement) cannot be passed as template parameters (e.g., to the std::for_each algorithm), this is instead possible in C++11, MSVC, and some other compilers (see [N2657] and Boost.Config's BOOST_NO_LOCAL_CLASS_TEMPLATE_PARAMETERS). To work around this limitation, this library investigated the following two "tricks" (both tricks can be extended to support function default parameters):

  1. The casting functor trick uses a non-local functor that calls a static member function of the local class via a function pointer. The static member function then calls the correct local function body after type casting the object from a void* pointer (local classes can always be used for type casting via static_cast or similar).
  2. The virtual functor trick derives the local functor class from a non-local base class. The correct overridden implementation of the virtual operator() is then called via dynamic binding.

For example (see also impl_tparam_tricks.cpp):

#include <boost/detail/lightweight_test.hpp>
#include <vector>
#include <algorithm>

// Casting functor trick.
struct casting_func {
    explicit casting_func(void* obj, void (*call)(void*, const int&))
            : obj_(obj), call_(call) {}
    // Unfortunately, function pointer call is not inlined.
    inline void operator()(const int& num) { call_(obj_, num); }
private:
    void* obj_;
    void (*call_)(void*, const int&);
};

// Virtual functor trick.
struct virtual_func {
    struct interface {
        // Unfortunately, virtual function call is not inlined.
        inline virtual void operator()(const int&) {}
    };
    explicit virtual_func(interface& func): func_(&func) {}
    inline void operator()(const int& num) { (*func_)(num); }
private:
    interface* func_;
};

int main(void) {
    int sum = 0, factor = 10;

    // Local class for local function.
    struct local_add : virtual_func::interface {
        explicit local_add(int& _sum, const int& _factor)
                : sum_(_sum), factor_(_factor) {}
        inline void operator()(const int& num) {
            body(sum_, factor_, num);
        }
        inline static void call(void* obj, const int& num) {
            local_add* self = static_cast<local_add*>(obj);
            self->body(self->sum_, self->factor_, num);
        }
    private:
        int& sum_;
        const int& factor_;
        inline void body(int& sum, const int& factor, const int& num) {
            sum += factor * num;
        }
    } add_local(sum, factor);
    casting_func add_casting(&add_local, &local_add::call);
    virtual_func add_virtual(add_local);

    std::vector<int> v(10);
    std::fill(v.begin(), v.end(), 1);

    // std::for_each(v.begin(), v.end(), add_local); // Error but OK on C++11.
    std::for_each(v.begin(), v.end(), add_casting); // OK.
    std::for_each(v.begin(), v.end(), add_virtual); // OK.

    BOOST_TEST(sum == 200);
    return boost::report_errors();
}

The casting functor trick measured slightly better run-time performances than the virtual functor trick so the current implementation of this library uses the casting functor trick (probably because in addition to the indirect function call, the virtual functor trick also requires accessing the virtual function table). However, neither one of the two tricks was observed to allow for compiler optimizations that inline the local function calls (because they rely on one indirect function call via either a function pointer or a virtual function respectively). Therefore, on compilers that accept local classes as template parameters (MSVC, C++11, etc, see [N2657] and Boost.Config's BOOST_NO_LOCAL_CLASS_TEMPLATE_PARAMETERS), this library automatically generates code that passes the local class type directly as template parameter without using neither one of these two tricks in order to take full advantage of compiler optimizations that inline the local function calls.

Parsing Macros

This library macros can parse the list of specified parameters and detect if any of the bound variable names matches the token this_ (to generate special code to bind the object in scope), or if the variable is bound by const (to generate special code to bind by constant), etc. The parameter tokens are inspected using preprocessor meta-programming and specifically using the macros defined by the files in the boost/local_function/detail/preprocessor/keyword/ directory. [31]

For example, the following code defines a macro that allows the preprocessor to detect if a set of space-separated tokens ends with this_ or not (see also impl_pp_keyword.cpp):

#include <boost/local_function/detail/preprocessor/keyword/thisunderscore.hpp>
#include <boost/local_function/detail/preprocessor/keyword/const.hpp>
#include <boost/local_function/detail/preprocessor/keyword/bind.hpp>
#include <boost/detail/lightweight_test.hpp>

// Expand to 1 if space-separated tokens end with `this_`, 0 otherwise.
#define IS_THIS_BACK(tokens) \
    BOOST_LOCAL_FUNCTION_DETAIL_PP_KEYWORD_IS_THISUNDERSCORE_BACK( \
    BOOST_LOCAL_FUNCTION_DETAIL_PP_KEYWORD_BIND_REMOVE_FRONT( \
    BOOST_LOCAL_FUNCTION_DETAIL_PP_KEYWORD_CONST_REMOVE_FRONT( \
        tokens \
    )))

int main(void) {
    BOOST_TEST(IS_THIS_BACK(const bind this_) == 1);
    BOOST_TEST(IS_THIS_BACK(const bind& x) == 0);
    return boost::report_errors();
}



[31] This technique is at the core of even more complex preprocessor parsing macros like the ones that parse the Contract++ syntax.


PrevUpHomeNext