route

package
v0.2.7-0...-d8d973c Latest Latest
Warning

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

 Go to latest Published: Jan 31, 2017 License: MIT Imports: 14 Imported by: 1

Documentation

Index

Constants

View Source 
const MaxFinalizers = 16

Variables

View Source 
var BTreeNew func() BTree2D

Functions

This section is empty.

Types

type BTree2D 

type BTree2D interface {
	Sync(next BTree2D, onAdd, onDel func(key1 uint64, key2 RouteInfo))
	GetLayer(key1 uint64) (SecondaryLayer, bool)
	SetLayer(key1 uint64, layer SecondaryLayer)
	ForEach(fn func(key uint64, layer SecondaryLayer) bool)
	ForEach2(key1 uint64, fn func(key2 RouteInfo) bool)
	Put(key1 uint64, key2 RouteInfo, finalizers ...func())
	Delete(key1 uint64, key2 RouteInfo) bool
	Drop(key1 uint64) bool
}

func New 

func New(cmp1 PrimaryCmpFunc, cmp2 SecondaryCmpFunc) BTree2D

type FinalizerList 

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

func (*FinalizerList) AddFinalizer 

func (f *FinalizerList) AddFinalizer(fn func()) bool

func (*FinalizerList) Finalize 

func (f *FinalizerList) Finalize()

func (*FinalizerList) Len 

func (f *FinalizerList) Len() int

type HashRingSelector 

type HashRingSelector struct {
	VBucket int
}

func (HashRingSelector) Select 

func (hrs HashRingSelector) Select(pool []RouteInfo) (idx int, cache bool)

type Iterator 

type Iterator struct {
	*Registry
	// contains filtered or unexported fields
}

func (Iterator) Next 

func (self Iterator) Next() Iterator

type Pair 

type Pair struct {
	K uint64
	V RouteInfo
}

type PrimaryCmpFunc 

type PrimaryCmpFunc func(key1, key2 uint64) int

PrimaryCmpFunc compares a and b. Return value is: 

< 0 if a <  b
  0 if a == b
> 0 if a >  b

type PrimaryEnumerator 

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

PrimaryEnumerator captures the state of enumerating a tree. It is returned from the Seek* methods. The enumerator is aware of any mutations made to the tree in the process of enumerating it and automatically resumes the enumeration at the proper key, if possible.

However, once an PrimaryEnumerator returns io.EOF to signal "no more items", it does no more attempt to "resync" on tree mutation(s). In other words, io.EOF from an PrimaryEnumerator is "sticky" (idempotent).

func (*PrimaryEnumerator) Close 

func (e *PrimaryEnumerator) Close()

Close recycles e to a pool for possible later reuse. No references to e should exist or such references must not be used afterwards.

func (*PrimaryEnumerator) Next 

func (e *PrimaryEnumerator) Next() (k uint64, v SecondaryLayer, err error)

Next returns the currently enumerated item, if it exists and moves to the next item in the key collation order. If there is no item to return, err == io.EOF is returned.

func (*PrimaryEnumerator) Prev 

func (e *PrimaryEnumerator) Prev() (k uint64, v SecondaryLayer, err error)

Prev returns the currently enumerated item, if it exists and moves to the previous item in the key collation order. If there is no item to return, err == io.EOF is returned.

type PrimaryLayer 

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

PrimaryLayer represents the primary layer, a tree holding comparable keys pointing to secondary layers.

func NewPrimaryLayer 

func NewPrimaryLayer(cmp1 PrimaryCmpFunc, cmp2 SecondaryCmpFunc) PrimaryLayer

NewPrimaryLayer initializes a new primary layer handle.

func (PrimaryLayer) Drop 

func (l PrimaryLayer) Drop(k uint64) (ok bool)

Drop removes the whole secondary layer associated with the key, invokes all the finalizers associated with elements of this secondary layer.

func (PrimaryLayer) ForEach 

func (l PrimaryLayer) ForEach(fn func(key uint64, layer SecondaryLayer) bool)

ForEach runs the provided function for every element in the layer, if function returns true, the loop stops.

func (PrimaryLayer) Get 

func (l PrimaryLayer) Get(k uint64) (layer SecondaryLayer, ok bool)

Get returns the secondary layer associated with the key.

func (PrimaryLayer) Len 

