Creating Circular Buffer lib

Hi all,

I am trying to create a circular buffer library that I can use to queue tasks in Arduino. The idea is that the buffer will contain chars and each function that needs to be executed will map to a specific char. (Please tell me if there is a better way to do this!)

To create the buffer I devoted the entirety of the last 4 evenings to try to recreate the code from Circular buffer - Wikipedia into the Arduino IDE.

Thanks to tips found online, I have put the typedef into a separate .h so this works correctly now.

I haven't managed to make it compile when I try to put the functions in a library. All examples I have found online for creating libraries are using C++ so I have tried to convert the functions to C++ but did not manage to get it to compile.

If I keep all the functions in the main program (instead of in a separate library) I have managed to make it compile, but my function to add tasks to the buffer did not work from what I could tell. If I try different combinations of addresses or pointers to pass to the function to add tasks to the buffer it inevitably fails to compile OR the tasks do not get added if it does compile.

Does anybody have any tips for creating C libraries?
How should I pass inputs to the functions outlined in the wiki article?

Any help would be massively appreciated!! This has been driving me crazy!

Many thanks in advance,

Nick

http://arduino.cc/forum/index.php/topic,97455.0.html
In particular, read item 6.

After reading that, read this.

nick_p:
Does anybody have any tips for creating C libraries?

Get the code working right in a plain old sketch before you try to extract it into a library.

Yes I have read those; as mentioned the tutorial is for C++ but my library should be only in C.

The reason I wanted to create the library is that I have also read that void functions need to be put in a separate library, especially if they should take custom data types as inputs.

It's weekend now and I have other commitments but I will try to upload code so that at least I can get the functions working correctly.

Meanwhile, if somebody has managed to get the code from wikipedia to compile -- first of all, congrats! -- please share 8)

Thanks for your help!

Sketch:

#include "circularbuffer.h"

CircularBuffer cb;


void setup() {
    Serial.begin(115200);
    ElemType elem = {0};
 
    int testBufferSize = 10; /* arbitrary size */
    cbInit(&cb, testBufferSize);
 
    /* Fill buffer with test elements 3 times */
    for (elem.value = 0; elem.value < 3 * testBufferSize; ++ elem.value)
        cbWrite(&cb, &elem);
 
    /* Remove and print all elements */
    while (!cbIsEmpty(&cb)) {
        cbRead(&cb, &elem);
        Serial.println(elem.value);
    }
 
    cbFree(&cb);
    
}

void loop()
{
    
}

Header file:

#ifndef CIRCULARBUFFER_H
#define CIRCULARBUFFER_H

#include <stdlib.h>

struct ElemType{ int value; };
 
/* Circular buffer object */
struct CircularBuffer{
    int         size;   /* maximum number of elements           */
    int         start;  /* index of oldest element              */
    int         end;    /* index at which to write new element  */
    ElemType   *elems;  /* vector of elements                   */
};
 

void cbInit(CircularBuffer *cb, int size) {
    cb->size  = size + 1; /* include empty elem */
    cb->start = 0;
    cb->end   = 0;
    cb->elems = (ElemType *)calloc(cb->size, sizeof(ElemType));
}
 
void cbFree(CircularBuffer *cb) {
    free(cb->elems); /* OK if null */ }
 
int cbIsFull(CircularBuffer *cb) {
    return (cb->end + 1) % cb->size == cb->start; }
 
int cbIsEmpty(CircularBuffer *cb) {
    return cb->end == cb->start; }
 
/* Write an element, overwriting oldest element if buffer is full. App can
   choose to avoid the overwrite by checking cbIsFull(). */
void cbWrite(CircularBuffer *cb, ElemType *elem) {
    cb->elems[cb->end] = *elem;
    cb->end = (cb->end + 1) % cb->size;
    if (cb->end == cb->start)
        cb->start = (cb->start + 1) % cb->size; /* full, overwrite */
}
 
/* Read oldest element. App must ensure !cbIsEmpty() first. */
void cbRead(CircularBuffer *cb, ElemType *elem) {
    *elem = cb->elems[cb->start];
    cb->start = (cb->start + 1) % cb->size;
}

#endif

but my library should be only in C.

Why?

The reason I wanted to create the library is that I have also read that void functions need to be put in a separate library, especially if they should take custom data types as inputs.

This is crap. Functions of any type, taking any kind of values, can be in the sketch with the loop() and setup() functions. A library is to make code reusable.

Meanwhile, if somebody has managed to get the code from wikipedia to compile -- first of all, congrats! -- please share

