Documentation
¶
Overview ¶
Package tree defines types that help navigating a tree in storage.
Index ¶
- Variables
- type Layout
- type Node
- type NodeID
- func NewNodeIDForTreeCoords(depth int64, index int64, maxPathBits int) (NodeID, error)
- func NewNodeIDFromBigInt(depth int, index *big.Int, totalDepth int) NodeID
- func NewNodeIDFromHash(h []byte) NodeID
- func NewNodeIDFromID2(id NodeID2) NodeID
- func NewNodeIDFromPrefix(prefix []byte, depth int, index int64, subDepth, totalDepth int) NodeID
- func NewNodeIDFromPrefixSuffix(prefix []byte, suffix *Suffix, maxPathBits int) NodeID
- func (n NodeID) AsKey() string
- func (n NodeID) BigInt() *big.Int
- func (n NodeID) Bit(i int) uint
- func (n NodeID) CoordString() string
- func (n NodeID) Copy() NodeID
- func (n NodeID) Equivalent(other NodeID) bool
- func (n NodeID) MaskLeft(depth int) NodeID
- func (n NodeID) Neighbor(depth int) NodeID
- func (n NodeID) PathLenBits() int
- func (n NodeID) Prefix(prefixBytes int) []byte
- func (n NodeID) PrefixAsKey(prefixBytes int) string
- func (n NodeID) Siblings() []NodeID
- func (n NodeID) Split(prefixBytes, suffixBits int) ([]byte, *Suffix)
- func (n NodeID) String() string
- func (n NodeID) Suffix(prefixBytes, suffixBits int) *Suffix
- func (n NodeID) ToNodeID2() NodeID2
- type NodeID2
- type PopulateSubtreeFunc
- type PrepareSubtreeWriteFunc
- type Suffix
- type TileID
Constants ¶
This section is empty.
Variables ¶
var ( // EmptySuffix is a reusable suffix of zero bits. To avoid special cases // there is a single byte path attached to it and there is no way to create // a Suffix with a nil or empty path. EmptySuffix = NewSuffix(0, []byte{0}) )
Functions ¶
This section is empty.
Types ¶
type Layout ¶
type Layout struct {
// Height is the height of the tree. It defines the maximal bit-length of a
// node ID that the tree can contain.
Height int
// contains filtered or unexported fields
}
Layout defines the mapping between tree node IDs and tile IDs.
func (*Layout) GetTileHeight ¶
GetTileHeight returns the height of the tile with the passed-in ID.
type NodeID ¶
type NodeID struct {
// Path is effectively a BigEndian bit set, with the MSB of Path[0]
// identifying the root child, and successive bits identifying the lower
// level children down to the leaf.
Path []byte
// PrefixLenBits is the number of significant bits in Path, which are
// considered part of this NodeID.
//
// e.g. if Path contains two bytes, and PrefixLenBits is 9, then the 8 bits
// in Path[0] are included, along with the MSB of Path[1]. The remaining
// 7 bits are not significant.
PrefixLenBits int
}
NodeID is an identifier of a Merkle tree Node. A default constructed NodeID is an empty ID representing the root of a (sub-)tree. The type is designed to be immutable, so the public fields should not be modified.
Reading paths right to left is the natural order when traversing from leaves towards the root. However, for internal nodes the rightmost bits of the IDs are not aligned on a byte boundary so care must be taken.
NodeIDs as presented to the storage layer will always have a multiple of 8 bits as they identify the root of a 256 element subtree.
Note that some of the APIs count bits with 0 being the rightmost in the entire path array when some of these might not be significant.
See the types.go file that defines this type for more detailed information and docs/storage for how they are used in the on-disk representation of Merkle trees.
func NewNodeIDForTreeCoords ¶
NewNodeIDForTreeCoords creates a new NodeID for a Tree node with a specified depth and index. This method is used exclusively by the Log, and, since the Log model grows upwards from the leaves, we modify the provided coords accordingly.
depth is the Merkle tree level: 0 = leaves, and increases upwards towards the root.
index is the horizontal index into the tree at level depth, so the returned NodeID will be zero padded on the right by depth places.
func NewNodeIDFromBigInt ¶
NewNodeIDFromBigInt creates a new node for a given depth and index, where the index can exceed a 64-bit range. The total tree depth must be provided. This occurs in the sparse Merkle tree implementation for maps as the lower levels have up 2^(hash size) entries. For log trees see NewNodeIDForTreeCoords.
func NewNodeIDFromHash ¶
NewNodeIDFromHash creates a new NodeID for the given Hash.
func NewNodeIDFromID2 ¶
NewNodeIDFromID2 constructs a NodeID from a NodeID2.
func NewNodeIDFromPrefix ¶
NewNodeIDFromPrefix returns a nodeID for a particular node within a subtree. Prefix is the prefix of the subtree. depth is the depth of index from the root of the subtree. index is the horizontal location of the subtree leaf. subDepth is the total number of levels in the subtree. totalDepth is the number of levels in the whole tree.
func NewNodeIDFromPrefixSuffix ¶
NewNodeIDFromPrefixSuffix undoes Split() and returns the NodeID.
func (NodeID) AsKey ¶
AsKey returns a string identifier for this NodeID suitable for short term use e.g. as a Map key. It is more efficient to use this than String() as it's not constrained to return a binary string.
func (NodeID) Bit ¶
Bit returns 1 if the zero indexed ith bit from the right (of the whole path array, not just the significant portion) is true, and false otherwise.
func (NodeID) CoordString ¶
CoordString returns a string representation assuming that the NodeID represents a tree coordinate. Using this on a NodeID for a sparse Merkle tree will give incorrect results. Intended for debugging purposes, the format could change.
func (NodeID) Equivalent ¶
Equivalent return true iff the other represents the same path prefix as this NodeID.
func (NodeID) Neighbor ¶
Neighbor returns a new copy of a node, applying a LeftMask operation and with the bit at PrefixLenBits in the copy flipped. In terms of a tree traversal, this is the parent node's other child node in the binary tree (often termed sibling node).
func (NodeID) Prefix ¶
Prefix returns a copy of NodeID's prefix. This is the same value that would be returned from Split, but without the overhead of calculating the suffix too.
func (NodeID) PrefixAsKey ¶
PrefixAsKey returns a NodeID's prefix in a format suitable for use as a map key. This is the same value that would be returned from Split, but without the overhead of calculating the suffix too.
func (NodeID) Siblings ¶
Siblings returns the siblings of the given node. In terms of a tree traversal, this returns the Neighbour() of every node (including this one) on the path up to the root. The array is of length PrefixLenBits and is ordered such that the nodes closest to the leaves are earlier in the array. These nodes are the ones that would be required for a Merkle tree inclusion proof for this node.
func (NodeID) Split ¶
Split splits a NodeID into a prefix and a suffix at prefixBytes. The returned prefix is a copy of the underlying bytes.
func (NodeID) String ¶
String returns a string representation of the binary value of the NodeID. The left-most bit is the MSB (i.e. nearer the root of the tree). The length of the returned string will always be the same as the prefix length of the node. For a string ID to use as a map key see AsKey().
type NodeID2 ¶
type NodeID2 struct {
// contains filtered or unexported fields
}
NodeID2 is a faster NodeID that does zero memory allocations in transforming methods like Prefix and Sibling. NodeID2 can be used as a key in Golang maps directly, as well as compared equal.
TODO(pavelkalinnikov): Rename to NodeID and document it properly when the code has migrated.
func NewNodeID2 ¶
NewNodeID2 creates a NodeID2 from the given path bytes truncated to the specified number of bits if necessary. Panics if the number of bits is more than the byte string contains.
func (NodeID2) FullBytes ¶
FullBytes returns the ID bytes that are complete. Note that there might still be up to 8 extra bits, which can be obtained with the LastByte method.
func (NodeID2) LastByte ¶
LastByte returns the terminating byte of the ID, with the number of upper bits that it uses (between 1 and 8, and 0 if the ID is empty). The remaining unused lower bits are always unset.
type PopulateSubtreeFunc ¶
type PopulateSubtreeFunc func(*storagepb.SubtreeProto) error
PopulateSubtreeFunc is a function which knows how to re-populate a subtree from just its leaf nodes.
type PrepareSubtreeWriteFunc ¶
type PrepareSubtreeWriteFunc func(*storagepb.SubtreeProto) error
PrepareSubtreeWriteFunc is a function that carries out any required tree type specific manipulation of a subtree before it's written to storage
type Suffix ¶
type Suffix struct {
// contains filtered or unexported fields
}
Suffix represents the tail of a NodeID. It is the path within the subtree. The portion of the path that extends beyond the subtree is not part of this suffix. We keep a cache of the Suffix values use by log trees, which will have a depth between 1 and 8 bits. These are reused to avoid constant reallocation and base64 conversion overhead.
func NewSuffix ¶
NewSuffix creates a new Suffix. The primary use for them is to get their String value to use as a key so we compute that once up front.
func ParseSuffix ¶
ParseSuffix converts a suffix string back into a Suffix.
type TileID ¶
type TileID struct {
Root NodeID
}
TileID holds the ID of a tile, which is aligned with the tree layout.
It assumes that strata heights are multiples of 8, and so the byte representation of the TileID matches NodeID.
Source Files