podman

1
/*
2
Copyright 2013 Google Inc.
3

4
Licensed under the Apache License, Version 2.0 (the "License");
5
you may not use this file except in compliance with the License.
6
You may obtain a copy of the License at
7

8
     http://www.apache.org/licenses/LICENSE-2.0
9

10
Unless required by applicable law or agreed to in writing, software
11
distributed under the License is distributed on an "AS IS" BASIS,
12
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13
See the License for the specific language governing permissions and
14
limitations under the License.
15
*/
16

17
// Package lru implements an LRU cache.
18
package lru
19

20
import "container/list"
21

22
// Cache is an LRU cache. It is not safe for concurrent access.
23
type Cache struct {
24
	// MaxEntries is the maximum number of cache entries before
25
	// an item is evicted. Zero means no limit.
26
	MaxEntries int
27

28
	// OnEvicted optionally specifies a callback function to be
29
	// executed when an entry is purged from the cache.
30
	OnEvicted func(key Key, value interface{})
31

32
	ll    *list.List
33
	cache map[interface{}]*list.Element
34
}
35

36
// A Key may be any value that is comparable. See http://golang.org/ref/spec#Comparison_operators
37
type Key interface{}
38

39
type entry struct {
40
	key   Key
41
	value interface{}
42
}
43

44
// New creates a new Cache.
45
// If maxEntries is zero, the cache has no limit and it's assumed
46
// that eviction is done by the caller.
47
func New(maxEntries int) *Cache {
48
	return &Cache{
49
		MaxEntries: maxEntries,
50
		ll:         list.New(),
51
		cache:      make(map[interface{}]*list.Element),
52
	}
53
}
54

55
// Add adds a value to the cache.
56
func (c *Cache) Add(key Key, value interface{}) {
57
	if c.cache == nil {
58
		c.cache = make(map[interface{}]*list.Element)
59
		c.ll = list.New()
60
	}
61
	if ee, ok := c.cache[key]; ok {
62
		c.ll.MoveToFront(ee)
63
		ee.Value.(*entry).value = value
64
		return
65
	}
66
	ele := c.ll.PushFront(&entry{key, value})
67
	c.cache[key] = ele
68
	if c.MaxEntries != 0 && c.ll.Len() > c.MaxEntries {
69
		c.RemoveOldest()
70
	}
71
}
72

73
// Get looks up a key's value from the cache.
74
func (c *Cache) Get(key Key) (value interface{}, ok bool) {
75
	if c.cache == nil {
76
		return
77
	}
78
	if ele, hit := c.cache[key]; hit {
79
		c.ll.MoveToFront(ele)
80
		return ele.Value.(*entry).value, true
81
	}
82
	return
83
}
84

85
// Remove removes the provided key from the cache.
86
func (c *Cache) Remove(key Key) {
87
	if c.cache == nil {
88
		return
89
	}
90
	if ele, hit := c.cache[key]; hit {
91
		c.removeElement(ele)
92
	}
93
}
94

95
// RemoveOldest removes the oldest item from the cache.
96
func (c *Cache) RemoveOldest() {
97
	if c.cache == nil {
98
		return
99
	}
100
	ele := c.ll.Back()
101
	if ele != nil {
102
		c.removeElement(ele)
103
	}
104
}
105

106
func (c *Cache) removeElement(e *list.Element) {
107
	c.ll.Remove(e)
108
	kv := e.Value.(*entry)
109
	delete(c.cache, kv.key)
110
	if c.OnEvicted != nil {
111
		c.OnEvicted(kv.key, kv.value)
112
	}
113
}
114

115
// Len returns the number of items in the cache.
116
func (c *Cache) Len() int {
117
	if c.cache == nil {
118
		return 0
119
	}
120
	return c.ll.Len()
121
}
122

123
// Clear purges all stored items from the cache.
124
func (c *Cache) Clear() {
125
	if c.OnEvicted != nil {
126
		for _, e := range c.cache {
127
			kv := e.Value.(*entry)
128
			c.OnEvicted(kv.key, kv.value)
129
		}
130
	}
131
	c.ll = nil
132
	c.cache = nil
133
}
134