Match a class by parameter type in a c++ template-generated class hierarchy

Question

Intro

I am working on a custom memory allocator and need to add some bookkeeping info to the header of each allocated chunk. There are several different chunk types and the bookkeeping info differs as well. For instance, for chunks shared between threads there is a need to add a reference counter, for chunks used by single thread there is no such need. For chunks taken from a memory pool there is a need to keep a reference to the originating pool, for chunks taken from the free store there is no such need.

Problem

So I would like to have a generic interface to add and get certain data types for a given chunk layout. Experimenting with this idea I came to a solution that is similar to std::tuple. However unlike tuples every type I add to the header is going to be unique. I just started to learn template meta-programming and other intricacies of c++, however the part with adding a type was straightforward for me.

The problem I came across is implementing a method similar to C++14 std::get by type template function for tuples. I figured there is no need to write much code for this as the compiler is able to match the correct base class in a method call. At first I put the get method right into template-generated layout class. However the compiler fails to match the correct class in this case. The problem was solved by moving the get method to another, manually added, level of class hierarchy.

The code below demonstrates the problem. Defining HAVE_GET_IN_LAYOUT to 0 produces a working solution while defining it to 1 produces a broken solution [at least with clang++ 3.5 and 3.6]

The question is, what is broken in this case?

#include <cstddef>
#include <iostream>

#ifndef HAVE_GET_IN_LAYOUT
#define HAVE_GET_IN_LAYOUT 0
#endif

constexpr std::size_t Align(std::size_t size, std::size_t offset) {
  return (size < 0x8
              ? (offset + 0x3) & ~0x3
              : (size < 0x10 ? (offset + 0x7) & ~0x7 : (offset + 0xf) & ~0xf));
}

template <std::size_t Start, typename... Ts> struct Layout {
  static constexpr std::size_t Size = 0;
  static constexpr std::size_t Offset = Start;
  static constexpr std::size_t TotalSize = Start;
};

template <std::size_t Start, typename T, typename... Ts>
struct Layout<Start, T, Ts...>
    : public Layout<Align(sizeof(T), Start) + sizeof(T), Ts...> {
  using Type = T;

  static constexpr std::size_t Size = sizeof(Type);
  static constexpr std::size_t Offset = Align(Size, Start);
  static constexpr std::size_t TotalSize = Layout<Offset + Size, Ts...>::TotalSize;

  Type value = Offset - Start; // no particular meaning, just for testing.

#if HAVE_GET_IN_LAYOUT
  template <typename U, std::size_t X, typename... Us>
  U &helper(Layout<X, U, Us...> *c) { return c->value; }

  template <typename U> U &get() { return helper<U>(this); }
#endif
};

template <typename... Ts> struct Result : public Layout<0, Ts...> {
#if !HAVE_GET_IN_LAYOUT
  template <typename U, std::size_t X, typename... Us>
  U &helper(Layout<X, U, Us...> *c) { return c->value; }

  template <typename U> U &get() { return helper<U>(this); }
#endif
};

int main() {
  std::cout << "layout size <> = " << Layout<0>::TotalSize << std::endl;
  std::cout << "layout size <int> = " << Layout<0, int>::TotalSize << std::endl;
  std::cout << "layout size <long> = " << Layout<0, long>::TotalSize << std::endl;
  std::cout << "layout size <int,int> = " << Layout<0, int, int>::TotalSize << std::endl;
  std::cout << "layout size <int,long> = " << Layout<0, int, long>::TotalSize << std::endl;
  std::cout << "layout size <long,int> = " << Layout<0, long, int>::TotalSize << std::endl;
  std::cout << "layout size <long,long> = " << Layout<0, long, long>::TotalSize << std::endl;

  std::cout << "get: " << Result<int, long, long double>{}.get<long>() << std::endl;

  return 0;
}

Answer 1

So it looks like my code was perfectly legal, it is rather some clang++ problem. Alternatively I might be abusing some not well defined C++ behaviour. But this looks unlikely so far. If any C++ language lawyer could correct me, I would greatly appreciate this.

Anyway, I ended up with using my workaround which I enhanced after looking at some of the sample code provided at the question comments.

If anyone is interested how the real code using the described trick looks like, I'm pasting it here.

// Round down to a power of two multiple.
constexpr std::size_t Align(std::size_t n, std::size_t a) {
  return n & ~(a - 1);
}

// Round up to a power of two multiple.
constexpr std::size_t AlignUp(std::size_t n, std::size_t a) {
  return Align(n + a - 1, a);
}

namespace memory {
namespace detail {

// Calculate a data item alignment according to its size.
constexpr std::size_t Align(std::size_t size, std::size_t offset) {
  return size < 0x08 ? ::AlignUp(offset, 0x04)
                     : size < 0x10 ? ::AlignUp(offset, 0x08)
                                   : ::AlignUp(offset, 0x10);
}

// Services for placement of a given type instance within a memory chunk
// at the specified offset.
template <typename T, std::size_t S> class EntryLayout {
public:
  using Type = T;
  using Pointer = T *;

  static constexpr std::size_t Size = sizeof(Type);
  static constexpr std::size_t Offset = Align(Size, S);
  static constexpr std::size_t EndOffset = Offset + Size;

  static Pointer Instance(char *ptr) {
    return reinterpret_cast<Pointer>(RawData(ptr));
  }

  template <typename... Args>
  static Pointer Construct(char *ptr, Args &&... args) {
    return new (RawData(ptr)) Type(std::forward<Args>(args)...);
  }

  static void Destruct(char *ptr) { Instance(ptr)->~Type(); }

private:
  static char *RawData(char *ptr) { return ptr + Offset; }
};

// Services for placement of a number of types within a memory
// chunk at the specified offset.
template <std::size_t S, typename... Tail> class ChunkLayout {
public:
  static constexpr std::size_t StartOffset = S;
  static constexpr std::size_t EndOffset = S;

  template <typename... Args> static void Construct(char *, Args...) {}

  static void Destruct(char *) {}
};

// Recursive template specialization of the above.
template <std::size_t S, typename Head, typename... Tail>
class ChunkLayout<S, Head, Tail...>
    : public ChunkLayout<EntryLayout<Head, S>::EndOffset, Tail...> {
public:
  using EntryType = Head;
  using HeadLayout = EntryLayout<Head, S>;
  using TailLayout = ChunkLayout<HeadLayout::EndOffset, Tail...>;

  static constexpr std::size_t StartOffset = S;
  static constexpr std::size_t EndOffset = TailLayout::EndOffset;

  static typename HeadLayout::Pointer Instance(char *ptr) {
    return HeadLayout::Instance(ptr);
  }

  template <typename... Args> void Construct(char *ptr, Args... args) {
    HeadLayout::Construct(ptr, args...);
    TailLayout::Construct(ptr, args...);
  }

  void Destruct(char *ptr) {
    TailLayout::Destruct(ptr);
    HeadLayout::Destruct(ptr);
  }
};

} // namespace detail

// Control of memory chunk free and used space.
class ChunkSpace {
public:
  ChunkSpace(std::size_t size) noexcept : free_{size}, used_(0) {}

  std::size_t Used() const { return used_; }
  std::size_t Free() const { return free_; }
  std::size_t Size() const { return free_ + used_; }

  bool Alloc(std::size_t size) {
    if (size > free_)
      return false;
    free_ -= size;
    used_ += size;
    return true;
  }

  void Reset(std::size_t size = 0) {
    assert(size <= used_);
    free_ = free_ + used_ - size;
    used_ = size;
  }

private:
  std::size_t free_;
  std::size_t used_;
};

template <typename... EntryType>
class Chunk : public detail::ChunkLayout<0, ChunkSpace, EntryType...> {
  using Layout = detail::ChunkLayout<0, ChunkSpace, EntryType...>;

public:
  Chunk(char *data, std::size_t size) : data_{data} {
    assert(size > Layout::EndOffset);

    // Construct ChunkSpace instance to bootstrap allocation.
    Layout::HeadLayout::Construct(data_, size);
    // Allocate space required for all the chunk data.
    Alloc(Layout::EndOffset);
    // Construct the rest of the chunk data.
    Layout::TailLayout::Construct(data_);
  }

  ~Chunk() {
    Layout::Destruct(data_);
  }

  template <typename T>
  T* Get() {
    return decltype(Upcast<T>(this))::Instance(data_);
  }

  template <typename T>
  const T* Get() const {
    return decltype(Upcast<T>(this))::Instance(data_);
  }

  std::size_t Used() const { return Get<ChunkSpace>()->Used(); }
  std::size_t Free() const { return Get<ChunkSpace>()->Free(); }
  std::size_t Size() const { return Get<ChunkSpace>()->Size(); }

  void *Allocate(std::size_t size) {
    std::size_t offset = Used();
    std::size_t aligned_offset = detail::Align(size, offset);
    std::size_t offset_padding = aligned_offset - offset;
    if (!Alloc(size + offset_padding))
      return nullptr;
    return data_ + aligned_offset;
  }

private:
  bool Alloc(std::size_t size) {
    return Get<ChunkSpace>()->Alloc(size);
  }

  // Some C++ magic to upcast to the base class that contains layout info
  // for a given entry type.
  template <typename Head, std::size_t S, typename... Tail>
  static typename detail::ChunkLayout<S, Head, Tail...>::HeadLayout
  Upcast(const detail::ChunkLayout<S, Head, Tail...> *);

  char *data_;
};

} // namespace memory

And now a sample use of all this machinery:

#include "chunk.h"
#include "iostream"

struct A {
  int value = 0xa;
};

struct B {
  int value = 0xb;
};

void alloc(memory::Chunk<A, B> &chunk, std::size_t size)
{
  chunk.Allocate(size);
  std::cout << "Allocate " << size << " bytes:" << std::endl;
  std::cout << "  used: " << chunk.Used() << std::endl;
  std::cout << "  free: " << chunk.Free() << std::endl;
}

int main()
{
  char buffer[1024];

  memory::Chunk<A, B> chunk(buffer, sizeof buffer);
  std::cout << "used: " << chunk.Used() << std::endl;
  std::cout << "free: " << chunk.Free() << std::endl;

  A *a = chunk.Get<A>();
  B *b = chunk.Get<B>();
  std::cout << std::hex;
  std::cout << "a: " << a->value << " b: " << b->value << std::endl;
  std::cout << std::dec;

  alloc(chunk, 1);
  alloc(chunk, 2);
  alloc(chunk, 4);
  alloc(chunk, 8);
  alloc(chunk, 16);

  return 0;
}