lru.go

Documentation: github.com/hashicorp/golang-lru/simplelru

     1  package simplelru
     2  
     3  import (
     4  	"container/list"
     5  	"errors"
     6  )
     7  
     8  // EvictCallback is used to get a callback when a cache entry is evicted
     9  type EvictCallback func(key interface{}, value interface{})
    10  
    11  // LRU implements a non-thread safe fixed size LRU cache
    12  type LRU struct {
    13  	size      int
    14  	evictList *list.List
    15  	items     map[interface{}]*list.Element
    16  	onEvict   EvictCallback
    17  }
    18  
    19  // entry is used to hold a value in the evictList
    20  type entry struct {
    21  	key   interface{}
    22  	value interface{}
    23  }
    24  
    25  // NewLRU constructs an LRU of the given size
    26  func NewLRU(size int, onEvict EvictCallback) (*LRU, error) {
    27  	if size <= 0 {
    28  		return nil, errors.New("must provide a positive size")
    29  	}
    30  	c := &LRU{
    31  		size:      size,
    32  		evictList: list.New(),
    33  		items:     make(map[interface{}]*list.Element),
    34  		onEvict:   onEvict,
    35  	}
    36  	return c, nil
    37  }
    38  
    39  // Purge is used to completely clear the cache.
    40  func (c *LRU) Purge() {
    41  	for k, v := range c.items {
    42  		if c.onEvict != nil {
    43  			c.onEvict(k, v.Value.(*entry).value)
    44  		}
    45  		delete(c.items, k)
    46  	}
    47  	c.evictList.Init()
    48  }
    49  
    50  // Add adds a value to the cache.  Returns true if an eviction occurred.
    51  func (c *LRU) Add(key, value interface{}) (evicted bool) {
    52  	// Check for existing item
    53  	if ent, ok := c.items[key]; ok {
    54  		c.evictList.MoveToFront(ent)
    55  		ent.Value.(*entry).value = value
    56  		return false
    57  	}
    58  
    59  	// Add new item
    60  	ent := &entry{key, value}
    61  	entry := c.evictList.PushFront(ent)
    62  	c.items[key] = entry
    63  
    64  	evict := c.evictList.Len() > c.size
    65  	// Verify size not exceeded
    66  	if evict {
    67  		c.removeOldest()
    68  	}
    69  	return evict
    70  }
    71  
    72  // Get looks up a key's value from the cache.
    73  func (c *LRU) Get(key interface{}) (value interface{}, ok bool) {
    74  	if ent, ok := c.items[key]; ok {
    75  		c.evictList.MoveToFront(ent)
    76  		if ent.Value.(*entry) == nil {
    77  			return nil, false
    78  		}
    79  		return ent.Value.(*entry).value, true
    80  	}
    81  	return
    82  }
    83  
    84  // Contains checks if a key is in the cache, without updating the recent-ness
    85  // or deleting it for being stale.
    86  func (c *LRU) Contains(key interface{}) (ok bool) {
    87  	_, ok = c.items[key]
    88  	return ok
    89  }
    90  
    91  // Peek returns the key value (or undefined if not found) without updating
    92  // the "recently used"-ness of the key.
    93  func (c *LRU) Peek(key interface{}) (value interface{}, ok bool) {
    94  	var ent *list.Element
    95  	if ent, ok = c.items[key]; ok {
    96  		return ent.Value.(*entry).value, true
    97  	}
    98  	return nil, ok
    99  }
   100  
   101  // Remove removes the provided key from the cache, returning if the
   102  // key was contained.
   103  func (c *LRU) Remove(key interface{}) (present bool) {
   104  	if ent, ok := c.items[key]; ok {
   105  		c.removeElement(ent)
   106  		return true
   107  	}
   108  	return false
   109  }
   110  
   111  // RemoveOldest removes the oldest item from the cache.
   112  func (c *LRU) RemoveOldest() (key, value interface{}, ok bool) {
   113  	ent := c.evictList.Back()
   114  	if ent != nil {
   115  		c.removeElement(ent)
   116  		kv := ent.Value.(*entry)
   117  		return kv.key, kv.value, true
   118  	}
   119  	return nil, nil, false
   120  }
   121  
   122  // GetOldest returns the oldest entry
   123  func (c *LRU) GetOldest() (key, value interface{}, ok bool) {
   124  	ent := c.evictList.Back()
   125  	if ent != nil {
   126  		kv := ent.Value.(*entry)
   127  		return kv.key, kv.value, true
   128  	}
   129  	return nil, nil, false
   130  }
   131  
   132  // Keys returns a slice of the keys in the cache, from oldest to newest.
   133  func (c *LRU) Keys() []interface{} {
   134  	keys := make([]interface{}, len(c.items))
   135  	i := 0
   136  	for ent := c.evictList.Back(); ent != nil; ent = ent.Prev() {
   137  		keys[i] = ent.Value.(*entry).key
   138  		i++
   139  	}
   140  	return keys
   141  }
   142  
   143  // Len returns the number of items in the cache.
   144  func (c *LRU) Len() int {
   145  	return c.evictList.Len()
   146  }
   147  
   148  // Resize changes the cache size.
   149  func (c *LRU) Resize(size int) (evicted int) {
   150  	diff := c.Len() - size
   151  	if diff < 0 {
   152  		diff = 0
   153  	}
   154  	for i := 0; i < diff; i++ {
   155  		c.removeOldest()
   156  	}
   157  	c.size = size
   158  	return diff
   159  }
   160  
   161  // removeOldest removes the oldest item from the cache.
   162  func (c *LRU) removeOldest() {
   163  	ent := c.evictList.Back()
   164  	if ent != nil {
   165  		c.removeElement(ent)
   166  	}
   167  }
   168  
   169  // removeElement is used to remove a given list element from the cache
   170  func (c *LRU) removeElement(e *list.Element) {
   171  	c.evictList.Remove(e)
   172  	kv := e.Value.(*entry)
   173  	delete(c.items, kv.key)
   174  	if c.onEvict != nil {
   175  		c.onEvict(kv.key, kv.value)
   176  	}
   177  }
   178
View as plain text