aboutsummaryrefslogtreecommitdiff
path: root/src/table/merkle.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/table/merkle.rs')
-rw-r--r--src/table/merkle.rs107
1 files changed, 83 insertions, 24 deletions
diff --git a/src/table/merkle.rs b/src/table/merkle.rs
index ef197dc8..92c18e09 100644
--- a/src/table/merkle.rs
+++ b/src/table/merkle.rs
@@ -15,6 +15,19 @@ use garage_util::background::BackgroundRunner;
use garage_util::data::*;
use garage_util::error::Error;
+pub type MerklePartition = [u8; 2];
+
+pub fn hash_of_merkle_partition(p: MerklePartition) -> Hash {
+ let mut partition_pos = [0u8; 32];
+ partition_pos[0..2].copy_from_slice(&p[..]);
+ partition_pos.into()
+}
+
+pub fn hash_of_merkle_partition_opt(p: Option<MerklePartition>) -> Hash {
+ p.map(hash_of_merkle_partition)
+ .unwrap_or([0xFFu8; 32].into())
+}
+
// This modules partitions the data in 2**16 partitions, based on the top
// 16 bits (two bytes) of item's partition keys' hashes.
// It builds one Merkle tree for each of these 2**16 partitions.
@@ -37,10 +50,10 @@ pub(crate) struct MerkleUpdater {
empty_node_hash: Hash,
}
-#[derive(Clone)]
+#[derive(Clone, Serialize, Deserialize)]
pub struct MerkleNodeKey {
// partition: first 16 bits (two bytes) of the partition_key's hash
- pub partition: [u8; 2],
+ pub partition: MerklePartition,
// prefix: a prefix for the hash of full keys, i.e. hash(hash(partition_key)+sort_key)
pub prefix: Vec<u8>,
@@ -214,8 +227,11 @@ impl MerkleUpdater {
// insertion and replace current node by an intermediary node
let (pos1, h1) = {
let key2 = key.next_key(blake2sum(&exlf_key[..]));
- let subhash =
- self.put_node_txn(tx, &key2, &MerkleNode::Leaf(exlf_key, exlf_hash))?;
+ let subhash = self.put_node_txn(
+ tx,
+ &key2,
+ &MerkleNode::Leaf(exlf_key, exlf_hash),
+ )?;
(key2.prefix[i], subhash)
};
let (pos2, h2) = {
@@ -280,14 +296,11 @@ impl MerkleUpdater {
}
// Access a node in the Merkle tree, used by the sync protocol
- pub(crate) fn read_node(
- &self,
- k: &MerkleNodeKey,
- ) -> Result<MerkleNode, Error> {
+ pub(crate) fn read_node(&self, k: &MerkleNodeKey) -> Result<MerkleNode, Error> {
let ent = self.merkle_tree.get(k.encode())?;
match ent {
None => Ok(MerkleNode::Empty),
- Some(v) => Ok(rmp_serde::decode::from_read_ref::<_, MerkleNode>(&v[..])?)
+ Some(v) => Ok(rmp_serde::decode::from_read_ref::<_, MerkleNode>(&v[..])?),
}
}
}
@@ -339,31 +352,77 @@ fn intermediate_rm_child(ch: &mut Vec<(u8, Hash)>, pos: u8) {
#[test]
fn test_intermediate_aux() {
let mut v = vec![];
-
+
intermediate_set_child(&mut v, 12u8, [12u8; 32].into());
- assert!(v == vec![(12u8, [12u8; 32].into())]);
-
+ assert_eq!(v, vec![(12u8, [12u8; 32].into())]);
+
intermediate_set_child(&mut v, 42u8, [42u8; 32].into());
- assert!(v == vec![(12u8, [12u8; 32].into()), (42u8, [42u8; 32].into())]);
-
+ assert_eq!(
+ v,
+ vec![(12u8, [12u8; 32].into()), (42u8, [42u8; 32].into())]
+ );
+
intermediate_set_child(&mut v, 4u8, [4u8; 32].into());
- assert!(v == vec![(4u8, [4u8; 32].into()), (12u8, [12u8; 32].into()), (42u8, [42u8; 32].into())]);
-
+ assert_eq!(
+ v,
+ vec![
+ (4u8, [4u8; 32].into()),
+ (12u8, [12u8; 32].into()),
+ (42u8, [42u8; 32].into())
+ ]
+ );
+
intermediate_set_child(&mut v, 12u8, [8u8; 32].into());
- assert!(v == vec![(4u8, [4u8; 32].into()), (12u8, [8u8; 32].into()), (42u8, [42u8; 32].into())]);
-
+ assert_eq!(
+ v,
+ vec![
+ (4u8, [4u8; 32].into()),
+ (12u8, [8u8; 32].into()),
+ (42u8, [42u8; 32].into())
+ ]
+ );
+
intermediate_set_child(&mut v, 6u8, [6u8; 32].into());
- assert!(v == vec![(4u8, [4u8; 32].into()), (6u8, [6u8; 32].into()), (12u8, [8u8; 32].into()), (42u8, [42u8; 32].into())]);
+ assert_eq!(
+ v,
+ vec![
+ (4u8, [4u8; 32].into()),
+ (6u8, [6u8; 32].into()),
+ (12u8, [8u8; 32].into()),
+ (42u8, [42u8; 32].into())
+ ]
+ );
intermediate_rm_child(&mut v, 42u8);
- assert!(v == vec![(4u8, [4u8; 32].into()), (6u8, [6u8; 32].into()), (12u8, [8u8; 32].into())]);
+ assert_eq!(
+ v,
+ vec![
+ (4u8, [4u8; 32].into()),
+ (6u8, [6u8; 32].into()),
+ (12u8, [8u8; 32].into())
+ ]
+ );
intermediate_rm_child(&mut v, 11u8);
- assert!(v == vec![(4u8, [4u8; 32].into()), (6u8, [6u8; 32].into()), (12u8, [8u8; 32].into())]);
+ assert_eq!(
+ v,
+ vec![
+ (4u8, [4u8; 32].into()),
+ (6u8, [6u8; 32].into()),
+ (12u8, [8u8; 32].into())
+ ]
+ );
intermediate_rm_child(&mut v, 6u8);
- assert!(v == vec![(4u8, [4u8; 32].into()), (12u8, [8u8; 32].into())]);
-
+ assert_eq!(v, vec![(4u8, [4u8; 32].into()), (12u8, [8u8; 32].into())]);
+
intermediate_set_child(&mut v, 6u8, [7u8; 32].into());
- assert!(v == vec![(4u8, [4u8; 32].into()), (6u8, [7u8; 32].into()), (12u8, [8u8; 32].into())]);
+ assert_eq!(
+ v,
+ vec![
+ (4u8, [4u8; 32].into()),
+ (6u8, [7u8; 32].into()),
+ (12u8, [8u8; 32].into())
+ ]
+ );
}