aboutsummaryrefslogtreecommitdiffstats
path: root/rest-services/cbs-client/src/main
diff options
context:
space:
mode:
Diffstat (limited to 'rest-services/cbs-client/src/main')
-rw-r--r--rest-services/cbs-client/src/main/java/org/onap/dcaegen2/services/sdk/rest/services/cbs/client/api/listener/MerkleTree.java246
1 files changed, 73 insertions, 173 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);
}