Универсальный кольцевой буфер на C#

Кольцевой буфер - это фиксированная очередь типа FIFO (акроним First In, First Out — «первым пришёл — первым ушёл»). Пространства в буфере можно рассматривать как связанные в кольцо. Элементы в буфере никогда не перемещаются. Вместо этого используются переменные указатели для идентификации головы и хвоста очереди.

Что такое кольцевой буфер?

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

В некоторых структурах очередей, когда элементы добавляются или удаляются, содержимое очереди физически перемещается в памяти. С круглым буфером позиции фиксированы. Голова и хвост очереди идентифицируются с помощью двух указателей, которые обновляются, когда элементы добавляются или удаляются. Кроме того, буферные пространства можно рассматривать как циклические. После использования последнего пробела в буфере, следующий элемент в очереди сохраняется в первом пространстве. На приведенной ниже диаграмме показана концептуальная модель кольцевого буфера.



Диаграмма представляет собой круговой буфер с шестнадцатью пробелами, тринадцать из которых используются. В этом случае значения от одного до тринадцати были добавлены по порядку. Голова очереди указывает на последнее значение, тринадцать, а хвост находится в пространстве, содержащем номер один. Когда следующий элемент будет выставлен в очередь, он будет добавлен в следующее доступное пустое пространство после тринадцати, и указатель на голову будет смещен, чтобы указать на эту позицию. Когда будет выполняться следующая операция декомпрессии, номер один в указателе хвоста будет извлечен, а хвост будет перемещаться по часовой стрелке на одно место. При удалении объекта нет необходимости очищать старое буферное пространство, поскольку значение будет перезаписано в какой-то момент в будущем.

Природа кругового буфера такова, что голова очереди может поймать хвост. Когда следующий элемент, который должен быть установлен в очередь, перезаписывает элемент хвоста, есть несколько возможных действий. Наиболее распространенными являются:

• Разрешить новому элементу перезаписывать элемент хвоста, перемещая указатель хвоста вперед, чтобы указать на следующий самый старый предмет. Этот подход полезен для обработки сигналов в реальном времени. Например, при применении фильтра к видеопотоку. Если хвост очереди перезаписан, это может вызвать «блики» в видео или мгновенную потерю качества, но может позволить выходному видео продолжить воспроизведение без паузы или замедления.
  
  
• Выбросьте исключение при попытке добавить в полную очередь или прочитать из пустого буфера. Это гарантирует, что никакие данные не будут потеряны, но менее полезны для очередей в режиме реального времени или где скорость постановки в очередь и извлечение из очереди неодинаковы.
  
  
• Блокируйте поток при попытке добавить в полную очередь или прочитать из пустой очереди. Как и при ловле исключений, это гарантирует, что данные не будут потеряны. Это полезно в параллельных приложениях, когда отдельные потоки используются для очереди и деоккуляции. Только один из двух потоков может быть заблокирован в любое время, и исключений не будет, поэтому очередь может использоваться для обработки больших потоков данных без риска сбоя.

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

Реализация кругового буфера

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

public class CircularBuffer<T>
{
}

Далее нам понадобятся несколько переменных уровня класса. Во-первых, нам нужно где-то хранить данные буфера. Для этого мы будем использовать массив типа, определенного в параметре type. Мы будем использовать два целых значения в качестве указателей на голову и хвост. Они будут содержать значения индекса для массива буфера. Два дополнительных целых числа будут содержать текущую длину очереди и размер буфера. Они будут использоваться при определении того, полностью ли заполнен или пуст буфер. Наконец, чтобы предотвратить ошибки синхронизации, если несколько потоков пытаются в очереди или деактивировать одновременно, мы создадим объект для управления блокировками.

Код для переменных уровня класса выглядит следующим образом:

T [] _buffer;
Int _head;
Int _tail;
Int _length;
Int _bufferSize;
Object _lock = new object ();

Добавление конструктора

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

public CircularBuffer(int bufferSize)
{
    _buffer = new T[bufferSize];
    _bufferSize = bufferSize;
    _head = bufferSize - 1;
}

Добавление флагов статуса очереди

