pot

package
v0.5.9-0...-ba7202b Latest Latest
Warning

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

Go to latest
Published: Mar 11, 2022 License: GPL-3.0 Imports: 9 Imported by: 0

Documentation

Overview

Package pot see doc.go

Package pot (proximity order tree) implements a container similar to a binary tree. The elements are generic Val interface types.

Each fork in the trie is itself a value. Values of the subtree contained under a node all share the same order when compared to other elements in the tree.

Example of proximity order is the length of the common prefix over bitvectors. (which is equivalent to the reverse rank of order of magnitude of the MSB first X OR distance over finite set of integers).

Methods take a comparison operator (pof, proximity order function) to compare two value types. The default pof assumes Val to be or project to a byte slice using the reverse rank on the MSB first XOR logarithmic distance.

If the address space if limited, equality is defined as the maximum proximity order.

The container offers applicative (functional) style methods on PO trees: * adding/removing en element * swap (value based add/remove) * merging two PO trees (union)

as well as iterator accessors that respect proximity order

When synchronicity of membership if not 100% requirement (e.g. used as a database of network connections), applicative structures have the advantage that nodes are immutable therefore manipulation does not need locking allowing for concurrent retrievals. For the use case where the entire container is supposed to allow changes by concurrent routines,

Pot * retrieval, insertion and deletion by key involves log(n) pointer lookups * for any item retrieval (defined as common prefix on the binary key) * provide synchronous iterators respecting proximity ordering wrt any item * provide asynchronous iterator (for parallel execution of operations) over n items * allows cheap iteration over ranges * asymmetric concurrent merge (union)

Note: * as is, union only makes sense for set representations since which of two values with equal keys survives is random * intersection is not implemented * simple get accessor is not implemented (but derivable from EachNeighbour)

Pinned value on the node implies no need to copy keys of the item type.

Note that * the same set of values allows for a large number of alternative POT representations. * values on the top are accessed faster than lower ones and the steps needed to retrieve items has a logarithmic distribution.

As a consequence one can organise the tree so that items that need faster access are torwards the top. In particular for any subset where popularity has a power distriution that is independent of proximity order (content addressed storage of chunks), it is in principle possible to create a pot where the steps needed to access an item is inversely proportional to its popularity. Such organisation is not implemented as yet.

TODO: * overwrite-style merge * intersection * access frequency based optimisations

Package pot see doc.go

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func DefaultPof

func DefaultPof(max int) func(one, other Val, pos int) (int, bool)

DefaultPof returns a proximity order comparison operator function

func Distance

func Distance(x, y []byte) (*big.Int, error)

Distance returns the distance between address x and address y as a (comparable) big integer using the distance metric defined in the swarm specification Fails if not all addresses are of equal length

func DistanceCmp

func DistanceCmp(a, x, y []byte) (int, error)

DistanceCmp compares x and y to a in terms of the distance metric defined in the swarm specfication it returns:

1 if x is closer to a than y
0 if x and y are equally far apart from (this means that x and y are the same address)
-1 if x is farther from a than y

Fails if not all addresses are of equal length

func DistanceRaw

func DistanceRaw(x, y []byte) ([]byte, error)

DistanceRaw returns the distance between address x and address y in big-endian binary format using the distance metric defined in the swarm specfication Fails if not all addresses are of equal length

func Label

func Label(v Val) string

Label displays the node's key in binary format

func NewAddressFromString

func NewAddressFromString(s string) []byte

NewAddressFromString creates a byte slice from a string in binary representation

func ProxCmp

func ProxCmp(a, x, y []byte) int

ProxCmp compares the distances x->a and y->a Returns -1 if x is closer to a, 1 if y is closer to a and 0 if they are equal.

func ToBin

func ToBin(a []byte) string

ToBin converts a byteslice to the string binary representation

func ToBytes

func ToBytes(v Val) []byte

ToBytes turns the Val into bytes

Types

type Address

type Address common.Hash

Address is an alias for common.Hash

func NewAddressFromBytes

func NewAddressFromBytes(b []byte) Address

NewAddressFromBytes constructs an Address from a byte slice

func RandomAddress

func RandomAddress() Address

RandomAddress generates a random address

func RandomAddressAt

func RandomAddressAt(self Address, prox int) (addr Address)

RandomAddressAt (address, prox) generates a random address at proximity order prox relative to address if prox is negative a random address is generated

func (Address) Bin

func (a Address) Bin() string

Bin returns the string form of the binary representation of an address (only first 8 bits)

func (Address) Bytes

func (a Address) Bytes() []byte

Bytes returns the Address as a byte slice

func (*Address) MarshalJSON

func (a *Address) MarshalJSON() (out []byte, err error)

MarshalJSON Address serialisation

func (Address) String

func (a Address) String() string

func (*Address) UnmarshalJSON

func (a *Address) UnmarshalJSON(value []byte) error

UnmarshalJSON Address deserialisation

type Bin

type Bin struct {
	ProximityOrder int
	Size           int
	ValIterator    ValIterator
}

type BinConsumer

type BinConsumer func(bin *Bin) bool

BinConsumer is called with a ProximityOrder, size and ValIterator of a Bin. It consumes a bin and if desired iterates over Val's in the bin using the ValIterator The function should return true if it wants to consume a new bin or false otherwise Consumer<Bin> in generics notation

type BytesAddress

type BytesAddress interface {
	Address() []byte
}

BytesAddress is an interface for elements addressable by a byte slice

type NeighbourConsumer

type NeighbourConsumer = func(Val, int) bool

type Pof

type Pof func(Val, Val, int) (int, bool)

