From: Nigel Stewart (nigels_at_[hidden])
Date: 2003-06-10 08:20:54
>>The circular buffer I've needed (and coded) fits none of aforementioned
>>descriptions. But it is a circular buffer nonetheless.
I have been scratching around various bookshelves
in search of a definitive coverage of FIFO, LIFO,
circular lists, circular buffers, etc. I certainly
is interesting the variety of interpretations that
are possible from the supposedly simple concept of
a cyclic_buffer, etc...
This particular case sounds to me like a circular
list, rather than a circular buffer. "List" to me
sounds like something that has variable length,
while "Buffer" sounds like something of fixed
length. That's purely my 0.02... (Admittedly,
that ignores the pointer-based construction of lists)
>>Constant time push/pop_front, constant time push/pop_back. When begin
>>and end collide, reallocation automatically happens vector-like.
The only point I would like to add is that this could
be layered on top of the cyclic_buffer. (by intercepting
push_front, push_front and insert calls, resizing
Possible resize policies:
i. Capacity is fixed at compile time.
ii. Capacity is fixed at construction time.
iii. Capacity can be manually managed by client code.
iv. Capacity is allowed to grow automatically. (ala std::vector)
Possible insert handling policies:
I. Insert into full buffer results in no change.
II. Insert into full buffer results in overwriting opposite end.
Insertion into arbitrary position overwrites beginning, if necessary.
III. Insert into full buffer results in exception.
Possible resize to smaller capacity policies:
1. Keep left-most items. (ala std::vector)
2. Keep right-most items.
The general gist of some random googling on "circular buffers":
- Automatic resizing does not appear to be common.
- No established convention in relation to arbitrary insert.
- No established convention in relation to resizing to smaller capacity.
Some links.... (I have tried to capture a variety of angles)
FOLDOC - Computing Dictionary
An area of memory used to store a continuous stream of data by starting
again at the beginning of the buffer after reaching the end. A circular
buffer is usually written by one process and read by another. Separate
read and write pointers are maintained. These are not allowed to pass
each other otherwise either unread data would be overwritten or
invalid data would be read.
---- Wiki: Circular Buffer http://c2.com/cgi/wiki?CircularBuffer A circular buffer is a memory allocation scheme where memory is reused (reclaimed) when an index, incremented modulo the buffer size, writes over a previously used location. A circular buffer makes a queue when separate indices are used for inserting and removing data. The queue can be safely shared between processors without further syncronization so long as one processor enqueues data and the other dequeues it. ---- CERN Program Library Reference Manual http://wwwasdoc.web.cern.ch/wwwasdoc/hbook_html3/node29.html Circular buffer In an online environment you often want to have the last N events inside a buffer, so that the experiment can be monitored continuously. To make it easier to handle this case, you can use routine HFNOV, which fills a circular buffer in memory with RWN events, and when the buffer is full, overwrites the oldest Ntuple. ---- C# implementation of a Circular Buffer http://www.codeproject.com/csharp/CircularBuffer.asp Circular Buffers are use for data transfer between two processes. The Producer process places items into the Circular Buffer and the Consumer process removes them. The variable capacity of the Circular Buffer accommodates timing differences between the Producer and Consumer processes. The Circular Buffer can execute faster than than other queues that hold a variable amount of data since a fixed size block of memory is allocated just once from memory management and then reused (the Circular Buffer can be visualized as such but is actually a linear buffer with indices that wrap, modulo the buffer size, when the end of the buffer is reached). Often, the Circular Buffer is used to decouple two processes that operate at different speeds. For example, a faster Producer process can "burst" data into the buffer and continue with its processing. A slower Consumer of that data can then read it at its own rate without synchronizing and slowing the Producer. In this type of application, the average rate, over time, of both processes must be the same to avoid an over or under flow condition of the Circular Buffer (this is the "Synchronous Mode" of operation). Also, sequencing is critical. ---- A Java bounded blocking queue based on an array or list. http://gee.cs.oswego.edu/dl/concurrent/dist/docs/java/util/concurrent/ArrayBlockingQueue.html http://gee.cs.oswego.edu/dl/concurrent/dist/docs/java/util/concurrent/LinkedBlockingQueue.html The implementation is a classic "bounded buffer", in which a fixed-sized array holds elements inserted by propducers and extracted by consumers. Array-based queues typically have more predictable performance than linked queues but lower throughput in most concurrent applications. ---- Circular Buffers - com.Ostermiller.util Java Utilities http://ostermiller.org/utils/CircularBuffer.html Implements the circular buffer producer/consumer model for Objects. ---- Circular Buffers http://ece-www.colorado.edu/~ecen2120/Manual/CircBuff/CircBuff.html A circular buffer implements a bounded queue, a data structure that behaves like the checkout line at the supermarket: information is added to the end of the queue and removed from the front. Unlike the supermarket line, the circular buffer has a fixed maximum capacity. ---- Dictionary of Algorithms and Data Structures circular queue http://www.nist.gov/dads/HTML/circularQueue.html An implementation of a bounded queue using an array. bounded queue http://www.nist.gov/dads/HTML/boundedqueue.html A queue limited to a fixed number of items.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk