Ring Buffer

Overview

A ring buffer is a data structure that makes managing data very easy. It’s essentially a queue, or a FIFO: you keep pushing data into the ring buffer, and then at some point in the future, you pop data off of it in the same order that you put in. That’s why it’s called a FIFO (First In, First Out): the first and second thing you put into the buffer are the first and second thing you get out of it. Buffers are really useful when you get data that you can’t or don’t want to handle at that moment, but will need later. In our case, we’ll be using the ring buffer to put in data we get from from the UART (my next post!), and then when the microcontroller is ready, we can pull the data out of the buffer and use it. If we’re getting a long string of characters, for example, it makes more sense to deal with the string all at once rather than one character at a time. The ring buffer makes this operation much simpler.

The RING part of the ring buffer arises from how the data is stored. In an ideal world, the microcontroller has an infinite amount of memory, and can store an infinite amount of data. However, in the real world, we have to limit the size of the buffer. So what do we do when the buffer is full, and more data needs to be put into it? One solution is to just ignore the new data. The advantage is that the data in the buffer won’t be corrupted or overridden, but that also means the system isn’t very robust; once the buffer fills up, the buffer stops updating, and that can cause serious problems, depending on the application. The second solution is to override the existing data. This will result in loss of the oldest data, which is replaced by the newest. This is why it’s called a RING buffer; the data goes in a circle, with the newest data constantly overriding the old data, reusing the same space in memory, just like how the hands of a clock goes in a circle, reusing the same number on the face of the clock. Let’s look at an example of a ring buffer in action:

There are 4 variables used to manage the ring buffer: the read index, the write index, number of elements, and overflow flag. The read index tells the system where it should read the data from; it is used when pulling data out of the buffer. The write index tells the system where data should be written to; it is used when putting data into the buffer. The number of elements is needed to know if the buffer is full. And the overflow flag is used to see if an overflow has occurred at some point, which the system may or may not care about.

Let’s step through the example:

1. Initially, the buffer is empty. The number of elements is zero, and the read and write indexes point to the same spot in the buffer, which has a size of 5. The overflow flag is set to FALSE.
2. The system has pushed a 1 into the buffer. This increments the write index, since the system should write to the next available spot. The number of elements has incremented as well. The read index does not increment.
3. The system has pushed a 2 and a 3 into the buffer. This again increments the write index (twice), and the number of elements (twice), but not the read index.
4. The system has pushed a 4 and a 5 into the buffer. This again increments the write index and number of elements by two, but not the read index. There are two important points to note: firstly, the buffer is full; all available slots have been taken up. Secondly, the write index has wrapped around, completing one “revolution” in the ring buffer. Just like at the beginning, the read and write indexes point to the same spot in the buffer!
5. A pop has occurred. The ring buffer returns the value that the read index was pointing to, which is 1. Then, the read index is incremented by one, so that the ring buffer can return the next element if the system performs another pop. The number of elements in the ring buffer is also decremented, since the popped value is removed from the ring buffer. This frees up one spot in the buffer.
6. The system has pushed a 6 into the buffer. This increments the write index and the number of elements. The buffer is full again, and the read and write indexes point to the same location in the buffer, though it’s a different location than the last time the buffer was full.
7. The system has pushed a 7 into the buffer. But the buffer is full! Several things occur. Firstly, the 2 is overridden and replaced by the 7, and the write index is incremented. Secondly, since data has been overridden, the overflow flag is changed to TRUE. Thirdly, since we don’t want the pop to return 7 (the newest data) but instead 3 (the oldest data), the read index is also incremented.
8. A pop has occurred. The ring buffer returns the value that the read index was pointing to, which is 3. In an ideal world, the pop would return 2, the value we should expect if no overrides had occurred. However, since that piece of data is long gone, the ring buffer should return the next best thing. Now, the buffer is no longer full, and a single spot has opened up. However, this does not clear the override flag. The override flag can only be set by the ring buffer, and it should only be cleared by the end user or application code.

Hopefully the theory of the ring buffer is clear now: it’s a way to store and retrieve data. The management of the pointers and overflow logic is all handled by the ring buffer; the end user only has to worry about pushing and popping values, and possibly checking and clearing the overflow flag.

Before moving onto the implementation of the ring buffer, I’d like to point out a couple of things. Firstly, the size of the ring buffer depends on several things, but the main ones are (1) how frequently data is pushed, (2) how frequently data is popped, (3) how bad an overflow is, (4) how much memory you can spare, and (5) how many data points you need. In some applications, an overflow is not a problem; in fact, it may be desirable behavior. For example, if the application code only wants the 10 most recent values, then overflows allow the old, outdated data to be washed away by the new data. However, if an overflow can cause the application code to get confused, for example you’re trying to store a string you’ll parse later, then things get more complicated. You’ll have to make sure the buffer is flushed (that is, everything is popped and the buffer is made empty) frequently, or the buffer is large enough that infrequent popping won’t result in an overflow, or you have to put in a fail-safe, for example the application throws away the contents of the buffer and asks for the data again in the event of an overflow. Of course, how you deal with this problem depends on your hardware; if you have memory a plenty, then make the buffer nice and big. Otherwise, you’ll have to make some performance / convenience compromises.

