9
\$\begingroup\$

Here's the implementation of a common data structure I use at work, mainly for logging purposes.

I tried to make it C++11-compliant, but even if this standard has been around for a few years, it is still quite new to me since I play with it only in my spare time (locked on VS2010 at work, which has a poor implementation of then-so-called C++0X.)

So, feel free to criticize and, hopefully, suggest some improvement; I'm especially interested in exception safety and correct implementation of move semantics (other than code style, performance issues and so on...)

I know it is still a naive implementation, so I intentionally avoided allocators and iterators by now, but...dont't be shy if you have something in mind.

#ifndef CIRCULAR_BUFFER_H
#define CIRCULAR_BUFFER_H

#include <algorithm>
#include <cstddef>
#include <cassert>
#include <stdexcept>
#include <iostream>

template <typename T>
class CircularBuffer
{
public:
    typedef size_t size_type;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T* pointer;
    typedef const T* const_pointer;

    explicit CircularBuffer(size_type capacity);
    CircularBuffer(const CircularBuffer<T> &rhs);
    CircularBuffer(CircularBuffer<T>&& rhs);
    ~CircularBuffer() { if (_buffer) delete[] _buffer; }

    CircularBuffer<T>& operator=(CircularBuffer<T> rhs);

    size_type size() const { return (_full ? _capacity : _front); }
    size_type capacity() const { return _capacity; }
    bool is_full() const { return _full; }

    const_reference operator[](size_type index) const;
    reference operator[](size_type index);

    void add(T item);
    void resize(size_type new_capacity);

    friend void swap(CircularBuffer<T> &a, CircularBuffer<T> &b)
    {
        std::swap(a._buffer, b._buffer);
        std::swap(a._capacity, b._capacity);
        std::swap(a._front, b._front);
        std::swap(a._full, b._full);
    }

private:
    pointer _buffer;
    size_type _capacity;
    size_type _front;
    bool _full;

    CircularBuffer();
};

template<typename T>
CircularBuffer<T>::CircularBuffer()
    : _buffer(nullptr)
    , _capacity(0)
    , _front(0)
    , _full(false)
{
}

template<typename T>
CircularBuffer<T>::CircularBuffer(size_type capacity)
    : CircularBuffer()
{
    if (capacity < 1) throw std::length_error("Invalid capacity");

    _buffer = new T[capacity];
    _capacity = capacity;
}

template<typename T>
CircularBuffer<T>::CircularBuffer(const CircularBuffer<T> &rhs)
    : _buffer(new T[rhs._capacity])
    , _capacity(rhs._capacity)
    , _front(rhs._front)
    , _full(rhs._full)
{
    std::copy(rhs._buffer, rhs._buffer + _capacity, _buffer);
}

template<typename T>
CircularBuffer<T>::CircularBuffer(CircularBuffer<T>&& rhs)
    : CircularBuffer()
{
    swap(*this, rhs);
}

template<typename T>
typename CircularBuffer<T>::const_reference
CircularBuffer<T>::operator[](size_type index) const
{
    static const std::out_of_range ex("index out of range");
    if (index < 0) throw ex;

    if (_full)
    {
        if (index >= _capacity) throw ex;
        return _buffer[(_front + index) % _capacity];
    }
    else
    {
        if (index >= _front) throw ex;
        return _buffer[index];
    }
}

template<typename T>
typename CircularBuffer<T>::reference 
CircularBuffer<T>::operator[](size_type index)
{
    return const_cast<reference>(static_cast<const CircularBuffer<T>&>(*this)[index]);
}

template<typename T>
CircularBuffer<T>& 
CircularBuffer<T>::operator=(CircularBuffer<T> rhs)
{
    swap(*this, rhs);
    return *this;
}

template<typename T>
void 
CircularBuffer<T>::add(T item)
{
    _buffer[_front++] = item;
    if (_front == _capacity) {
        _front = 0;
        _full = true;
    }
}

template<typename T>
void 
CircularBuffer<T>::resize(size_type new_capacity)
{
    if (new_capacity < 1) throw std::length_error("Invalid capacity");
    if (new_capacity == _capacity) return;

    size_type num_items = size();
    size_type offset = 0;
    if (num_items > new_capacity)
    {
        offset = num_items - new_capacity;
        num_items = new_capacity;
    }

    pointer new_buffer = new T[new_capacity];
    for (size_type item_no = 0; item_no < num_items; ++item_no)
    {
        new_buffer[item_no] = (*this)[item_no + offset];
    }

    pointer old_buffer = _buffer;

    _buffer = new_buffer;
    _capacity = new_capacity;
    _front = (num_items % _capacity);
    _full = (num_items == _capacity);

    delete[] old_buffer;
}

#endif // CIRCULAR_BUFFER_H
\$\endgroup\$
5
\$\begingroup\$

Exception safety

Let's look at the copy constructor:

