tree

package
v0.40.4 Latest Latest
Warning

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

 Go to latest Published: May 19, 2022 License: Apache-2.0 Imports: 25 Imported by: 5

Documentation

Index

Constants

View Source 
const (

	// weibull params
	K = 4.

	// TODO: seems like this should be targetSize / math.Gamma(1 + 1/K).
	L = targetSize
)

Variables

This section is empty.

Functions

func AscendingUintTuples 

func AscendingUintTuples(count int) (tuples [][2]val.Tuple, desc val.TupleDesc)

Map<Tuple<Uint32>,Tuple<Uint32>>

func CloneRandomTuples 

func CloneRandomTuples(items [][2]val.Tuple) (clone [][2]val.Tuple)

func OutputProllyNode 

func OutputProllyNode(w io.Writer, node Node) error

OutputProllyNode writes the node given to the writer given in a semi-human-readable format, where values are still displayed in hex-encoded byte strings, but are delineated into their fields. All nodes have keys displayed in this manner. Interior nodes have their child hash references spelled out, leaf nodes have value tuples delineated like the keys

func PrintTreeSummaryByLevel 

func PrintTreeSummaryByLevel(t *testing.T, nd Node, ns NodeStore)

func RandomCompositeTuplePairs 

func RandomCompositeTuplePairs(count int, keyDesc, valDesc val.TupleDesc) (items [][2]val.Tuple)

func RandomTuple 

func RandomTuple(tb *val.TupleBuilder) (tup val.Tuple)

func RandomTuplePairs 

func RandomTuplePairs(count int, keyDesc, valDesc val.TupleDesc) (items [][2]val.Tuple)

func ShuffleTuplePairs 

func ShuffleTuplePairs(items [][2]val.Tuple)

func SortTuplePairs 

func SortTuplePairs(items [][2]val.Tuple, keyDesc val.TupleDesc)

func ValueFromNode 

func ValueFromNode(root Node) types.Value

func WalkAddresses 

func WalkAddresses(ctx context.Context, nd Node, ns NodeStore, cb AddressCb) error

func WalkNodes 

func WalkNodes(ctx context.Context, nd Node, ns NodeStore, cb NodeCb) error

Types

type AddressCb 

type AddressCb func(ctx context.Context, addr hash.Hash) error

type Chunker 

type Chunker interface {
	AddPair(ctx context.Context, key, value Item) error
	Done(ctx context.Context) (Node, error)
}

func NewEmptyChunker 

func NewEmptyChunker[S message.Serializer](ctx context.Context, ns NodeStore, serializer S) (Chunker, error)

type CollisionFn 

type CollisionFn func(left, right Diff) (Diff, bool)

CollisionFn is a callback that handles 3-way merging of NodeItems. A typical implementation will attempt a cell-wise merge of the tuples, or register a conflict if such a merge is not possible.

type CompareFn 

type CompareFn func(left, right Item) int

type Cursor 

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

Cursor explores a tree of Nodes.

func NewCursorAtEnd 

func NewCursorAtEnd(ctx context.Context, ns NodeStore, nd Node) (cur *Cursor, err error)

func NewCursorAtItem 

func NewCursorAtItem(ctx context.Context, ns NodeStore, nd Node, item Item, search ItemSearchFn) (cur *Cursor, err error)

func NewCursorAtOrdinal 

func NewCursorAtOrdinal(ctx context.Context, ns NodeStore, nd Node, ord uint64) (cur *Cursor, err error)

func NewCursorAtStart 

func NewCursorAtStart(ctx context.Context, ns NodeStore, nd Node) (cur *Cursor, err error)

func NewCursorFromCompareFn 

func NewCursorFromCompareFn(ctx context.Context, ns NodeStore, n Node, i Item, compare CompareFn) (*Cursor, error)

func NewCursorFromSearchFn 

func NewCursorFromSearchFn(ctx context.Context, ns NodeStore, nd Node, search SearchFn) (cur *Cursor, err error)

func NewCursorPastEnd 

func NewCursorPastEnd(ctx context.Context, ns NodeStore, nd Node) (cur *Cursor, err error)

func NewLeafCursorAtItem 

func NewLeafCursorAtItem(ctx context.Context, ns NodeStore, nd Node, item Item, search ItemSearchFn) (cur Cursor, err error)

func (*Cursor) Advance 

func (cur *Cursor) Advance(ctx context.Context) (bool, error)

func (*Cursor) Clone 

