kaspa_consensus_core/
blockhash.rs

1use crate::{BlockHashSet, HashMapCustomHasher};
2use kaspa_hashes::{Hash, HASH_SIZE};
3use std::sync::Arc;
4
5pub type BlockHashes = Arc<Vec<Hash>>;
6
7/// `blockhash::NONE` is a hash which is used in rare cases as the `None` block hash
8pub const NONE: Hash = Hash::from_bytes([0u8; HASH_SIZE]);
9
10/// `blockhash::ORIGIN` is a special hash representing a `virtual genesis` block.
11/// It serves as a special local block which all locally-known
12/// blocks are in its future.
13pub const ORIGIN: Hash = Hash::from_bytes([0xfe; HASH_SIZE]);
14
15pub trait BlockHashExtensions {
16    fn is_none(&self) -> bool;
17    fn is_origin(&self) -> bool;
18}
19
20impl BlockHashExtensions for Hash {
21    fn is_none(&self) -> bool {
22        self.eq(&NONE)
23    }
24
25    fn is_origin(&self) -> bool {
26        self.eq(&ORIGIN)
27    }
28}
29
30/// Generates a unique block hash for each call to this function.
31/// To be used for test purposes only.
32pub fn new_unique() -> Hash {
33    use std::sync::atomic::{AtomicU64, Ordering};
34    static COUNTER: AtomicU64 = AtomicU64::new(1);
35    let c = COUNTER.fetch_add(1, Ordering::Relaxed);
36    Hash::from_u64_word(c)
37}
38
39pub trait BlockHashIteratorExtensions: Iterator<Item = Hash> {
40    /// Copy of itertools::unique, adapted for block hashes (uses `BlockHashSet` under the hood)
41    ///
42    /// Returns an iterator adaptor that filters out hashes that have
43    /// already been produced once during the iteration.
44    ///
45    /// Clones of visited elements are stored in a hash set in the
46    /// iterator.
47    ///
48    /// The iterator is stable, returning the non-duplicate items in the order
49    /// in which they occur in the adapted iterator. In a set of duplicate
50    /// items, the first item encountered is the item retained.
51    ///
52    /// NOTE: currently usages are expected to contain no duplicates, hence we alloc the expected capacity
53    fn block_unique(self) -> BlockUnique<Self>
54    where
55        Self: Sized,
56    {
57        let (lower, _) = self.size_hint();
58        BlockUnique { iter: self, seen: BlockHashSet::with_capacity(lower) }
59    }
60}
61
62impl<T: ?Sized> BlockHashIteratorExtensions for T where T: Iterator<Item = Hash> {}
63
64#[derive(Clone)]
65pub struct BlockUnique<I: Iterator<Item = Hash>> {
66    iter: I,
67    seen: BlockHashSet,
68}
69
70impl<I> Iterator for BlockUnique<I>
71where
72    I: Iterator<Item = Hash>,
73{
74    type Item = I::Item;
75
76    fn next(&mut self) -> Option<Self::Item> {
77        self.iter.by_ref().find(|&hash| self.seen.insert(hash))
78    }
79
80    #[inline]
81    fn size_hint(&self) -> (usize, Option<usize>) {
82        let (low, hi) = self.iter.size_hint();
83        ((low > 0 && self.seen.is_empty()) as usize, hi)
84    }
85}
86
87impl<I> DoubleEndedIterator for BlockUnique<I>
88where
89    I: DoubleEndedIterator<Item = Hash>,
90{
91    fn next_back(&mut self) -> Option<Self::Item> {
92        self.iter.by_ref().rev().find(|&hash| self.seen.insert(hash))
93    }
94}
95
96impl<I> std::iter::FusedIterator for BlockUnique<I> where I: Iterator<Item = Hash> + std::iter::FusedIterator {}
kaspa_consensus_core/blockhash.rs

kaspa_consensus_core/
blockhash.rs
