README
¶
package queue
A double-ended queue using a resizable ring buffer as its store
Data structure
- Generalize queue and stack
- Efficiently add and/or remove items at either end of the with O(1) performance
- Support queue operations (FIFO) with
enqueueadd to the back anddequeueto remove from the front. - Support stack operations (LIFO) with
pushandpop.pushandenqueueare the same action. - Optimize implementation for CPU and GC performance.
- Resize the circular buffer automatically by powers of two
- Grow when additional capacity is needed
- Shrink when only a quarter of the capacity is used
- Use bitwise arithmetic for all calculations. Since growth is by powers of two, adding elements will only cause O(log n) allocations.
- Wrap around the buffer to reuse previously used space making allocation unnecessary until all buffer capacity is used.
- Support concurrent use. Use the fastest sync primitives possible.
- Use only stdlib in the construction of this package.
- Require the user to specify the type upon creating the queue.
- Use generics to make sure that all code is type safe.
General Build
- Make sure that all code provide will build properly before sharing it
- Include tests to make sure that all code paths in all functions are tested.
Documentation
¶
Overview ¶
Package queue provides a generic, thread-safe, dynamically resizing double-ended queue (deque). It offers efficient O(1) time complexity for adding and removing items from both ends, making it suitable for both queue (FIFO) and stack (LIFO) operations.
The queue automatically resizes its internal buffer by powers of two to optimize for CPU and garbage collection performance, growing when capacity is needed and shrinking when the buffer is less than a quarter full. It uses bitwise arithmetic for efficient index calculations and supports concurrent use through internal locking.
Index ¶
- Variables
- type Dequeuer
- type Enqueuer
- type MockDequeuer
- type MockEnqueuer
- type MockQueuer
- type Queue
- func (q *Queue[T]) AddBack(item T) error
- func (q *Queue[T]) AddFront(item T) error
- func (q *Queue[T]) Cap() int
- func (q *Queue[T]) Clear()
- func (q *Queue[T]) Close()
- func (q *Queue[T]) Dequeue() (T, error)
- func (q *Queue[T]) Enqueue(item T) error
- func (q *Queue[T]) IsEmpty() bool
- func (q *Queue[T]) Len() int
- func (q *Queue[T]) PeekBack() (T, error)
- func (q *Queue[T]) PeekFront() (T, error)
- func (q *Queue[T]) Pop() (T, error)
- func (q *Queue[T]) Push(item T) error
- func (q *Queue[T]) RemoveBack() (T, error)
- func (q *Queue[T]) RemoveFront() (T, error)
- func (q *Queue[T]) Slice() []T
- func (q *Queue[T]) Stats() QueueStats
- type QueueStats
- type Queuer
Constants ¶
This section is empty.
Variables ¶
var ( // ErrEmptyQueue is returned when attempting to remove or peek from an empty queue. ErrEmptyQueue = errors.New("queue is empty") // ErrClosedQueue is returned when operating on a closed queue. ErrClosedQueue = errors.New("queue is closed") )
Functions ¶
This section is empty.
Types ¶
type Dequeuer ¶
type Dequeuer[T any] interface { // Dequeue removes and returns the item at the front. // Returns ErrEmptyQueue if empty, ErrClosedQueue if closed. Dequeue() (T, error) // Len returns the current number of items. Len() int // IsEmpty returns true if the queue has no items. IsEmpty() bool }
Dequeuer abstracts read operations on a queue. Used by consumers that only need to pull items.
type Enqueuer ¶
type Enqueuer[T any] interface { // Enqueue adds an item to the back of the queue. // Returns ErrClosedQueue if closed. Enqueue(item T) error // Len returns the current number of items. Len() int }
Enqueuer abstracts write operations on a queue. Used by producers that only need to push items.
type MockDequeuer ¶
type MockDequeuer[T any] struct { Items []T Err error Closed bool // contains filtered or unexported fields }
MockDequeuer is a mock implementation of Dequeuer for testing.
func (*MockDequeuer[T]) Dequeue ¶
func (m *MockDequeuer[T]) Dequeue() (T, error)
Dequeue removes and returns the next item from the mock queue.
func (*MockDequeuer[T]) IsEmpty ¶
func (m *MockDequeuer[T]) IsEmpty() bool
IsEmpty returns true if all items have been dequeued.
func (*MockDequeuer[T]) Len ¶
func (m *MockDequeuer[T]) Len() int
Len returns the number of remaining items.
type MockEnqueuer ¶
MockEnqueuer is a mock implementation of Enqueuer for testing.
func (*MockEnqueuer[T]) Enqueue ¶
func (m *MockEnqueuer[T]) Enqueue(item T) error
Enqueue adds an item to the mock queue.
func (*MockEnqueuer[T]) Len ¶
func (m *MockEnqueuer[T]) Len() int
Len returns the number of items in the queue.
type MockQueuer ¶
type MockQueuer[T any] struct { Items []T Err error Closed bool // contains filtered or unexported fields }
MockQueuer is a mock implementation of Queuer for testing.
func (*MockQueuer[T]) Dequeue ¶
func (m *MockQueuer[T]) Dequeue() (T, error)
Dequeue removes and returns the next item.
func (*MockQueuer[T]) Enqueue ¶
func (m *MockQueuer[T]) Enqueue(item T) error
Enqueue adds an item to the queue.
func (*MockQueuer[T]) IsEmpty ¶
func (m *MockQueuer[T]) IsEmpty() bool
IsEmpty returns true if the queue has no items.
func (*MockQueuer[T]) Len ¶
func (m *MockQueuer[T]) Len() int
Len returns the number of items in the queue.
type Queue ¶
type Queue[T any] struct { // contains filtered or unexported fields }
Queue is a generic, thread-safe, dynamically resizing double-ended queue (deque). Use NewQueue to create a queue. All methods are safe for concurrent use.
func NewQueue ¶
NewQueue creates a new queue with at least initialCap capacity. The actual capacity will be the next power of two greater than or equal to initialCap.
func (*Queue[T]) AddBack ¶
AddBack adds an item to the back of the queue. Returns ErrClosedQueue if the queue is closed.
func (*Queue[T]) AddFront ¶
AddFront adds an item to the front of the queue. Returns ErrClosedQueue if the queue is closed.
func (*Queue[T]) Clear ¶
func (q *Queue[T]) Clear()
Clear removes all items from the queue and resets its capacity.
func (*Queue[T]) Close ¶
func (q *Queue[T]) Close()
Close marks the queue as closed. Further operations will return ErrClosedQueue.
func (*Queue[T]) Dequeue ¶
Dequeue removes and returns the item at the front of the queue. Returns ErrEmptyQueue if the queue is empty, or ErrClosedQueue if closed.
func (*Queue[T]) Enqueue ¶
Enqueue adds an item to the back of the queue. Returns ErrClosedQueue if the queue is closed.
func (*Queue[T]) PeekBack ¶
PeekBack returns the item at the back of the queue without removing it. Returns ErrEmptyQueue if the queue is empty, or ErrClosedQueue if closed.
func (*Queue[T]) PeekFront ¶
PeekFront returns the item at the front of the queue without removing it. Returns ErrEmptyQueue if the queue is empty, or ErrClosedQueue if closed.
func (*Queue[T]) Pop ¶
Pop removes and returns the item at the back of the queue. Returns ErrEmptyQueue if the queue is empty, or ErrClosedQueue if closed.
func (*Queue[T]) Push ¶
Push adds an item to the back of the queue. Returns ErrClosedQueue if the queue is closed.
func (*Queue[T]) RemoveBack ¶
RemoveBack removes and returns the item at the back of the queue. Returns ErrEmptyQueue if the queue is empty, or ErrClosedQueue if closed.
func (*Queue[T]) RemoveFront ¶
RemoveFront removes and returns the item at the front of the queue. Returns ErrEmptyQueue if the queue is empty, or ErrClosedQueue if closed.
func (*Queue[T]) Slice ¶
func (q *Queue[T]) Slice() []T
Slice returns a copy of the queue's contents as a slice.
func (*Queue[T]) Stats ¶
func (q *Queue[T]) Stats() QueueStats
Stats returns statistics about the queue.
type QueueStats ¶
type QueueStats struct {
CtAddBack int // Total number of AddBack operations.
CtAddFront int // Total number of AddFront operations.
CtRemoveBack int // Total number of RemoveBack operations.
CtRemoveFront int // Total number of RemoveFront operations.
Size int // Current number of items in the queue.
Capacity int // Current capacity of the queue's internal buffer.
HeadIndex int // Current head index of the internal buffer.
TailIndex int // Current tail index of the internal buffer.
IsClosed bool // Whether the queue is closed.
}
QueueStats holds various statistics about the queue's current state.
Source Files