dualcache_ff/
arena.rs

1#[cfg(not(feature = "std"))]
2use alloc::{vec, vec::Vec};
3
4/// Slot allocator with QSBR epoch tracking support.
5///
6/// Tracks per-slot rank (frequency score) in a flat array for O(1)
7/// eviction candidate selection. The free_list stack provides O(1)
8/// slot allocation and reclamation.
9pub struct Arena {
10    pub(crate) capacity: usize,
11    pub(crate) cursor: usize,
12    pub(crate) rank: Vec<u8>,
13    pub hashes: Vec<u64>,
14    pub(crate) free_list: Vec<usize>,
15    pub(crate) count_sum: u64,
16}
17
18unsafe impl Send for Arena {}
19unsafe impl Sync for Arena {}
20
21impl Arena {
22    pub fn new(capacity: usize) -> Self {
23        Self {
24            capacity,
25            cursor: 0,
26            rank: vec![0; capacity],
27            hashes: vec![0; capacity],
28            free_list: (0..capacity).collect(),
29            count_sum: 0,
30        }
31    }
32
33    #[inline(always)]
34    pub fn pop_free_slot(&mut self) -> Option<usize> {
35        self.free_list.pop()
36    }
37
38    #[inline(always)]
39    pub fn push_free_slot(&mut self, idx: usize) {
40        self.free_list.push(idx);
41    }
42
43    #[inline(always)]
44    pub fn free_list_empty(&self) -> bool {
45        self.free_list.is_empty()
46    }
47
48    #[inline(always)]
49    pub fn free_list_len(&self) -> usize {
50        self.free_list.len()
51    }
52
53    #[inline(always)]
54    pub fn set_hash(&mut self, idx: usize, hash: u64) {
55        self.hashes[idx] = hash;
56    }
57
58    #[inline(always)]
59    pub fn get_hash(&self, idx: usize) -> u64 {
60        self.hashes[idx]
61    }
62
63    #[inline(always)]
64    pub fn set_rank(&mut self, idx: usize, rank: u8) {
65        let old = self.rank[idx];
66        self.rank[idx] = rank;
67        self.count_sum = self.count_sum - old as u64 + rank as u64;
68    }
69
70    #[inline(always)]
71    pub fn get_rank(&self, idx: usize) -> u8 {
72        self.rank[idx]
73    }
74
75    #[inline(always)]
76    pub fn decrement_rank(&mut self, idx: usize) {
77        if self.rank[idx] > 0 {
78            self.rank[idx] -= 1;
79            self.count_sum -= 1;
80        }
81    }
82
83    #[inline(always)]
84    pub fn count_sum(&self) -> u64 {
85        self.count_sum
86    }
87
88    #[inline(always)]
89    pub fn cursor(&self) -> usize {
90        self.cursor
91    }
92
93    #[inline(always)]
94    pub fn advance_cursor(&mut self) {
95        self.cursor = (self.cursor + 1) % self.capacity;
96    }
97
98    pub fn clear(&mut self) {
99        self.free_list = (0..self.capacity).collect();
100        self.rank.fill(0);
101        self.cursor = 0;
102        self.count_sum = 0;
103    }
104}
dualcache_ff/arena.rs

dualcache_ff/
arena.rs
