6
\$\begingroup\$

I would like to design an elegant yet efficient circular buffer of integers. I have designed a FIFO type circular buffer in C++(11)- starting with the class header (declaration) as follow:

[cyclicBuffer.hpp]:

#ifndef __CyclicBuff_HPP
#define __CyclicBuff_HPP
#pragma once

class CyclicBuffer
{
public:
    CyclicBuffer(int buffSize);
    ~CyclicBuffer();
    void setChar(char c);
    char getChar();
    void clearCycBuff(int buffSize);
private:
    char *buffer;
    int bufferSize;
    int head;   // index for the top of the buffer
    int tail;   // indes for the bottom of the buffer
};

#endif  

implementation of the class is as following: [cyclicBuffer.cpp]:

#include "stdafx.h"
#include "cyclicBuffer.hpp"
#include <iostream>

//using namespace std;

CyclicBuffer::CyclicBuffer(int buffSize)
{
    head = 0;
    tail = 0;
    bufferSize = buffSize;
    buffer = new char[bufferSize];
    std::cout << "Buffer initated successfully\n";

/*
    {
        std::cout << "Buffer was not created\n driver exiting...\n";
//      return -1;
    }*/
}

CyclicBuffer::~CyclicBuffer()
{
    delete buffer;
    std::cout << "Buffer destroyed successfully\n";
}


void CyclicBuffer::clearCycBuff(int buffSize)   //not used , has no meaning to set '0'

{
    head = 0;
    tail = 0;
    for (int i = 0; i <= buffSize; i++) 
        buffer[i] = '0';
}

void CyclicBuffer::setChar(char c)
{
    //std::cout << "head: " << head << '\n';
    head %= bufferSize;
    buffer[head] = c;
    head++;
}

char CyclicBuffer::getChar(void)
{
    //std::cout << " tail:" << tail<<'\n';
    tail %= bufferSize;
    return buffer[tail++];

}

Finally, testing the class by an instance as follow:

// CyclicBufferMain.cpp : Defines the entry point for the console 
// application.


#include "stdafx.h"
#include <iostream>
#include "cyclicBuffer.hpp"

#define SIZE    32

int main(void)
{
    CyclicBuffer aBuffer(SIZE);

    for (int i = 0; i < SIZE*1.5; i++)
        aBuffer.setChar((char)(i+45));

    for (int i = 0; i < SIZE ; i++)
        std::cout << aBuffer.getChar() << ' ';


    std::cout << '\n';



    return 0;
}

for the given main function the result will be like this: enter image description here

My question: is this class is efficient enough for low-rate uC ? (targeting to Atmel, RISC type or low performance ARM uC)

Regarding @Toby Speight: Thanks for your helpful comments and advices - few questions for you:

(1) when I did delete instead delete [], did I make a 'memory leak'? why MS VStudio (2015) didn't warn me?

(2) I would change the CyclicBuffer::clearCycBuff() member function to use buffer[i] = 0; (instead buffer[i]='0';) to clear the buffer's values.

(3) Why need to drop the commented-out code?

(4) You used uniform initializer at the constructor - is it big difference as to what I did using regular variable assignments at the constructor ?

(5) I know 'size_t' is it a specialize typedef that exists at the GNU and MS compilers but would have a problem using it when porting the code to a specific target which could not have such typedef ?

Thanks.

\$\endgroup\$

migrated from stackoverflow.com May 24 '17 at 20:08

This question came from our site for professional and enthusiast programmers.

  • 2
    \$\begingroup\$ I have usually found an additional value to be necessary: the number of items in the buffer, because when the index head == tail you cannot know whether a circular buffer is empty or full. \$\endgroup\$ – Weather Vane May 24 '17 at 19:44
  • 1
    \$\begingroup\$ ... and sweeter, because you don't need to be continually making a (head - tail + size) % size calculation to determine how many items there are in the buffer. \$\endgroup\$ – Weather Vane May 24 '17 at 19:53
  • 2
    \$\begingroup\$ The most heavy operation in your actual code is taking the remainder. Its performance varies target-wise, and you might find some performance gain by switching it to comparison with the container size. Also, restricting the possible buffer sizes to the power of two will allow you to substitute the division with bitwise and. \$\endgroup\$ – iehrlich May 24 '17 at 19:53
  • 2
    \$\begingroup\$ Also, you don't need both include guards and #pragma once. \$\endgroup\$ – iehrlich May 24 '17 at 19:54
  • 2
    \$\begingroup\$ Don't forget to change your delete to delete [] \$\endgroup\$ – Ceros May 24 '17 at 21:25
