lru

package
v0.4.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Dec 10, 2015 License: MPL-2.0, MPL-2.0 Imports: 3 Imported by: 0

README

golang-lru

This provides the lru package which implements a fixed-size thread safe LRU cache. It is based on the cache in Groupcache.

Documentation

Full docs are available on Godoc

Example

Using the LRU is very simple:

l, _ := New(128)
for i := 0; i < 256; i++ {
    l.Add(i, nil)
}
if l.Len() != 128 {
    panic(fmt.Sprintf("bad len: %v", l.Len()))
}

Documentation

Overview

This package provides a simple LRU cache. It is based on the LRU implementation in groupcache: https://github.com/golang/groupcache/tree/master/lru

Index

Constants

View Source
const (
	// Default2QRecentRatio is the ratio of the 2Q cache dedicated
	// to recently added entries that have only been accessed once.
	Default2QRecentRatio = 0.25

	// Default2QGhostEntries is the default ratio of ghost
	// entries kept to track entries recently evicted
	Default2QGhostEntries = 0.50
)

Variables

This section is empty.

Functions

This section is empty.

Types

type ARCCache added in v0.4.0

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

ARCCache is a thread-safe fixed size Adaptive Replacement Cache (ARC). ARC is an enhancement over the standard LRU cache in that tracks both frequency and recency of use. This avoids a burst in access to new entries from evicting the frequently used older entries. It adds some additional tracking overhead to a standard LRU cache, computationally it is roughly 2x the cost, and the extra memory overhead is linear with the size of the cache. ARC has been patented by IBM, but is similar to the TwoQueueCache (2Q) which requires setting parameters.

func NewARC added in v0.4.0

func NewARC(size int) (*ARCCache, error)

NewARC creates an ARC of the given size

func (*ARCCache) Add added in v0.4.0

func (c *ARCCache) Add(key, value interface{})

Add adds a value to the cache.

func (*ARCCache) Contains added in v0.4.0

func (c *ARCCache) Contains(key interface{}) bool

Contains is used to check if the cache contains a key without updating recency or frequency.

func (*ARCCache) Get added in v0.4.0

func (c *ARCCache) Get(key interface{}) (interface{}, bool)

Get looks up a key's value from the cache.

func (*ARCCache) Keys added in v0.4.0

func (c *ARCCache) Keys() []interface{}

Keys returns all the cached keys

func (*ARCCache) Len added in v0.4.0

func (c *ARCCache) Len() int

Len returns the number of cached entries

func (*ARCCache) Peek added in v0.4.0

func (c *ARCCache) Peek(key interface{}) (interface{}, bool)

Peek is used to inspect the cache value of a key without updating recency or frequency.

func (*ARCCache) Purge added in v0.4.0

func (c *ARCCache) Purge()

Purge is used to clear the cache

func (*ARCCache) Remove added in v0.4.0

func (c *ARCCache) Remove(key interface{})

Remove is used to purge a key from the cache

type Cache

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

Cache is a thread-safe fixed size LRU cache.

func New

func New(size int) (*Cache, error)

New creates an LRU of the given size

func NewWithEvict

func NewWithEvict(size int, onEvicted func(key interface{}, value interface{})) (*Cache, error)

NewWithEvict constructs a fixed size cache with the given eviction callback.

func (*Cache) Add

func (c *Cache) Add(key, value interface{}) bool

Add adds a value to the cache. Returns true if an eviction occured.

func (*Cache) Contains added in v0.2.0

func (c *Cache) Contains(key interface{}) bool

Check if a key is in the cache, without updating the recent-ness or deleting it for being stale.

func (*Cache) ContainsOrAdd added in v0.3.0

func (c *Cache) ContainsOrAdd(key, value interface{}) (ok, evict bool)

ContainsOrAdd checks if a key is in the cache without updating the recent-ness or deleting it for being stale, and if not, adds the value. Returns whether found and whether an eviction occurred.

func (*Cache) Get

func (c *Cache) Get(key interface{}) (interface{}, bool)

Get looks up a key's value from the cache.

func (*Cache) Keys

func (c *Cache) Keys() []interface{}

Keys returns a slice of the keys in the cache, from oldest to newest.

func (*Cache) Len

func (c *Cache) Len() int

Len returns the number of items in the cache.

func (*Cache) Peek added in v0.2.0

func (c *Cache) Peek(key interface{}) (interface{}, bool)

Returns the key value (or undefined if not found) without updating the "recently used"-ness of the key.

func (*Cache) Purge

func (c *Cache) Purge()

Purge is used to completely clear the cache

func (*Cache) Remove

func (c *Cache) Remove(key interface{})

Remove removes the provided key from the cache.

func (*Cache) RemoveOldest

func (c *Cache) RemoveOldest()

RemoveOldest removes the oldest item from the cache.

type TwoQueueCache added in v0.4.0

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

TwoQueueCache is a thread-safe fixed size 2Q cache. 2Q is an enhancement over the standard LRU cache in that it tracks both frequently and recently used entries seperately. This avoids a burst in access to new entries from evicting frequently used entries. It adds some additional tracking overhead to the standard LRU cache, and is computationally about 2x the cost, and adds some metadata over head. The ARCCache is similar, but does not require setting any parameters.

func New2Q added in v0.4.0

func New2Q(size int) (*TwoQueueCache, error)

New2Q creates a new TwoQueueCache using the default values for the parameters.

func New2QParams added in v0.4.0

func New2QParams(size int, recentRatio float64, ghostRatio float64) (*TwoQueueCache, error)

New2QParams creates a new TwoQueueCache using the provided parameter values.

func (*TwoQueueCache) Add added in v0.4.0

func (c *TwoQueueCache) Add(key, value interface{})

func (*TwoQueueCache) Contains added in v0.4.0

func (c *TwoQueueCache) Contains(key interface{}) bool

func (*TwoQueueCache) Get added in v0.4.0

func (c *TwoQueueCache) Get(key interface{}) (interface{}, bool)

func (*TwoQueueCache) Keys added in v0.4.0

func (c *TwoQueueCache) Keys() []interface{}

func (*TwoQueueCache) Len added in v0.4.0

func (c *TwoQueueCache) Len() int

func (*TwoQueueCache) Peek added in v0.4.0

func (c *TwoQueueCache) Peek(key interface{}) (interface{}, bool)

func (*TwoQueueCache) Purge added in v0.4.0

func (c *TwoQueueCache) Purge()

func (*TwoQueueCache) Remove added in v0.4.0

func (c *TwoQueueCache) Remove(key interface{})

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL