README
¶
queue
import "github.com/smallnest/queue"
Package queue provides multiple queue implementations. The lock-free and two-lock algorithms are from Michael and Scott. https://doi.org/10.1145/248052.248106
Queue
A queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence.The operations of a queue make it a first-in-first-out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed.
Package queue defines Queue interface:
type Queue interface {
Enqueue(v interface{})
Dequeue() interface{}
}
Currently it contains three implementations:
- lock-free queue:
LKQueue - two-lock queue:
CQueue - slice-based queue:
SliceQueue
Benchmark
goos: darwin
goarch: amd64
pkg: github.com/smallnest/queue
BenchmarkQueue/lock-free_queue#4-4 8399941 177 ns/op
BenchmarkQueue/two-lock_queue#4-4 7544263 155 ns/op
BenchmarkQueue/slice-based_queue#4-4 6436875 194 ns/op
BenchmarkQueue/lock-free_queue#32-4 8399769 140 ns/op
BenchmarkQueue/two-lock_queue#32-4 7486357 155 ns/op
BenchmarkQueue/slice-based_queue#32-4 4572828 235 ns/op
BenchmarkQueue/lock-free_queue#1024-4 8418556 140 ns/op
BenchmarkQueue/two-lock_queue#1024-4 7888488 155 ns/op
BenchmarkQueue/slice-based_queue#1024-4 8902573 218 ns/op
Documentation
¶
Overview ¶
Package queue provides a lock-free queue and two-Lock concurrent queue which use the algorithm proposed by Michael and Scott. https://doi.org/10.1145/248052.248106.
see pseudocode at https://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html It will be refactored after go generic is released.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BoundedQueue ¶
type BoundedQueue struct {
// contains filtered or unexported fields
}
BoundedQueue is a threadsafe bounded queue.
func NewBoundedQueue ¶
func NewBoundedQueue(n uint32) *BoundedQueue
NewBoundedQueue create a BoundedQueue.
func (*BoundedQueue) Dequeue ¶
func (q *BoundedQueue) Dequeue() interface{}
Dequeue removes and returns the value at the head of the queue. It will be blocked if the queue is empty.
func (*BoundedQueue) Enqueue ¶
func (q *BoundedQueue) Enqueue(v interface{})
Enqueue puts the given value v at the tail of the queue. If this queue if full, the caller will be blocked.
type CQueue ¶
type CQueue struct {
// contains filtered or unexported fields
}
CQueue is a concurrent unbounded queue which uses two-Lock concurrent queue qlgorithm.
type LKQueue ¶
type LKQueue struct {
// contains filtered or unexported fields
}
LKQueue is a lock-free unbounded queue.
func (*LKQueue) Dequeue ¶
func (q *LKQueue) Dequeue() interface{}
Dequeue removes and returns the value at the head of the queue. It returns nil if the queue is empty.
type Queue ¶
type Queue interface {
Enqueue(v interface{})
Dequeue() interface{}
}
Queue is a FIFO data structure. Enqueue puts a value into its tail, Dequeue removes a value from its head.
type SliceQueue ¶
type SliceQueue struct {
// contains filtered or unexported fields
}
SliceQueue is an unbounded queue which uses a slice as underlying.
func NewSliceQueue ¶
func NewSliceQueue(n int) (q *SliceQueue)
NewSliceQueue returns an empty queue.
func (*SliceQueue) Dequeue ¶
func (q *SliceQueue) Dequeue() interface{}
Dequeue removes and returns the value at the head of the queue. It returns nil if the queue is empty.
func (*SliceQueue) Enqueue ¶
func (q *SliceQueue) Enqueue(v interface{})
Enqueue puts the given value v at the tail of the queue.
Source Files
Directories