dualcache_ff/
filters.rs

1#[cfg(not(feature = "std"))]
2use alloc::{boxed::Box, vec::Vec};
3
4use crate::sync::atomic::{AtomicPtr, Ordering};
5use core::ptr;
6use crate::storage::Node;
7
8/// T1 — Hottest tier: direct-mapped L1 filter (fits in CPU L1 cache).
9///
10/// Each slot stores a raw pointer to the most recently seen node for
11/// that hash bucket. Slot assignment is pure bitmask: `hash & mask`.
12/// Collisions simply overwrite; no chaining, no locks.
13pub struct T1<K, V> {
14    pub(crate) mask: usize,
15    pub(crate) slots: Box<[AtomicPtr<Node<K, V>>]>,
16}
17
18unsafe impl<K: Send, V: Send> Send for T1<K, V> {}
19unsafe impl<K: Send + Sync, V: Send + Sync> Sync for T1<K, V> {}
20
21impl<K, V> T1<K, V> {
22    pub fn new(slots_count: usize) -> Self {
23        let mut slots = Vec::with_capacity(slots_count);
24        for _ in 0..slots_count {
25            slots.push(AtomicPtr::new(ptr::null_mut()));
26        }
27        Self {
28            mask: slots_count - 1,
29            slots: slots.into_boxed_slice(),
30        }
31    }
32
33    #[inline(always)]
34    pub fn load_slot(&self, hash: u64) -> *mut Node<K, V> {
35        let idx = hash as usize & self.mask;
36        self.slots[idx].load(Ordering::Acquire)
37    }
38
39    #[inline(always)]
40    pub fn store_slot(&self, hash: u64, ptr: *mut Node<K, V>) {
41        let idx = hash as usize & self.mask;
42        self.slots[idx].store(ptr, Ordering::Release);
43    }
44
45    /// Safe accessor that relies on QSBR epoch protection being active.
46    #[inline(always)]
47    pub fn get_node<'a>(&self, hash: u64) -> Option<&'a Node<K, V>> {
48        let ptr = self.load_slot(hash);
49        if ptr.is_null() {
50            None
51        } else {
52            Some(unsafe { &*ptr })
53        }
54    }
55
56    #[inline(always)]
57    pub fn clear_if_matches(&self, hash: u64, expected_ptr: *mut Node<K, V>) {
58        let idx = hash as usize & self.mask;
59        let _ = self.slots[idx].compare_exchange(
60            expected_ptr,
61            ptr::null_mut(),
62            Ordering::Release,
63            Ordering::Relaxed,
64        );
65    }
66
67    #[inline(always)]
68    pub fn clear_at(&self, idx: usize) {
69        self.slots[idx].store(ptr::null_mut(), Ordering::Relaxed);
70    }
71
72    #[inline(always)]
73    pub fn len(&self) -> usize {
74        self.slots.len()
75    }
76}
77
78/// T2 — Warm tier: direct-mapped L2 filter (intercepts warm data).
79///
80/// Structurally identical to T1 but sized differently (20% of capacity).
81/// Logically separated so future experiments can apply different policies
82/// (e.g., T2 uses CLOCK-Pro promotion while T1 uses LRU-hot demotion).
83pub struct T2<K, V> {
84    pub(crate) mask: usize,
85    pub(crate) slots: Box<[AtomicPtr<Node<K, V>>]>,
86}
87
88unsafe impl<K: Send, V: Send> Send for T2<K, V> {}
89unsafe impl<K: Send + Sync, V: Send + Sync> Sync for T2<K, V> {}
90
91impl<K, V> T2<K, V> {
92    pub fn new(slots_count: usize) -> Self {
93        let mut slots = Vec::with_capacity(slots_count);
94        for _ in 0..slots_count {
95            slots.push(AtomicPtr::new(ptr::null_mut()));
96        }
97        Self {
98            mask: slots_count - 1,
99            slots: slots.into_boxed_slice(),
100        }
101    }
102
103    #[inline(always)]
104    pub fn load_slot(&self, hash: u64) -> *mut Node<K, V> {
105        let idx = hash as usize & self.mask;
106        self.slots[idx].load(Ordering::Acquire)
107    }
108
109    #[inline(always)]
110    pub fn store_slot(&self, hash: u64, ptr: *mut Node<K, V>) {
111        let idx = hash as usize & self.mask;
112        self.slots[idx].store(ptr, Ordering::Release);
113    }
114
115    /// Safe accessor that relies on QSBR epoch protection being active.
116    #[inline(always)]
117    pub fn get_node<'a>(&self, hash: u64) -> Option<&'a Node<K, V>> {
118        let ptr = self.load_slot(hash);
119        if ptr.is_null() {
120            None
121        } else {
122            Some(unsafe { &*ptr })
123        }
124    }
125
126    #[inline(always)]
127    pub fn clear_if_matches(&self, hash: u64, expected_ptr: *mut Node<K, V>) {
128        let idx = hash as usize & self.mask;
129        let _ = self.slots[idx].compare_exchange(
130            expected_ptr,
131            ptr::null_mut(),
132            Ordering::Release,
133            Ordering::Relaxed,
134        );
135    }
136
137    #[inline(always)]
138    pub fn clear_at(&self, idx: usize) {
139        self.slots[idx].store(ptr::null_mut(), Ordering::Relaxed);
140    }
141
142    #[inline(always)]
143    pub fn len(&self) -> usize {
144        self.slots.len()
145    }
146}
dualcache_ff/filters.rs

dualcache_ff/
filters.rs
