Что не так с моим круговым буфером

Недавно у меня было собеседование, и меня попросили внедрить класс циклического буфера. Требовалось не использовать какие-либо контейнеры (включая STL).

Следовал мой код:

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;
    }
};

Интервьюер грустно, что стиль кодирования в порядке. Но в буфере есть ошибка, которая сделает этот класс ненадежным. Она попросила меня найти его, и я полностью потерпел неудачу. Она также не раскрыла мне эту ошибку.

Я снова проверил все: утечки, арифметику, возможные переполнения и т.д. Моя голова почти готова к взрыву. Я не знаю, где ошибка. Пожалуйста, помогите мне.

P.S. Извините за мой грязный английский.

Ответы

Ответ 1

В коде есть несколько ошибок. Во-первых, как уже указывалось в другом ответе, инициализируя _read -1, если вы пытаетесь прочитать перед записью, вы будете читать мусор. Во-вторых, если вы ничего не читаете, но вы пишете элементы size, _write будет обертываться и перезаписывать начало буфера, так как _read никогда не будет равным _write.

Но даже если вы выполнили инициализацию как _read, так и _write до допустимых значений, это не сработает, потому что в вашем коде условие _read == _write означает, что "буфер пуст" и "буфер заполнен". Один из двух индексов должен останавливать один элемент перед другим. Если _read == _write означает "буфер пуст", то (_read+1)%size == _write должен означать "полный буфер".

Внедряя циклический буфер таким образом, вы всегда будете тратить один элемент (вы можете хранить максимум size-1 элементов).

Существует еще один способ реализации циклического буфера, который не переносит элемент. Здесь статья, объясняющая оба способа реализации кругового буфера.

Ответ 2

Может ли быть, что _read инициализируется -1, а _write инициализируется 0, но в функции чтения вы проверяете, равны ли они? Когда буфер сначала инициализируется и попытка чтения выполняется, проверка if будет успешной, даже если в буфер не было добавлено ничего.

Ответ 3

При переполнении _read или _write у вас есть проблема. Когда размер не равен 2, вы пропускаете элементы. Это не является ожидаемым поведением в круговом буфере.

Они должны быть назначены по модулю _size после каждой операции.

Кроме того, в качестве побочной заметки я бы не сделал size параметр по умолчанию с произвольным значением. Если пользователь не знает, какой размер они должны использовать, они не понимают цели и опасности структуры данных.

Второе примечание. Я думаю, что некритические исключения, такие как "buffer over/underflow", должны быть отладки, только утверждает (также может быть, нулевой размер один). Если что-то подобное происходит, это огромная ошибка, сделанная пользователем, а не исключительный случай. Они возникают из-за логической ошибки в коде пользователя, а не от неконтролируемых ограничений, например, количества адресной памяти.

Размер одного тоже должен быть отлично.

Ответ 4

В дополнение к ошибке с инициализацией у вас также есть эта проблема:

когда вы добавляете элемент, вы проверяете (_read == _write), затем выполняете _write ++. Таким образом, вы можете писать без чтения, пока поле _write не переполнит его тип. Вы должны проверить ((_write -_read) == _size) перед записью, а не (_read == _write)