queue_file/
cache.rs

1//! Element position caching for optimized random access.
2//!
3//! This module provides the [`OffsetCache`] which stores element positions
4//! to accelerate [`Iter::nth`] operations on large queues. Without caching,
5//! seeking to element N requires O(N) reads from the beginning. With caching,
6//! this is reduced based on the chosen policy.
7
8use std::cell::{Cell, RefCell};
9use std::collections::VecDeque;
10
11use crate::Element;
12
13/// Maximum number of cached element positions.
14const MAX_CACHE_SIZE: usize = 4096;
15
16/// Policy controlling how element file-positions are cached to accelerate [`Iter::nth`].
17#[derive(Debug, Clone, Copy, PartialEq, Eq)]
18pub enum OffsetCacheKind {
19    /// Cache one position every `offset` elements.
20    ///
21    /// This policy provides a fixed seek performance (O(offset)) at the cost
22    /// of O(N/offset) memory usage.
23    Linear { offset: usize },
24    /// Cache positions at indices that are perfect squares (1, 4, 9, 16, 25, …).
25    ///
26    /// This policy provides a good trade-off between memory usage (O(√N)) and
27    /// seek performance (O(√N)).
28    Quadratic,
29}
30
31/// Cache for element positions to accelerate random access iteration.
32#[derive(Debug, Clone)]
33pub struct OffsetCache {
34    /// Cached (index, element) pairs.
35    pub(crate) offsets: RefCell<VecDeque<(usize, Element)>>,
36    /// The caching policy, if any.
37    pub(crate) kind: Option<OffsetCacheKind>,
38    /// Number of elements removed since cache creation.
39    pub(crate) total_removed: Cell<usize>,
40}
41
42impl OffsetCache {
43    /// Creates a new empty cache.
44    pub const fn new() -> Self {
45        Self { offsets: RefCell::new(VecDeque::new()), kind: None, total_removed: Cell::new(0) }
46    }
47
48    /// Sets the caching policy.
49    ///
50    /// Passing `None` disables caching and clears any existing cache.
51    pub fn set_policy(&mut self, kind: impl Into<Option<OffsetCacheKind>>) {
52        self.kind = kind.into();
53
54        if self.kind.is_none() {
55            self.clear();
56        }
57    }
58
59    /// Clears all cached offsets.
60    pub fn clear(&self) {
61        self.offsets.borrow_mut().clear();
62        self.total_removed.set(0);
63    }
64
65    /// Conditionally caches an element position based on the current policy.
66    ///
67    /// Called during iteration to cache element positions for future lookups.
68    pub fn cache_elem_if_needed(
69        &self, index: usize, elem: Element, elem_cnt: usize, affected_items: usize,
70    ) {
71        debug_assert!(index <= elem_cnt);
72        debug_assert!(index + 1 >= affected_items);
73
74        let need_to_cache = match self.kind {
75            Some(OffsetCacheKind::Linear { offset }) => {
76                let last_cached_abs_index = self.offsets.borrow().back().map_or(0, |(idx, _)| *idx);
77                let last_cached_rel_index =
78                    last_cached_abs_index.saturating_sub(self.total_removed.get());
79                Self::should_cache_linear(index, offset, last_cached_rel_index)
80            }
81            Some(OffsetCacheKind::Quadratic) => Self::should_cache_quadratic(index, affected_items),
82            None => false,
83        };
84
85        if !need_to_cache {
86            return;
87        }
88
89        let abs_index = index + self.total_removed.get();
90        let mut offsets = self.offsets.borrow_mut();
91
92        if let Some(&(last_cached_index, last_cached_elem)) = offsets.back() {
93            if last_cached_index >= abs_index {
94                if last_cached_index == abs_index {
95                    debug_assert_eq!(last_cached_elem.pos, elem.pos);
96                    debug_assert_eq!(last_cached_elem.len, elem.len);
97                }
98
99                return;
100            }
101        }
102
103        offsets.push_back((abs_index, elem));
104
105        if offsets.len() > MAX_CACHE_SIZE {
106            offsets.pop_front();
107        }
108    }
109
110    #[inline]
111    const fn should_cache_linear(index: usize, offset: usize, last_cached_index: usize) -> bool {
112        index.saturating_sub(last_cached_index) >= offset
113    }
114
115    #[inline]
116    fn should_cache_quadratic(index: usize, affected_items: usize) -> bool {
117        let x = (index as f64).sqrt() as usize;
118        x > 1 && (index + 1 - affected_items..=index).contains(&(x * x))
119    }
120
121    /// Returns the cached offset closest to but not exceeding `i`.
122    ///
123    /// Used by [`Iter::nth`] to jump directly to a cached position.
124    #[inline]
125    pub fn cached_offset_up_to(&self, i: usize) -> Option<(usize, Element)> {
126        let abs_i = i + self.total_removed.get();
127        let offsets = self.offsets.borrow();
128        let idx = offsets
129            .binary_search_by(|(idx, _)| idx.cmp(&abs_i))
130            .map_or_else(|i| i.checked_sub(1), Some)?;
131
132        let (abs_idx, elem) = offsets[idx];
133        Some((abs_idx.saturating_sub(self.total_removed.get()), elem))
134    }
135
136    /// Marks `n` elements as removed, updating internal counters.
137    ///
138    /// Called after [`QueueFile::remove_n`] to adjust cache state.
139    pub fn drop_up_to(&self, n: usize) {
140        self.total_removed.set(self.total_removed.get() + n);
141        let mut offsets = self.offsets.borrow_mut();
142        while matches!(offsets.front(), Some((index, _)) if *index < self.total_removed.get()) {
143            offsets.pop_front();
144        }
145    }
146}
queue_file/cache.rs

queue_file/
cache.rs
