Circular Buffer

Question

For my current project I need a circular buffer, which is able to do the following things:

• Push something to it (to the head).
• Pop something from it (from the tail). I don't need the popped data.
• Peak the head and tail (no popping).
• Iterate through the currently contained elements.

Here is my C implementation.

circularBuffer.h:

#ifndef CIRCULAR_BUFFER_H
#define CIRCULAR_BUFFER_H
#include <stdlib.h>
#include <stdbool.h>
struct circularBuffer {
 void *data; // Holds the buffer data.
 size_t headOffset; // The next position the buffer will write to.
 size_t tailOffset; // The position of the buffer tail.
 size_t elementSize; // Size of one element contained in the buffer.
 size_t numElements; // Number of elements the buffer is able to hold at once.
 bool isEmpty; // Flag, which holds, whether the buffer is empty. 
 // Allows to fill the whole buffer without losing the ability 
 // to determine, whether its empty or not.
};
struct circularBuffer *circularBuffer_create(size_t numElements, size_t elementSize);
// Push/Pop
void circularBuffer_push(struct circularBuffer *buf, void *ptr);
int circularBuffer_popTail(struct circularBuffer *buf);
// Get data
size_t circularBuffer_containedCount(struct circularBuffer *buf);
void *circularBuffer_peakTail(struct circularBuffer *buf);
void *circularBuffer_peakHead(struct circularBuffer *buf);
#endif /* !defined CIRCULAR_BUFFER_H */

circularBuffer.c:

#include <string.h>
#include <stdio.h>
#include "circularBuffer.h"
struct circularBuffer *circularBuffer_create(size_t numElements, size_t elementSize) {
 struct circularBuffer *tmp = calloc(1, sizeof(struct circularBuffer));
 if (!tmp) { return NULL; }
 tmp->data = malloc(numElements * elementSize);
 if (!tmp->data) {
 free(tmp);
 return NULL;
 }
 tmp->numElements = numElements;
 tmp->elementSize = elementSize;
 tmp->isEmpty = true;
 return tmp;
}
void circularBuffer_push(struct circularBuffer *buf, void *ptr) {
 if (!buf->isEmpty && buf->headOffset == buf->tailOffset) {
 buf->tailOffset = (buf->tailOffset + 1) % buf->numElements;
 }
 memcpy(buf->data + buf->headOffset*buf->elementSize, ptr, buf->elementSize);
 buf->headOffset = (buf->headOffset + 1) % buf->numElements;
 buf->isEmpty = false;
}
void *circularBuffer_peakTail(struct circularBuffer *buf) {
 return buf->isEmpty ? NULL : buf->data + buf->tailOffset * buf->elementSize;
}
void *circularBuffer_peakHead(struct circularBuffer *buf) {
 if (buf->isEmpty) { return NULL; }
 else if (buf->data + buf->headOffset != 0) { return buf->data + (buf->headOffset-1) * buf->elementSize; } 
 else { return buf->data + (buf->numElement-1) * buf->elementSize; }
}
int circularBuffer_popTail(struct circularBuffer *buf) {
 if (buf->isEmpty) { return 0; } // Empty buffer.
 buf->tailOffset = (buf->tailOffset + 1) % buf->numElements; 
 if (buf->tailOffset == buf->headOffset) { 
 buf->isEmpty = true; 
 }
 return 1;
}
size_t circularBuffer_containedCount(struct circularBuffer *buf) {
 if (buf->isEmpty) { return 0; }
 else if (buf->tailOffset < buf->headOffset) { return buf->headOffset - buf->tailOffset; }
 else if (buf->tailOffset == buf->headOffset) { return buf->numElements; }
 else return buf->numElements - buf->tailOffset + buf->headOffset;
}

Notes: I explicitly didn't check whether the buffer pointer is NULL in every function. The user should take care of it.

This basic implementation allows me to do everything I listed above quite nicely I think. Is there anything I could do better according performance? I'll probably use this pretty heavily.

• chux: "better according performance?" --> Is that only execution performance (faster better) or are you considering memory usage performance (lower better) or maintenance (simple better) or portability (more standard better)?
• chux: Why isn't circularBuffer_peakHead() just return buf->isEmpty ? NULL : buf->data + buf->headOffset * buf->elementSize;?
• William Morris: Minor point, the word you want is 'peek' not 'peak'.

Answer 1

1. Overall fairly good. Good use of size_t, naming conventions and portability.

