Circular_Buffer

This addition in RED demonstrates the behaviour:

Code:
#include "circular_buffer.h"

void setup() {
  Serial.begin(115200);
  delay(3000);
  Serial.println("----------------------");

  Circular_Buffer<uint8_t, 64, 10> k;
  Serial.print("Initial Q Size: "); Serial.println(k.capacity());
  
  uint8_t bufc[] = { 0, 1, 2, 3, 4, 5 };
  uint8_t bufc1[] = { 6, 7, 8, 9, 10, 11 };
  uint8_t bufc2[] = { 12, 13, 14, 15, 16, 17 };
  uint8_t bufc3[] = { 18, 19, 20, 21, 88, 23 };

  k.push_back(bufc, sizeof(bufc));
  k.push_back(bufc1, sizeof(bufc1));
  k.push_back(bufc2, sizeof(bufc2));
  k.push_back(bufc3, sizeof(bufc3));
  Serial.print("After Init, Q Size: "); Serial.println(k.size());
  
  uint8_t bufme[] = { 6, 19, 20, 21, 88, 12, 13, 4, 5 };
  k.list();
  Serial.println("Example of replace with 3 indicies");
  k.replace(bufme, sizeof(bufme), 1, 2, 3);
  k.list();
  //replace is comparing values 19,20,21 between queue and buffer, 
  //the order is not imporant, if you call:
  //k.replace(bufme, sizeof(bufme), 3, 1, 2);
  //it's the same search pattern, if those indexes match, 
  //the buffer will replace that queue content

  //There is a minimum of replace indicies need for replace,
  //however, it is possible to use only 1 or two indicies
  Serial.println("Example to replace based on 1 field");
  k.replace(bufme, sizeof(bufme), 0, 0, 0);  // 1 field
  k.list();
  Serial.println("Example to replace based on 2 fields");
  [COLOR="#FF0000"]bufme[7] = 99;[/COLOR]
  k.replace(bufme, sizeof(bufme), 5, 6, 6);  // 2 fields
  k.list(); 

}

void loop() {
  // put your main code here, to run repeatedly:

}

Output:
Code:
Queue list: 
0) 0 1 2 3 4 5 (6 entries.)
1) 6 19 20 21 88 12 13 [COLOR="#FF0000"]99[/COLOR] 5 (9 entries.)
2) 12 13 14 15 16 17 (6 entries.)
3) 6 19 20 21 88 12 13 4 5 (9 entries.)

usually this performance replace is for non doubling queues, where if a return is 0, you should push the buffer to queue, if a return was 1, replace it but dont push:
ex.
Code:
if ( _outgoing_queue.replace(buffer,4,1,1,1)  == 0) _outgoing_queue.push_back(buffer,4);

if theres nothing to replace, queue it, this single line prevents duplicates

EDIT, your sketch, the 3rd one actually did work, but you didnt notice it was replaced, with the same exact buffer :)
 
Last edited:
Thanks for the explanation tonton81, got myself confused as usual. Going to add your last example to the sketch.

usually this performance replace is for non doubling queues
Guess I started with first because I am on a LIFO system. :) Anyway its still a good exercise just with an added complication :)

With that said, I changed the sketch up and am now stuck on a new example, code extract:
Code:
  //Lets try that again with a little mix up on the buffer 
  Serial.println("mixed up buffer entries");
  init1_buffer();
  k.replace(bufme, sizeof(bufme), 5, 6, 6);  // 2 fields
  k.list();

Since I learned a new command, clear(), made it easier to see what I was doing. I put the array initialization stuff in a couple of init functions. Heres the one associated with that example:
Code:
void init1_buffer(){
  k.clear();
  uint8_t bufc[] = { 0, 1, 2, 3, 4, 5 };
  uint8_t bufc1[] = { 6, 7, 8, 9, 10, 11 };
  uint8_t bufc2[] = { 12, 13, 14, 15, 16, 17 };
  uint8_t bufc3[] = { 18, 19, 20, 21, 22, 23 };
  uint8_t bufc4[] = { 21, 22, 23, 24, 25, 12, 13, 14 };

  k.push_front(bufc, sizeof(bufc));
  k.push_back(bufc1, sizeof(bufc1));
  k.push_front(bufc4, sizeof(bufc4));
  k.push_back(bufc3, sizeof(bufc3));
  k.push_front(bufc2, sizeof(bufc2));
  k.list();
}
and here is output - nothing happened - but I did notice that the indicies for the buffer is different, assuming that because I am pushing to the front and back :) creating a bunch of 0's entries in between. Yeah I know, don't say it. I change it later. You know what they say if it can be done someone will do it :)
Code:
mixed up buffer entries
Queue Size: 5, Index order: 61 62 63 0 1 
First Entry: 12 13 14 15 16 17 (6 entries.)
Last Entry: 18 19 20 21 22 23 (6 entries.)

Queue list: 
0) 12 13 14 15 16 17 (6 entries.)
1) 21 22 23 24 25 12 13 14 (8 entries.)
2) 0 1 2 3 4 5 (6 entries.)
3) 6 7 8 9 10 11 (6 entries.)
4) 18 19 20 21 22 23 (6 entries.)

Queue Size: 5, Index order: 61 62 63 0 1 
First Entry: 12 13 14 15 16 17 (6 entries.)
Last Entry: 18 19 20 21 22 23 (6 entries.)

Queue list: 
0) 12 13 14 15 16 17 (6 entries.)
1) 21 22 23 24 25 12 13 14 (8 entries.)
2) 0 1 2 3 4 5 (6 entries.)
3) 6 7 8 9 10 11 (6 entries.)
4) 18 19 20 21 22 23 (6 entries.)
 
EDIT got it, the output is good

Code:
  k.push_front(bufc, sizeof(bufc));
  k.push_back(bufc1, sizeof(bufc1));
  k.push_front(bufc4, sizeof(bufc4));
  k.push_back(bufc3, sizeof(bufc3));
  k.push_front(bufc2, sizeof(bufc2));

Code:
Queue list: 
0) 12 13 14 15 16 17 (6 entries.)                        bufc2   5) pushed front
1) 21 22 23 24 25 12 13 14 (8 entries.)               buf4    3) pushed front
2) 0 1 2 3 4 5 (6 entries.)                                   bufc    1) pushed front
3) 6 7 8 9 10 11 (6 entries.)                               bufc1   2) pushed back
4) 18 19 20 21 22 23 (6 entries.)                        bufc3   4) pushed back

the order is correct

OHHHH, the INDEX order, well, thats normal :)
the head and tail are traversing over the edge of the array, so while your first Head) is pointed at 0 (clear), and your pushing in the back, technically the array indexes are correct

The ring buffer of the array system uses an initiailized count of 0->max in your case 64 (0-63), and the head & tail traverse over it like an ruler, and the ruler points to the proper array in the multidimensional array system
 
Last edited:
Circular_Buffer<uint8_t, 4, 10> k;
If we try that with overriding due to a size of 4 you'd get this:

Queue Size: 4, Index order: 1 2 3 0
First Entry: 12 13 14 15 16 17 (6 entries.)
Last Entry: 6 7 8 9 10 11 (6 entries.)

Queue list:
Code:
0) 12 13 14 15 16 17 (6 entries.)
1) 6 19 20 21 88 12 13 99 5 (9 entries.)
2) 0 1 2 3 4 5 (6 entries.)
3) 6 7 8 9 10 11 (6 entries.)
normal :)
 
"the ruler points to the proper array in the multidimensional array system " - yep - figured when I saw what I really did to the buffer :)

"If we try that with overriding due to a size of 4 you'd get this:" - yep. That would definitely work.

From my silly example, the replace never occurs.
Code:
Input: 
1) 21 22 23 24 25 12 13 14 (8 entries.)

