Skip to content

Instantly share code, notes, and snippets.

@rubenwardy

rubenwardy/ringbuffer.hpp Secret

Last active Feb 7, 2019
Embed
What would you like to do?
Simple RingBuffer
#pragma once
#include <vector>
namespace types {
template <typename T>
class RingBuffer
{
T empty_item;
std::vector<T> data;
int head = 0; // read
int tail = 0; // write
public:
RingBuffer<T>(int size, T empty_item):
empty_item(empty_item),
data(size + 1, empty_item)
{}
bool resize(int n)
{
if (n <= size())
return false;
// TODO: reduce copying here.
std::vector<T> data2(n + 1, empty_item);
T next = pop();
int i = 0;
while (next != empty_item) {
data2[i] = next;
i++;
next = pop();
}
data = data2;
head = 0;
tail = i;
return true;
}
void clear()
{
head = 0;
tail = 0;
}
bool empty() const
{
return tail == head;
}
int size() const
{
if (tail >= head)
return tail - head;
else
return data.size() - head + tail;
}
int max_size() const
{
return data.max_size() - 1;
}
int capacity() const
{
return data.size() - 1;
}
bool push(T item)
{
int next_tail = (tail + 1) % data.size();
if (next_tail == head)
return false;
data[tail] = item;
tail = next_tail;
return true;
}
T pop()
{
if (head == tail)
return empty_item;
T retval = data[head];
head = (head + 1) % data.size();
return retval;
}
T pop_front()
{
if (head == tail)
return empty_item;
tail--;
if (tail < 0)
tail = data.size() - 1;
T retval = data[tail];
return retval;
}
};
};
#pragma once
#include <sstream>
#include "../types/ring_buffer.hpp"
#include "../types.hpp"
#include "../vectors.hpp"
class RingBufferSizeTest : public AutoTest
{
public:
virtual bool setup()
{
return true;
}
virtual bool run()
{
// Basic pop/push
RingBuffer<int> buff(10, 0);
TEST(buff.size() == 0);
TEST(buff.capacity() == 10);
for (int i = 1; i < 50; i++) {
TEST(buff.push(i));
TEST(buff.size() == 1);
TEST(!buff.empty());
TEST(buff.pop() != 0);
TEST(buff.empty());
TEST(buff.size() == 0);
}
// Add ten items
for (int i = 0; i < 10; i++) {
TEST(buff.push(i + 1));
TEST(buff.size() == i + 1);
TEST(!buff.empty());
}
TEST(!buff.push(11));
TEST(buff.size() == 10);
TEST(!buff.resize(10));
TEST(!buff.resize(5));
TEST(buff.size() == 10);
// Resize to fit 20
TEST(buff.resize(20));
TEST(buff.size() == 10);
TEST(buff.capacity() == 20);
// Add ten more
for (int i = 10; i < 20; i++) {
TEST(buff.push(i + 1));
TEST(buff.size() == i + 1);
TEST(!buff.empty());
}
TEST(!buff.push(21));
TEST(buff.size() == 20);
// Check pop
for (int i = 0; i < 20; i++) {
TEST(buff.size() == 20 - i);
TEST(buff.pop() != 0);
TEST(buff.size() == 20 - i - 1);
}
TEST(buff.size() == 0);
TEST(buff.empty());
TEST(buff.capacity() == 20);
// Clear
buff.clear();
TEST(buff.size() == 0);
TEST(buff.empty());
TEST(buff.capacity() == 20);
for (int i = 1; i < 50; i++) {
TEST(buff.push(i));
TEST(buff.size() == 1);
TEST(buff.pop() != 0);
TEST(buff.size() == 0);
}
TEST(buff.empty());
TEST(buff.capacity() == 20);
for (int i = 0; i < 20; i++) {
TEST(buff.push(i + 1));
TEST(buff.size() == i + 1);
}
for (int i = 0; i < 20; i++) {
TEST(buff.size() == 20 - i);
TEST(buff.pop_front() == 20 - i);
TEST(buff.size() == 20 - i - 1);
}
TEST(buff.size() == 0);
return true;
}
virtual void teardown()
{}
};
bool do_ringbuffer_tests()
{
bool passed = true;
passed = do_test("RingBufferSizeTest", new RingBufferSizeTest()) && passed;
return passed;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment