fn_cache/
vec_cache.rs

1use crate::{FnCache, FnCacheMany};
2
3use std::sync::Arc;
4
5/// A cache for a function which uses a [`Vec`].
6///
7/// This cache is optimized for functions which must
8/// be calculated in order, so that there can be no
9/// gaps in the cache, and use `usize` as an argument.
10///
11/// If the function does not start at zero, or require
12/// every previous value to be calculated for the next
13/// one, consider using a [`HashCache`](crate::HashCache)
14/// instead.
15pub struct VecCache<'f, O> {
16	pub(crate) cache: Vec<O>,
17	f: Arc<dyn Fn(&mut Self, &usize) -> O + 'f + Send + Sync>,
18}
19
20impl<'f, O> FnCache<usize, O> for VecCache<'f, O> {
21	fn get(&mut self, input: usize) -> &O {
22		let len = self.cache.len();
23
24		if len <= input {
25			self.cache.reserve(input - len + 1);
26		}
27
28		while self.cache.len() <= input {
29			let next = self.cache.len();
30			let next_val = self.compute(next);
31			self.cache.push(next_val);
32		}
33
34		self.cache.get(input).unwrap()
35	}
36}
37
38impl<'f, O> FnCacheMany<usize, O> for VecCache<'f, O> {
39	fn get_many<const N: usize>(&mut self, inputs: [usize; N]) -> [&O; N] {
40		let len = self.cache.len();
41		let max = inputs.iter().max().copied().unwrap_or(0);
42
43		if len <= max {
44			self.cache.reserve(max - len + 1);
45		}
46
47		for i in inputs {
48			self.get(i);
49		}
50
51		inputs.map(|i| self.cache.get(i).unwrap())
52	}
53}
54
55impl<'f, O> VecCache<'f, O> {
56	/// Create a cache for the provided function. If the
57	/// function stores references, the cache can only
58	/// live as long as those references.
59	pub fn new<F>(f: F) -> Self
60	where
61		F: Fn(&usize) -> O + 'f + Send + Sync,
62	{
63		Self::recursive(move |_, x| f(x))
64	}
65
66	/// Create a cache for the provided recursive function.
67	/// If the function stores references, the cache can
68	/// only live as long as those references.
69	pub fn recursive<F>(f: F) -> Self
70	where
71		F: Fn(&mut Self, &usize) -> O + 'f + Send + Sync,
72	{
73		VecCache {
74			cache: Vec::default(),
75			f: Arc::new(f),
76		}
77	}
78
79	fn compute(&mut self, input: usize) -> O {
80		(self.f.clone())(self, &input)
81	}
82
83	/// Clears the cache. removing all values.
84	/// Keeps the allocated memory for reuse.
85	pub fn clear(&mut self) {
86		self.cache.clear();
87	}
88
89	/// Returns the number of elements in the cache.
90	pub fn len(&self) -> usize {
91		self.cache.len()
92	}
93
94	/// Reserves capacity for at least `additional` more elements
95	/// to be inserted in the cache. The collection may
96	/// reserve more space to avoid frequent reallocations.
97	pub fn reserve(&mut self, additional: usize) {
98		self.cache.reserve(additional)
99	}
100}
fn_cache/vec_cache.rs

fn_cache/
vec_cache.rs
