Documentation
¶
Overview ¶
Package eviction - Adaptive Replacement Cache (ARC) algorithm implementation.
Package eviction CAWOLFU is an eviction algorithm that uses the Cache-Aware Write-Optimized LFU (CAWOLFU) policy to select items for eviction.
Package eviction - Clock algorithm keeps a circular buffer ("hand") of pages and gives each page a second chance by decrementing an access count before eviction. The hand advances until it finds a page with zero access count, which is then evicted.
Package eviction - Least Frequently Used (LFU) eviction algorithm implementation ¶
Package eviction - LRU discards the least recently used entry first. Doubly linked list keeps MRU at head and LRU at tail; access moves node to head.
Index ¶
- type ARC
- type AlgorithmRegistry
- func (r *AlgorithmRegistry) NewAlgorithm(algorithmName string, capacity int) (IAlgorithm, error)
- func (r *AlgorithmRegistry) Register(name string, createFunc func(capacity int) (IAlgorithm, error))
- func (r *AlgorithmRegistry) RegisterMultiple(algorithms map[string]func(capacity int) (IAlgorithm, error))
- type CAWOLFU
- type CAWOLFULinkedList
- type CAWOLFUNode
- type ClockAlgorithm
- type FrequencyHeap
- type IAlgorithm
- type LFUAlgorithm
- type LRU
- type Node
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ARC ¶
type ARC struct {
// contains filtered or unexported fields
}
ARC implements the Adaptive Replacement Cache (resident T1/T2 and ghost B1/B2).
func NewARCAlgorithm ¶
NewARCAlgorithm creates a new ARC with capacity.
type AlgorithmRegistry ¶
type AlgorithmRegistry struct {
// contains filtered or unexported fields
}
AlgorithmRegistry manages eviction algorithm constructors.
func NewAlgorithmRegistry ¶
func NewAlgorithmRegistry() *AlgorithmRegistry
NewAlgorithmRegistry creates a new algorithm registry.
func NewEmptyAlgorithmRegistry ¶
func NewEmptyAlgorithmRegistry() *AlgorithmRegistry
NewEmptyAlgorithmRegistry creates a new algorithm registry without default algorithms. This is useful for testing or when you want to register only specific algorithms.
func (*AlgorithmRegistry) NewAlgorithm ¶
func (r *AlgorithmRegistry) NewAlgorithm(algorithmName string, capacity int) (IAlgorithm, error)
NewAlgorithm creates a new eviction algorithm with the given capacity.
func (*AlgorithmRegistry) Register ¶
func (r *AlgorithmRegistry) Register(name string, createFunc func(capacity int) (IAlgorithm, error))
Register registers a new eviction algorithm with the given name.
func (*AlgorithmRegistry) RegisterMultiple ¶
func (r *AlgorithmRegistry) RegisterMultiple(algorithms map[string]func(capacity int) (IAlgorithm, error))
RegisterMultiple registers a set of eviction algorithms.
type CAWOLFU ¶
type CAWOLFU struct {
// contains filtered or unexported fields
}
CAWOLFU is an eviction algorithm that uses the Cache-Aware Write-Optimized LFU (CAWOLFU) policy to select items for eviction.
func NewCAWOLFU ¶
NewCAWOLFU returns a new CAWOLFU with the given capacity.
type CAWOLFULinkedList ¶
type CAWOLFULinkedList struct {
// contains filtered or unexported fields
}
CAWOLFULinkedList is a struct that represents a linked list. It has a head and tail field.
type CAWOLFUNode ¶
type CAWOLFUNode struct {
// contains filtered or unexported fields
}
CAWOLFUNode is a struct that represents a node in the linked list. It has a key, value, and access count field.
type ClockAlgorithm ¶
type ClockAlgorithm struct {
// contains filtered or unexported fields
}
ClockAlgorithm is an in-memory cache with the Clock algorithm.
func NewClockAlgorithm ¶
func NewClockAlgorithm(capacity int) (*ClockAlgorithm, error)
NewClockAlgorithm creates a new in-memory cache with the given capacity and the Clock algorithm.
func (*ClockAlgorithm) Delete ¶
func (c *ClockAlgorithm) Delete(key string)
Delete deletes the item with the given key from the cache.
func (*ClockAlgorithm) Evict ¶
func (c *ClockAlgorithm) Evict() (string, bool)
Evict evicts an item from the cache based on the Clock algorithm.
func (*ClockAlgorithm) Get ¶
func (c *ClockAlgorithm) Get(key string) (any, bool)
Get retrieves the item with the given key from the cache.
func (*ClockAlgorithm) Set ¶
func (c *ClockAlgorithm) Set(key string, value any)
Set sets the item with the given key and value in the cache.
type FrequencyHeap ¶
type FrequencyHeap []*Node
FrequencyHeap is a heap of Nodes.
func (FrequencyHeap) Less ¶
func (fh FrequencyHeap) Less(i, j int) bool
Less returns true if the node at index i has a lower frequency than the node at index j.
func (*FrequencyHeap) Pop ¶
func (fh *FrequencyHeap) Pop() any
Pop removes the last node from the heap.
func (FrequencyHeap) Swap ¶
func (fh FrequencyHeap) Swap(i, j int)
Swap swaps the nodes at index i and j.
type IAlgorithm ¶
type IAlgorithm interface {
// Evict returns the next item to be evicted from the cache.
Evict() (string, bool)
// Set adds a new item to the cache with the given key.
Set(key string, value any)
// Get retrieves the item with the given key from the cache.
Get(key string) (any, bool)
// Delete removes the item with the given key from the cache.
Delete(key string)
}
IAlgorithm is the interface that must be implemented by eviction algorithms.
func NewEvictionAlgorithm ¶
func NewEvictionAlgorithm(algorithmName string, capacity int) (IAlgorithm, error)
NewEvictionAlgorithm creates a new eviction algorithm with the given capacity. It uses a new registry instance with default algorithms for each call. If the capacity is negative, it returns an error. The algorithmName parameter is used to select the eviction algorithm from the default algorithms.
type LFUAlgorithm ¶
type LFUAlgorithm struct {
// contains filtered or unexported fields
}
LFUAlgorithm is an eviction algorithm that uses the Least Frequently Used (LFU) policy to select items for eviction.
func NewLFUAlgorithm ¶
func NewLFUAlgorithm(capacity int) (*LFUAlgorithm, error)
NewLFUAlgorithm creates a new LFUAlgorithm with the given capacity.
func (*LFUAlgorithm) Delete ¶
func (l *LFUAlgorithm) Delete(key string)
Delete deletes a key-value pair from the cache.
func (*LFUAlgorithm) Evict ¶
func (l *LFUAlgorithm) Evict() (string, bool)
Evict evicts an item from the cache based on the LFU algorithm.
func (*LFUAlgorithm) Get ¶
func (l *LFUAlgorithm) Get(key string) (any, bool)
Get gets a value from the cache.
func (*LFUAlgorithm) Set ¶
func (l *LFUAlgorithm) Set(key string, value any)
Set sets a key-value pair in the cache.
type LRU ¶
type LRU struct {
sync.RWMutex // The mutex used to protect the cache
// contains filtered or unexported fields
}
LRU represents a LRU cache.
func NewLRUAlgorithm ¶
NewLRUAlgorithm creates a new LRU cache with the given capacity.
Source Files