cockroach: github.com/cockroachdb/cockroach/pkg/util/cache Index | Files

package cache

import "github.com/cockroachdb/cockroach/pkg/util/cache"

Index

Package Files

cache.go

type Config Uses

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 Uses

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 Uses

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 Uses

func (e *Entry) ID() uintptr

ID implements interval.Interface

func (*Entry) Range Uses

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

Range implements interval.Interface

func (Entry) String Uses

func (e Entry) String() string

type EvictionPolicy Uses

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 Uses

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 Uses

func NewIntervalCache(config Config) *IntervalCache

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

func (*IntervalCache) Add Uses

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

Add adds a value to the cache.

func (*IntervalCache) AddEntry Uses

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 Uses

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 Uses

func (bc *IntervalCache) Clear()

Clear clears all entries from the cache.

func (*IntervalCache) Del Uses

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

Del removes the provided key from the cache.

func (*IntervalCache) DelEntry Uses

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

DelEntry removes the provided entry from the cache.

func (*IntervalCache) Get Uses

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

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

func (*IntervalCache) GetOverlaps Uses

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 Uses

func (bc *IntervalCache) Len() int

Len returns the number of items in the cache.

func (*IntervalCache) MakeKey Uses

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

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

func (*IntervalCache) MoveToEnd Uses

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

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

func (*IntervalCache) NewKey Uses

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

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

type IntervalKey Uses

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

IntervalKey provides uniqueness as well as key interval.

func (IntervalKey) String Uses

func (ik IntervalKey) String() string

type OrderedCache Uses

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 Uses

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 Uses

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

Add adds a value to the cache.

func (*OrderedCache) AddEntry Uses

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 Uses

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 Uses

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 Uses

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

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

func (*OrderedCache) Clear Uses

func (bc *OrderedCache) Clear()

Clear clears all entries from the cache.

func (*OrderedCache) Del Uses

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

Del removes the provided key from the cache.

func (*OrderedCache) DelEntry Uses

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

DelEntry removes the provided entry from the cache.

func (*OrderedCache) Do Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

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

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

func (*OrderedCache) Get Uses

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

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

func (*OrderedCache) Len Uses

func (bc *OrderedCache) Len() int

Len returns the number of items in the cache.

func (*OrderedCache) MoveToEnd Uses

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

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

type UnorderedCache Uses

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 Uses

func NewUnorderedCache(config Config) *UnorderedCache

NewUnorderedCache creates a new UnorderedCache backed by a hash map.

func (*UnorderedCache) Add Uses

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

Add adds a value to the cache.

func (*UnorderedCache) AddEntry Uses

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 Uses

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 Uses

func (bc *UnorderedCache) Clear()

Clear clears all entries from the cache.

func (*UnorderedCache) Del Uses

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

Del removes the provided key from the cache.

func (*UnorderedCache) DelEntry Uses

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

DelEntry removes the provided entry from the cache.

func (*UnorderedCache) Get Uses

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

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

func (*UnorderedCache) Len Uses

func (bc *UnorderedCache) Len() int

Len returns the number of items in the cache.

func (*UnorderedCache) MoveToEnd Uses

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

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

Package cache imports 7 packages (graph) and is imported by 43 packages. Updated 2019-07-17. Refresh now. Tools for package owners.