func (l PrimaryLayer) Len() int

func (PrimaryLayer) Put 

func (l PrimaryLayer) Put(k uint64, k2 RouteInfo, finalizers ...func())

Put adds keys and callbacks to the secondary layer, which will be created if not yet existing.

func (PrimaryLayer) Rev 

func (l PrimaryLayer) Rev() uint64

func (PrimaryLayer) Seek 

func (l PrimaryLayer) Seek(k uint64) (e *PrimaryEnumerator, ok bool)

Seek returns an PrimaryEnumerator positioned on a secondary layer such that k >= layer's key.

func (PrimaryLayer) SeekFirst 

func (l PrimaryLayer) SeekFirst() (e *PrimaryEnumerator, err error)

SeekFirst returns an PrimaryEnumerator positioned on the first secondary layer in the tree.

func (PrimaryLayer) Set 

func (l PrimaryLayer) Set(k uint64, layer SecondaryLayer)

Set just adds a secondary layer to the tree, overwriting the previous one. Note that this action would trigger the replaced layer finalizers.

func (PrimaryLayer) Sync 

func (prev PrimaryLayer) Sync(next PrimaryLayer, onAdd, onDel func(key1 uint64, key2 RouteInfo))

type PrimaryTree 

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

PrimaryTree is a B+tree.

func NewPrimaryTree 

func NewPrimaryTree(cmp PrimaryCmpFunc) *PrimaryTree

NewPrimaryTree returns a newly created, empty PrimaryTree. The compare function is used for key collation.

func (*PrimaryTree) Clear 

func (t *PrimaryTree) Clear()

Clear removes all K/V pairs from the tree.

func (*PrimaryTree) Close 

func (t *PrimaryTree) Close()

Close performs Clear and recycles t to a pool for possible later reuse. No references to t should exist or such references must not be used afterwards.

func (*PrimaryTree) Delete 

func (t *PrimaryTree) Delete(k uint64) (ok bool)

Delete removes the k's KV pair, if it exists, in which case Delete returns true.

func (*PrimaryTree) First 

func (t *PrimaryTree) First() (k uint64, v SecondaryLayer)

First returns the first item of the tree in the key collating order, or (zero-value, zero-value) if the tree is empty.

func (*PrimaryTree) Get 

func (t *PrimaryTree) Get(k uint64) (v SecondaryLayer, ok bool)

Get returns the value associated with k and true if it exists. Otherwise Get returns (zero-value, false).

func (*PrimaryTree) Last 

func (t *PrimaryTree) Last() (k uint64, v SecondaryLayer)

Last returns the last item of the tree in the key collating order, or (zero-value, zero-value) if the tree is empty.

func (*PrimaryTree) Len 

func (t *PrimaryTree) Len() int

Len returns the number of items in the tree.

func (*PrimaryTree) Put 

func (t *PrimaryTree) Put(k uint64, upd func(oldV SecondaryLayer, exists bool) (newV SecondaryLayer, write bool)) (oldV SecondaryLayer, written bool)

Put combines Get and Set in a more efficient way where the tree is walked only once. The upd(ater) receives (old-value, true) if a KV pair for k exists or (zero-value, false) otherwise. It can then return a (new-value, true) to create or overwrite the existing value in the KV pair, or (whatever, false) if it decides not to create or not to update the value of the KV pair. 

tree.Set(k, v) call conceptually equals calling

tree.Put(k, func(generic.T, bool){ return v, true })

modulo the differing return values.

func (*PrimaryTree) Seek 

func (t *PrimaryTree) Seek(k uint64) (e *PrimaryEnumerator, ok bool)

Seek returns an PrimaryEnumerator positioned on an item such that k >= item's key. ok reports if k == item.key The PrimaryEnumerator's position is possibly after the last item in the tree.

func (*PrimaryTree) SeekFirst 

func (t *PrimaryTree) SeekFirst() (e *PrimaryEnumerator, err error)

SeekFirst returns an enumerator positioned on the first KV pair in the tree, if any. For an empty tree, err == io.EOF is returned and e will be nil.

func (*PrimaryTree) SeekLast 

func (t *PrimaryTree) SeekLast() (e *PrimaryEnumerator, err error)

SeekLast returns an enumerator positioned on the last KV pair in the tree, if any. For an empty tree, err == io.EOF is returned and e will be nil.