You could go the other way, and post your code (you admit that you read that you were supposed to) and post the error messages.

I've done this type of thing many times in embedded environments over the past few decades.
The thing to think about is what information needs to be in the Q.
For example, rather than have a token to indicate the function, it could be a pointer to the actual function.
Then does the function need any sort of context argument?
i.e. maybe you want to call the same function with some sort of context or instance information.

I finally ended up using function pointers and a void pointer as an argument to the function for each Q entry.
I also used a "magic" function pointer of -1 to indicate that the argument is a pointer to
an integer that should be increment rather being an argument to a function to be called.
There are some interesting things you can do with the mechanism especially if there is a timer/timeout
mechanism that uses the same Qs. (It allows easy timeout processing in foreground routines).

The thing to really weigh in the AVR environment is the trade off between RAM usage and flash usage
and the realtime needs of processing the Q.
For example, if the number of different functions to call is quite large and the Q contains a token,
then not only does it consume extra code but it can take additional time to do the translation
if a lookup table is not used. However, on the AVR if you use a lookup table, that consumes RAM by default.
RAM is quite precious on the AVR chips.
If you convert it to use PROGMEM instead, then it no longer uses RAM for the lookup but takes longer to perform the lookup.

If you don't use a token and use function pointers, then each entry needs 2 bytes per function pointer vs 1
when it is token. However, the processing time to get an entry from the Q and call the function will be
much shorter.
But if you have lots of entries in the Q, then the RAM use can be an issue.

It all comes down to trade-offs. What works "best" is really just a compromise that fits best into the
environment.

As far is getting the Q'ing code up and debugged. I'd write it and debug in on a bigger machine.
i.e. PC/MAC Unix/Linux machine where there are good debug tools. If the code is all in C it can be made
to be 100% portable and you will spend very little time (if any) having to fight logic/coding issues in the
Arduino environment (which has very limited debugging tools).

--- bill

Thank you all for your responses.

I have managed to make the code compile but the program is not working as expected. Or rather, at all.
I think tasks are not getting added to the queue because queueIsEmpty always returns True -- I think I have some pointers and addresses that are being passed to functions mixed up, but my programming is not so strong.

Bill, could you recommend any debug tools? I have Linux at home and Windows at work. No Mac though.
From what I understand from your post, I will need to consider a trade-off between using a handful of big functions (slower execution), or to use lots of small functions (lots of memory).

My intention is to use this as a basis for UAV controller. Therefore, the main tasks in the queue would be:
Read data --> Filter & Processing --> Estimator --> PID --> Output

The sensors I have are on I2C which are pretty slow to update (e.g. 100 Hz). My assumption (hope) is that the Estimator-->PID-->Output loop will execute much faster so I can run this several times before data is available on I2C. The 'Read data' task could be scheduled to run every nth cycle or else be scheduled by an interrupt.

If my assumption is incorrect and the data update rate is not a limiting factor, it would make the task vastly simpler because the loop would reduce to:
Read data --> Filter & Processing --> PID --> Output

After Output, the loop can then just wait until data is available.

Below is the datastructures.h file:

typedef struct 
{
  int size;   
  int head;  
  int count;
  char *tasks;  
} queue;

Here is the main program, including the (currently non-functional) queue functions:

//#include <malloc.h>
#include "datastructures.h"

queue testqueue; //create queue
char currenttask;
char addtask;
char resettask = 1;

void setup() {
  queueInit(&testqueue, 8);
  addtask = 'a';
  queueAdd(&testqueue, &addtask);
  
  Serial.begin(9600);
}

void loop() {
  
  if (!queueIsEmpty){
    queueGetTask(&testqueue, &currenttask);
    queueExecuteTask(&testqueue, &currenttask);
  }
  
  addtask = 'b';
  
  if (queueIsFull) queueFree(&testqueue);
  else queueAddFront(&testqueue, &addtask); 
 
  if (!queueIsEmpty){
    queueGetTask(&testqueue, &currenttask);
    queueExecuteTask(&testqueue, &currenttask);
  }
  
  // As an alternative to checking !queueIsEmpty before get & execute next task,
  // we can assume something went wrong if the queue is empty at the end of the
  // main loop, so we can add a 'reset' task to the queue to be executed next.
  // This implies that tasks must add themselves or another task upon completion.
  if (queueIsEmpty) queueAdd(&testqueue, &resettask);
  
}

/******************************************************************/
/*                    Task Queue functions                        */
/******************************************************************/

