tries

Documentation

Index

• Variables
• type Builder
  • func (b *Builder) Finish(ctx context.Context) (*Root, error)
  • func (b *Builder) Put(ctx context.Context, k, v []byte) error
• type Entry
  • func (*Entry) Descriptor() ([]byte, []int)
  • func (x *Entry) GetKey() []byte
  • func (x *Entry) GetValue() []byte
  • func (*Entry) ProtoMessage()
  • func (x *Entry) ProtoReflect() protoreflect.Message
  • func (x *Entry) Reset()
  • func (x *Entry) String() string
• type Index
  • func (*Index) Descriptor() ([]byte, []int)
  • func (x *Index) GetCount() uint64
  • func (x *Index) GetIsParent() bool
  • func (x *Index) GetRef() []byte
  • func (*Index) ProtoMessage()
  • func (x *Index) ProtoReflect() protoreflect.Message
  • func (x *Index) Reset()
  • func (x *Index) String() string
• type Iterator
  • func (it *Iterator) Next(ctx context.Context) (*Entry, error)
• type Machine
  • func NewMachine() *Machine
  • func (o *Machine) Delete(ctx context.Context, s cadata.Store, root Root, key []byte) (*Root, error)
  • func (o *Machine) Get(ctx context.Context, s cadata.Getter, root Root, key []byte) ([]byte, error)
  • func (o *Machine) MinEntry(ctx context.Context, s cadata.Store, root Root, gteq []byte) (*Entry, error)
  • func (o *Machine) NewBuilder(s writeStore, batchSize int) *Builder
  • func (o *Machine) NewIterator(s cadata.Store, root Root, span Span) *Iterator
  • func (o *Machine) Populate(ctx context.Context, s cadata.Store, root Root, set cadata.Set, ...) error
  • func (o *Machine) PostSlice(ctx context.Context, s cadata.Poster, ents []*Entry) (*Root, error)
  • func (o *Machine) Put(ctx context.Context, s cadata.Store, root Root, key, value []byte) (*Root, error)
  • func (o *Machine) PutBatch(ctx context.Context, s writeStore, root Root, ents []*Entry) (*Root, error)
  • func (o *Machine) Sync(ctx context.Context, dst, src cadata.Store, root Root, fn func(*Entry) error) error
  • func (o *Machine) Validate(ctx context.Context, s cadata.Store, x Root) error
  • func (o *Machine) Walk(ctx context.Context, s cadata.Store, root Root, w Walker) error
• type Node
  • func (*Node) Descriptor() ([]byte, []int)
  • func (x *Node) GetEntries() []*Entry
  • func (*Node) ProtoMessage()
  • func (x *Node) ProtoReflect() protoreflect.Message
  • func (x *Node) Reset()
  • func (x *Node) String() string
• type Ref
• type Root
• type Span
• type Walker

Variables

var (
	ErrNotExist = errors.Errorf("no entry for key")

	ErrCannotCollapse = errors.Errorf("cannot collapse parent into child")
	ErrCannotSplit    = errors.Errorf("cannot split, < 2 entries")
)

var File_trie_proto protoreflect.FileDescriptor

Types

type Builder

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

func (*Builder) Finish

func (b *Builder) Finish(ctx context.Context) (*Root, error)

func (*Builder) Put

func (b *Builder) Put(ctx context.Context, k, v []byte) error

type Entry

type Entry struct {
	Key   []byte `protobuf:"bytes,1,opt,name=key,proto3" json:"key,omitempty"`
	Value []byte `protobuf:"bytes,2,opt,name=value,proto3" json:"value,omitempty"`
	// contains filtered or unexported fields
}

func (*Entry) Descriptor

func (*Entry) Descriptor() ([]byte, []int)

Deprecated: Use Entry.ProtoReflect.Descriptor instead.

func (*Entry) GetKey

func (x *Entry) GetKey() []byte

func (*Entry) GetValue

func (x *Entry) GetValue() []byte

func (*Entry) ProtoMessage

func (*Entry) ProtoMessage()

func (*Entry) ProtoReflect

func (x *Entry) ProtoReflect() protoreflect.Message

func (*Entry) Reset

func (x *Entry) Reset()

func (*Entry) String

func (x *Entry) String() string

type Index

type Index struct {
	Ref      []byte `protobuf:"bytes,1,opt,name=ref,proto3" json:"ref,omitempty"`
	IsParent bool   `protobuf:"varint,2,opt,name=is_parent,json=isParent,proto3" json:"is_parent,omitempty"`
	Count    uint64 `protobuf:"varint,3,opt,name=count,proto3" json:"count,omitempty"`
	// contains filtered or unexported fields
}

