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 _ 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            idx = (idx + 1) & self.index_mask;
79        }
80    }
81
82    #[inline(always)]
83    pub fn index_remove(&self, hash: u64, tag: u16, g_idx: usize) {
84        let mut idx = hash as usize & self.index_mask;
85        for _ in 0..16 {
86            let entry = self.index[idx].load(Ordering::Acquire);
87            if entry == EMPTY {
88                return;
89            }
90            if entry != TOMBSTONE
91                && (entry >> TAG_SHIFT) as u16 == tag
92                && (entry & INDEX_MASK) == (g_idx as IndexType)
93            {
94                self.index[idx].store(TOMBSTONE, Ordering::Release);
95                return;
96            }
97            idx = (idx + 1) & self.index_mask;
98        }
99    }
100
101    #[inline(always)]
102    pub fn index_clear_at(&self, idx: usize) {
103        self.index[idx].store(EMPTY, Ordering::Relaxed);
104    }
105
106    #[inline(always)]
107    pub fn index_len(&self) -> usize {
108        self.index.len()
109    }
110
111    #[inline(always)]
112    pub fn get_node<'a>(&self, idx: usize) -> Option<&'a Node<K, V>> {
113        let ptr = self.nodes[idx].load(Ordering::Acquire);
114        if ptr.is_null() {
115            None
116        } else {
117            // Safety: QSBR guarantees pointer is valid during check-in.
118            Some(unsafe { &*ptr })
119        }
120    }
121
122    #[inline(always)]
123    pub fn node_get_full(&self, idx: usize, key: &K, current_epoch: u32) -> Option<V>
124    where
125        K: Eq,
126        V: Clone,
127    {
128        let ptr = self.nodes[idx].load(Ordering::Acquire);
129        if ptr.is_null() {
130            return None;
131        }
132        // Safety: QSBR guarantees pointer is valid during check-in.
133        let node = unsafe { &*ptr };
134        if node.key == *key {
135            if node.expire_at > 0 && node.expire_at < current_epoch {
136                return None;
137            }
138            Some(node.value.clone())
139        } else {
140            None
141        }
142    }
143
144    pub fn clear(&self) {
145        for i in 0..self.index.len() {
146            self.index[i].store(EMPTY, Ordering::Relaxed);
147        }
148        for i in 0..self.nodes.len() {
149            self.nodes[i].store(ptr::null_mut(), Ordering::Release);
150        }
151    }
152}
153
154impl<K, V> Drop for Cache<K, V> {
155    fn drop(&mut self) {
156        for node_ptr in self.nodes.iter() {
157            let ptr = node_ptr.swap(ptr::null_mut(), Ordering::Relaxed);
158            if !ptr.is_null() {
159                unsafe {
160                    let _ = Box::from_raw(ptr);
161                }
162            }
163        }
164    }
165}
dualcache_ff/storage.rs

dualcache_ff/
storage.rs
