1/*
  2Copyright 2013 Google Inc.
  3
  4Licensed under the Apache License, Version 2.0 (the "License");
  5you may not use this file except in compliance with the License.
  6You may obtain a copy of the License at
  7
  8     http://www.apache.org/licenses/LICENSE-2.0
  9
 10Unless required by applicable law or agreed to in writing, software
 11distributed under the License is distributed on an "AS IS" BASIS,
 12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 13See the License for the specific language governing permissions and
 14limitations under the License.
 15*/
 16
 17// Package lru implements an LRU cache.
 18package lru
 19
 20import "container/list"
 21
 22// Cache is an LRU cache. It is not safe for concurrent access.
 23type 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
 37type Key interface{}
 38
 39type 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.
 47func 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.
 56func (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.
 74func (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.
 86func (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.
 96func (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
106func (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.
116func (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.
124func (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}