void queueInit(queue *q, int size) {
  q->size = size;
  q->head = 0;
  q->count = 0;
  q->tasks = (char *)calloc(q->size, sizeof(char)); }

void queueFree(queue *q) {
  free(q->tasks); }

int queueIsFull(queue *q) {
  return q->count == q->size; }
 
int queueIsEmpty(queue *q) {
  return q->count == 0; }
    
int queueDuplicateExists(queue *q, char *task) {
  for (int i=0; i < q->count; i++) {  //loop is skipped if queue is empty
    if (*task == q->tasks[i]) return 1; } //true 
  return 0; } //false
 
// Since nothing is returned, app must check if !queueIsFull() before attempting to add task
// otherwise it cannot know if Add was successful
void queueAdd(queue *q, char *task) {
  if (queueDuplicateExists) return;
  if (queueIsFull) return;   
  else {
      int tail = (q->head + q->count) % q->size;
      q->tasks[tail] = *task;
      ++ q->count; } }

void queueAddFront(queue *q, char *task) {
  if (queueDuplicateExists) return;
  if (queueIsFull) return;   
  else {
      q->tasks[(q->head - 1) % q->size] = *task; 
      q->head -- % q->size;
      ++ q->count; } }
 
// App must ensure !queueIsEmpty() first!!
void queueGetTask(queue *q, char *task) {
    *task = q->tasks[q->head];
    q->head = (q->head + 1) % q->size;
    -- q->count; }

void queueExecuteTask(queue *q, char *task) {
 
  switch (*task) {
    case 'a':
    Serial.println("function 'a' was called");
    case 'b':
    Serial.println("fucntion 'b' was called");
    
    case 127:
    queueAdd(q, &resettask); // special reset task to be added in case queue is unexpectedly empty at end of main loop
                             // e.g. set char resettask = 'a' to start from that function again    
  }

  
}

If anybody can spot my mistake(s) or suggest any good debugging tools on Win or Linux that will allow me to debug this application better, please let me know.

queueIsEmpty and queueIsFull are both functions, each taking a single parameter that is a pointer to a queue.

if (!queueIsEmpty)

isn't going to work, because you are not calling the function properly. You need to call it like this:

if (!queueIsEmpty(&testqueue))

same with queueIsFull().

ditto for your usage of queueDuplicateExists as well.

Oops - thanks for pointing those out.

I had already corrected those mistakes but the code was very messy because I was trying different things so I pasted an earlier 'clean' version.

My main concern is with the functions that add & read to/from the queue -- those currently don't work I don't think. Has anybody spotted the mistake in those?

Actually, I'm having a little trouble passing on arguments to an function called inside another one...

void queueAdd(queue *q, char *task) {
  if (queueDuplicateExists) return;
  if (queueIsFull) return;   
  else {
      int tail = (q->head + q->count) % q->size;
      q->tasks[tail] = *task;
      ++ q->count; } }

How can I correctly pass the queue to the test functions inside the queueAdd function?

nick_p:
Bill, could you recommend any debug tools? I have Linux at home and Windows at work. No Mac though.

For debugging I write the code on a platform with the best debug tools.
It is worth the time to get source level debugging up and working.

Currently I use linux to get the logic debugged then move it to the AVR.
I use command-line gdb on linux for source level debugging.
gdb is nice because it works on pretty much everything including
embedded environments once you have the proper gdb interfaces set up.
I like gdb because it means only one environment to learn. (been using it for about 25 years)
There are some GUI wrappers and full IDEs like eclipse but I still use the command-line
as the command-line works the same everywhere.

From what I understand from your post, I will need to consider a trade-off between using a handful of big functions (slower execution), or to use lots of small functions (lots of memory).

No. The trade off I was referring to was between RAM usage for Q entries
and function call latency. i.e. the amount of time it takes to figure out
what function to call once the entry is pulled from the Q not the functions themselves.
The code you have now is using a case statement to figure out what function to call based on a "char" token.
As the number of functions increases, this method becomes less efficient, requiring more code and taking more time.
If the Q entries contained a function pointer instead, then there is no additional code to figure out what function
to call, and the code size and latency is a constant no matter how many functions are being used.
In the situations where I needed to do this in the past,
I also needed some context information, so my Q entries contained a function pointer and an argument.
Each function then received a single argument.
This allows doing things like scheduling the same function but with a different argument to be able to deal with say
multiple instances of something.
It would use the Q mechanism to Q tasks from the ISRs.
I've also had systems that had multiple Qs (usually 2) so that there could be a high priority Q and a low priority Q.

