llkv_btree/
node_cache.rs

1use crate::pager::Pager;
2use rustc_hash::FxHashMap;
3
4// ================================ LRU cache ==================================
5//
6// Lightweight intrusive LRU with O(1) get/insert/invalidate.
7// Stores pager pages (P::Page) keyed by page Id (P::Id).
8//
9// Design:
10// - HashMap<Id, Entry> where Entry holds page and prev/next links.
11// - Doubly-linked list by Ids via head/tail and per-entry links.
12// - On get: move to head, return cloned Page.
13// - On insert: insert at head, evict tail if over capacity.
14// - On invalidate: remove entry and fix links.
15// - No eviction work on hit.
16// - Page type must be cheap to clone (Arc<[u8]> in tests).
17
18struct LruEntry<Id, Page> {
19    page: Page,
20    prev: Option<Id>,
21    next: Option<Id>,
22}
23
24pub struct NodeCache<P>
25where
26    P: Pager,
27    P::Page: Clone,
28    P::Id: Clone + Eq + std::hash::Hash,
29{
30    map: FxHashMap<P::Id, LruEntry<P::Id, P::Page>>,
31    head: Option<P::Id>,
32    tail: Option<P::Id>,
33    cap: usize,
34}
35
36impl<P> Default for NodeCache<P>
37where
38    P: Pager,
39    P::Page: Clone,
40    P::Id: Clone + Eq + std::hash::Hash,
41{
42    fn default() -> Self {
43        NodeCache::<P>::new(1024, 2)
44    }
45}
46
47impl<P> NodeCache<P>
48where
49    P: Pager,
50    P::Page: Clone,
51    P::Id: Clone + Eq + std::hash::Hash,
52{
53    #[inline]
54    pub fn new(cap: usize, _unused: usize) -> Self {
55        // _unused kept for API compatibility with prior versions.
56        let cap = cap.max(1);
57        Self {
58            map: FxHashMap::default(),
59            head: None,
60            tail: None,
61            cap,
62        }
63    }
64
65    /// Return a clone of the cached page without mutating LRU state.
66    #[inline]
67    pub fn peek(&self, id: &P::Id) -> Option<P::Page> {
68        self.map.get(id).map(|e| e.page.clone())
69    }
70
71    /// Promote an entry to MRU if it exists (no-op if missing).
72    #[inline]
73    pub fn touch(&mut self, id: &P::Id) {
74        if self.map.contains_key(id) {
75            self.move_to_head(id);
76        }
77    }
78
79    #[inline]
80    pub fn set_limits(&mut self, read_cap: usize, _sweep_factor: usize) {
81        self.cap = read_cap.max(1);
82        while self.map.len() > self.cap {
83            self.evict_one();
84        }
85    }
86
87    #[inline]
88    pub fn get(&mut self, id: &P::Id) -> Option<P::Page> {
89        if !self.map.contains_key(id) {
90            return None;
91        }
92        self.move_to_head(id);
93        self.map.get(id).map(|e| e.page.clone())
94    }
95
96    #[inline]
97    pub fn insert(&mut self, id: P::Id, page: P::Page) {
98        if self.map.contains_key(&id) {
99            // Update page and move to MRU.
100            if let Some(e) = self.map.get_mut(&id) {
101                e.page = page;
102            }
103            self.move_to_head(&id);
104            return;
105        }
106        // Insert new at head.
107        let old_head = self.head.clone();
108        let entry = LruEntry {
109            page,
110            prev: None,
111            next: old_head.clone(),
112        };
113        self.map.insert(id.clone(), entry);
114        if let Some(h) = old_head
115            && let Some(e) = self.map.get_mut(&h)
116        {
117            e.prev = Some(id.clone());
118        }
119        self.head = Some(id.clone());
120        if self.tail.is_none() {
121            self.tail = Some(id.clone());
122        }
123        if self.map.len() > self.cap {
124            self.evict_one();
125        }
126    }
127
128    #[inline]
129    pub fn invalidate(&mut self, id: &P::Id) {
130        if !self.map.contains_key(id) {
131            return;
132        }
133        let (prev, next) = {
134            let e = self.map.get(id).unwrap();
135            (e.prev.clone(), e.next.clone())
136        };
137        // Fix neighbors.
138        if let Some(p) = prev.clone()
139            && let Some(pe) = self.map.get_mut(&p)
140        {
141            pe.next = next.clone();
142        }
143        if let Some(n) = next.clone()
144            && let Some(ne) = self.map.get_mut(&n)
145        {
146            ne.prev = prev.clone();
147        }
148        // Fix head/tail.
149        if self.head.as_ref() == Some(id) {
150            self.head = next;
151        }
152        if self.tail.as_ref() == Some(id) {
153            self.tail = prev;
154        }
155        self.map.remove(id);
156    }
157
158    #[inline]
159    pub fn clear(&mut self) {
160        self.map.clear();
161        self.head = None;
162        self.tail = None;
163    }
164
165    #[inline]
166    fn move_to_head(&mut self, id: &P::Id) {
167        if self.head.as_ref() == Some(id) {
168            return;
169        }
170        let (prev, next) = {
171            let e = self.map.get(id).unwrap();
172            (e.prev.clone(), e.next.clone())
173        };
174        // Detach from current spot.
175        if let Some(p) = prev.clone()
176            && let Some(pe) = self.map.get_mut(&p)
177        {
178            pe.next = next.clone();
179        }
180        if let Some(n) = next.clone()
181            && let Some(ne) = self.map.get_mut(&n)
182        {
183            ne.prev = prev.clone();
184        }
185        if self.tail.as_ref() == Some(id) {
186            self.tail = prev.clone();
187        }
188        // Attach at head.
189        let old_head = self.head.clone();
190        if let Some(e) = self.map.get_mut(id) {
191            e.prev = None;
192            e.next = old_head.clone();
193        }
194        if let Some(h) = old_head
195            && let Some(he) = self.map.get_mut(&h)
196        {
197            he.prev = Some(id.clone());
198        }
199        self.head = Some(id.clone());
200        if self.tail.is_none() {
201            self.tail = Some(id.clone());
202        }
203    }
204
205    #[inline]
206    fn evict_one(&mut self) {
207        let Some(tid) = self.tail.clone() else {
208            return;
209        };
210        self.invalidate(&tid);
211    }
212}
llkv_btree/node_cache.rs

llkv_btree/
node_cache.rs
