Circular Buffer using C/C++

Refer to Ring buffer basics | Creating a Circular buffer in C and C + + | C language to create a Ring buffer (Ring buffer) – Circular buffer (Ring buffer) | Performance of a Circular Buffer vs. Vector, Deque, and List .

The white part holds data, the blue part is empty (overwritable), tail++ after reading get data from tail, head++ after writing put data from head to buffer.

C implementation

#include <iostream>
#include<stdlib.h>
#include<assert.h>
using namespace std;

// Opaque circular buffer structure
typedef struct circular_buf_t circular_buf_t;


// Handle type, the way users interact with the API
typedef circular_buf_t* cbuf_handle_t;


// The hidden definition of our circular buffer structure
struct circular_buf_t {
	uint8_t* buffer;
	size_t head;
	size_t tail;
	size_t max; //of the buffer
	bool full;
};


/// Pass in a storage buffer and size 
/// Returns a circular buffer handle
cbuf_handle_t circular_buf_init(uint8_t* buffer, size_t size);


cbuf_handle_t circular_buf_init(uint8_t* buffer, size_t size)
{
	assert(buffer && size);

	cbuf_handle_t cbuf = malloc(sizeof(circular_buf_t));
	assert(cbuf);

	cbuf->buffer = buffer;
	cbuf->max = size;
	circular_buf_reset(cbuf);

	assert(circular_buf_empty(cbuf));

	return cbuf;
}

/// Free a circular buffer structure.
/// Does not free data buffer; owner is responsible for that
void circular_buf_free(cbuf_handle_t cbuf);

void circular_buf_free(cbuf_handle_t cbuf)
{
	assert(cbuf);
	free(cbuf);
}

/// Reset the circular buffer to empty, head == tail
void circular_buf_reset(cbuf_handle_t cbuf);

void circular_buf_reset(cbuf_handle_t cbuf)
{
	assert(cbuf);

	cbuf->head = 0;
	cbuf->tail = 0;
	cbuf->full = false;
}

// Adding and Removing Data
static void advance_pointer(cbuf_handle_t cbuf)
{
	assert(cbuf);

	if (cbuf->full)
	{
		cbuf->tail = (cbuf->tail + 1) % cbuf->max;
	}

	cbuf->head = (cbuf->head + 1) % cbuf->max;
	cbuf->full = (cbuf->head == cbuf->tail);
}


static void retreat_pointer(cbuf_handle_t cbuf)
{
	assert(cbuf);

	cbuf->full = false;
	cbuf->tail = (cbuf->tail + 1) % cbuf->max;
}


/// Put version 1 continues to add data if the buffer is full
/// Old data is overwritten
void circular_buf_put(cbuf_handle_t cbuf, uint8_t data);

void circular_buf_put(cbuf_handle_t cbuf, uint8_t data)
{
	assert(cbuf && cbuf->buffer);

	cbuf->buffer[cbuf->head] = data;

	advance_pointer(cbuf);
}

/// Put Version 2 rejects new data if the buffer is full
/// Returns 0 on success, -1 if buffer is full
int circular_buf_put2(cbuf_handle_t cbuf, uint8_t data);

int circular_buf_put2(cbuf_handle_t cbuf, uint8_t data)
{
	int r = - 1;

	assert(cbuf && cbuf->buffer);

	if (!circular_buf_full(cbuf))
	{
		cbuf->buffer[cbuf->head] = data;
		advance_pointer(cbuf);
		r = 0;
	}

	return r;
}

/// Retrieve a value from the buffer
/// Returns 0 on success, -1 if the buffer is empty
int circular_buf_get(cbuf_handle_t cbuf, uint8_t* data);

int circular_buf_get(cbuf_handle_t cbuf, uint8_t* data)
{
	assert(cbuf && data && cbuf->buffer);

	int r = - 1;

	if (!circular_buf_empty(cbuf))
	{
		*data = cbuf->buffer[cbuf->tail];
		retreat_pointer(cbuf);

		r = 0;
	}

	return r;
}

/// Returns true if the buffer is empty
bool circular_buf_empty(cbuf_handle_t cbuf);

bool circular_buf_empty(cbuf_handle_t cbuf)
{
	assert(cbuf);

	return(! cbuf->full && (cbuf->head == cbuf->tail)); }/// Returns true if the buffer is full
bool circular_buf_full(cbuf_handle_t cbuf);

