Help with circular buffer

I have been asked as an exercise to implement a circular buffer. I just need a bit of a hand understanding how they actually work.
When data is written to the buffer and the buffer fills up, the write then 'wraps around' the buffer overwriting the oldest data in the buffer and so on.
When the data is extracted the 'pop' starts from the oldest data. data can be popped one element at a time or the entire buffer. Either way the read/qrite portions of the data have to updated to the next 'oldest' data until all the data has been read back to start position - 1.

Then the whole process continues.
Or is the buffer a fixed size and when data is written the write is stopped when the array is at upper limit and an exception thrown outlining the problem?
Then the buffer is reset.

Thanks in advance

The buffer is fixed size.

There's no problem unless the next write will overwrite data that hasn't been read yet.

You either overwrite the data that hasn't been read, or you don't do that and indicate the problem in some way; exception, return value, whatever. Which of those you do depends on the requirements you have at hand.
Great - thanks! I need to implement a way that stops a write until a read has happened, but only if data is going to be overwritten. If there is still ‘room’ then the write can go ahead.
You know the size of the buffer.

Count up each time an element of data is added.
Decrement that count each time an element is read.
When the count reaches the size of the buffer, it's full and the next write will overwrite data that has never been read.
I have tried to implement. Not sure where to go with it now.

Any help is appreciated!!

Thanks in advance.


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
37
38
39
40
41
42
43
44
45
46
47
#ifndef Buffer_hpp
#define Buffer_hpp
#include <iostream>
#include "overflow.hpp"
#include "underflow.hpp"

template<typename T, int SZ = 20>
class buffer
{
private:
    T data[SZ];
    int read_pos{};
    int write_pos{};
public:
    void push(T x)
    {
        write_pos %= SZ;
        data[write_pos++] = x;
    }
    
    T pop()
    {
        
        read_pos %= SZ;
        return data[read_pos++];
    }
    
    int getWritePos()
    {
        return write_pos;
    }
    
    int getReadPos()
    {
        return read_pos;
    }
    
    void showbuffer()
    {
        for(int i{};i < SZ;i++)
            std::cout << data[i] << " ";
    }
};

#endif /* Buffer_hpp */

The buffer should contain a number.
The number begins at zero.
When you push data, add one to the number.
When you pop data, remove one from the number.

If the number ever equals the size, the buffer is full.
Thanks. This is where I am not thinking properly.
Say I push 5 times to the array. my count is 5 so when I pop the data I decrement 5. I understand that bit.
What I am having difficulty with, and for some reason I can't get to grips with it, the data has to popped first in first out?
If I pop decrementing count it will be 5 4 3 2 1.
It should be 1 2 3 4 5.
this is the bit I can't visualise. I apologise if I sound 'a bit thick' :) I am a beginner...!

Thanks a gain.
What I am having difficulty with, and for some reason I can't get to grips with it, the data has to popped first in first out?


Yes. Do that.
Tell me, when you've push hundreds of times, and then someone calls getWritePos(), will they get back a sensible value?
The result of getWritePos() should always be between 0 & SZ, or at least that what I think, because push(T x) has write_pos %= SZ.

sure. but consider a few scenarios:

you push 10 items for every read. what should you get out with the reads?
you pop 10 times for every write. what should you get out now?
you read more than it holds. what behavior do you expect?
the buffer is not full yet, and you read more than it holds. what behavior now?

at some point if the read/write are way out of sync the tool is effectively giving you a random read each time. If you want the oldest piece in there each time, you have to ensure that so every read and write operation are keeping it correct. A single index may be all you need, for some use cases...

I have never used one this way. I usually read the whole thing when I consume, not one by one, eg copy the array off and capture the starting point. But I do not use them often. Here is the question: what problem does this thing solve? If you can answer what you are doing with it, you can make sure the tool DOES that.
1
2
3
4
5
    void push(T x)
    {
        write_pos %= SZ;   // write_pos is now valid
        data[write_pos++] = x;    // You increment write_pos, which might make it invalid.
    }

So the write_pos is only valid between these two statements. That means code like:
1
2
3
4
    int getWritePos()
    {
        return write_pos;
    }
is incorrect because write_pos may be invalid.

You want write_pos to always be valid, except perhaps when it's getting updated:
1
2
3
4
5
void push(T x)
{
    data[write_pos++] = x;
    if (write_pos >= SZ) write_pos = 0;  // faster than %
}


Do the same sort of thing with read_pos.

Now, let's work on computing how many items are in the buffer. Once you have this, deciding if you can read or write to the buffer is easy.

Normally, the size of the buffer (the number of items in it) is just the difference between the pointers: size = write_pos - read_pos. Check that for off-by-one errors. A new buffer is empty and write_pos == read_pos == 0, so that's good.

The formula falls apart when the buffer wraps around. That's when write_pos < read_pos. In that case, the size is (write_pos - read_pos) + SZ

Create a method that returns the size of the buffer.

