-
Notifications
You must be signed in to change notification settings - Fork 1
/
lru.go
95 lines (81 loc) · 2.08 KB
/
lru.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// Copyright 2011 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 implements an LRU cache.
package lru
import (
"container/list"
"sync"
)
// Cache is an LRU cache, safe for concurrent access.
type Cache struct {
maxEntries int
mu sync.Mutex
ll *list.List
cache map[interface{}]*list.Element
}
// *entry is the type stored in each *list.Element.
type entry struct {
key, value interface{}
}
// New returns a new cache with the provided maximum items.
func New(maxEntries int) *Cache {
return &Cache{
maxEntries: maxEntries,
ll: list.New(),
cache: make(map[interface{}]*list.Element),
}
}
// Add adds the provided key and value to the cache, evicting
// an old item if necessary.
func (c *Cache) Add(key, value interface{}) {
c.mu.Lock()
defer c.mu.Unlock()
// Already in cache?
if ee, ok := c.cache[key]; ok {
c.ll.MoveToFront(ee)
ee.Value.(*entry).value = value
return
}
// Add to cache if not present
ele := c.ll.PushFront(&entry{key, value})
c.cache[key] = ele
if c.ll.Len() > c.maxEntries {
c.removeOldest()
}
}
// Get fetches the key's value from the cache.
// The ok result will be true if the item was found.
func (c *Cache) Get(key interface{}) (value interface{}, ok bool) {
c.mu.Lock()
defer c.mu.Unlock()
if ele, hit := c.cache[key]; hit {
c.ll.MoveToFront(ele)
return ele.Value.(*entry).value, true
}
return
}
// RemoveOldest removes the oldest item in the cache and returns its key and value.
// If the cache is empty, the empty string and nil are returned.
func (c *Cache) RemoveOldest() (key, value interface{}) {
c.mu.Lock()
defer c.mu.Unlock()
return c.removeOldest()
}
// note: must hold c.mu
func (c *Cache) removeOldest() (key, value interface{}) {
ele := c.ll.Back()
if ele == nil {
return
}
c.ll.Remove(ele)
ent := ele.Value.(*entry)
delete(c.cache, ent.key)
return ent.key, ent.value
}
// Len returns the number of items in the cache.
func (c *Cache) Len() int {
c.mu.Lock()
defer c.mu.Unlock()
return c.ll.Len()
}