[Qt-interest] circular buffer container

[Sean Harmer]

Hi André,

On Friday 23 April 2010 13:30:31 Andre Somers wrote:
> On 23-4-2010 11:38, Sean Harmer wrote:
> > Hi All,
> > 
> > Just in case anybody is doing data acquisition/logging type work, I have
> > just submitted a QCircularBuffer class as a merge request to gitorious.
> > The merge request is here:
> > 
> > http://qt.gitorious.org/qt/qt/merge_requests/2364
> > 
> > This is my first merge request of any size so I would really appreciate
> > any feedback that you can give on API, implementation and documentation
> > omissions etc.
> > 
> > Many thanks in advance,
> 
> First of all, I like the idea of adding a circular buffer to Qt. Very nice.

Thank you for taking a look at this.

> I did wonder when I glanced over your implementation: would it not have
> been much easier to implement this based on one of the exising container
> classes instead? That would result, I think, in an easier to maintain
> solution, as you have to do the heavy lifting of memory operations only
> once. This is how QQueue and QStack are implemented: a bit of sugar on
> top of QList and QVector respectively. To me, it seems like a circular
> buffer is not much more than a QQueue with a limited number of items in
> it, right? Is there a reason you chose a from-scratch aproach?

I seem to remember considering this approach but then decided against it 
because for some function implementations it was just easier to be able to 
directly shuffle items around in memory without having to go through the 
QVector API. Having the QVector API would not buy you anything in certain 
cases - the insert() and remove() functions for example try very hard to 
minimise the amount of copying that is performed. If I used the approach of a 
wrapper around QVector I would have simply had to access the underlying array 
using the data() function of QVector anyway so I would not have really gained 
much.

Also by doing it from scratch I was able to use the QSharedData and 
QSharedDataPointer classes to handle the implicit sharing for me. QVector was 
written before these classes were available and so it does the same job 
manually.

> I have created similar datastructures myself (based on the existing Qt
> datastructures) in the past. I found that often there are other criteria
> that are relevant than just what the oldest bit of data is. Wouldn't it
> make your data structure more versatile if you would provide an optional
> way to determine which item to drop first?
> 
> Let me give you an example: A long time ago, I implemented a system to
> store measurements of the windvector for a flight computer for glider
> pilots. These measurements had different quality, and we had an
> indication for that quality. Because of memory constraints, we only kept
> a limited number of such measurements in memory to determine the current
> wind. The selection of what item to drop, was a function of that quality
> *and* the age of the measurement. I can image similar constraints in
> other applications. You talk about data logging or visualisation
> applications in your merge request. Would also there not only the age of
> a piece of data, but also it's importance play a role? For instance, say
> you want to keep a log of events on a server. These come in the form of
> errors, severe warnings, warnings and information messages. Personally,
> I would build the application in a way that it would keep te errors and
> the severe warnings (perhaps detections of attemted server breakins?)
> longer in the displayed log than the informational and low-importantance
> warnings.
> However, such a feature may be out of scope :-)

I see what you mean and can understand the reason for it but I think it is out 
of scope for this particular class as I wanted it to always have O(1) 
append()/prepend() behaviour. If there is some additional criteria on which 
item to drop then these become O(n) operations as you potentially have to 
search the entire container to decide which item to drop. It should be 
relatively simple to encapsulate this class to provide that functionality 
though. Maybe I'll take a look at such a class next.

Thank you very much for your comments though.

All the best,

Sean

> André
> 
> - just another Qt user

Me too ;-)