1#![warn(missing_docs)]
4#![no_std]
5
6extern crate alloc;
7
8use alloc::boxed::Box;
9use core::{fmt, iter::FusedIterator, marker::PhantomData, ptr::addr_of_mut};
10
11#[derive(Clone)]
13pub struct LruSlab<T> {
14 slots: Box<[Slot<T>]>,
15 head: u32,
17 tail: u32,
19 free: u32,
21 len: u32,
23}
24
25impl<T> LruSlab<T> {
26 pub fn new() -> Self {
28 Self::with_capacity(0)
29 }
30
31 pub fn with_capacity(capacity: u32) -> Self {
33 assert!(capacity != u32::MAX, "capacity too large");
34 Self {
35 slots: (0..capacity)
36 .map(|n| Slot {
37 value: None,
38 prev: NONE,
39 next: if n + 1 == capacity { NONE } else { n + 1 },
40 })
41 .collect(),
42 head: NONE,
43 tail: NONE,
44 free: if capacity == 0 { NONE } else { 0 },
45 len: 0,
46 }
47 }
48
49 pub fn is_empty(&self) -> bool {
51 self.len == 0
52 }
53
54 pub fn len(&self) -> u32 {
56 self.len
57 }
58
59 pub fn capacity(&self) -> u32 {
61 self.slots.len() as u32
62 }
63
64 pub fn vacant_key(&self) -> u32 {
66 match self.free {
67 NONE => self.capacity(),
68 _ => self.free,
69 }
70 }
71
72 pub fn insert(&mut self, value: T) -> u32 {
76 let id = match self.alloc() {
77 Some(id) => id,
78 None => {
79 let len = self.capacity();
80 let cap = 2u32.saturating_mul(len.max(2)).min(u32::MAX - 1);
82 if cap == len {
83 panic!("cannot store more than 2^32-2 elements");
84 }
85 self.slots = self
86 .slots
87 .iter_mut()
88 .map(|x| Slot {
89 value: x.value.take(),
90 next: x.next,
91 prev: x.prev,
92 })
93 .chain((len..cap).map(|n| Slot {
94 value: None,
95 prev: NONE,
96 next: if n + 1 == cap { NONE } else { n + 1 },
97 }))
98 .collect();
99 self.free = len + 1;
100 len
101 }
102 };
103 let idx = id as usize;
104
105 debug_assert!(self.slots[idx].value.is_none(), "corrupt free list");
106 self.slots[idx].value = Some(value);
107 self.link_at_head(id);
108 self.len += 1;
109
110 id
111 }
112
113 pub fn lru(&self) -> Option<u32> {
115 if self.tail == NONE {
116 debug_assert_eq!(self.head, NONE);
117 None
118 } else {
119 Some(self.tail)
120 }
121 }
122
123 pub fn remove(&mut self, slot: u32) -> T {
125 let value = self.slots[slot as usize]
126 .value
127 .take()
128 .expect("removing empty slot");
129 self.unlink(slot);
130 self.slots[slot as usize].next = self.free;
131 self.slots[slot as usize].prev = NONE;
132 self.free = slot;
133 self.len -= 1;
134 value
135 }
136
137 pub fn get_mut(&mut self, slot: u32) -> &mut T {
139 self.freshen(slot);
140 self.peek_mut(slot)
141 }
142
143 pub fn peek(&self, slot: u32) -> &T {
145 self.slots[slot as usize].value.as_ref().unwrap()
146 }
147
148 pub fn peek_mut(&mut self, slot: u32) -> &mut T {
150 self.slots[slot as usize].value.as_mut().unwrap()
151 }
152
153 pub fn iter(&self) -> Iter<'_, T> {
155 let state = IterState::new(self);
156 Iter {
157 slots: &self.slots[..],
158 state,
159 }
160 }
161
162 pub fn iter_mut(&mut self) -> IterMut<'_, T> {
164 let state = IterState::new(self);
165 IterMut {
166 slots: self.slots[..].as_mut_ptr().cast(),
167 state,
168 _marker: PhantomData,
169 }
170 }
171
172 fn alloc(&mut self) -> Option<u32> {
174 if self.free == NONE {
175 return None;
176 }
177 let slot = self.free;
178 self.free = self.slots[slot as usize].next;
179 Some(slot)
180 }
181
182 fn freshen(&mut self, slot: u32) {
184 if self.slots[slot as usize].prev == NONE {
185 debug_assert_eq!(self.head, slot, "corrupt LRU list");
187 return;
188 }
189
190 self.unlink(slot);
191 self.link_at_head(slot);
192 }
193
194 fn link_at_head(&mut self, slot: u32) {
196 let idx = slot as usize;
197 if self.head == NONE {
198 self.slots[idx].next = NONE;
200 self.tail = slot;
201 } else {
202 self.slots[idx].next = self.head;
203 self.slots[self.head as usize].prev = slot;
204 }
205 self.slots[idx].prev = NONE;
206 self.head = slot;
207 }
208
209 fn unlink(&mut self, slot: u32) {
211 let idx = slot as usize;
212 if self.slots[idx].prev != NONE {
213 self.slots[self.slots[idx].prev as usize].next = self.slots[idx].next;
214 } else {
215 self.head = self.slots[idx].next;
216 }
217 if self.slots[idx].next != NONE {
218 self.slots[self.slots[idx].next as usize].prev = self.slots[idx].prev;
219 } else {
220 self.tail = self.slots[idx].prev;
222 }
223 }
224}
225
226impl<T> Default for LruSlab<T> {
227 fn default() -> Self {
228 Self::new()
229 }
230}
231
232impl<T> FromIterator<T> for LruSlab<T> {
233 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
234 let iter = iter.into_iter();
235 let mut slab = LruSlab::with_capacity(u32::try_from(iter.size_hint().0).unwrap());
236 for x in iter {
237 slab.insert(x);
238 }
239 slab
240 }
241}
242
243impl<'a, T> IntoIterator for &'a LruSlab<T> {
244 type Item = (u32, &'a T);
245
246 type IntoIter = Iter<'a, T>;
247
248 fn into_iter(self) -> Self::IntoIter {
249 self.iter()
250 }
251}
252
253impl<'a, T> IntoIterator for &'a mut LruSlab<T> {
254 type Item = (u32, &'a mut T);
255
256 type IntoIter = IterMut<'a, T>;
257
258 fn into_iter(self) -> Self::IntoIter {
259 self.iter_mut()
260 }
261}
262
263impl<T: fmt::Debug> fmt::Debug for LruSlab<T> {
264 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
265 f.debug_map().entries(self).finish()
266 }
267}
268
269#[derive(Clone)]
270struct Slot<T> {
271 value: Option<T>,
272 next: u32,
274 prev: u32,
276}
277
278const NONE: u32 = u32::MAX;
279
280pub struct Iter<'a, T> {
282 slots: &'a [Slot<T>],
283 state: IterState,
284}
285
286impl<'a, T> Iterator for Iter<'a, T> {
287 type Item = (u32, &'a T);
288 fn next(&mut self) -> Option<(u32, &'a T)> {
289 let idx = self.state.next(|i| self.slots[i as usize].next)?;
290 let result = self.slots[idx as usize]
291 .value
292 .as_ref()
293 .expect("corrupt LRU list");
294 Some((idx, result))
295 }
296
297 fn size_hint(&self) -> (usize, Option<usize>) {
298 (self.state.len as usize, Some(self.state.len as usize))
299 }
300}
301
302impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
303 fn next_back(&mut self) -> Option<(u32, &'a T)> {
304 let idx = self.state.next_back(|i| self.slots[i as usize].prev)?;
305 let result = self.slots[idx as usize]
306 .value
307 .as_ref()
308 .expect("corrupt LRU list");
309 Some((idx, result))
310 }
311}
312
313impl<T> ExactSizeIterator for Iter<'_, T> {
314 fn len(&self) -> usize {
315 self.state.len as usize
316 }
317}
318
319impl<T> FusedIterator for Iter<'_, T> {}
320
321pub struct IterMut<'a, T> {
323 slots: *mut Slot<T>,
324 state: IterState,
325 _marker: PhantomData<&'a mut [Slot<T>]>,
326}
327
328impl<'a, T> Iterator for IterMut<'a, T> {
329 type Item = (u32, &'a mut T);
330 fn next(&mut self) -> Option<(u32, &'a mut T)> {
331 unsafe {
334 let idx = self
335 .state
336 .next(|i| *addr_of_mut!((*self.slots.add(i as usize)).next))?;
337 let result = (*addr_of_mut!((*self.slots.add(idx as usize)).value))
338 .as_mut()
339 .expect("corrupt LRU list");
340 Some((idx, result))
341 }
342 }
343
344 fn size_hint(&self) -> (usize, Option<usize>) {
345 (self.state.len as usize, Some(self.state.len as usize))
346 }
347}
348
349impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
350 fn next_back(&mut self) -> Option<(u32, &'a mut T)> {
351 unsafe {
354 let idx = self
355 .state
356 .next_back(|i| *addr_of_mut!((*self.slots.add(i as usize)).prev))?;
357 let result = (*addr_of_mut!((*self.slots.add(idx as usize)).value))
358 .as_mut()
359 .expect("corrupt LRU list");
360 Some((idx, result))
361 }
362 }
363}
364
365impl<T> ExactSizeIterator for IterMut<'_, T> {
366 fn len(&self) -> usize {
367 self.state.len as usize
368 }
369}
370
371impl<T> FusedIterator for IterMut<'_, T> {}
372
373struct IterState {
374 head: u32,
375 tail: u32,
376 len: u32,
377}
378
379impl IterState {
380 fn new<T>(slab: &LruSlab<T>) -> Self {
381 Self {
382 head: slab.head,
383 tail: slab.tail,
384 len: slab.len,
385 }
386 }
387
388 fn next(&mut self, get_next: impl Fn(u32) -> u32) -> Option<u32> {
389 if self.len == 0 {
390 return None;
391 }
392 let idx = self.head;
393 self.head = get_next(idx);
394 self.len -= 1;
395 Some(idx)
396 }
397
398 fn next_back(&mut self, get_prev: impl Fn(u32) -> u32) -> Option<u32> {
399 if self.len == 0 {
400 return None;
401 }
402 let idx = self.tail;
403 self.tail = get_prev(idx);
404 self.len -= 1;
405 Some(idx)
406 }
407}
408
409#[cfg(test)]
410mod tests {
411 extern crate std;
412
413 use alloc::{format, string::String, vec::Vec};
414 use self::std::panic::{catch_unwind, AssertUnwindSafe};
415
416 use super::*;
417
418 #[test]
419 fn removing_vacant_slot_preserves_state() {
420 let mut slab = [42].into_iter().collect::<LruSlab<_>>();
421 let vacant = slab.insert(0);
422 slab.remove(vacant);
423 let before = (slab.len, slab.head, slab.tail, slab.free);
424 assert!(catch_unwind(AssertUnwindSafe(|| slab.remove(vacant))).is_err());
425 assert_eq!((slab.len, slab.head, slab.tail, slab.free), before);
426 }
427
428 #[test]
429 fn lru_order() {
430 let mut cache = LruSlab::new();
431 let b = cache.insert('b');
432 assert_eq!(cache.iter().map(|(_, x)| x).collect::<String>(), "b");
433 let _a = cache.insert('a');
434 assert_eq!(cache.iter().map(|(_, x)| x).collect::<String>(), "ab");
435 let d = cache.insert('d');
436 assert_eq!(cache.iter().map(|(_, x)| x).collect::<String>(), "dab");
437 let c = cache.insert('c');
438 assert_eq!(cache.iter().map(|(_, x)| x).collect::<String>(), "cdab");
439 let e = cache.insert('e');
440 assert_eq!(cache.iter().map(|(_, x)| x).collect::<String>(), "ecdab");
441
442 cache.get_mut(b);
443 cache.get_mut(c);
444 cache.get_mut(d);
445 cache.get_mut(e);
446
447 assert_eq!(cache.remove(cache.lru().unwrap()), 'a');
448 assert_eq!(cache.remove(cache.lru().unwrap()), 'b');
449 assert_eq!(cache.remove(cache.lru().unwrap()), 'c');
450 assert_eq!(cache.remove(cache.lru().unwrap()), 'd');
451 assert_eq!(cache.remove(cache.lru().unwrap()), 'e');
452 assert!(cache.lru().is_none());
453 }
454
455 #[test]
456 fn slot_reuse() {
457 let mut cache = LruSlab::new();
458 let a = cache.insert('a');
459 cache.remove(a);
460 let a_prime = cache.insert('a');
461 assert_eq!(a, a_prime);
462 assert_eq!(cache.len(), 1);
463 }
464
465 #[test]
466 fn debug() {
467 let slab = ['a', 'b'].into_iter().collect::<LruSlab<_>>();
468 assert_eq!(format!("{:?}", slab), "{1: 'b', 0: 'a'}");
469 }
470
471 #[test]
472 fn iter_reverse() {
473 let slab = ['a', 'b'].into_iter().collect::<LruSlab<_>>();
474 let mut double_reversed = slab.iter().rev().collect::<Vec<_>>();
475 double_reversed.reverse();
476 assert_eq!(slab.iter().collect::<Vec<_>>(), double_reversed);
477 }
478
479 #[test]
480 fn vacant_key() {
481 let mut slab = LruSlab::new();
482 assert_eq!(slab.vacant_key(), 0);
483 slab.insert(());
484 assert_eq!(slab.vacant_key(), 1);
485 slab.remove(0);
486 assert_eq!(slab.vacant_key(), 0);
487 }
488}