tree

package
v0.0.0-...-2c13b6f Latest Latest
Warning

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

 Go to latest Published: Nov 1, 2023 License: Apache-2.0 Imports: 30 Imported by: 1

Documentation

Index

Constants

View Source 
const (
	Modify op = 1
	Add    op = 2
	Remove op = 3
)
View Source 
const (
	DefaultMinChunkSize = 1 << 9
	DefaultMaxChunkSize = 1 << 12
)
View Source 
const (
	SuffixThreshold  = 0
	WeibullThreshold = 1
	RollingHash      = 2
)
View Source 
const DefaultChannelSize = 20
View Source 
const (
	TimeOutLimit = time.Second * 100
)

Variables

View Source 
var (

	// ProllyNodePrototype represents the IPLD node prototype of Metadata.
	// See: bindnode.Prototype.
	ProllyNodePrototype schema.TypedPrototype

	ChunkConfigPrototype schema.TypedPrototype

	ProllyTreePrototype schema.TypedPrototype

	ProofPrototype schema.TypedPrototype

	ProofSegmentPrototype schema.TypedPrototype
)
View Source 
var DefaultLinkProto = cidlink.LinkPrototype{
	Prefix: cid.Prefix{
		Version:  1,
		Codec:    uint64(multicodec.DagCbor),
		MhType:   uint64(multicodec.Sha2_256),
		MhLength: 20,
	},
}
View Source 
var (
	KeyNotFound = errors.New("Key not found")
)

Functions

func EncodeNode 

func EncodeNode(n ipld.Node) []byte

func RandomTestData 

func RandomTestData(count int) ([][]byte, []ipld.Node)

Types

type BlockNodeStore 

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

func NewBlockNodeStore 

func NewBlockNodeStore(bs blockstore.Blockstore, cfg *StoreConfig) (*BlockNodeStore, error)

func (*BlockNodeStore) Close 

func (ns *BlockNodeStore) Close()

func (*BlockNodeStore) LinkSystem 

func (ns *BlockNodeStore) LinkSystem() *ipld.LinkSystem

func (*BlockNodeStore) ReadNode 

func (ns *BlockNodeStore) ReadNode(ctx context.Context, c cid.Cid) (*ProllyNode, error)

func (*BlockNodeStore) ReadProof 

func (ns *BlockNodeStore) ReadProof(ctx context.Context, c cid.Cid) (Proof, error)

func (*BlockNodeStore) ReadTree 

func (ns *BlockNodeStore) ReadTree(ctx context.Context, c cid.Cid) (*ProllyTree, error)

func (*BlockNodeStore) ReadTreeConfig 

func (ns *BlockNodeStore) ReadTreeConfig(ctx context.Context, c cid.Cid) (*TreeConfig, error)

func (*BlockNodeStore) WriteNode 

func (ns *BlockNodeStore) WriteNode(ctx context.Context, nd *ProllyNode, prefix *cid.Prefix) (cid.Cid, error)

func (*BlockNodeStore) WriteProof 

func (ns *BlockNodeStore) WriteProof(ctx context.Context, prf Proof, prefix *cid.Prefix) (cid.Cid, error)

func (*BlockNodeStore) WriteTree 

func (ns *BlockNodeStore) WriteTree(ctx context.Context, root *ProllyTree, prefix *cid.Prefix) (cid.Cid, error)

func (*BlockNodeStore) WriteTreeConfig 

func (ns *BlockNodeStore) WriteTreeConfig(ctx context.Context, cfg *TreeConfig, prefix *cid.Prefix) (cid.Cid, error)

type ChunkStrategy 

type ChunkStrategy string

type CompareFunc 

type CompareFunc func(left, right []byte) int
var DefaultCompareFunc CompareFunc = bytes.Compare

type Cursor 

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

func CursorAtItem 

func CursorAtItem(root *ProllyNode, item []byte, cp CompareFunc, ns NodeStore) (*Cursor, error)

func (*Cursor) Advance 

func (cur *Cursor) Advance() error

func (*Cursor) Compare 

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

func (*Cursor) Equal 

func (cur *Cursor) Equal(other *Cursor) bool

func (*Cursor) GetIndex 

func (cur *Cursor) GetIndex() int

func (*Cursor) GetKey 

func (cur *Cursor) GetKey() []byte
func (cur *Cursor) GetLink() cid.Cid

func (*Cursor) GetTreeCount 

func (cur *Cursor) GetTreeCount() uint32

func (*Cursor) GetValue 

func (cur *Cursor) GetValue() ipld.Node

func (*Cursor) IsAtEnd 