Pof is the proximity order comparison operator function

type Pot

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

Pot is the node type (same for root, branching node and leaf)

func Add

func Add(t *Pot, val Val, pof Pof) (*Pot, int, bool)

Add inserts a new value into the Pot and returns the proximity order of v and a boolean indicating if the item was found Add called on (t, v) returns a new Pot that contains all the elements of t plus the value v, using the applicative add the second return value is the proximity order of the inserted element the third is boolean indicating if the item was found

func NewPot

func NewPot(v Val, po int) *Pot

NewPot constructor. Requires a value of type Val to pin and po to point to a span in the Val key The pinned item counts towards the size

func Remove

func Remove(t *Pot, v Val, pof Pof) (*Pot, int, bool)

Remove deletes element v from the Pot t and returns three parameters: 1. new Pot that contains all the elements of t minus the element v; 2. proximity order of the removed element v; 3. boolean indicating whether the item was found.

func Swap

func Swap(t *Pot, k Val, pof Pof, f func(v Val) Val) (r *Pot, po int, found bool, change bool)

Swap called on (k, f) looks up the item at k and applies the function f to the value v at k or to nil if the item is not found if f(v) returns nil, the element is removed if f(v) returns v' <> v then v' is inserted into the Pot if (v) == v the Pot is not changed it panics if Pof(f(v), k) show that v' and v are not key-equal BUG if "default" empty pot is supplied (created with NewPot(nil, 0), queried address NOT found, then returned pot will be a nil value

func Union

func Union(t0, t1 *Pot, pof Pof) (*Pot, int)

Union called on (t0, t1, pof) returns the union of t0 and t1 calculates the union using the applicative union the second return value is the number of common elements

func (*Pot) BiggestAddressGap

func (t *Pot) BiggestAddressGap() (po int, val Val)

BiggestAddressGap tries to find the biggest address not covered by an element in the address space. Biggest gaps tend to be top left of the tree (if the pot is rendered root top and bins with po = 0 left). As the bins progress to the right or down (higher proximity order) the address space gap left is smaller. An address gap is defined as a missing proximity order without any value. So for example, a root value with two bins, one with po 0 and one with po 2 has a gap in po=1. Of course it also has a gap in po>=3 but that gap is smaller in number of addresses contained. If the total space area is 1, the space covered by a bin of proximity order n can be defined as 1/2^n. So po=0 will occupy half of the area, po=5 1/32 of the area and so on. When a gap is found there is no need to go further on that level because advancing (horizontally or vertically) will decrease the maximum gap space by half. The function returns the proximity order of the gap and the reference value where the gap has been found (so the exact address set can be calculated)

func (*Pot) Each

func (t *Pot) Each(consumer ValConsumer) bool

Each is a synchronous iterator over the elements of pot with a consumer.

func (*Pot) EachBin

func (t *Pot) EachBin(pivotVal Val, pof Pof, minProximityOrder int, binConsumer BinConsumer, ascending bool)

EachBin iterates over bins relative to the pivot Val node and offers iterators to the caller on each subtree passing the proximity order and the size the iteration continues until the function's return value is false or there are no more subtrees. The order the bins are consumed depends on the bins po with respect to the pivot Val. minProximityOrder gives the caller the possibility of filtering the bins by proximityOrder >= minProximityOrder If pivotVal is the root val it iterates the bin as stored in this pot. ascending flag controls the sorting of bins in the iterator. True => will be for farthest to closest, false => closest to farthest

func (*Pot) EachNeighbour

func (t *Pot) EachNeighbour(val Val, pof Pof, consume NeighbourConsumer) bool

EachNeighbour is a synchronous iterator over neighbours of any target val the order of elements retrieved reflect proximity order to the target TODO: add maximum proxbin to start range of iteration

func (*Pot) EachNeighbourAsync

func (t *Pot) EachNeighbourAsync(val Val, pof Pof, max int, maxPos int, f func(Val, int), wait bool)

EachNeighbourAsync called on (val, max, maxPos, f, wait) is an asynchronous iterator over elements not closer than maxPos wrt val. val does not need to be match an element of the Pot, but if it does, and maxPos is keylength than it is included in the iteration Calls to f are parallelised, the order of calls is undefined. proximity order is respected in that there is no element in the Pot that is not visited if a closer node is visited. The iteration is finished when max number of nearest nodes is visited or if the entire there are no nodes not closer than maxPos that is not visited if wait is true, the iterator returns only if all calls to f are finished TODO: implement minPos for proper prox range iteration

func (*Pot) Pin

func (t *Pot) Pin() Val

Pin returns the pinned element (key) of the Pot

func (*Pot) PotWithPo

func (t *Pot) PotWithPo(pivotVal Val, desiredPo int, pof Pof) *Pot

PotWithPo returns a Pot with all elements with proximity order desiredPo w.r.t. pivotVal. is similar to obtain a bin but in a tree structure that helps in some calculations

func (*Pot) Size

func (t *Pot) Size() int

Size returns the number of values in the Pot

func (*Pot) String

func (t *Pot) String() string

type Val

type Val interface{}

Val is the element type for Pots

type ValConsumer

type ValConsumer func(Val) bool

ValConsumer is a function that consumes a Val and returns if it wants to consume more or not Consumer<Val> in generic notation

type ValIterator

type ValIterator func(ValConsumer) bool

ValIterator is a function that iterates values and executes for each of them a supplied ValConsumer. it returns the result of the last ValConsumer executed. It could hint users of this interface to continue iterating other ValIterators (for example in EachBin will continue or not with the next Bin). Iterator<Val> Iterator<T> => func (Consumer<T>) bool

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL