Implementation of fixed size queue using a ring (cyclic) buffer

Question

I found myself in need of a fixed size queue and decided to implement one using a ring (cyclic) buffer.

I have tried my best to match the API of std::queue with the addition of full() to test if the queue is full and unable to accept another element.

The code compiles cleanly with: -Wall -Wextra -pedantic --std=c++14 -lgtest -lgtest_main, it runs and all tests pass on clang 3.9.1. Unfortunately at least GCC 4.9.4 and below cannot compile the header file due to a bug where a noexcept specification can't refer to a member.

All comments welcome.

File: xtd/fixed_queue.hpp

#ifndef GUARD_INCLUDE_XTD_FIXED_QUEUE_HPP
#define GUARD_INCLUDE_XTD_FIXED_QUEUE_HPP

#include <array>
#include <cstdint>
#include <stdexcept>

namespace xtd {

  template <typename T, std::size_t N>
  class fixed_queue {
  public:
    using value_type = T;
    using reference = value_type&;
    using const_reference = const value_type&;
    using size_type = std::size_t;

    fixed_queue() = default;
    fixed_queue(const fixed_queue& other) { *this = other; }
    fixed_queue(fixed_queue&& other) { *this = std::move(other); }
    ~fixed_queue() { clear(); }

    fixed_queue& operator=(const fixed_queue& other) {
      clear();

      auto i = other.m_read_idx;
      while (i != other.m_write_idx) {
        emplace(*other.get(i));
        i = other.increment_index(i);
      }
      return *this;
    }

    fixed_queue& operator=(fixed_queue&& other) {
      clear();
      while (!other.empty()) {
        emplace(std::move(other.front()));
        other.pop();
      }
      return *this;
    }

    size_type capacity() const { return N; }

    size_type size() const {
      if (empty()) {
        return 0;
      } else if (m_write_idx > m_read_idx) {
        return m_write_idx - m_read_idx;
      } else {
        return N - m_read_idx + m_write_idx + 1;
      }
    }

    void clear() {
      while (!empty()) {
        pop();
      }
    }

    bool full() const { return size() == capacity(); }

    bool empty() const { return m_write_idx == m_read_idx; }

    reference front() { return const_cast<reference>(cthis()->front()); }
    const_reference front() const {
      assert_not_empty("Cannot peek an empty queue!");
      return *get(m_read_idx);
    }

    void pop() {
      assert_not_empty("Cannot pop an empty queue!");
      auto old_idx = m_read_idx;
      m_read_idx = increment_index(m_read_idx);
      get(old_idx)->~value_type();
    }

    void swap(fixed_queue<T, N>& other) noexcept(noexcept(swap(this->m_data, other.m_data))) {
      using std::swap;
      swap(m_data, other.m_data);
      swap(m_write_idx, other.m_write_idx);
      swap(m_read_idx, other.m_read_idx);
    }

    template <typename... Args>
    void emplace(Args&&... args) {
      assert_not_full("Cannot push to a full queue!");
      new (get(m_write_idx)) value_type(std::forward<Args>(args)...);
      m_write_idx = increment_index(m_write_idx);
    }

  private:
    // We add one to the capacity, this avoids the problem that:
    // read_idx == write_idx on both an empty and a full queue.
    // We will never get "truly full" as there will always be one
    // extra space.
    alignas(value_type) std::array<uint8_t, sizeof(value_type) * (N + 1)> m_data;
    size_type m_write_idx = 0;
    size_type m_read_idx = 0;

    auto cthis() const { return const_cast<const fixed_queue<T, N>*>(this); }

    auto assert_not_empty(const char* message) const {
      if (empty()) {
        throw std::runtime_error(message);
      }
    }

    auto assert_not_full(const char* message) const {
      if (full()) {
        throw std::runtime_error(message);
      }
    }

    auto increment_index(size_type i) const { return (i + 1) % (N + 1); }

    auto get(size_type i) { return const_cast<value_type*>(cthis()->get(i)); }
    auto get(size_type i) const { return reinterpret_cast<const value_type*>(m_data.data()) + i; }
  };

  template <typename T, std::size_t N>
  void swap(fixed_queue<T, N>& a, fixed_queue<T, N>& b) noexcept(noexcept(a.swap(b))) {
    a.swap(b);
  }
}

#endif

File: test/fixed_queue.cpp

#include "xtd/fixed_queue.hpp"

#include <gtest/gtest.h>
#include <ostream>

std::ostream& operator<<(std::ostream& os, const std::vector<std::string>& v) {
  os << "[";
  auto first = true;
  for (auto& x : v) {
    if (!first) {
      os << ", ";
    }
    first = false;
    os << x;
  }
  os << "]";
  return os;
}

namespace xtd {
  std::vector<std::string> destructorCalls;
  std::vector<std::string> constructorCalls;
  std::vector<std::string> copyConstructorCalls;
  std::vector<std::string> moveConstructorCalls;

  class TestClass {
  public:
    TestClass(const std::string& name) : m_name(name) { constructorCalls.emplace_back(m_name); }
    TestClass(TestClass&& other) : m_name(std::move(other.m_name)) {
      other.m_name = "--MOVED--";
      moveConstructorCalls.emplace_back(m_name);
    }
    TestClass(const TestClass& other) : m_name(other.m_name) {
      copyConstructorCalls.emplace_back(m_name);
    }
    ~TestClass() { destructorCalls.emplace_back(m_name); }

    bool operator==(const TestClass& other) const { return m_name == other.m_name; }

    const std::string& name() const { return m_name; }

  private:
    std::string m_name;
  };

  class fixed_queue_test : public ::testing::Test {
  protected:
    virtual void SetUp() {
      constructorCalls.clear();
      copyConstructorCalls.clear();
      moveConstructorCalls.clear();
      destructorCalls.clear();
    }
    virtual void TearDown() {}
  };

  TEST_F(fixed_queue_test, CopyAssignmentWithComplexObject) {
    auto cut = fixed_queue<TestClass, 3>();

    // Create a test case that is partially wrapped around.
    cut.emplace("foo");  // index 0
    cut.pop();
    cut.emplace("bar");  // 1
    cut.pop();
    cut.emplace("baz");  // 2
    cut.emplace("boz");  // index 0

    auto copy = fixed_queue<TestClass, 3>();
    copy.emplace("beef"); // make sure old data is cleared
    copy = cut; 

    ASSERT_EQ(cut.size(), copy.size());
    ASSERT_EQ(cut.front().name(), copy.front().name());
    ASSERT_EQ(0, moveConstructorCalls.size());
    ASSERT_EQ(5, constructorCalls.size());
    ASSERT_EQ(2, copyConstructorCalls.size());
    ASSERT_EQ(3, destructorCalls.size());

    ASSERT_EQ("baz", copyConstructorCalls[0]);
    ASSERT_EQ("boz", copyConstructorCalls[1]);
  }

  TEST_F(fixed_queue_test, MoveAssignmentWithComplexObject) {
    auto cut = fixed_queue<TestClass, 32>();

    cut.emplace("foo");
    cut.emplace("bar");
    cut.emplace("baz");
    cut.pop();

    auto copy = fixed_queue<TestClass, 32>();
    copy.emplace("beef");

    copy = std::move(cut);

    ASSERT_EQ(2, copy.size());
    ASSERT_EQ("bar", copy.front().name());
    // std::cout<<moveConstructorCalls<<std::endl;
    ASSERT_EQ(2, moveConstructorCalls.size());
    ASSERT_EQ(4, constructorCalls.size());
    ASSERT_EQ(4, destructorCalls.size());

    ASSERT_EQ("bar", moveConstructorCalls[0]);
    ASSERT_EQ("baz", moveConstructorCalls[1]);

    ASSERT_EQ("foo", constructorCalls[0]);
    ASSERT_EQ("bar", constructorCalls[1]);
    ASSERT_EQ("baz", constructorCalls[2]);
    ASSERT_EQ("beef", constructorCalls[3]);

    ASSERT_EQ("foo", destructorCalls[0]);
    ASSERT_EQ("beef", destructorCalls[1]);
    ASSERT_EQ("--MOVED--", destructorCalls[2]);
    ASSERT_EQ("--MOVED--", destructorCalls[3]);
  }

  TEST_F(fixed_queue_test, EmplacePopWithComplexObject) {
    auto cut = fixed_queue<TestClass, 32>();

    ASSERT_TRUE(constructorCalls.empty());
    ASSERT_TRUE(destructorCalls.empty());

    cut.emplace("foo");

    ASSERT_EQ(1, constructorCalls.size());
    ASSERT_EQ("foo", constructorCalls[0]);
    ASSERT_TRUE(destructorCalls.empty());

    cut.emplace("bar");
    cut.emplace("baz");
    cut.pop();

    ASSERT_EQ(3, constructorCalls.size());
    ASSERT_EQ("bar", constructorCalls[1]);
    ASSERT_EQ("baz", constructorCalls[2]);
    ASSERT_EQ(1, destructorCalls.size());
    ASSERT_EQ("foo", destructorCalls[0]);
  }

  TEST_F(fixed_queue_test, ClearWithComplexObject) {
    constructorCalls.clear();
    destructorCalls.clear();

    auto cut = fixed_queue<TestClass, 32>();

    cut.emplace("foo");
    cut.emplace("bar");
    cut.emplace("baz");
    cut.clear();

    ASSERT_TRUE(cut.empty());
    ASSERT_EQ(0, cut.size());
    ASSERT_EQ(3, constructorCalls.size());
    ASSERT_EQ("foo", constructorCalls[0]);
    ASSERT_EQ("bar", constructorCalls[1]);
    ASSERT_EQ("baz", constructorCalls[2]);
    ASSERT_EQ(constructorCalls, destructorCalls);
  }

  TEST_F(fixed_queue_test, DestructorWithComplexObject) {
    constructorCalls.clear();
    destructorCalls.clear();

    {
      auto cut = fixed_queue<TestClass, 32>();
      cut.emplace("foo");
      cut.emplace("bar");
      cut.emplace("baz");
    }

    ASSERT_EQ(3, constructorCalls.size());
    ASSERT_EQ("foo", constructorCalls[0]);
    ASSERT_EQ("bar", constructorCalls[1]);
    ASSERT_EQ("baz", constructorCalls[2]);
    ASSERT_EQ(constructorCalls, destructorCalls);
  }

  TEST_F(fixed_queue_test, DefaultConstructor) {
    auto cut = fixed_queue<int, 32>();
    ASSERT_EQ(32, cut.capacity());
    ASSERT_TRUE(cut.empty());
    ASSERT_FALSE(cut.full());
    ASSERT_EQ(0, cut.size());
  }

  TEST_F(fixed_queue_test, SimpleUsage) {
    auto cut = fixed_queue<int, 4>();

    cut.emplace(1);
    ASSERT_FALSE(cut.empty());

    cut.emplace(2);
    cut.emplace(3);
    cut.emplace(4);
    ASSERT_EQ(1, cut.front());
    ASSERT_EQ(4, cut.size());
    ASSERT_FALSE(cut.empty());
    ASSERT_TRUE(cut.full());
    ASSERT_EQ(4, cut.capacity());

    cut.pop();
    ASSERT_EQ(2, cut.front());
    ASSERT_EQ(3, cut.size());
    ASSERT_FALSE(cut.full());

    cut.pop();
    ASSERT_EQ(3, cut.front());
    ASSERT_EQ(2, cut.size());

    cut.pop();
    ASSERT_EQ(4, cut.front());
    ASSERT_EQ(1, cut.size());

    cut.pop();
    ASSERT_EQ(0, cut.size());
    ASSERT_TRUE(cut.empty());
  }

  TEST_F(fixed_queue_test, LoopingUsage) {
    const int capacity = 10;
    const int laps = 3;

    for (int window = 1; window <= capacity; ++window) {
      int counter = 0;
      auto cut = fixed_queue<int, capacity>();

      for (int i = 0; i < window; ++i) {
        cut.emplace(counter++);
      }

      try {
        for (int i = 0; i < capacity * laps; ++i) {
          std::string msg = "Window: " + std::to_string(window) + " i=" + std::to_string(i);
          ASSERT_EQ(counter - window, cut.front()) << msg;
          cut.pop();
          cut.emplace(counter++);
          ASSERT_EQ(window, cut.size()) << msg;
        }
      } catch (...) {
        std::cout << "Window: " << window << std::endl;
        throw;
      }
    }
  }
}

Answer 1

Non Standard Copy Semantics

Interested in why you chose to implement the copy constructor in terms of the copy assignment operator and not the other way around. Noting that the standard way to implement this is the copy and swap idiom (other way around).

I can see this is probably slightly more efficient. But is the decrease in readability worth it. Only you can answer that.

fixed_queue(const fixed_queue& other) { *this = other; }
fixed_queue& operator=(const fixed_queue& other) {
  clear();

  auto i = other.m_read_idx;
  while (i != other.m_write_idx) {
    emplace(*other.get(i));
    i = other.increment_index(i);
  }
  return *this;
}

The one issue I have with this is that it does not provide the strong exception guarantee and you can't fall back to the original state if something goes wrong.

Though this is correct. I don't like the copy constructor not explicitly initializing the members. Have to go check the rest of the code to make sure the members are initialized reeks of doing things in multiple places.

Move Semantics

The source of the move can be left in an undefined state (as long as it is valid).

I don't see the need to pop() values from the source object. just move them. Poping them adds extra work that is not required. The destructor when called when do all the cleanup required.

fixed_queue& operator=(fixed_queue&& other) {
  clear();
  while (!other.empty()) {
    emplace(std::move(other.front()));

    // Don't need this.
    // Though if you do remove this you need to change the above line
    // to get a reference to an internal member.
    other.pop();
  }
  return *this;
}

Alignment

Not 100% convinced this works.

alignas(value_type) std::array<uint8_t, sizeof(value_type) * (N + 1)> m_data;

You want the internals of the array (ie. the array members) to be aligned to value_type. This is technically aligning the array (not its members). I have not read up on the requirements of the array (so this may work) but this seems a bit doggy.

Just point this works because std::array is a special case (guaranteed to only have one element that aligns with the specified data type). In general aligning containers on their content data type may not work.

Initialization

size_type m_write_idx = 0;
size_type m_read_idx = 0;

I prefer the constructor to initialize members. It's easier to spot when things are missed. If you are going to initialize the members in the code then I prefer them near the construcors so that it is easy to spot.

Personally I lay my code out like this:

Class
    private   Variables
    public    Constructors/Assignment/Destructors

    public    methods
    protected methods
    private   methods

This way I can quickly see if the members have all been initialized.