diff options
| -rw-r--r-- | util/lru/lru.go | 125 |
1 files changed, 38 insertions, 87 deletions
diff --git a/util/lru/lru.go b/util/lru/lru.go index db77859a4..a6790cd46 100644 --- a/util/lru/lru.go +++ b/util/lru/lru.go @@ -4,6 +4,10 @@ // Package lru contains a typed Least-Recently-Used cache. package lru +import ( + "container/list" +) + // Cache is container type keyed by K, storing V, optionally evicting the least // recently used items if a maximum size is exceeded. // @@ -18,27 +22,14 @@ type Cache[K comparable, V any] struct { // an item is evicted. Zero means no limit. MaxEntries int - // head is a ring of LRU values. head points to the most recently - // used element, head.prev is the least recently used. - // - // An LRU is technically a simple list rather than a ring, but - // implementing it as a ring makes the list manipulation - // operations more regular, because the first/last positions in - // the list stop being special. - // - // head is nil when the LRU is empty. - head *entry[K, V] - // lookup is a map of all the LRU entries contained in - // head. lookup and head always contain exactly the same elements; - // lookup is just there to allow O(1) lookups of keys. - lookup map[K]*entry[K, V] + ll *list.List + m map[K]*list.Element // of *entry[K,V] } -// entry is an entry of Cache. +// entry is the element type for the container/list.Element. type entry[K comparable, V any] struct { - prev, next *entry[K, V] - key K - value V + key K + value V } // Set adds or replaces a value to the cache, set or updating its associated @@ -47,18 +38,19 @@ type entry[K comparable, V any] struct { // If MaxEntries is non-zero and the length of the cache is greater // after any addition, the least recently used value is evicted. func (c *Cache[K, V]) Set(key K, value V) { - if c.lookup == nil { - c.lookup = make(map[K]*entry[K, V]) + if c.m == nil { + c.m = make(map[K]*list.Element) + c.ll = list.New() } - if ent, ok := c.lookup[key]; ok { - c.moveToFront(ent) - ent.value = value + if ee, ok := c.m[key]; ok { + c.ll.MoveToFront(ee) + ee.Value.(*entry[K, V]).value = value return } - ent := c.newAtFront(key, value) - c.lookup[key] = ent + ele := c.ll.PushFront(&entry[K, V]{key, value}) + c.m[key] = ele if c.MaxEntries != 0 && c.Len() > c.MaxEntries { - c.deleteOldest() + c.DeleteOldest() } } @@ -79,14 +71,14 @@ func (c *Cache[K, V]) Contains(key K) bool { return ok } -// GetOk looks up a key's value from the cache, also reporting whether -// it was present. +// GetOk looks up a key's value from the cache, also reporting +// whether it was present. // // If found, key is moved to the front of the LRU. func (c *Cache[K, V]) GetOk(key K) (value V, ok bool) { - if ent, hit := c.lookup[key]; hit { - c.moveToFront(ent) - return ent.value, true + if ele, hit := c.m[key]; hit { + c.ll.MoveToFront(ele) + return ele.Value.(*entry[K, V]).value, true } var zero V return zero, false @@ -99,8 +91,8 @@ func (c *Cache[K, V]) GetOk(key K) (value V, ok bool) { // LRU. This should mostly be used for non-intrusive debug inspection // of the cache. func (c *Cache[K, V]) PeekOk(key K) (value V, ok bool) { - if ent, hit := c.lookup[key]; hit { - return ent.value, true + if ele, hit := c.m[key]; hit { + return ele.Value.(*entry[K, V]).value, true } var zero V return zero, false @@ -108,66 +100,25 @@ func (c *Cache[K, V]) PeekOk(key K) (value V, ok bool) { // Delete removes the provided key from the cache if it was present. func (c *Cache[K, V]) Delete(key K) { - if ent, ok := c.lookup[key]; ok { - c.deleteElement(ent) + if e, ok := c.m[key]; ok { + c.deleteElement(e) } } -// DeleteOldest removes the item from the cache that was least -// recently accessed. It is a no-op if the cache is empty. +// DeleteOldest removes the item from the cache that was least recently +// accessed. It is a no-op if the cache is empty. func (c *Cache[K, V]) DeleteOldest() { - if c.head != nil { - c.deleteOldest() + if c.ll != nil { + if e := c.ll.Back(); e != nil { + c.deleteElement(e) + } } } -// Len returns the number of items in the cache. -func (c *Cache[K, V]) Len() int { return len(c.lookup) } - -// newAtFront creates a new LRU entry using key and value, and inserts -// it at the front of c.head. -func (c *Cache[K, V]) newAtFront(key K, value V) *entry[K, V] { - ret := &entry[K, V]{key: key, value: value} - if c.head == nil { - ret.prev = ret - ret.next = ret - } else { - ret.next = c.head - ret.prev = c.head.prev - c.head.prev.next = ret - c.head.prev = ret - } - c.head = ret - return ret +func (c *Cache[K, V]) deleteElement(e *list.Element) { + c.ll.Remove(e) + delete(c.m, e.Value.(*entry[K, V]).key) } -// moveToFront moves ent, which must be an existing element of the -// cache, to the front of c.head. -func (c *Cache[K, V]) moveToFront(ent *entry[K, V]) { - if c.head == ent { - return - } - ent.prev.next = ent.next - ent.next.prev = ent.prev - ent.prev = c.head.prev - ent.next = c.head - c.head.prev.next = ent - c.head.prev = ent - c.head = ent -} - -// deleteOldest removes the oldest entry in the cache. It panics if -// there are no entries in the cache. -func (c *Cache[K, V]) deleteOldest() { c.deleteElement(c.head.prev) } - -// deleteElement removes ent from the cache. ent must be an existing -// current element of the cache. -func (c *Cache[K, V]) deleteElement(ent *entry[K, V]) { - if ent.next == ent { - c.head = nil - } else { - ent.next.prev = ent.prev - ent.prev.next = ent.next - } - delete(c.lookup, ent.key) -} +// Len returns the number of items in the cache. +func (c *Cache[K, V]) Len() int { return len(c.m) } |