func (cur *Cursor) IsAtEnd() bool

func (*Cursor) IsBiggerThanTheNode 

func (cur *Cursor) IsBiggerThanTheNode(key []byte) bool

func (*Cursor) IsValid 

func (cur *Cursor) IsValid() bool

func (*Cursor) SkipCommon 

func (cur *Cursor) SkipCommon(other *Cursor) error

type Diffs 

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

func NewDiffs 

func NewDiffs() *Diffs

func (*Diffs) AddMutation 

func (d *Diffs) AddMutation(mut *Mutation) error

func (*Diffs) Close 

func (d *Diffs) Close() error

func (*Diffs) NextMutations 

func (d *Diffs) NextMutations() (*Mutation, error)

type Framework 

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

func NewFramework 

func NewFramework(ctx context.Context, ns NodeStore, cfg *TreeConfig, cur *Cursor) (*Framework, error,
)

func (*Framework) AdvanceCursor 

func (fw *Framework) AdvanceCursor(ctx context.Context) error

func (*Framework) Append 

func (fw *Framework) Append(ctx context.Context, key []byte, val ipld.Node) error

func (*Framework) AppendBatch 

func (fw *Framework) AppendBatch(ctx context.Context, keys [][]byte, vals []ipld.Node) error

AppendBatch should only use in data input, cannot be used in rebalance procedure

func (*Framework) AppendFromMutations 

func (fw *Framework) AppendFromMutations(ctx context.Context, muts *Mutations) error

func (*Framework) BuildTree 

func (fw *Framework) BuildTree(ctx context.Context) (*ProllyTree, cid.Cid, error)

type HashThresholdConfig 

type HashThresholdConfig struct {
	ChunkingFactor int
	HashFunction   uint64
}

func (*HashThresholdConfig) Equal 

func (ptc *HashThresholdConfig) Equal(sc strategyConfig) bool

type Iterator 

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

func NewIterator 

func NewIterator(size int) *Iterator

func (*Iterator) Done 

func (si *Iterator) Done() bool

func (*Iterator) IsEmpty 

func (si *Iterator) IsEmpty() bool

func (*Iterator) Next 

func (si *Iterator) Next() (ipld.Node, ipld.Node, error)

func (*Iterator) NextPair 

func (si *Iterator) NextPair() ([]byte, ipld.Node, error)

type LevelBuilder 

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

type LinkSystemNodeStore 

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

func NewLinkSystemNodeStore 

func NewLinkSystemNodeStore(lsys *linking.LinkSystem) *LinkSystemNodeStore

func (*LinkSystemNodeStore) Close 

func (ns *LinkSystemNodeStore) Close()

func (*LinkSystemNodeStore) LinkSystem 

func (ns *LinkSystemNodeStore) LinkSystem() *ipld.LinkSystem

func (*LinkSystemNodeStore) ReadNode 

func (ns *LinkSystemNodeStore) ReadNode(ctx context.Context, c cid.Cid) (*ProllyNode, error)

func (*LinkSystemNodeStore) ReadProof 

func (ns *LinkSystemNodeStore) ReadProof(ctx context.Context, c cid.Cid) (Proof, error)

func (*LinkSystemNodeStore) ReadTree 

func (ns *LinkSystemNodeStore) ReadTree(ctx context.Context, c cid.Cid) (*ProllyTree, error)

func (*LinkSystemNodeStore) ReadTreeConfig 

func (ns *LinkSystemNodeStore) ReadTreeConfig(ctx context.Context, c cid.Cid) (*TreeConfig, error)

func (*LinkSystemNodeStore) WriteNode 

func (ns *LinkSystemNodeStore) WriteNode(ctx context.Context, nd *ProllyNode, prefix *cid.Prefix) (cid.Cid, error)

func (*LinkSystemNodeStore) WriteProof 

func (ns *LinkSystemNodeStore) WriteProof(ctx context.Context, prf Proof, prefix *cid.Prefix) (cid.Cid, error)

func (*LinkSystemNodeStore) WriteTree 

func (ns *LinkSystemNodeStore) WriteTree(ctx context.Context, root *ProllyTree, prefix *cid.Prefix) (cid.Cid, error)

func (*LinkSystemNodeStore) WriteTreeConfig 

func (ns *LinkSystemNodeStore) WriteTreeConfig(ctx context.Context, cfg *TreeConfig, prefix *cid.Prefix) (cid.Cid, error)

type Mutation 

type Mutation struct {
	Key []byte
	Val ipld.Node
	Op  op
}

type Mutations 

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

Mutations receives batch updates such as put, delete....., also used in ADL builder

