A circular buffer, also known as cyclic buffer or ring buffer is a special data structure that uses a single, fixed-size buffer as if it were connected end-to-end. That is, if you reach writing to the last available slot in the buffer, the next slot to write into is the first slot of the buffer. You can find the gereric version here
The following code is a sample implementation of that structure. You can freely use them if you need to. The code standard I am trying to follow is Google's C++ Style.
The header file:
circular_buffer.hpp
The following code is a sample implementation of that structure. You can freely use them if you need to. The code standard I am trying to follow is Google's C++ Style.
The header file:
circular_buffer.hpp
#ifndef MCP_CIRCULAR_BUFFER_H_ #define MCP_CIRCULAR_BUFFER_H_ namespace base { // This is a fixed-size, circular buffer of integer. // The class is not thread-safe, class CircularBuffer { public: // Creates a buffer with 'slots' slots. explicit CircularBuffer(int slots); // Destructor. ~CircularBuffer(); // Writes 'value' to the next available slot. It may overwrite // values that were not yet read out of the buffer. void write(int value); // Returns the next value available for reading, in the order they // were written, and marks slot as read. If the buffer is empty returns -1. int read(); // Removes all the elements from the buffer. void clear(); private: //array of integers int* data_; // the size of the buffer int num_of_slots_; //index to read the next integer from buffer int read_index_; //index to write a new integer to buffer int write_index_; // Non-copyable, non-assignable. CircularBuffer(CircularBuffer&); CircularBuffer& operator=(const CircularBuffer&); }; } // namespace base #endif // MCP_CIRCULAR_BUFFER_H_
circular_buffer.cpp
#include "circular_buffer.hpp" namespace base { CircularBuffer::CircularBuffer(int slots) { if (slots <= 0) { num_of_slots_ = 10; /*pre-assigned value */ } else { num_of_slots_ = slots; } clear(); } CircularBuffer::~CircularBuffer() { delete[] data_; } void CircularBuffer::write(int value) { data_[write_index_] = value; if (read_index_ == -1) { //if buffer is empty, set the read index to the //current write index. because that will be the first //slot to be read later. read_index_ = write_index_; } write_index_ = (write_index_ + 1) % num_of_slots_; } int CircularBuffer::read() { if (read_index_ == -1) { // buffer empty return -1; } int ret_val = data_[read_index_]; read_index_ = (read_index_ + 1) % num_of_slots_; if (read_index_ == write_index_) { /*all available data is read, now buffer is empty*/ read_index_ = -1; } return ret_val; } void CircularBuffer::clear() { read_index_ = -1; /* buffer empty */ write_index_ = 0; /* first time writing to that buffer*/ delete [] data_; data_ = new int[num_of_slots_]; /* allocate space for buffer */ } } // namespace base
Is this the full implementation? My copy of circular_buffer.cpp stops at line 51.
ReplyDeleteIn line 33 of circular_buffer.h you declare
int num_of_slots_writable_;
I cant see it being referenced anywhere?
I used to use it in the previous implementation of CB. After revising the code, I recognized that it was an unnecessary field. I thought I had deleted it, thanks for stating that. I am updating the code.
DeleteMahir,
DeleteIt's me Mr Anonymous again thanks for responding to my question and thanks for putting the example up in the first place. I am now using it to process a circular buffer of unsigned char's. Thanks for the help.
Johan
you're welcome Johan.
DeleteYou can add or remove functions depending on your need ;)
ReplyDeleteGreat example helped me a ton!!
ReplyDeleteI am glad to hear that :)
Deleteyou have to add in the constructor
ReplyDeletedata_ = new int[num_of_slots_]; /* allocate space for buffer */
constructor calls the clear function which already has the initialization.
DeleteWith 'write_index_ = (write_index_ + 1) % num_of_slots_; '
ReplyDeletesimply overwrites data if there is no read.
So better to put a check before data_[write_index_] = value;
like if (write_index_ == read_index_) return;
else data_[write_index_] = value;
or
we may write a Check_buffer_full method to verify buffer occupancy and accordingly call write.
Just a thought :)
The nature of the circular buffer allows overwriting oldest data. If that is not what you want, then you can surely inject a protection mechanism ;)
DeleteHi,
ReplyDeleteThis is ok but could be more useful with templates (e.g. template). And C type of arrays are really so last season :).
-Mzkysti
It is easy to implement I ll put one as soon as I find time
DeleteHi Mahir
ReplyDeleteI want to save a structure like AVframe in circular buffer. I have tried but not success.
Is it possible ?
Asaf