package ring
import "go.abhg.dev/container/ring"
Package ring implements a FIFO queue backed by a ring buffer.
Its main advantage over a queue backed by a slice or container/list is that it requires significantly fewer allocations for specific usage patterns.
- consistent rate of pushes and pops
- bursts of pushes followed by bursts of pops
Implementation
It's valuable to understand how the queue works under the hood so that you can reason about its performance characteristics and where it might be useful.
The queue is backed by a ring buffer: a slice that wraps around. When the queue is full, the ring buffer grows by doubling its capacity.
A ring buffer is a slice with two pointers: head and tail. The contents of the queue are usually [head:tail]. The queue is empty if head == tail.
+-------------------------------+
| ... | head | ... | tail | ... |
+-------------------------------+
'............'
Every pop moves the head forward. Every push moves the tail forward.
When the tail reaches the end of the current buffer, it wraps around to the beginning if there's room. At this point, the contents of the queue are [head:] + [:tail].
+-------------------------------+ | ... | tail | ... | head | ... | +-------------------------------+ ......' '.............
If there's no room for a push, the ring buffer grows by doubling its capacity.
When the head reaches the end of the current buffer, it wraps around to the beginning too, continuing to chase the tail. If it catches up with the tail, the queue is full.
Index
Types
type MuQ
type MuQ[T any] struct { // contains filtered or unexported fields }
MuQ is a thread-safe FIFO queue backed by a ring buffer. The zero value for MuQ is an empty queue ready to use.
MuQ is safe for concurrent use. If you need to use it from a single goroutine, use Q instead.
func NewMuQ
func NewMuQ[T any](capacity int) *MuQ[T]
NewMuQ returns a new thread-safe queue with the given capacity.
func (*MuQ[T]) Clear
func (q *MuQ[T]) Clear()
Clear removes all items from the queue. It does not adjust its internal capacity.
This is an O(1) operation and does not allocate.
func (*MuQ[T]) Empty
func (q *MuQ[T]) Empty() bool
Empty returns true if the queue is empty.
This is an O(1) operation and does not allocate.
func (*MuQ[T]) Len
func (q *MuQ[T]) Len() int
Len returns the number of items in the queue.
This is an O(1) operation and does not allocate.
func (*MuQ[T]) Push
func (q *MuQ[T]) Push(x T)
Push adds x to the back of the queue.
This operation is O(n) in the worst case if the queue needs to grow. However, for target use cases, it's amortized O(1). See package documentation for details. If your usage pattern is bursts of pushes followed by bursts of pops,
func (*MuQ[T]) Snapshot
func (q *MuQ[T]) Snapshot(dst []T) []T
Snapshot appends the contents of the queue to dst and returns the result.
Use dst to avoid allocations when you know the capacity of the queue or pass nil to let the function allocate a new slice.
The returned slice is a copy of the internal buffer and is safe to modify.
func (*MuQ[T]) TryPeek
func (q *MuQ[T]) TryPeek() (x T, ok bool)
TryPeek returns the item at the front of the queue. It returns false if the queue is empty. Otherwise, it returns true and the item.
This is an O(1) operation and does not allocate.
func (*MuQ[T]) TryPop
func (q *MuQ[T]) TryPop() (x T, ok bool)
TryPop removes and returns the item at the front of the queue. It returns false if the queue is empty. Otherwise, it returns true and the item.
This is an O(1) operation and does not allocate.
type Q
type Q[T any] struct { // contains filtered or unexported fields }
Q is a FIFO queue backed by a ring buffer. The zero value for Q is an empty queue ready to use.
Q is not safe for concurrent use. If you need to use it from multiple goroutines, use MuQ instead.
func NewQ
func NewQ[T any](capacity int) *Q[T]
NewQ returns a new queue with the given capacity. If capacity is zero, the queue is initialized with a default capacity.
The capacity defines the leeway for bursts of pushes before the queue needs to grow.
func (*Q[T]) Clear
func (q *Q[T]) Clear()
Clear removes all items from the queue. It does not adjust its internal capacity.
This is an O(1) operation and does not allocate.
func (*Q[T]) Empty
func (q *Q[T]) Empty() bool
Empty returns true if the queue is empty.
This is an O(1) operation and does not allocate.
func (*Q[T]) Len
func (q *Q[T]) Len() int
Len returns the number of items in the queue.
This is an O(1) operation and does not allocate.
func (*Q[T]) Peek
func (q *Q[T]) Peek() T
Peek returns the item at the front of the queue without removing it. It panics if the queue is empty.
This is an O(1) operation and does not allocate.
func (*Q[T]) Pop
func (q *Q[T]) Pop() T
Pop removes and returns the item at the front of the queue. It panics if the queue is empty.
This is an O(1) operation and does not allocate.
func (*Q[T]) Push
func (q *Q[T]) Push(x T)
Push adds x to the back of the queue.
This operation is O(n) in the worst case if the queue needs to grow. However, for target use cases, it's amortized O(1). See package documentation for details.
func (*Q[T]) Snapshot
func (q *Q[T]) Snapshot(dst []T) []T
Snapshot appends the contents of the queue to dst and returns the result. Use dst to avoid allocations when you know the capacity of the queue
dst := make([]T, 0, q.Len()) dst = q.Snapshot(dst)
Pass nil to let the function allocate a new slice.
q.Snapshot(nil) // allocates a new slice
The returned slice is a copy of the internal buffer and is safe to modify.
func (*Q[T]) TryPeek
func (q *Q[T]) TryPeek() (x T, ok bool)
TryPeek returns the item at the front of the queue. It returns false if the queue is empty. Otherwise, it returns true and the item.
This is an O(1) operation and does not allocate.
func (*Q[T]) TryPop
func (q *Q[T]) TryPop() (x T, ok bool)
TryPop removes and returns the item at the front of the queue. It returns false if the queue is empty. Otherwise, it returns true and the item.
This is an O(1) operation and does not allocate.