Lecture
A ring buffer, or circular buffer (English: ring-buffer) — is a data structure that uses a single fixed-size buffer in such a way as if, after the last element, the first one immediately followed again. Such a structure easily provides the ability to buffer data streams.
A ring buffer is created empty, with some predetermined length. For example, this is a seven-element buffer:
Suppose that a «1» is written into the middle of the buffer (in a ring buffer, the exact starting cell does not matter):
Then suppose that after the one, two more elements were added — «2» and «3»:
If after this two elements must be removed from the buffer, the two oldest elements are chosen. In our case, elements «1» and «2» are removed, and only «3» remains in the buffer:
If the buffer contains 7 elements, then it is full:
If writing to the buffer continues without taking its fullness into account, then new data will start overwriting old data. In our case, by adding elements «A» and «B», we will overwrite «3» and «4»:
In another implementation variant, the procedures serving the buffer can prevent data from being overwritten and return an error or throw an exception. Whether or not overwriting occurs is left to the discretion of the buffer's servicing procedures or the application using the ring buffer.
Finally, if two elements are now removed from the buffer, it will not be «3» and «4» that are removed, but «5» and «6», because «A» and «B» overwrote elements «3» and «4»; the buffer will arrive at the state:
A ring buffer implementation can be optimized by mapping the underlying buffer to two adjacent regions of virtual memory. (Naturally, the length of the underlying buffer must then equal some multiple of the system's page size.) Reading from and writing to the ring buffer can then be performed with greater efficiency through direct memory access; those accesses that go beyond the end of the first virtual memory region will automatically be carried over to the beginning of the underlying buffer. When the read offset advances into the second virtual memory region, both offsets — read and write — are decreased by the length of the underlying buffer.
Perhaps the most common version of a ring buffer uses 8-bit bytes as elements.
Some ring buffer implementations use fixed-length elements larger than 8 bits — 16-bit integers for audio buffers, 53-byte ATM cells for telecommunications buffers, and so on. Each element is contiguous and has correct data alignment, so software reading and writing these values can run faster than software processing non-contiguous and unaligned values.
«Ping-pong» buffering can be considered a highly specialized ring buffer with two large fixed-length elements.
A bip buffer (bipartite buffer) is very similar to a ring buffer, except that it always returns contiguous blocks, which can be of variable length. This provides almost all the efficiency advantages of a ring buffer, while retaining the ability to use the buffer in APIs that only accept contiguous blocks.
Compressed fixed-size ring buffers use an alternative indexing strategy, based on elementary number theory, to maintain a fixed-size compressed representation of the entire data sequence.
Implementation of a ring buffer in hardware, US patent 3979733, fig.4
A ring buffer can be implemented using a pointer and three integers:
This image shows a partially filled buffer with length = 7:
This image shows a full buffer with four overwritten elements (numbers 1 through 4):
At the start, the end and start indices are set to 0. A write operation on the circular buffer writes an element at the end index position, and the end index is advanced to the next buffer position. A read operation on the circular buffer reads an element from the start index position, and the start index is advanced to the next buffer position.
The start and end indices alone are not sufficient to distinguish the state of the buffer: full or empty, both of which use all of the buffer's slots, but can occur if the buffer only has a maximum used size of Length - 1. In this case the buffer is empty if the start and end indices are equal, and full when the used size equals Length - 1. Another solution is to have a separate integer counter that is incremented on a write operation and decremented on a read operation. Then checking for emptiness means checking whether the counter equals 0, and checking for fullness means checking whether the counter equals Length.
The ring buffer finds very wide application, including in microcontroller programming. This data structure is often used to organize various message queues and transmit-receive buffers of various communication interfaces. The popularity of the ring buffer is due to the fact that it is one of the simplest and most efficient ways to organize a FIFO (first in — first out) without using dynamic memory. There are many varieties of ring buffers.
Comments