summaryrefslogtreecommitdiff
path: root/vendor/github.com/golang/groupcache/lru/lru.go
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/golang/groupcache/lru/lru.go')
-rw-r--r--vendor/github.com/golang/groupcache/lru/lru.go133
1 files changed, 133 insertions, 0 deletions
diff --git a/vendor/github.com/golang/groupcache/lru/lru.go b/vendor/github.com/golang/groupcache/lru/lru.go
new file mode 100644
index 000000000..532cc45e6
--- /dev/null
+++ b/vendor/github.com/golang/groupcache/lru/lru.go
@@ -0,0 +1,133 @@
+/*
+Copyright 2013 Google Inc.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+*/
+
+// Package lru implements an LRU cache.
+package lru
+
+import "container/list"
+
+// Cache is an LRU cache. It is not safe for concurrent access.
+type Cache struct {
+ // MaxEntries is the maximum number of cache entries before
+ // an item is evicted. Zero means no limit.
+ MaxEntries int
+
+ // OnEvicted optionally specificies a callback function to be
+ // executed when an entry is purged from the cache.
+ OnEvicted func(key Key, value interface{})
+
+ ll *list.List
+ cache map[interface{}]*list.Element
+}
+
+// A Key may be any value that is comparable. See http://golang.org/ref/spec#Comparison_operators
+type Key interface{}
+
+type entry struct {
+ key Key
+ value interface{}
+}
+
+// New creates a new Cache.
+// If maxEntries is zero, the cache has no limit and it's assumed
+// that eviction is done by the caller.
+func New(maxEntries int) *Cache {
+ return &Cache{
+ MaxEntries: maxEntries,
+ ll: list.New(),
+ cache: make(map[interface{}]*list.Element),
+ }
+}
+
+// Add adds a value to the cache.
+func (c *Cache) Add(key Key, value interface{}) {
+ if c.cache == nil {
+ c.cache = make(map[interface{}]*list.Element)
+ c.ll = list.New()
+ }
+ if ee, ok := c.cache[key]; ok {
+ c.ll.MoveToFront(ee)
+ ee.Value.(*entry).value = value
+ return
+ }
+ ele := c.ll.PushFront(&entry{key, value})
+ c.cache[key] = ele
+ if c.MaxEntries != 0 && c.ll.Len() > c.MaxEntries {
+ c.RemoveOldest()
+ }
+}
+
+// Get looks up a key's value from the cache.
+func (c *Cache) Get(key Key) (value interface{}, ok bool) {
+ if c.cache == nil {
+ return
+ }
+ if ele, hit := c.cache[key]; hit {
+ c.ll.MoveToFront(ele)
+ return ele.Value.(*entry).value, true
+ }
+ return
+}
+
+// Remove removes the provided key from the cache.
+func (c *Cache) Remove(key Key) {
+ if c.cache == nil {
+ return
+ }
+ if ele, hit := c.cache[key]; hit {
+ c.removeElement(ele)
+ }
+}
+
+// RemoveOldest removes the oldest item from the cache.
+func (c *Cache) RemoveOldest() {
+ if c.cache == nil {
+ return
+ }
+ ele := c.ll.Back()
+ if ele != nil {
+ c.removeElement(ele)
+ }
+}
+
+func (c *Cache) removeElement(e *list.Element) {
+ c.ll.Remove(e)
+ kv := e.Value.(*entry)
+ delete(c.cache, kv.key)
+ if c.OnEvicted != nil {
+ c.OnEvicted(kv.key, kv.value)
+ }
+}
+
+// Len returns the number of items in the cache.
+func (c *Cache) Len() int {
+ if c.cache == nil {
+ return 0
+ }
+ return c.ll.Len()
+}
+
+// Clear purges all stored items from the cache.
+func (c *Cache) Clear() {
+ if c.OnEvicted != nil {
+ for _, e := range c.cache {
+ kv := e.Value.(*entry)
+ c.OnEvicted(kv.key, kv.value)
+ }
+ }
+ c.ll = nil
+ c.cache = nil
+}