Menu
What are some of the uses of circular buffer?
What are the benefits of using a circular buffer?
is it an alternative to double linked list?
353
In computer science, a circular buffer, circular queue, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams. There were early circular buffer implementations in hardware.
Circular Buffers can be implemented in two ways, using an array or a linked list. An empty object array along with its capacity is initialized inside the constructor as the type of elements added is unknown. Two pointers namely head and tail are maintained for insertion and deletion of elements.
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.
A Circular Queue is an extension of the Queue data structure such that the last element of the queue links to the first element. It is known as Ring Buffer, Circular Buffer or Cyclic Buffer.
I've used it for an in-memory log with a restricted size. For example, the application would write log entries while processing user requests. Whenever an exception occurred (that would be disruptive to the processing) the log records currently in memory would be dumped along with it.
The benefit of a circular buffer is, that you don't need infinite amounts of memory, since older entries get overridden automatically. The "challange" is, that you need to find a suitable size for your usecase. In the example above, it would be very unfortunate when the log record with the most vital information about the exception would have already been overridden.
Some systems/applications have tools to let you extract the current content of the buffer on demand, and not only when it would be extract automatically (if ever).
I believe ETW and the CLRs stress log, amongst many other system's kernel or highperformance trace/logging, are implemented that way.
The concept of using such buffers for in-memory tracing/logging is actually pretty common (not to say that this is the only use - certainly not), because it is way faster than written records to a file/database that you might never be interested in unless an error occurs. And on a related note, it conserves harddisk space.
85
Circular buffers are good for serial data streams in embedded systems. Microcontrollers often have a UART to handle a serial byte coming in, these need to be stored in order and dealt with later (bytes often come in at a faster rate than they can be handled).
The buffer effectively splits the timing-critical response required (when the bytes come in, in microseconds) to the non timing-critical response to the whole message (for example displaying the message which came in, in milliseconds), e.g.:
1) Upon the receipt of a byte the UART can generate an interrupt to which the software responds by quickly taking the received byte and shoves it onto the end of the buffer.
2) Background software routines can then regularly check if the buffer has anything in it yet and empty it as required.
As the circular buffer size can be defined pre-compilation the size is then limited. This helps improve space efficiency and should eliminate memory corruption at a trade off to how many bytes can be received before data starts to become lost.
42
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
