Combining container hashes with C++14 metaprogramming – Cure for insomnia #1729

The most missed feature in standard C++ for thirteen years, more than lambdas or variadic templates, are the hash container equivalents of std::map and std::set. The “normal” map and set containers are implemented as binary trees, and any class of objects that one may want to store in a map or set must implement strict weak ordering – meaning that either the less-than operator must be defined for that class, or the container template is instantiated with a custom compare functor.

All of the fundamental types and most of the standard library types for which a strict weak ordering makes sense has the less-than operator defined. User defined types which have “key” members that are fundamental types can simply define their own strict weak ordering based on the lexicographical ordering of the tuple of those key members. This makes it somewhat easy to recursively apply strict weak order to user defined types composed of, or derived from, other user defined types.

Similarly, in modern C++, the hash containers require that the class of objects stored in them must have a hash operation defined. As with the normal map and set, the standard library also provides default hashing functions for fundamental types and standard library types for which a hash makes sense.

Unlike the normal map and set, it is less trivial to provide hash functions for user defined types. Naïve combinations of hashes resulting from hash functions may lead to more collisions than desired, for while the standard library may provide a hash function that is generally reasonable for the fundamental and standardized types, it doesn’t necessarily apply for user defined hashes.

What is needed is a straightforward way to hash multiple objects as one entity and without having to do tricky bit-twiddling ourselves. Fortunately, the standard library, and the updated C++ language, provides all that is needed. There are three elements that are required to make this work:
1. It must look like std::hash
2. The standard library provides std::bitset for arbitrarily sized (nb: but computable at compile time) strings of bits, and it also provides a std::hash specialization for std::bitsets
3. It should not take more than one or two logical lines of code for clients to specialize

These three elements form what I call the “vice approach” to design. It is both top-down – by specifying what the design looks like; and bottom-up – by specifying the components of the implementation. In the vice is the programmer’s head, and the process of resolving the top design and the bottom design is tightening the vice around the programmer’s head until it either explodes1 or the carbon fuses into diamond.

So, to wit, the top surface of the design, which otherwise could be viewed as “how would a programmer write” should look like this:

struct Department {std::bitset<7> dep_id;};
struct Employee {short id; std::u16string name; Department dep;};
// Such that we can write something resembling (not C++ syntax):
hash(Department d) → hash(d.dep_id);
//and
hash(Employee e) → hash(e.id, e.name, e.dep);

The bottom surface of the design should result in this:

std::bitset</* Size of combined hashes */> result = /* Bit shifting */;
return std::hash</* type of result */>{}(result);

We start tightening the vice by figuring out how to calculate the size of the final bitset. Without this, we’d have to resort to using vector and the runtime calculation of the size and degraded performance when used with hash containers.

We somehow have to calculate the total number of bits, which I’ll call area2, of the hashes of each key member of an arbitrary structure like Department or Employee in compile-time. This means the use of template metaprogramming; namely, using variadic templates and recursive list processing.

// Definition
template<typename Arg, typename... Args>
struct area_of
{
  static constexpr area_of_t<Arg> value =
    area_of<Arg>::value + area_of<Args...>::value;
};
// Partial specialization
template<typename Arg>
struct area_of<Arg>
{
  static constexpr area_of_t<Arg> value =
    sizeof(area_of_t<Arg>) * CHAR_BIT;
};

For those unfamiliar with template metaprogramming, what this code does is similar to what LISP or Prolog does. Say you have a list {1, 2, 3, 4, 5, 6, 7 …}. To go through each of the list of the element, you extract the first element – the head – and pass the tail list to the next operation, which is often the recursively to the same function. A programmer would write something like this:

area_of<bitset<7>> /* and */ area_of<short, u16string, Department>