func (*Index) Descriptor

func (*Index) Descriptor() ([]byte, []int)

Deprecated: Use Index.ProtoReflect.Descriptor instead.

func (*Index) GetCount

func (x *Index) GetCount() uint64

func (*Index) GetIsParent

func (x *Index) GetIsParent() bool

func (*Index) GetRef

func (x *Index) GetRef() []byte

func (*Index) ProtoMessage

func (*Index) ProtoMessage()

func (*Index) ProtoReflect

func (x *Index) ProtoReflect() protoreflect.Message

func (*Index) Reset

func (x *Index) Reset()

func (*Index) String

func (x *Index) String() string

type Iterator

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

func (*Iterator) Next

func (it *Iterator) Next(ctx context.Context) (*Entry, error)

type Machine

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

func NewMachine

func NewMachine() *Machine

func (*Machine) Delete

func (o *Machine) Delete(ctx context.Context, s cadata.Store, root Root, key []byte) (*Root, error)

Delete removes

func (*Machine) Get

func (o *Machine) Get(ctx context.Context, s cadata.Getter, root Root, key []byte) ([]byte, error)

Get retrieves a value at key if it exists, otherwise ErrNotExist is returned

func (*Machine) MinEntry

func (o *Machine) MinEntry(ctx context.Context, s cadata.Store, root Root, gteq []byte) (*Entry, error)

MinEntry returns the first entry >= gteq

func (*Machine) NewBuilder

func (o *Machine) NewBuilder(s writeStore, batchSize int) *Builder

func (*Machine) NewIterator

func (o *Machine) NewIterator(s cadata.Store, root Root, span Span) *Iterator

func (*Machine) Populate

func (o *Machine) Populate(ctx context.Context, s cadata.Store, root Root, set cadata.Set, fn func(*Entry) error) error

func (*Machine) PostSlice

func (o *Machine) PostSlice(ctx context.Context, s cadata.Poster, ents []*Entry) (*Root, error)

PostSlice returns a new instance containing ents

func (*Machine) Put

func (o *Machine) Put(ctx context.Context, s cadata.Store, root Root, key, value []byte) (*Root, error)

Put returns a copy of root where key maps to value, and all other mappings are unchanged.

func (*Machine) PutBatch

func (o *Machine) PutBatch(ctx context.Context, s writeStore, root Root, ents []*Entry) (*Root, error)

PutBatch performs a batch of put operations on ents, returning a new instance reflecting all the changes.

func (*Machine) Sync

func (o *Machine) Sync(ctx context.Context, dst, src cadata.Store, root Root, fn func(*Entry) error) error

Sync ensures that data structure exists in dst, using src to retrieve missing pieces. Sync is only correct if dangling references can be guarenteed to not exist in dst.

func (*Machine) Validate

func (o *Machine) Validate(ctx context.Context, s cadata.Store, x Root) error

func (*Machine) Walk

func (o *Machine) Walk(ctx context.Context, s cadata.Store, root Root, w Walker) error

Walk walks a Trie calling methods on Walker throughout the traversal. w.ShouldWalk is called before walking a node, if false is returned the node is skipped w.EntryFn is called for every entry in a node w.NodeFn is called for the node after all the entries reachable from it have been walked.

type Node

type Node struct {
	Entries []*Entry `protobuf:"bytes,1,rep,name=entries,proto3" json:"entries,omitempty"`
	// contains filtered or unexported fields
}

func (*Node) Descriptor

func (*Node) Descriptor() ([]byte, []int)

Deprecated: Use Node.ProtoReflect.Descriptor instead.

func (*Node) GetEntries

func (x *Node) GetEntries() []*Entry

func (*Node) ProtoMessage

func (*Node) ProtoMessage()

func (*Node) ProtoReflect

func (x *Node) ProtoReflect() protoreflect.Message

func (*Node) Reset

func (x *Node) Reset()

func (*Node) String

func (x *Node) String() string

type Ref

type Ref struct {
	ID     cadata.ID     `json:"id"`
	DEK    *bccrypto.DEK `json:"dek"`
	Length uint32        `json:"length"`
}

type Root

type Root struct {
	Ref      Ref
	IsParent bool   `json:"is_parent"`
	Count    uint64 `json:"count"`
	Prefix   []byte `json:"prefix"`
}

type Span

type Span = state.ByteSpan

type Walker

type Walker struct {
	ShouldWalk func(root Root) bool
	EntryFn    func(*Entry) error
	NodeFn     func(root Root) error
}