func NewMutations 

func NewMutations() *Mutations

func (*Mutations) AddMutation 

func (m *Mutations) AddMutation(mut *Mutation) error

func (*Mutations) Finish 

func (m *Mutations) Finish()

func (*Mutations) Get 

func (m *Mutations) Get(item []byte) (ipld.Node, error)

func (*Mutations) NextMutation 

func (m *Mutations) NextMutation() (*Mutation, error)

type NodeCoder 

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

func NewNodeCoder 

func NewNodeCoder() *NodeCoder

func (*NodeCoder) EncodeNode 

func (nc *NodeCoder) EncodeNode(node ipld.Node) ([]byte, error)

func (*NodeCoder) InitEncoder 

func (nc *NodeCoder) InitEncoder(codec uint64) error

func (*NodeCoder) LoadEncoder 

func (nc *NodeCoder) LoadEncoder(indicator uint64, encodeFunc codec.Encoder) error

type NodeStore 

type NodeStore interface {
	WriteNode(ctx context.Context, nd *ProllyNode, prefix *cid.Prefix) (cid.Cid, error)
	ReadNode(ctx context.Context, c cid.Cid) (*ProllyNode, error)

	WriteTree(ctx context.Context, tree *ProllyTree, prefix *cid.Prefix) (cid.Cid, error)
	ReadTree(ctx context.Context, c cid.Cid) (*ProllyTree, error)

	WriteTreeConfig(ctx context.Context, cfg *TreeConfig, prefix *cid.Prefix) (cid.Cid, error)
	ReadTreeConfig(ctx context.Context, c cid.Cid) (*TreeConfig, error)

	WriteProof(ctx context.Context, prf Proof, prefix *cid.Prefix) (cid.Cid, error)
	ReadProof(ctx context.Context, c cid.Cid) (Proof, error)

	LinkSystem() *ipld.LinkSystem

	Close()
}

todo: maybe we need clean orphan nodes regularly?

func TestMemNodeStore 

func TestMemNodeStore() NodeStore

type ProllyNode 

type ProllyNode struct {
	IsLeaf       bool
	Keys         [][]byte
	Values       []ipld.Node
	SubtreeCount []uint32
}

func UnwrapProllyNode 

func UnwrapProllyNode(node ipld.Node) (*ProllyNode, error)

func (*ProllyNode) GetIdxKey 

func (n *ProllyNode) GetIdxKey(i int) []byte
func (n *ProllyNode) GetIdxLink(i int) cid.Cid

func (*ProllyNode) GetIdxTreeCount 

func (n *ProllyNode) GetIdxTreeCount(i int) uint32

func (*ProllyNode) GetIdxValue 

func (n *ProllyNode) GetIdxValue(i int) ipld.Node

func (*ProllyNode) IsEmpty 

func (n *ProllyNode) IsEmpty() bool

func (*ProllyNode) IsLeafNode 

func (n *ProllyNode) IsLeafNode() bool

func (*ProllyNode) ItemCount 

func (n *ProllyNode) ItemCount() int

func (*ProllyNode) KeyIndex 

func (n *ProllyNode) KeyIndex(item []byte, cp CompareFunc) int

KeyIndex finds the index that the closest but not smaller than the item

func (*ProllyNode) ToNode 

func (n *ProllyNode) ToNode() (nd ipld.Node, err error)

type ProllyRoot 

type ProllyRoot struct {
	Config cid.Cid
	Root   cid.Cid
}

type ProllyTree 

type ProllyTree struct {
	ProllyRoot
	// contains filtered or unexported fields
}

func BuildTestTreeFromData 

func BuildTestTreeFromData(t *testing.T, keys [][]byte, vals []ipld.Node) (*ProllyTree, cid.Cid)

func LoadProllyTreeFromRootCid 

func LoadProllyTreeFromRootCid(rootCid cid.Cid, ns NodeStore) (*ProllyTree, error)

func UnwrapProllyTree 

func UnwrapProllyTree(node ipld.Node) (*ProllyTree, error)

func (*ProllyTree) Delete 

func (pt *ProllyTree) Delete(ctx context.Context, key []byte) error

func (*ProllyTree) Diff 

func (pt *ProllyTree) Diff(other *ProllyTree) (*Diffs, error)

func (*ProllyTree) FirstKey 

func (pt *ProllyTree) FirstKey() ([]byte, error)

get the first(smallest) key of the tree

func (*ProllyTree) Get 

func (pt *ProllyTree) Get(key []byte) (ipld.Node, error)

func (*ProllyTree) GetProof 

func (pt *ProllyTree) GetProof(key []byte) (Proof, error)

