Circular buffer
From Freepedia
A circular buffer is a method of using memory within a computer program.
While the term "circular" is figurative, it alludes to the rotation through the buffer of the positions where the next data will be read and written. When moving through the buffer, the writer moves forward one step each time it writes, and when it passes the end of the buffer it starts again at the beginning. The reader moves through the buffer in the same way. As long as the reader is usually as fast as the writer, the buffer acts as a queue of the next data to be processed. If the writer is faster than the reader, the buffer can fill up.
The term ring buffer is also often used to describe a circular buffer.
Contents |
Implementation
A circular buffer requires storage space for the data of whatever size is desired and feasible, pointers to the current locations for reading and writing, and a method for determining when the buffer is empty or full. The processes of writing and reading also need to know how big the buffer is.
Buffer Space
The data storage for the buffer must be able to hold at least one unit of data, and should (if possible) be large enough to hold as much data as the data source will produce while the user of the data is either working with the data or is otherwise not reading it.
The units of data in the buffer can be anything, but are most often the smallest unit of data that the system can process efficiently.
Read and Write Pointers
The two pointers indicate where in memory the next data should be read or written. Each time data is read, the read pointer moves forward, going back to the beginning after reading the last thing in the buffer. Each time data is written, the write pointer moves forward, going back to the beginning after writing to the last position in the buffer. Depending on how the implementation handles writing to a full buffer, the writing process may also need to move the read pointer to make room fore more incoming data.
Empty and Full Buffers
If the read and write pointers point to the same spot in the buffer, that might mean that there is no data in the buffer (nothing has yet been written to the spot we next want to read from) or that the buffer is full (the next place we want to write already has in it data we have not yet read). There are two ways to make the distinction.
- Do not allow the write pointer to catch up to the read pointer. Consider the buffer full when there is only one element between the write pointer and the read pointer.
- Maintain a separate indication of whether there is data in the buffer. This can be the number of elements in the buffer, or a simple flag that is set to "Yes" each time data is written and "No" when the read pointer cateches up to the write pointer.
How to Write to a Full Buffer
If the data source produces more data than can fit in the buffer, there are three choices:
- If possible, tell the data source to wait until there is room in the buffer.
- If the latest data is the most important, write over the oldest data that has not been read, and move the read pointer to the position of the oldest remaining data.
- If the oldest data is the most important, ignore new data from the source until there is room again in the buffer.
How Full is the Buffer
If the implementation maintains a count of the number of elements in the buffer, that count can be checked at any time the information is necessary. Otherwise, the difference between the write pointer and the read pointer can provide that information. Assuming that the poisition of both pointers can be expressed as numbers and each element in the buffer increases the pointer's position by 1, the amount of data waiting in the buffer is w - r modulo n (with w representing the position of the write pointer, r representing the position of the read pointer, and n being the size of the buffer). If the result is zero, the process may need to check the indicator to see whether the buffer is empty or full.
Sharing the Buffer
The processes that read and write the data do not need to be able to communicate outside the buffer itself as long as there is an agreed method for losing data that does not fit in the buffer and the pointers to the reading and writing positions cannot be changed by both processes at exactly the same time.
See Also
- For information on the abstract data structure, and an implementation in scheme, see Queue.
- For a description of the behaviour and sample code, see FIFO.