При работе с очередью нам нужно знать, когда буфер заполнен или пуст. Эта информация также может быть полезна для пользователей класса, поэтому мы создадим два булевых свойства, которые указывают эти статусы. Очередь пуста, когда текущая длина равна нулю и заполняется, когда текущая длина совпадает с размером буфера.

Код для этого выглядит следующим образом:

public bool IsEmpty
{
    get { return _length == 0; }
}
 
public bool IsFull
{
    get { return _length == _bufferSize; }
}

Извлекаемые значения

Теперь мы можем добавить метод Dequeue, который извлекает и возвращает самый старый элемент из буфера. Это простой процесс, который состоит из нескольких шагов. Во-первых, если очередь пуста, мы генерируем исключение. Это не позволяет потребителям загружать слишком много элементов, что может привести к возврату данных, которые были предварительно удалены или извлечены из пустых пространств буфера.

Затем мы получаем значение массива в позиции хвоста, которое будет возвращено в конце процесса. Далее мы продвигаем хвост на одно пространство, увеличивая значение индекса. Если указатель достигает размера буфера, мы возвращаем его в ноль, чтобы следить за циклическим характером структуры данных. В коде это достигается с помощью оператора модуля. Продвижение определяется в отдельном методе NextPosition, поскольку эта функциональность будет повторно использоваться. Поскольку количество элементов в буфере теперь меньше, мы уменьшаем переменную длины до правильного значения.

Код метода показан ниже. Обратите внимание, что добавлена блокировка, чтобы гарантировать, что указатели не могут быть изменены другим процессом.

public T Dequeue()
{
    lock (_lock)
    {
        if (IsEmpty) throw new InvalidOperationException("Queue exhausted");
 
        T dequeued = _buffer[_tail];
        _tail = NextPosition(_tail);
        _length--;
        return dequeued;
    }
}
 
private int NextPosition(int position)
{
    return (position + 1) % _bufferSize;
}

Значения очереди

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

public void Enqueue(T toAdd)
{
    lock (_lock)
    {
        _head = NextPosition(_head);
        _buffer[_head] = toAdd;
        if (IsFull)
            _tail = NextPosition(_tail);
        else
            _length++;
    }
}

Использование кольцевого буфера

Теперь мы можем протестировать круговой буфер, запустив и сняв с охраны предметы. Для первого теста попробуйте код, показанный ниже. Он создает небольшой буфер с пятью целыми числами. Пять значений помещаются в очередь, а затем удаляются, показывая, что порядок элементов сохранен.

CircularBuffer<int> queue = new CircularBuffer<int>(5);
 
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
queue.Enqueue(4);
queue.Enqueue(5);
 
while (!queue.IsEmpty)
{
    Console.WriteLine("Dequeued {0}", queue.Dequeue());
}
 
/*Вывод
 
Dequeued 1
Dequeued 2
Dequeued 3
Dequeued 4
Dequeued 5
 
*/

Второй пример показывает, что происходит, когда емкость очереди превышена. Здесь шесть элементов добавляются в очередь, которая может содержать только пять. При удалении мы видим, что самый старый элемент был отброшен.

CircularBuffer<int> queue = new CircularBuffer<int>(5);
 
queue.Enqueue(1);
queue.Enqueue(2);
queue.Enqueue(3);
queue.Enqueue(4);
queue.Enqueue(5);
queue.Enqueue(6);
queue.Enqueue(7);
 
while (!queue.IsEmpty)
{
    Console.WriteLine("Dequeued {0}", queue.Dequeue());
}
 
/* Вывод
 
Dequeued 3
Dequeued 4
Dequeued 5
Dequeued 6
Dequeued 7
 
*/

Если статья оказалась вам полезна, то я не откажусь от благодарности в денежном эквиваленте. Если вам что-то непонятно, то вы всегда можете написать мне на почту up777up@yandex.ru – за небольшую плату вам будет оказана квалифицированная помощь по алгоритмам, структурам данных или любым другим областям теоретического и практического программирования на C# (.NET). Также я могу предложить вам свои услуги по программированию и на других языках: C++, Java, PHP, JavaScript.