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