Growable ringbuffer with a limit to capacity

[coderedart]

I don't know if this is a popular use case, but considering #84 the road to 1.0, i thought it is better to bring it up now rather than later.

The idea is a Growable RingBuffer which behaves like a VecDeque (or even a simple Vec) when pushing new elements until a certain limit (capacity) by growing itself, and then it becomes a RingBuffer by not growing and just overwriting old elements with new elements.

A simple example:
If you are parsing a zip archive and listing the file names, then a malicious actor might upload an archive with lots of files. If you used a GrowableAllocRingBuffer, you would keep allocating for all those files until you run out of memory. If you wanted to limit the max number of files, then you will have to choose an arbitrary limit and pre-allocate a large ringbuffer. But, as most zip archives will only have a few files, you are wasting memory if you pre-allocate too much. Here, it would help to have a growable ring buffer that grows only when needed, but also has a max limit, so as to start acting like a ring buffer and avoid running out of memory.

Another Example: Lets take the example of logging errors. If there is something wrong, i want the most recent 100 lines of error logs. But, most of the time, there will be very few errors, and pre-allocating space for 100 lines of error logs seems like a waste of space. And if i use a GrowableAllocRingBuffer, i will need to check for the limit every time i am pushing a new element and reallocate if under limit. That is a very error prone approach.

The sensible alternative is obviously to make a newtype over the existing GrowableAllocRingBuffer, but i think this is generally a useful enough structure to have in the library itself.

Anytime there is a need for a large ringbuffers, and you don't want to pay for the large allocation upfront, this structure would be very helpful to have.

EDIT: In my particular use case, it is about mlua mods/plugins for my app. I will provide a egui tracing window like

This will help the users (or plugin devs) debug the plugins, in case of any misbehavior. And as we only need the most recent X (eg: 200) number of log entries, RingBuffer is perfect for this. But most plugins work fine, and it would be a waste to allocate such a huge ring buffer for them. And if i use a VecDeque, a malicious plugin would just spam logs to trigger out-of-memory crash.

A maximum limit would allow the user to scale the RingBuffer only when necessary at runtime, while still providing a safety measure by not letting it grow too much.

[jdonszelmann]

Hmm, that's an interesting idea. I'm not sure how useful it is, but if it's useful to you it might be to others. As you've noted, we do have a growable ringbuffer, but growable containers in rust never shrink their size. We'd manually need to call shrink to fit or similar methods.

Alternatively we can just expose the shrink method on growable ringbuffers so users can do it themselves. In fact, I think we already do that through the deref impl.

@NULLx76 what do you think about a data structure like this?

[NULLx76]

This definitely sounds like it can be useful, and I think the implementation should be relatively straightforward, so I do think we can provide it. Also, as the use case is relatively well-defined.