Skip to content

A simple thread-safe and fixed size LRU. Based on the Hashlru Algorithm 🔃

License

Notifications You must be signed in to change notification settings

saurabh0719/go-hashlru

Repository files navigation

go-hashlru

A simple thread-safe, fixed size LRU written in Go. Based on dominictarr's Hashlru Algorithm. 🔃

Uses map[interface{}]interface{} to allow kv pairs of any type. The hlru package contains all the necessary functions.


cache, _ := hlru.NewHLRU(100)

cache.Set("key", "value")

val, _ := cache.Get("key")

fmt.Println(val)
// value

Visit example/example.go in the root directory for a simple example.


Table of Contents :

Installation

$ go get github.com/saurabh0719/go-hashlru

Latest - v0.1.0


API Reference

HashLRU Struct

type HashLRU struct {
	maxSize            int
	size               int
	oldCache, newCache map[interface{}]interface{}
	onEvictedCB        func(key, value interface{})
	lock               sync.RWMutex
}

The HashLRU algorithm maintains two separate maps and bulk eviction happens only after both the maps fill up. Hence onEvictedCB is triggered in bulk and is not an accurate measure of timely LRU-ness.

As explained by dominictarr :

  • This algorithm does not give you an ordered list of the N most recently used items, but has the important properties of the LRU (bounded memory use and O(1) time complexity)

This implementation uses sync.RWMutex to ensure thread-safety.

Go back to the table of contents

func NewHLRU

func NewHLRU(maxSize int) (*HashLRU, error)

Returns a new instance of HashLRU of the given size: maxSize.

func NewWithEvict

func NewWithEvict(maxSize int, onEvict func(key, value interface{})) (*HashLRU, error)

Takes maxSzie and a callback function onEvict as arguments and returns a new instance of HashLRU of the given size.

func (lru *HashLRU) Set

func (lru *HashLRU) Set(key, value interface{})

Adds a new key-value pair to the cache and updates it.

func (lru *HashLRU) Get

func (lru *HashLRU) Get(key interface{}) (interface{}, bool)

Get the value of any key and updates the cache. Returns value, true if the kv pair is found, else returns nil, false.

func (lru *HashLRU) Has

func (lru *HashLRU) Has(key interface{}) bool

Returns true if the key exists, else returns false.

func (lru *HashLRU) Remove

func (lru *HashLRU) Remove(key interface{}) bool

Deletes the key-value pair and returns true if its successful, else returns false.

Go back to the table of contents

func (lru *HashLRU) Peek

func (lru *LRU) Peek(key interface{}) (interface{}, bool)

Get the value of a key without updating the cache. Returns value, true if the kv pair is found, else returns nil, false.

func (lru *HashLRU) Clear

func (lru *HashLRU) Clear()

Empties the Cache.

func (lru *HashLRU) Resize

func (lru *HashLRU) Resize(newSize int) (int, error)

Update the maxSize of the cache. Items will be evicted automatically to adjust. Returns the number of evicted key-value pairs due to the re-size.

func (lru *HashLRU) Len

func (lru *HashLRU) Len() int

Returns the total number of key-value pairs present in the cache.

func (lru *HashLRU) Keys

func (lru* HashLRU) Keys() []interface{}

Returns a slice of all the Keys in the cache.

func (lru *HashLRU) Vals

func (lru *HashLRU) Vals() []interface{}

Returns a slice of all the Values in the cache.

Go back to the table of contents


Tests

$ go test 

Use -v for an detailed output.


Benchmark

$ go test -run=XXX -bench=.

HashLRU has a better hit/miss ratio for BenchmarkHLRU_Rand and BenchmarkHLRU_Freq (negligible) as compared to same benchmark tests from golang-lru. However, golang-lru does have a slightly lower ns/op.

Go back to the table of contents


About

A simple thread-safe and fixed size LRU. Based on the Hashlru Algorithm 🔃

Topics

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages