Circular Buffer in C - Follow Up

Question

This is a follow up to this post I uploaded a few days back on my alternative account about a circular buffer in C. I'm confident that I fixed most of the warnings and even added an iterator.

circularBuffer.h

#ifndef CIRCULAR_BUFFER_H
#define CIRCULAR_BUFFER_H

#include <stddef.h>   // max_align_t in source

struct circularBuffer;

// circularBufferCreate: {{{
// Creates a new circularBuffer in memory and returns a pointer to it.
//
// @param capacity    The capacity of the new circularBuffer.
// @param elementSize The element size of the contained elements.
//                    Expected to be greater than zero.
//
// @return Pointer to the created circularBuffer in memory.
//         NULL on allocation fail or false arguments. }}}
struct circularBuffer *circularBufferCreate(size_t capacity, size_t elementSize);

// circularBufferDestroy: {{{
// Destroys the passed circularBuffer struct in memory.
//
// @param buf The circularBuffer, which is to be destroyed. }}}
void circularBufferDestroy(struct circularBuffer *buf);



// circularBufferCardinality: {{{
// Returns the current number of elements stored in the passed circularBuffer.
//
// @param buf Pointer to the circularBuffer to get cardinality from;
//
// @return The number of elements currently stored in the passed circularBuffer. }}}
size_t circularBufferCardinality(const struct circularBuffer *buf);

// circularBufferIsEmpty: {{{
// Checks whether a circularBuffer is empty.
//
// @param buf Pointer to the circularBuffer to check emptyness of (not NULL).
//
// @return Non-zero when empty, zero otherwise. }}}
int circularBufferIsEmpty(const struct circularBuffer *buf);

// circularBufferIsFull: {{{
// Checks whether a circularBuffer is full.
//
// @param buf Pointer to the circularBuffer to check fullness of (not NULL).
//
// @return Not zero when full, zero otherwise. }}}
int circularBufferIsFull(const struct circularBuffer *buf);



// circularBufferPushHead: {{{
// Pushes the data pointed to by ptr onto the circularBuffers head.
//
// @param buf CiruclarBuffer the data is pushed onto.
// @param ptr Data to be pushed. }}}
void circularBufferPushHead(struct circularBuffer *buf, void *ptr);

// circularBufferPopTail: {{{
// Pops current tail element of passed circularBuffer and returns pointer to it.
//
// @param buf circularBuffer, which tail should be popped (NON-NULL-REQUIRED).
//
// @return Pointer to popped data.
//         This pointer is only valid until the data is overwritten internally. 
//         For later use copying is necessary. }}}
char *circularBufferPopTail(struct circularBuffer *buf);


// circularBufferPeekHead: {{{
// Returns pointer to the current head element of the buffer.
//
// @param buf CircularBuffer, on which head a peek is wanted (NON-NULL-REQUIRED).
//
// @return Pointer to the current head of the passed circular buffer.
//         NULL in the case of an empty buffer.
// }}} 
const char *circularBufferPeekHead(const struct circularBuffer *buf);

// circularBufferPeekTail: {{{
// Returns pointer to the current tail element of the buffer.
//
// @param buf CircularBuffer, on which tail a peek is wanted (NON-NULL-REQUIRED).
//
// @return Pointer to the current tail of the passed circular buffer.
//         NULL in the case of an empty buffer.
// }}} 
const char *circularBufferPeekTail(const struct circularBuffer *buf);



struct circularBufferIterator;

// circularBufferIteratorCreate: {{{
// Creates a new circularBufferIterator in memory and returns a pointer to it.
//
// @return Pointer to the created circularBufferIterator in memory.
//         NULL on allocation. }}}
struct circularBufferIterator *circularBufferIteratorCreate();

// circularBufferIteratorDestroy: {{{
// Destroys the passed circularBufferIterator struct in memory.
//
// @param buf Pointer to the struct circularBufferIterator, 
//            which is to be destroyed. }}}
void circularBufferIteratorDestroy(struct circularBufferIterator *it);


// circularBufferIteratorPrepare: {{{
// Prepares passed iterator to iterate over the elements of passed buffer.
//
// @param it  CircularBufferIterator, which is about to get prepared.
// @param buf CircularBuffer, which should be iterated over by the iterator.
// }}}
void circularBufferIteratorPrepare(struct circularBufferIterator *it, const struct circularBuffer *buf);

