Merkle tree data structure
- class swh.model.merkle.MerkleNode(data=None)#
Representation of a node in a Merkle Tree.
A (generalized) Merkle Tree is a tree in which every node is labeled with a hash of its own data and the hash of its children.
node.hash = hash(node.data + sum(child.hash for child in node.children))
This class efficiently implements the Merkle Tree data structure on top of a Python
dict, minimizing hash computations and new data collections when updating nodes.
Node data is stored in the
dataattribute, while (named) children are stored as items of the underlying dictionary.
Addition, update and removal of objects are instrumented to automatically invalidate the hashes of the current node as well as its registered parents; It also resets the collection status of the objects so the updated objects can be collected.
The collection of updated data from the tree is implemented through the
collect()function and associated helpers.
Invalidate the cached hash of the current node.
- update_hash(*, force=False) Any #
Recursively compute the hash of the current node.
force (bool) – invalidate the cache and force the computation for this node and all children.
- abstract compute_hash() Any #
Compute the hash of the current node.
The hash should depend on the data of the node, as well as on hashes of the children nodes.
Add several named children from a dictionary
Retrieve and format the collected data for the current node, for use by
Can be overridden, for instance when you want the collected data to contain information about the child nodes.
- collect_node() Set[MerkleNode] #
Collect the current node if it has not been yet, for use by
- collect() Set[MerkleNode] #
Collect the added and modified nodes in the subtree rooted at self since the last collect operation.
setof collected nodes
Recursively unmark collected nodes in the subtree rooted at self.
This lets the caller use