func (*ProllyTree) IsMutating 

func (pt *ProllyTree) IsMutating() bool

func (*ProllyTree) LastKey 

func (pt *ProllyTree) LastKey() ([]byte, error)

get the last(largest) key of the tree

func (*ProllyTree) LoadProllyTreeFromRootNode 

func (pt *ProllyTree) LoadProllyTreeFromRootNode(ns NodeStore) error

func (*ProllyTree) Merge 

func (pt *ProllyTree) Merge(ctx context.Context, other *ProllyTree) error

func (*ProllyTree) Mutate 

func (pt *ProllyTree) Mutate() error

func (*ProllyTree) NodeStore 

func (pt *ProllyTree) NodeStore() NodeStore

func (*ProllyTree) Put 

func (pt *ProllyTree) Put(ctx context.Context, key []byte, val ipld.Node) error

func (*ProllyTree) Rebuild 

func (pt *ProllyTree) Rebuild(ctx context.Context) (cid.Cid, error)

func (*ProllyTree) Search 

func (pt *ProllyTree) Search(ctx context.Context, start []byte, end []byte) (*Iterator, error)

func (*ProllyTree) ToNode 

func (pt *ProllyTree) ToNode() (nd ipld.Node, err error)

func (*ProllyTree) TreeCid 

func (pt *ProllyTree) TreeCid() (*cid.Cid, error)

func (*ProllyTree) TreeConfig 

func (pt *ProllyTree) TreeConfig() TreeConfig

func (*ProllyTree) TreeCount 

func (pt *ProllyTree) TreeCount() uint32

type Proof 

type Proof []ProofSegment

func UnwrapProof 

func UnwrapProof(node ipld.Node) (*Proof, error)

func (*Proof) ToNode 

func (pf *Proof) ToNode() (nd ipld.Node, err error)

type ProofSegment 

type ProofSegment struct {
	// Which TreeNode this key is in
	// For last segment this should be the root CID
	Node cid.Cid
	// Which index in the node the key is in
	// For leaf nodes this is the value
	// For non-leafs this is where the prev node was linked
	Index int
}

Segments in proving a key-value pair is in a tree

func UnwrapProofSegment 

func UnwrapProofSegment(node ipld.Node) (*ProofSegment, error)

func (*ProofSegment) ToNode 

func (ps *ProofSegment) ToNode() (nd ipld.Node, err error)

type RollingHashConfig 

type RollingHashConfig struct {
	RollingHashWindow uint32
}

func (*RollingHashConfig) Equal 

func (rhc *RollingHashConfig) Equal(sc strategyConfig) bool

type Splitter 

type Splitter interface {
	// IsBoundary returns whether boundary generated at current location
	IsBoundary() bool
	Append(key, val []byte) error
	Reset()
}

func NewSplitterFromConfig 

func NewSplitterFromConfig(config *TreeConfig) Splitter

type StoreConfig 

type StoreConfig struct {
	CacheSize int
}

type SuffixSplitter 

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

func (*SuffixSplitter) Append 

func (p *SuffixSplitter) Append(key, val []byte) error

func (*SuffixSplitter) IsBoundary 

func (p *SuffixSplitter) IsBoundary() bool

func (*SuffixSplitter) Reset 

func (p *SuffixSplitter) Reset()

type TreeConfig 

type TreeConfig struct {
	MinNodeSize    int
	MaxNodeSize    int
	MaxPairsInNode int
	CidVersion     uint64
	Codec          uint64
	HashFunction   uint64
	HashLength     *int
	//NodeCodec      NodeCodec
	StrategyType byte
	Strategy     strategy
}

TreeConfig includes config for prolly tree, it includes some global setting, the splitter method you choose and specific configs about the splitter

func DefaultChunkConfig 

func DefaultChunkConfig() *TreeConfig

func UnwrapChunkConfig 

func UnwrapChunkConfig(node ipld.Node) (*TreeConfig, error)

func (*TreeConfig) CidPrefix 

func (cfg *TreeConfig) CidPrefix() *cid.Prefix

func (*TreeConfig) Equal 

func (cfg *TreeConfig) Equal(another *TreeConfig) bool

func (*TreeConfig) ToNode 

func (cfg *TreeConfig) ToNode() (n ipld.Node, err error)

type WeibullThresholdConfig 

type WeibullThresholdConfig struct {
	K float64
	L float64
}

func (*WeibullThresholdConfig) Equal 

func (wtc *WeibullThresholdConfig) Equal(sc strategyConfig) bool

Source Files

View all Source files

Directories

Path Synopsis

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.