README
¶
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.
Documentation
¶
Overview ¶
Package o provides a ring-buffer accounting abstraction that allows you to build your own ring buffers without having to dynamically cast values from interface{} back and forth.
Implementing your own ¶
The trick to having a type-safe ring buffer is simple: You define a new structure that contains the accounting interface (defined here) and a buffer of the appropriate capacity on it. The accounting interface gives your code the indexes that it needs to update the ring at, and your code can go its merry way.
For an example, see the ring buffer backed ReadWriter defined in package ringio.
Behavior when full ¶
The ring buffer accountants defined in this package all return errors if they're full or empty. To simply overwrite the oldest element, use function ForcePush.
Non-destructive operations on Rings ¶
If your code needs to only inspect the contents of the ring instead of shifting them out, you can use the Inspect method (which returns ranges, see the next section) or a stateful iterator in either LIFO or FIFO direction available to do this conveniently:
o.ScanLIFO(ring) and o.ScanFIFO(ring)
See Scanner for defails and usage examples.
Ranges across a Ring ¶
A Ring assumes that all indexes between the first occupied index (the "read" end) and the last occupied index (the "write" end) are continuously occupied. Since rings wrap around to zero, that doesn't mean however, that each continuous index is greater than the index before it
To make it easier to deal with these index ranges, every operation that deals with ranges (e.g. Inspect, Consume, PushN) will return two Range objects, by convention named first and second.
These ranges cover the two parts of the buffer. Assume a ring buffer like this, x marking occupied elements and _ marking unoccupied ones:
0 1 2 3 4 5 6 7 (Capacity)
+---+---+---+---+---+---+---+
| x | _ | _ | x | x | x | x |
+---+---+---+---+---+---+---+
^ ^ Read end points here
|
+- Write end points here
The way o.Ranges represents a range between the Read and the Write end is:
first = o.Range{Start: 3, End: 7}
second = o.Range{Start: 0, End: 1}
Note that the End index of a range is the first index greater than the one that's occupied. This allows using these Range ends as points in a slice expression without modification.
Thread Safety ¶
None of the data structures provided here are safe from data races. To use them in thread-safe ring buffer implementations, users must protect both the accounting operations and backing buffer writes with a Mutex.
Credit ¶
The ring buffer accounting techniques in this package and were translated into go from a post on the blog of Juho Snellman, https://www.snellman.net/blog/archive/2016-12-13-ring-buffers/.
Index ¶
- Constants
- type Range
- type Ring
- func (r Ring) Capacity() uint
- func (r Ring) Consume() (first Range, second Range)
- func (r Ring) Empty() bool
- func (r Ring) ForcePush() uint
- func (r Ring) Full() bool
- func (r Ring) Inspect() (first Range, second Range)
- func (r Ring) Mask(i uint) uint
- func (r Ring) Push() (uint, error)
- func (r Ring) PushN(count uint) (first, second Range, err error)
- func (r Ring) Shift() (uint, error)
- func (r Ring) ShiftN(count uint) (first, second Range, err error)
- func (r Ring) Size() uint
- type Scanner
- type Slice
Examples ¶
Constants ¶
const ErrEmpty emptyErr = iota
ErrEmpty indicates a removal operation on an empty ring.
const ErrFull fullErr = iota
ErrFull indicates an addition operation on a full ring.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Range ¶
type Range struct {
Start uint // The first element of the range
End uint // The first element that is not part of the range.
}
Range is a normalized set of numbers representing continuous range of indexes that are occupied in the Ring. Start must always be <= End.
They can be used in go slice bounds like so:
[range.Start:range.End]
type Ring ¶
type Ring struct {
// contains filtered or unexported fields
}
Ring provides accounting functions for ring buffers.
Example ¶
A simple queue of strings that refuses to add elements when full.
package main
import (
"fmt"
"github.com/antifuchs/o"
)
func main() {
queueIndexes := o.NewRing(16)
for i := 0; i < 16; i++ {
next, _ := queueIndexes.Push()
fmt.Print(next, " ")
}
_, err := queueIndexes.Push()
fmt.Print(err)
}
Output: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 inserting into a full ring
func NewRing ¶
NewRing returns a new Ring data structure with the given capacity.
If cap is a power of 2, returns a Ring optimized for bitwise manipulation of the indexes.
If cap is 0, returns a Ring that does not perform any operations and only returns errors.
Otherwise, the returned data structure uses general modulo division for its integer adjustments, and is a lot slower than the power-of-2 variant.
func NewRingForSlice ¶
NewRingForSlice creates a Ring that fits a slice. The slice's type must implement o.Slice (which is also satisfied if the type implements sort.Interface).
It is not advisable to resize the slice after creating a ring for it.
Example ¶
package main
import (
"fmt"
"sort"
"github.com/antifuchs/o"
)
func main() {
// create some backing store:
store := make([]int, 90)
// put a ring on it:
ring := o.NewRingForSlice(sort.IntSlice(store))
// it is empty:
fmt.Println(ring.Empty())
}
Output: true
func (Ring) Capacity ¶
Capacity returns the number of continuous indexes that can be represented on the ring.
func (Ring) Consume ¶
Consume resets the ring to its empty state, returning a set of indexes that can be used to construct a copy of the elements that were occupied in the ring prior to resetting.
See also Inspect.
func (Ring) ForcePush ¶
ForcePush forces a new element onto the ring, discarding the oldest element if the ring is full. It returns the index of the inserted element.
Using ForcePush to insert into the Ring means the Ring will lose data that has not been consumed yet. This is fine under some circumstances, but can have disastrous consequences for code that expects to read consistent data. It is generally safer to use .Push and handle ErrFull explicitly.
func (Ring) Inspect ¶
Inspect returns a set of indexes that represent the bounds of the elements occupied in the ring.
Returned indexes ¶
Since a ring buffer consists of indexes that might wrap around to zero, callers of Inspect must use all returned Ranges to get an accurate picture of the occupied elements. The second range may be empty (Start & Length = 0) if there is nothing occupied on the left part of the buffer.
func (Ring) Mask ¶
Mask adjusts an index value (which potentially exceeds the ring buffer's Capacity) to fit the ring buffer and returns the adjusted value.
This method is probably most useful in tests, or when doing low-level things not supported by o.Ring yet. If you find yourself relying on this in code, please file a bug.
func (Ring) Push ¶
Push lets a writer account for a new element in the ring, and returns that element's index.
Returns ErrFull if the ring is filled to capacity.
func (Ring) PushN ¶
PushN bulk-pushes count indexes onto the end of the Ring and returns ranges covering the indexes that were pushed.
If the Ring can not accommodate all elements before filling up, PushN reserves nothing and returns ErrFull; the ranges returned in this case are meaningless and have zero length.
func (Ring) Shift ¶
Shift lets a reader account for removing an element from the ring for reading, returning that element's index.
Returns ErrEmpty if the ring has no elements to read.
func (Ring) ShiftN ¶
ShiftN bulk-"read"s count indexes from the start of the Ring and returns ranges covering the indexes that were removed.
If the Ring holds only fewer elements as requested, ShiftN reads nothing and returns ErrFull; the ranges returned in this case are meaningless and have zero length.
type Scanner ¶
type Scanner struct {
// contains filtered or unexported fields
}
Scanner implements iterating over the elements in a Ring without removing them. It represents a snapshot of the Ring at the time it was created.
A Scanner does not update its Ring's range validity when .Next is called. Adding or reading elements from the Ring while a Scanner is active can mean invalidated indexes will be returned from the Scanner.
func ScanFIFO ¶
ScanFIFO returns a Scanner for the given Ring that iterates over the occupied indexes in FIFO (newest to oldest) direction.
Example ¶
package main
import (
"fmt"
"github.com/antifuchs/o"
)
func main() {
ring := o.NewRing(17)
// Put stuff in the ring:
for i := 0; i < 19; i++ {
ring.ForcePush()
}
// Now find all the indexes in first-in/first-out order:
s := o.ScanFIFO(ring)
for s.Next() {
fmt.Print(s.Value(), " ")
}
}
Output: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1
func ScanLIFO ¶
ScanLIFO returns a Scanner for the given Ring that iterates over the occupied indexes in LIFO (newest to oldest, think of a stack) direction.
Example ¶
package main
import (
"fmt"
"github.com/antifuchs/o"
)
func main() {
ring := o.NewRing(17)
// Put stuff in the ring:
for i := 0; i < 19; i++ {
ring.ForcePush()
}
// Now find all the indexes in last-in/first-out order:
s := o.ScanLIFO(ring)
for s.Next() {
fmt.Print(s.Value(), " ")
}
}
Output: 1 0 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2
func (*Scanner) Next ¶
Next advances the Scanner in the traversal direction (forward in FIFO direction, backward in LIFO), returning a boolean indicating whether there *is* a next position in the ring.
It is safe to call Next after reaching the last position - in that case, it will always return a negative result.
func (*Scanner) Value ¶
Value returns the next position in the traversal of a Ring's occupied positions, in the given order, after Next() returned a positive value.
If Value is called before the first call to Next, or after Next returned a result indicating there are no more positions, Value panics,
Source Files
Directories