lru.go

Documentation: github.com/dsoprea/go-utility/v2/data

     1  package ridata
     2  
     3  import (
     4  	"errors"
     5  	"fmt"
     6  
     7  	"github.com/dsoprea/go-logging"
     8  )
     9  
    10  var (
    11  	// ErrLruEmpty indicates that the LRU is empty..
    12  	ErrLruEmpty = errors.New("lru is empty")
    13  )
    14  
    15  // LruKey is the type of an LRU key.
    16  type LruKey interface{}
    17  
    18  // LruItem is the interface that any item we add to the LRU must satisfy.
    19  type LruItem interface {
    20  	Id() LruKey
    21  }
    22  
    23  type lruNode struct {
    24  	before *lruNode
    25  	after  *lruNode
    26  	item   LruItem
    27  }
    28  
    29  // String will return a string representation of the node.
    30  func (ln *lruNode) String() string {
    31  	var beforePhrase string
    32  	if ln.before != nil {
    33  		beforePhrase = fmt.Sprintf("%v", ln.before.item.Id())
    34  	} else {
    35  		beforePhrase = "<NULL>"
    36  	}
    37  
    38  	var afterPhrase string
    39  	if ln.after != nil {
    40  		afterPhrase = fmt.Sprintf("%v", ln.after.item.Id())
    41  	} else {
    42  		afterPhrase = "<NULL>"
    43  	}
    44  
    45  	return fmt.Sprintf("[%v] BEFORE=[%s] AFTER=[%s]", ln.item.Id(), beforePhrase, afterPhrase)
    46  }
    47  
    48  type lruEventFunc func(id LruKey) (err error)
    49  
    50  // Lru establises an LRU of IDs of any type.
    51  type Lru struct {
    52  	top     *lruNode
    53  	bottom  *lruNode
    54  	lookup  map[LruKey]*lruNode
    55  	maxSize int
    56  	dropCb  lruEventFunc
    57  }
    58  
    59  // NewLru returns a new instance.
    60  func NewLru(maxSize int) *Lru {
    61  	return &Lru{
    62  		lookup:  make(map[LruKey]*lruNode),
    63  		maxSize: maxSize,
    64  	}
    65  }
    66  
    67  // SetDropCb sets a callback that will be triggered whenever an item ages out
    68  // or is manually dropped.
    69  func (lru *Lru) SetDropCb(cb lruEventFunc) {
    70  	lru.dropCb = cb
    71  }
    72  
    73  // Count returns the number of items in the LRU.
    74  func (lru *Lru) Count() int {
    75  	return len(lru.lookup)
    76  }
    77  
    78  // MaxCount returns the maximum number of items the LRU can contain.
    79  func (lru *Lru) MaxCount() int {
    80  	return lru.maxSize
    81  }
    82  
    83  // IsFull will return true if at capacity.
    84  func (lru *Lru) IsFull() bool {
    85  	return lru.Count() == lru.maxSize
    86  }
    87  
    88  // Exists will do a membership check for the given key.
    89  func (lru *Lru) Exists(id LruKey) bool {
    90  	_, found := lru.lookup[id]
    91  	return found
    92  }
    93  
    94  // FindPosition will return the numerical position in the list. Since the LRU
    95  // will never be very large, this call is not expensive, per se. But, it *is*
    96  // O(n) and any call to us will compound with any loops you happen to wrap us
    97  // into.
    98  func (lru *Lru) FindPosition(id LruKey) int {
    99  	node, found := lru.lookup[id]
   100  	if found == false {
   101  		return -1
   102  	}
   103  
   104  	position := 0
   105  	for ; node.before != nil; node = node.before {
   106  		position++
   107  	}
   108  
   109  	return position
   110  }
   111  
   112  // Get touches the cache and returns the data.
   113  func (lru *Lru) Get(id LruKey) (found bool, item LruItem, err error) {
   114  	defer func() {
   115  		if state := recover(); state != nil {
   116  			err = log.Wrap(state.(error))
   117  		}
   118  	}()
   119  
   120  	if node, found := lru.lookup[id]; found == true {
   121  		_, _, err := lru.Set(node.item)
   122  		log.PanicIf(err)
   123  
   124  		return true, node.item, nil
   125  	}
   126  
   127  	return false, nil, nil
   128  }
   129  
   130  // Set bumps an item to the front of the LRU. It will be added if it doesn't
   131  // already exist. If as a result of adding an item the LRU exceeds the maximum
   132  // size, the least recently used item will be discarded.
   133  //
   134  // If it was not previously in the LRU, `added` will be `true`.
   135  func (lru *Lru) Set(item LruItem) (added bool, droppedItem LruItem, err error) {
   136  	defer func() {
   137  		if state := recover(); state != nil {
   138  			err = log.Wrap(state.(error))
   139  		}
   140  	}()
   141  
   142  	// TODO(dustin): !! Add tests for added/droppedItem returns.
   143  
   144  	id := item.Id()
   145  
   146  	node, found := lru.lookup[id]
   147  
   148  	added = (found == false)
   149  
   150  	if found == true {
   151  		// It's already at the front.
   152  		if node.before == nil {
   153  			return added, nil, nil
   154  		}
   155  
   156  		// If we were at the bottom, the bottom is now whatever was upstream of
   157  		// us.
   158  		if lru.bottom == node {
   159  			lru.bottom = lru.bottom.before
   160  		}
   161  
   162  		// Prune.
   163  		if node.before != nil {
   164  			node.before.after = node.after
   165  			node.before = nil
   166  		}
   167  
   168  		// Insert at the front.
   169  		node.after = lru.top
   170  
   171  		// Point the head of the list to us.
   172  		lru.top = node
   173  	} else {
   174  		node = &lruNode{
   175  			after: lru.top,
   176  			item:  item,
   177  		}
   178  
   179  		lru.lookup[id] = node
   180  
   181  		// Point the head of the list to us.
   182  		lru.top = node
   183  	}
   184  
   185  	// Update the link from the downstream node.
   186  	if node.after != nil {
   187  		node.after.before = node
   188  	}
   189  
   190  	if lru.bottom == nil {
   191  		lru.bottom = node
   192  	}
   193  
   194  	if len(lru.lookup) > lru.maxSize {
   195  		lastItemId := lru.Oldest()
   196  		lastNode := lru.lookup[lastItemId]
   197  
   198  		found, err := lru.Drop(lastItemId)
   199  		log.PanicIf(err)
   200  
   201  		if found == false {
   202  			log.Panicf("drop of old item was ineffectual")
   203  		}
   204  
   205  		droppedItem = lastNode.item
   206  	}
   207  
   208  	return added, droppedItem, nil
   209  }
   210  
   211  // Drop discards the given item.
   212  func (lru *Lru) Drop(id LruKey) (found bool, err error) {
   213  	defer func() {
   214  		if state := recover(); state != nil {
   215  			err = log.Wrap(state.(error))
   216  		}
   217  	}()
   218  
   219  	node, found := lru.lookup[id]
   220  	if found == false {
   221  		return false, nil
   222  	}
   223  
   224  	// Keep the `top` node up-to-date.
   225  	if node.before == nil {
   226  		lru.top = node.after
   227  	}
   228  
   229  	// Keep the `bottom` node up-to-date.
   230  	if node.after == nil {
   231  		lru.bottom = node.before
   232  	}
   233  
   234  	// Detach us from the previous node and link that node to the one after us.
   235  	if node.before != nil {
   236  		node.before.after = node.after
   237  	}
   238  
   239  	delete(lru.lookup, id)
   240  
   241  	if lru.dropCb != nil {
   242  		err := lru.dropCb(id)
   243  		log.PanicIf(err)
   244  	}
   245  
   246  	return true, nil
   247  }
   248  
   249  // Newest returns the most recently used ID.
   250  func (lru *Lru) Newest() LruKey {
   251  	if lru.top != nil {
   252  		return lru.top.item.Id()
   253  	}
   254  
   255  	return nil
   256  }
   257  
   258  // Oldest returns the least recently used ID.
   259  func (lru *Lru) Oldest() LruKey {
   260  	if lru.bottom != nil {
   261  		return lru.bottom.item.Id()
   262  	}
   263  
   264  	return nil
   265  }
   266  
   267  // All returns a list of all IDs.
   268  func (lru *Lru) All() []LruKey {
   269  	collected := make([]LruKey, len(lru.lookup))
   270  	i := 0
   271  	for value := range lru.lookup {
   272  		collected[i] = value
   273  		i++
   274  	}
   275  
   276  	return collected
   277  }
   278  
   279  // PopOldest will pop the oldest entry out of the LRU and return it. It will
   280  // return ErrLruEmpty when empty.
   281  func (lru *Lru) PopOldest() (item LruItem, err error) {
   282  	lk := lru.Oldest()
   283  	if lk == nil {
   284  		return nil, ErrLruEmpty
   285  	}
   286  
   287  	node := lru.lookup[lk]
   288  	if node == nil {
   289  		log.Panicf("something went wrong resolving the oldest item")
   290  	}
   291  
   292  	found, err := lru.Drop(lk)
   293  	log.PanicIf(err)
   294  
   295  	if found == false {
   296  		log.Panicf("something went wrong dropping the oldest item")
   297  	}
   298  
   299  	return node.item, nil
   300  }
   301  
   302  // Dump returns a list of all IDs.
   303  func (lru *Lru) Dump() {
   304  	fmt.Printf("Count: (%d)\n", len(lru.lookup))
   305  	fmt.Printf("\n")
   306  
   307  	fmt.Printf("Top: %v\n", lru.top)
   308  	fmt.Printf("Bottom: %v\n", lru.bottom)
   309  	fmt.Printf("\n")
   310  
   311  	i := 0
   312  	for ptr := lru.top; ptr != nil; ptr = ptr.after {
   313  		fmt.Printf("%03d: %s\n", i, ptr)
   314  		i++
   315  	}
   316  }
   317
View as plain text