template<typename T>
CircularBuffer<T>::CircularBuffer(const CircularBuffer<T> &rhs)
    : _buffer(new T[rhs._capacity])
    // ...
{
    std::copy(rhs._buffer, rhs._buffer + _capacity, _buffer);
}

What will happen if std::copy (read T's copy constructor/assignment operator) throws? Right, a memory leak - CircularBuffer won't get constructed, its' destructor will not be called, and the memory allocated for _buffer will be lost.

To avoid this issue, consider using something RAII'ish for your _buffer (as Loki Astari mentioned, std::vector might be a good choice) . Or simply wrap std::copy in a try block and delete[] your _buffer in a catch-handler.

Logic errors

if (index < 0) throw ex;

Your index is unsigned, it cannot be less than zero.

Style and usability

Consider using default member initializers and explicitly deleting your default constructor:

template <typename T>
class CircularBuffer
{
public:
    CircularBuffer() = delete;
    // ...
private:
    pointer _buffer = nullptr;
    size_type _capacity = 0;
    size_type _front = 0;
    bool _full = false;
};

Doing this will clean up your code a bit and will clearly state that your CircularBuffer is not default-constructible.

\$\endgroup\$
  • \$\begingroup\$ I have serious doubts about the fact my call to std::copy could throw...but maybe I need to check if the dynamic allocation succeeds. \$\endgroup\$ – bassfault Jul 16 '16 at 11:11
  • 2
    \$\begingroup\$ What causes these serious doubts? Your call to std::copy invokes T's copy assignment operator, which can easily throw, since you don't impose any constraints on T. It might not throw for specific types you instantiate CircularBuffer with, but it doesn't make CircularBuffer exception-safe. \$\endgroup\$ – Nikita Kakuev Jul 16 '16 at 12:35
  • 1
    \$\begingroup\$ @bel8z And you don't really need to check if dynamic allocation succeeds. If it doesn't, then new will throw, your CircularBuffer won't be constructed, and no resources will be leaked. That's a pretty strong exception guarantee. \$\endgroup\$ – Nikita Kakuev Jul 16 '16 at 12:51
10
\$\begingroup\$

Rather than implement all the memory management yourself use an existing container and just implement the circular part yourself.

template <typename T>
class CircularBuffer
{
    std::vector<T>  buffer; // maybe there is a better one
    ...                     // I would think on this a bit.

The main reason is that std::vector will not construct the elements that are not used. Yours on the other hand default constructs all the elements in _buffer. If T is not default constructible this is a problem. If T is expensive to default construct this is a problem.

Move

The move operators should usually be marked as noexcept

CircularBuffer(CircularBuffer<T>&& rhs) noexcept;
// Also you should probably have an explicit move assignment.
CircularBuffer<T>& operator=(CircularBuffer<T>&& rhs) noexcept;

Swap

I normally implement the function swap in terms of a member function swap that I mark as noexcept (because the move operators usually need swap and they need it to be noexcept).

friend void swap(CircularBuffer<T>& lhs, CircularBuffer<T>& rhs)
{
    lhs.swap(rhs);
}

Swap is one of those rare places that you should use using std::swap.

void swap(CircularBuffer<T>& rhs)
{
    using std::swap;
    swap(_buffer,   rhs._buffer);
    swap(_capacity, rhs._capacity);
    swap(_front,    rhs._front);
    swap(_full,     rhs._full);
}

The reason for this is if you change the types of your members (possibly to some custom type) then the swap() function continues to work without modification.

Design

Not really a circular buffer as there is no back or front concept implemented here.

\$\endgroup\$
  • \$\begingroup\$ Probably I'd use a deque instead of a vector. Anyway, I miss a point: I know it is implementation-defined, but I don't think that an empty vector has zero capacity when instantiated, so in some way it must allocate some memory. I'm curious about how to do this without default costructing elements. Allocators? Honestly, I thought allocating an array dinamically using new was enough, and that the elements of the array where not initialized - your answer seems to state my assumption was clearly wrong, isn't it? \$\endgroup\$ – bassfault Jul 16 '16 at 11:04
  • \$\begingroup\$ Also, when I implemented this thing I was only concerned with storing items in a "circular fashion", and I didn't find useful to expose details as front and back of the buffer. But I'm quite interested about the "back or front concept" you mentioned...so, can you expand a bit? \$\endgroup\$ – bassfault Jul 16 '16 at 11:09
  • \$\begingroup\$ @bel8z: The point of a circular buffer. Is you put stuff in one end and take it out of the other. So your front is chasing the back around and around the buffer. Without the ability to take stuff out of the back all you really have is a resizable array/stack. \$\endgroup\$ – Martin York Jul 16 '16 at 23:24
  • 1
    \$\begingroup\$ @bel8z: When you call new it not only allocates the memory but also calls the constructor for the type. When you use new to create an array of objects each object is constructed (in order) using the default constructor. Read this blog article See the section "Version-3 Lazy Construction of elements" to allocate memory without constructing the members. \$\endgroup\$ – Martin York Jul 16 '16 at 23:25
  • \$\begingroup\$ deque would be better if you want an infinitely sized buffer that you can add elements to the front and remove them from the back. But a circular buffer (of a fixed size) then vector is better. \$\endgroup\$ – Martin York Jul 16 '16 at 23:29
-4
\$\begingroup\$

To expand on Loki's comment "Not really a circular buffer as there is no back or front concept implemented here." I have attached a small section of some JavaScript code implementing a dynamic start/end (front/back) that was very useful to me (my head hurts when dealing that kind of "math")

You can learn a-lot about the sneaky ways in which to handle circular buffers by examining this JavaScript code (not mine, only excerpt attached). Ignoring the fact that it's JavaScript, it is an excellent example of how to have a dynamic start and end index, such that if your circular buffer is set to have a size of 10, only indexes 0 through 9 will ever be used.

Note, this also implements an optional callback (this.overflow) which is called when an element is about to removed from the buffer.

/**
 * a circular bufffer
 * @class
 */
function CBuffer() {
    this.size = this.start = 0;
    // set to callback fn if data is about to be overwritten
    this.overflow = null;
    // emulate Array based on passed arguments
    if (arguments.length > 1 || typeof arguments[0] !== 'number') {
        this.data = new Array(arguments.length);
        this.end = (this.length = arguments.length) - 1;
        this.push.apply(this, arguments);
    } else {
        this.data = new Array(arguments[0]);
        this.end = (this.length = arguments[0]) - 1;
    }
    // need to `return this` so `return CBuffer.apply` works
    return this;
}


/** @typedef {*} item */

CBuffer.prototype = {
    // properly set constructor
    constructor : CBuffer,

    /* mutator */

    /**
     * pop last item
     *
     * @method
     * @this CBuffer
     * @returns {item}
     */
    pop: function () {
        var item;
        if (this.size === 0) return void 0;
        item = this.data[this.end];
        // remove the reference to the object so it can be garbage collected
        delete this.data[this.end];
        this.end = (this.end - 1 + this.length) % this.length;
        this.size--;
        return item;
    },
    /**
     * push item to the end
     *
     * @method
     * @this CBuffer
     * @returns {item}
     */
    push: function () {
        var i = 0;
        // check if overflow is set, and if data is about to be overwritten
        if (this.overflow && this.size + arguments.length > this.length) {
            // call overflow function and send data that's about to be overwritten
            for (; i < this.size + arguments.length - this.length; i++) {
                this.overflow(this.data[(this.end + i + 1) % this.length], this);
            }
        }
        // push items to the end, wrapping and erasing existing items
        // using arguments variable directly to reduce gc footprint
        for (i = 0; i < arguments.length; i++) {
            this.data[(this.end + i + 1) % this.length] = arguments[i];
        }
        // recalculate size
        if (this.size < this.length) {
            if (this.size + i > this.length) this.size = this.length;
            else this.size += i;
        }
        // recalculate end
        this.end = (this.end + i) % this.length;
        // recalculate start
        this.start = (this.length + this.end - this.size + 1) % this.length;
        // return number current number of items in CBuffer
        return this.size;
    },
    remove: function(predicate, options) {
        options = _.defaults(options, {
            // whether to quash notification via callback of removal
            silent: false, 
        });
        var newData = this.slice();
        var removed = _.remove(newData, predicate);
        this.fill(null); // delete references
        this.data = _.merge(this.data, newData);
        this.start = 0;
        this.size = newData.length;
        this.end = this.size - 1;
        if (!options.silent) {
            for (var i = 0, len = removed.length; i < len; ++i) {
                this.overflow(removed[i], this);
            }
        }
        return removed;
    },
    torray: function (start, end) {
        var length = this.size;

        start = Number(start) || 0;

        if (start < 0) {
            if (start >= end)
                return [];
            start = (-start > length) ? 0 : length + start;
        }

        if (end == null || end > length)
            end = length;
        else if (end < 0)
            end += length;
        else
            end = Number(end) || 0;

        length = start < end ? end - start : 0;

        var result = Array(length);
        for (var index = 0; index < length; index++) {
            result[index] = this.data[
                (this.start + start + index)
                % this.length
            ];
        }
        return result;
    }
\$\endgroup\$
  • 2
    \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. \$\endgroup\$ – Mast Dec 9 '16 at 10:57
  • \$\begingroup\$ @Mast, ummmm... no, I haven't presented a solution, I presented a small section of an implementation in another language, elaborating on the comment by Loki "Not really a circular buffer as there is no back or front concept implemented here." i.e. I have shown how (in theory) a back and front can be implemented. Unfortunately it was a bit long to fit into a comment appending Loki's answer. I'm new to codereview, so forgive me, perhaps I should have prefaced this "answer" with something similar to what I have just written in this comment? \$\endgroup\$ – Orwellophile Dec 9 '16 at 11:02
  • 1
    \$\begingroup\$ What parts of your answers would you say review the code given by the author of the question? \$\endgroup\$ – Mast Dec 9 '16 at 12:05

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.