diff options
author | Adrian Kummerlaender | 2014-07-24 16:46:52 +0200 |
---|---|---|
committer | Adrian Kummerlaender | 2014-07-24 16:46:52 +0200 |
commit | d3a6e17e32578a2c4c376626cbe5401cb57cd097 (patch) | |
tree | b741fc18c784856e099e6619f2fd3b3ca4a343dd | |
parent | 3c74afdd77033e85ad1e6869ac08802203177b1e (diff) | |
download | blog_content-d3a6e17e32578a2c4c376626cbe5401cb57cd097.tar blog_content-d3a6e17e32578a2c4c376626cbe5401cb57cd097.tar.gz blog_content-d3a6e17e32578a2c4c376626cbe5401cb57cd097.tar.bz2 blog_content-d3a6e17e32578a2c4c376626cbe5401cb57cd097.tar.lz blog_content-d3a6e17e32578a2c4c376626cbe5401cb57cd097.tar.xz blog_content-d3a6e17e32578a2c4c376626cbe5401cb57cd097.tar.zst blog_content-d3a6e17e32578a2c4c376626cbe5401cb57cd097.zip |
Added basic article datasource and output transformations
* articles contain the handle and date in their file name
** i.e. it is split using XPath string functions
** usage of the ISO date format provides automatic ordering
* added some articles from my blog as example data
5 files changed, 534 insertions, 0 deletions
diff --git a/articles/2013-03-01_introduction_to_expressing_and_controlling_object_ownership_in_cpp11.md b/articles/2013-03-01_introduction_to_expressing_and_controlling_object_ownership_in_cpp11.md new file mode 100644 index 0000000..1756d63 --- /dev/null +++ b/articles/2013-03-01_introduction_to_expressing_and_controlling_object_ownership_in_cpp11.md @@ -0,0 +1,92 @@ +# Introduction to expressing and controlling object ownership in C++11 + +_This is a theoretical introduction to my findings on memory management in C++11. You will not find code examples in this article because I think a explanation of what something is and how it is linked to other things is sometimes more helpful than a row of code snippets. Also I am only actively using C++ in a free time project (as of today unpublished) since about 3/4 of a year and there are already lots of nice code samples out there :) For more information on using the classes mentioned in this article I suggest checking out [cppreference.com](http://en.cppreference.com/w/cpp/memory)._ + +One important step to prevent memory errors in C++ applications is tracking the ownership of object instances. +Thereby the important aspect is not tracking who instantiated an object, but who is responsible for freeing the object. + +For every object allocated by _new_ or _std::malloc_ there has to be an corresponding _delete_ or _std::free_ - otherwise +we will leak memory on the heap because it is never released back into the hands of the operating system. + +This specific property of memory management in C++ is what makes tracking object ownership so important. If we do not know who owns +an object instance, we do not know who has to release the memory allocated for it. This means that we always have to think about freeing memory before letting a scope exit throw away our pointer to it. If we loose all pointers to a heap allocated object it will not automatically disappear but stay in memory _"forever"_. + +* Before we exit a scope by _return_, all memory allocated by _new_ or _std::malloc_ has to be freed +* Before we exit a scope by throwing an exception, all memory allocated by _new_ or _std::malloc_ has to be freed + +This is a lot to think about and it is easy to forget places where a scope is exited. These potential error sources only get more as a program grows in complexity. + +Luckily there is one thing that is guaranteed by the ISO C++ standard itself to be executed in all cases before a scope is exited: +Destructors of stack-allocated objects. To quote the standard: + +> As control passes from a throw-expression to a handler, destructors are invoked for all automatic objects +> constructed since the try block was entered. The automatic objects are destroyed in the reverse order of the +> completion of their construction. +> ([ISO C++ Standard draft, N3337](http://www.open-std.org/jtc1/sc22/wg21/), p. 380) + +This property enables us to delegate the freeing of memory to object destructors - we can wrap memory management in classes which can +then be used as normal scope bound variables. This approach to memory management called <abbr title="Resource Acquisition Is Initialization">[RAII](http://en.wikipedia.org/wiki/Resource_Acquisition_Is_Initialization)</abbr> +was invented by Bjarne Stroustrup, the creator +of C++, and enables us to free our minds from constantly worrying about possibilities for memory leaking. Without this technique C++ +code would mostly consist of code to allocate and free memory, and as such is vital to writing readable and at the same time exception safe code. + +We could write appropriate classes to wrap our object instance pointers by ourselves but luckily the current C++ standard library version includes +shiny new _smart pointer_ templates that give us flexible and standardised templates that do just that: wrap our pointers and limit their +lifetime to a scope. + +### std::unique_ptr + +> A unique pointer is an object that owns another object and manages that other object through a pointer. +> More precisely, a unique pointer is an object u that stores a pointer to a second object p and will dispose of +> p when u is itself destroyed (e.g., when leaving block scope (6.7)). In this context, u is said to own p. +> ([ISO C++ Standard draft, N3337](http://www.open-std.org/jtc1/sc22/wg21/), p. 513) + +As the standard states and the name implies a `std::unique_ptr` is an object that owns another object (pointer) uniquely. A `std::unique_ptr` can not be +copied, only moved and destroys the owned object in its destructor. This behavior implies that the contained object only has one owner - if we return +such a smart pointer from a function we say that the caller gains unique ownership over the returned object. But we can still retrieve a copy of the +contained pointer - because of that the `std::unique_ptr` only implies that it is unique, it does not enforce it other than by being non copyable. +This possibility to retrieve the raw pointer is not a weakness because it enables us to use normal raw pointers as a way to imply: you are allowed to +use this object instance in any way you like, but you are not required to think about its destruction. + +### std::shared_ptr + +> The shared\_ptr class template stores a pointer, usually obtained via new. shared\_ptr implements semantics +> of shared ownership; the last remaining owner of the pointer is responsible for destroying the object, or +> otherwise releasing the resources associated with the stored pointer. +> ([ISO C++ Standard draft, N3337](http://www.open-std.org/jtc1/sc22/wg21/), p. 524) + +In comparison to a `std::unique_ptr` a `std::shared_ptr` is usually not the unique owner of the contained object. It implements reference counting and +only destroys the managed memory if it is the only remaining - unique - owner when its destructor is executed. If we return a `std::shared_ptr` from a +function we say that the caller gains shared ownership over the returned object. This has the effect of making it hard to know when a contained object +will finally be released but as with the `std::unique_ptr` the task of worrying about this issue is handled automatically in the background. +I seldomly have the requirement to share ownership of an object with other objects, but there is one case I can think of were we can take advantage +of the reference counting part of the `std::shared_ptr` implementation: A factory class that needs to keep a pointer to the instantiated object (in my case +event subscribers) because it passes events into it but wants to give the caller an easy way to state that it is no longer using the object and wants to remove it from +the subscriber list. If we use a `std::shared_ptr` for this example we can regularly check the smart pointers for uniqueness and if that is the case remove +it from our subscriber list. As long as we have one or more owners outside the factory that are using the object to retrieve events we know that it is still +required to be supplied, if that is no longer the case we can safely remove it from the subscriber list. + +### std::weak_ptr + +> The weak\_ptr class template stores a weak reference to an object that is already managed by a shared\_ptr. +> To access the object, a weak\_ptr can be converted to a shared_ptr using the member function lock. +> ([ISO C++ Standard draft, N3337](http://www.open-std.org/jtc1/sc22/wg21/), p. 533) + +If we want to imply to a owner of a `std::shared_ptr` that she is only granted temporary, non-owning access to the object instance as we did through +raw pointers to the contained object of a `std::unique_ptr`, we can do that by passing a `std::weak_ptr`. This means +that a function returning such a smart pointer is implying that we grant the caller temporary shared ownership while advertising the possibility that +the contained object instance does not exist anymore. We can not assume that we have a usable instance and will have to check before converting the `std::weak_ptr` to +a `std::shared_ptr`. + +### What I prefer to use + +As I already hinted earlier I am only seldomly using a `std::shared_ptr` and the accompanying `std::weak_ptr` and am mostly relying on the combination of +a single, distinct object owning `std::unique_ptr` that passes around "use only" raw pointers to other objects that are guaranteed to not exceed the lifetime of the owner +itself. These new smart pointers in C++11 really make writing nice and exception safe code easier and make C++ feel more like a language with automatic +garbage collection while still enabling the programmer to use the full possibilities of pointers when it is appropriate. We can take advantage of the +possibilities of automatic memory management without the cost of a full blown automatic garbage collection system. + +I for one like this approach to handling memory very much and find C++11 code to be easier on the eyes while making a higher level of abstraction of the program +logic possible. + +As a footnote, smart pointers are only one of many interesting additions in C++11. If you want more you should definitely check out the [other features](http://www.stroustrup.com/C++11FAQ.html)! diff --git a/articles/2013-04-27_declaring_functions_local_to_a_translation_unit_in_cpp.md b/articles/2013-04-27_declaring_functions_local_to_a_translation_unit_in_cpp.md new file mode 100644 index 0000000..1cb8480 --- /dev/null +++ b/articles/2013-04-27_declaring_functions_local_to_a_translation_unit_in_cpp.md @@ -0,0 +1,43 @@ +# Declaring functions local to a translation unit in C++ + +In a current project of mine I defined the following function marked with the inline hint without declaring it in a header file: + + inline bool checkStorageSection(const void* keyBuffer) { + return (StorageSection::Edge == readNumber<uint8_t>( + reinterpret_cast<const uint8_t*>(keyBuffer)+0 + )); + } + +This function was not defined in one but in multiple translation units - each instance with the same signature but a slightly different comparison contained in the function body. I expected these functions to be local to their respective translation unit and in the best case to be inlined into their calling member methods. + +While debugging another issue that seemed to be unrelated to these functions I noticed a strange behaviour: The calls in the member methods that should have linked to their respective local function definition all linked to the same definition in a different translation unit (the one displayed above). A quick check in GDB using the _x_-command to display the function addresses confirmed this suspicion: + + // Function address in translation unit A + 0x804e718 <GraphDB::checkStorageSection(void const*)>: 0x83e58955 + + // Function address in translation unit B + 0x804e718 <GraphDB::checkStorageSection(void const*)>: 0x83e58955 + +The address _0x804e718_ was the address of the function definition in translation unit "A" in both cases. At first I suspected that the cause was probably that both definitions were located in the same namespace, but excluding them from the enclosing namespace declaration did not fix the problem. + +After that I turned to the language standard and found the following statements concerning linkage: + +> A name having namespace scope (3.3.6) has internal linkage if it is the name of +> — a variable, function or function template that is explicitly declared static +> ([ISO C++ Standard draft, N3337](http://www.open-std.org/jtc1/sc22/wg21/), p. 55/56) + +and: + +> A name having namespace scope that has not been given internal linkage above has the same linkage as the enclosing namespace if it is the name of +> — a variable; or +> — a function; or +> ([ISO C++ Standard draft, N3337](http://www.open-std.org/jtc1/sc22/wg21/), p. 56) + +Internal linkage is defined as: + +> When a name has internal linkage , the entity it denotes can be referred to by names from other scopes in the same translation unit. +> ([ISO C++ Standard draft, N3337](http://www.open-std.org/jtc1/sc22/wg21/), p. 55) + +This means that functions in a namespace that are not explicitly marked as linked internally by the _static_ keyword, have linkage across translation units. So the compiler must have simply selected the first definition of the function and linked all following calls to this function signature to that first instance without checking if there was a definition in the current translation unit. + +So the problem was fixed by simply adding _static_ to the function definition. After this change all calls led to the correct definition. diff --git a/articles/2013-10-06_notizen_zu_cpp_und_unicode.md b/articles/2013-10-06_notizen_zu_cpp_und_unicode.md new file mode 100644 index 0000000..6685687 --- /dev/null +++ b/articles/2013-10-06_notizen_zu_cpp_und_unicode.md @@ -0,0 +1,94 @@ +# Notizen zu C++ und Unicode + +Unicode ist ein Zeichensatz der den Großteil der weltweit gebräuchlichen Schriftsysteme abdeckt. +Jedes einzelne Symbol wird dabei von einem sogenannten Code-Point definiert, welcher bis zu 21 Bit umfassen kann. +Je nach präferierter Enkodierung wird ein solcher Code-Point von vier, zwei oder einer Code-Unit mit einer Länge von respektive ein, zwei oder vier Byte repräsentiert. + +Die direkte Repräsentation eines Unicode Code-Points ohne Aufteilung auf mehrere Code-Units nennt sich UTF-32. Wird ein Code-Point in ein oder zwei jeweils zwei Byte langen Code-Units enkodiert, spricht man von UTF-16. Die in gewöhnlichen Anwendungsfällen effizienteste Enkodierung ist UTF-8. Dort wird jeder Code-Point von bis zu vier jeweils ein Byte langen Code-Units repräsentiert. Vorteil von UTF-8 gegenüber den beiden anderen Varianten ist dabei die Rückwärtskompatibilität zu ASCII sowie die Unabhängigkeit von der jeweils plattformspezifischen Byte-Reihenfolge. + +Getreu der auf [UTF-8 Everywhere](http://www.utf8everywhere.org/) hervorgebrachten Argumentation werden wir uns im Folgenden mit UTF-8 beschäftigen und die beiden alternativen Enkodierungsarten ignorieren. + +Grundsätzlich stellt es auf der Plattform meiner Wahl - Linux mit Lokalen auf _en\_US.UTF-8_ - kein Problem dar, UTF-8 enkodierte Strings in C++ Programmen zu verarbeiten. +Den Klassen der C++ Standard Library ist es, solange wir nur über das reine Speichern und Bewegen von Strings sprechen, egal ob dieser in UTF-8, ASCII oder einem ganz anderen Zeichensatz kodiert ist. Möchten wir sicher gehen, dass ein in einer Instanz von _std::string_ enthaltener Text tatsächlich in UTF-8 enkodiert wird und dies nicht vom Zeichensatz der Quelldatei abhängig ist, reicht es dies durch voranstellen von _u8_ zu definieren: + + std::string test(u8"Hellø Uni¢ød€!"); + +Der C++ Standard garantiert uns, dass ein solcher String in UTF-8 enkodiert wird. Auch die Ausgabe von in dieser Form enkodierten Strings funktioniert nach meiner Erfahrung - z.T. erst nach setzen der Lokale mittels _std::setlocale_ - einwandfrei. Probleme gibt es dann, wenn wir den Text als solchen näher untersuchen oder sogar verändern wollen bzw. die Ein- und Ausgabe des Textes in anderen Formaten erfolgen soll. Für letzteres gibt es eigentlich die _std::codecvt_ Facetten, welche aber in der aktuellen Version der GNU libstdc++ noch [nicht implementiert](http://gcc.gnu.org/onlinedocs/libstdc++/manual/status.html#status.iso.2011) sind. +Wir müssen in diesem Fall also auf externe Bibliotheken wie beispielweise [iconv](https://www.gnu.org/software/libiconv/) oder [ICU](http://site.icu-project.org/) zurückgreifen. Auch die in der C++ Standard Library enthaltenen Templates zur String-Verarbeitung helfen uns bei Multibyte-Enkodierungen, zu denen auch UTF-8 zählt, nicht viel, da diese mit dem _char_ Datentyp und nicht mit Code-Points arbeiten. So liefert _std::string_ beispielsweise für einen UTF-8 enkodierten String, welcher nicht nur von dem in einer Code-Unit abbildbaren ASCII-Subset Gebrauch macht, nicht die korrekte Zeichenanzahl. Auch eine String-Iteration ist mit den Standard-Klassen nur Byte- und nicht Code-Point-Weise umsetzbar. Wir stehen also vor der Entscheidung eine weitere externe Bibliothek zu verwenden oder Programm-Intern vollständig auf UTF-32 zu setzen. + +### Ein UTF-8 Codepoint-Iterator in C++ + +Um zumindest für rein lesende Zugriffe auf UTF-8 Strings nicht gleich eine Bibliothek wie Boost oder [easl](http://code.google.com/p/easl/) verwenden zu müssen habe ich einen einfachen UTF-8 Codepoint-Iterator anhand der Spezifikation in [RFC3629](http://tools.ietf.org/html/rfc3629) implementiert. Den Quellcode dieser Klasse stelle ich auf [Github](https://github.com/KnairdA/CodepointIterator) oder in [cgit](http://code.kummerlaender.eu/CodepointIterator/tree/) als Open Source unter der MIT-Lizenz zur freien Verfügung. + +UTF-8 enkodiert die aktuell maximal 21 Bit eines Unicode Code-Points in bis zu vier Code-Units mit einer Länge von je einem Byte. Die verbleibenden +maximal 11 Bit werden dazu verwendet, Anfangs- und Fortsetzungs-Bytes eines Code-Points zu kennzeichnen und schon in der ersten Code-Unit zu definieren, in wie vielen Code-Units das aktuelle Symbol enkodiert ist. + +<p> +<table> + <thead> + <tr> + <th scope="col">Payload</th> + <th scope="col">Struktur</th> + </tr> + </thead> + <tbody> + <tr> + <td>7</td> + <td><tt>0xxxxxxx</tt></td> + </tr> + <tr> + <td>11</td> + <td><tt>110xxxxx 10xxxxxx</tt></td> + </tr> + <tr> + <td>17</td> + <td><tt>1110xxxx 10xxxxxx 10xxxxxx</tt></td> + </tr> + <tr> + <td>21</td> + <td><tt>11110xxx 10xxxxxx 10xxxxxx 10xxxxxx</tt></td> + </tr> + </tbody> +</table> +</p> + +In obenstehender Tabelle ist die in [RFC3629](http://tools.ietf.org/html/rfc3629) definierte Struktur der einzelnen Code-Units zusammen mit der jeweiligen Anzahl der Payload-Bits dargestellt. +Anhand der Tabelle können wir erkennen, dass die Rückwärtskompatibilität zu ASCII dadurch gewährleistet wird, dass alle Code-Points bis +einschließlich 127 im ersten Byte dargestellt werden können. Sobald in der ersten Code-Unit das Bit mit dem höchsten Stellenwert gesetzt ist, handelt es sich um einen Code-Point mit mehr als einer Code-Unit. Die genaue Anzahl der Code-Units lässt sich an der Anzahl der führenden 1er-Bits erkennen. Zwischen Payload und Header steht dabei immer ein 0er-Bit, Fortsetzungs-Bytes beginnen in UTF-8 immer mit dem Präfix <tt>10</tt>. + +Zur Erkennung und Umformung der UTF-8 Code-Units verwenden wir in der _UTF8::CodepointIterator_-Klasse die folgenden, in stark typisierten Enums definierten, Bitmasken: + + enum class CodeUnitType : uint8_t { + CONTINUATION = 128, // 10000000 + LEADING = 64, // 01000000 + THREE = 32, // 00100000 + FOUR = 16, // 00010000 + }; + + enum class CodePoint : uint8_t { + CONTINUATION = 63, // 00111111 + TWO = 31, // 00011111 + THREE = 15, // 00001111 + FOUR = 7, // 00000111 + }; + +Bei tieferem Interesse lässt sich die Implementierung der UTF-8 Logik in der Quelldatei [codepoint_iterator.cc](https://github.com/KnairdA/CodepointIterator/blob/master/src/codepoint_iterator.cc) nachlesen. +Zusätzlich zu den in GoogleTest geschriebenen [Unit-Tests](https://github.com/KnairdA/CodepointIterator/blob/master/test.cc) sehen wir im folgenden noch ein einfaches Beispiel zur Verwendung des `UTF8::CodepointIterator` mit einem [Beispieltext](http://www.columbia.edu/~fdc/utf8/) in altnordischen Runen: + + std::string test(u8"ᛖᚴ ᚷᛖᛏ ᛖᛏᛁ ᚧ ᚷᛚᛖᚱ ᛘᚾ ᚦᛖᛋᛋ ᚨᚧ ᚡᛖ ᚱᚧᚨ ᛋᚨᚱ"); + + for ( UTF8::CodepointIterator iter(test.cbegin()); + iter != test.cend(); + ++iter ) { + std::wcout << static_cast<wchar_t>(*iter); + } + +Die Dereferenzierung einer Instanz des Iterators produziert den aktuellen Code-Point als _char32\_t_, da dieser Datentyp garantiert vier Byte lang ist. Die Ausgabe eines solchen UTF-32 enkodierten Code-Points ist mir allerdings leider nur nach dem Cast in _wchar\_t_ gelungen. Dieser wird trotzdem nicht als Dereferenzierungs-Typ verwendet, da die Länge nicht fest definiert ist, sondern abhängig von der jeweiligen C++ Implementierung unterschiedlich sein kann. Dies stellt jedoch kein größeres Problem dar, da der Iterator für die interne Betrachtung von Strings und nicht zur Konvertierung für die Ausgabe gedacht ist. + +### Fazit + +* UTF-8 ist die Kodierung der Wahl, da Übermenge von ASCII und kompakt für englische Texte +* Nicht alle Möglichkeiten die im Standard definiert sind, sind auch implementiert +* String-Manipulation und Konvertierung benötigten externe Bibliotheken +* Rein lesende Iteration durch UTF-8 enkodierte Strings ist mit relativ wenig Aufwand möglich +* Am wichtigsten ist es *eine* Kodierung zu verwenden und nur für I/O zu konvertieren diff --git a/articles/2013-11-03_mapping_binary_structures_as_tuples_using_template_metaprogramming.md b/articles/2013-11-03_mapping_binary_structures_as_tuples_using_template_metaprogramming.md new file mode 100644 index 0000000..24c000e --- /dev/null +++ b/articles/2013-11-03_mapping_binary_structures_as_tuples_using_template_metaprogramming.md @@ -0,0 +1,240 @@ +# Mapping binary structures as tuples using template metaprogramming + +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](https://code.google.com/p/leveldb/). While the resulting prototype [libGraphStorage](https://github.com/KnairdA/GraphStorage/) +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](https://github.com/KnairdA/GraphStorage/blob/master/src/storage/id/edge_id.cc) 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 libraries [_std::tuple_](http://en.cppreference.com/w/cpp/utility/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_](http://en.cppreference.com/w/cpp/types/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_](http://en.cppreference.com/w/cpp/utility/tuple/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_](http://en.cppreference.com/w/cpp/utility/tuple/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_](http://en.cppreference.com/w/cpp/utility/tuple/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](https://github.com/KnairdA/BinaryMapping/) or [cgit](http://code.kummerlaender.eu/BinaryMapping/). diff --git a/articles/2014-01-05_disabling_methods_in_implicitly_instantiated_class_template_specializations_in_cpp.md b/articles/2014-01-05_disabling_methods_in_implicitly_instantiated_class_template_specializations_in_cpp.md new file mode 100644 index 0000000..55da8fd --- /dev/null +++ b/articles/2014-01-05_disabling_methods_in_implicitly_instantiated_class_template_specializations_in_cpp.md @@ -0,0 +1,65 @@ +# Disabling methods in implicitly instantiated class template specializations in C++ + +During my current undertaking of developing a [template based library](https://github.com/KnairdA/BinaryMapping) with the purpose of making it easy to map flat binary structures into `std::tuple` instances, I came upon the problem of enabling methods in a template class only when a argument of the class template equals a specific type. + +The specific scenario I am talking about is disabling the _serialize_ and _deserialize_ template methods in all specializations of the +_[Tuple](https://github.com/KnairdA/BinaryMapping/blob/master/src/tuple/tuple.h)_ class template whose _Endianess_ argument is not of the type _UndefinedEndian_. My first working implementation of this requirement looks as follows: + + template < + typename CustomOrder, + typename Helper = Endianess + > + inline typename std::enable_if< + std::is_same<UndefinedEndian, Helper>::value, + void + >::type serialize() { + Serializer<InPlaceSorter<CustomOrder>>::serialize(this->tuple_); + } + +As we can see I am relying on the standard libraries `std::enable_if` template to enable the method only if the _Helper_ template argument equals the type _UndefinedEndian_. One may wonder why I am supplying the `std::enable_if` template with the argument _Helper_ instead of directly specifying the class template argument _Endianess_. This was needed because of the following paragraph of the ISO C++ standard: + +> The implicit instantiation of a class template specialization causes the implicit instantiation of the declarations, but not of the definitions or default arguments, of the class member functions, [...] +> ([ISO C++ Standard draft, N3337](http://www.open-std.org/jtc1/sc22/wg21/), p. 346) + +This paragraph means that as soon as we instantiate a class template specialization by actually using it all method declarations are also implicitly instantiated. This leads to a problem as soon as we are generating a invalid method declaration by disabling it, as the _Endianess_ class template argument is not seen as a variable template argument by the time we are declaring the _serialize_ or _deserialize_ methods. So if we want to use `std::enable_if` to disable a method specialization we need to make it dependent on a template argument of that method. This is why +I defined a additional _Helper_ argument which defaults to the class template's _Endianess_ argument in the declaration of both methods. + +The code supplied above works as expected but has at least two flaws: There is an additonal template argument whose sole purpose is to work around the C++ standard to make _[SFINAE](https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error)_ possible and the return type of the method is obfuscated by the use of the `std::enable_if` template. +Luckily it is not the only way of achieving our goal: + + template < + typename CustomOrder, + typename = typename std::enable_if< + std::is_same<UndefinedEndian, Endianess>::value, + void + >::type + > + inline void serialize() { + Serializer<InPlaceSorter<CustomOrder>>::serialize(this->tuple_); + } + +In this second example implementation we are moving the `std::enable_if` template from the return type into a unnamed default template argument of the method. This unnamed default +template argument which was not possible prior to the C++11 standard reduces the purpose of the `std::enable_if` template to selectively disabling method specializations. Additionally +the return type can be straight forwardly declared and the _Helper_ template argument was eliminated. + +But during my research concerning this problem I came up with one additional way of achieving our goal which one could argue is even better than the second example: + + template <typename CustomOrder> + inline void serialize() { + static_assert( + std::is_same<Endianess, UndefinedEndian>::value, + "Endianess must be UndefinedEndian to use serialize<*>()" + ); + + Serializer<InPlaceSorter<CustomOrder>>::serialize(this->tuple_); + } + +This implementation of the _serialize_ method renounces any additonal template arguments and instead uses a declaration called `static_assert` which makes any specializations where +the statement `std::is_same<Endianess, UndefinedEndian>::value` resolves to false ill-formed. Additionally it also returns a helpful message to the compiler log during such a situation. + +While I finally [decided on](https://github.com/KnairdA/BinaryMapping/commit/ed85e10cf43767576141d94f2b86f3cc1eda9dfb) using the second approach detailed in this article in the library +because it feels better to me, the usage of `static_assert` makes it possible to generate better template error messages and I will certainly try to make use of this feature in the future. + +__Update 1:__ The second listing currently only compiles in Clang 3.3 from the test set consisting of g++ 4.8.2 and Clang 3.3. While I believe the listing to be valid according to the standard I need to check if it is a bug in one of the compilers or if it is a situation where the standard doesn't clearly define what the compiler should do. I will update this article as soon as I come to a conclusion in this matter. + +__Update 2:__ I found a corresponding [issue](http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57314) in the GCC bug tracker. So this problem is actually a case where the C++ standard is not clearly defined and this also explains the difference in behaviour between Clang and g++. In the liked issue there is also a link to the corresponding core language [issue](http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1635). So it seems that I have to either wait for the standard committee to come to a solution or to use listing number three instead of the currently used implementation in my library. |