Documentation
¶
Index ¶
- Constants
- func GetBBKey(BIdx byte, key [32]byte) (BBKey [32]byte)
- func GetHash(e Entry) []byte
- type BPT
- func (b *BPT) Clean(node *Node)
- func (b *BPT) Dirty(node *Node)
- func (b *BPT) Equal(b2 *BPT) (equal bool)
- func (b *BPT) GetDirtyList() (list []*Node)
- func (b *BPT) Insert(key, hash [32]byte)
- func (b *BPT) IsDirty(node *Node) bool
- func (b *BPT) Marshal() (data []byte)
- func (b *BPT) MarshalByteBlock(borderNode *Node) (data []byte)
- func (b *BPT) MarshalEntry(entry Entry, data []byte) []byte
- func (b *BPT) NewNode(parent *Node) (node *Node)
- func (b *BPT) NewValue(key, hash [32]byte) (value *Value)
- func (b *BPT) UnMarshal(data []byte) (newData []byte)
- func (b *BPT) UnMarshalByteBlock(borderNode *Node, data []byte) []byte
- func (b *BPT) UnMarshalEntry(parent *Node, data []byte) (Entry, []byte)
- func (b *BPT) Update()
- type Entry
- type Manager
- type Node
- type NotLoaded
- type Value
Constants ¶
const ( TNil = iota + 1 // When persisting, this is the type for nils TNode // Type for Nodes TValue // Type for values TNotLoaded // When transisioning into a new Byte Block, the NotLoaded indicates a need to load from disk )
Variables ¶
This section is empty.
Functions ¶
Types ¶
type BPT ¶
type BPT struct {
Root *Node // The root of the Patricia Tree, holding the summary hash for the Patricia Tree
DirtyMap map[uint64]*Node // Map of dirty nodes.
MaxHeight int // Highest height of any node in the BPT
MaxNodeID uint64 // Maximum node id assigned to any node
// contains filtered or unexported fields
}
BPT Binary Patricia Tree. Two types of Entry in the Tree:
Node - a node in a binary tree that ends in Values (Left and Right)
Value - a key / value pair where the key is a ChainID and the value
is the hash of the state of the chain
The BPT can be updated many times, then updated in batch (which reduces the hashes that have to be performed to update the summary hash)
func NewBPT ¶
func NewBPT() *BPT
New BPT Allocate a new BPT and set up the structures required to get to work with Binary Patricia Trees.
func (*BPT) GetDirtyList ¶
GetDirtyList Convert the map to a list (must work down from the highest heights to the root (to keep from stomping on hashing orders; all hashes at the same height are independent of each other, but must be computed before we handle the next lowest height, and so forth.
func (*BPT) IsDirty ¶
IsDirty Sort if a node is in the dirty tracking. Allows batching updates for greater efficiency.
func (*BPT) Marshal ¶
Marshal Must have the MaxNodeID at the very least to be able to add nodes to the BPT
func (*BPT) MarshalByteBlock ¶
MarshalByteBlock Given the node leading into a byte block, marshal all the nodes within the block. A borderNode is a node that completes a byte boundry. So consider a theoretical key 03e706b93d2e515c6eff056ee481eb92f9e790277db91eb748b3cc5b46dfe8ca The first byte is 03, second is a7, third is 06 etc.
The node in block 03 that completes e7 is the board node. The Left path would begin the path to the theoretical key (a bit zero).
func (*BPT) MarshalEntry ¶
MarshalEntry Recursive routine that marshals a byte block starting from an entry on the Left or on the Right. Calling MarshalEntry from the Left only marshals half the node space of a byte block. Have to call MarshalEntry from the Right to complete coverage.
func (*BPT) NewNode ¶
NewNode Allocate a new Node for use with this BPT. Note that various bookkeeping tasks are performed for the caller.
func (*BPT) UnMarshal ¶
UnMarshal Load the BPT in support of initialization from disk. Note that an existing BPT will be over written completely.
func (*BPT) UnMarshalByteBlock ¶
UnMarshalByteBlock
func (*BPT) UnMarshalEntry ¶
type Entry ¶
type Entry interface {
T() int // Returns the type of entry
GetHash() []byte // Returns the Hash for the entry
Marshal() []byte // Serialize the state of the Node or Value
UnMarshal(data []byte) []byte // Unmarshal the state into the Node or Value
Equal(entry Entry) bool // Return Entry == entry
}
Entry We only have two node types, a Node that builds the Patricia Tree, and a Value that holds the values at the leaves.
type Manager ¶
type Manager struct {
DBManager *database.Manager
Dirty []*Node
Bpt *BPT
LoadedBB map[[32]byte]*Node
}
func NewBPTManager ¶
NewBPTManager Get a new BPTManager which keeps the BPT on disk. If the BPT is on disk, then it can be reloaded as needed.
type Node ¶
type Node struct {
ID uint64 // Node Count
Height int // Root is 0. above root is 1. Above above root is 2, etc.
BBKey [32]byte // Byte Block Key.
Hash [32]byte // This is the summary hash for the tree
Left Entry // The hash of the child Left and up the tree, bit is zero
Right Entry // the hash to the child Right and up the tree, bit is one
Parent *Node // the Parent node "below" this node
}
func (*Node) GetHash ¶
GetHash Returns the Hash value for computing the summary hash of the BPT. By being in the interface, it does eliminate some book keeping where a node easily has L and R nodes, but doesn't know if those are Node or Value instances.
func (*Node) GetID ¶
GetID Returns the ID for this node. This is used to compare nodes and serve as a key in the BPT.DirtyMap.
func (*Node) Marshal ¶
Marshal Serialize the fields of the Node. Note this doesn't do too much towards fitting the node into the actual BPT, but it helps a bit.
See (p *BPT)MarshalByteBlock
type Value ¶
type Value struct {
Key [32]byte // The key for the Patricia Tree value
Hash [32]byte // The current value for the key
}
Value holds the key / hash mapping for the BPT. With Accumulate, the key represents a ChainID and a state Hash for a chain in the protocol
func (*Value) Equal ¶
Equal Return true if a given Entry is a Value instance, and has the same Key and Hash as this Value
func (*Value) GetHash ¶
GetHash Returns the combination hash of the Key and the Hash. This is the state that really must be proven to users
Source Files