list.go

Documentation: github.com/hashicorp/golang-lru/v2/internal

     1  // Copyright 2009 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE_list file.
     4  
     5  package internal
     6  
     7  import "time"
     8  
     9  // Entry is an LRU Entry
    10  type Entry[K comparable, V any] struct {
    11  	// Next and previous pointers in the doubly-linked list of elements.
    12  	// To simplify the implementation, internally a list l is implemented
    13  	// as a ring, such that &l.root is both the next element of the last
    14  	// list element (l.Back()) and the previous element of the first list
    15  	// element (l.Front()).
    16  	next, prev *Entry[K, V]
    17  
    18  	// The list to which this element belongs.
    19  	list *LruList[K, V]
    20  
    21  	// The LRU Key of this element.
    22  	Key K
    23  
    24  	// The Value stored with this element.
    25  	Value V
    26  
    27  	// The time this element would be cleaned up, optional
    28  	ExpiresAt time.Time
    29  
    30  	// The expiry bucket item was put in, optional
    31  	ExpireBucket uint8
    32  }
    33  
    34  // PrevEntry returns the previous list element or nil.
    35  func (e *Entry[K, V]) PrevEntry() *Entry[K, V] {
    36  	if p := e.prev; e.list != nil && p != &e.list.root {
    37  		return p
    38  	}
    39  	return nil
    40  }
    41  
    42  // LruList represents a doubly linked list.
    43  // The zero Value for LruList is an empty list ready to use.
    44  type LruList[K comparable, V any] struct {
    45  	root Entry[K, V] // sentinel list element, only &root, root.prev, and root.next are used
    46  	len  int         // current list Length excluding (this) sentinel element
    47  }
    48  
    49  // Init initializes or clears list l.
    50  func (l *LruList[K, V]) Init() *LruList[K, V] {
    51  	l.root.next = &l.root
    52  	l.root.prev = &l.root
    53  	l.len = 0
    54  	return l
    55  }
    56  
    57  // NewList returns an initialized list.
    58  func NewList[K comparable, V any]() *LruList[K, V] { return new(LruList[K, V]).Init() }
    59  
    60  // Length returns the number of elements of list l.
    61  // The complexity is O(1).
    62  func (l *LruList[K, V]) Length() int { return l.len }
    63  
    64  // Back returns the last element of list l or nil if the list is empty.
    65  func (l *LruList[K, V]) Back() *Entry[K, V] {
    66  	if l.len == 0 {
    67  		return nil
    68  	}
    69  	return l.root.prev
    70  }
    71  
    72  // lazyInit lazily initializes a zero List Value.
    73  func (l *LruList[K, V]) lazyInit() {
    74  	if l.root.next == nil {
    75  		l.Init()
    76  	}
    77  }
    78  
    79  // insert inserts e after at, increments l.len, and returns e.
    80  func (l *LruList[K, V]) insert(e, at *Entry[K, V]) *Entry[K, V] {
    81  	e.prev = at
    82  	e.next = at.next
    83  	e.prev.next = e
    84  	e.next.prev = e
    85  	e.list = l
    86  	l.len++
    87  	return e
    88  }
    89  
    90  // insertValue is a convenience wrapper for insert(&Entry{Value: v, ExpiresAt: ExpiresAt}, at).
    91  func (l *LruList[K, V]) insertValue(k K, v V, expiresAt time.Time, at *Entry[K, V]) *Entry[K, V] {
    92  	return l.insert(&Entry[K, V]{Value: v, Key: k, ExpiresAt: expiresAt}, at)
    93  }
    94  
    95  // Remove removes e from its list, decrements l.len
    96  func (l *LruList[K, V]) Remove(e *Entry[K, V]) V {
    97  	e.prev.next = e.next
    98  	e.next.prev = e.prev
    99  	e.next = nil // avoid memory leaks
   100  	e.prev = nil // avoid memory leaks
   101  	e.list = nil
   102  	l.len--
   103  
   104  	return e.Value
   105  }
   106  
   107  // move moves e to next to at.
   108  func (l *LruList[K, V]) move(e, at *Entry[K, V]) {
   109  	if e == at {
   110  		return
   111  	}
   112  	e.prev.next = e.next
   113  	e.next.prev = e.prev
   114  
   115  	e.prev = at
   116  	e.next = at.next
   117  	e.prev.next = e
   118  	e.next.prev = e
   119  }
   120  
   121  // PushFront inserts a new element e with value v at the front of list l and returns e.
   122  func (l *LruList[K, V]) PushFront(k K, v V) *Entry[K, V] {
   123  	l.lazyInit()
   124  	return l.insertValue(k, v, time.Time{}, &l.root)
   125  }
   126  
   127  // PushFrontExpirable inserts a new expirable element e with Value v at the front of list l and returns e.
   128  func (l *LruList[K, V]) PushFrontExpirable(k K, v V, expiresAt time.Time) *Entry[K, V] {
   129  	l.lazyInit()
   130  	return l.insertValue(k, v, expiresAt, &l.root)
   131  }
   132  
   133  // MoveToFront moves element e to the front of list l.
   134  // If e is not an element of l, the list is not modified.
   135  // The element must not be nil.
   136  func (l *LruList[K, V]) MoveToFront(e *Entry[K, V]) {
   137  	if e.list != l || l.root.next == e {
   138  		return
   139  	}
   140  	// see comment in List.Remove about initialization of l
   141  	l.move(e, &l.root)
   142  }
   143
View as plain text