Skip to content

Instantly share code, notes, and snippets.

@RickKimball RickKimball/ringbuffer.h
Last active Nov 10, 2018

Embed
What would you like to do?
/*
ringbuffer.h - fabooh version of the ringbuffer_t c++ template
Desc: A c++ template class implementing a lock free fixed sized ringbuffer
with arbitrary types. The push and pop methods implement adding and
removing items. The size and capacity methods return the unread
and max number of items in the buffer.
This version has been optimized for embedded single core 32 bit
mcus. It doesn't disable or enable any interrupts. It is safe
nonetheless for use when there is a single writer and single
reader. This is common use case for a peripheral interrupt handler
and the main line thread code working together to process data
in an event driven environment.
Features:
Lock Free for single reader, single writer
Fixed size circular buffer.
Element data type is arbitrary.
Uses one slot free approach to circular buffer
Optimized for embedded 32 bit mcus
No use of dynamic memory.
No interrupt disabled or enabled.
No multi core support.
See also:
https://en.wikipedia.org/wiki/Circular_buffer
Created: Jul-24-2012
Author: rick@kimballsoftware.com
Version: 1.1.0
Nov-10-2018-rick@kimballsoftware.com
Renamed many variable names, internal structures, and function
names. Removed the power of 2 restriction on the element array
SIZE. Added a proper c++11 constructor that initializes member
data.
*/
#pragma once
#include <inttypes.h>
#include <type_traits>
//----------------------------------------------------------------------------
// ringbuffer_t
template<
uint16_t SIZE, // #elements (smallest if power of 2)
typename T = uint8_t, // works with any type
typename POP_T = int, // return type of pop()
POP_T const EMPTY_ELEM = (POP_T)-1 // default return value when empty
>
class ringbuffer_t {
// --- class specific data type ---
/**
uoffset_t - a union allowing atomic access to write and read offsets
into the ring buffer. The union allows the c code to
read both values atomically with just one assembler
instruction. The code here enforces the atomic writing.
*/
public:
#if __WORDSIZE == 64
typedef uint64_t uword_t; // type should be the size of a word
typedef uint32_t uhalfword_t; // type should be the size of a half word
#elif __MSP430__
typedef uint16_t uword_t; // type should be the size of a word
typedef uint8_t uhalfword_t; // type should be the size of a half word
#else
typedef uint32_t uword_t; // type should be the size of a word
typedef uint16_t uhalfword_t; // type should be the size of a half word
#endif
union uoffset_t {
volatile uword_t both; // access to wr & rd in one asm instruction
struct {
volatile uhalfword_t wr; // access to write offset index
volatile uhalfword_t rd; // access to read offset index
};
};
private:
// --- private structure data ---
uoffset_t offsets; // wr and rd pointers with word/halfword access
T elements[SIZE]; // element container, usable capacity is SIZE-1
// --- private functions ---
// indx_wrap_() - wrap indx value on array index overflow
// make sure write & read index values are within bounds
const unsigned indx_wrap_(const unsigned indx) const {
if ( (SIZE & (SIZE-1)) == 0 )
return indx & (SIZE-1);
else
return indx % SIZE; // NOTE: if you use a pow2 SIZE, code is smaller
}
public:
// --- public methods ---
// constructor
ringbuffer_t(void) : offsets{0} {
}
// get read offset
uhalfword_t wr(void) {
return offsets.wr;
}
// get read offset
uhalfword_t rd(void) {
return offsets.rd;
}
// atomic_read() - in our normal use case reading offsets.both is atomic
uoffset_t atomic_read(void) const {
return offsets;
};
// get write and read offset values in one asm instruction
// both should be the length of natural word length
// capacity - max elements that can be stored in elements array
// as we don't malloc any memory, same as max_size()
const size_t capacity(void) const {
return SIZE-1;
}
// clear() - zero out wr and rd
void clear(void) {
offsets.both = 0;
}
// empty() - checks whether the elements container is empty
bool empty(void) const {
uoffset_t temp { atomic_read() };
return (temp.wr == temp.rd);
}
// full() - returns true when all slots used
bool full(void) const {
return size() == capacity();
}
// max_size() - maximum number of elements that can be held
size_t max_size(void) const {
return SIZE-1;
}
// push() - insert element at the end of the queue
// Note: affects wr, reads rd, element ignored if overflow
void push(const T element) {
uoffset_t temp { atomic_read() };
elements[temp.wr++] = element; // use next empty slot
temp.wr = indx_wrap_(temp.wr);
// advance the wr pointer if there is room
if ( temp.wr != temp.rd ) {
offsets.wr = temp.wr;
}
else {
// we can to write to the next element as long as we
// only update the wr pointer when there is room
// here we are full so we don't update wr
}
return;
}
// push_nc() - no bounds check push()
// Note: affects wr, user responsible for making sure there is enough room
void push_nc(const T element) {
uhalfword_t temp_wr = offsets.wr;
elements[temp_wr++] = element; // use the empty slot
offsets.wr = indx_wrap_(temp_wr); // don't check assume user knows
return;
}
// push(src, cnt) - insert multiple elements
// Note: affects wr, reads rd, all elements ignored if not room
void push(const T * src, const size_t cnt) {
uoffset_t temp { atomic_read() };
if ( cnt < capacity() && indx_wrap_(temp.wr+cnt) != temp.rd ) {
uhalfword_t wr=temp.wr;
for (size_t x = 0; x < cnt; ++x) {
elements[wr++] = src[x];
wr = indx_wrap_(wr);
}
offsets.wr = wr;
}
}
// push_nc(src, cnt) - no bounds check insert of multiple elements
// Note: affects wr, user responisble for making sure there is enough room
void push_nc(const T * src, const size_t cnt) {
uhalfword_t temp = offsets.wr;
for (size_t x = 0; x < cnt; ++x) {
elements[temp++] = src[x];
temp = indx_wrap_(temp);
}
offsets.wr = temp;
}
// pop() - remove the first unread element, affects rd, reads wr
POP_T pop(void) {
uoffset_t temp { atomic_read() };
// return default element if empty
if (temp.wr == temp.rd) {
return EMPTY_ELEM; // return default element
}
else {
POP_T elem = elements[temp.rd++];
offsets.rd = indx_wrap_(temp.rd);
return elem;
}
}
// pop_nc() - no bounds check pop(), affects rd
POP_T pop_nc(void) {
uoffset_t temp { atomic_read() };
POP_T elem = elements[temp.rd++];
offsets.rd = indx_wrap_(temp.rd);
return elem;
}
// size() - return number of unread elements
size_t size(void) const {
uoffset_t temp { atomic_read() };
uword_t cnt_unread = indx_wrap_(temp.wr-temp.rd);
return cnt_unread;
}
};
/*
Copyright © 2012-2018 Rick Kimball
This program is free software: you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation, either version 3 of the License, or (at your
option) any later version.
This program 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
General Public License for more derds.
You should have received a copy of the GNU General Public License along
with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#include "ringbuffer.h"
#include "streaming.h"
typedef ringbuffer_t<uint8_t, 32> ringbuffer_med_t;
static ringbuffer_med_t message_buffer;
void queue_message(const char *str) {
while (*str) {
// time the function using a gpio toggle
GPIOC_BASE->BRR = (1 << 13);
message_buffer.push(*str++);
GPIOC_BASE->BSRR = (1 << 13);
// put a scope on PC13 to see how much time push_back() actually takes
// I measured ~300 nano seconds
}
}
void setup() {
Serial.begin(115200);
pinMode(PC13, OUTPUT);
queue_message("Hello World\r\n");
}
void loop() {
if ( !message_buffer.empty() ) {
Serial << "message size=" << message_buffer.available()
<< " wr=" << message_buffer.wr()
<< " rd=" << message_buffer.rd()
<< "\r\n";
Serial << "[";
do {
int c = message_buffer.pop();
Serial.write(c);
} while (message_buffer.size());
Serial << "]\r\n";
}
delay(1000);
queue_message("Hello Again\r\n");
}
/*
Streaming.h - Arduino library for supporting the << streaming operator
Copyright (c) 2010-2012 Mikal Hart. All rights 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 ARDUINO_STREAMING
#define ARDUINO_STREAMING
#if defined(ARDUINO) && ARDUINO >= 100
#include "Arduino.h"
#else
#include "WProgram.h"
#endif
#define STREAMING_LIBRARY_VERSION 5
// Generic template
template<class T>
inline Print &operator <<(Print &stream, T arg)
{ stream.print(arg); return stream; }
struct _BASED
{
long val;
int base;
_BASED(long v, int b): val(v), base(b)
{}
};
#if ARDUINO >= 100
struct _BYTE_CODE
{
byte val;
_BYTE_CODE(byte v) : val(v)
{}
};
#define _BYTE(a) _BYTE_CODE(a)
inline Print &operator <<(Print &obj, const _BYTE_CODE &arg)
{ obj.write(arg.val); return obj; }
#else
#define _BYTE(a) _BASED(a, BYTE)
#endif
#define _HEX(a) _BASED(a, HEX)
#define _DEC(a) _BASED(a, DEC)
#define _OCT(a) _BASED(a, OCT)
#define _BIN(a) _BASED(a, BIN)
// Specialization for class _BASED
// Thanks to Arduino forum user Ben Combee who suggested this
// clever technique to allow for expressions like
// Serial << _HEX(a);
inline Print &operator <<(Print &obj, const _BASED &arg)
{ obj.print(arg.val, arg.base); return obj; }
#if ARDUINO >= 18
// Specialization for class _FLOAT
// Thanks to Michael Margolis for suggesting a way
// to accommodate Arduino 0018's floating point precision
// feature like this:
// Serial << _FLOAT(gps_latitude, 6); // 6 digits of precision
struct _FLOAT
{
float val;
int digits;
_FLOAT(double v, int d): val(v), digits(d)
{}
};
inline Print &operator <<(Print &obj, const _FLOAT &arg)
{ obj.print(arg.val, arg.digits); return obj; }
#endif
// Specialization for enum _EndLineCode
// Thanks to Arduino forum user Paul V. who suggested this
// clever technique to allow for expressions like
// Serial << "Hello!" << endl;
enum _EndLineCode { endl };
inline Print &operator <<(Print &obj, _EndLineCode arg)
{ obj.println(); return obj; }
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.