queue

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[T any] interface {
	Enqueue(v T)
	Dequeue() T
}

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-8         	 4835329	       266.2 ns/op	      16 B/op	       1 allocs/op
BenchmarkQueue/two-lock_queue#4-8          	 9112242	       168.0 ns/op	      16 B/op	       1 allocs/op
BenchmarkQueue/slice-based_queue#4-8       	 8778811	       182.0 ns/op	      40 B/op	       0 allocs/op

BenchmarkQueue/two-lock_queue#32-8         	 9109314	       133.1 ns/op	      16 B/op	       1 allocs/op
BenchmarkQueue/slice-based_queue#32-8      	 7939176	       171.8 ns/op	      54 B/op	       0 allocs/op
BenchmarkQueue/lock-free_queue#32-8        	 4735264	       253.8 ns/op	      16 B/op	       1 allocs/op

BenchmarkQueue/lock-free_queue#1024-8      	 4654297	       242.6 ns/op	      16 B/op	       1 allocs/op
BenchmarkQueue/two-lock_queue#1024-8       	 7714422	       138.2 ns/op	      16 B/op	       1 allocs/op
BenchmarkQueue/slice-based_queue#1024-8    	 8609463	       169.7 ns/op	      34 B/op	       0 allocs/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

• type BoundedQueue
  • func NewBoundedQueue[T any](n uint32) *BoundedQueue[T]
  • func (q *BoundedQueue[T]) Dequeue() T
  • func (q *BoundedQueue[T]) Enqueue(v T)
  • func (q *BoundedQueue[T]) Len() int
• type CQueue
  • func NewCQueue[T any]() *CQueue[T]
  • func (q *CQueue[T]) Dequeue() T
  • func (q *CQueue[T]) Enqueue(v T)
• type LKQueue
  • func NewLKQueue[T any]() *LKQueue[T]
  • func (q *LKQueue[T]) Dequeue() T
  • func (q *LKQueue[T]) Enqueue(v T)
• type Queue
• type SliceQueue
  • func NewSliceQueue[T any](n int) (q *SliceQueue[T])
  • func (q *SliceQueue[T]) Dequeue() T
  • func (q *SliceQueue[T]) Enqueue(v T)

Types

type BoundedQueue

type BoundedQueue[T any] struct {
	// contains filtered or unexported fields
}

BoundedQueue is a threadsafe bounded queue.

func NewBoundedQueue

func NewBoundedQueue[T any](n uint32) *BoundedQueue[T]

NewBoundedQueue create a BoundedQueue.

func (*BoundedQueue[T]) Dequeue

func (q *BoundedQueue[T]) Dequeue() T

Dequeue removes and returns the value at the head of the queue. It will be blocked if the queue is empty.

func (*BoundedQueue[T]) Enqueue

func (q *BoundedQueue[T]) Enqueue(v T)

Enqueue puts the given value v at the tail of the queue. If this queue if full, the caller will be blocked.

func (*BoundedQueue[T]) Len

func (q *BoundedQueue[T]) Len() int

Len returns length of this queue.

type CQueue

type CQueue[T any] struct {
	// contains filtered or unexported fields
}

CQueue is a concurrent unbounded queue which uses two-Lock concurrent queue qlgorithm.

func NewCQueue

func NewCQueue[T any]() *CQueue[T]

NewCQueue returns an empty CQueue.

func (*CQueue[T]) Dequeue

func (q *CQueue[T]) Dequeue() T

Dequeue removes and returns the value at the head of the queue. It returns nil if the queue is empty.

func (*CQueue[T]) Enqueue

func (q *CQueue[T]) Enqueue(v T)

Enqueue puts the given value v at the tail of the queue.

type LKQueue

type LKQueue[T any] struct {
	// contains filtered or unexported fields
}

LKQueue is a lock-free unbounded queue.

func NewLKQueue

func NewLKQueue[T any]() *LKQueue[T]

NewLKQueue returns an empty queue.

func (*LKQueue[T]) Dequeue

func (q *LKQueue[T]) Dequeue() T

Dequeue removes and returns the value at the head of the queue. It returns the zero value if the queue is empty.

func (*LKQueue[T]) Enqueue

func (q *LKQueue[T]) Enqueue(v T)

Enqueue puts the given value v at the tail of the queue.

type Queue

type Queue[T any] interface {
	Enqueue(v T)
	Dequeue() T
}

Queue is a FIFO data structure. Enqueue puts a value into its tail, Dequeue removes a value from its head.

type SliceQueue

type SliceQueue[T any] struct {
	// contains filtered or unexported fields
}

SliceQueue is an unbounded queue which uses a slice as underlying.

func NewSliceQueue

func NewSliceQueue[T any](n int) (q *SliceQueue[T])

NewSliceQueue returns an empty queue.

func (*SliceQueue[T]) Dequeue

func (q *SliceQueue[T]) Dequeue() T

Dequeue removes and returns the value at the head of the queue. It returns nil if the queue is empty.

func (*SliceQueue[T]) Enqueue

func (q *SliceQueue[T]) Enqueue(v T)

Enqueue puts the given value v at the tail of the queue.