pot

package
v1.8.22-0...-509facd Latest Latest
Warning

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

Go to latest
Published: May 17, 2019 License: GPL-3.0 Imports: 7 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 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 interface{}) int

ProxCmp compares the distances a->target and b->target. Returns -1 if a is closer to target, 1 if b is closer to target 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 BytesAddress

type BytesAddress interface {
	Address() []byte
}

BytesAddress is an interface for elements addressable by a byte slice

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

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) Each

func (t *Pot) Each(f func(Val) bool) bool

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

func (*Pot) EachBin

func (t *Pot) EachBin(val Val, pof Pof, po int, f func(int, int, func(func(val Val) bool) bool) bool)

EachBin iterates over bins of the pivot 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 subtries

func (*Pot) EachNeighbour

func (t *Pot) EachNeighbour(val Val, pof Pof, f func(Val, int) bool) 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) 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

Jump to

Keyboard shortcuts

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