Circular_Buffer

[tonton81]

Hello all! I just worked the past 2 days on a pretty much advanced version of a circular buffer that follows the STL naming convections of std::queue,deque,vector, etc...

It supports multiple circular buffer creations without the use of reallocation, new, or malloc. The system uses a template for the configuration of the buffers for the class

Regarding the features, the public methods are as follows:

        void push_back(T value) { return write(value); }
        void push_front(T value);
        T pop_front() { return read(); }
        T pop_back();
        void write(T value);
        void push_back(const T *buffer, uint16_t length) { write(buffer, length); }
        void write(const T *buffer, uint16_t length);
        void push_front(const T *buffer, uint16_t length);
        T peek(uint16_t pos = 0);
        T peekBytes(T *buffer, uint16_t length);
        T read();
        T pop_front(T *buffer, uint16_t length) { readBytes(buffer,length); }
        T read(T *buffer, uint16_t length) { readBytes(buffer,length); }
        T readBytes(T *buffer, uint16_t length);
        void flush() { return head = tail = _available = 0; }
        void print(const char *p);
        void println(const char *p);
        uint16_t size() { return available(); }
        uint16_t available() { return _available; }
        T* front() { return _cabuf[peek()]; }
        T* back() { return _cabuf[(tail-1)&(_size-1)]; }

Aside from the circular buffer, there is an even more powerful feature introduced, which is called "Circular Arrays", which might be an interest to most people

if we call:
Circular_Buffer<uint16_t, 32> c5;

c5 is your circular buffer, with 32 entry queue supporting uint16_t Types.
The library supports uint8_t, uint16_t, and uint32_t entries

To use the circular array version, its as follows:
Circular_Buffer<uint16_t, 64, 250> myQueue;

myQueue now contains 64 arrays of 250 uint16_t elements!
The array version circulates the entire bank of 64 before circling back to recycle the arrays, so its pretty efficient.
Whats more important is that both circular buffers and circular arrays all use memmove, for fastest data transfers!

I've setup a demo on my repo and the library as well, hope you all enjoy it

github.com/tonton81/Circular_Buffer

I must also let you know. Both circular buffers and circular arrays all support FIFO, LIFO, and MIXED (FIFO+LIFO); This can lead you to design a priority queue system where front entries for priority items and back entries for least priority
Library is capable of inserting to back or front, including reading from back or front, and removing from back and front. Ditto with the array version

Enjoy!

[mjs513]

Just created a pull request with a updated readme with the notes from post#1

[tonton81]

Merged, thanks

I'm pretty sure the array system will be the most used by the users, although the circular ring buffer does have some uses still:

Averaging ADC readings: (using the uint16_t Type for the ring buffer)
External UART queue: have the incomming data pulled to a bigger queue system rather than modifying the core

But for me, I prefer the array system, it did a painless conversion from STL -> Circular_Buffer using less code for either libraries using it or sketches using it, and the data in that array is guarenteed to be all intact as well

Just as a sample for the SPI_MSTransfer library code, it's as simple as this:

    if ( mtsca.size() > 0 ) {
      uint16_t checksum = 0, buf_pos = 0, len = mtsca.front()[3], buf[len]; AsyncMST info;
      for ( uint16_t i = 0; i < mtsca.front()[1] - 1; i++ ) checksum ^= mtsca.front()[i];
      ( checksum == mtsca.front()[mtsca.front()[1]-1] ) ? info.error = 0 : info.error = 1;
      info.packetID = mtsca.front()[4];
      len = mtsca.front()[3];
      memmove (&buf[0], &mtsca.front()[5], mtsca.front()[3] * 2 );
      mtsca.pop_front();
      if ( _slave_handler != nullptr ) _slave_handler(buf, len, info);
    }

As you can see, the system uses static placements during all array creations, we could pull the resource, ex. array length, from the front()[1] field, and front()[3] dipicts sub array size, starting at front()[5]
Because the system is predictable, we don't need to waste time "parsing", instead, we know the positions of the data we need, so we use it to our advantage

This allows us to "peek" into the array, without removing it, giving people more control on how to handle the data, rather than running into "out of sync" issues, or even "partially overwritten" ring buffers
This allows a single array based queue system to be designed around MANY projects by using a predicatable array system for a multi project based sketch, and dealing with more than 1 dataset without conflicts

[defragster]

This developed on the SPI_Transfer thread - seems a very cool solution for data storage - like the SPI_Transfer is for using SPI connected between two Teensys.

