CODEWITHSUNDEEP
c++
J. Doe
J. Doe

Reputation: 429

What's wrong with my circular buffer

Recently I had a job interview and I was asked to implement circular buffer class. It was required to not use any containers (incl. STL).

Mine code was following:

template<class T>
class CircularFifo
{
    T *    _data;
    size_t _size;

    size_t _read;  // last readen elem
    size_t _write; // next write index

    CircularFifo(CircularFifo const &) = delete;
    CircularFifo & operator=(CircularFifo const &) = delete;
    CircularFifo(CircularFifo &&) = delete;
    CircularFifo & operator=(CircularFifo &&) = delete;

public:
    explicit inline
    CircularFifo(size_t size = 2048)
        : _data(new T[size])
        , _size(size)
        , _read(-1)
        , _write(0)
    {
        if (0 == _size)
        {
            throw std::runtime_error("too empty buffer");
        }

        if (1 == _size)
        {
            throw std::runtime_error("too short buffer");
        }

        if (-1 == size)
        {
            throw std::runtime_error("too huge buffer");
        }
    }

    inline ~CircularFifo()
    {
        delete []_data;
    }

    inline T read()
    {
        if (_read == _write)
        {
            throw std::runtime_error("buffer underflow");
        }
        return _data[(++_read) % _size];
    }

    inline void write(T const & obj)
    {
        if (_read == _write)
        {
            throw std::runtime_error("buffer overflow");
        }
        _data[(_write++) % _size] = obj;
    }
};

An interviewer sad that coding style is fine. But there is a bug in the buffer which will makes this class unreliable. She asked me to find it and I totally failed. She also haven't disclosed this bug to me too.

I re-checked everything: leaks, arithmetics, possible overflows etc. My head almost ready to explode. I don't know where is mistake. Please help me.

P.S. Sorry for my messy English.

Upvotes: 12

Views: 1865

Answers (4)

Andrew Kashpur
Andrew Kashpur

Reputation: 746

In addition to mistake with initialization you have also this problem:

when you add element, you check (_read == _write), then do _write++. So you can write without reading until you _write field will overflow its type. You need to check ( (_write -_read) == _size) before writing, not (_read == _write)

Upvotes: 0

Vladan Bato
Vladan Bato

Reputation: 96

There are several bugs in your code. First, as already pointed out in another answer, by initializing _read to -1, if you try to read before writing, you will read garbage. Second, if you don't read anything, but you write size items, _write will wrap around and overwrite the start of the buffer, as _read will never equal _write.

But even if you did initialize both _read and _write to valid values, it wouldn't work because in your code, the condition _read == _write means both "buffer is empty" and "buffer is full". One of the two indices must stop one element before the other. If _read == _write means "buffer empty", then (_read+1)%size == _write should mean "buffer full".

By implementing the circular buffer this way, you will always waste one element (you can store a maximum of size-1 items).

There is another way of implementing a circular buffer that doesn't waste an element. Here's an article explaining both ways of implementing a circular buffer.

Upvotes: 8

Sopel
Sopel

Reputation: 1219

When _read or _write overflow you have a problem. When the size is not a power of 2 you skip elements. This is not be an expected behaviour in circular buffer.

They should be assigned modulo _size after each operation.

Also, as a side note, I would not make size a default parameter with an arbitrary value. If the user doesn't know what size they should use they don't understand the purpose and dangers of the data structure.

Second note. I think the noncritical exceptions, like "buffer over/underflow" should be debug only asserts (also maybe zero size one). If something like this happens it is a huge bug made by a user, not an exceptional case. They arise from logical mistake in user's code, not from uncontrollable limitations like for example amount of addressable memory.

Size of one should be perfectly fine too though.

Upvotes: 0

Trevor
Trevor

Reputation: 366

Could it be that _read is initialized to -1 and _write is initialized to 0, but in the read function you check if they are equal? When the buffer is first initialized, and a read is attempted, the if check will succeed even though nothing has been added to the buffer.

Upvotes: 16

Related Questions