qht/
basicqht.rs

1use crate::filter::Filter;
2pub use std::collections::hash_map::DefaultHasher;
3pub use std::hash::{Hash, Hasher};
4
5pub type Fingerprint = u64;
6
7/// The `BasicQHT` trait collects common functionality between the different QHT flavours
8pub trait BasicQHT: Filter {
9    /// Obtains the fingerprint stored in a given bucket
10    fn get_fingerprint_from_bucket(&self, address: usize, bucket_number: usize) -> Fingerprint;
11
12    /// Inserts a fingerprint in a bucket
13    fn insert_fingerprint_in_bucket(
14        &mut self,
15        address: usize,
16        bucket_number: usize,
17        fingerprint: Fingerprint,
18    );
19
20    /// Checks whether a fingerprint is in a cell
21    fn in_cell(&self, address: usize, fingerprint: Fingerprint) -> bool;
22
23    /// Obtains the fingerprint of an object
24    fn get_fingerprint(&self, e: impl Hash) -> Fingerprint;
25}
26
27/// Returns the hash of (e, base, counter)
28pub fn get_hash(e: impl Hash, base: u64, counter: u64) -> u64 {
29    let mut s = DefaultHasher::new();
30    e.hash(&mut s);
31    base.hash(&mut s);
32    counter.hash(&mut s);
33    s.finish()
34}
35
36#[macro_export]
37macro_rules! impl_basicqht {
38    ($struct_type:ty) => {
39        impl BasicQHT for $struct_type {
40            /// Retrieves a fingerprint from a given bucket (provided as an `address` and `bucket_number`)
41            fn get_fingerprint_from_bucket(
42                &self,
43                address: usize,
44                bucket_number: usize,
45            ) -> Fingerprint {
46                let offset = (address * self.n_buckets + bucket_number) * self.fingerprint_size;
47
48                self.qht.extract_u64(offset, self.fingerprint_size)
49            }
50
51            /// Inserts a fingerprint in a given buffer (provided as an `address` and `bucket_number`)
52            fn insert_fingerprint_in_bucket(
53                &mut self,
54                address: usize,
55                bucket_number: usize,
56                fingerprint: Fingerprint,
57            ) {
58                let offset = (address * self.n_buckets + bucket_number) * self.fingerprint_size;
59
60                self.qht
61                    .insert_u64(fingerprint, offset, self.fingerprint_size);
62            }
63
64            /// Checks whether a fingerprint belongs to a given cell
65            fn in_cell(&self, address: usize, fingerprint: Fingerprint) -> bool {
66                for idx in 0..self.n_buckets {
67                    if self.get_fingerprint_from_bucket(address, idx) == fingerprint {
68                        return true;
69                    }
70                }
71                false
72            }
73
74            /// Obtains an element's fingerprint
75            fn get_fingerprint(&self, e: impl Hash) -> Fingerprint {
76                let mut fingerprint = 0;
77                let mut counter = 0;
78
79                while fingerprint == 0 {
80                    let v = get_hash(&e, 2, counter);
81                    fingerprint = (v % self.pow_fingerprint_size) as Fingerprint;
82                    counter += 1;
83                }
84                fingerprint
85            }
86        }
87    };
88}
qht/basicqht.rs

qht/
basicqht.rs
