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.

Package singleflight provides a duplicate function call suppression mechanism.

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 Group
  • func (g *Group[K, V]) Do(key K, fn func() (V, error)) (v V, err error, shared bool)
  • func (g *Group[K, V]) DoChan(key K, fn func() (V, error)) <-chan Result
  • func (g *Group[K, V]) Forget(key K)
• 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 Loaded
• type LoadingStore
  • func NewLoadingStore[K comparable, V any](store *Store[K, V]) *LoadingStore[K, V]
  • func (s *LoadingStore[K, V]) Get(ctx context.Context, key K) (V, error)
  • func (s *LoadingStore[K, V]) Loader(loader func(ctx context.Context, key K) (Loaded[V], error))
• type MetaData
• type Metrics
• 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 RemoveReason
• type Result
• 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]) Cost(cost func(v V) int64)
  • func (s *Store[K, V]) Delete(key K)
  • func (s *Store[K, V]) Doorkeeper(enabled bool)
  • func (s *Store[K, V]) Get(key K) (V, bool)
  • func (s *Store[K, V]) Len() int
  • func (s *Store[K, V]) RemovalListener(listener func(key K, value V, reason RemoveReason))
  • func (s *Store[K, V]) Set(key K, value V, cost int64, ttl time.Duration) bool
• 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
)

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 Group

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

Group represents a class of work and forms a namespace in which units of work can be executed with duplicate suppression.

func (*Group[K, V]) Do

func (g *Group[K, V]) Do(key K, fn func() (V, error)) (v V, err error, shared bool)

Do executes and returns the results of the given function, making sure that only one execution is in-flight for a given key at a time. If a duplicate comes in, the duplicate caller waits for the original to complete and receives the same results. The return value shared indicates whether v was given to multiple callers.

func (*Group[K, V]) DoChan

func (g *Group[K, V]) DoChan(key K, fn func() (V, error)) <-chan Result

The returned channel will not be closed.

func (*Group[K, V]) Forget

func (g *Group[K, V]) Forget(key K)

Forget tells the singleflight to forget about a key. Future calls to Do for this key will call the function rather than waiting for an earlier call to complete.

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 Loaded

type Loaded[V any] struct {
	Value V
	Cost  int64
	TTL   time.Duration
}

type LoadingStore

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

func NewLoadingStore

func NewLoadingStore[K comparable, V any](store *Store[K, V]) *LoadingStore[K, V]

func (*LoadingStore[K, V]) Get

func (s *LoadingStore[K, V]) Get(ctx context.Context, key K) (V, error)

func (*LoadingStore[K, V]) Loader

func (s *LoadingStore[K, V]) Loader(loader func(ctx context.Context, key K) (Loaded[V], error))

type MetaData

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

type Metrics

type Metrics struct {
}

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 RemoveReason

type RemoveReason uint8

const (
	REMOVED RemoveReason = iota
	EVICTED
	EXPIRED
)

type Result

type Result struct {
	Val    interface{}
	Err    error
	Shared bool
}

Result holds the results of Do, so they can be passed on a channel.

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]) Cost

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

func (*Store[K, V]) Delete

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

func (*Store[K, V]) Doorkeeper

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

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]) RemovalListener

func (s *Store[K, V]) RemovalListener(listener func(key K, value V, reason RemoveReason))

func (*Store[K, V]) Set

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

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
}