func (cur *Cursor) Clone() *Cursor

func (*Cursor) Compare 

func (cur *Cursor) Compare(other *Cursor) int

func (*Cursor) CurrentKey 

func (cur *Cursor) CurrentKey() Item

func (*Cursor) CurrentRef 

func (cur *Cursor) CurrentRef() hash.Hash

func (*Cursor) CurrentValue 

func (cur *Cursor) CurrentValue() Item

func (*Cursor) Invalidate 

func (cur *Cursor) Invalidate()

func (*Cursor) Retreat 

func (cur *Cursor) Retreat(ctx context.Context) (bool, error)

func (*Cursor) Valid 

func (cur *Cursor) Valid() bool

type Diff 

type Diff struct {
	Key      Item
	From, To Item
	Type     DiffType
}

type DiffType 

type DiffType byte
const (
	AddedDiff    DiffType = 0
	ModifiedDiff DiffType = 1
	RemovedDiff  DiffType = 2
)

type Differ 

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

func DifferFromRoots 

func DifferFromRoots(ctx context.Context, ns NodeStore, from, to Node, cmp CompareFn) (Differ, error)

func (Differ) Next 

func (td Differ) Next(ctx context.Context) (diff Diff, err error)

type Item 

type Item []byte

func CurrentCursorItems 

func CurrentCursorItems(cur *Cursor) (key, value Item)

type ItemSearchFn 

type ItemSearchFn func(item Item, nd Node) (idx int)

type MutationIter 

type MutationIter interface {
	NextMutation(ctx context.Context) (key, value Item)
	Close() error
}

type Node 

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

func ApplyMutations 

func ApplyMutations[S message.Serializer](
	ctx context.Context,
	ns NodeStore,
	root Node,
	serializer S,
	edits MutationIter,
	compare CompareFn,
) (Node, error)

func NewTupleLeafNode 

func NewTupleLeafNode(keys, values []val.Tuple) Node

func NodeFromBytes 

func NodeFromBytes(msg []byte) Node

func ThreeWayMerge 

func ThreeWayMerge[S message.Serializer](
	ctx context.Context,
	ns NodeStore,
	left, right, base Node,
	compare CompareFn,
	collide CollisionFn,
	serializer S,
) (final Node, err error)

ThreeWayMerge implements a three-way merge algorithm using |base| as the common ancestor, |right| as the source branch, and |left| as the destination branch. Both |left| and |right| are diff'd against |base| to compute merge patches, but rather than applying both sets of patches to |base|, patches from |right| are applied directly to |left|. This reduces the amount of write work and improves performance. In the case that a key-value pair was modified on both |left| and |right| with different resulting values, the CollisionFn is called to perform a cell-wise merge, or to throw a conflict.

func (Node) Count 

func (nd Node) Count() int

func (Node) GetKey 

func (nd Node) GetKey(i int) Item

GetKey returns the |ith| key of this node

func (Node) HashOf 

func (nd Node) HashOf() hash.Hash

func (Node) IsLeaf 

func (nd Node) IsLeaf() bool

IsLeaf returns whether this node is a leaf

func (Node) Level 

func (nd Node) Level() int

Level returns the tree Level for this node

func (Node) Size 

func (nd Node) Size() int

func (Node) TreeCount 

func (nd Node) TreeCount() int

type NodeCb 

type NodeCb func(ctx context.Context, nd Node) error

type NodeStore 

type NodeStore interface {
	// Read reads a prolly tree Node from the store.
	Read(ctx context.Context, ref hash.Hash) (Node, error)

	// Write writes a prolly tree Node to the store.
	Write(ctx context.Context, nd Node) (hash.Hash, error)

	// Pool returns a buffer pool.
	Pool() pool.BuffPool

	// Format returns the types.NomsBinFormat of this NodeStore.
	Format() *types.NomsBinFormat
}

NodeStore reads and writes prolly tree Nodes.

func NewNodeStore 

func NewNodeStore(cs chunks.ChunkStore) NodeStore

NewNodeStore makes a new NodeStore.

func NewTestNodeStore 

func NewTestNodeStore() NodeStore

type Samples 

type Samples []int

func (Samples) Summary 

func (s Samples) Summary() string

type SearchFn 

type SearchFn func(nd Node) (idx int)

type SubtreeCounts 

type SubtreeCounts []uint64

func (SubtreeCounts) Sum 

func (sc SubtreeCounts) Sum() (s uint64)

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.