containers

package
v0.1.0 Latest Latest
Warning

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

 Go to latest Published: Jul 11, 2023 License: Apache-2.0, GPL-2.0, GPL-3.0-or-later, + 1 more Imports: 11 Imported by: 0

Documentation

Overview

Package containers implements generic (type-parameterized) datatype containers.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func LoadOrElse 

func LoadOrElse[K comparable, V any](m Map[K, V], k K, vFn func(K) V) V

func NativeCompare 

func NativeCompare[T constraints.Ordered](a, b T) int

NativeCompare implements the Ordered[T] Compare operation for natively-ordered (integer types, float types, and string types). While this operation be conceptualized as subtration, NativeCompare is careful to avoid integer overflow.

Types

type Cache 

type Cache[K comparable, V any] interface {
	// Acquire loads the value for `k` (possibly from the cache),
	// records that value in to the cache, and increments the
	// cache entry's in-use counter preventing it from being
	// evicted.
	//
	// If the cache is at capacity and all entries are in-use,
	// then Acquire blocks until an entry becomes available (via
	// `Release`).
	Acquire(context.Context, K) *V

	// Release decrements the in-use counter for the cache entry
	// for `k`.  If the in-use counter drops to 0, then that entry
	// may be evicted.
	//
	// It is invalid (runtime-panic) to call Release for an entry
	// that does not have a positive in-use counter.
	Release(K)

	// Delete invalidates/removes an entry from the cache.  Blocks
	// until the in-user counter drops to 0.
	//
	// It is valid to call Delete on an entry that does not exist
	// in the cache.
	Delete(K)

	// Flush does whatever it needs to in order to ensure that if
	// the program exited right now, no one would be upset.  Flush
	// does not empty the cache.
	Flush(context.Context)
}

func NewARCache 

func NewARCache[K comparable, V any](cap int, src Source[K, V]) Cache[K, V]

NewARCache returns a new thread-safe Adaptive Replacement Cache (ARC).

Fundamentally, the point of ARC is to combine both recency information and frequency information together to form a cache policy that is better than both least-recently-used eviction (LRU) or least-frequently-used eviction (LFU); and the balance between how much weight is given to recency vs frequency is "adaptive" based on the characteristics of the current workload.

The Adaptive Replacement Cache is patented by IBM (patent US-6,996,676-B2 is set to expire 2024-02-22).

This implementation does NOT make use of the enhancements in ZFS' enhanced ARC, which are patented by Sun (now Oracle) (patent US-7,469,320-B2 is set to expire 2027-02-13).

This implementation has a few enhancements compared to standard ARC:

  • This implementation supports explicitly deleting/invalidating cache entries; the standard ARC algorithm assumes that the only reason an entry is ever removed from the cache is because the cache is full and the entry had to be evicted to make room for a new entry.

  • This implementation supports pinning entries such that they cannot be evicted. This is one of the enhancement from the enhanced version of ARC used by ZFS, but the version here is not based on the ZFS version.

It is invalid (runtime-panic) to call NewARCache with a non-positive capacity or a nil source.

func NewLRUCache 

func NewLRUCache[K comparable, V any](cap int, src Source[K, V]) Cache[K, V]

NewLRUCache returns a new thread-safe Cache with a simple Least-Recently-Used eviction policy.

It is invalid (runtime-panic) to call NewLRUCache with a non-positive capacity or a nil source.

type Color 

type Color bool
const (
	Black Color = false
	Red   Color = true
)

type IntervalTree 

type IntervalTree[K Ordered[K], V any] struct {
	MinFn func(V) K
	MaxFn func(V) K
	// contains filtered or unexported fields
}

func (*IntervalTree[K, V]) Equal 

func (t *IntervalTree[K, V]) Equal(u *IntervalTree[K, V]) bool

func (*IntervalTree[K, V]) Insert 

func (t *IntervalTree[K, V]) Insert(val V)

func (*IntervalTree[K, V]) Max 

func (t *IntervalTree[K, V]) Max() (K, bool)

func (*IntervalTree[K, V]) Min 

func (t *IntervalTree[K, V]) Min() (K, bool)

func (*IntervalTree[K, V]) Range 

func (t *IntervalTree[K, V]) Range(fn func(V) bool)

func (*IntervalTree[K, V]) Search 

func (t *IntervalTree[K, V]) Search(fn func(K) int) (V, bool)

func (*IntervalTree[K, V]) Subrange 

func (t *IntervalTree[K, V]) Subrange(rangeFn func(K) int, handleFn func(V) bool)

type LinkedList 

type LinkedList[T any] struct {
	Len            int
	Oldest, Newest *LinkedListEntry[T]
}