6
\$\begingroup\$

Improve the wrap-around logic

There's obvious inefficiency in:

head %= bufferSize;

% uses division, but because we're incrementing, we know that head / bufferSize is at most 1. Instead, we can:

if (++head >= bufferSize)
    head -= bufferSize;

On architectures such as ARM, there's no branch here, as any decent compiler will just use a condition flag on the subtraction.


Consider checking for overrun and underrun

At the moment, this buffer has no checking for the read and write positions crossing each other. Perhaps that's what you need, but it's quite unusual to have an unchecked circular buffer, and if you were holding (e.g.) audio data, you can imagine how it would sound, given the output you show.


Match new and delete

Since you create buffer using new[], you must use the array form delete[] in the destructor:

CyclicBuffer::~CyclicBuffer()
{
    delete[] buffer;
}

Style points

Prefer initializers to assignment

A constructor should initialize all the members of the class:

CyclicBuffer::CyclicBuffer(std::size_t buffSize)
  : buffer(new char[bufferSize]),
    bufferSize(buffSize),
    head(0),
    tail(0)
{
}

A good compiler will warn you if you have uninitialized members (e.g. g++ -Wall -Wextra).

Note that I've also changed the argument to be a size_t, as a negative size is meaningless. The int members should all be size_t, too.

Avoid numeric character constants

What's special about the number 45? If you care about its character value, (and if you're using an ASCII-like system), it's clearer to write '-' instead.

Drop the commented-out code

I don't want to see using std::namespace;, ever. Not even in a comment.

\$\endgroup\$
  • \$\begingroup\$ Regarding the suggested fix about % division, since it is always incrementing, we can put if (++head >= bufferSize) head = 0; right? And it should be more efficient as we are avoiding the subtraction. Am I missing something here? \$\endgroup\$ – Anubis Jun 28 '18 at 10:55
  • \$\begingroup\$ No, you're missing nothing - assigning zero is less work than subtraction, and would be a further improvement. \$\endgroup\$ – Toby Speight Jul 4 '18 at 7:20
  • 3
    \$\begingroup\$ @TobySpeight : In fact, // is the best prefix for using namespace std; \$\endgroup\$ – Calak Nov 12 '18 at 14:57
4
\$\begingroup\$

Constructor initialization - 0 out the array

buffer(new T[size]{}) will set all the values to 0 instead of random garbage

template<class T>
CyclicBuffer<T>::CyclicBuffer(std::size_t size): head(0), tail(0), buffer(new T[size]{}), size(size) {

}

Adding and Getting can use equality comparison

Comparing equality rather than subtracting/greater or equals makes it more readable

template<class T>
void CyclicBuffer<T>::add(T val) {
    if (head == size)
        head = 0;

    buffer[head++] = val;
}

template<class T>
T CyclicBuffer<T>::get() {
    if (tail == size)
        tail = 0;

    return buffer[tail++];
}

Use template<class T> to make your structure generic

You will be able to insert any type:

CyclicBuffer<char> charCyclicBuffer(5);
CyclicBuffer<int> intCyclicBuffer(5);

Use std::size_t for portability

Besides portability - size, head, tail will never be negative

template<class T>
class CyclicBuffer{
public:
    explicit CyclicBuffer(std::size_t size);

    ~CyclicBuffer();

    void add(T val);

    T get();

