lru

Documentation

Overview

Package list implements a doubly linked list.

To iterate over a list (where l is a *List):

for e := l.Front(); e != nil; e = e.Next() {
	// do something with e.Value
}

Index

• type Cache
  • func NewCache[K comparable, V cache.Value](capacity uint64) *Cache[K, V]
  • func (c *Cache[K, V]) Delete(key K)
  • func (c *Cache[K, V]) Get(key K) (V, error)
  • func (c *Cache[K, V]) Len() int
  • func (c *Cache[K, V]) LoadAndDelete(key K) (V, bool)
  • func (c *Cache[K, V]) Put(key K, value V) (bool, error)
  • func (c *Cache[K, V]) Range(visitor func(K, V) bool)
  • func (c *Cache[K, V]) RangeFIFO(visitor func(K, V) bool)
  • func (c *Cache[K, V]) RangeFILO(visitor func(K, V) bool)
• type Element
  • func (e *Element[V]) Next() *Element[V]
  • func (e *Element[V]) Prev() *Element[V]
• type List
  • func NewList[V any]() *List[V]
  • func (l *List[V]) Back() *Element[V]
  • func (l *List[V]) Front() *Element[V]
  • func (l *List[V]) Init() *List[V]
  • func (l *List[V]) InsertAfter(v V, mark *Element[V]) *Element[V]
  • func (l *List[V]) InsertBefore(v V, mark *Element[V]) *Element[V]
  • func (l *List[V]) Len() int
  • func (l *List[V]) MoveAfter(e, mark *Element[V])
  • func (l *List[V]) MoveBefore(e, mark *Element[V])
  • func (l *List[V]) MoveToBack(e *Element[V])
  • func (l *List[V]) MoveToFront(e *Element[V])
  • func (l *List[V]) PushBack(v V) *Element[V]
  • func (l *List[V]) PushBackList(other *List[V])
  • func (l *List[V]) PushFront(v V) *Element[V]
  • func (l *List[V]) PushFrontList(other *List[V])
  • func (l *List[V]) Remove(e *Element[V]) any

Types

type Cache

type Cache[K comparable, V cache.Value] struct {
	// contains filtered or unexported fields
}

Cache provides a generic thread-safe lru cache that can be used for storing filters, blocks, etc.

func NewCache

func NewCache[K comparable, V cache.Value](capacity uint64) *Cache[K, V]

NewCache return a cache with specified capacity, the cache's size can't exceed that given capacity.

func (*Cache[K, V]) Delete

func (c *Cache[K, V]) Delete(key K)

Delete removes an item from the cache.

func (*Cache[K, V]) Get

func (c *Cache[K, V]) Get(key K) (V, error)

Get will return value for a given key, making the element the most recently accessed item in the process. Will return nil if the key isn't found.

func (*Cache[K, V]) Len

func (c *Cache[K, V]) Len() int

Len returns number of elements in the cache.

func (*Cache[K, V]) LoadAndDelete

func (c *Cache[K, V]) LoadAndDelete(key K) (V, bool)

LoadAndDelete queries an item and deletes it from the cache using the specified key.

func (*Cache[K, V]) Put

func (c *Cache[K, V]) Put(key K, value V) (bool, error)

Put inserts a given (key,value) pair into the cache, if the key already exists, it will replace value and update it to be most recent item in cache. The return value indicates whether items had to be evicted to make room for the new element.

func (*Cache[K, V]) Range

func (c *Cache[K, V]) Range(visitor func(K, V) bool)

Range iterates the cache without any ordering.

func (*Cache[K, V]) RangeFIFO

func (c *Cache[K, V]) RangeFIFO(visitor func(K, V) bool)

RangeFIFO iterates the items with FIFO order, behaving like a queue.

func (*Cache[K, V]) RangeFILO

func (c *Cache[K, V]) RangeFILO(visitor func(K, V) bool)

RangeFILO iterates the items with FILO order, behaving like a stack.

type Element

type Element[V any] struct {

	// The value stored with this element.
	Value V
	// contains filtered or unexported fields
}

Element is an element of a linked list.

func (*Element[V]) Next

func (e *Element[V]) Next() *Element[V]

Next returns the next list element or nil.

func (*Element[V]) Prev

func (e *Element[V]) Prev() *Element[V]

Prev returns the previous list element or nil.

type List

type List[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[V any]() *List[V]

NewList returns an initialized list.

func (*List[V]) Back

func (l *List[V]) Back() *Element[V]

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

func (*List[V]) Front

func (l *List[V]) Front() *Element[V]

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

func (*List[V]) Init

func (l *List[V]) Init() *List[V]

Init initializes or clears list l.

func (*List[V]) InsertAfter

func (l *List[V]) InsertAfter(v V, mark *Element[V]) *Element[V]

InsertAfter inserts a new element e with value v immediately after mark and returns e. If mark is not an element of l, the list is not modified. The mark must not be nil.

func (*List[V]) InsertBefore

func (l *List[V]) InsertBefore(v V, mark *Element[V]) *Element[V]

InsertBefore inserts a new element e with value v immediately before mark and returns e. If mark is not an element of l, the list is not modified. The mark must not be nil.

func (*List[V]) Len

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

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

func (*List[V]) MoveAfter

func (l *List[V]) MoveAfter(e, mark *Element[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[V]) MoveBefore

func (l *List[V]) MoveBefore(e, mark *Element[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[V]) MoveToBack

func (l *List[V]) MoveToBack(e *Element[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[V]) MoveToFront

func (l *List[V]) MoveToFront(e *Element[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[V]) PushBack

func (l *List[V]) PushBack(v V) *Element[V]

PushBack inserts a new element e with value v at the back of list l and returns e.

func (*List[V]) PushBackList

func (l *List[V]) PushBackList(other *List[V])

PushBackList inserts a copy of another list at the back of list l. The lists l and other may be the same. They must not be nil.

func (*List[V]) PushFront

func (l *List[V]) PushFront(v V) *Element[V]

PushFront inserts a new element e with value v at the front of list l and returns e.

func (*List[V]) PushFrontList

func (l *List[V]) PushFrontList(other *List[V])

PushFrontList inserts a copy of another list at the front of list l. The lists l and other may be the same. They must not be nil.

func (*List[V]) Remove

func (l *List[V]) Remove(e *Element[V]) any

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.