Home | Projects | Notes > Data Structures & Algorithms > Ring Buffer

Ring Buffer

Introduction

A ring buffer is a fixed-size data structure that uses a single, contiguous block of memory as a circular queue. It maintains two indices (front and back) to manage reading and writing. When the end of the buffer is reached, it wraps around to the beginning — forming a logical circle.

Pros:

• Constant-Time Operations: O(1) time for enqueue and dequeue (no shifting of elements).

• Fixed Memory Footprint: Efficient for systems with limited memory or real-time constraints.

• Cache-Friendly: Data is stored contiguously in memory.

• Ideal for Streaming: Commonly used in audio buffers, UART RX/TX buffers, and producer-consumer models.

Cons:

• Fixed Capacity: Must predefine buffer size; resizing is non-trivial.

• Wasted Slot (optional): Some implementations leave one slot empty to distinguish full vs. empty.

• Requires Careful Index Management: Logic for wraparound and full/empty detection can be error-prone.

• Not Suited for Arbitrary Insertion/Deletion: Only supports FIFO (queue-style) behavior.

Implementation (C++)

Header (rbuffer.hpp)

​x
1
#ifndef RBUFFER_HPP
2
#define RBUFFER_HPP
3

4
#include <iostream>
5

6
class rbuffer
7
{
8
public:
9
    rbuffer(const int cap);
10
    ~rbuffer();
11
    bool empty() const;
12
    bool full() const;
13
    void push(const int val);
14
    int pop();
15
    int front() const;
16
    int size() const;
17
    int capacity() const;
18
    void clear();
19

20
private:
21
    int *buffer;
22
    int cap;
23
    int head;
24
    int tail;
25
    int sz;
26
};
27

28
#endif

Source (rbuffer.cpp)

74
1
#include "rbuffer.hpp"
2
#include <stdexcept>
3

4
rbuffer::rbuffer(const int cap)
5
    : cap(cap), head(0), tail(0), sz(0)
6
{
7
    buffer = new int[cap];
8
}
9

10
rbuffer::~rbuffer()
11
{
12
    delete[] buffer;
13
}
14

15
bool rbuffer::empty() const
16
{
17
    return sz == 0;
18
}
19

20
bool rbuffer::full() const
21
{
22
    return sz == cap;
23
}
24

25
void rbuffer::push(const int val)
26
{
27
    if (full())
28
    {
29
        throw std::overflow_error("Ring buffer overflow");
30
    }
31

32
    buffer[tail++] = val;
33
    tail %= cap;
34
    ++sz;
35
}
36

37
int rbuffer::pop()
38
{
39
    if (empty())
40
    {
41
        throw std::underflow_error("Ring buffer underflow");
42
    }
43

44
    int val = buffer[head++];
45
    head %= cap;
46
    --sz;
47

48
    return val;
49
}
50

51
int rbuffer::front() const
52
{
53
    if (empty())
54
    {
55
        throw std::runtime_error("Ring buffer is empty");
56
    }
57

58
    return buffer[head];
59
}
60

61
int rbuffer::size() const
62
{
63
    return sz;
64
}
65

66
int rbuffer::capacity() const
67
{
68
    return cap;
69
}
70

71
void rbuffer::clear()
72
{
73
    head = tail = sz = 0;
74
}

Test Driver

9
1
5 0
2
0 3
3
0
4
1 5
5
0
6
5
7
1
8
0 3
9
3

Implementation (C)

Header (rbuffer.h)

42
1
#ifndef RBUFFER_H
2
#define RBUFFER_H
3

4
#include <stdbool.h>
5

6
typedef struct
7
{
8
    int *buffer;
9
    int capacity;
10
    int head;
11
    int tail;
12
    int size;
13
} rbuffer;
14

15
// initializes the ring buffer
16
bool rbuffer_init(rbuffer *rb, const int cap);
17

18
// frees allocated memory
19
void rbuffer_destroy(rbuffer *rb);
20

21
// adds an element to the buffer
22
bool rbuffer_push(rbuffer *rb, const int val);
23

24
// removes the oldest element
25
bool rbuffer_pop(rbuffer *rb);
26

27
// finds the oldest element if any
28
bool rbuffer_front(rbuffer *rb, int *out_val);
29

30
// checks if buffer is empty
31
bool rbuffer_empty(const rbuffer *rb);
32

33
// checks if buffer is full
34
bool rbuffer_full(const rbuffer *rb);
35

36
// clears the buffer
37
void rbuffer_clear(rbuffer *rb);
38

39
// returns the number of elements currently in the buffer
40
int rbuffer_size(const rbuffer *rb);
41

42
#endif

Source (rbuffer.c)

127
1
#include "rbuffer.h"
2
#include <stdlib.h>
3
#include <stddef.h>
4

5
// initializes the ring buffer
6
bool rbuffer_init(rbuffer *rb, const int cap)
7
{
8
    if (!rb || cap <= 0)
9
    {
10
        return false;
11
    }
12

13
    rb->buffer = (int *)malloc(cap * sizeof(int));
14
    if (!rb->buffer)
15
    {
16
        // memory allocation failed
17
        return false;
18
    }
19

20
    rb->head = 0;
21
    rb->tail = 0;
22
    rb->size = 0;
23
    rb->capacity = cap;
24

25
    return true;
26
}
27

28
// frees allocated memory
29
void rbuffer_destroy(rbuffer *rb)
30
{
31
    if (!rb)
32
    {
33
        return;
34
    }
35

36
    if (rb->buffer)
37
    {
38
        free(rb->buffer);
39
        rb->buffer = NULL;
40
    }
41

42
    rb->head = 0;
43
    rb->tail = 0;
44
    rb->size = 0;
45
    rb->capacity = 0;
46
}
47

48
// adds an element to the buffer
49
bool rbuffer_push(rbuffer *rb, const int val)
50
{
51
    if (!rb || !rb->buffer || rbuffer_full(rb))
52
    {
53
        return false;
54
    }
55

56
    rb->buffer[rb->tail] = val;
57
    rb->tail = (rb->tail + 1) % rb->capacity;
58
    rb->size++;
59

60
    return true;
61
}
62

63
// removes the oldest element
64
bool rbuffer_pop(rbuffer *rb)
65
{
66
    if (!rb || !rb->buffer || rbuffer_empty(rb))
67
    {
68
        return false;
69
    }
70

71
    rb->head = (rb->head + 1) % rb->capacity;
72
    rb->size--;
73

74
    return true;
75
}
76

77
// finds the oldest element if any
78
bool rbuffer_front(rbuffer *rb, int *out_val)
79
{
80
    if (!rb || !rb->buffer || rbuffer_empty(rb))
81
    {
82
        return false;
83
    }
84
    
85
    if (out_val)
86
    {
87
        *out_val = rb->buffer[rb->head];
88
    }
89

90
    return true;
91
}
92

93
// checks if buffer is empty
94
bool rbuffer_empty(const rbuffer *rb)
95
{
96
    return !rb || (rb->size == 0);
97
}
98

99
// checks if buffer is full
100
bool rbuffer_full(const rbuffer *rb)
101
{
102
    return !rb && rb->buffer && (rb->size == rb->capacity);
103
}
104

105
// clears the buffer
106
void rbuffer_clear(rbuffer *rb)
107
{
108
    if (!rb)
109
    {
110
        return;
111
    }
112

113
    rb->head = 0;
114
    rb->tail = 0;
115
    rb->size = 0;
116
}
117

118
// returns the number of elements currently in the buffer
119
int rbuffer_size(const rbuffer *rb)
120
{
121
    if (!rb)
122
    {
123
        return 0;
124
    }
125

126
    return rb->size;
127
}

Test Driver

32
1
#include <stdio.h>
2
#include "rbuffer.h"
3

4
int main(int argc, char *argv[])
5
{
6
    rbuffer rb;
7

8
    rbuffer_init(&rb, 5);
9

10
    rbuffer_push(&rb, 10);
11
    rbuffer_push(&rb, 20);
12
    rbuffer_push(&rb, 30);
13
    rbuffer_push(&rb, 40);
14
    rbuffer_push(&rb, 50);
15

16
    int val;
17
    while (!rbuffer_empty(&rb))
18
    {
19
        if (rbuffer_front(&rb, &val))
20
        {
21
            printf("%d\n", val);
22
        }
23
        
24
        rbuffer_pop(&rb);
25
    }
26

27
    rbuffer_destroy(&rb);
28

29
    printf("%d %d\n", rbuffer_empty(&rb), rbuffer_full(&rb));
30

31
    return 0;
32
}

1
1
10
2
20
3
30
4
40
5
50
6
1 0