LinkedList is a doubly-linked list.

Rather than "head/tail", "front/back", or "next/prev", it has "oldest" and "newest". This is for to make code using it clearer; as the motivation for the LinkedList is as an implementation detail in LRU caches and FIFO queues, where this temporal naming is meaningful. Similarly, it does not implement many common features of a linked-list, because these applications do not need such features.

Compared to `containers/list.List`, LinkedList has the disadvantages that it has fewer safety checks and fewer features in general.

func (*LinkedList[T]) Delete 

func (l *LinkedList[T]) Delete(entry *LinkedListEntry[T])

Delete removes an entry from the list. The entry is invalid once Delete returns, and should not be reused or have its .Value accessed.

It is invalid (runtime-panic) to call Delete on a nil entry.

It is invalid (runtime-panic) to call Delete on an entry that isn't in the list.

func (*LinkedList[T]) IsEmpty 

func (l *LinkedList[T]) IsEmpty() bool

IsEmpty returns whether the list empty or not.

func (*LinkedList[T]) MoveToNewest 

func (l *LinkedList[T]) MoveToNewest(entry *LinkedListEntry[T])

MoveToNewest moves an entry fron any position in the list to the "newest" end of the list. If the entry is already in the "newest" position, then MoveToNewest is a no-op.

It is invalid (runtime-panic) to call MoveToNewest on a nil entry.

It is invalid (runtime-panic) to call MoveToNewest on an entry that isn't in the list.

func (*LinkedList[T]) Store 

func (l *LinkedList[T]) Store(entry *LinkedListEntry[T])

Store appends a value to the "newest" end of the list, returning the created entry.

It is invalid (runtime-panic) to call Store on a nil entry.

It is invalid (runtime-panic) to call Store on an entry that is already in a list.

type LinkedListEntry 

type LinkedListEntry[T any] struct {
	List         *LinkedList[T]
	Older, Newer *LinkedListEntry[T]
	Value        T
}

LinkedListEntry [T] is an entry in a LinkedList [T].

type Map 

type Map[K comparable, V any] interface {
	Store(K, V)
	Load(K) (V, bool)
	Has(K) bool
	Delete(K)
	Len() int
}

type NativeOrdered 

type NativeOrdered[T constraints.Ordered] struct {
	Val T
}

NativeOrdered takes a type that is natively-ordered (integer types, float types, and string types), and wraps them such that they implement the Ordered interface.

func (NativeOrdered[T]) Compare 

func (a NativeOrdered[T]) Compare(b NativeOrdered[T]) int

Compare implements Ordered[T].

type Optional 

type Optional[T any] struct {
	OK  bool
	Val T
}

func OptionalNil 

func OptionalNil[T any]() Optional[T]

func OptionalValue 

func OptionalValue[T any](val T) Optional[T]

func (Optional[T]) MarshalJSON 

func (o Optional[T]) MarshalJSON() ([]byte, error)

func (*Optional[T]) UnmarshalJSON 

func (o *Optional[T]) UnmarshalJSON(dat []byte) error

type Ordered 

type Ordered[T _Ordered[T]] _Ordered[T]

An Ordered is a type that has a 

func (a T) Compare(b T) int

method that returns a value <1 if a is "less than" b, >1 if a is "greater than" b, or 0 if a is "equal to" b.

You can conceptualize as subtraction: 

func (a T) Compare(b T) int {
	return a - b
}

Be careful to avoid integer overflow if actually implementing it as subtraction.

type RBNode 

type RBNode[T Ordered[T]] struct {
	Parent, Left, Right *RBNode[T]

	Color Color

	Value T
}

func (*RBNode[T]) Next 

func (cur *RBNode[T]) Next() *RBNode[T]

func (*RBNode[T]) Prev 

func (cur *RBNode[T]) Prev() *RBNode[T]

type RBTree 

type RBTree[T Ordered[T]] struct {
	AttrFn func(*RBNode[T])
	// contains filtered or unexported fields
}

func (*RBTree[T]) Delete 

func (t *RBTree[T]) Delete(nodeToDelete *RBNode[T])

func (*RBTree[T]) Equal 

func (t *RBTree[T]) Equal(u *RBTree[T]) bool

func (*RBTree[T]) Insert 

func (t *RBTree[T]) Insert(val T)

func (*RBTree[T]) Len 

func (t *RBTree[T]) Len() int

func (*RBTree[T]) Max 

func (t *RBTree[T]) Max() *RBNode[T]

Max returns the maximum value stored in the tree, or nil if the tree is empty.

func (*RBTree[T]) Min 

func (t *RBTree[T]) Min() *RBNode[T]