func (*PrimaryTree) Set 

func (t *PrimaryTree) Set(k uint64, v SecondaryLayer)

Set sets the value associated with k.

func (*PrimaryTree) Ver 

func (t *PrimaryTree) Ver() uint64

type RandomSelector 

type RandomSelector struct {
}

func (RandomSelector) Select 

func (RandomSelector) Select(pool []RouteInfo) (idx int, cache bool)

type Reducer 

type Reducer interface {
	Reduce(pool []RouteInfo) []RouteInfo
}

type Registry 

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

func (*Registry) Close 

func (self *Registry) Close()

func (*Registry) Discover 

func (self *Registry) Discover(
	r Selector,
	sname uint64,
	reducer Reducer,
) (RouteInfo, bool)

func (*Registry) DiscoverTimeout 

func (self *Registry) DiscoverTimeout(
	r Selector, sname uint64,
	wait time.Duration,
	reducer Reducer,
) (srv RouteInfo, found bool)

func (*Registry) Iter 

func (self *Registry) Iter() Iterator

func (*Registry) Pop 

func (self *Registry) Pop(id uint64, srv RouteInfo)

func (*Registry) Push 

func (self *Registry) Push(id uint64, srv RouteInfo, action ...func())

func (*Registry) Sync 

func (self *Registry) Sync(other *Registry, onAdd, onDelete func(uint64, RouteInfo))

type RndDistSelector 

type RndDistSelector struct {
}

func (RndDistSelector) Select 

func (RndDistSelector) Select(pool []RouteInfo) (int, bool)

type RouteInfo 

type RouteInfo struct {
	Host     uint64
	Distance int
	Upstream transport.Transport
}

func (RouteInfo) String 

func (r RouteInfo) String() string

type SecondaryCmpFunc 

type SecondaryCmpFunc func(key1, key2 RouteInfo) int

SecondaryCmpFunc compares a and b. Return value is: 

< 0 if a <  b
  0 if a == b
> 0 if a >  b

type SecondaryEnumerator 

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

SecondaryEnumerator captures the state of enumerating a tree. It is returned from the Seek* methods. The enumerator is aware of any mutations made to the tree in the process of enumerating it and automatically resumes the enumeration at the proper key, if possible.

However, once an SecondaryEnumerator returns io.EOF to signal "no more items", it does no more attempt to "resync" on tree mutation(s). In other words, io.EOF from an SecondaryEnumerator is "sticky" (idempotent).

func (*SecondaryEnumerator) Close 

func (e *SecondaryEnumerator) Close()

Close recycles e to a pool for possible later reuse. No references to e should exist or such references must not be used afterwards.

func (*SecondaryEnumerator) Next 

func (e *SecondaryEnumerator) Next() (k RouteInfo, v *FinalizerList, err error)

Next returns the currently enumerated item, if it exists and moves to the next item in the key collation order. If there is no item to return, err == io.EOF is returned.

func (*SecondaryEnumerator) Prev 

func (e *SecondaryEnumerator) Prev() (k RouteInfo, v *FinalizerList, err error)

Prev returns the currently enumerated item, if it exists and moves to the previous item in the key collation order. If there is no item to return, err == io.EOF is returned.

type SecondaryLayer 

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

SecondaryLayer represents the secondary layer, a tree holding Finalizable yet Comparable keys.

func NewSecondaryLayer 

func NewSecondaryLayer(cmp SecondaryCmpFunc) SecondaryLayer

NewSecondaryLayer initializes a new secondary layer handle.

func (SecondaryLayer) Delete 

func (l SecondaryLayer) Delete(k RouteInfo) (ok bool)

Delete removes the key and runs all its finalizers.

func (SecondaryLayer) Finalize 

func (l SecondaryLayer) Finalize()

Finalize locks the layer and runs finalizers of all the keys from this layer. Call this if you're going to drop an entire layer.

func (SecondaryLayer) ForEach 

func (l SecondaryLayer) ForEach(fn func(key RouteInfo, val *FinalizerList) bool)

ForEach runs the provided function for every element in the layer, if function returns true, the loop stops.

func (SecondaryLayer) Len 

func (l SecondaryLayer) Len() int

func (SecondaryLayer) Put 

func (l SecondaryLayer) Put(k RouteInfo, finalizers ...func()) (added int)