bool circular_buf_full(cbuf_handle_t cbuf)
{
	assert(cbuf);

	return cbuf->full;
}

/// Returns the maximum capacity of the buffer
size_t circular_buf_capacity(cbuf_handle_t cbuf);

size_t circular_buf_capacity(cbuf_handle_t cbuf)
{
	assert(cbuf);

	return cbuf->max;
}

/// Returns the current number of elements in the buffer
size_t circular_buf_size(cbuf_handle_t cbuf);

size_t circular_buf_size(cbuf_handle_t cbuf)
{
	assert(cbuf);

	size_t size = cbuf->max;

	// The current position of the "head" pointer (incremented when adding elements)
	// The current position of the "tail" pointer (incremented after reading the element)

	if(! cbuf->full) {if (cbuf->head >= cbuf->tail)
		{
			size = (cbuf->head - cbuf->tail);
		}
		else{ size = (cbuf->max + cbuf->head - cbuf->tail); }}return size;
}
Copy the code

C++ implementation

#include <iostream>
#include <memory>         // std::unique_ptr Defined in header <memory>
#include <thread>         // std::thread
#include <mutex>          // std::mutex, std::lock_guard
using namespace std;

template <class T>
class circular_buffer {
public:
	explicit circular_buffer(size_t size) :
		buf_(std::unique_ptr<T[]>(new T[size])),
		max_size_(size)
	{
		//empty constructor
	}

	void put(T item); // Adding Data
	T get(a); // Retrieving Data
	void reset(a);
	bool empty(a) const;
	bool full(a) const;
	size_t capacity(a) const;
	size_t size(a) const;

private:
	std::mutex mutex_;
	std::unique_ptr<T[]> buf_;
	size_t head_ = 0;
	size_t tail_ = 0;
	const size_t max_size_;
	bool full_ = 0;
};

template <class T>
bool circular_buffer<T>::empty(a)const
{
	//if head and tail are equal, we are empty
	return(! full_ && (head_ == tail_)); }template <class T>
bool circular_buffer<T>::full(a)const
{
	//If tail is ahead the head by 1, we are full
	return full_;
}


template <class T>
void circular_buffer<T>::reset()
{
	std::lock_guard<std::mutex> lock(mutex_);
	head_ = tail_;
	full_ = false;
}

template <class T>
size_t circular_buffer<T>::capacity(a)const
{
	return max_size_;
}


template <class T>
size_t circular_buffer<T>::size(a)const
{
	size_t size = max_size_;

	if(! full_) {if (head_ >= tail_)
		{
			size = head_ - tail_;
		}
		else{ size = max_size_ + head_ - tail_; }}return size;
}


template <class T>
void circular_buffer<T>::put(T item)
{
	std::lock_guard<std::mutex> lock(mutex_);

	buf_[head_] = item;

	if (full_)
	{
		tail_ = (tail_ + 1) % max_size_;
	}

	head_ = (head_ + 1) % max_size_;

	full_ = head_ == tail_; // C++ operator priority "==" > "="
}


template <class T>
T circular_buffer<T>::get()
{
	std::lock_guard<std::mutex> lock(mutex_);

	if (empty())
	{
		return T(a); }//Read data and advance the tail (we now have a free space)
	auto val = buf_[tail_];
	full_ = false;
	tail_ = (tail_ + 1) % max_size_;

	return val;
}

int main(a)
{
	// Here's an example using a buffer of 10 uint32_t entries:
	circular_buffer<uint32_t> circle(10);

	// Adding data is easy:
	uint32_t x = 100;
	circle.put(x);

	// And getting data is equally easy:
	x = circle.get(a); std::cout << x << endl; }Copy the code

Performance of a Circular Buffer

A sort of spec sheet for a circular buffer container class like boost::circular_buffer might look like this:

• Sequence container
• Insert or remove: from front or back O(1), from elsewhere O(n)
• Index time: by position, O(1)
• Sort: O(n log2 n).
• Search: O(log2 n) if sorted, else O(n)
• Iterators and references to an item are invalidated when the item is removed. Iterators and references to the item at one end of the circular buffer are invalidated when an item is inserted on the other end of the circular buffer, and the circular buffer is already full. All iterators and references are invalidated when the capacity is increased.
• Iterators are random-access iterators.
• Iterators produce items front-to-back or back-to-front.
• Fixed-capacity data structure