[−][src]Struct exonum_merkledb::indexes::proof_list::ProofListIndex
A Merkelized version of an array list that provides proofs of existence for the list items.
ProofListIndex
implements a Merkle tree, storing elements as leaves and using u64
as
an index. ProofListIndex
requires that elements implement the BinaryValue
trait.
Safety
A ProofListIndex
may contain at most 2 ** 56
elements (which is approximately 7.2e16
),
not 2 ** 64
as ListIndex
. Since this amount is still astronomically large,
an index overflow is treated similar to an integer overflow; extend
and push
methods will panic if the index size exceeds 2 ** 56
. (Unlike integer overflows, the panic
will occur in any compile mode, regardless of whether debug assertions are on.)
For added safety, the application may check that an overflow does not occur before performing
these operations. However, this check will be redundant in most realistic scenarios:
even if 10,000,000 elements are added to a ProofListIndex
every second, it will take
~228 years to overflow it.
Using readonly methods such as get
, iter_from
and get_proof
is safe for all
index values; it is unnecessary to check on the calling side whether the index exceeds
2 ** 56 - 1
.
Methods
impl<T, V> ProofListIndex<T, V> where
T: RawAccess,
V: BinaryValue,
[src]
T: RawAccess,
V: BinaryValue,
pub fn get(&self, index: u64) -> Option<V>
[src]
Returns the element at the indicated position or None
if the indicated position
is out of bounds.
Examples
use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ProofListIndex}; let db = TemporaryDB::new(); let fork = db.fork(); let mut index = fork.get_proof_list("name"); assert_eq!(None, index.get(0)); index.push(10); assert_eq!(Some(10), index.get(0));
pub fn last(&self) -> Option<V>
[src]
Returns the last element of the proof list or None
if it is empty.
Examples
use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ProofListIndex}; let db = TemporaryDB::new(); let fork = db.fork(); let mut index = fork.get_proof_list("name"); assert_eq!(None, index.last()); index.push(1); assert_eq!(Some(1), index.last());
pub fn is_empty(&self) -> bool
[src]
Returns true
if the proof list contains no elements.
Examples
use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ProofListIndex}; let db = TemporaryDB::new(); let fork = db.fork(); let mut index = fork.get_proof_list("name"); assert!(index.is_empty()); index.push(10); assert!(!index.is_empty());
pub fn len(&self) -> u64
[src]
Returns the number of elements in the proof list.
Examples
use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ProofListIndex}; let db = TemporaryDB::new(); let fork = db.fork(); let mut index = fork.get_proof_list("name"); assert_eq!(0, index.len()); index.push(1); assert_eq!(1, index.len());
pub fn height(&self) -> u8
[src]
Returns the height of the Merkle tree built based on the list.
The height of the empty list is 0; otherwise, the height is computed as ceil(log2(l)) + 1
,
where l
is the list length.
Examples
use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ProofListIndex}; let db = TemporaryDB::new(); let fork = db.fork(); let mut index = fork.get_proof_list("name"); assert_eq!(0, index.height()); index.push(1); assert_eq!(1, index.height()); index.push(1); assert_eq!(2, index.height());
pub fn get_proof(&self, index: u64) -> ListProof<V>
[src]
Returns a proof of existence for the list element at the specified position.
Returns a proof of absence if the list doesn't contain an element with the specified index
.
Examples
use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ProofListIndex}; let db = TemporaryDB::new(); let fork = db.fork(); let mut index = fork.get_proof_list("name"); index.push(1); let proof = index.get_proof(0); let proof_of_absence = index.get_proof(1);
pub fn get_range_proof<R: RangeBounds<u64>>(&self, range: R) -> ListProof<V>
[src]
Returns the proof of existence for the list elements in the specified range.
Returns a proof of absence for a range of values, if either or both its bounds exceed the list state.
Panics
Panics if the range bounds are illegal.
Examples
use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ProofListIndex}; let db = TemporaryDB::new(); let fork = db.fork(); let mut index = fork.get_proof_list("name"); index.extend(vec![1, 2, 3, 4, 5]); let range_proof = index.get_range_proof(1..3); assert!(range_proof.indexes_unchecked().eq(vec![1, 2])); // This proof will contain only 4 elements with indexes 1..5. let intersection_proof = index.get_range_proof(1..10); assert!(intersection_proof.indexes_unchecked().eq(1..5)); // This proof does not contain any elements at all. let empty_proof = index.get_range_proof(100..10000); assert!(empty_proof.entries_unchecked().is_empty());
pub fn iter(&self) -> Values<V>
[src]
Returns an iterator over the list values.
Examples
use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ProofListIndex}; let db = TemporaryDB::new(); let fork = db.fork(); let index = fork.get_proof_list::<_, u8>("name"); for val in index.iter() { println!("{}", val); }
pub fn iter_from(&self, from: u64) -> Values<V>
[src]
Returns an iterator over the list values starting from the specified position.
Examples
use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ProofListIndex}; let db = TemporaryDB::new(); let fork = db.fork(); let index = fork.get_proof_list::<_, u8>("name"); for val in index.iter_from(1) { println!("{}", val); }
impl<T, V> ProofListIndex<T, V> where
T: RawAccessMut,
V: BinaryValue,
[src]
T: RawAccessMut,
V: BinaryValue,
pub fn push(&mut self, value: V)
[src]
Appends an element to the back of the proof list.
Examples
use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ProofListIndex}; let db = TemporaryDB::new(); let fork = db.fork(); let mut index = fork.get_proof_list("name"); index.push(1); assert!(!index.is_empty());
pub fn extend<I>(&mut self, iter: I) where
I: IntoIterator<Item = V>,
[src]
I: IntoIterator<Item = V>,
Extends the proof list with the contents of an iterator.
Examples
use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ProofListIndex}; let db = TemporaryDB::new(); let fork = db.fork(); let mut index = fork.get_proof_list("name"); index.extend([1, 2, 3].iter().cloned()); assert_eq!(3, index.len());
pub fn set(&mut self, index: u64, value: V)
[src]
Changes a value at the specified position.
Panics
Panics if index
is equal or greater than the current state of the proof list.
Examples
use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ProofListIndex}; let db = TemporaryDB::new(); let fork = db.fork(); let mut index = fork.get_proof_list("name"); index.push(1); assert_eq!(Some(1), index.get(0)); index.set(0, 100); assert_eq!(Some(100), index.get(0));
pub fn truncate(&mut self, new_length: u64)
[src]
Shortens the list, keeping the indicated number of first len
elements
and dropping the rest.
If len
is greater than the current state of the list, this has no effect.
Examples
use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ProofListIndex}; let db = TemporaryDB::new(); let fork = db.fork(); let mut index = fork.get_proof_list("name"); index.extend([1, 2, 3, 4, 5].iter().cloned()); assert_eq!(5, index.len()); index.truncate(3); assert!(index.iter().eq(vec![1, 2, 3]));
pub fn pop(&mut self) -> Option<V>
[src]
Removes the last element from the list and returns it, or returns None
if the list is empty.
Examples
use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ProofListIndex}; let db = TemporaryDB::new(); let fork = db.fork(); let mut index = fork.get_proof_list("name"); assert_eq!(None, index.pop()); index.push(1); assert_eq!(Some(1), index.pop());
pub fn clear(&mut self)
[src]
Clears the proof list, removing all values.
Notes
Currently, this method is not optimized to delete a large set of data. During the execution of this method, the amount of allocated memory is linearly dependent on the number of elements in the index.
Examples
use exonum_merkledb::{access::CopyAccessExt, TemporaryDB, Database, ProofListIndex}; let db = TemporaryDB::new(); let fork = db.fork(); let mut index = fork.get_proof_list("name"); index.push(1); assert!(!index.is_empty()); index.clear(); assert!(index.is_empty());
Trait Implementations
impl<T: Debug + RawAccess, V: Debug> Debug for ProofListIndex<T, V>
[src]
impl<T, V> FromAccess<T> for ProofListIndex<T::Base, V> where
T: Access,
V: BinaryValue,
[src]
T: Access,
V: BinaryValue,
fn from_access(access: T, addr: IndexAddress) -> Result<Self, AccessError>
[src]
fn from_root(access: T) -> Result<Self, AccessError>
[src]
impl<T, V> IndexIterator for ProofListIndex<T, V> where
T: RawAccess,
V: BinaryValue,
[src]
T: RawAccess,
V: BinaryValue,
type Key = u64
Type encompassing index keys.
type Value = V
Type encompassing index values.
fn index_iter(&self, from: Option<&u64>) -> Entries<u64, V>
[src]
impl<'a, T, V> IntoIterator for &'a ProofListIndex<T, V> where
T: RawAccess,
V: BinaryValue,
[src]
T: RawAccess,
V: BinaryValue,
type Item = V
The type of the elements being iterated over.
type IntoIter = Values<'a, V>
Which kind of iterator are we turning this into?
fn into_iter(self) -> Self::IntoIter
[src]
impl<T, V> ObjectHash for ProofListIndex<T, V> where
T: RawAccess,
V: BinaryValue,
[src]
T: RawAccess,
V: BinaryValue,
object_hash
for a list depends on all list items. It explicitly commits to the list length
in order to be able to more easily prove absence of elements and to prevent second pre-image
attacks.
Specification
The object_hash
is calculated as follows:
h = sha256( HashTag::ListNode || u64_LE(len) || root_hash )
Here, u64_LE
is the 8-byte little-endian serialization of an integer. In particular,
for an empty list
h = sha256( HashTag::ListNode || 0 || Hash::zero() )
root_hash
is defined recursively based on the binary Merkle tree corresponding
to the list. The tree is built so that left children at each level are filled up first,
and the depth of each leaf node is the same. For example, here's the structure of a tree
with 6 leaves:
root (0..6)
/ \
0..4 4..6
/ \ |
0..2 2..4 4..6
/ \ / \ / \
0 1 2 3 4 5
For branch nodes of the tree,
node_hash = sha256( HashTag::ListBranchNode || left_hash || right_hash? )
where left_hash
is the hash of the left child and right_hash
is the optional hash
of the right child, which may be absent if the tree is not balanced.
For leaves, the hash is
leaf_hash = sha256( HashTag::Blob || serialized_value ).
Examples
let db = TemporaryDB::new(); let fork = db.fork(); let mut index = fork.get_proof_list("name"); let default_hash = index.object_hash(); assert_eq!(HashTag::empty_list_hash(), default_hash); index.push(1); let hash = index.object_hash(); assert_ne!(hash, default_hash);
fn object_hash(&self) -> Hash
[src]
Auto Trait Implementations
impl<T, V> RefUnwindSafe for ProofListIndex<T, V> where
T: RefUnwindSafe,
V: RefUnwindSafe,
<T as RawAccess>::Changes: RefUnwindSafe,
T: RefUnwindSafe,
V: RefUnwindSafe,
<T as RawAccess>::Changes: RefUnwindSafe,
impl<T, V> Send for ProofListIndex<T, V> where
T: Send,
V: Send,
<T as RawAccess>::Changes: Send,
T: Send,
V: Send,
<T as RawAccess>::Changes: Send,
impl<T, V> Sync for ProofListIndex<T, V> where
T: Sync,
V: Sync,
<T as RawAccess>::Changes: Sync,
T: Sync,
V: Sync,
<T as RawAccess>::Changes: Sync,
impl<T, V> Unpin for ProofListIndex<T, V> where
T: Unpin,
V: Unpin,
<T as RawAccess>::Changes: Unpin,
T: Unpin,
V: Unpin,
<T as RawAccess>::Changes: Unpin,
impl<T, V> UnwindSafe for ProofListIndex<T, V> where
T: UnwindSafe,
V: UnwindSafe,
<T as RawAccess>::Changes: UnwindSafe,
T: UnwindSafe,
V: UnwindSafe,
<T as RawAccess>::Changes: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<V, T> VZip<V> for T where
V: MultiLane<T>,
V: MultiLane<T>,