lru

package
v0.0.0-...-d3da680 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Dec 4, 2024 License: Apache-2.0 Imports: 5 Imported by: 26

Documentation

Overview

Package lru provides least-recently-used (LRU) cache.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Cache

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

Cache is a least-recently-used (LRU) cache implementation. The cache stores key-value mapping entries up to a size limit. If more items are added past that limit, the entries that have have been referenced least recently will be evicted.

A Cache must be constructed using the New method.

Cache is safe for concurrent access, using a read-write mutex to allow multiple non-mutating readers (Peek) or only one mutating reader/writer (Get, Put, Mutate).

func New

func New[K comparable, V any](maxSize int) *Cache[K, V]

New creates a new LRU with given maximum size.

If maxSize is <= 0, the LRU cache will have infinite capacity and will never prune LRU elements when adding new ones. Use Prune to reclaim memory occupied by expired elements.

func (*Cache[K, V]) Create

func (c *Cache[K, V]) Create(ctx context.Context, key K, fn Maker[V]) (v V, err error)

Create write-locks around key and invokes the supplied Maker to generate a new value.

If multiple concurrent operations invoke GetOrCreate or Create at the same time, they will serialize, and at most one Maker will be invoked at a time. If the Maker succeeds, it is more likely that the first operation will generate and install a value, and the other operations will all quickly retrieve that value once unblocked.

If the Maker returns an error, the error will be returned by Create and no modifications will be made to the Cache. If Maker returns a nil error, the value that it returns will be added into the Cache and returned to the caller.

Note that the Cache's lock will not be held while the Maker is running. Operations on to the Cache using other methods will not lock around key. This will not interfere with Create.

func (*Cache[K, V]) Get

func (c *Cache[K, V]) Get(ctx context.Context, key K) (V, bool)

Get fetches the element associated with the supplied key, updating its recently-used standing.

Get uses the cache read/write lock.

func (*Cache[K, V]) GetOrCreate

func (c *Cache[K, V]) GetOrCreate(ctx context.Context, key K, fn Maker[V]) (v V, err error)

GetOrCreate retrieves the current value of key. If no value exists for key, GetOrCreate will lock around key and invoke the supplied Maker to generate a new value.

If multiple concurrent operations invoke GetOrCreate at the same time, they will serialize, and at most one Maker will be invoked at a time. If the Maker succeeds, it is more likely that the first operation will generate and install a value, and the other operations will all quickly retrieve that value once unblocked.

If the Maker returns an error, the error will be returned by GetOrCreate and no modifications will be made to the Cache. If Maker returns a nil error, the value that it returns will be added into the Cache and returned to the caller.

Note that the Cache's lock will not be held while the Maker is running. Operations on to the Cache using other methods will not lock around key. This will not interfere with GetOrCreate.

func (*Cache[K, V]) Len

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

Len returns the number of entries in the cache.

Len uses the cache read lock.

func (*Cache[K, V]) Mutate

func (c *Cache[K, V]) Mutate(ctx context.Context, key K, gen Generator[V]) (value V, ok bool)

Mutate adds a value to the cache, using a Generator to create the value.

Mutate uses the cache read/write lock.

The Generator will receive the current value, or nil if there is no current value. It returns the new value, or nil to remove this key from the cache.

The Generator is called while the cache's lock is held. This means that the Generator MUST NOT call any cache methods during its execution, as doing so will result in deadlock/panic.

Returns the value that was put in the cache, which is the value returned by the Generator. "ok" will be true if the value is in the cache and valid.

The key will be considered most recently used regardless of whether it was put.

func (*Cache[K, V]) Peek

func (c *Cache[K, V]) Peek(ctx context.Context, key K) (V, bool)

Peek fetches the element associated with the supplied key without updating the element's recently-used standing.

Peek uses the cache read lock.

func (*Cache[K, V]) Prune

func (c *Cache[K, V]) Prune(ctx context.Context)

Prune iterates through entries in the Cache and prunes any which are expired.

func (*Cache[K, V]) Put

func (c *Cache[K, V]) Put(ctx context.Context, key K, value V, exp time.Duration) (prev V, had bool)

Put adds a new value to the cache. The value in the cache will be replaced regardless of whether an item with the same key already existed.

If the supplied expiration is <=0, the item will not have a time-based expiration associated with it, although it still may be pruned if it is not used.

Put uses the cache read/write lock.

Returns whether not a value already existed for the key.

The new item will be considered most recently used.

func (*Cache[K, V]) Remove

func (c *Cache[K, V]) Remove(key K) (val V, has bool)

Remove removes an entry from the cache. If the key is present, its current value will be returned; otherwise, nil will be returned.

Remove uses the cache read/write lock.

func (*Cache[K, V]) Reset

func (c *Cache[K, V]) Reset()

Reset clears the full contents of the cache.

Purge uses the cache read/write lock.

type Generator

type Generator[V any] func(it *Item[V]) *Item[V]

Generator generates a new value, given the current value and its remaining expiration time.

The returned value will be stored in the cache after the Generator exits, even if it is nil.

The Generator is executed while the Cache's lock is held.

If the returned Item is nil, no item will be retained, and the current value (if any) will be purged. If the returned Item's expiration is <=0, the returned Item will never expire. Otherwise, the Item will expire in the future.

type Item

type Item[V any] struct {
	// Value is the item's value. It may be nil.
	Value V
	// Exp is the item's expiration.
	Exp time.Duration
}

Item is a Cache item. It's used when interfacing with Mutate.

type Maker

type Maker[V any] func() (v V, exp time.Duration, err error)

Maker generates a new value. It is used by GetOrCreate, and is run while a lock on that value's key is held, but not while the larger Cache is locked, so it is safe for this to take some time.

The returned value, v, will be stored in the cache after Maker exits.

If the Maker returns an error, the returned value will not be cached, and the error will be returned by GetOrCreate.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL