README
¶
LRU Cache
A quick primer: https://en.wikipedia.org/wiki/Cache_algorithms under section
Least Recently Used (LRU)
How LRU Caches are used in Olivia
As of the current time in writing this, LRU Caches are used solely to memoize
key hashes so that every insertion/retrieval of a key from the bloom filters
don't need to always hash the key x times.
The backbone of the LRU cache is a min binary heap ordering by unix nano timestamps.
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
var MAXINT64 = int64(1<<63 - 1)
MAXINT64 Signifies the maximum value for an int64 in Go
Functions ¶
This section is empty.
Types ¶
type LRUCacheInt32Array ¶
type LRUCacheInt32Array struct {
KeyCount int
Keys map[string][]uint32
KeyTimeouts binheap.BinHeap
Mutex *sync.Mutex
}
LRUCacheInt32Array is a simple implementation of an LRU cache which will be used in the cache based whenever we want to cache values that we don't care too much if they're frequently thrown away, so long as the most frequently sought keys are preserved within the datastructure.
func NewInt32Array ¶
func NewInt32Array(maxEntries int) *LRUCacheInt32Array
New simply allocates a new instance of an LRU cache with `maxEntries` total slots.
func (*LRUCacheInt32Array) Add ¶
func (l *LRUCacheInt32Array) Add(key string, value []uint32) ([]uint32, bool)
Add handles adding keys to the cache and verifying that any values already existing in the map are prioritized higher. If too many (max amount) of keys are already in the LRU Cache, we will remove the least high prioritized to make room for a new key. If the return value for the `bool` is false, that means the key was added. If the return value for the `bool` is false, that means the key already existed in the LRU cache.
func (*LRUCacheInt32Array) Get ¶
func (l *LRUCacheInt32Array) Get(key string) ([]uint32, bool)
Get Retrieves a key from the LRU cache and increases its priority.
func (*LRUCacheInt32Array) RemoveLeastUsed ¶
func (l *LRUCacheInt32Array) RemoveLeastUsed()
RemoveLeastUsed removes the least high prioritized key in the LRU cache. Because we use an underlying map of string : uint32 (unix timestamp), we also remove any keys from that map, as well.
type LRUCacheString ¶
type LRUCacheString struct {
KeyCount int
Keys map[string]string
KeyTimeouts shared.BinHeap
Mutex *sync.Mutex
}
LRUCache is a simple implementation of an LRU cache which will be used in the cache based whenever we want to cache values that we don't care too much if they're frequently thrown away, so long as the most frequently sought keys are preserved within the datastructure.
func NewString ¶
func NewString(maxEntries int) *LRUCacheString
New simply allocates a new instance of an LRU cache with `maxEntries` total slots.
func (*LRUCacheString) Add ¶
func (l *LRUCacheString) Add(key string, value string) (string, bool)
Add handles adding keys to the cache and verifying that any values already existing in the map are prioritized higher. If too many (max amount) of keys are already in the LRU Cache, we will remove the least high prioritized to make room for a new key. If the return value for the `bool` is false, that means the key was added. If the return value for the `bool` is false, that means the key already existed in the LRU cache.
func (*LRUCacheString) Get ¶
func (l *LRUCacheString) Get(key string) (string, bool)
Get Retrieves a key from the LRU cache and increases its priority.
func (*LRUCacheString) RemoveLeastUsed ¶
func (l *LRUCacheString) RemoveLeastUsed()
RemoveLeastUsed removes the least high prioritized key in the LRU cache. Because we use an underlying map of string : int64 (unix timestamp), we also remove any keys from that map, as well.
Source Files