README
¶
container/ring
container/ring provides an efficient queue data structure intended to be used in performance-sensitive contexts with usage patterns that have:
- a similar rate of pushes and pops
- bursts of pushes followed by bursts of pops
Example
As an example, this is a good place to store pending nodes during a breadth-first traversal of a graph. It will allocate only if a node has more direct children than capacity in the queue. For example, given a hypothetical tree structure:
var pending ring.Q[Node]
pending.Push(root)
for !pending.Empty() {
current := pending.Pop()
visit(current)
for _, child := range current.Children {
pending.Push(child)
}
}
See API Reference for more details.
Motivation
I often find myself needing a queue in projects.
In a hurry, I reach for container/list or a slice.
However, they are both allocation-heavy (depending on usage pattern).
This repository largely exists so that there's a known working version of a more efficient queue implementation (for specific usage patterns) that I can use or copy-paste directly where I need. Feel free to use it in the same way if it meets your needs.
License
This software is made available under the MIT license.
Documentation
¶
Overview ¶
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 ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type MuQ ¶ added in v0.2.0
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 (*MuQ[T]) Clear ¶ added in v0.2.0
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 ¶ added in v0.2.0
Empty returns true if the queue is empty.
This is an O(1) operation and does not allocate.
func (*MuQ[T]) Len ¶ added in v0.2.0
Len returns the number of items in the queue.
This is an O(1) operation and does not allocate.
func (*MuQ[T]) Push ¶ added in v0.2.0
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 ¶ added in v0.2.0
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 ¶ added in v0.2.0
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 ¶ added in v0.2.0
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.
Example (Loop) ¶
package main
import (
"fmt"
"go.abhg.dev/container/ring"
)
func main() {
var q ring.MuQ[int]
for i := 0; i < 3; i++ {
q.Push(i)
}
for v, ok := q.TryPop(); ok; v, ok = q.TryPop() {
fmt.Println(v)
}
}
Output: 0 1 2
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 ¶
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 ¶
Empty returns true if the queue is empty.
This is an O(1) operation and does not allocate.
func (*Q[T]) Len ¶
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.
Example (Loop) ¶
package main
import (
"fmt"
"go.abhg.dev/container/ring"
)
func main() {
var q ring.Q[int]
for i := 0; i < 3; i++ {
q.Push(i)
}
for !q.Empty() {
fmt.Println(q.Pop())
}
}
Output: 0 1 2
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 ¶ added in v0.2.0
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 ¶ added in v0.2.0
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 ¶ added in v0.2.0
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.
Example (Loop) ¶
package main
import (
"fmt"
"go.abhg.dev/container/ring"
)
func main() {
var q ring.Q[int]
for i := 0; i < 3; i++ {
q.Push(i)
}
for v, ok := q.TryPop(); ok; v, ok = q.TryPop() {
fmt.Println(v)
}
}
Output: 0 1 2
Source Files