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 ¶
- func DefaultPof(max int) func(one, other Val, pos int) (int, bool)
- func Distance(x, y []byte) (*big.Int, error)
- func DistanceCmp(a, x, y []byte) (int, error)
- func DistanceRaw(x, y []byte) ([]byte, error)
- func Label(v Val) string
- func NewAddressFromString(s string) []byte
- func ProxCmp(a, x, y []byte) int
- func ToBin(a []byte) string
- func ToBytes(v Val) []byte
- type Address
- type Bin
- type BinConsumer
- type BytesAddress
- type NeighbourConsumer
- type Pof
- type Pot
- func (t *Pot) BiggestAddressGap() (po int, val Val)
- func (t *Pot) Each(consumer ValConsumer) bool
- func (t *Pot) EachBin(pivotVal Val, pof Pof, minProximityOrder int, binConsumer BinConsumer, ...)
- func (t *Pot) EachNeighbour(val Val, pof Pof, consume NeighbourConsumer) bool
- func (t *Pot) EachNeighbourAsync(val Val, pof Pof, max int, maxPos int, f func(Val, int), wait bool)
- func (t *Pot) Pin() Val
- func (t *Pot) PotWithPo(pivotVal Val, desiredPo int, pof Pof) *Pot
- func (t *Pot) Size() int
- func (t *Pot) String() string
- type Val
- type ValConsumer
- type ValIterator
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func DefaultPof ¶
DefaultPof returns a proximity order comparison operator function
func Distance ¶
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 ¶
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 ¶
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 NewAddressFromString ¶
NewAddressFromString creates a byte slice from a string in binary representation
func ProxCmp ¶
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.
Types ¶
type Address ¶
Address is an alias for common.Hash
func NewAddressFromBytes ¶
NewAddressFromBytes constructs an Address from a byte slice
func RandomAddressAt ¶
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 ¶
Bin returns the string form of the binary representation of an address (only first 8 bits)
func (*Address) MarshalJSON ¶
MarshalJSON Address serialisation
func (*Address) UnmarshalJSON ¶
UnmarshalJSON Address deserialisation
type Bin ¶
type Bin struct {
ProximityOrder int
Size int
ValIterator ValIterator
}
type BinConsumer ¶
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 Pot ¶
type Pot struct {
// contains filtered or unexported fields
}
Pot is the node type (same for root, branching node and leaf)
func Add ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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
type ValConsumer ¶
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
Source Files