Mapping binary structures as tuples using template metaprogramming @ /home/adrian

» Mapping binary structures as tuples using template metaprogramming

» November 3, 2013 | cpp development english | Adrian Kummerländer

My current programming related interests are centered mainly around low level data storage and querying techniques - i.e. implementing my own database. The first step in this direction was a graph storage library based on Google LevelDB. While the resulting prototype libGraphStorage performs fairly well it just doesn’t fulfill all my expectations concerning performance and storage requirements. Additionally the decision of building a graph storage on top of a key value store proofed to be too limiting as my mental image of the kind of system I wanted to develop changed over time. While I now have a clearer plan about what I want to build I am also back to square one of actually implementing anything. As I chose to abandon the concept of building higher level data structures on top of existing key-value store libraries in favor of building everything from the system calls up by myself, I am now faced among other things with implementing nice abstractions around mapping raw binary data into various structures.

For the purpose of this article I am going to limit myself to flat structures with fixed length fields. The result I am aiming for is a template which enables me to write mappings like EdgeId in a more compact and efficient way. This also includes support for handling differences in endianness and In-place modification of the structure fields.

Mapping buffers as tuples

To be able to easily work with structure definitions using template metaprogramming I am relying on the standard library’s std::tuple template.

template<typename Tuple>
class BinaryMapping {
    public:
        BinaryMapping(uint8_t* const buffer):
            buffer_(buffer) {
            TupleReader::read(this->tuple_, buffer);
        }

        template <size_t Index>
        decltype(*std::get<Index>(Tuple{})) get() {
            return *std::get<Index>(this->tuple_);
        }

        template <size_t Index,
                  typename Value = decltype(*std::get<Index>(Tuple{}))>
        void set(const Value value) {
            *std::get<Index>(this->tuple_) = value;
        }

    private:
        uint8_t* const buffer_;
        Tuple tuple_;

};

This implementation of a template class BinaryMapping provides get and set template methods for accessing values in a given binary buffer using the mapping provided by a given Tuple template argument. The most notable element of this class is the usage of the decltype keyword which was introduced in C++11. This keyword makes it easier to declare types dependent on template arguments or other types that are difficult to declare using the standard notations. This is possible because decltype exposes the return type of an expression during the compilation phase. So the expression decltype(*std::get<Index>(Tuple{})) is replaced with the return type of the expression *std::get<Index>(Tuple{}) during template instantiation. As the return type of this expression is dependent on the template arguments Index and Tuple the return type of the template method which is using a decltype expression as its return type is also dependent on the template arguments.

As you may have noticed the above template class is not complete as I have not included a implementation of the TupleReader::read method which does the actual work of mapping the binary buffer as a tuple. This mapping is achieved by the following recursive template methods:

struct TupleReader {
    template <typename Tuple, size_t Index = 0, off_t Offset = 0>
    static inline typename std::enable_if<
        Index == std::tuple_size<Tuple>::value, void
    >::type read(Tuple&, uint8_t*) { }

    template <typename Tuple, size_t Index = 0, off_t Offset = 0>
    static inline typename std::enable_if<
        Index < std::tuple_size<Tuple>::value, void
    >::type read(Tuple& tuple, uint8_t* buffer) {
        std::get<Index>(tuple) = reinterpret_cast<
            typename std::tuple_element<Index, Tuple>::type
        >(buffer+Offset);

        read<Tuple,
             Index  + 1,
             Offset + sizeof(decltype(*std::get<Index>(Tuple{})))>(
            tuple, buffer
        );
    }
};

Template metaprogramming in C++ offers a Turing-complete language which is fully executed during compilation. This means that any problem we may solve during the runtime of a normal program may also be solved during compilation using template metaprogramming techniques. This kind of programming is comparable to functional programming as we have to rely on recursion and pattern matching.
The above coding contains two overloads of the read method. The first is our exit condition which stops the recursion as soon as we have processed every tuple element. The second one matches every element of a given tuple and sets the pointer of each element to the matching position in the binary buffer. To make this work I use the following four standard library templates:

std::enable_if makes it possible to exclude template instantiations from overload resolution based on a condition passed as a template argument. The condition has to be a statically resolvable boolean expression, the second argument of the template is the type to be returned when the condition resolves to a true value. TupleReader uses this template to match the recursive version of the read method to any Index value below the tuple element count and the empty version to the case where the Index argument equals the tuple element count. This equals an escape condition for the recursion started by the second overload of the read method as it increases the Index on each call.

std::get returns a reference to the Nth element of the given tuple as specified by the corresponding template argument. The methods in TupleReader use this template to set the pointer on each element to the appropriate buffer offset.

std::tuple_size returns the number of elements in the std::tuple instantiation passed as the template argument. This value is used as a reference value to compare the current recursion index to.

std::tuple_element returns the type of the Nth element of a given std::tuple instantiation as specified by the template argument. I use this template to get the type to which the current buffer offset has to be cast to match the pointer of the corresponding tuple element.

While the Index argument of the read template method is increased by one, the Offset value is increased by the size of the current tuple element type so the current total buffer offset is always available as a template argument.

The classes TupleReader and BinaryMapping are enough to map a binary structure as a std::tuple instantiation like in the following example where I define a TestRecord tuple containing a pointer to uint64_t and uint16_t integers:

typedef std::tuple<uint64_t*, uint16_t*> TestRecord;

uint8_t* buffer = reinterpret_cast<uint8_t*>(
    std::calloc(10, sizeof(uint8_t))
);

