cache

Documentation

Index

• type Config
• type Entry
  • func (e *Entry) Compare(b llrb.Comparable) int
  • func (e *Entry) ID() uintptr
  • func (e *Entry) Range() interval.Range
  • func (e Entry) String() string
• type EvictionPolicy
• type IntervalCache
  • func NewIntervalCache(config Config) *IntervalCache
  • func (bc *IntervalCache) Add(key, value interface{})
  • func (bc *IntervalCache) AddEntry(entry *Entry)
  • func (bc *IntervalCache) AddEntryAfter(entry, after *Entry)
  • func (bc *IntervalCache) Clear()
  • func (bc *IntervalCache) Del(key interface{})
  • func (bc *IntervalCache) DelEntry(entry *Entry)
  • func (bc *IntervalCache) Get(key interface{}) (value interface{}, ok bool)
  • func (ic *IntervalCache) GetOverlaps(start, end []byte) []*Entry
  • func (bc *IntervalCache) Len() int
  • func (ic *IntervalCache) MakeKey(start, end []byte) IntervalKey
  • func (bc *IntervalCache) MoveToEnd(entry *Entry)
  • func (ic *IntervalCache) NewKey(start, end []byte) *IntervalKey
• type IntervalKey
  • func (ik IntervalKey) String() string
• type OrderedCache
  • func NewOrderedCache(config Config) *OrderedCache
  • func (bc *OrderedCache) Add(key, value interface{})
  • func (bc *OrderedCache) AddEntry(entry *Entry)
  • func (bc *OrderedCache) AddEntryAfter(entry, after *Entry)
  • func (oc *OrderedCache) Ceil(key interface{}) (interface{}, interface{}, bool)
  • func (oc *OrderedCache) CeilEntry(key interface{}) (*Entry, bool)
  • func (bc *OrderedCache) Clear()
  • func (bc *OrderedCache) Del(key interface{})
  • func (bc *OrderedCache) DelEntry(entry *Entry)
  • func (oc *OrderedCache) Do(f func(k, v interface{}) bool) bool
  • func (oc *OrderedCache) DoEntry(f func(e *Entry) bool) bool
  • func (oc *OrderedCache) DoRange(f func(k, v interface{}) bool, from, to interface{}) bool
  • func (oc *OrderedCache) DoRangeEntry(f func(e *Entry) bool, from, to interface{}) bool
  • func (oc *OrderedCache) Floor(key interface{}) (interface{}, interface{}, bool)
  • func (oc *OrderedCache) FloorEntry(key interface{}) (*Entry, bool)
  • func (bc *OrderedCache) Get(key interface{}) (value interface{}, ok bool)
  • func (bc *OrderedCache) Len() int
  • func (bc *OrderedCache) MoveToEnd(entry *Entry)
• type UnorderedCache
  • func NewUnorderedCache(config Config) *UnorderedCache
  • func (bc *UnorderedCache) Add(key, value interface{})
  • func (bc *UnorderedCache) AddEntry(entry *Entry)
  • func (bc *UnorderedCache) AddEntryAfter(entry, after *Entry)
  • func (bc *UnorderedCache) Clear()
  • func (bc *UnorderedCache) Del(key interface{})
  • func (bc *UnorderedCache) DelEntry(entry *Entry)
  • func (bc *UnorderedCache) Get(key interface{}) (value interface{}, ok bool)
  • func (bc *UnorderedCache) Len() int
  • func (bc *UnorderedCache) MoveToEnd(entry *Entry)

Types

type Config

type Config struct {
	// Policy is one of the consts listed for EvictionPolicy.
	Policy EvictionPolicy

	// ShouldEvict is a callback function executed each time a new entry
	// is added to the cache. It supplies cache size, and potential
	// evictee's key and value. The function should return true if the
	// entry may be evicted; false otherwise. For example, to support a
	// maximum size for the cache, use a method like:
	//
	//   func(size int, key Key, value interface{}) { return size > maxSize }
	//
	// To support max TTL in the cache, use something like:
	//
	//   func(size int, key Key, value interface{}) {
	//     return timeutil.Now().UnixNano() - value.(int64) > maxTTLNanos
	//   }
	ShouldEvict func(size int, key, value interface{}) bool

	// OnEvicted optionally specifies a callback function to be
	// executed when an entry is purged from the cache.
	OnEvicted func(key, value interface{})

	// OnEvictedEntry optionally specifies a callback function to
	// be executed when an entry is purged from the cache.
	OnEvictedEntry func(entry *Entry)
}

A Config specifies the eviction policy, eviction trigger callback, and eviction listener callback.

type Entry

type Entry struct {
	Key, Value interface{}
	// contains filtered or unexported fields
}

Entry holds the key and value and a pointer to the linked list which defines the eviction ordering.

func (*Entry) Compare

func (e *Entry) Compare(b llrb.Comparable) int

Compare implements the llrb.Comparable interface for cache entries. This facility is used by the OrderedCache, and crucially requires that keys used with that cache implement llrb.Comparable.