Output:
1) 21 22 23 24 25 12 13 14 (8 entries.

When it should have been after the replace:
Code:
1) 6 19 20 21 88 12 13 99 5 (9 entries.)

Bottom line don't do what I did - fill it in one direction only or make it the size of the entries.
 
im not home to test for another 5 hours or so, but im pretty confident in the replace feature, im using it in a hammered 0ms loop handling data queues for a uart display
 
Yeah but I guarantee you didn't anything as crazy as I did :)

EDIT: Ok. Here is the example with a whole lot of comments. Let me know if anything needs changing
 

Attachments

  • CB_replace_func.zip
    2 KB · Views: 117
Last edited:
Morning tonton81
Ok - back at circular buffer library :) Started playing around with your statistical functions and it works with one exception probably because I am missing something. Using the example posted on the uNavINS thread:
Code:
  myFloats.push_back(3.14159);
  myFloats.push_back(12.3456);
  myFloats.push_back(78.91234);
  myFloats.push_back(7.91234);
  myFloats.push_back(11.91234);
  myFloats.push_back(58.91234);
  myFloats.push_back(18.91234);

if I make the circular_buffer array 8 elements (1 more than the actual number of pushes), everything works:
Code:
MIN: 3.14159
MAX: 78.91234
VARIANCE: 736.18878
DEVIATION: 27.13280
MEAN: 27.43555
SUM: 192.04887
AVERAGE: 27.43555
MEDIAN: 7.91234

Now if I make it
Code:
Circular_Buffer<float, 7> myFloats;
it generates
Code:
MIN: 0.00000
MAX: 18.91234
VARIANCE: 72.99522
DEVIATION: 8.54372
MEAN: 5.40353
SUM: 37.82468
AVERAGE: 5.40353
MEDIAN: 0.00000
which is obviously wrong. So what am I missing here.

Mike
 
power of 2, 7 is not, its all we talked about this week :)

you can choose 1,2,4,8,16,32,64,128,256,512,1024,etc... but nothing in between
 
duh - I forgot, and I just said it on the other thread - dummy. At least I prove your unexpected results :)
 
power of 2, 7 is not, its all we talked about this week :)

you can choose 1,2,4,8,16,32,64,128,256,512,1024,etc... but nothing in between

How about 23?

tonton81 - noted before - would it make sense to ignore any allocated buffers over the lowest included power of 2?

so 7 would control 4 and 23 would actually just set up for 16?

Then the code would fail gracefully when it ran out of buffers as it enforced the rule - rather than making CB look bad for having 'bad non-usable behavior'

Perhaps in the .list - add a note about that? Then add a note to verify or debug CB's to print .list - and include that in all the examples.
 
I was wondering what push_front .vs. push_back did to the stored data. So below find a sample sketch showing the effect.

I wasn't sure if one might overwrite values opposite of the other. Looking at the code it wasn't immediately clear.

I saw the data wasn't stored in a typical list at all - but rather stored and moved into order as needed with each update.
> This is great if the user wanted to do block moves in and out - and had the data storage address.
> But the constant memcpy and shifting of data - while fast and accurate - is a great deal of overhead more than updating pointers, especially when large object space is involved.

>> And this would be more than a little problematic during interrupts or if not guarded with mutexes if threaded.

Not that indexes and pointers in a typical head/tail couldn't be problematic as well - except a reader might only update the HEAD and the writer might only update the TAIL and the reader access would not change data locations removing a value and adjusting the head and the writer would write over a free space and update the tail and change nothing else.

> With circular_buffer code shifting the data positions adding or removing can relocate all data at once - so it seems an interrupted read or write could have bad side effects?

This came up as I considered if a CB gave a safe way to push data for consumption from an interrupt - while the main code would look to pull the data out?

--- it would be nice if the simple CB case could list() the data the way the CA/multi case does.
--- what syntax would allow passing 'cbPF' or 'cbPB' as a parameter to cbShow( CB *foo ) so I could call cbShow() twice rather than use global CB's and duplicate the print code in cbShow()?

