Looking at the forum search results this appear to have been quite a common topic: how to implement a circular buffer.
I believe I have a decent and general implementation which should represent a decent compromise between size and flexibility, but I'm looking for your opinion before pushing a new library into the library manager list.
Also, my search for an equivalent library didn't produce any result, but may be I've skipped some important source, so if you know of an existing and possibly better implementation that can also save people some time.
The library is available as a Gist on Github, but I also attach it here (it's a single file) for sake of simplicity; if you wish to make any specific comment and you have a Github account feel free to comment directly on the source code.
The implementation allows to use the buffer as a queue ([b]append[/b] and [b]pop[/b]) or as a stack ([b]push[/b] and [b]pop[/b]): do you believe the names are appropriate?
Would it be clearer using [b]push[/b] and [b]pull[/b] for a queue and [b]push[/b] and [b]pop[/b] for a stack?
/*
CircularBuffer.h - Circular buffer library for Arduino.
Copyright (c) 2017 Roberto Lo Giacco. All right reserved.
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
#ifndef __CIRCULAR_BUFFER__
#define __CIRCULAR_BUFFER__
#include <inttypes.h>
template<typename T, uint16_t S>
class CircularBuffer {
public:
CircularBuffer() : head(buffer), tail(buffer), count(0) {
}
~CircularBuffer() {
}
/**
* Adds an element to the beginning of buffer returning `false` if the addition caused overwriting an existing element.
*/
bool push(T value) {
if (head == buffer) {
head = buffer + S;
}
*--head = value;
if (count == S) {
if (tail-- == buffer) {
tail = buffer + S - 1;
}
return false;
} else {
if (count++ == 0) {
tail = head;
}
return true;
}
}
/**
* Adds an element to the end of buffer returning `false` if the addition caused overwriting an existing element.
*/
bool append(T value) {
if (++tail == buffer + S) {
tail = buffer;
}
*tail = value;
if (count == S) {
if (++head == buffer + S) {
head = buffer;
}
return false;
} else {
if (count++ == 0) {
head = tail;
}
return true;
}
}
/**
* Removes an element from the beginning of the buffer.
*/
T pop() {
T result = *head++;
if (head == buffer + S) {
head = buffer;
}
count--;
return result;
}
/**
* Removes an element from the end of the buffer.
*/
T pull() {
T result = *tail--;
if (tail == buffer) {
tail = buffer + S - 1;
}
count--;
return result;
}
/**
* Returns the element at the beginning of the buffer.
* Like pop(), but it doesn't remove the element.
*/
T inline first() { return *head; }
/**
* Returns the element at the end of the buffer.
* Like poll(), but it doesn't remove the element.
*/
T inline last() { return *tail; }
/**
* Array-like access to buffer
*/
T operator [] (uint16_t index) { return *(buffer + ((head - buffer + index) % S)); }
/**
* Returns how many elements are actually stored in the buffer.
*/
int inline size() { return count; }
/**
* Returns how many elements can be safely pushed into the buffer.
*/
int inline available() { return S - count; }
/**
* Returns `true` if no elements can be removed from the buffer.
*/
bool inline isEmpty() { return count == 0; }
/**
* Returns `true` if no elements can be added to the buffer without overwriting existing elements.
*/
bool inline isFull() { return count == S; }
/**
* Resets the buffer to a clean status, dropping any reference to current elements
* and making all buffer positions available again.
*/
void inline clear() {
head = tail = buffer;
count = 0;
}
private:
T buffer[S];
T *head;
T *tail;
uint16_t count;
};
#endif
PaulS:
The typical terms for putting stuff into, and removing stuff from a queue, are enqueue and dequeue.
Do NOT plan to release the code that way. The class definitions belong in a header file. The implementations belong in a source file.
When using CPP templates you cannot separate the definition from the implementation, the compiler needs to know and replace the exact template implementation at compile time.
What I can do is to separate the implementation ina .tpp file which gets included FROM the header file, but as for .h and .cpp, having a .h and a .tpp is not changing a lot.
PaulS:
Stacks and queues do not use circular buffers.
I must disagree with you here: generally speaking that depends on the stack and queue implementation you are looking for. Stacks and queues are two names associated to two opposite linear data structure usage: Last In Fist Out (LIFO) and First In First Out (FIFO) respectively.
Normally we use a FIFO approach with buffers, but that really depends on the context.
Also depends from the context if it's better to keep the data store growing indefinitely or somehow limit it: on micro controllers I prefer to lose data instead of increasing memory consumption, that's the reason for using a circular buffer.
Use case scenario: I have to display a motor RPM, I'm sampling it 100 times a second, but I update the display only every 500ms, meaning I collect 50 samples every 500ms... Once I update the display I want to use the average of the existing samples, but due to interrupt routines I can get 49, 50 or 51 samples... Using a circular buffer (doesn't matter the LIFO/stack or FIFO/queue because I never pop anything out of the buffer) I can solve the problem with no particular hassle.
@PaulS what about the questions in my original post? I know enqueue and dequeue are the standard names, but I'm looking which one of the proposed makes much sense: I would prefer to avoid having two names for the same operation (add a new item or get an item from the store).
I recognize 3 different read/write operations in LIFO & FIFO, with either two different type of addition or two different type of removal...
PaulS:
You had two.
I believe that I answered that.
The typical names for putting stuff into, and removing stuff from, a stack are push and pop.
So, for a stack, your names are fine. For a queue, they are not.
Again, I believe I answered that. What would be clearest is using names that people are familiar with.
Sorry, edited before seeing you did already reply.
I understand your logic regarding names and I would normally agree, but I'd rather avoid having 2 names for the same operation.
As in my edit above, I know enqueue and dequeue are the standard FIFO names, but I'm looking which one of the proposed makes much sense: I would prefer to avoid having two names for the same operation (add a new item or get an item from the store).
I recognize 3 different read/write operations in LIFO & FIFO, with either two different type of addition or two different type of removal...
An alternative might be to completely drop the stack/queue naming...
bool append(T) adds to the end, result informs about overwriting
T last(bool) reads/removes from the back, boolean value determines the removal
T first(bool) reads/removes from the front, boolean value determines the removal
Anyway, do you believe a library like this is worth publishing?
I've accepted your header/source advice and split the code into .h and .tpp, see CircularBuffer on Github if you like.
So, for a stack, your names are fine. For a queue, they are not.
The STL uses push and pop for both queues and stacks. Both push to the back, it's just that a stack pops from the back and a queue pops from the front.
rlogiacco:
Anyway, do you believe a library like this is worth publishing?
So, how do you get the Arduino IDE to even recognize the .tpp extension? What version are you using?
I was trying to compile your example just putting your lib into the example directory... gave up.
Personally, I'd ditch @PaulS's advice and incorporate the source into the header, like is commonly done with Template classes. IMHO, people will see that it looks different, because it is.
Have you thought about a namespace? You are using very common function names....
BulldogLowell:
So, how do you get the Arduino IDE to even recognize the .tpp extension? What version are you using?
I was trying to compile your example just putting your lib into the example directory... gave up.
Actually I don't personally use the Arduino IDE but Sloeber, its Eclipse based alternative.
The .tpp extension doesn't have to be recognized, it could be .xyz and should work the same way because it's the header file which includes the .tpp, in other words the .tpp will be considered as an extension of the .h file... at least that's my understanding.
I did try this myself with Arduino IDE 1.8.2 and just adding CircularBuffer folder under libraries allows a nice compilation of a sketch importing CircularBuffer.h.
BulldogLowell:
Personally, I'd ditch @PaulS's advice and incorporate the source into the header, like is commonly done with Template classes. IMHO, people will see that it looks different, because it is.
While I like the header/source separation if that makes things too complicate I'll revert to one file only.
BulldogLowell:
Have you thought about a namespace? You are using very common function names....
Isn't the class name already a namespace? I mean, the functions will not clash with other...
Jiggy-Ninja:
The STL uses push and pop for both queues and stacks. Both push to the back, it's just that a stack pops from the back and a queue pops from the front.
Yup. Nonetheless STL is not really common among Arduino developers and I'm not looking to create two separate classes... While I wish to provide both LIFO and FIFO I'm not looking to create CircularQueue and CircularStack
I came with 3 different naming styles, they all seem an acceptable compromise to me:
push (adds to head), pull (removes from tail) and pop (removes from head)
push (adds to head), append (adds to tail) and pop (removes from head)
append (adds to tail), head/first (removes from head) and tail/last (removes from tail)
They all sound straightforward to me, but English is not my first language...
PaulS:
Why? The beauty of classes is that you can have two functions that do the same thing, but with names that make sense for the way the user thinks.
void enqueue(T value)
{
push(value);
}
T dequeue()
{
return pop();
}
If we weren't on Arduino I would totally agree with you, but every new function we create requires space in Flash memory, even if it's just to store the function name. I have been trying to squeeze the last byte out of the library so I'm unwilling to give up some bytes in that direction, even if it makes a lot sense to me.
I'm a Java developer, so getting into this mindset has not been easy...
rlogiacco:
Actually I don't personally use the Arduino IDE but Sloeber, its Eclipse based alternative.
I guess I was thinking the run-of-the-mill Arduino user who may may not be capable of rolling their own class but would be interested in using your lib.
rlogiacco:
Isn't the class name already a namespace? I mean, the functions will not clash with other...
I was thinking more of the semantics, if I opened someone's code and it was using STL speak and common vector jargon.
Use case scenario: I have to display a motor RPM, I'm sampling it 100 times a second, but I update the display only every 500ms, meaning I collect 50 samples every 500ms... Once I update the display I want to use the average of the existing samples, but due to interrupt routines I can get 49, 50 or 51 samples... Using a circular buffer (doesn't matter the LIFO/stack or FIFO/queue because I never pop anything out of the buffer) I can solve the problem with no particular hassle.
You might want to check my RunningAverage lib for the use case.
rlogiacco:
Yup. Nonetheless STL is not really common among Arduino developers and I'm not looking to create two separate classes... While I wish to provide both LIFO and FIFO I'm not looking to create CircularQueue and CircularStack
I came with 3 different naming styles, they all seem an acceptable compromise to me:
push (adds to head), pull (removes from tail) and pop (removes from head)
push (adds to head), append (adds to tail) and pop (removes from head)
append (adds to tail), head/first (removes from head) and tail/last (removes from tail)
They all sound straightforward to me, but English is not my first language...
Functions that do something should have a verb in the name. Push, pull, pop, and append are fine names for adding and removing elements, but not head, first, tail, or last. Those should just return a reference to the element, and not remove it from the container.
That's a pretty valid example, but more oriented to math than to general use IMHO due to the extensive use of doubles.
One thing I feel as a plus with my implementation is the memory occupation is fixed at compile time (no malloc involved) which should also reduce troubleshooting.
Naturally your library is less general and, as such, provides a lot more value in its specific field of application while I'm trying to tackle a more generic problem: that's why I also added an array-like indexed access operation to browse the elements.
I can see an easy way to re-implement your library over my circular buffer to get the best of both
It can be used to implement a stack or a queue or a circular buffer.
And with a few additional methods one can also create a priority queue from it.
The Operations table reported in that wiki page contains exactly the type of advice I was looking for: THANKS!
I believe I'll go for the names which seem to be more frequently adopted: push, pop, shift and unshift accompanied by first, last, size and the indexed access operator []. I might also consider leaving isEmpty and isFull there, may be also available, though all of them can easily be computed by the user.
MorganS:
No. The Flash memory never knows the name of the functions or variables.
Right. Then I'm missing something.
Will a class with one function and another class with 100 functions, all containing the same statements, have the same size? I thought we had to keep in memory an address table resolving calls to flash addresses...
rlogiacco:
The Operations table reported in that wiki page contains exactly the type of advice I was looking for: THANKS!
Updated version with refactored names and examples is available on Github: any comment is very welcome, better if it comes before I release/publish the library for the Library Manager.