So when we pass a list of types to area_of, it extracts the head Arg, and the tail is kept in the parameter pack Args. It calculates the area of the head by calling area_of::value, and then combines it to the area of the tail. Since the tail is itself still a list, the call to area_of::valuewill recursively calculate the area of its head and its tail etc etc. Args… is called template parameter unpacking which is almost like a macro that places the rest tail into the code. We have a partial specialization of area_of which takes one argument, and this is the exit condition that is required of any recursive process, whether it’s a runtime operation or a compile time operation. In that exit condition, it calculates the area of each individual part of the hash by multiplying its size in bytes by the number of bits per byte. CHAR_BIT is a standard library defined macro and should be used instead of assuming all compilers use octets for bytes.

The member value of area_of is declared as static constexpr. This is pretty much necessary of all template metaprogramming. constexpr tells the compiler to evaluate the expression at compile time if possible, and therefore usable as a template argument for something else.
The definition of area_of_t will be explained later, but it would suffice to say that it is the type of the integer that is returned by a hash function. At this point, we only have to consider that we only need to know the sizeof that integer type. It’s often defined as std::size_t but why assume when the compiler can work it out for you.

With the definitions of area_of, we now can figure out the bit size of any combination of hashes:

std::bitset<area_of<bitset<7>>> result;
std::bitset<area_of<short, u16string, Department>> result;

Now we get on to the task of tightening the other side of the vice. We’ll call it multihash and we define it thus:

template<typename...> struct multihash;
template<typename T> struct multihash<T> : std::hash<T>{};

We declare a struct template multihash with variadic template arguments. We don’t give it a definition, as there is no sensible default that covers all bases. We can, however, partially specialize it for one template argument and by default, we will make it equivalent to std::hash. This makes it easier later on where we want to calculate the hash of any single value and we don’t want to have to call the correct hash depending on whether it is a fundamental or library provided type versus a user defined type.

To put it another way, we would be able to call multihash or multihash and let the compiler figure out whether it calls the std::hash or the user defined version. Now that we have the easy stuff defined, we can now define a version of multihash that can do the work of hashing an arbitrary number of arguments.

template<typename Arg, typename... Args>
struct multihash<Arg, Args...>
{
  auto operator()(const Arg& arg, const Args&... args) const noexcept
  {
    std::bitset<area_of<Arg, Args...>::value> concat{
      multihash<Arg>{}(arg)
    };
    concat <<= (concat.size() - area_of<Arg>::value);
    concat |= multihash<Args...>{}(args...);
    return std::hash<decltype(concat)>{}(concat);
  }
};

multihash follows in the footsteps of std::hash in that is is a functor – an object that can be used like a function (has the operator() defined). One, is that one of its specializations inherits from std::hash, but more importantly, it needs to be a functor to be used in the hash containers. The operator() is declared as const noexcept to allow for optimizations, and uses return type deduction so that, again, the compiler can work out the integer type it needs to return rather than having us figure it out and maybe getting it wrong.

Similarly to area_of, this uses the list/head/tail recursive structure to move through the variadic template arguments one by one. Note that const Args&… is not the same kind of variadic functions as the printf clan. This is completely safe as, unlike printf, these parameter packs preserves both the number of arguments and the type of their arguments. It is as though the compiler generates a completely new function for every permutation of arguments that occurs in a program’s source code, but without the nastiness of variadic functions or C preprocessor macros.

The actual function itself basically calculates the hash of each individual argument, and concatenates them into the bitset concat, the area of which we have already calculated during compilation, and return the hash of that uber-bitset as the combined hash. Then we have completed the circle – tightened the vice.

What’s left is actually explaining where area_of_t comes from. It is defined like this:

template<typename T>
using area_of_t = decltype(multihash<T>{}(std::declval<T>()));

C++ has now introduced an alternative to typedef called aliases. We define the integer type of the area_of calculation to be the type returned when we use multihash an any single type. The use of declval and decltype allows us to get the compiler to evaluate the expression to figure out its type without actually having to run the program. Thus, there is already a definition for all of the fundamental types and library defined types, and also for any user defined types that have specialized multihash to provide their own hash definitions. So now we actually get to see how a programmer would use this library:

template
struct multihash
{
  auto operator()(const Department& dep) const noexcept
  {
    return multihash{}(dep.dep_id);
  }
};