Then modify push() and pop() to use size() to check for an overflow or underflow. You'll have to decide what to do when it underflows or overflows.

Finally, modify showbuffer to print only the items that are actually in the buffer. In other words, skip the unused slots.
Thanks fellas. I have only now logged on and seen your replies. Today I have had a total rethink on how to implement it. My new class is below. I haven't tested to destruction but from what I have done it looks like I am getting expected results.
I have only used integers so far. Haven't tried with any other data types as yet.

Thanks again.

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#ifndef Buffer_hpp
#define Buffer_hpp
#include <iostream>
#include "overflow.hpp"
#include "underflow.hpp"

template<typename T, int SZ = 20>
class buffer
{
private:
    T data[SZ];
    int bufferlength{};
    int readIndex{};
    int writeIndex{};
public:
    void WriteToBUffer(T x)
    {
        if(bufferFull())
        {
            //std::cout << "Buffer Full" << std::endl;
            std::cout << "Buffer overwrite" << std::endl;
            ++readIndex;//increment index
            --bufferlength;//decrement bufferlenght as it will be incremented in push
            push(x);
        }
        else
        {
            push(x);
        }
    }
    
    void ReadFromBUffer()
    {
        if(!bufferEmpty())
        {
            //std::cout << "\nbuffer empty"; << std::endl;
            pop();
        }
        //else
        //{
            //pop();
        //}
    }
    
    bool bufferFull()
    {
        return bufferlength == SZ;
    }
    
    bool bufferEmpty()
    {
        return bufferlength == 0;
    }
    
    
    void push(T x)
    {
        writeIndex %= SZ;
        data[writeIndex++] = x;
        bufferlength++;
    }
    
    void pop()
    {
        readIndex %= SZ;
        std::cout << data[readIndex++] << " ";
        bufferlength--;//decrement until buffer empty i.e. zero
    }
    
    int getWritePos()
    {
        return writeIndex;
    }
    
    int getReadPos()
    {
        return readIndex;
    }
    
};

#endif /* Buffer_hpp */

#include <iostream>
#include <string>
#include "Buffer.hpp"

int main(int argc, const char * argv[]) {

    const int buffer_size{30};
    
    buffer<int, buffer_size> mybuff;
    
    for(int i{}; i < 8;i++)
    {
        mybuff.WriteToBUffer(i + 1);
    }
    
    for(int i{};i < 8;i++)
    {
        if(mybuff.bufferEmpty())
        {
            std::cout << "\nbuffer empty" << std::endl;
            break;
        }
        else
        {
            mybuff.ReadFromBUffer();
        }
    }
    std::cout << std::endl;
    
    for(int i{}; i < 25;i++)
    {
        mybuff.WriteToBUffer((i + 1) * 20);
    }
   
    for(int i{}; i < 25;i++)
    {
        if(mybuff.bufferEmpty())
        {
            std::cout << "\nbuffer empty" << std::endl;
            break;
        }
        else
        {
            mybuff.ReadFromBUffer();
        }
    }
    
    
    std::cout << std::endl;
    
    
    return 0;
}



Sometimes it's good to write a test program that drive the class directly. Then you can build a larger and larger input file to test the program:

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
37
38
using std::string;
using std::cin;
using std::cout;

int main(int argc, const char * argv[]) {

    const int buffer_size{30};

    buffer<int, buffer_size> mybuff;

    string cmd;
    int num;
    while (cin >> cmd) {
        if (cmd == "push") {
            cin >> num;
            mybuff.push(num);
            cout << "pushed " << num << '\n';
        } else if (cmd == "pop") {
            cout << "pop: ";
            mybuff.pop();
            cout << '\n';
        } else if (cmd == "readpos") {
            cout << mybuff.getReadPos() << '\n';
        } else if (cmd == "writepos") {
            cout << mybuff.getWritePos() << '\n';
        } else if (cmd == "print") {
            mybuff.print();
        } else if (cmd == "bufferEmpty") {
            cout << "bufferEmpty() = " << mybuff.bufferEmpty() << '\n';
        } else if (cmd == "bufferFull") {
            cout << "bufferFull() = " << mybuff.bufferFull() << '\n';
        } else {
            cout << "Unknown command " << cmd << '\n';
        }
    }

    return 0;
}


Sample input:
push 1
push 2
push 3
bufferEmpty
bufferFull
pop
pop
bufferEmpty
bufferFull
pop
bufferEmpty
bufferFull

Corresponding output
pushed 1
pushed 2
pushed 3
bufferEmpty() = 0
bufferFull() = 0
pop: 1
pop: 2
bufferEmpty() = 0
bufferFull() = 0
pop: 3
bufferEmpty() = 1
bufferFull() = 0

Everything looks good so far.
Thanks everyone for your help! I have written test program and ran through it with my IDE and it does do what its supposed to!

Thanks again. No doubt I will be back shortly with more questions...
Topic archived. No new replies allowed.