lruexpirecache.go

Documentation: k8s.io/apimachinery/pkg/util/cache

     1  /*
     2  Copyright 2016 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package cache
    18  
    19  import (
    20  	"container/list"
    21  	"sync"
    22  	"time"
    23  )
    24  
    25  // Clock defines an interface for obtaining the current time
    26  type Clock interface {
    27  	Now() time.Time
    28  }
    29  
    30  // realClock implements the Clock interface by calling time.Now()
    31  type realClock struct{}
    32  
    33  func (realClock) Now() time.Time { return time.Now() }
    34  
    35  // LRUExpireCache is a cache that ensures the mostly recently accessed keys are returned with
    36  // a ttl beyond which keys are forcibly expired.
    37  type LRUExpireCache struct {
    38  	// clock is used to obtain the current time
    39  	clock Clock
    40  
    41  	lock sync.Mutex
    42  
    43  	maxSize      int
    44  	evictionList list.List
    45  	entries      map[interface{}]*list.Element
    46  }
    47  
    48  // NewLRUExpireCache creates an expiring cache with the given size
    49  func NewLRUExpireCache(maxSize int) *LRUExpireCache {
    50  	return NewLRUExpireCacheWithClock(maxSize, realClock{})
    51  }
    52  
    53  // NewLRUExpireCacheWithClock creates an expiring cache with the given size, using the specified clock to obtain the current time.
    54  func NewLRUExpireCacheWithClock(maxSize int, clock Clock) *LRUExpireCache {
    55  	if maxSize <= 0 {
    56  		panic("maxSize must be > 0")
    57  	}
    58  
    59  	return &LRUExpireCache{
    60  		clock:   clock,
    61  		maxSize: maxSize,
    62  		entries: map[interface{}]*list.Element{},
    63  	}
    64  }
    65  
    66  type cacheEntry struct {
    67  	key        interface{}
    68  	value      interface{}
    69  	expireTime time.Time
    70  }
    71  
    72  // Add adds the value to the cache at key with the specified maximum duration.
    73  func (c *LRUExpireCache) Add(key interface{}, value interface{}, ttl time.Duration) {
    74  	c.lock.Lock()
    75  	defer c.lock.Unlock()
    76  
    77  	// Key already exists
    78  	oldElement, ok := c.entries[key]
    79  	if ok {
    80  		c.evictionList.MoveToFront(oldElement)
    81  		oldElement.Value.(*cacheEntry).value = value
    82  		oldElement.Value.(*cacheEntry).expireTime = c.clock.Now().Add(ttl)
    83  		return
    84  	}
    85  
    86  	// Make space if necessary
    87  	if c.evictionList.Len() >= c.maxSize {
    88  		toEvict := c.evictionList.Back()
    89  		c.evictionList.Remove(toEvict)
    90  		delete(c.entries, toEvict.Value.(*cacheEntry).key)
    91  	}
    92  
    93  	// Add new entry
    94  	entry := &cacheEntry{
    95  		key:        key,
    96  		value:      value,
    97  		expireTime: c.clock.Now().Add(ttl),
    98  	}
    99  	element := c.evictionList.PushFront(entry)
   100  	c.entries[key] = element
   101  }
   102  
   103  // Get returns the value at the specified key from the cache if it exists and is not
   104  // expired, or returns false.
   105  func (c *LRUExpireCache) Get(key interface{}) (interface{}, bool) {
   106  	c.lock.Lock()
   107  	defer c.lock.Unlock()
   108  
   109  	element, ok := c.entries[key]
   110  	if !ok {
   111  		return nil, false
   112  	}
   113  
   114  	if c.clock.Now().After(element.Value.(*cacheEntry).expireTime) {
   115  		c.evictionList.Remove(element)
   116  		delete(c.entries, key)
   117  		return nil, false
   118  	}
   119  
   120  	c.evictionList.MoveToFront(element)
   121  
   122  	return element.Value.(*cacheEntry).value, true
   123  }
   124  
   125  // Remove removes the specified key from the cache if it exists
   126  func (c *LRUExpireCache) Remove(key interface{}) {
   127  	c.lock.Lock()
   128  	defer c.lock.Unlock()
   129  
   130  	element, ok := c.entries[key]
   131  	if !ok {
   132  		return
   133  	}
   134  
   135  	c.evictionList.Remove(element)
   136  	delete(c.entries, key)
   137  }
   138  
   139  // RemoveAll removes all keys that match predicate.
   140  func (c *LRUExpireCache) RemoveAll(predicate func(key any) bool) {
   141  	c.lock.Lock()
   142  	defer c.lock.Unlock()
   143  
   144  	for key, element := range c.entries {
   145  		if predicate(key) {
   146  			c.evictionList.Remove(element)
   147  			delete(c.entries, key)
   148  		}
   149  	}
   150  }
   151  
   152  // Keys returns all unexpired keys in the cache.
   153  //
   154  // Keep in mind that subsequent calls to Get() for any of the returned keys
   155  // might return "not found".
   156  //
   157  // Keys are returned ordered from least recently used to most recently used.
   158  func (c *LRUExpireCache) Keys() []interface{} {
   159  	c.lock.Lock()
   160  	defer c.lock.Unlock()
   161  
   162  	now := c.clock.Now()
   163  
   164  	val := make([]interface{}, 0, c.evictionList.Len())
   165  	for element := c.evictionList.Back(); element != nil; element = element.Prev() {
   166  		// Only return unexpired keys
   167  		if !now.After(element.Value.(*cacheEntry).expireTime) {
   168  			val = append(val, element.Value.(*cacheEntry).key)
   169  		}
   170  	}
   171  
   172  	return val
   173  }
   174
View as plain text