// circularBufferIteratorNext: {{{
// Fetches the next element form the passed iterator. 
//
// @param it  CircularBufferIterator, which the next element should be fetched from.
//
// @return Pointer to the fetched data. May get overwritten by buffer at a later point in time.
//         Copying required for use parallel to the buffer.
// }}}
char *circularBufferIteratorNext(struct circularBufferIterator *it);

#endif /* !defined CIRCULAR_BUFFER_H */

circularBuffer.c

#include <string.h>     // memcpy
#include <stdlib.h>     // SIZE_MAX, calloc, free
#include <stdalign.h>   // alignas

#include "circularBuffer.h"

struct circularBuffer {
  size_t capacity;
  size_t cardinality;
  size_t alignElementSize;
  size_t originalElementSize;

  size_t headOffset;
  size_t tailOffset;

  alignas(max_align_t) char data[];
};

static inline size_t incrementIndex(const struct circularBuffer *buf, size_t index) {
  // Avoid expensive modulo arithmetic
  return (++index == buf->capacity) ? 0 : index;
}

struct circularBuffer *circularBufferCreate(size_t capacity, size_t elementSize) {

  if (elementSize == 0) {
    return NULL; 
  }

  size_t alignElementSize;
  if (elementSize >= sizeof(max_align_t)) { 
    // Least number of  blocks sizeof (max_align_t) where one element fits into.
    alignElementSize = (elementSize + sizeof (max_align_t) - 1) / sizeof (max_align_t) * sizeof(max_align_t);
  } else {
    alignElementSize = elementSize;
    // Find smallest int x >= 0 where (elementSize + x) divides sizeof (max_align_t) evenly.
    while (sizeof(max_align_t) % alignElementSize != 0) { alignElementSize++; }
  }

  if (SIZE_MAX / alignElementSize <= capacity ||
      SIZE_MAX - sizeof (struct circularBuffer) < capacity * elementSize) {
    return NULL;
  }

  // Do I need to take extra care of the initial alignment of buf->data[] at this point?
  // Or is the alignas(max_align_t) enough?
  struct circularBuffer *buf = calloc(1, sizeof (*buf) + alignElementSize * capacity);

  if (!buf) {
    return NULL;
  }

  buf->capacity = capacity;
  buf->cardinality = 0;
  buf->alignElementSize = alignElementSize;
  buf->originalElementSize = elementSize;

  buf->headOffset = 0;
  buf->tailOffset = 0;

  return buf;
}

void circularBufferDestroy(struct circularBuffer *buf) {
  free(buf);
}

size_t circularBufferCardinality(const struct circularBuffer *buf) {
  return buf->cardinality;
}

int circularBufferIsEmpty(const struct circularBuffer *buf) {
  return buf->cardinality == 0;
}

int circularBufferIsFull(const struct circularBuffer *buf) {
  return buf->cardinality == buf->capacity;
}

void circularBufferPushHead(struct circularBuffer *buf, void *ptr) {
  if (buf->cardinality != 0) {
    buf->headOffset = incrementIndex(buf, buf->headOffset);

    // Cannot use circularBufferIsFull(buf) at this point,
    // since the cardinality isn't incremented yet.
    // circularBufferIsFull(buf) uses the cardinality
    // to determine fullness. 
    if (buf->headOffset == buf->tailOffset) {
      buf->tailOffset = incrementIndex(buf, buf->tailOffset);
    }
  }

  memcpy(buf->data + buf->headOffset*buf->alignElementSize, ptr, buf->originalElementSize);

  if (!circularBufferIsFull(buf)) {
    buf->cardinality++;
  }
}

char *circularBufferPopTail(struct circularBuffer *buf) {
  if (buf->cardinality == 0) {
    return NULL;
  }

  // Store point to be returned.
  size_t tmpOffset = buf->tailOffset;;

  // Pop internally.
  buf->tailOffset = incrementIndex(buf, buf->tailOffset); 
  buf->cardinality--;

  return buf->data + tmpOffset * buf->alignElementSize;
}

const char *circularBufferPeekHead(const struct circularBuffer *buf) {
  return buf->cardinality == 0 ? NULL : buf->data + buf->alignElementSize * buf->headOffset;
}

const char *circularBufferPeekTail(const struct circularBuffer *buf) {
  return buf->cardinality == 0 ? NULL : buf->data + buf->alignElementSize * buf->tailOffset;
}

struct circularBufferIterator {
  struct circularBuffer *buf;
  size_t continuousIndex;
  size_t actualIndex;
};

