reifydb_core/encoded/shape/
cache.rs

1// SPDX-License-Identifier: AGPL-3.0-or-later
2// Copyright (c) 2026 ReifyDB
3
4use std::{cell::RefCell, collections::HashMap};
5
6use crate::encoded::shape::{RowShape, fingerprint::RowShapeFingerprint};
7
8#[derive(Debug)]
9pub struct RowShapeCacheCell {
10	inner: RefCell<Inner>,
11}
12
13#[derive(Debug)]
14struct Inner {
15	map: HashMap<RowShapeFingerprint, Entry>,
16	capacity: usize,
17	counter: u64,
18}
19
20#[derive(Debug)]
21struct Entry {
22	shape: RowShape,
23	last_access: u64,
24}
25
26impl Inner {
27	fn evict_lru(&mut self) {
28		let mut oldest_key: Option<RowShapeFingerprint> = None;
29		let mut oldest_access = u64::MAX;
30		for (key, entry) in self.map.iter() {
31			if entry.last_access < oldest_access {
32				oldest_access = entry.last_access;
33				oldest_key = Some(*key);
34			}
35		}
36		if let Some(key) = oldest_key {
37			self.map.remove(&key);
38		}
39	}
40}
41
42impl RowShapeCacheCell {
43	pub fn new(capacity: usize) -> Self {
44		assert!(capacity > 0, "RowShapeCacheCell capacity must be greater than 0");
45		Self {
46			inner: RefCell::new(Inner {
47				map: HashMap::with_capacity(capacity),
48				capacity,
49				counter: 0,
50			}),
51		}
52	}
53
54	pub fn get(&self, fingerprint: &RowShapeFingerprint) -> Option<RowShape> {
55		let mut inner = self.inner.borrow_mut();
56		let access = inner.counter;
57		let shape = match inner.map.get_mut(fingerprint) {
58			Some(entry) => {
59				entry.last_access = access;
60				entry.shape.clone()
61			}
62			None => return None,
63		};
64		inner.counter += 1;
65		Some(shape)
66	}
67
68	pub fn insert(&self, shape: RowShape) {
69		let fingerprint = shape.fingerprint();
70		let mut inner = self.inner.borrow_mut();
71		let access = inner.counter;
72		inner.counter += 1;
73
74		if let Some(entry) = inner.map.get_mut(&fingerprint) {
75			entry.shape = shape;
76			entry.last_access = access;
77			return;
78		}
79
80		if inner.map.len() >= inner.capacity {
81			inner.evict_lru();
82		}
83
84		inner.map.insert(
85			fingerprint,
86			Entry {
87				shape,
88				last_access: access,
89			},
90		);
91	}
92
93	pub fn contains_key(&self, fingerprint: &RowShapeFingerprint) -> bool {
94		self.inner.borrow().map.contains_key(fingerprint)
95	}
96
97	pub fn clear(&self) {
98		self.inner.borrow_mut().map.clear();
99	}
100
101	pub fn len(&self) -> usize {
102		self.inner.borrow().map.len()
103	}
104
105	pub fn is_empty(&self) -> bool {
106		self.inner.borrow().map.is_empty()
107	}
108
109	pub fn capacity(&self) -> usize {
110		self.inner.borrow().capacity
111	}
112}
113
114#[cfg(test)]
115mod tests {
116	use reifydb_value::value::value_type::ValueType;
117
118	use super::*;
119
120	fn shape(types: &[ValueType]) -> RowShape {
121		RowShape::testing(types)
122	}
123
124	#[test]
125	fn insert_then_get_returns_same_shape() {
126		let cache = RowShapeCacheCell::new(2);
127		let s = shape(&[ValueType::Int4]);
128		let fp = s.fingerprint();
129
130		cache.insert(s.clone());
131
132		assert_eq!(cache.get(&fp), Some(s));
133	}
134
135	#[test]
136	fn get_absent_fingerprint_returns_none() {
137		let cache = RowShapeCacheCell::new(2);
138		let absent = shape(&[ValueType::Int4]).fingerprint();
139
140		assert_eq!(cache.get(&absent), None);
141	}
142
143	#[test]
144	fn evicts_least_recently_used_when_at_capacity() {
145		let cache = RowShapeCacheCell::new(2);
146		let a = shape(&[ValueType::Int4]);
147		let b = shape(&[ValueType::Int8]);
148		let c = shape(&[ValueType::Utf8]);
149
150		cache.insert(a.clone());
151		cache.insert(b.clone());
152		// a is the least-recently-used, so inserting c must evict a, not b/c.
153		cache.insert(c.clone());
154
155		assert_eq!(cache.get(&a.fingerprint()), None);
156		assert_eq!(cache.get(&b.fingerprint()), Some(b));
157		assert_eq!(cache.get(&c.fingerprint()), Some(c));
158	}
159
160	#[test]
161	fn get_promotes_recency_and_protects_from_eviction() {
162		let cache = RowShapeCacheCell::new(2);
163		let a = shape(&[ValueType::Int4]);
164		let b = shape(&[ValueType::Int8]);
165		let c = shape(&[ValueType::Utf8]);
166
167		cache.insert(a.clone());
168		cache.insert(b.clone());
169		// Touch a so it becomes more recent than b; the next insert must evict b.
170		cache.get(&a.fingerprint());
171		cache.insert(c.clone());
172
173		assert_eq!(cache.get(&a.fingerprint()), Some(a));
174		assert_eq!(cache.get(&b.fingerprint()), None);
175		assert_eq!(cache.get(&c.fingerprint()), Some(c));
176	}
177
178	#[test]
179	fn insert_existing_fingerprint_updates_in_place_without_growing() {
180		let cache = RowShapeCacheCell::new(2);
181		let s = shape(&[ValueType::Int4]);
182
183		cache.insert(s.clone());
184		cache.insert(s.clone());
185
186		assert_eq!(cache.len(), 1);
187		assert_eq!(cache.get(&s.fingerprint()), Some(s));
188	}
189
190	#[test]
191	fn reports_contains_len_is_empty_and_capacity() {
192		let cache = RowShapeCacheCell::new(3);
193		assert!(cache.is_empty());
194		assert_eq!(cache.capacity(), 3);
195
196		let s = shape(&[ValueType::Int4]);
197		cache.insert(s.clone());
198
199		assert!(cache.contains_key(&s.fingerprint()));
200		assert!(!cache.contains_key(&shape(&[ValueType::Int8]).fingerprint()));
201		assert_eq!(cache.len(), 1);
202		assert!(!cache.is_empty());
203	}
204
205	#[test]
206	fn clear_removes_all_entries() {
207		let cache = RowShapeCacheCell::new(2);
208		cache.insert(shape(&[ValueType::Int4]));
209		cache.insert(shape(&[ValueType::Int8]));
210
211		cache.clear();
212
213		assert!(cache.is_empty());
214		assert_eq!(cache.len(), 0);
215	}
216
217	#[test]
218	#[should_panic]
219	fn new_with_zero_capacity_panics() {
220		RowShapeCacheCell::new(0);
221	}
222}
reifydb_core/encoded/shape/cache.rs

reifydb_core/encoded/shape/
cache.rs
