cache

package
v2.1.2+incompatible Latest Latest
Warning

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

 Go to latest Published: Mar 5, 2019 License: Apache-2.0 Imports: 7 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	TD234 = iota
	BU23
)

Operation LLRBMode of the underlying LLRB tree.

View Source 
const LLRBMode = BU23

LLRBMode .

Variables

View Source 
var ErrEmptyRange = errors.New("interval: empty range")

ErrEmptyRange is returned if an interval is used where the start value is equal to the end value.

View Source 
var ErrInvertedRange = errors.New("interval: inverted range")

ErrInvertedRange is returned if an interval is used where the start value is greater than the end value.

View Source 
var ExclusiveOverlapper = exclusiveOverlapper{}

ExclusiveOverlapper defines overlapping as a pair of ranges that share a segment of the keyspace in the exclusive. "exclusive" means that the start keys are treated as inclusive and the end keys are treated as exclusive.

View Source 
var InclusiveOverlapper = inclusiveOverlapper{}

InclusiveOverlapper defines overlapping as a pair of ranges that share a segment of the keyspace in the inclusive way. "inclusive" means that both start and end keys treated as inclusive values.

Functions

func Compare 

func Compare(a, b Interface) int

Compare returns a value indicating the sort order relationship between a and b. The comparison is performed lexicographically on (a.Range().Start, a.ID()) and (b.Range().Start, b.ID()) tuples where Range().Start is more significant that ID().

Given c = Compare(a, b): 

c == -1  if (a.Range().Start, a.ID()) < (b.Range().Start, b.ID());
c == 0 if (a.Range().Start, a.ID()) == (b.Range().Start, b.ID()); and
c == 1 if (a.Range().Start, a.ID()) > (b.Range().Start, b.ID()).

"c == 0" is equivalent to "Equal(a, b) == true".

func Equal 

func Equal(a, b Interface) bool

Equal returns a boolean indicating whethter the given Interfaces are equal to each other. If "Equal(a, b) == true", "a.Range().End == b.Range().End" must hold. Otherwise, the interval tree behavior is undefined. "Equal(a, b) == true" is equivalent to "Compare(a, b) == 0". But the former has measurably better performance than the latter. So Equal should be used when only equality state is needed.

Types

type Comparable 

type Comparable []byte

A Comparable is a type that describes the ends of a Range.

func (Comparable) Compare 

func (c Comparable) Compare(o Comparable) int

Compare returns a value indicating the sort order relationship between the receiver and the parameter.

Given c = a.Compare(b): 

c == -1 if a < b;
c == 0 if a == b; and
c == 1 if a > b.

func (Comparable) Equal 

func (c Comparable) Equal(o Comparable) bool

Equal returns a boolean indicating if the given comparables are equal to each other. Note that this has measurably better performance than Compare() == 0, so it should be used when only equality state is needed.

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, entry interface{})
}

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

type Entry 

type Entry struct {
	Alloc      interface{}
	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() Range

Range implements interval.Interface

func (*Entry) Release 

func (e *Entry) Release(pool *sync.Pool)

Release resets the entry object and puts it back to the pool.

func (*Entry) Reset 

func (e *Entry) Reset()

Reset resets the entry object.

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 Interface 

type Interface interface {
	Range() Range
	// Returns a unique ID for the element.
	// TODO(nvanbenschoten): Should this be changed to an int64?
	ID() uintptr
}

An Interface is a type that can be inserted into an interval tree.

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 {
	Range
	// contains filtered or unexported fields
}

IntervalKey provides uniqueness as well as key interval.

func (IntervalKey) String 

func (ik IntervalKey) String() string

type Operation 

type Operation func(Interface) (done bool)

An Operation is a function that operates on an Interface. If done is returned true, the Operation is indicating that no further work needs to be done and so the DoMatching function should traverse no further.

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 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{}))

Do invokes f on all of the entries in the cache.

func (*OrderedCache) DoRange 

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