struct circularBufferIterator *circularBufferIteratorCreate() {
  return calloc(1, sizeof(struct circularBufferIterator));
}

void circularBufferIteratorDestroy(struct circularBufferIterator *it) {
  free(it);
}

void circularBufferIteratorPrepare(struct circularBufferIterator *it, const struct circularBuffer *buf) {
  it->buf = buf;
  it->continuousIndex = 0;
  it->actualIndex = it->buf->tailOffset;
}

char *circularBufferIteratorNext(struct circularBufferIterator *it) {
  if (it->continuousIndex == it->buf->cardinality) {
    return NULL;
  }

  it->continuousIndex++;

  size_t tmp = it->actualIndex;
  it->actualIndex = incrementIndex(it->buf, it->actualIndex);

  return it->buf->data + tmp * it->buf->alignElementSize;
}

Notes to possible reviewers:

I'm still unsure about the initial padding of the flexible array member. I'm especially hoping for a review on that topic.
It's also especially wanted that the old data is overwritten, when new data is pushed to the head and the buffer is already filled - "It's a feature not a bug".

Here is a really small test:

#include <stdio.h>

#include "circularBuffer.h"

void DEBUG_circularBufferPrintContent(struct circularBufferIterator *it, struct circularBuffer *buf);
void DEBUG_circularBufferPrintState(const struct circularBuffer *buf);  

int main() {
  struct circularBuffer *buf;
  struct circularBufferIterator *it;

  buf = circularBufferCreate(3, sizeof(long));
  it  = circularBufferIteratorCreate();

  if (!buf) {
    printf("ERROR: No buffer was returned.\n");
    return -1;
  }

  if (!it) {
    printf("ERROR: No iterator was returned.\n");
    return -1;
  }

  printf("--- TEST INITIAL STATE ---\n");
  DEBUG_circularBufferPrintState(buf);
  DEBUG_circularBufferPrintContent(it, buf);

  printf("\n--- TEST UNDERFLOW ---\n");
  circularBufferPopTail(buf);
  DEBUG_circularBufferPrintState(buf);
  DEBUG_circularBufferPrintContent(it, buf);

  printf("\n--- TEST PUSH ---\n");
  long l = 0;
  circularBufferPushHead(buf, &l);
  DEBUG_circularBufferPrintState(buf);
  DEBUG_circularBufferPrintContent(it, buf);

  printf("\n--- TEST POP ---\n");
  circularBufferPopTail(buf);
  DEBUG_circularBufferPrintState(buf);
  DEBUG_circularBufferPrintContent(it, buf);

  printf("\n--- TEST FULL ---\n");
  for (l = 1; l <= 3; l++) { circularBufferPushHead(buf, &l); }
  DEBUG_circularBufferPrintState(buf);
  DEBUG_circularBufferPrintContent(it, buf);

  printf("\n--- TEST OVERFLOW ---\n");
  l = 4;
  circularBufferPushHead(buf, &l);
  DEBUG_circularBufferPrintState(buf);
  DEBUG_circularBufferPrintContent(it, buf);

  printf("\n--- TEST POP ---\n");
  circularBufferPopTail(buf);
  DEBUG_circularBufferPrintState(buf);
  DEBUG_circularBufferPrintContent(it, buf);

  circularBufferIteratorDestroy(it);
  circularBufferDestroy(but);

  return 0;
}

void DEBUG_circularBufferPrintContent(struct circularBufferIterator *it, struct circularBuffer *buf) {
  printf("--> DEBUG: ");

  long *tmp;
  for (circularBufferIteratorPrepare(it, buf); (tmp = (long*) circularBufferIteratorNext(it)) != NULL; ) {
    printf("%ld, ", *tmp);
  }

  printf("\n");
}

void DEBUG_circularBufferPrintState(const struct circularBuffer *buf) {
  printf("--> DEBUG: CARDINALITY: %zu, IS_EMPTY: %5s, IS_FULL: %5s\n", 
      circularBufferCardinality(buf), 
      circularBufferIsEmpty(buf) ? "true" : "false",
      circularBufferIsFull(buf) ? "true" : "false");
}

@coderodde I added a small piece of code I used to test the circulerBuffer. — user101048
– user101048, Commented Mar 27, 2016 at 11:41
Nice implementation, although I see no value yet to field cardinality. — chux
– chux, Commented Apr 2, 2016 at 3:56