Secondly, the sum property. I didn’t mention it during the walk-through of the example, because it’s not hugely important, but it’s helpful to update the sum of the ring buffer as its contents get updated. Each time a value is pushed into the ring buffer, the sum is incremented by that value. Each time a value is popped, the sum is decremented by that value. Each time an overflow occurs, the sum is decremented by the overridden value, and incremented by the new one. The sum makes getting the average of the contents of the ring buffer trivial; all you need to do is divide the sum by the number of elements. You could, of course, calculate the sum only when the application code asks for the average; for example, just have a for loop that runs through all the valid elements of the array and get their sum. However, if the ring buffer becomes very large, then updating the sum as you modify the ring buffer allows calculating the average to be done without having to traverse the buffer. Of course, sums and averages of the buffer make no sense for some data types, for example if you’re storing booleans or characters.

Implementation

Above is the class definition. Right away, in trying to implement the ring buffer, we run into two problems. Firstly, we want to generalize the type of data the ring buffer stores; it could be char, uint16_t, float, etc. How do we do that? It’d be pretty inconvenient to define the same class over and over again, just to change the data type. Secondly, how do we set the buffer size? We could use a macro and have a #define BUFFER_SIZE, but then that means all instances of ring buffers would have the same size, unless you define the same class over and over again, just with different buffer sizes.

Fortunately for us, C++ uses templates to solves both of these problems. A template allows the type and numbers to be abstracted. Here, rbuffer is the array that will hold the elements of the ring buffer. The data type of rbuffer has been abstracted to T, and the size of rbuffer has been abstracted to N. When this class is constructed, both T and N will have to be defined. For UART, T would be char, and N would be something like 20. If I’m using the ring buffer to hold 32 samples from a 16 bit ADC, then T would be uint16_t and N would be 32. N and T are used in various places in this class definition; for example, one of the methods, called get_size, just returns N. Another example is the macro RBUFFER_INDEX_INC, which is responsible for incrementing and wrapping around the index.

The constructor is very simple for this class: it initializes the buffer by writing 0 to each spot, then zeros all of its private variables. The initialization of the buffer isn’t necessary, but it may save on future headaches, so let’s do it for now.

As mentioned previously, push is responsible for putting data into the buffer. Here, sum is incremented with the new value, the new value is written to where the write index is pointing, and then the write index is incremented using a macro. Then, the system checks for an overflow. If an overflow has not occurred, then the number of elements is incremented. If an overflow has occurred, then the number of elements does not change, since the new value is replacing an old value. Additionally, for an overflow, the read index must be incremented. Finally, the overflow flag is set.

I originally wanted the pop method to return the value; for example, popping a 3 will cause the method to return 3. However, what would the method return if the buffer is empty? It could return a specific number that denotes a failure, for example -1 or 0, but that limits what kind of data the buffer can store. Instead, I had the method return a bool, indicating if the pop was successful. If the buffer is empty, then a false is returned; otherwise, a true is returned, and the popped value is written to the provided reference (a reference is like a pointer in C, but it is automatically dereferrenced; here, writing to val will cause the argument provided to be updated).

So the logic of pop is as follows: if the buffer is not empty, then val is updated with whatever the read index points to. Then, the read index is updated. The sum is decremented by the value that has been popped, and the number of elements is decremented. If the buffer is empty, then nothing occurs, and a false is returned.

Now, if you want to get 5 elements from the ring buffer, then you could call pop five times, but I wanted a method that made this process easier. Here. flush will pop until the buffer is empty, or the requested number of elements have been popped, whichever comes first.

The application code that calls this method has to provide a pointer, which indicates the array that the popped elements should be written to. In order to prevent an overflow, the maximum number of popped elements must also be provided. The method returns the number of elements that have been popped; this information is important because if the buffer becomes empty before the requested number of pops have been performed, then that information should be provided to the application code. This return value is also very helpful as the condition in a while loop or if statement; if the buffer is empty, then the method returns 0, so the code doesn’t execute. If the buffer isn’t empty, then the method returns something greater than 0 (as long as max_num isn’t zero), and the code will execute.

Here are the rest of the methods. For the most part, they just set or get private variables. The only tricky one is the get_average method. What happens if you try to get the average of an empty buffer? Since the sum will be divided by the number of elements, which is zero, you’ll crash the system. So the method checks to see if the buffer is empty; if it is, then the method simply returns 0.

Next time, I’ll show how the ring buffer is used in the UART HAL to manage the data that is coming in over serial.