Circular Buffer

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 bounded queue when separate indices are used for inserting and removing data. The queue can be safely shared between threads (or processors) without further synchronization so long as one processor enqueues data and the other dequeues it. (Also, modifications to the read/write pointers must be atomic, and this is a non-blocking queue--an error is returned when trying to write to a full queue or read from an empty queue).

Note that a circular buffer with n elements is usually used to implement a queue with n-1 elements--there is always one empty element in the buffer. Otherwise, it becomes difficult to distinguish between a full and empty queue--the read and write pointers would be identical in both cases.

Circular buffers are a key concept in ...

DualMace
LogicAnalyzer
StatementTrapHandler
Media Processing
DeviceDrivers, used for queues between front and back ends

Use a CircularBuffer for data that streams by. Use a DoubleBuffer for data that is generated from start to finish and only then replaces a previous generation.

If the buffer is already full and we try to add another item, what do we do ?

It's best to

block the writing process. Wait until the reading process pulls out an item to make space for the new item.

But sometimes the data comes from some physical hardware that *can't* wait (LogicAnalyzer, airplane BlackBox, StatementTrapHandler ...). In that case, we're going to lose data sooner or later.

In most cases, more recent data is more important than old data, so we

Delete (remove from the queue) the oldest item, making space for the new item.

DoubleBuffer and TripleBuffer can be thought of as special cases of CircularBuffer (where the CircularBuffer is 2 or 3 objects long, and each object is itself a buffer).

How many items are in the queue ?

Some people use a integer to remember exactly how many items are in the queue.

With this "extra" data, a buffer of n elements can hold the full n data items, rather than n-1 data items. When both pointers point to the same location (buffer.insert == buffer.remove), then buffer.size distinguishes between the empty buffer (0 == buffer.size) or a full buffer ( n == buffer.size ).

Other people don't like this "extra" data -- it's too much hassle to keep it synchronized with the pointers. (It violates OnceAndOnlyOnce). Easier just to make the buffer 1 element larger. If we ever want to know the size, use

   size = (n + buffer.insert - buffer.remove) mod n;

Does anybody know how easy or difficult is to remove an entry from the middle of the circular buffer?

It's a big pain; I would consider a different data structure for that. Perhaps something like a PriorityQueue .

Implementing it as a CircularLinkedList of LeasedStrings solves this, while creating a (usually) unacceptable level of complexity. YMMV. What is implied is that the buffer is actually a queue of not-necessarily-consecutive data. Alternatively you can shift the buffer contents to fill in where you've removed data and, while this is simpler, it's not terribly RealTime-friendly.

In either case, it's not trivial.

The SimplestThing is to somehow "blank" the entry that you want removed -- overwrite it with space characters, or null pointers, or some other way of indicating "I am not a valid entry -- ignore and skip over me".

Most circular buffers contain fixed-length elements. Storing variable-length objects can be tricky: you're forced to break the last element into 2 parts when you reach the end of the buffer and wrap around, unless you use a BipBuffer? ( http://www.codeproject.com/internet/bipbuffer.asp ).

Well, the time difference is big so I am uncertain how useful this will be to you but interms of simplicity of programming a CircularLinkedList would probably be best with a counter specifying the total number of entries in the queue so that you can skip over n/2 of these elements and remove the "middle" element. "Middle" as for even number of entries there is no true middle. But as stated before the running time of this will be very bad fo example if you had millions elements each of these could take seconds. Not much for each of them but if you wanted to modify a list currently containning a million entries a million times that is 1,000,000 seconds or more. I have often thought of combining hash tables with doubley linked lists to make updates fast but... I have never tried to program it.