Circular buffer: Difference between revisions

Revision as of 07:10, 19 June 2022

Revision as of 01:02, 28 June 2022

Line 6:

== Overview ==

[[File:Circular Buffer Animation.gif|400px|thumbnail|A 24-byte keyboard circular buffer. When the write pointer is about to reach the read pointer—because the microprocessor is not responding—the buffer stops recording keystrokes. On some computers a beep would be played.]]

A circular buffer first starts out empty and has a set length. In the diagram below is a 7-element buffer:

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

Assume that 1 is written in the center of a circular buffer (the exact starting ___location is not important in a circular buffer):

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

Then assume that two more elements are added to the circular buffer — 2 & 3 — which get put after 1:

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

Line 59:

:[[Image:Circular buffer - 6789AB5 with pointers.svg|250px]]

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 are not enough to tell 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 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.</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.