public class ArrayMerkleTree extends Object implements MerkleTree
MerkleTree
implementation, which
represents each node of the tree as a single int
containing
the node's hash.
The array representation of the tree comes with optimal memory footprint and memory layout. The memory layout is leveraged by the breadth-first (and breadth-last) traversal of the tree such as recalculating the hash for each non-leaf node. This traversal is optimal, since it is a sequential memory walk coming with low CPU cache miss rates, which in the case of a deep tree enables much better performance compared to the linked representation of the tree.
The nodes in this implementation are referenced by their breadth-first order in the tree. Using this order as reference comes with the following properties:
MerkleTreeUtil.getLevelOfNode(int)
MerkleTreeUtil.getNodeHashRangeOnLevel(int)
,
MerkleTreeUtil.getNodeRangeLow(int)
,
MerkleTreeUtil.getNodeRangeHigh(int)
offset = order * NODE_SIZE
.
Every leaf of the tree may cover multiple elements in the underlying
data structure. These elements are key-value pairs and the keys of the
elements are stored in a data structure that are referred to as data
blocks. This implementation stores the keys in OAHashSet
s, one
set for each leaf. These sets are initialized in tree construction time
eagerly with initial capacity one.
This implementation updates the tree synchronously. It can do that,
since updating a leaf's hash doesn't need to access the values belong
to the leaf, thank to the not order-sensitive hash function in use.
See MerkleTreeUtil.addHash(int, int)
,
MerkleTreeUtil.removeHash(int, int)
,
MerkleTreeUtil.sumHash(int, int)
Modifier and Type | Field and Description |
---|---|
protected int |
depth |
protected int |
leafLevelOrder |
protected int[] |
tree |
Constructor and Description |
---|
ArrayMerkleTree(int depth) |
Modifier and Type | Method and Description |
---|---|
void |
clear()
Clears the Merkle tree
|
int |
depth()
Returns the depth of the tree
|
int |
depth()
Returns the depth of the tree
|
long |
footprint()
Returns the memory footprint of Merkle Tree in bytes
|
void |
forEachKeyOfNode(int nodeOrder,
Consumer<Object> consumer)
Performs the given action for each key of the specified node
until all elements have been processed or the action throws an
exception.
|
int |
getNodeHash(int nodeOrder)
Returns the hash for the node with the given
nodeOrder |
int |
getNodeKeyCount(int nodeOrder)
Returns the number of the keys under the specified node.
|
protected void |
setNodeHash(int nodeOrder,
int hash) |
void |
updateAdd(Object key,
Object value)
Updating the tree with adding a new entry to the tree
|
void |
updateRemove(Object key,
Object removedValue)
Updating the tree with removing an entry
|
void |
updateReplace(Object key,
Object oldValue,
Object newValue)
Updating the tree with replacing an old value with a new one
|
protected final int[] tree
protected final int depth
protected final int leafLevelOrder
public void updateAdd(Object key, Object value)
MerkleTree
updateAdd
in interface MerkleTree
key
- The key that value belongs tovalue
- The value of the added entrypublic void updateReplace(Object key, Object oldValue, Object newValue)
MerkleTree
updateReplace
in interface MerkleTree
key
- The key that values belong tooldValue
- The old value of the replaced entrynewValue
- The new value of the replaced entrypublic void updateRemove(Object key, Object removedValue)
MerkleTree
updateRemove
in interface MerkleTree
key
- The key that values belong toremovedValue
- The value of the entry removed from the
underlying data structurepublic int getNodeHash(int nodeOrder)
nodeOrder
nodeOrder
- The order of the nodepublic void forEachKeyOfNode(int nodeOrder, Consumer<Object> consumer)
MerkleTree
The node referenced by nodeOrder
can be either a leaf or a
non-leaf node. In the latter case consumer
is called for
each key that belong the the leaves of the subtree under the
specified node.
This method does not define ordering for the keys belong to the
node nodeOrder
, therefore the caller should not rely on it.
forEachKeyOfNode
in interface MerkleTree
nodeOrder
- The node for which all keysconsumer
- The action which is called for each keypublic int getNodeKeyCount(int nodeOrder)
MerkleTree
The node referenced by nodeOrder
can be either a leaf or a
non-leaf node. In the latter case the method returns with the sum
of the key counts of the subtree under the specified node
getNodeKeyCount
in interface MerkleTree
nodeOrder
- The node for which the key count is queriedpublic long footprint()
MerkleTree
footprint
in interface MerkleTree
public void clear()
MerkleTree
clear
in interface MerkleTree
public int depth()
protected void setNodeHash(int nodeOrder, int hash)
public int depth()
Copyright © 2019 Hazelcast, Inc.. All Rights Reserved.