diff options
4 files changed, 116 insertions, 215 deletions
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<V> { private static final String DEFAULT_DIGEST_ALGORITHM = "SHA-256"; private final ValueSerializer<V> valueSerializer; + private final byte[] hash; + private final Option<V> value; + private final Map<String, MerkleTree<V>> children; private final HashAlgorithm hashAlgorithm; - private final MTNode<V> root; private final Function1<V, byte[]> hashForValue; private MerkleTree( @NotNull ValueSerializer<V> valueSerializer, @NotNull HashAlgorithm hashAlgorithm, - @NotNull MTNode<V> root) { - this.valueSerializer = Objects.requireNonNull(valueSerializer); + @NotNull byte[] hash, + @NotNull Option<V> value, + @NotNull Map<String, MerkleTree<V>> 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<V> { * 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 <V> type of values kept in a tree + * @param <V> type of values kept in a tree * @return empty tree */ public static @NotNull <V> MerkleTree<V> emptyWithDefaultDigest(@NotNull ValueSerializer<V> serializer) { @@ -75,8 +81,8 @@ public final class MerkleTree<V> { * 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 <V> type of values kept in a tree + * @param serializer a way of serializing a value to array of bytes + * @param <V> type of values kept in a tree * @return empty tree */ public static @NotNull <V> MerkleTree<V> emptyWithDigest( @@ -92,13 +98,18 @@ public final class MerkleTree<V> { /** * 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 <V> type of values kept in a tree + * @param <V> type of values kept in a tree * @return empty tree */ + public static <V> MerkleTree<V> emptyWithHashProvider(ValueSerializer<V> serializer, HashAlgorithm hashAlgorithm) { - return new MerkleTree<>(serializer, hashAlgorithm, MTNode.empty(hashAlgorithm)); + return MerkleTree.empty(serializer, hashAlgorithm); + } + + private static <V> MerkleTree<V> empty(@NotNull ValueSerializer<V> 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<V> { } } - /** - * 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 <code>this</code> if hashes are the same - */ - public MerkleTree<V> add(V value, String... path) { - return add(List.of(path), value); - } /** * Assigns a value to a given path. - * + * <p> * 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 <code>this</code> if hashes are the same */ + public MerkleTree<V> add(List<String> path, V value) { - final MTNode<V> 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<V> addSubtree(final List<String> path, final MerkleTree<V> subtree) { + if (path.isEmpty()) { + return subtree; + } else { + String label = path.head(); + MerkleTree<V> 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<V> get(String... path) { - return get(List.of(path)); + private MerkleTree<V> addSubtree(String label, MerkleTree<V> subtree) { + final Map<String, MerkleTree<V>> 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<V> get(List<String> path) { - return root.findNode(path).flatMap(MTNode::value); + private MerkleTree<V> 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<V> other, String... path) { - return isSame(List.of(path), other); + public Option<MerkleTree<V>> subtree(List<String> 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<String> path, MerkleTree<V> other) { final byte[] oldHash = other.hashOf(path); final byte[] curHash = hashOf(path); @@ -189,142 +197,34 @@ public final class MerkleTree<V> { * @param path a path of a node to check * @return a hash or empty array if node does not exist */ + public byte[] hashOf(List<String> 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<MerkleTree<V>> subtree(List<String> 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<MerkleTree<V>> 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<V> { - - private final byte[] hash; - private final Option<V> value; - private final Map<String, MTNode<V>> children; - private final HashAlgorithm hashAlgorithm; - - static <V> MTNode<V> empty(HashAlgorithm hashAlgorithm) { - return new MTNode<>(hashAlgorithm, new byte[0], Option.none(), HashMap.empty()); - } - - static <V> MTNode<V> leaf(HashAlgorithm hashAlgorithm, byte[] hash, V value) { - return new MTNode<>(hashAlgorithm, hash, Option.of(value), HashMap.empty()); - } - - private MTNode( - HashAlgorithm hashAlgorithm, - byte[] hash, - Option<V> value, - Map<String, MTNode<V>> children) { - this.hashAlgorithm = hashAlgorithm; - this.hash = hash.clone(); - this.value = value; - this.children = children; - } - - MTNode<V> addChild(final List<String> path, final MTNode<V> child) { - if (path.isEmpty()) { - return child; - } else { - String label = path.head(); - MTNode<V> newChild = children.get(label).fold( - () -> MTNode.<V>empty(hashAlgorithm).addChild(path.tail(), child), - node -> node.addChild(path.tail(), child) - ); - return addChild(label, newChild); - } - } - - Option<V> value() { - return value; - } - - Option<MTNode<V>> findNode(List<String> path) { - return path.headOption().fold( - () -> Option.of(this), - head -> children.get(head).flatMap(child -> child.findNode(path.tail())) - ); + public Option<V> get(List<String> path) { + return subtree(path).flatMap(MerkleTree::value); } byte[] hash() { - return hash; + return hash.clone(); } - private MTNode<V> addChild(String label, MTNode<V> child) { - final Map<String, MTNode<V>> 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<V> value() { + return value; } - private byte[] hashForChild(String label, MTNode<V> child) { - return composeHashes(List.of(label.getBytes(), child.hash())); + private byte[] hashForSubtree(String label, MerkleTree<V> subtree) { + return composeHashes(List.of(label.getBytes(), subtree.hash())); } private byte[] composeHashes(Iterable<byte[]> hashes) { @@ -346,7 +246,7 @@ final class MTNode<V> { 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<String> tree = cut.fromJsonObject(jsonObject); - - assertThat(tree.isSame(emptyTree())).isTrue(); + assertThat(tree.isSame(List.empty(), emptyTree())).isTrue(); } @Test @@ -51,7 +51,7 @@ class MerkleTreeParserTest { MerkleTree<String> tree = cut.fromJsonObject(jsonObject); MerkleTree<String> expected = emptyTree() - .add("v1", "p1"); + .add(List.of("p1"), "v1"); assertThat(tree).isEqualTo(expected); } @@ -67,7 +67,7 @@ class MerkleTreeParserTest { MerkleTree<String> tree = cut.fromJsonObject(jsonObject); MerkleTree<String> 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<String> tree = cut.fromJsonObject(jsonObject); MerkleTree<String> 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<String> tree = cut.fromJsonObject(jsonObject); MerkleTree<String> 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<String> tree = cut.fromJsonObject(jsonObject); MerkleTree<String> 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<String> tree = cut.fromJsonObject(jsonObject); MerkleTree<String> 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<String> 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<String> 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<String> 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<String> cut = emptyTree() - .add("some value", "ala", "ma", "kota"); + .add(List.of("ala", "ma", "kota"), "some value"); - final MerkleTree<String> result = cut.add("some value", "ala", "ma", "kota"); + final MerkleTree<String> result = cut.add(List.of("ala", "ma", "kota"),"some value"); assertThat(result).isSameAs(cut); } @@ -73,21 +74,21 @@ class MerkleTreeTest { @Test void shouldRecalculateHashesAfterAddingNewNode() { MerkleTree<String> 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<String> modified = cut.add("value4", "ala", "surname"); + final MerkleTree<String> 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()); } |