On that thread - beyond routine data storage - some uses seemed like:
> .print() in an isr() to store info to pull and print later
> .print() or other to queue data to wait for a 512 byte buffer with .size() to send to SD in writable blocks
> TeensyThreads where one thread can queue data to a given Circular_Buffer and another task can process/print it
> Error or process logging captured but selectively displayed

[tonton81]

New method updated on the repo for the circular multidimensional array system --> pop_front(buffer, length);
this gives you an instant copy & deque of the array using memmove transfer

Previously I was using the front() method to read the array contents before dequeing with pop_front(), then I realized, why not have an automated deque transfer as well.

Seeing as the system of SPI_MSTransfer uses the 2nd dWord([1]) as a length variable, to copy the queue it was as simple as this:

      uint16_t array[mtsca.front()[1]];
      mtsca.pop_front(array,sizeof(array)/2 );

"array" now contained all the elements from the queue which has been removed in the process

[tonton81]

Good evening, what should we call the queue lookup updater? I'm currently testing it with a random method name, called match(T *buffer, uint16_t length, int pos1, int pos2, int pos3, int pos4 = -1, int pos5 = -1);

Yeah I'm crazy but I like making crazy code! The method is independant of the other functions of circular buffer so nothing else needs to change, here is a sample of what it does
theres 5 (Type(8,16,32)) positions you could match against, with 3 inputs minimum required, once a match is found, the queue position will be overritten with the buffer, provided the match is a success

So, lets demonstrate an example:

#include "circular_buffer.h"
Circular_Buffer<uint8_t, 10, 6> ca;

void setup() {
  Serial.begin(1);
  while (!Serial);
  Serial.println("----------------------");

  uint8_t buf[6] = { 0, 1, 2, 3, 4, 5 };
  uint8_t buf1[6] = { 6, 7, 8, 9, 10, 11 };
  uint8_t buf2[6] = { 12, 13, 14, 15, 16, 17 };
  uint8_t buf3[6] = { 18, 19, 20, 21, 22, 23 };
  uint8_t buf4[6] = { 24, 25, 26, 27, 28, 29 };
  ca.push_back(buf, 6);
  ca.push_back(buf1, 6);
  ca.push_back(buf2, 6);
  ca.push_back(buf3, 6);
  ca.pop_front();
  ca.pop_front();
  ca.push_back(buf4, 6);
  ca.push_back(buf, 6);
  ca.push_back(buf1, 6);
  ca.push_back(buf, 6);
  ca.push_back(buf1, 6);

  Serial.println(ca.size());

  uint8_t buft[6] = { 18, 19, 20, 77, 9, 23 };
  ca.match(buft, 6, 0, 5, 2);


}


void loop() {

}

Theres 10 arrays assigned of 6 bytes, i start off by adding queues, removing 2 items, and readding more, then I test out the new method. Keep an eye on the red code

Heres the output (with debugging enabled):

----------------------
7

Displaying current queue: 
0 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 
0 1 2 3 4 5 
6 7 8 9 10 11 

Displaying updated queue: 
0 1 2 3 4 5 
6 7 8 9 10 11 
12 13 14 15 16 17 
18 19 20 77 9 23 
24 25 26 27 28 29 
0 1 2 3 4 5 
6 7 8 9 10 11

both buffers positions match (0, 2, and 5, order is irrelevant), so buffer is memmoved into it's place

How crazy am I now?

If you have buffers queuing for devices requiring waiting for ACKs, this should keep your queues happily updated, without creating duplicates wasting precious queue space

Any takers on the method name? It's got more spunk than just being "match"

That display debug code will be remove, i cant leave that in the library, i just temporarily put it there for verification because only the library has access to the entire queue system, so couldnt do it via sketch
Now I see it working, I dont need those prints

I might make the method a bool as well, returning 1 if a match was updated, or 0 if no matches

While I'm at it, I could also make a queue printer using that debug code, that dumps all your queue data to serial monitor, so you can see "whats in your queue"
I'd need a method name for that too

[mjs513]

Ok, not very original but about just qMatch or qmatchMaker. for the printer dump qView

EDIT: You know you probably half way just to write a method to qLogger No further comment

[defragster]

Looking for first use - in the code I see this:

T Circular_Buffer<T,_size,multi>::pop_back() {
  _available--;

What happens when 0 == _available on entry?

[tonton81]

like all c++ features, you check size before you —, this removes overhead, and is very known, user should know this

[tonton81]

nevermind, i understand what you mean, ill fix that after the MST, it should remain 0.. actually ill be home in 2-3 hours, ill fix that before i work on mst

[tonton81]

added commit

https://github.com/tonton81/Circular...161e1ea24960e2

[tonton81]

Good evening everyone. Theres been a major update and change as well as additional features to the library, that I'm sure you all might enjoy!

The array queue system had a bug with the incremental system, so I did a total redesign that makes it work perfectly.
There have been additional features implemented as well, MUCH more stable, pretty solid

Lots of new methods have been added, including a smart "replace" method:

        T capacity() { return _size; }
+        T length_back() { return _cabuf[(tail-1)&(_size-1)][0]; }
+        T length_front() { return _cabuf[_cbuf[(head)&(_size-1)]][0]; }
+        T list();
+        T max_size() { return multi; }
+        T pop_back(T *buffer, uint16_t length);
+        T* peek_front() { return front(); } 
+        T* peek_back() { return back(); } 
+        T* front() { return _cabuf[_cbuf[(head)&(_size-1)]]+1; }
+        T* back() { return _cabuf[(tail-1)&(_size-1)]+1; }
+        bool replace(T *buffer, uint16_t length, int pos1, int pos2, int pos3, int pos4 = -1, int pos5 = -1);

The new system is aware of the array sizes you write to the circular array system. To get the raw array size, you call max_size(), to get the actual array data size, you call length_front() or length_back()
pop_back(buf,len) was added for LIFO support. The buffer push/popping is very fast!
list() is a visual perspective of whats in your queue, printed to teensy's Serial interface, without displaying the garbage of the raw storage container, only displaying actual array data input.
peek() is used for ring buffer uses, peek_front() and peek_back() is used for circular array system, they are same as calling STL's front() and back() methods

replace is a very nice feature, it can compare and replace between 3 MIN to 5 MAX array indexes without modifying the head or tail, this is good for user code that constantly writes to the array system, where an update to an existing queue is preferred over a double queue

Example, if we take this simple code:

  Serial.println("----------------------");

  Circular_Buffer<uint8_t, 64, 10> k;
  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 };

  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("Q Size: "); Serial.println(k.size());
  uint8_t bufme[] = { 6, 19, 20, 21, 88, 64, 33, 54, 88 };
  k.list();
  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

the output:

----------------------
Q Size: 4
Queue Size: 4, Index order: 0 1 2 3 
First Entry: 0 1 2 3 4 5 (6 entries.)
Last Entry: 18 19 20 21 22 23 (6 entries.)

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

Queue Size: 4, Index order: 0 1 2 3 
First Entry: 0 1 2 3 4 5 (6 entries.)
Last Entry: 6 19 20 21 88 64 33 54 88 (9 entries.)

Queue list: 
0) 0 1 2 3 4 5 (6 entries.)
1) 6 7 8 9 10 11 (6 entries.)
2) 12 13 14 15 16 17 (6 entries.)
3) 6 19 20 21 88 64 33 54 88 (9 entries.)

as you can see, the internal queue was updated accordingly

capacity() method gets you the total queue storage available in your queue, ex, to get remaining:

int queue_entries_left;
queue_entries_left = ( Q.capacity() - Q.size() );

Also, if you write past the full state, the head and tail are pushed forward and the oldest element is overwritten

[turtle9er]

Been following this thread, however still waiting to use it when school is done in a month and can get back to projects. Just letting you know so you don't lose interest.....and really I am waiting to see if someone comes up with a logging to SD card system using your circular buffers.

[tonton81]

turtl9er, although i havnt played with SD cards yet, the behaviour of either the built in circular ring or array buffer should be capable, im sure if i have the time to learn the SD code me or someone will provide an example, it shouldnt be anymore different than using a normal array system, but will see how the near future plans out. The library has grown quite a lot of new set of features currently undocumented that many people will admire and probably use. Will try to document them this week. They will truely show the potential of what the library will be capable of, with great simplicity in usercode.

Thank you for your feedback
Tony

[defragster]

Tonton81 - perhaps you could try modifying this example - ...\libraries\SdFat\examples\LowLatencyLogger

There are two other variants of LowLatencyLogger there. The CircularBuffer or CA? should map in perfectly and manage the byte counting and 'buffer' transition

Perhaps a CB version method [ SpillWrite() ] where the B's are 512 bytes long and when it overflows one it auto indexes to the next. Then the 'Reader to SD' looks for a filled 512 buffer to transfer and remove?

[tonton81]

yes i could write that feature if necessary

[defragster]

yes i could write that feature if necessary

I knew that - might be the perfect way to get CB exposure and also let more folks use their SD cards. And use their SD cards with SPI_MSTransfer to one or more slaves - as long as the Slave SPI interrupts don't mess with the SD writing.

[tonton81]

hey i made i2c work didnt i lol

[mjs513]

tonton81 - you are the man

[mjs513]

Started playing with your posted circular buffer examples and ran into problem I was running the replace example you posted and that worked like a charm for

k.replace(bufme, sizeof(bufme), 1, 2, 3);

but if I changed it to run

k.replace(bufme, sizeof(bufme), 2, 3);

it throws the following error:

CB_replace_func:24: error: no matching function for call to 'Circular_Buffer<unsigned char, 64u, 10u>::replace(uint8_t [9], unsigned int, int, int)'

Does this mean that the minimum number for the test is 3 and the maximum is 5?

[tonton81]

yes, 3 minimum, 5 max, but you can "trick it", each value is an index, if you want 2 values only, repeat it:

compare one field:

k.replace(bufme, sizeof(bufme), 1, 1, 1);

compare 2 fields:

k.replace(bufme, sizeof(bufme), 1, 2, 2);

compare 3 fields.... etc
order doesnt matter btw:

k.replace(bufme, sizeof(bufme), 2, 1, 3);

I use the "trick" method when comparing only 2 fields for a match

[mjs513]

That's good to know. Told you I was going to start playing around with it

[tonton81]

I knew the question would creep up eventually

[mjs513]

So, guess I am the eventually Told you I was going to work on examples since I am learning. Anyway seem to be having a problem with replace on 2. The third example looks at indices 5 and 6 of bufme and should replace the bufc2 elements but doesn't, what did I do wrong?
Sketch:

#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");
  k.replace(bufme, sizeof(bufme), 5, 6, 6);  // 2 fields
  k.list(); 

}

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

}

Output:

----------------------
Initial Q Size: 64
After Init, Q Size: 4
Queue Size: 4, Index order: 0 1 2 3 
First Entry: 0 1 2 3 4 5 (6 entries.)
Last Entry: 18 19 20 21 88 23 (6 entries.)

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

Example of replace with 3 indicies
Queue Size: 4, Index order: 0 1 2 3 
First Entry: 0 1 2 3 4 5 (6 entries.)
Last Entry: 6 19 20 21 88 12 13 4 5 (9 entries.)

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

Example to replace based on 1 field
Queue Size: 4, Index order: 0 1 2 3 
First Entry: 0 1 2 3 4 5 (6 entries.)
Last Entry: 6 19 20 21 88 12 13 4 5 (9 entries.)

Queue list: 
0) 0 1 2 3 4 5 (6 entries.)
1) 6 19 20 21 88 12 13 4 5 (9 entries.)
2) 12 13 14 15 16 17 (6 entries.)
3) 6 19 20 21 88 12 13 4 5 (9 entries.)

Example to replace based on 2 fields
Queue Size: 4, Index order: 0 1 2 3 
First Entry: 0 1 2 3 4 5 (6 entries.)
Last Entry: 6 19 20 21 88 12 13 4 5 (9 entries.)

Queue list: 
0) 0 1 2 3 4 5 (6 entries.)
1) 6 19 20 21 88 12 13 4 5 (9 entries.)
2) 12 13 14 15 16 17 (6 entries.)
3) 6 19 20 21 88 12 13 4 5 (9 entries.)

[tonton81]

 uint8_t bufme[] = { 6, 19, 20, 21, 88, 12, 13, 4, 5 };

indices 5 and 6 are 12 and 13 respectively. you have no items in your queue where the 5th and 6th positions match.....

0) 0 1 2 3 4 5 (6 entries.)
1) 6 7 8 9 10 11 (6 entries.)
2) 12 13 14 15 16 17 (6 entries.)
3) 18 19 20 21 88 23 (6 entries.)


Or this?

Queue list:
0) 0 1 2 3 4 5 (6 entries.)
1) 6 19 20 21 88 12 13 4 5 (9 entries.)
2) 12 13 14 15 16 17 (6 entries.)
3) 6 19 20 21 88 12 13 4 5 (9 entries.)

this is because the first match after the 2nd test matched the first entry as 0,0,0 both are 6.....

so on the 3rd test (2 indices) you already had 2 queues the same, but if you keep that up, only the 1st found item is replaced, not all of them..