README
¶
DEPRECATION WARNING This package is unmaintained and probably not what you're looking for.
lfucache 
import "github.com/calmh/lfucache"
Package lfucache implements an O(1) LFU cache structure.
This structure is described in the paper "An O(1) algorithm for implementing the LFU cache eviction scheme" by K. Shah, A. Mitra and D. Matani.
It is based on two levels of doubly linked lists and gives O(1) insert, access and delete operations. The cache supports sending evicted items to interested listeners via channels, and manually evicting all cache items matching a criteria. This is useful for example when using the package as a write cache for a database, where items must be written to the backing store on eviction.
The cache structure is not thread safe.
Example
c := lfucache.Create(1024) // The cache will hold up to 1024 items.
c.Access("mykey") // => nil, false
c.Insert("mykey", 2345) // => true
v, ok := c.Access("mykey") // => v = interface{}{2345}, ok = true
c.Delete("mykey") // => true
Documentation
http://godoc.org/github.com/calmh/lfucache
License
MIT
Documentation
¶
Overview ¶
Package lfucache implements an O(1) LFU (Least Frequenty Used) cache.
**DEPRECATION WARNING**
This package is unmaintained and probably not what you're looking for.
This structure is described in the paper "An O(1) algorithm for implementing the LFU cache eviction scheme" by K. Shah, A. Mitra and D. Matani. It is based on two levels of doubly linked lists and gives O(1) insert, access and delete operations. It is implemented here with a few practical optimizations and extra features.
The cache supports sending evicted items to interested listeners via channels, and manually evicting cache items matching a certain criteria. This is useful for example when using the package as a write cache for a database, where items must be written to the backing store on eviction.
The cache structure is not thread safe.
Example:
c := lfucache.Create(1024) // The cache will hold up to 1024 items.
c.Access("mykey") // => nil, false
c.Insert("mykey", 2345) // => true
v, ok := c.Access("mykey") // => v = interface{}{2345}, ok = true
c.Delete("mykey") // => true
---
Copyright (c) 2013 Jakob Borg. Licensed under the MIT license.
Index ¶
- type Cache
- func (c *Cache) Access(key interface{}) (interface{}, bool)
- func (c *Cache) Cap() int
- func (c *Cache) Delete(key interface{}) bool
- func (c *Cache) EvictIf(test func(interface{}) bool) int
- func (c *Cache) Evictions(e chan<- interface{})
- func (c *Cache) Insert(key interface{}, value interface{})
- func (c *Cache) Len() int
- func (c *Cache) Resize(capacity int)
- func (c *Cache) Statistics() Statistics
- func (c *Cache) UnregisterEvictions(e chan<- interface{})
- type Statistics
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Cache ¶
type Cache struct {
// contains filtered or unexported fields
}
Cache is an LFU cache structure.
func (*Cache) Access ¶
Access an item in the cache. Returns "value, ok" similar to map indexing. Increases the item's use count.
func (*Cache) Delete ¶
Delete deletes an item from the cache and returns true. Does nothing and returns false if the key was not present in the cache.
func (*Cache) EvictIf ¶
EvictIf applies test to each item in the cache and evicts it if the test returns true. Returns the number of items that were evicted.
func (*Cache) Evictions ¶
func (c *Cache) Evictions(e chan<- interface{})
Evictions registers a channel used to report items that get evicted from the cache. Only items evicted due to LFU or EvictIf() will be sent on the channel, not items removed by calling Delete(). The channel must be unregistered using UnregisterEvictions() prior to ceasing reads in order to avoid deadlocking evictions.
func (*Cache) Insert ¶
func (c *Cache) Insert(key interface{}, value interface{})
Insert inserts an item into the cache. If the key already exists, the existing item is evicted and the new one inserted. The key type is restricted to those acceptable as map keys (http://golang.org/ref/spec#Map_types).
func (*Cache) Statistics ¶
func (c *Cache) Statistics() Statistics
Statistics returns the cache statistics.
func (*Cache) UnregisterEvictions ¶
func (c *Cache) UnregisterEvictions(e chan<- interface{})
UnregisterEvictions removes the channel from the list of channels to be notified on item eviction. Must be called when there is no longer a reader for the channel in question.
type Statistics ¶
type Statistics struct {
LenFreq0 int // Number of items at frequency zero, i.e Inserted but not Accessed
Inserts int // Number of Insert()s
Hits int // Number of hits (Access() to item)
Misses int // Number of misses (Access() to non-existant key)
Evictions int // Number of evictions (due to size constraints on Insert(), or EvictIf() calls)
Deletes int // Number of Delete()s.
FreqListLen int // Current length of frequency list, i.e. the number of distinct usage levels
}
Statistics contains current item counts and operation counters.
Source Files