internal

Documentation

Overview

Package mpsc provides an efficient implementation of a multi-producer, single-consumer lock-free queue.

The Push function is safe to call from multiple goroutines. The Pop and Empty APIs must only be called from a single, consumer goroutine.

Index

• Constants
• type Clock
• type CountMinSketch
  • func NewCountMinSketch(size uint) *CountMinSketch
  • func (s *CountMinSketch) Add(h uint64) bool
  • func (s *CountMinSketch) Estimate(h uint64) uint
• type Entry
  • func NewEntry[K comparable, V any](key K, value V, cost int64, expire int64) *Entry[K, V]
  • func (e *Entry[K, V]) Next(listType uint8) *Entry[K, V]
  • func (e *Entry[K, V]) Prev(listType uint8) *Entry[K, V]
• type Hasher
  • func NewHasher[K comparable]() *Hasher[K]
• type List
  • func NewList[K comparable, V any](size uint, listType uint8) *List[K, V]
  • func (l *List[K, V]) Back() *Entry[K, V]
  • func (l *List[K, V]) Contains(entry *Entry[K, V]) bool
  • func (l *List[K, V]) Front() *Entry[K, V]
  • func (l *List[K, V]) Len() int
  • func (l *List[K, V]) MoveAfter(e, mark *Entry[K, V])
  • func (l *List[K, V]) MoveBefore(e, mark *Entry[K, V])
  • func (l *List[K, V]) MoveToBack(e *Entry[K, V])
  • func (l *List[K, V]) MoveToFront(e *Entry[K, V])
  • func (l *List[K, V]) PopTail() *Entry[K, V]
  • func (l *List[K, V]) PushFront(e *Entry[K, V]) *Entry[K, V]
  • func (l *List[K, V]) Remove(e *Entry[K, V])
  • func (l *List[K, V]) Reset()
• type MetaData
• type OPCODE
• type Queue
  • func NewQueue[V any]() *Queue[V]
  • func (q *Queue[V]) Empty() bool
  • func (q *Queue[V]) Pop() (V, bool)
  • func (q *Queue[V]) Push(x V)
• type ReadBufItem
• type Shard
  • func NewShard[K comparable, V any](size uint, qsize uint) *Shard[K, V]
• type Slru
  • func NewSlru[K comparable, V any](size uint) *Slru[K, V]
• type Store
  • func NewStore[K comparable, V any](maxsize int64) *Store[K, V]
  • func (s *Store[K, V]) Close()
  • func (s *Store[K, V]) Delete(key K)
  • func (s *Store[K, V]) Get(key K) (V, bool)
  • func (s *Store[K, V]) Len() int
  • func (s *Store[K, V]) Set(key K, value V, cost int64, ttl time.Duration) bool
  • func (s *Store[K, V]) SetCost(cost func(v V) int64)
  • func (s *Store[K, V]) SetDoorkeeper(enabled bool)
  • func (s *Store[K, V]) WriteBufLen() int
• type TimerWheel
  • func NewTimerWheel[K comparable, V any](size uint) *TimerWheel[K, V]
• type TinyLfu
  • func NewTinyLfu[K comparable, V any](size uint, hasher *Hasher[K]) *TinyLfu[K, V]
  • func (t *TinyLfu[K, V]) Access(item ReadBufItem[K, V])
  • func (t *TinyLfu[K, V]) EvictEntries() []*Entry[K, V]
  • func (t *TinyLfu[K, V]) Remove(entry *Entry[K, V])
  • func (t *TinyLfu[K, V]) Set(entry *Entry[K, V]) *Entry[K, V]
  • func (t *TinyLfu[K, V]) UpdateCost(entry *Entry[K, V], delta int64)
  • func (t *TinyLfu[K, V]) UpdateThreshold()
• type WriteBufItem

Constants

const (
	NEW int8 = iota
	REMOVE
	UPDATE
)

const (
	LIST_PROBATION uint8 = 1
	LIST_PROTECTED uint8 = 2
	WHEEL_LIST     uint8 = 3
)

const (
	MAX_READ_BUFF_SIZE  = 64
	MIN_WRITE_BUFF_SIZE = 4
	MAX_WRITE_BUFF_SIZE = 1024
	MAINTANCE           = 1
)

Types

type Clock

type Clock struct {
	// contains filtered or unexported fields
}

type CountMinSketch

type CountMinSketch struct {
	// contains filtered or unexported fields
}

func NewCountMinSketch

func NewCountMinSketch(size uint) *CountMinSketch

func (*CountMinSketch) Add

func (s *CountMinSketch) Add(h uint64) bool

func (*CountMinSketch) Estimate

func (s *CountMinSketch) Estimate(h uint64) uint

type Entry

type Entry[K comparable, V any] struct {
	// contains filtered or unexported fields
}

func NewEntry

func NewEntry[K comparable, V any](key K, value V, cost int64, expire int64) *Entry[K, V]

func (*Entry[K, V]) Next

func (e *Entry[K, V]) Next(listType uint8) *Entry[K, V]

func (*Entry[K, V]) Prev

func (e *Entry[K, V]) Prev(listType uint8) *Entry[K, V]

type Hasher

type Hasher[K comparable] struct {
	// contains filtered or unexported fields
}

func NewHasher

func NewHasher[K comparable]() *Hasher[K]

type List

type List[K comparable, V any] struct {
	// contains filtered or unexported fields
}

List represents a doubly linked list. The zero value for List is an empty list ready to use.

func NewList

func NewList[K comparable, V any](size uint, listType uint8) *List[K, V]

New returns an initialized list.

func (*List[K, V]) Back

func (l *List[K, V]) Back() *Entry[K, V]

Back returns the last element of list l or nil if the list is empty.

func (*List[K, V]) Contains

func (l *List[K, V]) Contains(entry *Entry[K, V]) bool

func (*List[K, V]) Front

func (l *List[K, V]) Front() *Entry[K, V]

Front returns the first element of list l or nil if the list is empty.

func (*List[K, V]) Len

func (l *List[K, V]) Len() int

Len returns the number of elements of list l. The complexity is O(1).

func (*List[K, V]) MoveAfter

func (l *List[K, V]) MoveAfter(e, mark *Entry[K, V])

MoveAfter moves element e to its new position after mark. If e or mark is not an element of l, or e == mark, the list is not modified. The element and mark must not be nil.

func (*List[K, V]) MoveBefore

func (l *List[K, V]) MoveBefore(e, mark *Entry[K, V])

MoveBefore moves element e to its new position before mark. If e or mark is not an element of l, or e == mark, the list is not modified. The element and mark must not be nil.

func (*List[K, V]) MoveToBack

func (l *List[K, V]) MoveToBack(e *Entry[K, V])

MoveToBack moves element e to the back of list l. If e is not an element of l, the list is not modified. The element must not be nil.

func (*List[K, V]) MoveToFront

func (l *List[K, V]) MoveToFront(e *Entry[K, V])

MoveToFront moves element e to the front of list l. If e is not an element of l, the list is not modified. The element must not be nil.

func (*List[K, V]) PopTail

func (l *List[K, V]) PopTail() *Entry[K, V]

func (*List[K, V]) PushFront

func (l *List[K, V]) PushFront(e *Entry[K, V]) *Entry[K, V]

PushFront push entry to list head

func (*List[K, V]) Remove

func (l *List[K, V]) Remove(e *Entry[K, V])

Remove removes e from l if e is an element of list l. It returns the element value e.Value. The element must not be nil.

func (*List[K, V]) Reset

func (l *List[K, V]) Reset()

type MetaData

type MetaData[K comparable, V any] struct {
	// contains filtered or unexported fields
}

type OPCODE

type OPCODE int8

type Queue

type Queue[V any] struct {
	// contains filtered or unexported fields
}

func NewQueue

func NewQueue[V any]() *Queue[V]

func (*Queue[V]) Empty

func (q *Queue[V]) Empty() bool

Empty returns true if the queue is empty

Empty must be called from a single, consumer goroutine

func (*Queue[V]) Pop

func (q *Queue[V]) Pop() (V, bool)

Pop removes the item from the front of the queue or nil if the queue is empty

Pop must be called from a single, consumer goroutine

func (*Queue[V]) Push

func (q *Queue[V]) Push(x V)

Push adds x to the back of the queue.

Push can be safely called from multiple goroutines

type ReadBufItem

type ReadBufItem[K comparable, V any] struct {
	// contains filtered or unexported fields
}

type Shard

type Shard[K comparable, V any] struct {
	// contains filtered or unexported fields
}

func NewShard

func NewShard[K comparable, V any](size uint, qsize uint) *Shard[K, V]

type Slru

type Slru[K comparable, V any] struct {
	// contains filtered or unexported fields
}

func NewSlru

func NewSlru[K comparable, V any](size uint) *Slru[K, V]

type Store

type Store[K comparable, V any] struct {
	// contains filtered or unexported fields
}

func NewStore

func NewStore[K comparable, V any](maxsize int64) *Store[K, V]

New returns a new data struct with the specified capacity

func (*Store[K, V]) Close

func (s *Store[K, V]) Close()

func (*Store[K, V]) Delete

func (s *Store[K, V]) Delete(key K)

func (*Store[K, V]) Get

func (s *Store[K, V]) Get(key K) (V, bool)

func (*Store[K, V]) Len

func (s *Store[K, V]) Len() int

func (*Store[K, V]) Set

func (s *Store[K, V]) Set(key K, value V, cost int64, ttl time.Duration) bool

func (*Store[K, V]) SetCost

func (s *Store[K, V]) SetCost(cost func(v V) int64)

func (*Store[K, V]) SetDoorkeeper

func (s *Store[K, V]) SetDoorkeeper(enabled bool)

func (*Store[K, V]) WriteBufLen

func (s *Store[K, V]) WriteBufLen() int

type TimerWheel

type TimerWheel[K comparable, V any] struct {
	// contains filtered or unexported fields
}

func NewTimerWheel

func NewTimerWheel[K comparable, V any](size uint) *TimerWheel[K, V]

type TinyLfu

type TinyLfu[K comparable, V any] struct {
	// contains filtered or unexported fields
}

func NewTinyLfu

func NewTinyLfu[K comparable, V any](size uint, hasher *Hasher[K]) *TinyLfu[K, V]

func (*TinyLfu[K, V]) Access

func (t *TinyLfu[K, V]) Access(item ReadBufItem[K, V])

func (*TinyLfu[K, V]) EvictEntries

func (t *TinyLfu[K, V]) EvictEntries() []*Entry[K, V]

func (*TinyLfu[K, V]) Remove

func (t *TinyLfu[K, V]) Remove(entry *Entry[K, V])

func (*TinyLfu[K, V]) Set

func (t *TinyLfu[K, V]) Set(entry *Entry[K, V]) *Entry[K, V]

func (*TinyLfu[K, V]) UpdateCost

func (t *TinyLfu[K, V]) UpdateCost(entry *Entry[K, V], delta int64)

func (*TinyLfu[K, V]) UpdateThreshold

func (t *TinyLfu[K, V]) UpdateThreshold()

type WriteBufItem

type WriteBufItem[K comparable, V any] struct {
	// contains filtered or unexported fields
}