Martin R · Accepted Answer · 2016-03-27 19:37:54Z

There is an asymmetry in your APIs, as can for example be seen in

void circularBufferPushHead(struct circularBuffer *buf, void *ptr);
char *circularBufferPopTail(struct circularBuffer *buf);
char *circularBufferIteratorNext(struct circularBufferIterator *it);

All functions which add an element to the circular buffer take the a void * parameter, but returning the elements is done as a char *.

I would recommend to use void * in all cases (and apart from changing the function prototypes, no changes are necessary). Since void * can be assigned to any pointer type without an explicit cast, retrieving elements simplifies from (taking your test code as an example)

tmp = (long*) circularBufferIteratorNext(it);

to

tmp = circularBufferIteratorNext(it);

Your calculations of alignElementSize seem unnecessary to me (and causes to more memory to be allocated than necessary). Here are some quotes of the C11 standard (taken from http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf):

6.2.8 Alignment of objects

2 A fundamental alignment is represented by an alignment less than or equal to the greatest alignment supported by the implementation in all contexts, which is equal to _Alignof (max_align_t).

3 An extended alignment is represented by an alignment greater than _Alignof (max_align_t). It is implementation-defined whether any extended alignments are supported and the contexts in which they are supported. A type having an extended alignment requirement is an over-aligned type.

7.22.3 Memory management functions

1 The order and contiguity of storage allocated by successive calls to the aligned_alloc, calloc, malloc, and realloc functions is unspecified. The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object with a fundamental alignment requirement and then used to access such an object or an array of such objects in the space allocated.

So – unless you are using "over-aligned types" – the alignment of data in

struct circularBuffer {
    // ... 

    alignas(max_align_t) char data[];
};

is suitable for any type of object if the memory of struct circularBuffer was obtained from malloc() or a related function.

It is then not necessary to separate between alignElementSize and originalElementSize and the buffer creation simplifies to

struct circularBuffer *circularBufferCreate(size_t capacity, size_t elementSize) {

    if (elementSize == 0) {
        return NULL; 
    }

    if ((SIZE_MAX - sizeof(struct circularBuffer)) / elementSize < capacity) {
        return NULL;
    }

    struct circularBuffer *buf = calloc(1, sizeof(struct circularBuffer) + elementSize * capacity);
    if (!buf) {
        return NULL;
    }

    buf->capacity = capacity;
    buf->cardinality = 0;
    buf->elementSize = elementSize;

    buf->headOffset = 0;
    buf->tailOffset = 0;

    return buf;
}

You can replace calloc() by malloc() if the initialization with zero bytes is not needed.

(If you are planning to work with – implementation-defined – "over-aligned" types then the required alignment must be passed as an additional parameter to the creation function, and more work is necessary to ensure that the address of the data field is property aligned.)

The iterator expects that no elements are added or removed to the circular buffer during the iteration. A possible solution to detect such a programming error would be to add a generation number to struct circularBuffer which is incremented with every modification. Then copy that generation number to struct circularBufferIterator in circularBufferIteratorPrepare() and verify it to be unchanged in circularBufferIteratorNext(). I would add such a check at least if the program is compiled in DEBUG mode.

It suffices to

#include <stddef.h>   // max_align_t in source

in the implementation file "circularBuffer.c", it is not needed in the header file "circularBuffer.h".

Edward · Accepted Answer · 2016-03-30 12:18:05Z

I see some things that may help you improve your code.

Use all of the required `#include`s

The macro SIZE_MAX is used but its declaration is in #include <stdint.h> (not <stdlib.h>) which is not actually in the list of includes.

Be careful with `const`

The code currently contains this function:

void circularBufferIteratorPrepare(struct circularBufferIterator *it, const struct circularBuffer *buf) {
  it->buf = buf;
  it->continuousIndex = 0;
  it->actualIndex = it->buf->tailOffset;
}

The problem is the first line it->buf = buf because the latter is const but the former is not. One solution is to change the structure definition to this:

struct circularBufferIterator {
  const struct circularBuffer *buf;
  size_t continuousIndex;
  size_t actualIndex;
};

And then change the declaration of circularBufferIteratorNext() to this:

const char *circularBufferIteratorNext(struct circularBufferIterator *it);

Study the standard

My understanding is that further alignment calculations are unnecessary in circularBufferCreate(). Quoting the C11 standard 5.7.5, paragraph 6:

The alignment requirement of the declared object or member is taken to be the specified alignment.

What that means is that the alignas specifier in your struct definition is sufficient to make sure that the first element is aligned. However, because you apparently want each of the members aligned as well, you'll need to do more work, but not as much as you're currently doing. See the next suggestion.

Simplify your code

The alignas() macro, as mentioned, only serves to align the first element of an array and only if the variable is implicitly allocated rather than allocated using malloc or calloc. What you need is for the data portion to be aligned. Fortunately, since you're using C11, there's a facility for exactly that purpose which is called aligned_alloc. This would also simplify your code at the modest expense of two allocations. (This can be consolidated into a single allocation, but I doubt it would be worth the effort.) Here's part of the function using aligned_alloc:

  if (elementSize == 0) {
    return NULL; 
  }
  struct circularBuffer *buf = malloc(sizeof(*buf));

  if (!buf) {
    return NULL;
  }
  buf->data = aligned_alloc(elementSize, capacity * elementSize);
  if (!buf->data) {
    free(buf);
    return NULL;
  }

Naturally, this assumes that data is declared as char *data;

Don't clear memory unless it's needed

The use of calloc within circularBufferCreate() is not really needed. You could just use malloc instead and avoid having the entire structure also zeroed. This is also the effect of aligned_alloc above.

Eliminate redundant elements

The alignElementSize and originalElementSize are the same when using aligned_alloc, so they can easily be combined into one, perhaps named elementSize.

Use `bool` type where practical

The circularBufferIsEmpty and similar functions would be better expressed as returning bool as defined in <stdbool.h> rather than an int as currently coded.

Enhance testing to check for alignment

Since one of your particular concerns was alignment, I suggest adding testing for that. To make it easier to adapt to different data types, I added the following to your test code:

typedef long mytype;
void myprint(const mytype *tmp) {
    printf("%p=%d, ", (void *)tmp, (int)(*tmp));
}
static mytype testarray[4] = { 1, 2, 3, 4};

Then I made some changes to main to accomodate. For example,

printf("\n--- TEST FULL ---\n");
for (int l = 0; l < 3; l++) { circularBufferPushHead(buf, &testarray[l]); }

Finally, the debug print routine was changed to this:

void DEBUG_circularBufferPrintContent(
        struct circularBufferIterator *it, 
        struct circularBuffer *buf) 
{
  printf("--> DEBUG: ");

  mytype *tmp;
  for (circularBufferIteratorPrepare(it, buf); 
       (tmp = (mytype*) circularBufferIteratorNext(it)) != NULL; ) 
  {
    myprint(tmp);
    if((unsigned long)tmp % _Alignof(mytype) != 0)  
        printf("[<-- Uh oh.  Unaligned member: %p] ", (void *)tmp);
  }

  printf("\n");
}

Casting to unsigned long` in (unsigned long)tmp seems arbitrary. Why type unsigned long? What is special about unsigned long? Why not use a maximal width like uintmax_t or better yet, if available, uintptr_t?. OTOH, since code is doing (unsigned long)tmp % _Alignof(mytype), certainly even (unsigned)tmp % _Alignof(mytype) would suffice. — chux
– chux, Commented Apr 2, 2016 at 3:21
Nice review - up vote. And good idea about aligned_alloc(). A value to discerning between alignElementSize and originalElementSize comes with any pushing of the element. One disagreement: Even thought the circular queue benefits by aligning to the element size, it is not known the that location of pushing occurs from an aligned pointer, thus only copying the original size is critical. With circularBufferPushHead(struct circularBuffer *buf, void *ptr);, memcpy from ptr with a size of alignElementSize may lead to UB. Best done with originalElementSize. — chux
– chux, Commented Apr 2, 2016 at 3:52

Stack Exchange Network

Circular Buffer in C - Follow Up

2 Answers 2

Use all of the required `#include`s

Be careful with `const`

Study the standard

Simplify your code

Don't clear memory unless it's needed

Eliminate redundant elements

Use `bool` type where practical

Enhance testing to check for alignment

You must log in to answer this question.

Linked

Hot Network Questions

Circular Buffer in C - Follow Up

2 Answers 2

Use all of the required #includes

Be careful with const

Study the standard

Simplify your code

Don't clear memory unless it's needed

Eliminate redundant elements

Use bool type where practical

Enhance testing to check for alignment

You must log in to answer this question.

Linked

Related

Hot Network Questions

Use all of the required `#include`s

Be careful with `const`

Use `bool` type where practical