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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With