lru

README

LRU Cache

An implementation of a LRU cache. The cache supports Push, Put, Get Peek and Remove operations, all of which are O(1). This package was heavily influenced by the LRU Cache implementation in a Rust crate.

Example

Below is a simple example of how to instantiate and use a LRU cache.

package main

import (
	"fmt"

	"github.com/lovelysunlight/lru-go"
)

func main() {
	cache, _ := lru.New[string, string](2)
	cache.Put("apple", "red")
	cache.Put("banana", "yellow")

	var (
		r, v string
		ok   bool
	)

	r, ok = cache.Get("apple")
	fmt.Printf("Get() found: %v, value: %q\n", ok, r)

	r, ok = cache.Get("banana")
	fmt.Printf("Get() found: %v, value: %q\n", ok, r)

	r, ok = cache.Get("pear")
	fmt.Printf("Get() found: %v, value: %q\n", ok, r)

	r, ok = cache.Peek("apple")
	fmt.Printf("Peek() found: %v, value: %q\n", ok, r)

	r, ok = cache.Peek("banana")
	fmt.Printf("Peek() found: %v, value: %q\n", ok, r)

	r, ok = cache.Peek("pear")
	fmt.Printf("Peek() found: %v, value: %q\n", ok, r)

	r, ok = cache.Remove("banana")
	fmt.Printf("Remove() found: %v, value: %q\n", ok, r)

	r, v, ok = cache.RemoveOldest()
	fmt.Printf("RemoveOldest() found: %v, key: %q, value: %q\n", ok, r, v)

	fmt.Printf("Len() = : %v\n", cache.Len())
	fmt.Printf("Cap() = : %v\n", cache.Cap())
}

Documentation

See the API documentation on go.dev

Thanks

• jeromefroe/lru-rs
• hashicorp/golang-lru

Documentation

Index

• func DisableDeepCopy[K comparable, V any]() cacheOptionFunc[K, V]
• func Enable2Q[K comparable, V any](size int) cacheOptionFunc[K, V]
• func EnableDeepCopy[K comparable, V any]() cacheOptionFunc[K, V]
• func EnableLRUK[K comparable, V any](threshold uint64) cacheOptionFunc[K, V]
• func WithVisitCacheSize[K comparable, V any](size int) cacheOptionFunc[K, V]
• type Cache
  • func New[K comparable, V any](size int, opts ...cacheOptionFunc[K, V]) (c *Cache[K, V], err error)
  • func (c *Cache[K, V]) Cap() int
  • func (c *Cache[K, V]) Clear()
  • func (c *Cache[K, V]) Contains(key K) (ok bool)
  • func (c *Cache[K, V]) FIFOCap() int
  • func (c *Cache[K, V]) FIFOLen() int
  • func (c *Cache[K, V]) FIFOResize(size int) int
  • func (c *Cache[K, V]) Get(key K) (value V, ok bool)
  • func (c *Cache[K, V]) IsEnable2Q() bool
  • func (c *Cache[K, V]) IsEnableLRUK() bool
  • func (c *Cache[K, V]) Keys() []K
  • func (c *Cache[K, V]) Len() int
  • func (c *Cache) OptionalCopyKey(data K) K
  • func (c *Cache) OptionalCopyKeyN(data []K) []K
  • func (c *Cache) OptionalCopyValue(data V) V
  • func (c *Cache) OptionalCopyValueN(data []V) []V
  • func (c *Cache[K, V]) Peek(key K) (value V, ok bool)
  • func (c *Cache[K, V]) PeekOldest() (key K, value V, ok bool)
  • func (c *Cache[K, V]) Push(key K, value V) (oldKey K, oldValue V, ok bool)
  • func (c *Cache[K, V]) Put(key K, value V) (oldValue V, ok bool)
  • func (c *Cache[K, V]) Remove(key K) (value V, ok bool)
  • func (c *Cache[K, V]) RemoveOldest() (key K, value V, ok bool)
  • func (c *Cache[K, V]) Resize(size int) (evicted int)
  • func (c *Cache[K, V]) Values() []V
  • func (c *Cache[K, V]) VisitsCap() int
  • func (c *Cache[K, V]) VisitsLen() int
  • func (c *Cache[K, V]) VisitsResize(size int) int

Functions

func DisableDeepCopy

func DisableDeepCopy[K comparable, V any]() cacheOptionFunc[K, V]

Disable to return a deep copy of the value in `Get`, `Peek`, `PeekOldest`, `Keys` and `Values`.

cache, _ := lru.New[string, string](3, lru.DisableDeepCopy())
cache.Put("foo", []int{1,2})
v1, _ := cache.Get("apple")
v1[0] = 100
v2, _ := cache.Get("apple")
fmt.Println(v1, v2)

func Enable2Q

func Enable2Q[K comparable, V any](size int) cacheOptionFunc[K, V]

Enable 2Q algorithm

func EnableDeepCopy

func EnableDeepCopy[K comparable, V any]() cacheOptionFunc[K, V]

Enable to return a deep copy of the value in `Get`, `Peek`, `PeekOldest`, `Keys` and `Values`.

cache, _ := lru.New[string, string](3, lru.EnableDeepCopy())
cache.Put("foo", []int{1,2})
v1, _ := cache.Get("apple")
v1[0] = 100
v2, _ := cache.Get("apple")
fmt.Println(v1, v2)

func EnableLRUK

func EnableLRUK[K comparable, V any](threshold uint64) cacheOptionFunc[K, V]

Enable LRU-K algorithm

func WithVisitCacheSize

func WithVisitCacheSize[K comparable, V any](size int) cacheOptionFunc[K, V]

Resize the size of visit cache.

