在C++模板生成的类层次结构中，通过参数类型匹配一个类

Question

简介

我正在开发一个自定义的内存分配器，需要在每个分配块的头部添加一些簿记信息。有几种不同的块类型，簿记信息也不同。例如，对于在线程之间共享的块，需要添加引用计数器；对于单个线程使用的块，没有这样的需要。对于从内存池中获取的块，需要保留对原始内存池的引用，而对于从自由存储区获取的块则没有这样的需要。

问题

因此，我希望有一个通用接口，可以为给定的块布局添加和获取某些数据类型。通过尝试这个想法，我得出了一个类似于 std::tuple 的解决方案。但与元组不同的是，我添加到头部的每种类型都将是唯一的。我刚开始学习模板元编程和 c++ 的其他复杂性，但添加类型的部分对我来说很直观。

我遇到的问题是实现类似于 C++14 的 std::get 模板函数的方法。我发现在方法调用中编译器能够匹配正确的基类，因此不需要编写太多代码。起初，我将 get 方法直接放入模板生成的布局类中。然而，在这种情况下，编译器无法匹配正确的类。通过将 get 方法移动到另一个手动添加的类层次结构中，问题得以解决。

下面的代码演示了这个问题。将 HAVE_GET_IN_LAYOUT 定义为 0 将产生一个可行的解决方案，而将其定义为 1 将产生一个错误的解决方案 [至少在 clang++ 3.5 和 3.6 中是如此]。

问题是，这种情况下有什么问题？

#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;
}

- Aleksey Demakov

---

为什么不简单地使用元组并进行一些模板递归呢？ - danielschemmel

@Jarod42 尽管不使用 clang - melak47

如果我简化get/helper的实现，使用类似于@gha.st所做的简单递归（如此），那么也没有问题。 - melak47

@gha.st使用元组在这里可能会节省一些输入，但是我的真实代码比上面的示例复杂得多，恐怕在其他情况下使用元组会使它更加困难或模糊。无论如何，这也是我学习现代C++的一种方式。 - Aleksey Demakov

一个简化的例子也重现了这个问题（http://coliru.stacked-crooked.com/a/cda7eb40c43120d0）。当非类型参数被移除时，clang++也接受了该程序（http://coliru.stacked-crooked.com/a/55a535803f69db0a）。 - dyp

Answer 1

看起来我的代码是完全合法的，问题可能出在clang++上。或者我可能滥用了一些未定义的C ++行为，但目前看来这种情况不太可能。如果有任何C ++语言律师能够纠正我，我将非常感激。

无论如何，最终我使用了自己的解决方法，并在查看了一些问题评论中提供的示例代码后进行了增强。

如果有人对使用所描述的技巧的真实代码感兴趣，我会在这里粘贴它。

// 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

现在来展示一下所有这些机器的样例用法：

#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;
}

- Aleksey Demakov