From cfdbdae4e7ef655a579349426fdd2779841264ad Mon Sep 17 00:00:00 2001 From: Izabela Zawadzka Date: Fri, 1 Mar 2019 09:17:26 +0100 Subject: Merge MerkleTree and MTNode Change-Id: Iffe72a0f40a8e608fa7f0a6424eacc21f196e167 Issue-ID: DCAEGEN2-1303 Signed-off-by: Izabela Zawadzka --- .../cbs/client/api/listener/MerkleTree.java | 246 ++++++--------------- 1 file changed, 73 insertions(+), 173 deletions(-) (limited to 'rest-services/cbs-client/src/main') diff --git a/rest-services/cbs-client/src/main/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/MerkleTree.java b/rest-services/cbs-client/src/main/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/MerkleTree.java index 837a1ca7..831ffdf7 100644 --- a/rest-services/cbs-client/src/main/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/MerkleTree.java +++ b/rest-services/cbs-client/src/main/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/MerkleTree.java @@ -46,17 +46,23 @@ public final class MerkleTree { private static final String DEFAULT_DIGEST_ALGORITHM = "SHA-256"; private final ValueSerializer valueSerializer; + private final byte[] hash; + private final Option value; + private final Map> children; private final HashAlgorithm hashAlgorithm; - private final MTNode root; private final Function1 hashForValue; private MerkleTree( @NotNull ValueSerializer valueSerializer, @NotNull HashAlgorithm hashAlgorithm, - @NotNull MTNode root) { - this.valueSerializer = Objects.requireNonNull(valueSerializer); + @NotNull byte[] hash, + @NotNull Option value, + @NotNull Map> children) { this.hashAlgorithm = Objects.requireNonNull(hashAlgorithm); - this.root = Objects.requireNonNull(root); + this.valueSerializer = Objects.requireNonNull(valueSerializer); + this.hash = Objects.requireNonNull(hash.clone()); + this.value = Objects.requireNonNull(value); + this.children = Objects.requireNonNull(children); hashForValue = valueSerializer.andThen(hashAlgorithm); } @@ -64,7 +70,7 @@ public final class MerkleTree { * Create an empty tree with given serializer and using default digest algorithm as a hash function. * * @param serializer a way of serializing a value to array of bytes - * @param type of values kept in a tree + * @param type of values kept in a tree * @return empty tree */ public static @NotNull MerkleTree emptyWithDefaultDigest(@NotNull ValueSerializer serializer) { @@ -75,8 +81,8 @@ public final class MerkleTree { * Create an empty tree with given serializer and given digest algorithm used as a hash function. * * @param digestAlgorithmName name of a digest algorithm as used by {@link MessageDigest#getInstance(String)} - * @param serializer a way of serializing a value to array of bytes - * @param type of values kept in a tree + * @param serializer a way of serializing a value to array of bytes + * @param type of values kept in a tree * @return empty tree */ public static @NotNull MerkleTree emptyWithDigest( @@ -92,13 +98,18 @@ public final class MerkleTree { /** * Create an empty tree with given hash function. * - * @param serializer a function which serializes values to a byte array + * @param serializer a function which serializes values to a byte array * @param hashAlgorithm a function which calculates a hash of a serialized value - * @param type of values kept in a tree + * @param type of values kept in a tree * @return empty tree */ + public static MerkleTree emptyWithHashProvider(ValueSerializer serializer, HashAlgorithm hashAlgorithm) { - return new MerkleTree<>(serializer, hashAlgorithm, MTNode.empty(hashAlgorithm)); + return MerkleTree.empty(serializer, hashAlgorithm); + } + + private static MerkleTree empty(@NotNull ValueSerializer serializer, HashAlgorithm hashAlgorithm) { + return new MerkleTree<>(serializer, hashAlgorithm, new byte[0], Option.none(), HashMap.empty()); } private static MessageDigest messageDigest(String digestAlgorithmName) { @@ -109,74 +120,71 @@ public final class MerkleTree { } } - /** - * Assigns a value to a given path. - * - * Overrides current value if already exists. - * - * @param value a value to assign - * @param path path of labels from root - * @return an updated tree instance or this if hashes are the same - */ - public MerkleTree add(V value, String... path) { - return add(List.of(path), value); - } /** * Assigns a value to a given path. - * + *

* Overrides current value if already exists. * - * @param path path of labels from root + * @param path path of labels from root * @param value a value to assign * @return an updated tree instance or this if hashes are the same */ + public MerkleTree add(List path, V value) { - final MTNode result = root.addChild(path, MTNode.leaf(hashAlgorithm, hashForValue.apply(value), value)); - return Arrays.equals(result.hash(), root.hash()) - ? this - : new MerkleTree<>(valueSerializer, hashAlgorithm, result); + return addSubtree(path, leaf(value)); } + private MerkleTree addSubtree(final List path, final MerkleTree subtree) { + if (path.isEmpty()) { + return subtree; + } else { + String label = path.head(); + MerkleTree newSubtree = children.get(label).fold( + () -> MerkleTree.empty(valueSerializer, hashAlgorithm).addSubtree(path.tail(), subtree), + node -> node.addSubtree(path.tail(), subtree) + ); + return addSubtree(label, newSubtree); + } + } - /** - * Gets a value assigned to a given path. - * - * @param path to search for - * @return Some(value) if path exists and contains a value, None otherwise - */ - public Option get(String... path) { - return get(List.of(path)); + private MerkleTree addSubtree(String label, MerkleTree subtree) { + final Map> newSubtrees = children.put(label, subtree); + byte[] newHash = composeHashes(newSubtrees.iterator(this::hashForSubtree)); + return Arrays.equals(newHash, hash) ? this : new MerkleTree<>( + valueSerializer, + hashAlgorithm, + newHash, + value, + newSubtrees + ); } - /** - * Gets a value assigned to a given path. - * - * @param path to search for - * @return Some(value) if path exists and contains a value, None otherwise - */ - public Option get(List path) { - return root.findNode(path).flatMap(MTNode::value); + private MerkleTree leaf(V value) { + return new MerkleTree<>(valueSerializer, hashAlgorithm, hashForValue.apply(value), Option.of(value), HashMap.empty()); } /** - * Checks if nodes under given path are the same in {@code this} and {@code other} tree. + * Returns a subtree with given node as a root. * - * @param other a tree to compare with - * @param path a path to a subtree to compare - * @return true if hashes are the same, false otherwise + * @param path a path of a node to be a subtree root + * @return Some(subtree) if path exists, None otherwise */ - public boolean isSame(MerkleTree other, String... path) { - return isSame(List.of(path), other); + public Option> subtree(List path) { + return path.headOption().fold( + () -> Option.of(this), + head -> children.get(head).flatMap(subtree -> subtree.subtree(path.tail())) + ); } /** * Checks if nodes under given path are the same in {@code this} and {@code other} tree. * * @param other a tree to compare with - * @param path a path to a subtree to compare + * @param path a path to a subtree to compare * @return true if hashes are the same, false otherwise */ + public boolean isSame(List path, MerkleTree other) { final byte[] oldHash = other.hashOf(path); final byte[] curHash = hashOf(path); @@ -189,142 +197,34 @@ public final class MerkleTree { * @param path a path of a node to check * @return a hash or empty array if node does not exist */ + public byte[] hashOf(List path) { - return root - .findNode(path) - .map(node -> node.hash().clone()) + return subtree(path) + .map(MerkleTree::hash) .getOrElse(() -> new byte[0]); } /** - * Returns a hash of a node under given path. - * - * @param path a path of a node to check - * @return a hash or empty array if node does not exist - */ - public byte[] hashOf(String... path) { - return hashOf(List.of(path)); - } - - /** - * Returns a subtree with given node as a root. - * - * @param path a path of a node to be a subtree root - * @return Some(subtree) if path exists, None otherwise - */ - public Option> subtree(List path) { - return root.findNode(path).map(node -> new MerkleTree<>(valueSerializer, hashAlgorithm, node)); - } - - /** - * Returns a subtree with given node as a root. - * - * @param path a path of a node to be a subtree root - * @return Some(subtree) if path exists, None otherwise - */ - public Option> subtree(String... path) { - return subtree(List.of(path)); - } - - /** - * Hash of a root node. + * Gets a value assigned to a given path. * - * @return a copy of root node's hash + * @param path to search for + * @return Some(value) if path exists and contains a value, None otherwise */ - public byte[] hash() { - return root.hash().clone(); - } - - @Override - public String toString() { - return root.toString(); - } - - @Override - public boolean equals(Object o) { - if (this == o) { - return true; - } - if (o == null || getClass() != o.getClass()) { - return false; - } - MerkleTree that = (MerkleTree) o; - return Objects.equals(root, that.root); - } - - @Override - public int hashCode() { - return Objects.hash(root); - } -} -final class MTNode { - - private final byte[] hash; - private final Option value; - private final Map> children; - private final HashAlgorithm hashAlgorithm; - - static MTNode empty(HashAlgorithm hashAlgorithm) { - return new MTNode<>(hashAlgorithm, new byte[0], Option.none(), HashMap.empty()); - } - - static MTNode leaf(HashAlgorithm hashAlgorithm, byte[] hash, V value) { - return new MTNode<>(hashAlgorithm, hash, Option.of(value), HashMap.empty()); - } - - private MTNode( - HashAlgorithm hashAlgorithm, - byte[] hash, - Option value, - Map> children) { - this.hashAlgorithm = hashAlgorithm; - this.hash = hash.clone(); - this.value = value; - this.children = children; - } - - MTNode addChild(final List path, final MTNode child) { - if (path.isEmpty()) { - return child; - } else { - String label = path.head(); - MTNode newChild = children.get(label).fold( - () -> MTNode.empty(hashAlgorithm).addChild(path.tail(), child), - node -> node.addChild(path.tail(), child) - ); - return addChild(label, newChild); - } - } - - Option value() { - return value; - } - - Option> findNode(List path) { - return path.headOption().fold( - () -> Option.of(this), - head -> children.get(head).flatMap(child -> child.findNode(path.tail())) - ); + public Option get(List path) { + return subtree(path).flatMap(MerkleTree::value); } byte[] hash() { - return hash; + return hash.clone(); } - private MTNode addChild(String label, MTNode child) { - final Map> newChildren = children.put(label, child); - byte[] newHash = composeHashes(newChildren.iterator(this::hashForChild)); - return Arrays.equals(newHash, hash) ? this : new MTNode<>( - hashAlgorithm, - newHash, - value, - newChildren - ); + private Option value() { + return value; } - private byte[] hashForChild(String label, MTNode child) { - return composeHashes(List.of(label.getBytes(), child.hash())); + private byte[] hashForSubtree(String label, MerkleTree subtree) { + return composeHashes(List.of(label.getBytes(), subtree.hash())); } private byte[] composeHashes(Iterable hashes) { @@ -346,7 +246,7 @@ final class MTNode { if (o == null || getClass() != o.getClass()) { return false; } - MTNode mtNode = (MTNode) o; + MerkleTree mtNode = (MerkleTree) o; return Arrays.equals(hash, mtNode.hash); } -- cgit 1.2.3-korg