merkletrie

Documentation

Index

• type Iter
  • func NewIter(n Noder) *Iter
  • func (iter *Iter) Next() (Noder, bool)
  • func (iter *Iter) Step() (Noder, bool)
• type Noder

Types

type Iter

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

Iter is a radix tree iterator that will traverse the trie in depth-first pre-order. Entries are traversed in (case-sensitive) alphabetical order for each level.

This is the kind of traversal you will expect when listing ordinary files and directories recursively, for example:

     Trie           Traversal order
     ----           ---------------
      .
    / | \           a
   /  |  \          b
  b   a   z   ===>  b/a
 / \                b/c
c   a               z

The Step method will return the next item, the Next method will do the same but without descending deeper into the tree (i.e. skipping the contents of "directories").

The name of the type and its methods are based on the well known "next" and "step" operations, quite common in debuggers, like gdb.

func NewIter

func NewIter(n Noder) *Iter

NewIter returns a new iterator for the trie with its root at n.

func (*Iter) Next

func (iter *Iter) Next() (Noder, bool)

Next returns the next node without descending deeper into the tree and true. If there are no more entries it returns nil and false.

func (*Iter) Step

func (iter *Iter) Step() (Noder, bool)

Step returns the next node in the tree, descending deeper into it if needed. If there are no more nodes in the tree, it returns nil and false.

type Noder

type Noder interface {
	// Hash returns the hash of the element.
	Hash() []byte
	// Key returns the key of the element.
	Key() string
	// Children returns the children of the element, sorted
	// in reverse key alphabetical order.
	Children() []Noder
	// NumChildren returns the number of children this element has.
	//
	// This method is an optimization: the number of children is easily
	// calculated as the length of the value returned by the Children
	// method (above); yet, some implementations will be able to
	// implement NumChildren in O(1) while Children is usually more
	// complex.
	NumChildren() int
}

The Noder interface is implemented by the elements of a Merkle Trie.