A fast polymorphic object queue.

poly-queue.hpp

#ifndef SF_POLY_QUEUE_H_
#define SF_POLY_QUEUE_H_

#include <stdexcept>
#include <iostream>
#include <stdint.h>
#include <type_traits>

namespace sf {

template<size_t SegSize> struct Segment
{
  Segment<SegSize> *next = nullptr;
  size_t len = 0;
  size_t off = 0;
  uintptr_t data[SegSize];
  size_t pos(size_t add=0) const
  {
    return (off+len+add) % SegSize;    
  }
};

template<typename ObjTy, size_t SegSize=32>
class PolymorphicQueue
{
  typedef Segment<SegSize> SegTy;
public:
  PolymorphicQueue()
  :head(new SegTy())
  ,tail(head)
  ,count(0)
  {
  }
  ~PolymorphicQueue()
  {
    for (auto node = head; node; ) {
      auto next = node->next;
      delete node;
      node = next;
    }
    head = nullptr;
    tail = nullptr;
  }

  template<typename SubTy, typename ...Args>
  SubTy &emplace_back(Args &&...args)
  {
    constexpr auto amount = (sizeof(SubTy) + sizeof(void*) - 1) / sizeof(void*) + 1;

    static_assert(amount <= SegSize, "SubTy is too lerge.");
    static_assert(std::is_base_of<ObjTy,SubTy>::value, "SubTy is not subtype of ObjTy.");

    auto padding = SegSize - tail->pos();
    if (padding < (std::min)
      (SegSize - tail->len, amount))
    {
      tail->data[tail->pos()] = 1 | (padding << 1);
      tail->len += padding;
    }
    if (amount > SegSize - tail->len) {
      tail = tail->next = new SegTy();
    }

    auto obj = new (reinterpret_cast<void*>
      (tail->data + tail->pos(1))) SubTy(std::forward<Args>(args)...);

    tail->data[tail->pos()] = 0 | (amount << 1);
    tail->len += amount;
    ++ count;
    return *obj;
  }

  ObjTy &pop_front()
  {
    for (;;) {
      while (head->len == 0) {
        auto next = head->next;
        if (!next) {
          throw std::logic_error("No entry.");
        }
        delete head;
        head = next;
      }
      auto offset = head->off;
      auto amount = head->data[offset];
      head->len -= (amount >> 1);
      head->off += (amount >> 1);
      head->off %= SegSize;
      if ((amount & 1) == 0) {
        -- count;
        return *reinterpret_cast<ObjTy*>(head->data+offset+1);
      }
    }
  }

  size_t size() const { return count; }

  void dump(std::ostream &os) const
  {
    os << "PolymorphicQueue(" << SegSize << "){nodes:[";
    for (auto node = head; node; node = node->next) {
      os
      << "{off:" << node->off
      << ",len:" << node->len
      << ",data:["
      ;
      auto off = node->off;
      auto len = node->len;
      while (len != 0) {
        auto amount = node->data[off];
        os << (amount & 1 ? "padding": "item") << "(" << off << ":" << (amount >> 1) << ");";
        len -= (amount >> 1);
        off += (amount >> 1);
        off %= SegSize;
      }
      os << "]};";
    }
    os << "]}";
  }

private:
  SegTy *head;
  SegTy *tail;
  size_t count;
};

} // namespace
#endif

test-poly-queue.cpp

#include <gtest/gtest.h>
#include "poly-queue.hpp"

namespace {

class A
{
public:
  A(const char *name)
  :name(name)
  {}
  virtual ~A() {}
  const char *name;
};

class B: public A
{
public:
  B(const char *name, const char *job)
  :A(name), job(job) {}
  const char *job;
};

template<typename Ty, size_t N>
std::string to_str(const sf::PolymorphicQueue<Ty,N> &q)
{
  std::ostringstream oss;
  q.dump(oss);
  return oss.str();
}
} // namespace

using namespace sf;

TEST(PolymorphicQueueTest, new) {
  PolymorphicQueue<A> q;
  EXPECT_EQ("PolymorphicQueue(32){nodes:[{off:0,len:0,data:[]};]}", to_str(q));
  EXPECT_EQ(0, q.size());
}

static_assert(sizeof(A) == (1 + 1 /* tbl */) * sizeof(void*), "omg");
static_assert(sizeof(B) == (2 + 1 /* tbl */) * sizeof(void*), "omg");

TEST(PolymorphicQueueTest, emplace_back) {

  PolymorphicQueue<A> q;

  q.emplace_back<A>("John");
  EXPECT_EQ(1, q.size());
  EXPECT_EQ("PolymorphicQueue(32)"
    "{nodes:[{off:0,len:3,data:["
      "item(0:3);"
    "]};]}", to_str(q));

  q.emplace_back<B>("Tom", "Software Engineer");
  EXPECT_EQ(2, q.size());
  EXPECT_EQ("PolymorphicQueue(32)"
    "{nodes:[{off:0,len:7,data:["
      "item(0:3);"
      "item(3:4);"
    "]};]}", to_str(q));
}

TEST(PolymorphicQueueTest, pop_front) {

  PolymorphicQueue<A> q;

  q.emplace_back<A>("John");
  q.emplace_back<B>("Tom", "Software Engineer");
  q.emplace_back<B>("Bob", "Chief Technical Officer");

  {
    auto &e = q.pop_front();
    EXPECT_EQ(e.name, "John");
    EXPECT_EQ(2, q.size());
    EXPECT_EQ(nullptr, dynamic_cast<B*>(&e));
  }

  {
    auto &e = q.pop_front();
    EXPECT_EQ(e.name, "Tom");
    EXPECT_EQ(1, q.size());
    auto p = dynamic_cast<B*>(&e);
    ASSERT_NE(nullptr, p);
    ASSERT_EQ("Software Engineer", p->job);
  }

  {
    auto &e = q.pop_front();
    EXPECT_EQ(e.name, "Bob");
    EXPECT_EQ(0, q.size());
    auto p = dynamic_cast<B*>(&e);
    ASSERT_NE(nullptr, p);
    ASSERT_EQ("Chief Technical Officer", p->job);
  }

}

TEST(PolymorphicQueueTest, padding) {

  PolymorphicQueue<A,5> q;

  q.emplace_back<A>("John");
  q.pop_front();

  q.emplace_back<A>("Mary");
  EXPECT_EQ("PolymorphicQueue(5)"
    "{nodes:[{off:3,len:5,data:["
      "padding(3:2);"
      "item(0:3);"
    "]};]}", to_str(q));

  EXPECT_EQ("Mary", q.pop_front().name);
  EXPECT_EQ("PolymorphicQueue(5)"
    "{nodes:[{off:3,len:0,data:[]};]}", to_str(q));

}

TEST(PolymorphicQueueTest, segment) {

  PolymorphicQueue<A,5> q;

  q.emplace_back<B>("Tom", "Software Engineer");
  EXPECT_EQ("PolymorphicQueue(5)"
    "{nodes:["
      "{off:0,len:4,data:["
        "item(0:4);"
      "]};"
    "]}", to_str(q));

  q.emplace_back<B>("Bob", "Chief Technical Officer");
  EXPECT_EQ("PolymorphicQueue(5)"
    "{nodes:["
      "{off:0,len:4,data:["
        "item(0:4);"
      "]};"
      "{off:0,len:4,data:["
        "item(0:4);"
      "]};"
    "]}", to_str(q));

  EXPECT_EQ( "Tom", q.pop_front().name);
  EXPECT_EQ("PolymorphicQueue(5)"
    "{nodes:["
      "{off:4,len:0,data:[]};"
      "{off:0,len:4,data:["
        "item(0:4);"
      "]};"
    "]}", to_str(q));

  EXPECT_EQ( "Bob", q.pop_front().name);
  EXPECT_EQ("PolymorphicQueue(5)"
    "{nodes:["
      "{off:4,len:0,data:[]};"
    "]}", to_str(q));

}