lru.go

Documentation: github.com/aws/smithy-go/container/private/cache/lru

     1  // Package lru implements [cache.Cache] with an LRU eviction policy.
     2  //
     3  // This implementation is NOT thread-safe.
     4  //
     5  // This package is designated as private and is intended for use only by the
     6  // smithy client runtime. The exported API therein is not considered stable and
     7  // is subject to breaking changes without notice.
     8  package lru
     9  
    10  import (
    11  	"container/list"
    12  
    13  	"github.com/aws/smithy-go/container/private/cache"
    14  )
    15  
    16  // New creates a new LRU cache with the given capacity.
    17  func New(cap int) cache.Cache {
    18  	return &lru{
    19  		entries: make(map[interface{}]*list.Element, cap),
    20  		cap:     cap,
    21  		mru:     list.New(),
    22  	}
    23  }
    24  
    25  type lru struct {
    26  	entries map[interface{}]*list.Element
    27  	cap     int
    28  
    29  	mru *list.List // least-recently used is at the back
    30  }
    31  
    32  type element struct {
    33  	key   interface{}
    34  	value interface{}
    35  }
    36  
    37  func (l *lru) Get(k interface{}) (interface{}, bool) {
    38  	e, ok := l.entries[k]
    39  	if !ok {
    40  		return nil, false
    41  	}
    42  
    43  	l.mru.MoveToFront(e)
    44  	return e.Value.(*element).value, true
    45  }
    46  
    47  func (l *lru) Put(k interface{}, v interface{}) {
    48  	if len(l.entries) == l.cap {
    49  		l.evict()
    50  	}
    51  
    52  	ev := &element{
    53  		key:   k,
    54  		value: v,
    55  	}
    56  	e := l.mru.PushFront(ev)
    57  	l.entries[k] = e
    58  }
    59  
    60  func (l *lru) evict() {
    61  	e := l.mru.Remove(l.mru.Back())
    62  	delete(l.entries, e.(*element).key)
    63  }
    64
View as plain text