BinaryMapping<TestRecord> mapping(buffer);

mapping.set<0>(42);
mapping.set<1>(1337);

std::cout << mapping.get<0>() << std::endl;
std::cout << mapping.get<1>() << std::endl;

Endianness

As you may remember this does not take endianness into account as I defined as a requirement in the beginning. I first thought about including support for different endianness types into the BinaryMapping template class which worked, but led to problems as soon as I mixed calls to get and set. The resulting problems could of course have been fixed but this would probably have conflicted with In-place modifications of the buffer. Because of that I chose to implement endianness support in a separate set of templates.

struct BigEndianSorter {
    template <class Key>
    static void write(uint8_t*, const Key&);

    template <typename Key>
    static Key read(uint8_t* buffer);
};

To be able to work with different byte orderings I abstracted the basic operations down to read and write template methods contained in a struct so I would be able to provide separate implementations of these methods for each type of endianness. The following template specialization of the write method which does an In-place reordering of a uint64_t should be enough to understand the basic principle:

template <>
void BigEndianSorter::write<uint64_t>(uint8_t* buffer, const uint64_t& number) {
    *reinterpret_cast<uint64_t*>(buffer) = htobe64(number);
}

As soon as I had the basic endianness conversion methods implemented in a manner which could be used to specialize other template classes I was able to build a generic implementation of a serializer which respects the structure defined by a given std::tuple instantiation:

template <class ByteSorter>
struct Serializer {
    template <typename Tuple, size_t Index = 0, off_t Offset = 0>
    static inline typename std::enable_if<
        Index == std::tuple_size<Tuple>::value, void
    >::type serialize(uint8_t*) { }

    template <typename Tuple, size_t Index = 0, off_t Offset = 0>
    static inline typename std::enable_if<
        Index < std::tuple_size<Tuple>::value, void
    >::type serialize(uint8_t* buffer) { 
        ByteSorter::template write<typename std::remove_reference<
            decltype(*std::get<Index>(Tuple{}))
        >::type>(
            buffer+Offset,
            *reinterpret_cast<typename std::tuple_element<Index, Tuple>::type>(
                buffer+Offset
            )
        );

        serialize<Tuple,
                  Index  + 1,
                  Offset + sizeof(decltype(*std::get<Index>(Tuple{})))>(
            buffer
        );
    }

    template <typename Tuple, size_t Index = 0, off_t Offset = 0>
    static inline typename std::enable_if<
        Index == std::tuple_size<Tuple>::value, void
    >::type deserialize(uint8_t*) { }

    template <typename Tuple, size_t Index = 0, off_t Offset = 0>
    static inline typename std::enable_if<
        Index < std::tuple_size<Tuple>::value, void
    >::type deserialize(uint8_t* buffer) { 
        *reinterpret_cast<typename std::tuple_element<Index, Tuple>::type>(
            buffer+Offset
        ) = *ByteSorter::template read<
            typename std::tuple_element<Index, Tuple>::type
        >(buffer+Offset);

        deserialize<Tuple,
                    Index  + 1,
                    Offset + sizeof(decltype(*std::get<Index>(Tuple{})))>(
            buffer
        );
    }
};

It should be evident that the way both the serialize and deserialize template methods are implemented is very similar to the TupleReader implementation. In fact the only difference is that no actual std::tuple instantiation instance is touched and instead of setting pointers to the buffer we are only reordering the bytes of each section of the buffer corresponding to a tuple element. This results in a complete In-place conversion between different byte orderings using the methods provided by a ByteSorter template such as BigEndianSorter.

Conclusion

At last I am now able to do everything I planned in the beginning in a very compact way using the Serializer, TupleReader and BinaryMapping templates. In practice this now looks like this:

typedef std::tuple<uint64_t*, uint16_t*> TestRecord;

uint8_t* buffer = reinterpret_cast<uint8_t*>(
    std::calloc(10, sizeof(uint8_t))
);

BinaryMapping<TestRecord> mapping(buffer);

mapping.set<0>(42);
mapping.set<1>(1001);

Serializer<BigEndianSorter>::serialize<TestRecord>(buffer);

uint8_t* testBuffer = reinterpret_cast<uint8_t*>(
    std::calloc(10, sizeof(uint8_t))
);

std::memcpy(testBuffer, buffer, 10);

Serializer<BigEndianSorter>::deserialize<TestRecord>(testBuffer);

BinaryMapping<TestRecord> testMapping(testBuffer);

std::cout << testMapping.get<0>() << std::endl;
std::cout << testMapping.get<1>() << std::endl;

std::free(buffer);
std::free(testBuffer);

The above coding makes use of all features provided by the described templates by first setting two values using BinaryMapping specialized on the TestRecord tuple, serializing them using Serializer specialized on the BigEndianSorter, deserializing the buffer back to the host byte ordering and reading the values using another BinaryMapping.

I find the template metaprogramming based approach to mapping binary structures into tuples described in this article to be very nice and clear. While template metaprogramming takes a while to get into it is a very powerful method for describing code in a generic way. I would certainly not recommend to try and fit everything in a template based approach but in some cases - especially when one would otherwise be required to write lots of boilerplate code repeatedly - it just fits and works out rather nicely. The best example for this would probably be the standard library which basically is just a large library of templates.
The next step in extending the templates explained in this article would probably be adapting the BinaryMapping template to offer sliding window like iteration over larger buffers and extending the supported data types.

Update: The current version of a small C++ template library extending the BinaryMapping templates detailed in this article may be found on Github or cgit.