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.

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.

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.

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;