com.hazelcast.wan.merkletree

Class MerkleTreeUtil

java.lang.Object

com.hazelcast.wan.merkletree.MerkleTreeUtil

public final class MerkleTreeUtil
extends Object

Utility methods for Merkle tree implementation

Method Summary

Modifier and Type	Method and Description
static Collection<Integer>	compareTrees(com.hazelcast.wan.merkletree.MerkleTreeView local, com.hazelcast.wan.merkletree.MerkleTreeView remote) Compares the provided local and the remote Merkle trees and returns the breadth-first orders of the leaves that found to be different.
static RemoteMerkleTreeView	createRemoteMerkleTreeView(DataInput in) Creates a RemoteMerkleTreeView by reading the hashes of the leaves of a Merkle tree from the provided DataInput
static int	getLeftChildOrder(int nodeOrder) Returns the breadth-first order of the left child node of the node with nodeOrder
static int	getLevelOfNode(int nodeOrder) Returns the level a node with the given order is on in the tree
static int	getNodesOnLevel(int level) Returns the number of nodes on the provided level
static int	getParentOrder(int nodeOrder) Returns the breadth-first order of the parent node of the node with nodeOrder
static int	getRightChildOrder(int nodeOrder) Returns the breadth-first order of the right child node of the node with nodeOrder
static int	sumHash(int leftHash, int rightHash) Sums the hash of the left and the right children
static void	writeLeaves(DataOutput out, com.hazelcast.wan.merkletree.MerkleTreeView merkleTreeView) Writes the hashes of the leaves of a Merkle tree into the provided DataOutput

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

sumHash

public static int sumHash(int leftHash,
                          int rightHash)

Sums the hash of the left and the right children

May be used only when calculating a non-leaf node's hash code from its children's hashes.

Parameters:

leftHash - The hash of the left child

rightHash - The hash of the right child

Returns:

the accumulated hash

See Also:

addHash(int, int), removeHash(int, int)

getLevelOfNode

public static int getLevelOfNode(int nodeOrder)

Returns the level a node with the given order is on in the tree

Parameters:

nodeOrder - The breadth-first order of a node for which its level to be calculated

Returns:

the level which the node with order is on

getNodesOnLevel

public static int getNodesOnLevel(int level)

Returns the number of nodes on the provided level

Parameters:

level - The level

Returns:

the number of the nodes on the given level

getParentOrder

public static int getParentOrder(int nodeOrder)

Returns the breadth-first order of the parent node of the node with nodeOrder

Parameters:

nodeOrder - The order of the node for which its parent's order to be calculated

Returns:

the order of the parent node

getLeftChildOrder

public static int getLeftChildOrder(int nodeOrder)

Returns the breadth-first order of the left child node of the node with nodeOrder

Parameters:

nodeOrder - The order of the node for which its left child's order to be calculated

Returns:

the order of the left child node

getRightChildOrder

public static int getRightChildOrder(int nodeOrder)

Returns the breadth-first order of the right child node of the node with nodeOrder

Parameters:

nodeOrder - The order of the node for which its right child's order to be calculated

Returns:

the order of the right child node

compareTrees

public static Collection<Integer> compareTrees(com.hazelcast.wan.merkletree.MerkleTreeView local,
                                               com.hazelcast.wan.merkletree.MerkleTreeView remote)

Compares the provided local and the remote Merkle trees and returns the breadth-first orders of the leaves that found to be different.

This method compares only the leaves instead of traversing only the subtrees that are different. This way possible hash collisions inside the tree don't remain hidden and then syncing the clusters can be initiated. This comes at the cost of comparing every leaf at every comparison.

Parameters:

local - The view of the local Merkle tree

remote - The view of the remote Merkle tree

Returns:

the order of the leaves found to be different

writeLeaves

public static void writeLeaves(DataOutput out,
                               com.hazelcast.wan.merkletree.MerkleTreeView merkleTreeView)
                        throws IOException

Writes the hashes of the leaves of a Merkle tree into the provided DataOutput

Parameters:

out - The data output to write the leaves into

merkleTreeView - The Merkle tree which leaves to be written into the data output

Throws:

IOException - if an I/O error occurs

createRemoteMerkleTreeView

public static RemoteMerkleTreeView createRemoteMerkleTreeView(DataInput in)
                                                       throws IOException

Creates a RemoteMerkleTreeView by reading the hashes of the leaves of a Merkle tree from the provided DataInput

Parameters:

in - The data input the hashes to be read from

Returns:

the view representing the remote Merkle tree

Throws:

IOException - if an I/O error occurs