stack_test_epic_core/core/pmmr/
vec_backend.rs

1// Copyright 2020 The Grin Developers
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::collections::HashSet;
16use std::convert::TryFrom;
17use std::fs::File;
18
19use croaring::Bitmap;
20
21use crate::core::hash::Hash;
22use crate::core::pmmr::{self, Backend};
23use crate::core::BlockHeader;
24use crate::ser::PMMRable;
25
26/// Simple/minimal/naive MMR backend implementation backed by Vec<T> and Vec<Hash>.
27/// Removed pos are maintained in a HashSet<u64>.
28#[derive(Clone, Debug)]
29pub struct VecBackend<T: PMMRable> {
30	/// Backend elements (optional, possible to just store hashes).
31	pub data: Option<Vec<T>>,
32	/// Vec of hashes for the PMMR (both leaves and parents).
33	pub hashes: Vec<Hash>,
34	/// Positions of removed elements (is this applicable if we do not store data?)
35	pub removed: HashSet<u64>,
36}
37
38impl<T: PMMRable> Backend<T> for VecBackend<T> {
39	fn append(&mut self, elmt: &T, hashes: Vec<Hash>) -> Result<(), String> {
40		if let Some(data) = &mut self.data {
41			data.push(elmt.clone());
42		}
43		self.hashes.append(&mut hashes.clone());
44		Ok(())
45	}
46
47	fn get_hash(&self, position: u64) -> Option<Hash> {
48		if self.removed.contains(&position) {
49			None
50		} else {
51			self.get_from_file(position)
52		}
53	}
54
55	fn get_data(&self, position: u64) -> Option<T::E> {
56		if self.removed.contains(&position) {
57			None
58		} else {
59			self.get_data_from_file(position)
60		}
61	}
62
63	fn get_from_file(&self, position: u64) -> Option<Hash> {
64		let idx = usize::try_from(position.saturating_sub(1)).expect("usize from u64");
65		self.hashes.get(idx).cloned()
66	}
67
68	fn get_data_from_file(&self, position: u64) -> Option<T::E> {
69		if let Some(data) = &self.data {
70			let idx = usize::try_from(pmmr::n_leaves(position).saturating_sub(1))
71				.expect("usize from u64");
72			data.get(idx).map(|x| x.as_elmt())
73		} else {
74			None
75		}
76	}
77
78	fn data_as_temp_file(&self) -> Result<File, String> {
79		unimplemented!()
80	}
81
82	/// Number of leaves in the MMR
83	fn n_unpruned_leaves(&self) -> u64 {
84		unimplemented!()
85	}
86
87	fn leaf_pos_iter(&self) -> Box<dyn Iterator<Item = u64> + '_> {
88		Box::new(
89			self.hashes
90				.iter()
91				.enumerate()
92				.map(|(x, _)| (x + 1) as u64)
93				.filter(move |x| pmmr::is_leaf(*x) && !self.removed.contains(x)),
94		)
95	}
96
97	fn leaf_idx_iter(&self, from_idx: u64) -> Box<dyn Iterator<Item = u64> + '_> {
98		let from_pos = pmmr::insertion_to_pmmr_index(from_idx + 1);
99		Box::new(
100			self.leaf_pos_iter()
101				.skip_while(move |x| *x < from_pos)
102				.map(|x| pmmr::n_leaves(x).saturating_sub(1)),
103		)
104	}
105
106	fn remove(&mut self, position: u64) -> Result<(), String> {
107		self.removed.insert(position);
108		Ok(())
109	}
110
111	fn rewind(&mut self, position: u64, _rewind_rm_pos: &Bitmap) -> Result<(), String> {
112		if let Some(data) = &mut self.data {
113			let idx = pmmr::n_leaves(position);
114			data.truncate(usize::try_from(idx).expect("usize from u64"));
115		}
116		self.hashes
117			.truncate(usize::try_from(position).expect("usize from u64"));
118		Ok(())
119	}
120
121	fn snapshot(&self, _header: &BlockHeader) -> Result<(), String> {
122		Ok(())
123	}
124
125	fn release_files(&mut self) {}
126
127	fn dump_stats(&self) {}
128}
129
130impl<T: PMMRable> VecBackend<T> {
131	/// Instantiates a new empty vec backend.
132	pub fn new() -> VecBackend<T> {
133		VecBackend {
134			data: Some(vec![]),
135			hashes: vec![],
136			removed: HashSet::new(),
137		}
138	}
139
140	/// Instantiate a new empty "hash only" vec backend.
141	pub fn new_hash_only() -> VecBackend<T> {
142		VecBackend {
143			data: None,
144			hashes: vec![],
145			removed: HashSet::new(),
146		}
147	}
148
149	/// Size of this vec backend in hashes.
150	pub fn size(&self) -> u64 {
151		self.hashes.len() as u64
152	}
153}
stack_test_epic_core/core/pmmr/vec_backend.rs

stack_test_epic_core/core/pmmr/
vec_backend.rs
