veloren_world/util/
small_cache.rs

1use arr_macro::arr;
2
3fn calc_idx(v: impl Iterator<Item = i32>) -> usize {
4    let mut r = 0;
5    for (e, h) in v.zip([0x6eed0e9d, 0x2f72b421, 0x18132f72, 0x891e2fba].into_iter()) {
6        r ^= (e as u32).wrapping_mul(h);
7    }
8    r as usize
9}
10
11// NOTE: Use 128 if TerrainChunkSize::RECT_SIZE.x = 128.
12const CACHE_LEN: usize = 32;
13
14pub struct SmallCache<K, V: Default> {
15    index: [Option<K>; CACHE_LEN + 9],
16    data: [V; CACHE_LEN + 9],
17    random: u32,
18}
19impl<K: Copy, V: Default> Default for SmallCache<K, V> {
20    fn default() -> Self {
21        Self {
22            index: [None; CACHE_LEN + 9],
23            data: arr![V::default(); 41], // TODO: Use CACHE_LEN
24            random: 1,
25        }
26    }
27}
28impl<K: Copy + Eq + IntoIterator<Item = i32>, V: Default> SmallCache<K, V> {
29    pub fn get<F: FnOnce(K) -> V>(&mut self, key: K, f: F) -> &V {
30        let idx = calc_idx(key.into_iter()) % CACHE_LEN;
31
32        // Search
33        if self.index[idx].as_ref().map(|k| k == &key).unwrap_or(false) {
34            return &self.data[idx];
35        } else if self.index[idx + 1]
36            .as_ref()
37            .map(|k| k == &key)
38            .unwrap_or(false)
39        {
40            return &self.data[idx + 1];
41        } else if self.index[idx + 4]
42            .as_ref()
43            .map(|k| k == &key)
44            .unwrap_or(false)
45        {
46            return &self.data[idx + 4];
47        } else if self.index[idx + 9]
48            .as_ref()
49            .map(|k| k == &key)
50            .unwrap_or(false)
51        {
52            return &self.data[idx + 9];
53        }
54        // Not present so insert
55        for i in 0..4 {
56            let idx = idx + i * i;
57            if self.index[idx].is_none() {
58                self.index[idx] = Some(key);
59                self.data[idx] = f(key);
60                return &self.data[idx];
61            }
62        }
63        // No space randomly remove someone
64        let step = super::seed_expan::diffuse(self.random) as usize % 4;
65        let idx = step * step + idx;
66        self.random = self.random.wrapping_add(1);
67        self.index[idx] = Some(key);
68        self.data[idx] = f(key);
69        &self.data[idx]
70    }
71}
veloren_world/util/small_cache.rs

veloren_world/util/
small_cache.rs
