Documentation
¶
Index ¶
- Constants
- func GetChildrenNodeKeys(nodeKey [32]byte) (left, right [32]byte, ok bool)
- func GetHash(e Entry) []byte
- func GetHtKey(nodeKey [32]byte) (height int, key [32]byte, ok bool)
- func GetNodeKey(height int, key [32]byte) (nodeKey [32]byte, ok bool)
- type BPT
- func (b *BPT) Clean(node *BptNode)
- func (b *BPT) CollectReceipt(BIdx, bit byte, node *BptNode, key [32]byte, receipt *managed.Receipt) (hash []byte)
- func (b *BPT) Dirty(node *BptNode)
- func (b *BPT) EnsureRootHash()
- func (b *BPT) Equal(b2 *BPT) (equal bool)
- func (b *BPT) Get(node *BptNode, key [32]byte) (highest *BptNode, entry *Entry, found bool)
- func (b *BPT) GetDirtyList() (list []*BptNode)
- func (b *BPT) GetRange(startKey [32]byte, count int) (values []*Value, lastKey [32]byte)
- func (b *BPT) GetReceipt(chainID [32]byte) *managed.Receipt
- func (b *BPT) GetRoot() (root *BptNode)
- func (b *BPT) Insert(key, hash [32]byte)
- func (b *BPT) IsDirty(node *BptNode) bool
- func (b *BPT) LoadNext(BIdx, bit byte, node *BptNode, key [32]byte)
- func (b *BPT) Marshal() (data []byte)
- func (b *BPT) MarshalByteBlock(borderNode *BptNode) (data []byte)
- func (b *BPT) MarshalEntry(entry Entry, data []byte) []byte
- func (b *BPT) NewNode(key [32]byte, parent *BptNode) (node *BptNode)
- func (b *BPT) NewValue(parent *BptNode, key, hash [32]byte) (value *Value)
- func (b *BPT) Print(entry Entry)
- func (b *BPT) UnMarshal(data []byte) (newData []byte)
- func (b *BPT) UnMarshalByteBlock(borderNode *BptNode, data []byte) []byte
- func (b *BPT) UnMarshalEntry(parent *BptNode, data []byte) (Entry, []byte)
- func (b *BPT) Update()
- func (b *BPT) WalkRange(found *bool, node *BptNode, count int, key [32]byte, values []*Value) []*Value
- type BptNode
- type Entry
- type Manager
- 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 ¶
func GetChildrenNodeKeys ¶ added in v0.5.1
GetLeftNodeKey Computes the nodeKey that a left branch from a BptNode must have
func GetHtKey ¶ added in v0.5.1
GetHtKey Extract the height and Key fragment from a nodeKey. The reverse operation of GetNodeKey Mostly useful for debugging and testing
func GetNodeKey ¶ added in v0.5.1
GetNodeKey We need a key to address nodes in the protocol. These nodes need a unique key for debugging purposes. We return the key with height number of bits followed by a one end bit followed by all bits clear Heights greater than 255 (0-254) bits are not supported.
Types ¶
type BPT ¶
type BPT struct {
RootHash [32]byte // Root hash of the BPT
Root *BptNode // The root of the Patricia Tree, holding the summary hash for the Patricia Tree
DirtyMap map[[32]byte]*BptNode // Map of dirty nodes.
MaxHeight int // Highest height of any node in the BPT
NumNodes uint64 // number of nodes in the BPT
// 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) CollectReceipt ¶
func (b *BPT) CollectReceipt(BIdx, bit byte, node *BptNode, key [32]byte, receipt *managed.Receipt) (hash []byte)
CollectReceipt A recursive routine that searches the BPT for the given chainID. Once it is found, the search unwinds and builds the receipt.
Inputs: BIdx -- byte index into the key bit -- index to the bit node -- the node in the BPT where we have reached in our search so far key -- The key in the BPT we are looking for
func (*BPT) EnsureRootHash ¶
func (b *BPT) EnsureRootHash()
func (*BPT) Get ¶ added in v0.5.1
Get Return the highest node that exists on the path to a particular node, and the entry along the path
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) GetRange ¶ added in v0.5.1
Insert Starts the search of the BPT for the location of the key in the BPT
func (*BPT) GetReceipt ¶
GetReceipt Returns the receipt for the current state for the given chainID
func (*BPT) GetRoot ¶ added in v0.5.1
GetRoot Get the Root node for the BPT. This may load the BPT Root node from disk if not loaded yet.
func (*BPT) IsDirty ¶
IsDirty Sort if a node is in the dirty tracking. Allows batching updates for greater efficiency.
func (*BPT) LoadNext ¶ added in v0.5.1
LoadNext Load the next level of nodes if it is necessary. We build Byte Blocks of nodes which store all the nodes and values within 8 bits of a key. If the key is longer, certainly there will be more Byte Blocks 8 bits later.
Note if a Byte Block is loaded, then the node passed in is replaced by the node loaded.
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 boundary. 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 ¶
func (*BPT) Update ¶
func (b *BPT) Update()
Update the Patricia Tree hashes with the values from the updates since the last update
func (*BPT) WalkRange ¶ added in v0.5.1
func (b *BPT) WalkRange(found *bool, node *BptNode, count int, key [32]byte, values []*Value) []*Value
WalkRange A recursive routine that pushes collisions towards the leaves of the binary patricia tree until the keys don't match any more. Note that this tree cannot handle duplicate keys, but that is an assumption of patricia trees anyway
Inputs: node -- the node in the BPT where the value (key, hash) is being inserted count -- the number of hashes to collect key -- The key in the BPT which determines were in the BPT the hash goes hash -- The current value of the key, as tracked by the BPT
type BptNode ¶
type BptNode struct {
Height int // Root is 0. above root is 1. Above above root is 2, etc.
NodeKey [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 *BptNode // the Parent node "below" this node
}
func (*BptNode) 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 (*BptNode) 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 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 storage.KeyValueTxn
Dirty []*BptNode
Bpt *BPT
}
func NewBPTManager ¶
func NewBPTManager(dbManager storage.KeyValueTxn) *Manager
NewBPTManager Get a new BPTManager which keeps the BPT on disk. If the BPT is on disk, then it can be reloaded as needed.
func (*Manager) GetRootHash ¶
GetRootHash Note this provides the root hash (generally) of the previous hash of the entire BPT. If called JUST after a call to Update() then it returns the current root hash, which would be true up to the point that any node in the BPT is updated.
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
Source Files