[boost] Re: Review Request: cyclic_buffer

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
        as necessary)
        
        To summarise:

        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
http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?circular+buffer

circular buffer

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.