lfucache

README

lfu-go

This is the implementation of LFU in Golang on basis of this paper.

An O(1) algorithm for implementing the LFU cache eviction scheme

This implementation used Double LinkedList & HashMap,Set to implemenent the paper. Operations like Insertion/Deletion are done in O(1) operation.

package main

import (
	"fmt"

	lfu "github.com/Anshumakkar/lfu-go"
)

func main() {
	// Make a new cache with capacity of cache.
	cache := lfu.NewLFUCache(10)

	// Set some values to cache
	cache.Set("key", "value")

	// Retrieve the values from cache
	value := cache.Get("key")
	fmt.Println(value)
	// Evict values from cache forcefully
	evictedCount := cache.Evict(1)
	fmt.Println("Evicted count is ", evictedCount)
}

Documentation

Index

• type CacheEntry
• type EvictionChannel
• type LFUCache
  • func NewLFUCache(capacity int) *LFUCache
  • func (c *LFUCache) Evict(count int) int
  • func (c *LFUCache) Get(key string) interface{}
  • func (c *LFUCache) Len() int
  • func (c *LFUCache) RemoveEntry(currentNode *list.Element, e *CacheEntry)
  • func (c *LFUCache) Set(key string, value interface{})
• type ListEntry

Types

type CacheEntry

type CacheEntry struct {
	Key   string
	Value interface{}
	// contains filtered or unexported fields
}

CacheEntry - It stoes the key and value and holds address to DLL Node of that frequency

type EvictionChannel

type EvictionChannel struct {
	Key   string
	Value interface{}
}

type LFUCache

type LFUCache struct {
	EvictionChannel chan EvictionChannel //this channel is to send evictedInformation, if there is a listener
	// contains filtered or unexported fields
}

LFUCache - LFU Cache

func NewLFUCache

func NewLFUCache(capacity int) *LFUCache

func (*LFUCache) Evict

func (c *LFUCache) Evict(count int) int

func (*LFUCache) Get

func (c *LFUCache) Get(key string) interface{}

func (*LFUCache) Len

func (c *LFUCache) Len() int

func (*LFUCache) RemoveEntry

func (c *LFUCache) RemoveEntry(currentNode *list.Element, e *CacheEntry)

func (*LFUCache) Set

func (c *LFUCache) Set(key string, value interface{})

type ListEntry

type ListEntry struct {
	// contains filtered or unexported fields
}

ListEntry - This is what each node of DLL Contains