Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What's wrong with my circular buffer

Tags:

c++

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.

like image 276
J. Doe Avatar asked Feb 14 '17 14:02

J. Doe


1 Answers

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.

like image 191
Trevor Avatar answered Sep 30 '22 03:09

Trevor