lru

README

lru

Package lru implements generic least-recently-used caches with near O(1) perf.

LRU Cache

A least-recently-used (LRU) cache is a cache that holds a limited number of items with an eviction policy such that when the capacity of the cache is exceeded, the least-recently-used item is automatically removed when inserting a new item. The meaning of used in this implementation is either accessing the item via a lookup or adding the item into the cache, including when the item already exists.

External Use

This package has intentionally been designed so it can be used as a standalone package for any projects needing to make use of well-tested and concurrent safe least-recently-used caches with near O(1) performance characteristics for lookups, inserts, and deletions.

Installation and Updating

This package is part of the github.com/decred/dcrd/lru module. Use the standard go tooling for working with modules to incorporate it.

Examples

• Basic Cache Usage Demonstrates creating a new cache instance, inserting items into the cache, causing an eviction of the least-recently-used item, and removing an item.

• Basic KV Cache Usage Demonstrates creating a new k/v cache instance, inserting items into the cache, causing an eviction of the least-recently-used item, and removing an item.

License

Package lru is licensed under the copyfree ISC License.

Documentation

Overview

Package lru implements generic least-recently-used caches with near O(1) perf.

LRU Cache

A least-recently-used (LRU) cache is a cache that holds a limited number of items with an eviction policy such that when the capacity of the cache is exceeded, the least-recently-used item is automatically removed when inserting a new item. The meaning of used in this implementation is either accessing the item via a lookup or adding the item into the cache, including when the item already exists.

External Use

This package has intentionally been designed so it can be used as a standalone package for any projects needing to make use of a well-test least-recently-used cache with near O(1) performance characteristics for lookups, inserts, and deletions.

Example (BasicKVUsage)

This example demonstrates creating a new kv cache instance, inserting items into the cache, causing an eviction of the least-recently-used item, and removing an item.

package main

import (
	"fmt"

	"github.com/decred/dcrd/lru"
)

func main() {
	// Create a new cache instance with the desired limit.
	const maxItems = 100
	cache := lru.NewKVCache(maxItems)

	// Insert items into the cache.
	for i := 0; i < maxItems; i++ {
		cache.Add(i, i)
	}

	// At this point, the cache has reached the limit, so the first entry will
	// still be a member of the cache.
	if !cache.Contains(0) {
		fmt.Println("cache does not contain expected item 0")
		return
	}

	// Adding another item will evict the least-recently-used item, which will
	// be the value 1 since 0 was just accessed above.
	oneOverMax := int(maxItems) + 1
	cache.Add(oneOverMax, oneOverMax)
	if cache.Contains(1) {
		fmt.Println("cache contains unexpected item 1")
		return
	}

	// Remove an item from the cache.
	cache.Delete(3)
	if cache.Contains(3) {
		fmt.Println("cache contains unexpected item 3")
		return
	}

}

Example (BasicUsage)

This example demonstrates creating a new cache instance, inserting items into the cache, causing an eviction of the least-recently-used item, and removing an item.

package main

import (
	"fmt"

	"github.com/decred/dcrd/lru"
)

func main() {
	// Create a new cache instance with the desired limit.
	const maxItems = 100
	cache := lru.NewCache(maxItems)

	// Insert items into the cache.
	for i := 0; i < maxItems; i++ {
		cache.Add(i)
	}

	// At this point, the cache has reached the limit, so the first entry will
	// still be a member of the cache.
	if !cache.Contains(0) {
		fmt.Println("cache does not contain expected item 0")
		return
	}

	// Adding another item will evict the least-recently-used item, which will
	// be the value 1 since 0 was just accessed above.
	cache.Add(int(maxItems) + 1)
	if cache.Contains(1) {
		fmt.Println("cache contains unexpected item 1")
		return
	}

	// Remove an item from the cache.
	cache.Delete(3)
	if cache.Contains(3) {
		fmt.Println("cache contains unexpected item 3")
		return
	}

}

Index

• type Cache
  • func NewCache(limit uint) Cache
  • func (m *Cache) Add(item interface{})
  • func (m *Cache) Contains(item interface{}) bool
  • func (m *Cache) Delete(item interface{})
• type KVCache
  • func NewKVCache(limit uint) KVCache
  • func (m *KVCache) Add(key interface{}, value interface{})
  • func (m *KVCache) Contains(key interface{}) bool
  • func (m *KVCache) Delete(key interface{})
  • func (m *KVCache) Lookup(key interface{}) (interface{}, bool)

Examples

• Package (BasicKVUsage)
• Package (BasicUsage)

Types

type Cache

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

Cache provides a concurrency safe least-recently-used cache with nearly O(1) lookups, inserts, and deletions. The cache is limited to a maximum number of items with eviction for the oldest entry when the limit is exceeded.

The NewCache function must be used to create a usable cache since the zero value of this struct is not valid.

func NewCache

func NewCache(limit uint) Cache

NewCache returns an initialized and empty LRU cache. See the documentation for Cache for more details.

func (*Cache) Add

func (m *Cache) Add(item interface{})

Add adds the passed item to the cache and handles eviction of the oldest item if adding the new item would exceed the max limit. Adding an existing item makes it the most recently used item.

This function is safe for concurrent access.

func (*Cache) Contains

func (m *Cache) Contains(item interface{}) bool

Contains returns whether or not the passed item is a member of the cache.

This function is safe for concurrent access.

func (*Cache) Delete

func (m *Cache) Delete(item interface{})

Delete deletes the passed item from the cache (if it exists).

This function is safe for concurrent access.

type KVCache

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

KVCache provides a concurrency safe least-recently-used key/value cache with nearly O(1) lookups, inserts, and deletions. The cache is limited to a maximum number of items with eviction for the oldest entry when the limit is exceeded.

The NewKVCache function must be used to create a usable cache since the zero value of this struct is not valid.

func NewKVCache

func NewKVCache(limit uint) KVCache

NewKVCache returns an initialized and empty KV LRU cache. See the documentation for KV for more details.

func (*KVCache) Add

func (m *KVCache) Add(key interface{}, value interface{})

Add adds the passed k/v to the cache and handles eviction of the oldest pair if adding the new pair would exceed the max limit. Adding an existing pair makes it the most recently used item.

This function is safe for concurrent access.

func (*KVCache) Contains

func (m *KVCache) Contains(key interface{}) bool

Contains returns whether or not the passed key is a member of the cache. The associated item of the passed key if it exists becomes the most recently used item.

This function is safe for concurrent access.

func (*KVCache) Delete

func (m *KVCache) Delete(key interface{})

Delete deletes the k/v associated with passed key from the cache (if it exists).

This function is safe for concurrent access.

func (*KVCache) Lookup

func (m *KVCache) Lookup(key interface{}) (interface{}, bool)

Lookup returns the associated value of the passed key, if it is a member of the cache. Looking up an existing item makes it the most recently used item.

This function is safe for concurrent access.