Circular buffer: Difference between revisions

Revision as of 21:22, 12 September 2022

Latest revision as of 06:43, 10 April 2025

(43 intermediate revisions by 28 users not shown)

Line 1:

{{Short description|Data structure in computer science}}

{{Cleanup bare URLs|date=August 2022}}

[[Image:Circular buffer.svg|thumb|200px|A ring showing, conceptually, a circular buffer. This visually shows that the buffer has no real end and it can loop around the buffer. However, since memory is never physically created as a ring, a linear representation is generally used as is done below.]]

In [[computer science]], a '''circular buffer''', '''circular queue''', '''cyclic buffer''' or '''ring buffer''' is a [[data structure]] that uses a single, fixed-size [[buffer (computer science)|buffer]] as if it were connected end-to-end. This structure lends itself easily to buffering [[data stream]]s.<ref>{{citation|title=Operating Systems: Three Easy Pieces [Chapter: Condition Variables, figure 30.13]|url=http://pages.cs.wisc.edu/~remzi/OSTEP/threads-cv.pdf|

publisher=Arpaci-Dusseau Books|date=2014|first1=Remzi H.|last1=Arpaci-Dusseau|first2=Andrea C.|last2=Arpaci-Dusseau}}</ref> There were early circular buffer implementations in hardware.<ref>{{cite web|last1=Hartl|first1=Johann|title=Impulswiederholer - Telephone Exchange (video)|date=17 October 2011 |url=https://www.youtube.com/watch?v=_xI9tXi-UNs|publisher=Youtube|access-date=15 December 2021}}</ref><ref>{{cite web|last1=Fraser|first1=Alexander Gibson|title=US patent 3979733 Digital data communications system packet switch|url=https://patents.google.com/patent/US3979733A/en|publisher=US States Patent|access-date=15 December 2021}}</ref>

== Overview ==

Line 19:

:[[Image:Circular buffer - XX123XX.svg|250px]]

If two elements are removed, the two oldest values inside of the circular buffer would be removed. Circular buffers use FIFO (''[[first in, first out (computing)|first in, first out]]'') logic. In the example, 1 & 2 were the first to enter the circular buffer, they are the first to be removed, leaving 3 inside of the buffer.

:[[Image:Circular buffer - XXXX3XX.svg|250px]]

Line 33:

Alternatively, the routines that manage the buffer could prevent overwriting the data and return an error or raise an [[exception handling|exception]]. Whether or not data is overwritten is up to the semantics of the buffer routines or the application using the circular buffer.

Finally, if two elements are now removed then what would be returnedremoved is '''not''' 3A & 4B, but 5 & 6 because A5 & B6 overwroteare now the 3 & theoldest 4elements, yielding the buffer with:

:[[Image:Circular buffer - X789ABX.svg|250px]]

Line 46:

== Circular buffer mechanics ==

:[[Image:Hardware_circular_buffer_implementation_patent_us3979733_fig4.png|250px|thumb|Circular buffer implementation in hardware, US patent 3979733, fig4]]

A circular buffer can be implemented using a [[pointer (computer programming)|pointer]] and four integers:<ref name="Liu Wu Das 2021 p. 117">{{cite book |last1=Liu |first1=Z. |url=https://books.google.com/books?id=si1CEAAAQBAJ&pg=PA117 |title=Wireless Algorithms, Systems, and Applications: 16th International Conference, WASA 2021, Nanjing, China, June 25–27, 2021, Proceedings, Part II |last2=Wu |first2=F. |last3=Das |first3=S.K. |publisher=Springer International Publishing |year=2021 |isbn=978-3-030-86130-8 |series=Lecture Notes in Computer Science |page=117 |access-date=2023-09-04}}</ref>

A circular buffer can be implemented using two [[pointer (computer programming)|pointer]]s and two integers:

* buffer start in memory

* buffer capacity (Lengthlength)

* write to buffer index (end)

* read from buffer index (start)

Line 62:

In the beginning the indexes end and start are set to 0. The circular buffer write operation writes an element to the end index position and the end index is incremented to the next buffer position. The circular buffer read operation reads an element from the start index position and the start index is incremented to the next buffer position.

The start and end indexes alone are not enough to telldistinguish between buffer full or empty state while also utilizing all buffer slots,<ref>{{cite web|last1=Chandrasekaran|first1=Siddharth|title=Implementing Circular/Ring Buffer in Embedded C|url=https://embedjournal.com/implementing-circular-buffer-embedded-c/|website=Embed Journal|publisher=EmbedJournal Team|access-date=14 August 2017|archive-url=https://web.archive.org/web/20170211031659/http://embedjournal.com/implementing-circular-buffer-embedded-c/|archive-date=11 February 2017|url-status=live|date=2014-05-16}}</ref> but can be if the buffer only has a maximum in-use size of Length -− 1.<ref>[https://www.kernel.org/doc/Documentation/circular-buffers.txt#:~:text=A%20circular%20buffer%20is%20a,next%20item%20in%20the%20buffer Circular buffers] kernel.org</ref> In this case, the buffer is empty if the start and end indexes are equal and full when the in-use size is Length -− 1.

Another solution is to have another integer count that is incremented at a write operation and decremented at a read operation. Then checking for emptiness means testing count equals 0 and checking for fullness means testing count equals Length.<ref>{{cite web |title=ArrayQueue: An Array-Based Queue |url=http://opendatastructures.org/ods-python/2_3_ArrayQueue_Array_Based_.html |website=Open Data Structures (in pseudocode) |first=Pat |last=Morin|author-link= Pat Morin |access-date=7 November 2015 |archive-url=https://web.archive.org/web/20150831023453/http://opendatastructures.org/ods-python/2_3_ArrayQueue_Array_Based_.html |archive-date=31 August 2015 |url-status=live }}</ref>

The following source code is a [[C (programming language)|C]] implementation together with a minimal test. Function put() puts an item in the buffer, function get() gets an item from the buffer. Both functions take care about the capacity of the buffer :

<syntaxhighlight lang="c">

#include <stdio.h>

#define BUFLEN 3

intenum buf[BUFLEN];{ N = /*10 array}; to be// treatedsize asof circular buffer */

int end = 0; /* write index */

int start = 0; /* read index */

int buffer [N]; // note: only (N - 1) elements can be stored at a given time

void put(int item)

int writeIndx = 0;

int readIndx = 0;

voidint put (int item)

{

if ((writeIndx + 1) % N == readIndx)

buf[end++] = item;

{

end %= N;

// buffer is full, avoid overflow

end %=return N0;

}

bufbuffer[end++writeIndx] = item;

writeIndx = (writeIndx + 1) % N;

return 1;

}

int get (int * value)

{

if (readIndx == writeIndx)

{

// buffer is empty

return 0;

}

*value = buffer[readIndx];

readIndx = (readIndx + 1) % N;

return 1;

}

int getmain ()

{

// test circular buffer

int item = buf[start++];

int value start %= N1001;

while (put return(value item++));

while (get (& value))

printf ("read %d\n", value);

return 0;

}

</syntaxhighlight>

== Optimization ==

A circular-buffer implementation may be optimized by [[Mmap|mapping]] the underlying buffer to two contiguous regions of [[virtual memory]].<ref>{{Citecite web |title=mikeash.com: Friday Q&A 2012-02-17: Ring Buffers and Mirrored Memory: Part II |author=Mike Ash |work=mikeash.com |date=2012-02-17 |access-date=2019-01-10 |url=https://www.mikeash.com/pyblog/friday-qa-2012-02-17-ring-buffers-and-mirrored-memory-part-ii.html |archive-url=https://web.archive.org/web/20190111054903/https://www.mikeash.com/pyblog/friday-qa-2012-02-17-ring-buffers-and-mirrored-memory-part-ii.html |archive-date=2019-01-11 |url-status=live }}</ref>{{Disputed inline|talk=Talk:Circular_buffer#Optimization|date=January 2022}} (Naturally, the underlying buffer‘s length must then equal some multiple of the system’s [[Page (computing)|page size]].) Reading from and writing to the circular buffer may then be carried out with greater efficiency by means of direct memory access; those accesses which fall beyond the end of the first virtual-memory region will automatically wrap around to the beginning of the underlying buffer. When the read offset is advanced into the second virtual-memory region, both offsets—read and write—are decremented by the length of the underlying buffer.

== Fixed-length-element and contiguous-block circular buffer ==

Perhaps the most common version of the circular buffer uses 8-bit bytes as elements.

Some implementations of the circular buffer use fixed-length elements that are bigger than 8-bit bytes—16-bit integers for audio buffers, 53-byte [[Asynchronous Transfer Mode|ATM]] cells for telecom buffers, etc. Each item is contiguous and has the correct [[data alignment]], so software reading and writing these values can be faster than software that handles non-contiguous and non-aligned values.

[[Ping-pong buffer]]ing can be considered a very specialized circular buffer with exactly two large fixed-length elements.

The ''bip buffer'' (bipartite buffer) is very similar to a circular buffer, except it always returns contiguous blocks which can be variable length. This offers nearly all the efficiency advantages of a circular buffer while maintaining the ability for the buffer to be used in APIs that only accept contiguous blocks.<ref name="cooke">Simon Cooke (2003), [http://www.codeproject.com/Articles/3479/The-Bip-Buffer-The-Circular-Buffer-with-a-Twist "The Bip Buffer - The Circular Buffer with a Twist"] {{Webarchive|url=https://web.archive.org/web/20121006080117/http://www.codeproject.com/Articles/3479/The-Bip-Buffer-The-Circular-Buffer-with-a-Twist |date=2012-10-06 }}</ref>

Fixed-sized compressed circular buffers use an alternative indexing strategy based on elementary number theory to maintain a fixed-sized compressed representation of the entire data sequence.<ref name="gunther">{{cite journal|last1=Gunther|first1=John C.|title=Algorithm 938: Compressing circular buffers|journal=ACM Transactions on Mathematical Software|date=March 2014|volume=40|issue=2|pages=1–12|doi=10.1145/2559995|s2cid=14682572 }}</ref>