DoRange 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 DoRange loop will exit; false, it will continue. DoRange returns whether the iteration exited early.

func (*OrderedCache) Floor 

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

Floor 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.

func (*OrderedCache) OrderedDo 

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

OrderedDo invokes func f with all entries in LRU order (the LRU entry first).

type Overlapper 

type Overlapper interface {
	// Overlap checks whether two ranges overlap.
	Overlap(Range, Range) bool
}

Overlapper specifies the overlapping relationship.

type Range 

type Range struct {
	Start, End Comparable
}

A Range is a type that describes the basic characteristics of an interval.

func (Range) Equal 

func (r Range) Equal(other Range) bool

Equal returns whether the two ranges are equal.

func (Range) String 

func (r Range) String() string

String implements the Stringer interface.

type Tree 

type Tree interface {
	// AdjustRanges fixes range fields for all nodes in the tree. This must be
	// called before Get, Do or DoMatching* is used if fast insertion or deletion
	// has been performed.
	AdjustRanges()
	// Len returns the number of intervals stored in the Tree.
	Len() int
	// Get returns a slice of Interfaces that overlap r in the tree. The slice is
	// sorted nondecreasingly by interval start.
	Get(r Range) []Interface
	// GetWithOverlapper returns a slice of Interfaces that overlap r in the tree
	// using the provided overlapper function. The slice is sorted nondecreasingly
	// by interval start.
	GetWithOverlapper(r Range, overlapper Overlapper) []Interface
	// Insert inserts the Interface e into the tree. Insertions may replace an
	// existing Interface which is equal to the Interface e.
	Insert(e Interface, fast bool) error
	// Delete deletes the Interface e if it exists in the tree. The deleted
	// Interface is equal to the Interface e.
	Delete(e Interface, fast bool) error
	// Do performs fn on all intervals stored in the tree. The traversal is done
	// in the nondecreasing order of interval start. A boolean is returned
	// indicating whether the traversal was interrupted by an Operation returning
	// true. If fn alters stored intervals' sort relationships, future tree
	// operation behaviors are undefined.
	Do(fn Operation) bool
	// DoMatching performs fn on all intervals stored in the tree that overlaps r.
	// The traversal is done in the nondecreasing order of interval start. A
	// boolean is returned indicating whether the traversal was interrupted by an
	// Operation returning true. If fn alters stored intervals' sort
	// relationships, future tree operation behaviors are undefined.
	DoMatching(fn Operation, r Range) bool
	// Iterator creates an iterator to iterate over all intervals stored in the
	// tree, in-order.
	Iterator() TreeIterator
}

Tree is an interval tree. For all the functions which have a fast argment, fast being true means a fast operation which does not adjust node ranges. If fast is false, node ranges are adjusted.

func NewTree 

func NewTree(overlapper Overlapper) Tree

NewTree creates a new interval tree with the given overlapper function. It uses the augmented Left-Leaning Red Black tree implementation.

type TreeIterator 

type TreeIterator interface {
	// Next returns the current interval stored in the interval tree	and moves
	// the iterator to the next interval. The method returns false if no intervals
	// remain in the interval tree.
	Next() (Interface, bool)
}

TreeIterator iterates over all intervals stored in the interval tree, in-order.

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.

Source Files

View all Source files

Directories

Path Synopsis
biogo
store/interval
Package interval implements an interval tree based on an augmented Left-Leaning Red Black tree.
 Package interval implements an interval tree based on an augmented Left-Leaning Red Black tree.
store/interval/landscape
Package landscape implements persistence landscape calculation for a set of intervals.
 Package landscape implements persistence landscape calculation for a set of intervals.
store/kdtree
Package kdtree implements a k-d tree.
 Package kdtree implements a k-d tree.
store/llrb
Package llrb implements Left-Leaning Red Black trees as described by Robert Sedgewick.
 Package llrb implements Left-Leaning Red Black trees as described by Robert Sedgewick.
store/step
Package step implements a step vector type.
 Package step implements a step vector type.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.