Types

type Cache

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

Cache is a thread-safe fixed size LRU cache.

func New

func New[K comparable, V any](size int, opts ...cacheOptionFunc[K, V]) (c *Cache[K, V], err error)

New creates an LRU of the given size.

func (*Cache[K, V]) Cap

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

Values returns the size of LRU cache.

cache, _ := lru.New[string, string](3)
fmt.Println(lru.Cap())

func (*Cache[K, V]) Clear

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

Clears all cache entries.

cache, _ := lru.New[string, string](3)
cache.Put("apple", "red")
cache.Put("banana", "yellow")
cache.Clear()
fmt.Println(cache.Len())

func (*Cache[K, V]) Contains

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

Checks if a key exists in cache without updating the recent-ness.

cache, _ := lru.New[string, string](3)
cache.Put("apple", "red")
cache.Put("banana", "yellow")
fmt.Println(cache.Contains("banana"))

func (*Cache[K, V]) FIFOCap

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

FIFOCap returns the size of fifo-list.

func (*Cache[K, V]) FIFOLen

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

FIFOLen returns the number of items in the fifo-list

func (*Cache[K, V]) FIFOResize

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

FIFOResize changes the fifo-list size.

func (*Cache[K, V]) Get

func (c *Cache[K, V]) Get(key K) (value V, ok bool)

Get looks up a key's value from the cache with updating the "recently used"-ness of the key.

cache, _ := lru.New[string, string](3)
cache.Put("apple", "red")
cache.Put("banana", "yellow")
v, ok := cache.Get("banana")
fmt.Println(ok, v)

func (*Cache[K, V]) IsEnable2Q

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

whether or not enable 2Q algorithm

func (*Cache[K, V]) IsEnableLRUK

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

whether or not enable LRU-K algorithm

func (*Cache[K, V]) Keys

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

Keys returns a slice of the keys in the cache, from oldest to newest.

cache, _ := lru.New[string, string](3)
cache.Put("apple", "red")
cache.Put("banana", "yellow")
fmt.Printf("%+v", cache.Keys())

func (*Cache[K, V]) Len

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

Len returns the number of items in the LRU cache.

cache, _ := lru.New[string, string](3)
cache.Put("apple", "red")
cache.Put("banana", "yellow")
fmt.Println(lru.Len())

func (*Cache) OptionalCopyKey

func (c *Cache) OptionalCopyKey(data K) K

func (*Cache) OptionalCopyKeyN

func (c *Cache) OptionalCopyKeyN(data []K) []K

func (*Cache) OptionalCopyValue

func (c *Cache) OptionalCopyValue(data V) V

func (*Cache) OptionalCopyValueN

func (c *Cache) OptionalCopyValueN(data []V) []V

func (*Cache[K, V]) Peek

func (c *Cache[K, V]) Peek(key K) (value V, ok bool)

Peek returns the key value (or undefined if not found) without updating the "recently used"-ness of the key.

cache, _ := lru.New[string, string](3)
cache.Put("apple", "red")
cache.Put("banana", "yellow")
v, ok := cache.Peek("banana")
fmt.Println(ok, v)

func (*Cache[K, V]) PeekOldest

func (c *Cache[K, V]) PeekOldest() (key K, value V, ok bool)

Returns the oldest entry without updating the "recently used"-ness of the key.

cache, _ := lru.New[string, string](3)
cache.Put("apple", "red")
cache.Put("banana", "yellow")
k, v, ok := cache.PeekOldest()
fmt.Println(ok, k, v)

func (*Cache[K, V]) Push

func (c *Cache[K, V]) Push(key K, value V) (oldKey K, oldValue V, ok bool)

Pushes a key-value pair into the cache. If an entry with key `key` already exists in the cache or another cache entry is removed (due to the lru's capacity), then it returns the old entry's key-value pair or not.

cache, _ := lru.New[string, string](3)
cache.Push("apple", "red")

func (*Cache[K, V]) Put

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

Puts a key-value pair into cache. If the key already exists in the cache, then it updates the key's value and returns the old value or not.

cache, _ := lru.New[string, string](3)
cache.Put("apple", "red")
fmt.Println(ok, k, v)

func (*Cache[K, V]) Remove

func (c *Cache[K, V]) Remove(key K) (value V, ok bool)

Remove removes the provided key from the cache, returning the value if the key was contained.

cache, _ := lru.New[string, string](3)
cache.Put("apple", "red")
cache.Put("banana", "yellow")
v, ok := cache.Remove("apple")
fmt.Println(ok, v)

func (*Cache[K, V]) RemoveOldest

func (c *Cache[K, V]) RemoveOldest() (key K, value V, ok bool)

RemoveOldest removes the oldest item from the cache.

cache, _ := lru.New[string, string](3)
k, v, ok := cache.RemoveOldest()

func (*Cache[K, V]) Resize

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

Resize changes the cache size.

cache, _ := lru.New[string, string](3)
cache.Put("apple", "red")
cache.Put("banana", "yellow")
cache.Put("orange", "orange")
fmt.Println(cache.Resize(2), cache.Cap())

func (*Cache[K, V]) Values

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

Values returns a slice of the values in the cache, from oldest to newest.

cache, _ := lru.New[string, string](3)
cache.Put("apple", "red")
cache.Put("banana", "yellow")
fmt.Printf("%+v", cache.Values())

func (*Cache[K, V]) VisitsCap

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

VisitsCap returns the size of LFU cache.

func (*Cache[K, V]) VisitsLen

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

VisitsLen returns the number of items in the LFU cache.

func (*Cache[K, V]) VisitsResize

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

VisitsResize changes the LFU cache size.