dualcache_ff/
storage.rs

1#[cfg(not(feature = "std"))]
2use alloc::{boxed::Box, vec::Vec};
3
4use crate::sync::atomic::{AtomicPtr, Ordering};
5use crate::sync::index_types::{AtomicIndex, IndexType, EMPTY, TOMBSTONE, TAG_SHIFT, INDEX_MASK};
6use core::ptr;
7
8/// A single cached entry. Stored in the Arena node pool.
9pub struct Node<K, V> {
10    pub key: K,
11    pub value: V,
12    /// Epoch at which this node expires (0 = no expiry).
13    pub expire_at: u32,
14    /// Index into the Arena / Cache node arrays.
15    pub g_idx: u32,
16}
17
18/// L3 lock-free hash index + node pointer array.
19///
20/// `index` is a flat open-addressed array of packed `u64` entries:
21///   bits[63:48] = 16-bit tag (hash >> 48)
22///   bits[47:0]  = Arena slot index
23/// Sentinel values: 0 = empty, u64::MAX = tombstone.
24pub struct Cache<K, V> {
25    pub(crate) index_mask: usize,
26    pub(crate) index: Box<[AtomicIndex]>,
27    pub(crate) nodes: Box<[AtomicPtr<Node<K, V>>]>,
28}
29
30unsafe impl<K: Send, V: Send> Send for Cache<K, V> {}
31unsafe impl<K: Send + Sync, V: Send + Sync> Sync for Cache<K, V> {}
32
33impl<K, V> Cache<K, V> {
34    pub fn new(capacity: usize) -> Self {
35        let index_size = (capacity * 2).next_power_of_two();
36        let mut index = Vec::with_capacity(index_size);
37        for _ in 0..index_size {
38            index.push(AtomicIndex::new(EMPTY));
39        }
40
41        let mut nodes = Vec::with_capacity(capacity);
42        for _ in 0..capacity {
43            nodes.push(AtomicPtr::new(ptr::null_mut()));
44        }
45
46        Self {
47            index_mask: index_size - 1,
48            index: index.into_boxed_slice(),
49            nodes: nodes.into_boxed_slice(),
50        }
51    }
52
53    #[inline(always)]
54    pub fn index_probe(&self, hash: u64, tag: u16) -> Option<usize> {
55        let mut idx = hash as usize & self.index_mask;
56        for _ in 0..16 {
57            let entry = self.index[idx].load(Ordering::Acquire);
58            if entry == EMPTY {
59                return None;
60            }
61            if entry != TOMBSTONE && (entry >> TAG_SHIFT) as u16 == tag {
62                return Some((entry & INDEX_MASK) as usize);
63            }
64            idx = (idx + 1) & self.index_mask;
65        }
66        None
67    }
68
69    #[inline(always)]
70    pub fn index_store(&self, hash: u64, tag: u16, entry: IndexType) {
71        let mut idx = hash as usize & self.index_mask;
72        for i in 0..16 {
73            let prev = self.index[idx].load(Ordering::Acquire);
74            if prev == EMPTY || prev == TOMBSTONE || (prev >> TAG_SHIFT) == (tag as IndexType) {
75                self.index[idx].store(entry, Ordering::Release);
76                return;
77            }
78            if i == 15 {
79                self.index[hash as usize & self.index_mask].store(entry, Ordering::Release);
80            }
81            idx = (idx + 1) & self.index_mask;
82        }
83    }
84
85    #[inline(always)]
86    pub fn index_remove(&self, hash: u64, tag: u16, g_idx: usize) {
87        let mut idx = hash as usize & self.index_mask;
88        for _ in 0..16 {
89            let entry = self.index[idx].load(Ordering::Acquire);
90            if entry == EMPTY {
91                return;
92            }
93            if entry != TOMBSTONE
94                && (entry >> TAG_SHIFT) as u16 == tag
95                && (entry & INDEX_MASK) == (g_idx as IndexType)
96            {
97                self.index[idx].store(TOMBSTONE, Ordering::Release);
98                return;
99            }
100            idx = (idx + 1) & self.index_mask;
101        }
102    }
103
104    #[inline(always)]
105    pub fn index_clear_at(&self, idx: usize) {
106        self.index[idx].store(EMPTY, Ordering::Relaxed);
107    }
108
109    #[inline(always)]
110    pub fn index_len(&self) -> usize {
111        self.index.len()
112    }
113
114    #[inline(always)]
115    pub fn get_node<'a>(&self, idx: usize) -> Option<&'a Node<K, V>> {
116        let ptr = self.nodes[idx].load(Ordering::Acquire);
117        if ptr.is_null() {
118            None
119        } else {
120            // Safety: QSBR guarantees pointer is valid during check-in.
121            Some(unsafe { &*ptr })
122        }
123    }
124
125    #[inline(always)]
126    pub fn node_get_full(&self, idx: usize, key: &K, current_epoch: u32) -> Option<V>
127    where
128        K: Eq,
129        V: Clone,
130    {
131        let ptr = self.nodes[idx].load(Ordering::Acquire);
132        if ptr.is_null() {
133            return None;
134        }
135        // Safety: QSBR guarantees pointer is valid during check-in.
136        let node = unsafe { &*ptr };
137        if node.key == *key {
138            if node.expire_at > 0 && node.expire_at < current_epoch {
139                return None;
140            }
141            Some(node.value.clone())
142        } else {
143            None
144        }
145    }
146
147    pub fn clear(&self) {
148        for i in 0..self.index.len() {
149            self.index[i].store(EMPTY, Ordering::Relaxed);
150        }
151        for i in 0..self.nodes.len() {
152            self.nodes[i].store(ptr::null_mut(), Ordering::Release);
153        }
154    }
155}
156
157impl<K, V> Drop for Cache<K, V> {
158    fn drop(&mut self) {
159        for node_ptr in self.nodes.iter() {
160            let ptr = node_ptr.swap(ptr::null_mut(), Ordering::Relaxed);
161            if !ptr.is_null() {
162                unsafe {
163                    let _ = Box::from_raw(ptr);
164                }
165            }
166        }
167    }
168}
dualcache_ff/storage.rs

dualcache_ff/
storage.rs