When using this mechanism, the idle loop did nothing more than process the Qs.
Everything else was scheduled through the Qs.
Essentially it is callback Q. And the idle loop runs the Q(s) and processes
all the callbacks.

--- bill

nick_p:
Actually, I'm having a little trouble passing on arguments to an function called inside another one...

void queueAdd(queue *q, char *task) {

if (queueDuplicateExists) return;
  if (queueIsFull) return;   
  else {
      int tail = (q->head + q->count) % q->size;
      q->tasks[tail] = *task;
      ++ q->count; } }




How can I correctly pass the queue to the test functions inside the queueAdd function?

If you're trying to call a function or method, you need to put parentheses () after the function/method name.

The logic you have there to check for duplicates and queue full conditions and increment pointers and so on would IMO be much better encapsulated into a CircularBuffer class rather than as a struct with separate independent functions.

Thanks, I had tried that before but my syntax was incorrect.

It works now :slight_smile:

Thank you everyone for your help.

For anyone interested, below is the code:

//#include <malloc.h>
#include "datastructures.h"

queue testqueue; //create queue
char currenttask;
char addtask;
char resettask = 1;

void setup() {
  queueInit(&testqueue, 8);
  addtask = 'a';
  queueAdd(&testqueue, &addtask);
  
  Serial.begin(9600);
}

void loop() {
  
  if (!queueIsEmpty(&testqueue)){
    queueGetTask(&testqueue, &currenttask);
    queueExecuteTask(&testqueue, &currenttask);
  }
  
  addtask = 'b';
  
  if (queueIsFull(&testqueue)) queueFree(&testqueue);
  else queueAddFront(&testqueue, &addtask); 
 
  if (!queueIsEmpty(&testqueue)){
    queueGetTask(&testqueue, &currenttask);
    queueExecuteTask(&testqueue, &currenttask);
  }
  
  // As an alternative to checking !queueIsEmpty before get & execute next task,
  // we can assume something went wrong if the queue is empty at the end of the
  // main loop, so we can add a 'reset' task to the queue to be executed next.
  // This implies that tasks must add themselves or another task upon completion.
  if (queueIsEmpty(&testqueue)) queueAdd(&testqueue, &resettask);
  
}


/******************************************************************/
/*                    Task Queue functions                        */
/******************************************************************/

void queueInit(queue *q, int size) {
  q->size = size;
  q->head = 0;
  q->count = 0;
  q->tasks = (char *)calloc(q->size, sizeof(char)); }

void queueFree(queue *q) {
  free(q->tasks); }

int queueIsFull(queue *q) {
  return q->count == q->size; }
 
int queueIsEmpty(queue *q) {
  return q->count == 0; }
    
int queueDuplicateExists(queue *q, char *task) {
  for (int i=0; i < q->count; i++) {  //loop is skipped if queue is empty
    if (*task == q->tasks[i]) return 1; } //true 
  return 0; } //false
 
// Since nothing is returned, app must check if !queueIsFull() before attempting to add task
// otherwise it cannot know if Add was successful
void queueAdd(queue *q, char *task) {
  if (queueDuplicateExists(q, task)) return;
  if (queueIsFull(q)) return;   
  else {
      int tail = (q->head + q->count) % q->size;
      q->tasks[tail] = *task;
      ++ q->count; } }

void queueAddFront(queue *q, char *task) {
  if (queueDuplicateExists(q, task)) return;
  if (queueIsFull(q)) return;   
  else {
      q->tasks[(q->head - 1) % q->size] = *task; 
      q->head -- % q->size;
      ++ q->count; } }
 
// App must ensure !queueIsEmpty() first!!
void queueGetTask(queue *q, char *task) {
    *task = q->tasks[q->head];
    q->head = (q->head + 1) % q->size;
    -- q->count; }

void queueExecuteTask(queue *q, char *task) {
 
  switch (*task) {
    case 'a':
    Serial.println("function 'a' was called");
    case 'b':
    Serial.println("function 'b' was called");
    
    case 127:
    queueAdd(q, &resettask); // special reset task to be added in case queue is unexpectedly empty at end of main loop
                             // e.g. set char resettask = 'a' to start from that function again    
  }

  
}


/* function that returns free Ram on the device
int freeRam () {
  extern int __heap_start, *__brkval; 
  int v; 
  return (int) &v - (__brkval == 0 ? (int) &__heap_start : (int) __brkval); 
}
*/