template
struct multihash
{
  auto operator()(const Employee& emp) const noexcept
  {
    return multihash{}
             (emp.id, emp.name, emp.dep);
  }
};

This is not really that far off from our original goal of being able to define these in just one line. These are explicit instantions of multihash for the types Department and Employee. The multihash of Department must be defined before Employee’s because the multihash of Employee needs to “see” the definition for Department. Otherwise it would use the default, which is std::hash, for which we have not instantiated.

Note the judicious use of decltype in order to supply the template arguments. This just makes it much more easier if we, say, define Employee::name to be std::wstring instead and so we don’t have to change anything as we’ve told the compiler to figure it out. Finally, for completeness, we show the normal usage for this:

multihash emp_hash;
multihash dep_hash;

Department dep1{0b0'00'00'01};
Department dep2{0b0'00'00'10};
Department dep3{0b0'00'00'11};

Employee emp1{1, u"one", dep1};
Employee emp2{2, u"two", dep2};
Employee emp3{3, u"three", dep3};

std::cout << dep_hash(dep1) << std::endl;
std::cout << dep_hash(dep2) << std::endl;
std::cout << dep_hash(dep3) << std::endl;

std::cout << emp_hash(emp1) << std::endl;
std::cout << emp_hash(emp2) << std::endl;
std::cout << emp_hash(emp3) << std::endl;

std::unordered_set<Employee, multihash> empset{
  emp1, emp2, emp3};

Just because we can, we demonstrate the other new C++ features, such as binary literals (0b11010101), number literal separators (31’4159’26’535897’9), unicode string literals (u”I’m a string”), and braced initialization ({1, u”two”, dep3} or {emp3, emp2, emp1}).

Advertisements

Easy adapter pattern with object map

Say you want to have an a class that allows dynamic adaptation. You can’t create it as a template class to provide “policies” in policy based design because different policies will create distinct classes. This will prevent different adapter classes from attaching to the same object.

You also wouldn’t want to require adapter classes to have to inherit from some interface and introduce an unneeded dependency through virtual inheritance.

Ideally, you’d want to have the flexibility of templates but in a dynamic context. This is the kind of container you’d need to achieve this:

#include <unordered_map>
#include <typeindex>
#include <memory>
.
.
.
std::unordered_map<std::type_index, std::shared_ptr<void>> object_map;

type_index is a C++11 feature that allows types to have hash and weak ordering semantics. To get rid of the boilerplate code to use this container, you’d have interface functions like these:

template<typename T, typename... Args>
void add_object(Args... args)
{
  object_map[std::type_index{typeid(T)}] = std::static_pointer_cast<void>(std::make_shared<T>(args...));
}

template<typename T>
T& get_object()
{
  return *static_cast<T*>(object_map[std::type_index{typeid(T)}].get());
}

shared_ptr is used because it is the only smart pointer that supports a void type as well as having nice helper functions to cast to shared_ptrs of other types. It also uses variadic templates to allow construction via make_shared, which is the exception safe way to create a shared_ptr. What’s also nice about it is that the casting to a void shared_ptr does not throw away custom deleters, as proven by this code:

struct A
{
  static int gen;

  A()
  {
    ++gen;
  }

  void operator()()
  {
    std::clog <<  "Run A: " << gen <<  std::endl;
  }

  ~A()
  {
    std::cerr <<  "Destructing A" <<  std::endl;
  }
};

int A::gen = 0;

int main()
{
  auto aptr = std::shared_ptr<A>(new A(), [](A* _p)
    {
      std::cerr << "Custom delete A" <<  std::endl;
      delete _p;
    });
  auto voidptr = std::static_pointer_cast(aptr);
  aptr.reset();
  (*std::static_pointer_cast<A>(voidptr).get())();
  std::clog << "Number of owners: " <<  voidptr.use_count() << " " << aptr.use_count() << std::endl;

  return 0;
}

A has destructor to signal that it is in fact being deleted. aptr has a custom deleter. After being cast to a shared_ptr<void>, aptr is reset to show that it isn't the custom deleter in aptr that is destroying the A object but the one that is casted into voidptr.

The output of that test is:

Run A: 1
Number of owners: 1 0
Custom delete A
Destructing A

So back to the object map. This simple test demonstrates it working:

std::clog << "Object map test" << std::endl;
add_object<A>();
add_object<int>(42);
add_object<double>(2.71828);
add_object<std::string>("Hello world!");

std::cout << get_object<std::string>() << " " << get_object<int>() << " " << get_object<double>() << std::endl;
get_object<A>()();

The output of this test is:

Object map test
Hello world! 42 2.71828
Run A: 2
Destructing A

Making templates easier with named-arguments

Say you have a template that requires a large number of arguments. ie, more than three. This is not a very clear or concise interface and not self-documenting. Any thing with a large number of arguments suffers from the same problem. You can give default arguments but if you just want to provide one argument that happens to be after one or more other default arguments, you have to provide those as well and you have to know the defaults if you want to keep the default behaviour bar the one you want to modify. My solution to provide named template arguments is this:

template<typename NumType,
         NumType TLow = std::numeric_limits<NumType>::lowest(),
         NumType TMin = std::numeric_limits<NumType>::min(),
         NumType TMax = std::numeric_limits<NumType>::max(),
         NumType TDef = 0,
         NumType TInv = -1,
         typename Specials = TestList<NumType>,
         typename Excludes = TestList<NumType> >
struct NumWrapper
{
    static constexpr NumType low = TLow;
    static constexpr NumType min = TMin;
    static constexpr NumType max = TMax;
    static constexpr NumType def = TDef;
    static constexpr NumType inv = TInv;
    typedef Specials inc_type;
    typedef Excludes exc_type;

    template<NumType Special>
    struct Min
    {
        typedef NumWrapper<NumType, low, Special, max, def, inv, Specials, Excludes> type;
    };

    template<NumType Special>
    struct Max
    {
        typedef NumWrapper<NumType, low, min, Special, def, inv, Specials, Excludes> type;
    };

    template<NumType Special>
    struct Low
    {
        typedef NumWrapper<NumType, Special, min, max, def, inv, Specials, Excludes> type;
    };

    template<NumType Special>
    struct Def
    {
        typedef NumWrapper<NumType, low, min, max, Special, inv, Specials, Excludes> type;
    };

    template<NumType Special>
    struct Inv
    {
        typedef NumWrapper<NumType, low, min, max, def, Special, Specials, Excludes> type;
    };

    template<NumType... List>
    struct Inc
    {
        typedef NumWrapper<NumType, low, min, max, def, inv, TestList<NumType, List...>, exc_type> type;
    };

    template<NumType... List>
    struct Exc
    {
        typedef NumWrapper<NumType, low, min, max, def, inv, inc_type, TestList<NumType, List...> > type;
    };

    NumType val = def;
    NumWrapper() = default;
    NumWrapper(NumType _v) : val(_v) {}

    operator NumType ()
    {
        return val;
    }
};

This class is something I needed to quickly create data ranges really easily in order to generate values for testing. I may want to provide a different minimum that is different from the underlying type but use the std::numeric_limits for the other values, or I may want to provide extra values that have a special meaning within the context of its use.

The named argument effect is achieved by declaring nested classes in the NumWrapper classes that have an internal typedef that creates a new NumWrapper type from the enclosing template instantiation. The internal typedef only instantiates on the template argument they “name”, and use the rest of the values from the enclosing template instantiation. The use of default template arguments in the main definition, and the inheritance of those arguments as you continue the typedef chain means the user does not then have to provide those values if they don’t want to.

Take special note that, as the library developer, you will of course need to know the order of the template arguments. You just have to make it so that the user of your library does not have to know the order.

Declaring a new integer type becomes as simple as this:

typedef NumWrapper<short>::Max<9999>::type::Def<1>::type::Min<-10>::type::Inc<2,3,5,7,11,13,17,19>::type MyIntegralType;

It also makes it easy to figure out what the expected range and values of this integral type should be. You can even automate its specialization for std::numeric_limits:

namespace std
{
    template<typename NumType, NumType TLow, NumType TMin, NumType TMax, NumType TDef, NumType TInv, typename Specials, typename Excludes>
    struct numeric_limits<NumWrapper<NumType, TLow, TMin, TMax, TDef, TInv, Specials, Excludes> > : numeric_limits<NumType>
    {
        static constexpr bool is_specialized = true;
        static constexpr NumType min()
        {
            return NumWrapper<NumType, TLow, TMin, TMax, TDef, TInv, Specials, Excludes>::min;
        }

        static constexpr NumType max()
        {
            return NumWrapper<NumType, TLow, TMin, TMax, TDef, TInv, Specials, Excludes>::max;
        }

        static constexpr NumType lowest()
        {
            return NumWrapper<NumType, TLow, TMin, TMax, TDef, TInv, Specials, Excludes>::low;
        }
    };

    template<typename NumType, NumType TLow, NumType TMin, NumType TMax, NumType TDef, NumType TInv, typename Specials, typename Excludes>
    struct is_arithmetic<NumWrapper<NumType, TLow, TMin, TMax, TDef, TInv, Specials, Excludes>> : is_arithmetic<NumType> {};
}

This way, the user will never have to specialize std::numeric_limits ever again.

One final note, you can use preprocessor macros to make this even more easier to write:

#define NUMTYPE(type) NumWrapper<type>
#define TLOW(low) ::Low<low>::type
#define TMIN(min) ::Min<min>::type
#define TMAX(max) ::Max<max>::type
#define TDEF(def) ::Def<def>::type
#define TINV(inv) ::Inv<inv>::type
#define TINC(...) ::Inc<__VA_ARGS__>::type
#define TEXC(...) ::Exc<__VA_ARGS__>::type

typedef NUMTYPE(short)TMAX(9999)TDEF(1)TMIN(-10)TINC(2,3,5,7,11,13,17,19) MyIntegralType;

Almost lambdas in C99 – faking local variable capture

Function objects, and therefore lambdas, are not possible in C. However, if we think about one of the main benefits of lambdas – local variable capture – we can write both functions that can “capture” local variables, and functions that use those functions. Say for example you need to read from a socket. You can write the same socket reading routine each time, and handle all the errors and signals each time, handle the buffer management each time, or you can write a “generic” function that hides all the details:

int socket_read(int sock, bool (*func)(char*, ssize_t, va_list), ...)
{
    ssize_t rc = 1024;
    char buffer[rc];
    va_list args;
    va_start(args, func);
    while(!func(buffer, rc, args))
    {
        va_end(args);
        va_start(args, func);
        errno = 0;
        rc = recv(sock, buffer, sizeof(buffer), MSG_PEEK);
        if(rc > 0)
        {
            rc = recv(sock, buffer, rc, 0);
        }
        else if(rc == 0)
        {
            break;
        }
        else if(rc == -1 && errno != EAGAIN && errno != EWOULDBLOCK)
        {
            break;
        }
    }
    va_end(args);
    return rc;
}

Note that this function also takes care of the va_args initialization and cleanup, making client code safer.

An example usage would be to have separate functions that reads, for example, HTTP headers, and one that reads HTTP payload:

bool read_header(char* buf, ssize_t len, va_list args)
{
    ssize_t* hblen = va_arg(args, ssize_t*);
    ssize_t* hlen = va_arg(args, ssize_t*);
    char** headers = va_arg(args, char**);
    if(*hlen + len > *hblen)
    {
        if(!(*headers = (char*) realloc(*headers, *hlen + len)))  // Replace naive memory management algorithm with more efficient one
        {
            return true;
        }
        *hblen = *hlen + len;
    }
    memcpy(*headers + *hlen, buf, len);
    *hlen += len;
    return strstr(*headers, "rnrn") != NULL;
}

bool read_payload(char* buf, ssize_t len, va_list args)
{
    ssize_t* bytes_left = va_arg(args, ssize_t*);
    char** data = va_arg(args, char**);
    memcpy(*data, buf, len);
    *data += len;
    *bytes_left -= len;
    return bytes_left;
}

Note that the read_header function has its own buffer management due to the variable nature of HTTP headers, but the read_payload function doesn’t need to because it would be used to read fixed size data which would be provided by outside code.

Note also how each of the functions can virtually communicate with itself through the pointers passed into it via the va_list, even though it has no direct control of the socket_read loop.

Note that you should also be mindful of the order of the varargs. The rule of thumb is the put the most important and/or independent variables first. eg, sizes should always come before the buffer they limit.

Now you can read from a socket much more elegantly:

int main()
{
    int sock = socket(AF_INET, SOCK_STREAM, 0);

    // Set up socket
    // ...

    ssize_t hblen = 0;
    ssize_t hlen = 0;
    char* headers = NULL;  // For the purposes of this example, rely on realloc(NULL,size) behaviour. In real use, preallocate, and set hblen to size
    socket_read(sock, read_header, &hblen, &hlen, &headers);

    // Note that read_header may read more than just the header
    // so find rnrn, and copy the rest of the valid contents
    // into the following payload buffer
    // and adjust begin accordingly

    ssize_t clen /* = Find and interpret Content-Length header */;
    char payload[clen];
    char* begin = payload;
    socket_read(sock, read_payload, &clen, &begin);
    return 0;
}

Note how you’ve effectively locally captured variables from the calling function to be passed on to the delegate functions. Note that I also don’t clutter the calling function with memory management.

  • DISCLAIMER: I can vouch that the technique works, but since I rewrote code from scratch for this example and have not tested it due to time constraints, I cannot guarantee that the code works as is. It will need tweaking to get rid of bugs.

The Invalid Value constructor – a proposal

C++ has the concept of the default constructor. One is provided for you by the compiler under most common circumstances. What isn’t provided is the concept of a default constructor for an invalid value of the class. I propose the following convention for an invalid value constructor:

struct Value
{
    Value(std::nullptr_t) {std::cout << "Null constructor" << std::endl;}
    Value(void* v) {std::cout << "Null pointer constructor" << std::endl;}
};

int main()
{
    Value v{nullptr};
    return 0;
}

The output of this program is:

Null constructor

This works because nullptr on its own has the type of std::nullptr, and so overload resolution will choose the narrowest possible match, thus the constructor that takes the single argument of nullptr.

The Internals Pattern, or emulating Ada’s discriminated variant records

In C, unions are not typesafe and requires that the programmer be completely responsible with how the unions are used. Ada’s discriminated variant records are a typesafe way of doing unions and using the Internals pattern1 we can get the same functionality in C++. This is all the code that’s needed:

template<typename...>
struct Internals
{
    // Empty struct for the default case
};

Due to C++’s template instantiation rules, you can have different members of a class for any specialization of the template. In essence:

template<>
struct Internals<int>
{
    int int_data;  // Note that there is no requirement that the members are the same
};

template<>
struct Internals<std::string>
{
    std::string string_data;
};

template<>
struct Internals<int, int>
{
    std::tuple<int, int> int_tuple_data;
};

All of these structs are completely different types, even though they all come from the Internals templated type. They bear no relation to each other in the way inheritance would have done, and this is the main benefit. You can have compile-time polymorphism that is checked before you even run the code. This is now possible:

template<typename T, typename U, typename... Vs>
struct Scaffold
{
    Internals<Scaffold> internals;
    void print()
    {
        std::cout << "Default dummy data" << std::endl;
    }
};

template<>
struct Internals<Scaffold<int, float, char, double>>
{
    std::string data{"Specialized dummy data"};
};

template<>
void Scaffold<int, float, char, double>::print()
{
    std::cout << this->internals.data << std::endl;
}

int main()
{
    Scaffold<long, long>{}.print();
    Scaffold<int, float, char, double>{}.print();

    return 0;
}

The output of this program is:

Default dummy data
Specialized dummy data

This is a useful behaviour when you want something akin to aspects, or crosscutting concerns. Clients of your framework can specialize the internals without having to derive from any framework class, decoupling the framework scaffolding from the client.


  1. I have not found this pattern discussed anywhere and so do not know the correct name even if there is one