trie

Documentation

Index

• Variables
• func Run(c cnfg.Config) error
• func String(t Searchable) string
• func TestCOW(c cnfg.Config) error
• func TestMerge(cnfg.Config) error
• func ToGviz(g gviz.Graph, file, title string) error
• type Database
• type Joiner
• type KeyValue
  • func (k KeyValue) String() string
  • func (k *KeyValue) Verify() error
• type SearchFunc
• type Searchable
• type StringDatabase
  • func NewStrings(db Database) StringDatabase
• type StringKeyValue
• type Trie
  • func Join(meet, a, b *Trie, merger Joiner) (*Trie, error)
  • func New() (*Trie, error)
  • func (t *Trie) Copy() *Trie
  • func (t *Trie) Delete(key []byte) (Database, error)
  • func (t *Trie) Edges() (out []gviz.Edge)
  • func (t *Trie) Get(key []byte) ([]byte, error)
  • func (t *Trie) Hash() ([]byte, error)
  • func (t *Trie) IsClean() bool
  • func (t *Trie) MarkDirty()
  • func (t *Trie) Nodes() (out []gviz.Node)
  • func (t *Trie) Search(f SearchFunc) (*KeyValue, error)
  • func (t *Trie) Set(key, value []byte) (Database, error)
  • func (t *Trie) String() string
  • func (t *Trie) ToGviz(file, title string) error
• type Visualizable

Variables

var EmptyKey = errors.New("empty key")

var NotFound = errors.New("key not found")

returned or wrapped to indicate key not found

Functions

func Run

func Run(c cnfg.Config) error

func String

func String(t Searchable) string

func TestCOW

func TestCOW(c cnfg.Config) error

func TestMerge

func TestMerge(cnfg.Config) error

func ToGviz

func ToGviz(g gviz.Graph, file, title string) error

Types

type Database

type Database interface {
	Set([]byte, []byte) (Database, error)
	Get([]byte) ([]byte, error)
	Delete([]byte) (Database, error)
	Hash() ([]byte, error)
	Searchable
	Visualizable
}

copy-on-write database

type Joiner

type Joiner interface {
	Join(meet, a, b *KeyValue) (*KeyValue, error)
}

type KeyValue

type KeyValue struct {
	Key, Value, Hash []byte
}

func (KeyValue) String

func (k KeyValue) String() string

func (*KeyValue) Verify

func (k *KeyValue) Verify() error

type SearchFunc

type SearchFunc func(kv *KeyValue) bool

type Searchable

type Searchable interface {
	// error indicates not found or worse, else keyvalue is non-nil
	Search(SearchFunc) (*KeyValue, error)
}

type StringDatabase

type StringDatabase interface {
	Set(string, string) (StringDatabase, error)
	Get(string) (string, error)
	Delete(string) (StringDatabase, error)
	Hash() ([]byte, error)
	Search(func(kv *StringKeyValue) bool) (*StringKeyValue, error)
	Visualizable
}

func NewStrings

func NewStrings(db Database) StringDatabase

type StringKeyValue

type StringKeyValue struct {
	Key, Value string
}

type Trie

type Trie struct {
	*KeyValue
	Merkle []byte
	Next   [256]*Trie
	Count  *big.Int // number of kv pairs in this and all descendants
}

func Join

func Join(meet, a, b *Trie, merger Joiner) (*Trie, error)

Join is a three-way merge

func New

func New() (*Trie, error)

func (*Trie) Copy

func (t *Trie) Copy() *Trie

Copy without merkle hash, in order to mark "dirty"

func (*Trie) Delete

func (t *Trie) Delete(key []byte) (Database, error)

func (*Trie) Edges

func (t *Trie) Edges() (out []gviz.Edge)

func (*Trie) Get

func (t *Trie) Get(key []byte) ([]byte, error)

func (*Trie) Hash

func (t *Trie) Hash() ([]byte, error)

func (*Trie) IsClean

func (t *Trie) IsClean() bool

func (*Trie) MarkDirty

func (t *Trie) MarkDirty()

func (*Trie) Nodes

func (t *Trie) Nodes() (out []gviz.Node)

func (*Trie) Search

func (t *Trie) Search(f SearchFunc) (*KeyValue, error)

func (*Trie) Set

func (t *Trie) Set(key, value []byte) (Database, error)

TODO: also need a set method etc that returns *Trie

func (*Trie) String

func (t *Trie) String() string

func (*Trie) ToGviz

func (t *Trie) ToGviz(file, title string) error

type Visualizable

type Visualizable interface {
	ToGviz(file, title string) error
}