Put adds finalizers for the key, creating the item if not exists yet.

func (SecondaryLayer) Rev 

func (l SecondaryLayer) Rev() uint64

func (SecondaryLayer) Seek 

func (l SecondaryLayer) Seek(k RouteInfo) (e *SecondaryEnumerator, ok bool)

Seek returns an SecondaryEnumerator positioned on a key such that k >= key.

func (SecondaryLayer) SeekFirst 

func (l SecondaryLayer) SeekFirst() (e *SecondaryEnumerator, err error)

SeekFirst returns an SecondaryEnumerator positioned on the first key in the tree.

func (SecondaryLayer) Sync 

func (prev SecondaryLayer) Sync(next SecondaryLayer, onAdd, onDel func(key RouteInfo))

type SecondaryTree 

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

SecondaryTree is a B+tree.

func NewSecondaryTree 

func NewSecondaryTree(cmp SecondaryCmpFunc) *SecondaryTree

NewSecondaryTree returns a newly created, empty SecondaryTree. The compare function is used for key collation.

func (*SecondaryTree) Clear 

func (t *SecondaryTree) Clear()

Clear removes all K/V pairs from the tree.

func (*SecondaryTree) Close 

func (t *SecondaryTree) Close()

Close performs Clear and recycles t to a pool for possible later reuse. No references to t should exist or such references must not be used afterwards.

func (*SecondaryTree) Delete 

func (t *SecondaryTree) Delete(k RouteInfo) (ok bool)

Delete removes the k's KV pair, if it exists, in which case Delete returns true.

func (*SecondaryTree) First 

func (t *SecondaryTree) First() (k RouteInfo, v *FinalizerList)

First returns the first item of the tree in the key collating order, or (zero-value, zero-value) if the tree is empty.

func (*SecondaryTree) Get 

func (t *SecondaryTree) Get(k RouteInfo) (v *FinalizerList, ok bool)

Get returns the value associated with k and true if it exists. Otherwise Get returns (zero-value, false).

func (*SecondaryTree) Last 

func (t *SecondaryTree) Last() (k RouteInfo, v *FinalizerList)

Last returns the last item of the tree in the key collating order, or (zero-value, zero-value) if the tree is empty.

func (*SecondaryTree) Len 

func (t *SecondaryTree) Len() int

Len returns the number of items in the tree.

func (*SecondaryTree) Put 

func (t *SecondaryTree) Put(k RouteInfo, upd func(oldV *FinalizerList, exists bool) (newV *FinalizerList, write bool)) (oldV *FinalizerList, written bool)

Put combines Get and Set in a more efficient way where the tree is walked only once. The upd(ater) receives (old-value, true) if a KV pair for k exists or (zero-value, false) otherwise. It can then return a (new-value, true) to create or overwrite the existing value in the KV pair, or (whatever, false) if it decides not to create or not to update the value of the KV pair. 

tree.Set(k, v) call conceptually equals calling

tree.Put(k, func(generic.U, bool){ return v, true })

modulo the differing return values.

func (*SecondaryTree) Seek 

func (t *SecondaryTree) Seek(k RouteInfo) (e *SecondaryEnumerator, ok bool)

Seek returns an SecondaryEnumerator positioned on an item such that k >= item's key. ok reports if k == item.key The SecondaryEnumerator's position is possibly after the last item in the tree.

func (*SecondaryTree) SeekFirst 

func (t *SecondaryTree) SeekFirst() (e *SecondaryEnumerator, err error)

SeekFirst returns an enumerator positioned on the first KV pair in the tree, if any. For an empty tree, err == io.EOF is returned and e will be nil.

func (*SecondaryTree) SeekLast 

func (t *SecondaryTree) SeekLast() (e *SecondaryEnumerator, err error)

SeekLast returns an enumerator positioned on the last KV pair in the tree, if any. For an empty tree, err == io.EOF is returned and e will be nil.

func (*SecondaryTree) Set 

func (t *SecondaryTree) Set(k RouteInfo, v *FinalizerList)

Set sets the value associated with k.

func (*SecondaryTree) Ver 

func (t *SecondaryTree) Ver() uint64

type Selector 

type Selector interface {
	Select(pool []RouteInfo) (idx int, cache bool) // pool can't empty
}

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.