Min returns the minimum value stored in the tree, or nil if the tree is empty.

func (*RBTree[T]) Range 

func (t *RBTree[T]) Range(fn func(*RBNode[T]) bool)

func (*RBTree[T]) Search 

func (t *RBTree[T]) Search(fn func(T) int) *RBNode[T]

Search the tree for a value that satisfied the given callbackk function. A return value of 0 means to return this value; <0 means to go left on the tree (the value is too high), >0 means to go right on th etree (the value is too low). 

        +-----+
        | v=8 | == 0 : this is it
        +-----+
       /       \
      /         \
<0 : go left   >0 : go right
    /             \
 +---+          +---+
 | 7 |          | 9 |
 +---+          +---+

Returns nil if no such value is found.

func (*RBTree[T]) Subrange 

func (t *RBTree[T]) Subrange(rangeFn func(T) int, handleFn func(*RBNode[T]) bool)

Subrange is like Search, but for when there may be more than one result.

type RangeMap 

type RangeMap[K comparable, V any] interface {
	Map[K, V]
	Range(func(K, V) bool)
}

type Set 

type Set[T comparable] map[T]struct{}

Set is an unordered set of T.

func NewSet 

func NewSet[T comparable](values ...T) Set[T]

func (*Set[T]) DecodeJSON 

func (o *Set[T]) DecodeJSON(r io.RuneScanner) error

func (Set[T]) Delete 

func (o Set[T]) Delete(v T)

func (Set[T]) DeleteFrom 

func (o Set[T]) DeleteFrom(p Set[T])

func (Set[T]) EncodeJSON 

func (o Set[T]) EncodeJSON(w io.Writer) error

func (Set[T]) Has 

func (o Set[T]) Has(v T) bool

func (Set[T]) HasAny 

func (a Set[T]) HasAny(b Set[T]) bool

func (Set[T]) Insert 

func (o Set[T]) Insert(v T)

func (Set[T]) InsertFrom 

func (o Set[T]) InsertFrom(p Set[T])

func (Set[T]) Intersection 

func (small Set[T]) Intersection(big Set[T]) Set[T]

func (Set[T]) TakeOne 

func (o Set[T]) TakeOne() T

type SlicePool 

type SlicePool[T any] struct {
	// contains filtered or unexported fields
}

func (*SlicePool[T]) Get 

func (p *SlicePool[T]) Get(size int) []T

func (*SlicePool[T]) Put 

func (p *SlicePool[T]) Put(slice []T)

type SortedMap 

type SortedMap[K Ordered[K], V any] struct {
	// contains filtered or unexported fields
}

func (*SortedMap[K, V]) Delete 

func (m *SortedMap[K, V]) Delete(key K)

func (*SortedMap[K, V]) Has 

func (m *SortedMap[K, V]) Has(key K) bool

func (*SortedMap[K, V]) Len 

func (m *SortedMap[K, V]) Len() int

func (*SortedMap[K, V]) Load 

func (m *SortedMap[K, V]) Load(key K) (value V, ok bool)

func (*SortedMap[K, V]) Range 

func (m *SortedMap[K, V]) Range(fn func(key K, value V) bool)

func (*SortedMap[K, V]) Search 

func (m *SortedMap[K, V]) Search(fn func(K, V) int) (K, V, bool)

func (*SortedMap[K, V]) Store 

func (m *SortedMap[K, V]) Store(key K, value V)

func (*SortedMap[K, V]) Subrange 

func (m *SortedMap[K, V]) Subrange(rangeFn func(K, V) int, handleFn func(K, V) bool)

type Source 

type Source[K comparable, V any] interface {
	// Load updates a 'V' (which is reused across the lifetime of
	// the cache, and may or may not be zero) to be set to the
	// value for the 'K'.
	Load(context.Context, K, *V)

	// Flush does whatever it needs to in order to ensure that if
	// the program exited right now, no one would be upset.  Flush
	// being called does not mean that the entry is being evicted
	// from the cache.
	Flush(context.Context, *V)
}

A Source is something that a Cache sits in front of.

type SourceFunc 

type SourceFunc[K comparable, V any] func(context.Context, K, *V)

SourceFunc implements Source. Load calls the function, and Flush is a no-op.

func (SourceFunc[K, V]) Flush 

func (SourceFunc[K, V]) Flush(context.Context, *V)

func (SourceFunc[K, V]) Load 

func (fn SourceFunc[K, V]) Load(ctx context.Context, k K, v *V)

type SubrangeMap 

type SubrangeMap[K comparable, V any] interface {
	RangeMap[K, V]
	Subrange(rangeFn func(K, V) int, handleFn func(K, V) bool)
}

Source Files

View all Source files

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.