2. 6.1 vs half-dozen the other idea. Consider size_t UsageCount vs. bool isEmpty. This value is a direct report of count of elements eliminating size_t circularBuffer_containedCount() as a function. IMO, it will make other parts of code simpler too.

   #define circularBuffer_containedCount(buf) (buf->UsageCount)
   #define circularBuffer_isEmpty(buf) (buf->UsageCount == 0)
   #define circularBuffer_isFull(buf) (buf->UsageCount >= buf->numElements)
   

3. Making implementation private. (Especially if you do no go for idea #2.) Only define struct circularBuffer in the .c file. In the .h, just declare the pointer struct circularBuffer *.

4. Missing function: To complement circularBuffer_create(), I'd expect circularBuffer_destroy()

5. Functions that do not alter buf should have const in their signature to help show that and to enforce it.

   // circularBuffer_peakHead(struct circularBuffer *buf)
   circularBuffer_peakHead(const struct circularBuffer *buf)
   

6. Agree with @vnp about code problem. Alternative solution: add cast. I like the visible portion of code (header file) using void *data.

   //buf->data + buf->headOffset != 0
   (char *) buf->data + buf->headOffset != 0
   

7. Minor: circularBuffer_create() omits the explicit initialization of some fields counting on calloc() to do the zero fill. I'd rather see the explicit initialization.

8. Minor: for debugging purposes, suggest calloc(numElements, elementSize); rather than malloc() as it s nice to have all the allocated memory in a known state. It also has a benefit on the rare machine where numElements * elementSize overflows, yet calloc() would work.

9. Thought: circularBuffer_create() does 2 allocations. It could do only 1 and then segment the parts. I'm on the fence as to the value of speed vs. clarity here.

10. Minor: Style: Recommend a bit more distinctiveness between functions that just a single empty line.

11. Symmetry in naming: use 1 pair or the other - suggest shorter pair

    circularBuffer_pushHead();
    circularBuffer_popTail();
    // or
    circularBuffer_push();
    circularBuffer_pop();
    // not 
    circularBuffer_push();
    circularBuffer_popTail();
    

12. circularBuffer_push() should not add data if buffer is full. Better to either return error code, fault, set errno, but do not overwrite data.

13. Use 0 or NULL, not both for the null pointer. I am suspicious about the functionality of circularBuffer_peakHead() if (buf->data + buf->headOffset != 0) looks odd.

14. if (!tmp->data) is only a problem if numElements * elementSize is non-zero. Strange to have elementSize of zero, but no real reason to disallow it. On the other hand, if code passed in numElements == 0, that is more difficult to handle with other code like % buf->numElements.

• LastSecondsToLive: Wow, so many great ideas. I wasn't thinking that so much could be made clearer/better. Thank you! The only thing I won't change is point 12. I explicitly need the behavior to override the old data, if new data arrives. Maybe I'll add a boolean return value to report, whether something was overwritten though. Thanks again :)
• LastSecondsToLive: And how would I handle 9.? I was thinking about an array in the structure, but since I don't know the size, this won't work. How is this normally done?
• chux: @LastSecondsToLive For #9, struct circularBuffer *tmp = calloc(1, sizeof *tmp + numElements * elementSize); tmp->data = &tmp[1];
• chux: @LastSecondsToLive A different way to do this since C99 is with flexible array member which is an indefinite sized array at the end of a structure.
• LastSecondsToLive: Thanks, very interesting - never heard of it before, but I'm relatively new to C, so I guess that's fine...

Answer 2

• void * data;

  results in the

  warning: arithmetic on a pointer to void is a GNU extension [-Wpointer-arith]
   memcpy(buf->data + buf->headOffset*buf->elementSize, ptr, buf->elementSize);
  

  For portability make it char * data;.

• Fail early

  If a condition

  buf->data + buf->headOffset != 0
  

  ever fails, the structure is badly corrupted. You should fail immediately, with as much noise as possible (the core dump suffices). In no case you can mask the problem.

• LastSecondsToLive: Do you mean the line in peak_Head? I think this is actually wrong and just buf->headOffset was meant. Do you want me to delete this post, overthink and ask again, because of broken code?
• vnp: @LastSecondsToLive It is totally up to you. For me, the code fits the CodeReview format perfectly well. You are also welcome to post the fixed version as a follow-up question.
• LastSecondsToLive: Okay, I'll keep it up, wait a couple more hours, rewrite a better version and may do a follow up :)

Answer 3

Modulo arithmetic might be expensive. Consider replacing:

buf->tailOffset = (buf->tailOffset + 1) % buf->numElements;

with something more along the form of:

if (++buf->tailOffset == buf->numElements) buf->tailOffset = 0;