antifuchs/o

Ring-buffers in go without interface{}

o - go ring buffers for arbitrary types without interface{}

This package provides the data structures that you need in order to implement an efficient ring buffer in go. In contrast to other ring buffer packages (and the Ring package in the go stdlib which really should not count as a ring buffer), this package has the following nice properties:

• It provides the minimum functionality and maximum flexibility necessary for your own ring buffer structure.
• It allows multiple modes of usage for different ring buffer usage scenarios.
• It does not require casting from interface{}.

Minimum functionality - what do you get?

This package handles the grody integer math in ring buffers (it's not suuuper grody, but it's not easy to get right on the first try. Let me help!)

That's it. You are expected to use the o.Ring interface provided by this package in your own structure, with a buffer that you allocate, and you're supposed to put things onto the right index in that buffer (with o.Ring doing the grody integer math).

You get two buffer data structures: One that works for all kinds of capacities, and one that is optimized for powers of two.

Maximum flexibility & multiple usage modes

The default usage mode for o.Ring is to .Push and .Shift for LIFO operations, similar to queues and typical log buffers. You can find an example in the ringio package implemented here. These functions return errors if you push onto a full ring, or if you shift from an empty ring.

You can also use Ring.ForcePush to insert a new element regardless of whether the ring is full, overwriting the element that's there.

And then, if you do not want to shift out elements to read them, you can use o.ScanFIFO and o.ScanLIFO to get an iterator over the occupied indexes in the ring (LIFO for oldest to newest, FIFO for newest to oldest), and iterate over your ring's buffer using those indexes - it's your data structure! You get to go entirely hog wild.

Why do this at all?

Depending on where you intend to use a "generic" ring buffer (that backs onto an array of interface{}), it sometimes is difficult to reason about whether what you get out is what you expect. The error handling code for that sometimes gets grody, but really - that isn't the reason why I did this.

Mostly, I did it as a semi-joke that I thought could be useful in a problem I was solving. Now that I've actually written this, I'm no longer sure it ever was a joke. People might acually want to use this and feel good about using it, and now I'm terrified because I think this might actually be a reasonable thing to use.

o's Issues

Ring is incorrect when not saturated

If the ring isn't "saturated" - i.e. has not been filled to capacity - then the Inspect method (and thus the Scan* helpers) will incorrectly return a range that includes one value past the end of the filled ring. See the following playground link for an example:

https://play.golang.org/p/v6H-fwd26SG

maskRing Shift should mask the return value

I think right now wrapping around the ring buffer once will cause maskRing.Shift to return values that are out of bounds. The return value should be masked.

github PR templates aren't working

I think I made the pull request templates wrong: A new PR doesn't offer any "kind" of pull request, and the form is blank.

I thought I'd done it according to https://help.github.com/en/articles/creating-a-pull-request-template-for-your-repository, but maybe not.

Idea: accountant for an LRU cache

A fixed-size LRU cache might be the perfect use case for this shape of solution:

• User defines a backing store as an array with a fixed size.
• LRU cache accountant keeps track of the index at which the entry would live.
• LRU cache accountant could even trigger expiry / finalization of elements, but maybe that would be over the top.