8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "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)? \$\endgroup\$ – chux - Reinstate Monica Mar 18 '16 at 19:55
  • \$\begingroup\$ Why isn't circularBuffer_peakHead() just return buf->isEmpty ? NULL : buf->data + buf->headOffset * buf->elementSize;? \$\endgroup\$ – chux - Reinstate Monica Mar 18 '16 at 20:44
  • \$\begingroup\$ Minor point, the word you want is 'peek' not 'peak'. \$\endgroup\$ – William Morris Mar 21 '16 at 23:20
4
\$\begingroup\$
  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.

\$\endgroup\$
  • \$\begingroup\$ 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 :) \$\endgroup\$ – LastSecondsToLive Mar 18 '16 at 22:38
  • \$\begingroup\$ 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? \$\endgroup\$ – LastSecondsToLive Mar 19 '16 at 8:39
  • \$\begingroup\$ @LastSecondsToLive For #9, struct circularBuffer *tmp = calloc(1, sizeof *tmp + numElements * elementSize); tmp->data = &tmp[1]; \$\endgroup\$ – chux - Reinstate Monica Mar 19 '16 at 16:24
  • \$\begingroup\$ @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. \$\endgroup\$ – chux - Reinstate Monica Mar 19 '16 at 16:28
  • \$\begingroup\$ Thanks, very interesting - never heard of it before, but I'm relatively new to C, so I guess that's fine... \$\endgroup\$ – LastSecondsToLive Mar 19 '16 at 17:22
4
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – LastSecondsToLive Mar 17 '16 at 23:10
  • \$\begingroup\$ @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. \$\endgroup\$ – vnp Mar 17 '16 at 23:16
  • \$\begingroup\$ Okay, I'll keep it up, wait a couple more hours, rewrite a better version and may do a follow up :) \$\endgroup\$ – LastSecondsToLive Mar 17 '16 at 23:18
2
\$\begingroup\$

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;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.