blob: 98630b8cceea800a715e8a5b9c49ce60bad13a45 [file] [log] [blame]
// Copyright 2023 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Package lru provides an LRU cache.
package lru
import (
// Cache is an LRU cache.
type Cache[K comparable, V any] struct {
mu sync.Mutex
size int
entries map[K]*entry[V]
tick uint // increases every time an entry is used
type entry[V any] struct {
lastUsed uint // the tick of the last operation
v V
// New returns a new Cache. Size must be positive or it will panic.
func New[K comparable, V any](size int) *Cache[K, V] {
if size < 1 {
panic(fmt.Errorf("lru.New called with non-positive size %v", size))
return &Cache[K, V]{
size: size,
entries: map[K]*entry[V]{},
// Get gets the entry for k in the Cache.
func (c *Cache[K, V]) Get(k K) (V, bool) {
entry, ok := c.entries[k]
if !ok {
var zero V
return zero, false
entry.lastUsed = c.tick
return entry.v, true
// Put puts in an entry for k, v in Cache, evicting
// the least recently used entry if necessary.
func (c *Cache[K, V]) Put(k K, v V) {
_, ok := c.entries[k]
if !ok {
// k not already in c.entries. We need to evict the least recently
// used entry.
if c.size < 1 {
panic("attempting to insert into an uninitialized cache.")
if len(c.entries) > c.size {
panic(fmt.Errorf("size of cache, %d, has grown beyond size limit %d", len(c.entries), c.size))
if len(c.entries) == c.size {
// evict least recently used element.
var oldestTick uint = math.MaxUint
var oldestKey K
for k, e := range c.entries {
if e.lastUsed <= oldestTick {
oldestTick = e.lastUsed
oldestKey = k
delete(c.entries, oldestKey)
c.entries[k] = &entry[V]{lastUsed: c.tick, v: v}