The sample below takes the same data and does a push .front to one CB and .back to a second CB - it then peeks the values to print them in order - print output follows:
Code:
#include "circular_buffer.h"
Circular_Buffer<uint32_t, 4> cbPF;
Circular_Buffer<uint32_t, 4> cbPB;
uint32_t DL[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};

void setup() {
	Serial.begin(115200);
	while (!Serial && millis() < 2000 );
	Serial.println("\n" __FILE__ " " __DATE__ " " __TIME__ " " );
}
void loop() {
	uint32_t ii;
	for ( ii = 0; ii < 10; ii++ ) {
		cbPF.push_front( DL[ii] );
		cbPB.push_back( DL[ii] );
		cbShow();
	}
	while (1);
}

void cbShow( void ) {
	int ii;
	Serial.print ( "Push_Frnt::\t" );
	for ( ii = 0; ii < cbPF.available(); ii++ ) {
		Serial.print ( cbPF.peek( ii ) );
		Serial.print ( "\t" );
	}
	Serial.print ( ">Avg:" );
	Serial.print ( cbPF.average(  ) );
	Serial.println ( );
	Serial.print ( "Push_Back::\t" );
	for ( ii = 0; ii < cbPB.available(); ii++ ) {
		Serial.print ( cbPB.peek( ii ) );
		Serial.print ( "\t" );
	}
	Serial.print ( ">Avg:" );
	Serial.print ( cbPB.average(  ) );
	Serial.println ( );
	Serial.println ( );
}

Sample output showing that the data is effectively stored the same just in mirror image - and the same values get overwritten at the same time.
Code:
Push_Frnt::	[B]1	[/B]>Avg:1
Push_Back::	[B]1	[/B]>Avg:1

Push_Frnt::	[B]2	[/B]1	>Avg:1
Push_Back::	1	[B]2	[/B]>Avg:1

Push_Frnt::	[B]3	[/B]2	1	>Avg:2
Push_Back::	1	2	[B]3	[/B]>Avg:2

Push_Frnt::	[B]4	[/B]3	2	1	>Avg:2
Push_Back::	1	2	3	[B]4	[/B]>Avg:2

Push_Frnt::	[B]5	[/B]4	3	2	>Avg:3
Push_Back::	2	3	4	[B]5	[/B]>Avg:3

Push_Frnt::	[B]6	[/B]5	4	3	>Avg:4
Push_Back::	3	4	5	[B]6	[/B]>Avg:4

Push_Frnt::	[B]7	[/B]6	5	4	>Avg:5
Push_Back::	4	5	6	[B]7	[/B]>Avg:5

Push_Frnt::	[B]8	[/B]7	6	5	>Avg:6
Push_Back::	5	6	7	[B]8	[/B]>Avg:6

Push_Frnt::	[B]9	[/B]8	7	6	>Avg:7
Push_Back::	6	7	8	[B]9	[/B]>Avg:7

Push_Frnt::	[B]0	[/B]9	8	7	>Avg:6
Push_Back::	7	8	9	[B]0	[/B]>Avg:6
 
pushing to front or back changes the pointer position of the head and tail and memmoves the array into the CBA

for CB it works normal, with a clear limit of write, it can memmove a write, otherwise at the turn point itll shift the bytes in one at a time

is the above a question or a demonstration? :)

Dont forget for average, its truncated to your Type, in your case uint32_t, is this what you were referring to? i mentioned it in the uNav thread

You suggest I add list support for the CB (non array version)?
 
If your thinking about if it's safe for ISR use, it probably is to some extent, as long as the tail and head don't reach each other, and you only write in one end, not both

If your writing back and front (priority queueing) like im doing in another library, for single threads is fine (as long as your not filling faster than removing), multiple threads definately will need a mutex.

