Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to efficiently wrap the index of a fixed-size circular buffer

I have a fixed size circular buffer (implemented as an array): upon initialization, the buffer gets filled with the specified maximum number of elements which allows the use of a single position index in order to keep track of our current position in the circle.

What is an efficient way to access an element in the circular buffer? Here is my current solution:

int GetElement(int index)
{
    if (index >= buffer_size || index < 0)
    {
        // some code to handle the case
    }
    else
    {
        // wrap the index
        index = end_index + index >= buffer_size ? (index + end_index) - buffer_size : end_index + index;
    }

    return buffer[index];
}

Some definitions:
end_index is the index of the element immediately after the last element in the circle (it would also be considered the same as the start_index, or the first element of the circle).
buffer_size is the maximum size of the buffer.

like image 800
Kiril Avatar asked Feb 01 '11 21:02

Kiril


People also ask

How do you know if a circular buffer is full?

Determining if a Buffer is Full Both the “full” and “empty” cases of the circular buffer look the same: head and tail pointer are equal. There are two approaches to differentiating between full and empty: “Waste” a slot in the buffer: Full state is head + 1 == tail.

Is circular buffer the same as ring buffer?

A circular buffer is a popular way to implement a data stream because the code can be compact. A ring buffer is also known as a circular buffer, circular queue or cyclic buffer.


1 Answers

Best I've come up with is:

public static int Wrap(int index, int n)
{
    return ((index % n) + n) % n;
}

(Assuming you need to work with negative numbers)

like image 143
mpen Avatar answered Sep 22 '22 12:09

mpen