HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Circular Buffer in C - Follow Up

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
circularfollowbuffer

Problem

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 // 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 circular

Solution

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 = 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    // max_align_t in source


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

Code Snippets

void circularBufferPushHead(struct circularBuffer *buf, void *ptr);
char *circularBufferPopTail(struct circularBuffer *buf);
char *circularBufferIteratorNext(struct circularBufferIterator *it);
tmp = (long*) circularBufferIteratorNext(it);
tmp = circularBufferIteratorNext(it);
struct circularBuffer {
    // ... 

    alignas(max_align_t) char data[];
};
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;
}

Context

StackExchange Code Review Q#123699, answer score: 2

Revisions (0)

No revisions yet.