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 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) GetTileID ¶
GetTileID returns the ID of the tile that the given node belongs to.
Note that nodes located at strata boundaries normally belong to tiles rooted above them. However, the topmost node (with an empty NodeID) is the root for its own tile since there is nothing above it.
func (*Layout) GetTileRootID ¶ added in v1.3.6
GetTileRootID returns the ID for the root of the tile that the node with the given ID belongs to.
func (*Layout) Split ¶
Split returns the ID of the that the given node belongs to, and the corresponding local address within this tile.
func (*Layout) TileHeight ¶ added in v1.3.5
TileHeight returns the height of a tile with its root located at the specified depth from the tree root. The result is not defined if rootDepth is not a tile boundary.
TODO(pavelkalinnikov, v2): Use "type-safe" structured argument like NodeID2.
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.
TODO(pavelkalinnikov, v2): To be removed in the next major version.
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 identifies a node of a Merkle tree. It is a bit string that counts the node down from the tree root, i.e. 0 and 1 bits represent going to the left or right child correspondingly.
NodeID2 is immutable, comparable, and can be used as a Golang map key. It also incurs zero memory allocations in transforming methods like Prefix and Sibling.
The internal structure of NodeID2 is driven by its use-cases:
- To make NodeID2 objects immutable and comparable, the Golang string type is used for storing the bit string bytes.
- To make Sibling and Prefix operations fast, the last byte is stored separately from the rest of the bytes, so that it can be "amended".
- To make NodeID2 objects comparable, there is only one (canonical) way to encode an ID. For example, if the last byte is used partially, its unused bits are always unset. See invariants next to field definitions below.
Constructors and methods of NodeID2 make sure its invariants are always met.
For example, an 11-bit node ID [1010,1111,001] is structured as follows: - path string contains 1 byte, which is [1010,1111]. - last byte is [0010,0000]. Note the unset lower 5 bits. - bits is 3, so effectively only the upper 3 bits [001] of last are used.
TODO(pavelkalinnikov, v2): Replace NodeID with this type.
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 NewNodeID2WithLast ¶ added in v1.3.5
NewNodeID2WithLast creates a NodeID2 from the given path bytes and the additional last byte, of which only the specified number of most significant bits is used. The number of bits must be between 1 and 8, and can be 0 only if the path bytes string is empty; otherwise the function panics.
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 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.
TODO(pavelkalinnikov, v2): This type is specific to SubtreeProto. Move it.
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.
TODO(pavelkalinnikov): Mask the last byte of path.
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