ArrayMerkleTree (Hazelcast Root 3.12.13 API)

java.lang.Object
- com.hazelcast.wan.merkletree.ArrayMerkleTree

All Implemented Interfaces:

MerkleTree
```
public class ArrayMerkleTree
extends Object
implements MerkleTree
```
A not thread-safe, array based 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:
- The order of a node is unique for each node and refers to the node on the same level and position in every binary tree. This makes a single node easily referable even between clusters.
- The order of a node intrinsically encodes the level of the tree on which the given node is. See MerkleTreeUtil.getLevelOfNode(int)
- The order of a node also intrinsically encodes the hash range that the node covers since the followings are known based on the order:
  1. the level the node is on
  2. the number of the nodes on the same level
  3. the node's relative order from the leftmost node on the same level
  4. because of the points above and that the codomain of the hash function is known (32 bit ints), the range of the hashes that a single node on the given level covers is known, hence the range covered by a concrete node can be calculated. See MerkleTreeUtil.getNodeHashRangeOnLevel(int), MerkleTreeUtil.getNodeRangeLow(int), MerkleTreeUtil.getNodeRangeHigh(int)
- The offset of a node can be calculated easily and cheaply with as 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 OAHashSets, 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)

Field Summary

Fields
Modifier and Type Field and Description

protected int depth

protected int leafLevelOrder

protected int[] tree

Fields
Modifier and Type	Field and Description
`protected int`	`depth`
`protected int`	`leafLevelOrder`
`protected int[]`	`tree`

Constructor Summary

Constructors
Constructor and Description

ArrayMerkleTree(int depth)

Constructors
Constructor and Description
`ArrayMerkleTree(int depth)`

Method Summary

All Methods Instance Methods Abstract Methods Concrete Methods
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

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - tree
```
protected final int[] tree
```
  - depth
```
protected final int depth
```
  - leafLevelOrder
```
protected final int leafLevelOrder
```
- Constructor Detail
  - ArrayMerkleTree
```
public ArrayMerkleTree(int depth)
```
- Method Detail
  - updateAdd
```
public void updateAdd(Object key,
                      Object value)
```
    Description copied from interface: MerkleTree
    
    Updating the tree with adding a new entry to the tree
    
    Specified by:
    
    updateAdd in interface MerkleTree
    
    Parameters:
    
    key - The key that value belongs to
    
    value - The value of the added entry
  - updateReplace
```
public void updateReplace(Object key,
                          Object oldValue,
                          Object newValue)
```
    Description copied from interface: MerkleTree
    
    Updating the tree with replacing an old value with a new one
    
    Specified by:
    
    updateReplace in interface MerkleTree
    
    Parameters:
    
    key - The key that values belong to
    
    oldValue - The old value of the replaced entry
    
    newValue - The new value of the replaced entry
  - updateRemove
```
public void updateRemove(Object key,
                         Object removedValue)
```
    Description copied from interface: MerkleTree
    
    Updating the tree with removing an entry
    
    Specified by:
    
    updateRemove in interface MerkleTree
    
    Parameters:
    
    key - The key that values belong to
    
    removedValue - The value of the entry removed from the underlying data structure
  - getNodeHash
```
public int getNodeHash(int nodeOrder)
```
    Returns the hash for the node with the given nodeOrder
    
    Parameters:
    
    nodeOrder - The order of the node
    
    Returns:
    
    the hash of the node
  - forEachKeyOfNode
```
public void forEachKeyOfNode(int nodeOrder,
                             Consumer<Object> consumer)
```
    Description copied from interface: MerkleTree
    
    Performs the given action for each key of the specified node until all elements have been processed or the action throws an exception.
    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.
    
    Specified by:
    
    forEachKeyOfNode in interface MerkleTree
    
    Parameters:
    
    nodeOrder - The node for which all keys
    
    consumer - The action which is called for each key
  - getNodeKeyCount
```
public int getNodeKeyCount(int nodeOrder)
```
    Description copied from interface: MerkleTree
    
    Returns the number of the keys under the specified node.
    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
    
    Specified by:
    
    getNodeKeyCount in interface MerkleTree
    
    Parameters:
    
    nodeOrder - The node for which the key count is queried
    
    Returns:
    
    the number of the keys under the specified node
  - footprint
```
public long footprint()
```
    Description copied from interface: MerkleTree
    
    Returns the memory footprint of Merkle Tree in bytes
    
    Specified by:
    
    footprint in interface MerkleTree
    
    Returns:
    
    the memory footprint of the Merkle Tree in bytes
  - clear
```
public void clear()
```
    Description copied from interface: MerkleTree
    
    Clears the Merkle tree
    
    Specified by:
    
    clear in interface MerkleTree
  - depth
```
public int depth()
```
    Returns the depth of the tree
    
    Returns:
    
    the depth of the tree
  - setNodeHash
```
protected void setNodeHash(int nodeOrder,
                           int hash)
```
  - depth
```
public int depth()
```
    Returns the depth of the tree
    
    Returns:
    
    the depth of the tree

Class ArrayMerkleTree

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

tree

depth

leafLevelOrder

Constructor Detail

ArrayMerkleTree

Method Detail

updateAdd

updateReplace

updateRemove

getNodeHash

forEachKeyOfNode

getNodeKeyCount

footprint

clear

depth

setNodeHash

depth