lfucache

Documentation

Overview

Package lfucache implements LFU (Least Frequently Used) cache

Index

• type LFUCache
  • func NewCache(capacity bytesize.ByteSize) *LFUCache
  • func (c *LFUCache) Delete(key string) (ok bool)
  • func (c *LFUCache) Get(key string) (value string, ok bool)
  • func (c *LFUCache) Put(key, value string) (created bool)
  • func (c *LFUCache) Restore(closer io.ReadCloser) error
  • func (c *LFUCache) Snapshot() (raft.FSMSnapshot, error)

Types

type LFUCache

type LFUCache struct {
	sync.RWMutex
	cache.UnImplementedCache
	// contains filtered or unexported fields
}

LFUCache data structure

func NewCache

func NewCache(capacity bytesize.ByteSize) *LFUCache

NewCache LFUCache constructor

func (*LFUCache) Delete

func (c *LFUCache) Delete(key string) (ok bool)

Delete deletes a key from LFU cache

func (*LFUCache) Get

func (c *LFUCache) Get(key string) (value string, ok bool)

Get through checking node[key], we can get the node in O(1) time. Just performs update, then we can return the value of node.

func (*LFUCache) Put

func (c *LFUCache) Put(key, value string) (created bool)

Put If `key` already exists in self._node, we do the same operations as `get`, except updating the node.val to new value. Otherwise 1. if the cache reaches its capacity, pop the least frequently used item. (*) 2. add new node to self._node 3. add new node to the DLinkedList with frequency 1 4. reset minFreq to 1

(*) How to pop the least frequently used item? Two facts: 1. we maintain the minFreq, the minimum possible frequency in cache. 2. All cache with the same frequency are stored as a DLinkedList, with recently used order (Always append at head) 3. The tail of the DLinkedList with minFreq is the least recently used one, pop it.

func (*LFUCache) Restore

func (c *LFUCache) Restore(closer io.ReadCloser) error

func (*LFUCache) Snapshot

func (c *LFUCache) Snapshot() (raft.FSMSnapshot, error)