Template Metaprogramming is cool! Using C++11 template overloading to make sense of queue behaviour.

photopin cc

Metaprogramming putting meat on the bones.

TL;DR Using an enumerated type as a behaviour selector at compile time by using template overloading[1] to select either total or partial queue access[2] behaviour whilst maintaining the same queue ADT interface 

The libfbp design goal is for a uniform queue interface as per the prescribed Abstract Data Type definition here using only enqueue and dequeue access class functions instead of having separate class function method calls for either partial or total access behaviour i.e. to get rid of try_enqueue and try_dequeue.

A queue can either be bounded or unbounded. 

• Bounded: holding only a limited number of items set as its capacity.
• Unbounded: being able to hold a, logically at least, unlimited amount of items - but physical storage limitations would ultimately apply.

Further, the queue access can either be partial or total. (Or for that matter synchronous but that's a different story.)

• Partial: Access calls will wait for certain conditions to hold true before returning e.g. a dequeue request will, if the queue is empty, wait for the condition that it is not empty to be true before removing an item and returning it.
• Total: by contrast access calls will not wait until they can perform the request but, rather, will return immediately with either a failure code or will throw an exception e.g. a dequeue request will, if the queue is empty, throw a queue empty exception.

Traditionally, selecting this behaviour has been done by having separate classes for unbounded/bounded and different class function names for partial/total, typically dequeue/enqueue and try_dequeue/try_enqueue.

However, by using template metaprogramming C++ no such idioms are required and behaviour can be selected at compile time.

Take for instance the enumerated data type used to select the kind of queue for the job:

This is implemented by the queue as follows which, although not mutually exclusive, only permits unbounded construction for partial access and bounded construction for total access. The scenario of total access for an unbounded queue is a bit of an oddity in that a total dequeue request can throw a queue empty exception but an unbounded queue total enqueue request is always fulfilled! 

I normally trail the next blog entry here in some "humorously" prescient manner  that is supposed to betray some sort of ongoing plan for delivery. But none exists and I have no idea what the next blog entry will be until I have written some code in my Tom Lehrer-esque copious free time.

References:

[1] Template Specialization and Overloading - Guru of the Week #49

[2] Maurice Herlihy and Nir Shavit. 2008. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.