if your only writing back, and reading front, it *should* be ISR safe even for the array version, I don't know exactly how multidimensional arrays work in terms of being "shared", but mutexes in ISR's are a no no as ISR has priority over normal code, you might end up in a deadlock in the ISR as it sits there because the loop() never released the lock from a current read/write...
 
That was a demonstration AND a question.

Indeed it demonstrates the type limits the average value as would be expected, and it would be nice to have a way to DUMP the LIST for simple CB.

Safe for ISR using what methods? Where I push_back data FIFO and then I want to pull_front it off FIFO - won't that constantly/dynamically shift the memory to remove the first item?
 
depends?
only the pointer is moved, no memory is shifted

In the ring buffer mode:
the value is retrieved when read, but not actually removed, the head (or tail) moves over.
The only write that occurs is when doing a push_fromt, push_back, or write, for the ring buffer, push_back and write are one and the same
Other than that, only the head and tails are moved back and front

for the array version, its similar, where it does the same to the multidimensional array system
the first bank: [0][0] would be the position the hail/tail points to when it traverses it's incremented internal buffer.
example,

Circular_Buffer<uint32_t, 4, 10> cbPF;

The internal confined ring buffer for the array system sets the values inside to be 0,1,2,3 accordingly. Every time the head/tail changes position, that value is used in the multidirectional array indice to know which array it can read/write from

If a user prefers not to overwrite his/her buffer, he can check the size() and block if necessary, unless in future i add an internal method to do it by command

If I'm off topic let me know :p
 
Last edited:
I would probably add the list later on, still busy adding to the MST, it's on my todo list :)

I like your demo graphics :p
 
I would probably add the list later on, still busy adding to the MST, it's on my todo list :)

I like your demo graphics :p

I did that graphic output to see how it works - apparently that is not how it is stored though. Would have been ice to just write the code once and be able to PASS IN a CB and have it show the results - I still don't know how to PASS a CB as it is a Template reference and not a class or object? Also how would a CB be 'extern'd across compile units?

I looked at the code and wasn't sure what was coming and going - it looked like stuff was most always moving - I didn't follow the head/tail movement. Lots to learn and don't have the time for that.

Indeed my point was to include for interrupt usage a MUTEX won't work as it would block the INT code if the main code was doing something.
 
I defined the CB in MST as static, which I was able to access via scope

You can also put it straight in the CPP file directly without putting it in the H file, so it remains global, accessible via other sketch/libraries

Using the static/scope method I did not need to declare any externs, but then again, you'd put the extern in your other libraries that would look for it

Havn't played with extern much, used it once in teensquitto to link AsyncUDP to teensquitto to use it's uart protocol and callback, may get ideas there :)

You'd obviously need to include the other library in the one you want it to access, then you should be able to do:

Code:
  Serial.println(SPI_MSTransfer::stmca.capacity());
  Serial.println(SPI_MSTransfer::stmca.max_size());

As long as the object's method/variable is declared public, it'll be accessible. This is why mtsca and stmca are public, so the spi0_isr can access them (with the additional object pointer)

Code:
_slave_pointer->SPI_MSTransfer::mtsca.push_back(data, len);

in teensquitto the extern can be found, what I did was the same as the ESP's AsyncUDP demo library, it created an internal constructed object (like I also did for SPI_MST slave called "slave") using the extern keyword, and was able to just use the object between libraries and user sketch without constructing it in the sketch
 
I don't have the equipment you have for testing (your data hardware from other threads), but I could figure out what you want as long as the sketch starts up I can do some debugging to find out how to make it work in your case, I just need a zip file and simple instructions :)
 
Stored. printout is from head to tail (available only)

yes stored order head to tail

good? :)
 
Last edited:
Good. For debug it might be fun to show H&T vals? Assume this won't be used much unless somebody wants to see why their numbers aren't making sense.

Queue Size: 7 H:# T:#

Queue entries:
-3.14 -12.35 -78.91 -7.91 -11.91 -58.91 -18.91
 
Back
Top