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 ++++++--------------- .../api/listener/ListenableCbsConfigTest.java | 6 +- .../client/api/listener/MerkleTreeParserTest.java | 34 +-- .../cbs/client/api/listener/MerkleTreeTest.java | 45 ++-- 4 files changed, 116 insertions(+), 215 deletions(-) (limited to 'rest-services/cbs-client/src') 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); } diff --git a/rest-services/cbs-client/src/test/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/ListenableCbsConfigTest.java b/rest-services/cbs-client/src/test/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/ListenableCbsConfigTest.java index 3e77251d..e5cb4f11 100644 --- a/rest-services/cbs-client/src/test/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/ListenableCbsConfigTest.java +++ b/rest-services/cbs-client/src/test/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/ListenableCbsConfigTest.java @@ -46,7 +46,7 @@ class ListenableCbsConfigTest { cut.listen(List.of("some-key"), subtreeOption -> actualChanges.updateAndGet( - changes -> changes.append(subtreeOption.flatMap(subtree -> subtree.get()).getOrElse("[None]"))) + changes -> changes.append(subtreeOption.flatMap(subtree -> subtree.get(List.empty())).getOrElse("[None]"))) ); @@ -77,7 +77,7 @@ class ListenableCbsConfigTest { cut.subtreeChanges(List.of("some-key")) .map(subtreeOption -> - subtreeOption.flatMap(subtree -> subtree.get()).getOrElse("[None]") + subtreeOption.flatMap(subtree -> subtree.get(List.empty())).getOrElse("[None]") ) .subscribe(replayProcessor); @@ -107,7 +107,7 @@ class ListenableCbsConfigTest { cut.subtreeChanges(List.of("streams", "publishes")) .map(subtreeOption -> - subtreeOption.flatMap(subtree -> subtree.get("topic1", "dmaap-url")).getOrElse("[None]") + subtreeOption.flatMap(subtree -> subtree.get(List.of("topic1", "dmaap-url"))).getOrElse("[None]") ) .subscribe(actualChanges); diff --git a/rest-services/cbs-client/src/test/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/MerkleTreeParserTest.java b/rest-services/cbs-client/src/test/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/MerkleTreeParserTest.java index 080f8097..c9ceeaf1 100644 --- a/rest-services/cbs-client/src/test/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/MerkleTreeParserTest.java +++ b/rest-services/cbs-client/src/test/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/MerkleTreeParserTest.java @@ -22,6 +22,7 @@ package org.onap.dcaegen2.services.sdk.rest.services.cbs.client.api.listener; import com.google.gson.JsonArray; import com.google.gson.JsonObject; +import io.vavr.collection.List; import org.jetbrains.annotations.NotNull; import org.junit.jupiter.api.Test; @@ -39,8 +40,7 @@ class MerkleTreeParserTest { JsonObject jsonObject = new JsonObject(); MerkleTree tree = cut.fromJsonObject(jsonObject); - - assertThat(tree.isSame(emptyTree())).isTrue(); + assertThat(tree.isSame(List.empty(), emptyTree())).isTrue(); } @Test @@ -51,7 +51,7 @@ class MerkleTreeParserTest { MerkleTree tree = cut.fromJsonObject(jsonObject); MerkleTree expected = emptyTree() - .add("v1", "p1"); + .add(List.of("p1"), "v1"); assertThat(tree).isEqualTo(expected); } @@ -67,7 +67,7 @@ class MerkleTreeParserTest { MerkleTree tree = cut.fromJsonObject(jsonObject); MerkleTree expected = emptyTree() - .add("v1", "p1", "p2", "p3"); + .add(List.of("p1", "p2", "p3"), "v1"); assertThat(tree).isEqualTo(expected); } @@ -82,8 +82,8 @@ class MerkleTreeParserTest { MerkleTree tree = cut.fromJsonObject(jsonObject); MerkleTree expected = emptyTree() - .add("vA", "p1", "A") - .add("vB", "p1", "B"); + .add(List.of("p1", "A"), "vA") + .add(List.of("p1", "B"), "vB"); assertThat(tree).isEqualTo(expected); } @@ -100,8 +100,8 @@ class MerkleTreeParserTest { MerkleTree tree = cut.fromJsonObject(jsonObject); MerkleTree expected = emptyTree() - .add("v1", "p1", "0") - .add("v2", "p1", "1", "p2"); + .add(List.of("p1", "0"), "v1") + .add(List.of("p1", "1", "p2"), "v2"); assertThat(tree).isEqualTo(expected); } @@ -123,10 +123,10 @@ class MerkleTreeParserTest { MerkleTree tree = cut.fromJsonObject(jsonObject); MerkleTree expected = emptyTree() - .add("v1", "p1") - .add("v2", "p2", "0") - .add("v3", "p2", "1") - .add("v4", "p3", "p4"); + .add(List.of("p1"), "v1") + .add(List.of("p2", "0"), "v2") + .add(List.of("p2", "1"), "v3") + .add(List.of("p3", "p4"), "v4"); assertThat(tree).isEqualTo(expected); } @@ -144,11 +144,11 @@ class MerkleTreeParserTest { MerkleTree tree = cut.fromJsonObject(jsonObject); MerkleTree expected = emptyTree() - .add("1", "p1", "0") - .add("2", "p1", "1") - .add("3.0", "p1", "2") - .add("true", "p1", "3") - .add("999799799799799", "p1", "4"); + .add(List.of("p1", "0"), "1") + .add(List.of("p1", "1"), "2") + .add(List.of("p1", "2"), "3.0") + .add(List.of("p1", "3"), "true") + .add(List.of("p1", "4"), "999799799799799"); assertThat(tree).isEqualTo(expected); } diff --git a/rest-services/cbs-client/src/test/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/MerkleTreeTest.java b/rest-services/cbs-client/src/test/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/MerkleTreeTest.java index 2a9a7fcd..b24ff2ee 100644 --- a/rest-services/cbs-client/src/test/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/MerkleTreeTest.java +++ b/rest-services/cbs-client/src/test/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/MerkleTreeTest.java @@ -22,6 +22,7 @@ package org.onap.dcaegen2.services.sdk.rest.services.cbs.client.api.listener; import static org.assertj.core.api.Assertions.assertThat; +import io.vavr.collection.List; import org.junit.jupiter.api.Test; import org.onap.dcaegen2.services.sdk.rest.services.cbs.client.api.listener.MerkleTree; @@ -34,38 +35,38 @@ class MerkleTreeTest { @Test void shouldBeAbleToGetEntries() { MerkleTree cut = emptyTree() - .add("value1", "ala", "ma", "kota") - .add("value2", "ala", "ma", "psa"); + .add(List.of("ala","ma", "kota"), "value1") + .add(List.of("ala", "ma", "psa"),"value2"); - assertThat(cut.get("ala", "ma", "kota")).contains("value1"); - assertThat(cut.get("ala", "ma", "psa")).contains("value2"); + assertThat(cut.get(List.of("ala", "ma", "kota"))).contains("value1"); + assertThat(cut.get(List.of("ala", "ma", "psa"))).contains("value2"); } @Test void shouldReturnNoneForNonExistingPaths() { MerkleTree cut = emptyTree() - .add("value1", "ala", "ma", "kota") - .add("value2", "ala", "ma", "psa"); + .add(List.of("ala", "ma", "kota"), "value1") + .add(List.of("ala", "ma", "psa"),"value2"); - assertThat(cut.get("ala", "je", "obiad")).isEmpty(); + assertThat(cut.get(List.of("ala", "je", "obiad"))).isEmpty(); } @Test void shouldReturnNoneWhenNodeDoesntContainValue() { MerkleTree cut = emptyTree() - .add("value1", "ala", "ma", "kota") - .add("value2", "ala", "ma", "psa"); + .add(List.of("ala", "ma", "kota"),"value1") + .add(List.of("ala", "ma", "psa"), "value2"); - assertThat(cut.get("ala", "ma")).isEmpty(); + assertThat(cut.get(List.of("ala", "ma"))).isEmpty(); } @Test void shouldNotCreateNewObjectWhenNothingChanged() { MerkleTree cut = emptyTree() - .add("some value", "ala", "ma", "kota"); + .add(List.of("ala", "ma", "kota"), "some value"); - final MerkleTree result = cut.add("some value", "ala", "ma", "kota"); + final MerkleTree result = cut.add(List.of("ala", "ma", "kota"),"some value"); assertThat(result).isSameAs(cut); } @@ -73,21 +74,21 @@ class MerkleTreeTest { @Test void shouldRecalculateHashesAfterAddingNewNode() { MerkleTree cut = emptyTree() - .add("value1", "ala", "ma", "kota") - .add("value2", "ala", "ma", "psa") - .add("value3", "ala", "name"); + .add(List.of("ala", "ma", "kota"), "value1") + .add(List.of("ala", "ma", "psa"), "value2") + .add(List.of("ala", "name"), "value3"); - final MerkleTree modified = cut.add("value4", "ala", "surname"); + final MerkleTree modified = cut.add(List.of("ala", "surname"), "value4"); assertThat(modified).isNotSameAs(cut); - assertThat(modified.hashOf("ala", "ma")).isEqualTo(cut.hashOf("ala", "ma")); - assertThat(modified.hashOf("ala", "ma", "kota")).isEqualTo(cut.hashOf("ala", "ma", "kota")); - assertThat(modified.hashOf("ala", "ma", "psa")).isEqualTo(cut.hashOf("ala", "ma", "psa")); - assertThat(modified.hashOf("ala", "name")).isEqualTo(cut.hashOf("ala", "name")); + assertThat(modified.hashOf(List.of("ala", "ma"))).isEqualTo(cut.hashOf(List.of("ala", "ma"))); + assertThat(modified.hashOf(List.of("ala", "ma", "kota"))).isEqualTo(cut.hashOf(List.of("ala", "ma", "kota"))); + assertThat(modified.hashOf(List.of("ala", "ma", "psa"))).isEqualTo(cut.hashOf(List.of("ala", "ma", "psa"))); + assertThat(modified.hashOf(List.of("ala", "name"))).isEqualTo(cut.hashOf(List.of("ala", "name"))); - assertThat(modified.hashOf("ala", "surname")).isNotEqualTo(cut.hashOf("ala", "surname")); - assertThat(modified.hashOf("ala")).isNotEqualTo(cut.hashOf("ala")); + assertThat(modified.hashOf(List.of("ala", "surname"))).isNotEqualTo(cut.hashOf(List.of("ala", "surname"))); + assertThat(modified.hashOf(List.of("ala"))).isNotEqualTo(cut.hashOf(List.of("ala"))); assertThat(modified.hash()).isNotEqualTo(cut.hash()); } -- cgit 1.2.3-korg