minhash_rs/
atomic.rs

1use core::hash::{Hash, Hasher};
2use core::{
3    mem::transmute,
4    sync::atomic::{AtomicU16, AtomicU32, AtomicU64, AtomicU8, AtomicUsize},
5};
6
7use fnv::FnvHasher;
8use siphasher::sip128::SipHasher13;
9
10use crate::prelude::*;
11
12pub trait AtomicFetchMin {
13    type Word;
14
15    /// Set the minimum value atomically
16    ///
17    /// # Arguments
18    /// * `value` - The value to set.
19    /// * `ordering` - The ordering to use.
20    ///
21    fn set_min(&self, value: Self::Word, ordering: core::sync::atomic::Ordering);
22}
23
24impl AtomicFetchMin for AtomicU8 {
25    type Word = u8;
26
27    fn set_min(&self, value: Self::Word, ordering: core::sync::atomic::Ordering) {
28        self.fetch_min(value, ordering);
29    }
30}
31
32impl AtomicFetchMin for AtomicU16 {
33    type Word = u16;
34
35    fn set_min(&self, value: Self::Word, ordering: core::sync::atomic::Ordering) {
36        self.fetch_min(value, ordering);
37    }
38}
39
40impl AtomicFetchMin for AtomicU32 {
41    type Word = u32;
42
43    fn set_min(&self, value: Self::Word, ordering: core::sync::atomic::Ordering) {
44        self.fetch_min(value, ordering);
45    }
46}
47
48impl AtomicFetchMin for AtomicU64 {
49    type Word = u64;
50
51    fn set_min(&self, value: Self::Word, ordering: core::sync::atomic::Ordering) {
52        self.fetch_min(value, ordering);
53    }
54}
55
56impl AtomicFetchMin for AtomicUsize {
57    type Word = usize;
58
59    fn set_min(&self, value: Self::Word, ordering: core::sync::atomic::Ordering) {
60        self.fetch_min(value, ordering);
61    }
62}
63
64pub trait IterHashes<Word, const PERMUTATIONS: usize>
65where
66    Word: Min + XorShift + Copy + Eq,
67    u64: Primitive<Word>,
68{
69    /// Iterate on the hashes from the provided value and hasher.
70    ///
71    /// # Arguments
72    /// * `value` - The value to hash.
73    fn iter_hashes_from_value<H: Hash, HS: Hasher>(
74        value: H,
75        mut hasher: HS,
76    ) -> impl Iterator<Item = Word> {
77        // Calculate the hash.
78        value.hash(&mut hasher);
79        let mut hash: Word = hasher.finish().splitmix().splitmix().convert();
80
81        // Iterate over the words.
82        (0..PERMUTATIONS).map(move |_| {
83            hash = hash.xorshift();
84            hash
85        })
86    }
87
88    /// Iterate on the SipHasher13 hashes from the provided value.
89    ///
90    /// # Arguments
91    /// * `value` - The value to hash.
92    ///
93    /// # Examples
94    ///
95    /// ```rust
96    /// use minhash_rs::prelude::*;
97    ///
98    /// let mut minhash = MinHash::<u64, 128>::new();
99    ///
100    /// assert!(!minhash.may_contain_value_with_siphashes13(42));
101    /// minhash.insert_with_siphashes13(42);
102    /// assert!(minhash.may_contain_value_with_siphashes13(42));
103    /// minhash.insert_with_siphashes13(47);
104    /// assert!(minhash.may_contain_value_with_siphashes13(47));
105    /// ```
106    ///  
107    fn iter_siphashes13_from_value<H: Hash>(value: H) -> impl Iterator<Item = Word> {
108        Self::iter_hashes_from_value(value, SipHasher13::new())
109    }
110
111    /// Iterate on the keyed SipHasher13 hashes from the provided value.
112    ///
113    /// # Arguments
114    /// * `value` - The value to hash.
115    /// * `key0` - The first key.
116    /// * `key1` - The second key.
117    ///
118    /// # Examples
119    ///
120    /// ```rust
121    /// use minhash_rs::prelude::*;
122    ///
123    /// let mut minhash = MinHash::<u64, 128>::new();
124    /// let key0 = 0x0123456789ABCDEF;
125    /// let key1 = 0xFEDCBA9876543210;
126    ///
127    /// assert!(!minhash.may_contain_value_with_keyed_siphashes13(42, key0, key1));
128    /// minhash.insert_with_keyed_siphashes13(42, key0, key1);
129    /// assert!(minhash.may_contain_value_with_keyed_siphashes13(42, key0, key1));
130    /// minhash.insert_with_keyed_siphashes13(47, key0, key1);
131    /// assert!(minhash.may_contain_value_with_keyed_siphashes13(47, key0, key1));
132    /// ```
133    ///
134    fn iter_keyed_siphashes13_from_value<H: Hash>(
135        value: H,
136        key0: u64,
137        key1: u64,
138    ) -> impl Iterator<Item = Word> {
139        Self::iter_hashes_from_value(value, SipHasher13::new_with_keys(key0, key1))
140    }
141
142    /// Iterate on the FVN hashes from the provided value.
143    ///
144    /// # Arguments
145    /// * `value` - The value to hash.
146    ///
147    /// # Examples
148    ///
149    /// ```rust
150    /// use minhash_rs::prelude::*;
151    ///
152    /// let mut minhash = MinHash::<u64, 128>::new();
153    ///
154    /// assert!(!minhash.may_contain_value_with_fvn(42));
155    /// minhash.insert_with_fvn(42);
156    /// assert!(minhash.may_contain_value_with_fvn(42));
157    /// minhash.insert_with_fvn(47);
158    /// assert!(minhash.may_contain_value_with_fvn(47));
159    /// ```
160    ///  
161    fn iter_fvn_from_value<H: Hash>(value: H) -> impl Iterator<Item = Word> {
162        Self::iter_hashes_from_value(value, FnvHasher::default())
163    }
164
165    /// Iterate on the keyed SipHasher13 hashes from the provided value.
166    ///
167    /// # Arguments
168    /// * `value` - The value to hash.
169    /// * `key` - The first key.
170    ///
171    /// # Examples
172    ///
173    /// ```rust
174    /// use minhash_rs::prelude::*;
175    ///
176    /// let mut minhash = MinHash::<u64, 128>::new();
177    /// let key = 0x0123456789ABCDEF;
178    ///
179    /// assert!(!minhash.may_contain_value_with_keyed_fvn(42, key));
180    ///
181    fn iter_keyed_fvn_from_value<H: Hash>(value: H, key: u64) -> impl Iterator<Item = Word> {
182        Self::iter_hashes_from_value(value, FnvHasher::with_key(key))
183    }
184}
185
186impl<Word: Min + XorShift + Copy + Eq, const PERMUTATIONS: usize> IterHashes<Word, PERMUTATIONS>
187    for MinHash<Word, PERMUTATIONS>
188where
189    u64: Primitive<Word>,
190{
191}
192
193pub trait AtomicMinHash<AtomicWord: AtomicFetchMin, const PERMUTATIONS: usize>
194where
195    Self: IterHashes<AtomicWord::Word, PERMUTATIONS>,
196    AtomicWord::Word: Min + XorShift + Copy + Eq,
197    u64: Primitive<<AtomicWord as AtomicFetchMin>::Word>,
198    AtomicWord::Word: XorShift + Copy,
199{
200    /// Iterate over the words.
201    fn iter_atomic<'a>(&'a self) -> impl Iterator<Item = &'a AtomicWord>
202    where
203        AtomicWord: 'a,
204        Self: 'a;
205
206    /// Insert a value into the MinHash atomically, with SipHasher13.
207    ///
208    /// # Arguments
209    /// * `value` - The value to insert.
210    ///
211    /// # Examples
212    ///
213    /// ```
214    /// use minhash_rs::prelude::*;
215    ///
216    /// let mut minhash = MinHash::<u64, 4>::new();
217    ///
218    /// assert!(!minhash.may_contain_value_with_siphashes13(42));
219    /// minhash.fetch_insert_with_siphashes13(42, core::sync::atomic::Ordering::Relaxed);
220    /// assert!(!minhash.is_empty());
221    /// assert!(
222    ///     minhash.may_contain_value_with_siphashes13(42),
223    ///     concat!(
224    ///         "The MinHash should contain the value 42, ",
225    ///         "but it does not. The MinHash is: {:?}. ",
226    ///         "The hashes associated to the value 42 are: {:?}."
227    ///     ),
228    ///     minhash,
229    ///     MinHash::<u64, 4>::iter_siphashes13_from_value(42).collect::<Vec<_>>()
230    /// );
231    /// minhash.fetch_insert_with_siphashes13(47, core::sync::atomic::Ordering::Relaxed);
232    /// assert!(minhash.may_contain_value_with_siphashes13(47));
233    ///
234    /// ```
235    ///
236    fn fetch_insert_with_siphashes13<H: Hash>(
237        &self,
238        value: H,
239        ordering: core::sync::atomic::Ordering,
240    ) {
241        // Iterate over the words.
242        for (word, hash) in self
243            .iter_atomic()
244            .zip(Self::iter_siphashes13_from_value(value))
245        {
246            word.set_min(hash, ordering);
247        }
248    }
249
250    /// Insert a value into the MinHash atomically, with keyed SipHasher13.
251    ///
252    /// # Arguments
253    /// * `value` - The value to insert.
254    /// * `key0` - The first key.
255    /// * `key1` - The second key.
256    ///
257    /// # Examples
258    ///
259    /// ```
260    /// use minhash_rs::prelude::*;
261    ///
262    /// let mut minhash = MinHash::<u64, 4>::new();
263    /// let key0 = 0x0123456789ABCDEF;
264    /// let key1 = 0xFEDCBA9876543210;
265    ///
266    /// assert!(!minhash.may_contain_value_with_keyed_siphashes13(42, key0, key1));
267    /// minhash.fetch_insert_with_keyed_siphashes13(42, key0, key1, core::sync::atomic::Ordering::Relaxed);
268    /// assert!(!minhash.is_empty());
269    /// assert!(
270    ///     minhash.may_contain_value_with_keyed_siphashes13(42, key0, key1),
271    ///     concat!(
272    ///         "The MinHash should contain the value 42, ",
273    ///         "but it does not. The MinHash is: {:?}. ",
274    ///         "The hashes associated to the value 42 are: {:?}."
275    ///     ),
276    ///     minhash,
277    ///     MinHash::<u64, 4>::iter_keyed_siphashes13_from_value(42, key0, key1).collect::<Vec<_>>()
278    /// );
279    /// minhash.fetch_insert_with_keyed_siphashes13(47, key0, key1, core::sync::atomic::Ordering::Relaxed);
280    /// assert!(minhash.may_contain_value_with_keyed_siphashes13(47, key0, key1));
281    ///
282    /// ```
283    ///
284    fn fetch_insert_with_keyed_siphashes13<H: Hash>(
285        &self,
286        value: H,
287        key0: u64,
288        key1: u64,
289        ordering: core::sync::atomic::Ordering,
290    ) {
291        // Iterate over the words.
292        for (word, hash) in self
293            .iter_atomic()
294            .zip(Self::iter_keyed_siphashes13_from_value(value, key0, key1))
295        {
296            word.set_min(hash, ordering);
297        }
298    }
299}
300
301impl<const PERMUTATIONS: usize> AtomicMinHash<AtomicU8, PERMUTATIONS>
302    for MinHash<u8, PERMUTATIONS>
303{
304    /// Iterate over the words.
305    fn iter_atomic<'a>(&'a self) -> impl Iterator<Item = &'a AtomicU8>
306    where
307        Self: 'a,
308    {
309        let words: &[AtomicU8] = unsafe { transmute(self.as_ref()) };
310        words.iter()
311    }
312}
313
314impl<const PERMUTATIONS: usize> AtomicMinHash<AtomicU16, PERMUTATIONS>
315    for MinHash<u16, PERMUTATIONS>
316{
317    /// Iterate over the words.
318    fn iter_atomic<'a>(&'a self) -> impl Iterator<Item = &'a AtomicU16>
319    where
320        Self: 'a,
321    {
322        let words: &[AtomicU16] = unsafe { transmute(self.as_ref()) };
323        words.iter()
324    }
325}
326
327impl<const PERMUTATIONS: usize> AtomicMinHash<AtomicU32, PERMUTATIONS>
328    for MinHash<u32, PERMUTATIONS>
329{
330    /// Iterate over the words.
331    fn iter_atomic<'a>(&'a self) -> impl Iterator<Item = &'a AtomicU32>
332    where
333        Self: 'a,
334    {
335        let words: &[AtomicU32] = unsafe { transmute(self.as_ref()) };
336        words.iter()
337    }
338}
339
340impl<const PERMUTATIONS: usize> AtomicMinHash<AtomicU64, PERMUTATIONS>
341    for MinHash<u64, PERMUTATIONS>
342{
343    /// Iterate over the words.
344    fn iter_atomic<'a>(&'a self) -> impl Iterator<Item = &'a AtomicU64>
345    where
346        Self: 'a,
347    {
348        let words: &[AtomicU64] = unsafe { transmute(self.as_ref()) };
349        words.iter()
350    }
351}
352
353impl<const PERMUTATIONS: usize> AtomicMinHash<AtomicUsize, PERMUTATIONS>
354    for MinHash<usize, PERMUTATIONS>
355{
356    /// Iterate over the words.
357    fn iter_atomic<'a>(&'a self) -> impl Iterator<Item = &'a AtomicUsize>
358    where
359        Self: 'a,
360    {
361        let words: &[AtomicUsize] = unsafe { transmute(self.as_ref()) };
362        words.iter()
363    }
364}
minhash_rs/atomic.rs

minhash_rs/
atomic.rs