func (*Entry) ID

func (e *Entry) ID() uintptr

ID implements interval.Interface

func (*Entry) Range

func (e *Entry) Range() interval.Range

Range implements interval.Interface

func (Entry) String

func (e Entry) String() string

type EvictionPolicy

type EvictionPolicy int

EvictionPolicy is the cache eviction policy enum.

const (
	CacheLRU  EvictionPolicy = iota // Least recently used
	CacheFIFO                       // First in, first out
	CacheNone                       // No evictions; don't maintain ordering list
)

Constants describing LRU and FIFO, and None cache eviction policies respectively.

type IntervalCache

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

IntervalCache is a cache which supports querying of intervals which match a key or range of keys. It is backed by an interval tree. See comments in UnorderedCache for more details on cache functionality.

Note that the IntervalCache allow multiple identical segments, as specified by start and end keys.

Keys supplied to the IntervalCache's Get, Add & Del methods must be constructed from IntervalCache.NewKey().

IntervalCache is not safe for concurrent access.

func NewIntervalCache

func NewIntervalCache(config Config) *IntervalCache

NewIntervalCache creates a new Cache backed by an interval tree. See NewCache() for details on parameters.

func (*IntervalCache) Add

func (bc *IntervalCache) Add(key, value interface{})

Add adds a value to the cache.

func (*IntervalCache) AddEntry

func (bc *IntervalCache) AddEntry(entry *Entry)

AddEntry adds a value to the cache. It provides an alternative interface to Add which the caller can use to reduce allocations by bundling the Entry structure with the key and value to be stored.

func (*IntervalCache) AddEntryAfter

func (bc *IntervalCache) AddEntryAfter(entry, after *Entry)

AddEntryAfter adds a value to the cache, making sure that it is placed after the second entry in the eviction queue. It provides an alternative interface to Add which the caller can use to reduce allocations by bundling the Entry structure with the key and value to be stored.

func (*IntervalCache) Clear

func (bc *IntervalCache) Clear()

Clear clears all entries from the cache.

func (*IntervalCache) Del

func (bc *IntervalCache) Del(key interface{})

Del removes the provided key from the cache.

func (*IntervalCache) DelEntry

func (bc *IntervalCache) DelEntry(entry *Entry)

DelEntry removes the provided entry from the cache.

func (*IntervalCache) Get

func (bc *IntervalCache) Get(key interface{}) (value interface{}, ok bool)

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

func (*IntervalCache) GetOverlaps

func (ic *IntervalCache) GetOverlaps(start, end []byte) []*Entry

GetOverlaps returns a slice of values which overlap the specified interval. The slice is only valid until the next call to GetOverlaps.

func (*IntervalCache) Len

func (bc *IntervalCache) Len() int

Len returns the number of items in the cache.

func (*IntervalCache) MakeKey

func (ic *IntervalCache) MakeKey(start, end []byte) IntervalKey

MakeKey creates a new interval key defined by start and end values.

func (*IntervalCache) MoveToEnd

func (bc *IntervalCache) MoveToEnd(entry *Entry)

MoveToEnd moves the entry to the end of the eviction queue.

func (*IntervalCache) NewKey

func (ic *IntervalCache) NewKey(start, end []byte) *IntervalKey

NewKey creates a new interval key defined by start and end values.

type IntervalKey

type IntervalKey struct {
	interval.Range
	// contains filtered or unexported fields
}

IntervalKey provides uniqueness as well as key interval.

func (IntervalKey) String

func (ik IntervalKey) String() string

type OrderedCache

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

OrderedCache is a cache which supports binary searches using Ceil and Floor methods. It is backed by a left-leaning red black tree. See comments in UnorderedCache for more details on cache functionality.

OrderedCache requires that keys implement llrb.Comparable.

OrderedCache is not safe for concurrent access.

func NewOrderedCache

func NewOrderedCache(config Config) *OrderedCache

NewOrderedCache creates a new Cache backed by a left-leaning red black binary tree which supports binary searches via the Ceil() and Floor() methods. See NewUnorderedCache() for details on parameters.

func (*OrderedCache) Add

func (bc *OrderedCache) Add(key, value interface{})

Add adds a value to the cache.

func (*OrderedCache) AddEntry

func (bc *OrderedCache) AddEntry(entry *Entry)

AddEntry adds a value to the cache. It provides an alternative interface to Add which the caller can use to reduce allocations by bundling the Entry structure with the key and value to be stored.

func (*OrderedCache) AddEntryAfter

func (bc *OrderedCache) AddEntryAfter(entry, after *Entry)

AddEntryAfter adds a value to the cache, making sure that it is placed after the second entry in the eviction queue. It provides an alternative interface to Add which the caller can use to reduce allocations by bundling the Entry structure with the key and value to be stored.

func (*OrderedCache) Ceil

func (oc *OrderedCache) Ceil(key interface{}) (interface{}, interface{}, bool)

Ceil returns the smallest key-value pair greater than or equal to key.

func (*OrderedCache) CeilEntry

func (oc *OrderedCache) CeilEntry(key interface{}) (*Entry, bool)

CeilEntry returns the smallest cache entry greater than or equal to key.

func (*OrderedCache) Clear

func (bc *OrderedCache) Clear()

Clear clears all entries from the cache.

func (*OrderedCache) Del

func (bc *OrderedCache) Del(key interface{})

Del removes the provided key from the cache.

func (*OrderedCache) DelEntry

func (bc *OrderedCache) DelEntry(entry *Entry)

DelEntry removes the provided entry from the cache.

func (*OrderedCache) Do

func (oc *OrderedCache) Do(f func(k, v interface{}) bool) bool

Do invokes f on all key-value pairs in the cache. f returns a boolean indicating the traversal is done. If f returns true, the Do loop will exit; false, it will continue. Do returns whether the iteration exited early.

func (*OrderedCache) DoEntry

func (oc *OrderedCache) DoEntry(f func(e *Entry) bool) bool

DoEntry invokes f on all cache entries in the cache. f returns a boolean indicating the traversal is done. If f returns true, the DoEntry loop will exit; false, it will continue. DoEntry returns whether the iteration exited early.

func (*OrderedCache) DoRange

func (oc *OrderedCache) DoRange(f func(k, v interface{}) bool, from, to interface{}) bool

DoRange invokes f on all key-value pairs in the range of from -> to. f returns a boolean indicating the traversal is done. If f returns true, the DoRange loop will exit; false, it will continue. DoRange returns whether the iteration exited early.

func (*OrderedCache) DoRangeEntry

func (oc *OrderedCache) DoRangeEntry(f func(e *Entry) bool, from, to interface{}) bool

DoRangeEntry invokes f on all cache entries in the range of from -> to. f returns a boolean indicating the traversal is done. If f returns true, the DoRangeEntry loop will exit; false, it will continue. DoRangeEntry returns whether the iteration exited early.

func (*OrderedCache) Floor

func (oc *OrderedCache) Floor(key interface{}) (interface{}, interface{}, bool)

Floor returns the greatest key-value pair less than or equal to key.

func (*OrderedCache) FloorEntry

func (oc *OrderedCache) FloorEntry(key interface{}) (*Entry, bool)

FloorEntry returns the greatest cache entry less than or equal to key.

func (*OrderedCache) Get

func (bc *OrderedCache) Get(key interface{}) (value interface{}, ok bool)

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

func (*OrderedCache) Len

func (bc *OrderedCache) Len() int

Len returns the number of items in the cache.

func (*OrderedCache) MoveToEnd

func (bc *OrderedCache) MoveToEnd(entry *Entry)

MoveToEnd moves the entry to the end of the eviction queue.

type UnorderedCache

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

UnorderedCache is a cache which supports custom eviction triggers and two eviction policies: LRU and FIFO. A listener pattern is available for eviction events. This cache uses a hashmap for storing elements, making it the most performant. Only exact lookups are supported.

UnorderedCache requires that keys are comparable, according to the go specification (http://golang.org/ref/spec#Comparison_operators).

UnorderedCache is not safe for concurrent access.

func NewUnorderedCache

func NewUnorderedCache(config Config) *UnorderedCache

NewUnorderedCache creates a new UnorderedCache backed by a hash map.

func (*UnorderedCache) Add

func (bc *UnorderedCache) Add(key, value interface{})

Add adds a value to the cache.

func (*UnorderedCache) AddEntry

func (bc *UnorderedCache) AddEntry(entry *Entry)

AddEntry adds a value to the cache. It provides an alternative interface to Add which the caller can use to reduce allocations by bundling the Entry structure with the key and value to be stored.

func (*UnorderedCache) AddEntryAfter

func (bc *UnorderedCache) AddEntryAfter(entry, after *Entry)

AddEntryAfter adds a value to the cache, making sure that it is placed after the second entry in the eviction queue. It provides an alternative interface to Add which the caller can use to reduce allocations by bundling the Entry structure with the key and value to be stored.

func (*UnorderedCache) Clear

func (bc *UnorderedCache) Clear()

Clear clears all entries from the cache.

func (*UnorderedCache) Del

func (bc *UnorderedCache) Del(key interface{})

Del removes the provided key from the cache.

func (*UnorderedCache) DelEntry

func (bc *UnorderedCache) DelEntry(entry *Entry)

DelEntry removes the provided entry from the cache.

func (*UnorderedCache) Get

func (bc *UnorderedCache) Get(key interface{}) (value interface{}, ok bool)

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

func (*UnorderedCache) Len

func (bc *UnorderedCache) Len() int

Len returns the number of items in the cache.

func (*UnorderedCache) MoveToEnd

func (bc *UnorderedCache) MoveToEnd(entry *Entry)

MoveToEnd moves the entry to the end of the eviction queue.