    inline std::size_t getSize() {
        return this->size;
    }

private:
    T *buffer;
    std::size_t size;
    std::size_t head;
    std::size_t tail;
};
\$\endgroup\$
4
\$\begingroup\$
  • Don't use leading or double underscores.

    "Each identifier that contains a double underscore __ or begins with an underscore followed by an uppercase letter is reserved to the implementation for any use." (5.10.3.1)
    "Each identifier that begins with an underscore is reserved to the implementation for use as a name in the global namespace." (5.10.3.2)

  • Only include what you need.

    Don't include "stdafx.h" if you don't use it.

  • Avoid raw pointers

    buffer = new char[bufferSize]; creates an array of dynamic storage duration and default-initializes it to indeterminate values. The destructor must destroy it with delete[] buffer;.

    Now that you have a raw pointer as a data member you need to worry about copy construction, copy assignment, move construction and move assignment.

    Without a user-defined copy constructor the compiler will create one for you, which copies all data member. Now after CyclicBuffer a(10); CyclicBuffer b(a); both a.buffer and b.buffer point to the same array. As soon as the second destructor tries to delete[] the array you are in UB-Land. (The same is true for the copy assignment operator.)
    The compiler will NOT create a move constructor or move assignment operator for you because there is a user-defined destructor.

    But there's an alternative: Instead of creating and destroying the array manually you can just use a std::vector<char>. Now you don't need a destructor and the compiler-generated special member functions do everything you need.

  • Prefer classes without destructors.

    If a class implements a destructor it should probably also implement a copy constructor, a copy assignment operator, a move constructor and a move assignment operator. That's commonly known as the Rule of Five.

    IMHO an even better approach is the Rule of Zero. "Classes that have custom destructors, copy/move constructors or copy/move assignment operators should deal exclusively with ownership (which follows from the Single Responsibility Principle). Other classes should not have custom destructors, copy/move constructors or copy/move assignment operators."

    You can follow that rule by using a std::vector<char> for your buffer.

  • clearCycBuffer(int buffSize)

    What happens if you pass a buffSize different from this->bufferSize? This function should not take a parameter and use bufferSize instead.

    You use a traditional for-loop. Consider using std::fill or std::fill_n. It's easier to write and read: std::fill_n(buffer, bufferSize, '0'); or std::fill(begin(buffer), end(buffer), '0'); if you use a std::vector.

  • Avoid the preprocessor if you can.

    Before main() you use the preprocessor to define a constant SIZE. There is no reason not to use a constant variable for that: const int SIZE = 32;

  • Naming

    The name clearCycBuff is redundant and should be renamed to clear.

    If I'd read a method name getChar() or setChar() I would not instantly assume that it advances the buffer. Personally, instead of "get"/"set" I would prefer verbs like "read"/"write" or "shift"/"push" or something similar.

  • Additional methods

    As a user of your class I would want some methods to access the capacity and the number of elements available to getChar() and I'd want to have a way to see if the buffer is empty or full.

    I suggest:

    • int capacity() const;
    • int size() const;
    • bool empty() const;
    • bool full() const;

    More advance would be iterators and begin()/end() functions, so that CyclicBuffer works with the algorithms from the standard library.

  • Be clear about what you provide

    With the current code it's valid to read more items from the buffer than were put into it. That may be a char of indeterminate value (for a newly constructed buffer), an item from a previous iteration or a '0' (after a clearCycBuffer).
    It's not clear why you set all your items to '0' in clearCycBuffer but don't set them to a meaningful value in the constructor. Also, without context '0' is a strange choice, maybe you wanted to write '\0'.

    Add a comment or some documentation that describes if the user may read beyond what was written and what value will be returned.

  • Look at your competitors

    boost::circular_buffer is a high quality implementation of a circular buffer and has an excellent documentation.

    There is a proposal to add a ring span to the standard library. John Kalb, Matt Bentley and Odin Holms talk about it in on CppChat.

    You can also find several discussions about the API and the implementation of circular buffers, e.g.

\$\endgroup\$
  • \$\begingroup\$ Keep in mind that the user asked for advice for a low-rate uC. It is possible that the added overhead (FLASH/heap) for incorporating the standard library is too much. \$\endgroup\$ – c.fogelklou Mar 7 at 3:39

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.