— Franz Kafka
In systems programming, ring buffers are ubiquitous. Like regular queues, they’re first-in first-out data structures but contrary to classic queues they’re fixed in size and don’t grow dynamically. This is especially important in real-time contexts where time and space determinism is paramount.
In today’s circular episode I want to show you my go-to ring buffer implementation. I like it, because it’s short and decently efficient. I deliberately used only basic C++ syntax, so it should compile fine with even compilers from the previous millennium (i. e. C++98):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
template<typename T, int N> class ring_buffer { public: ring_buffer() { clear(); } size_t capacity() const { return N; } bool empty() const { return head_ == tail_; } size_t size() const { return head_ >= tail_ ? head_ - tail_ : BUFSIZE - (tail_ - head_); } void add(const T& item) { buffer_[head_] = item; advance(head_); if (head_ == tail_) { advance(tail_); // Drop oldest entry, keep rest. } } const T& remove() { assert(!empty()); size_t old_tail = tail_; advance(tail_); return buffer_[old_tail]; } void clear() { tail_ = head_ = 0U; } private: static const size_t BUFSIZE = N + 1U; void advance(size_t& value) { value = (value + 1) % BUFSIZE; } T buffer_[BUFSIZE]; size_t head_; size_t tail_; }; |
You can specify the data type of ring buffer elements via template parameter T and the total number of elements to track via template parameter N, respectively. Here’s a little usage scenario:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
ring_buffer<int, 10> rb; assert(rb.capacity() == 10); rb.add(123); rb.add(42); rb.add(23); assert(rb.size() == 3); while (!rb.empty()) { cout << rb.remove() << endl; } assert(rb.size() == 0); |
A common problem that you face when implementing a ring buffer is discriminating between empty and full states, as in both cases the head and tail index point to the same location. I solved it by allocating one extra element, which might waste a little bit of space but makes the code easier on the eye and probably faster compared to the alternative approach which requires you have to maintain an extra boolean flag.
When the buffer becomes full during an add operation (head == tail), the tail index is immediately advanced by one, thus dropping the oldest element. As this all happens within the add method, from a ring_buffer user’s point of view the head index is only ever equal to the tail index when the ring buffer is empty.
Contemporary compilers will replace the potentially costly modulo operation in the advance helper method with an AND operation for buffer sizes that are base-2 numbers. However, keep in mind that the advance method uses the internal buffer size (BUFSIZE), which is one greater than the requested ring buffer size (N), so this is most likely an efficient ring buffer:
|
1 2 3 4 |
ring_buffer<double, 15> rb; // Internal buffer has 16 entries. // index % 16 reduced to index & 15. |
while this isn’t:
|
1 2 3 |
ring_buffer<double, 16> rb; // Internal buffer with 17 entries. |
[Update 2020-05-29: Part VIII of this series shows how to optimize/simplify ring_buffer::size().]