wasmer_types/entity/
secondary_map.rs

1// This file contains code from external sources.
2// Attributions: https://github.com/wasmerio/wasmer/blob/master/ATTRIBUTIONS.md
3
4//! Densely numbered entity references as mapping keys.
5
6use crate::entity::iter::{Iter, IterMut};
7use crate::entity::keys::Keys;
8use crate::entity::EntityRef;
9use crate::lib::std::cmp::min;
10use crate::lib::std::marker::PhantomData;
11use crate::lib::std::ops::{Index, IndexMut};
12use crate::lib::std::slice;
13use crate::lib::std::vec::Vec;
14use rkyv::Archive;
15
16/// A mapping `K -> V` for densely indexed entity references.
17///
18/// The `SecondaryMap` data structure uses the dense index space to implement a map with a vector.
19/// Unlike `PrimaryMap`, an `SecondaryMap` can't be used to allocate entity references. It is used
20/// to associate secondary information with entities.
21///
22/// The map does not track if an entry for a key has been inserted or not. Instead it behaves as if
23/// all keys have a default entry from the beginning.
24#[derive(Debug, Clone, rkyv::Serialize, rkyv::Deserialize, rkyv::Archive)]
25pub struct SecondaryMap<K, V>
26where
27    K: EntityRef,
28    V: Clone,
29{
30    pub(crate) elems: Vec<V>,
31    pub(crate) default: V,
32    pub(crate) unused: PhantomData<K>,
33}
34
35/// Shared `SecondaryMap` implementation for all value types.
36impl<K, V> SecondaryMap<K, V>
37where
38    K: EntityRef,
39    V: Clone,
40{
41    /// Create a new empty map.
42    pub fn new() -> Self
43    where
44        V: Default,
45    {
46        Self {
47            elems: Vec::new(),
48            default: Default::default(),
49            unused: PhantomData,
50        }
51    }
52
53    /// Create a new, empty map with the specified capacity.
54    ///
55    /// The map will be able to hold exactly `capacity` elements without reallocating.
56    pub fn with_capacity(capacity: usize) -> Self
57    where
58        V: Default,
59    {
60        Self {
61            elems: Vec::with_capacity(capacity),
62            default: Default::default(),
63            unused: PhantomData,
64        }
65    }
66
67    /// Create a new empty map with a specified default value.
68    ///
69    /// This constructor does not require V to implement Default.
70    pub fn with_default(default: V) -> Self {
71        Self {
72            elems: Vec::new(),
73            default,
74            unused: PhantomData,
75        }
76    }
77
78    /// Returns the number of elements the map can hold without reallocating.
79    pub fn capacity(&self) -> usize {
80        self.elems.capacity()
81    }
82
83    /// Get the element at `k` if it exists.
84    #[inline(always)]
85    pub fn get(&self, k: K) -> Option<&V> {
86        self.elems.get(k.index())
87    }
88
89    /// Is this map completely empty?
90    #[inline(always)]
91    pub fn is_empty(&self) -> bool {
92        self.elems.is_empty()
93    }
94
95    /// Remove all entries from this map.
96    #[inline(always)]
97    pub fn clear(&mut self) {
98        self.elems.clear()
99    }
100
101    /// Iterate over all the keys and values in this map.
102    pub fn iter(&self) -> Iter<K, V> {
103        Iter::new(self.elems.iter())
104    }
105
106    /// Iterate over all the keys and values in this map, mutable edition.
107    pub fn iter_mut(&mut self) -> IterMut<K, V> {
108        IterMut::new(self.elems.iter_mut())
109    }
110
111    /// Iterate over all the keys in this map.
112    pub fn keys(&self) -> Keys<K> {
113        Keys::with_len(self.elems.len())
114    }
115
116    /// Iterate over all the values in this map.
117    pub fn values(&self) -> slice::Iter<V> {
118        self.elems.iter()
119    }
120
121    /// Iterate over all the values in this map, mutable edition.
122    pub fn values_mut(&mut self) -> slice::IterMut<V> {
123        self.elems.iter_mut()
124    }
125
126    /// Resize the map to have `n` entries by adding default entries as needed.
127    pub fn resize(&mut self, n: usize) {
128        self.elems.resize(n, self.default.clone());
129    }
130}
131
132impl<K, V> Default for SecondaryMap<K, V>
133where
134    K: EntityRef,
135    V: Clone + Default,
136{
137    fn default() -> SecondaryMap<K, V> {
138        SecondaryMap::new()
139    }
140}
141
142/// Immutable indexing into an `SecondaryMap`.
143///
144/// All keys are permitted. Untouched entries have the default value.
145impl<K, V> Index<K> for SecondaryMap<K, V>
146where
147    K: EntityRef,
148    V: Clone,
149{
150    type Output = V;
151
152    #[inline(always)]
153    fn index(&self, k: K) -> &V {
154        self.elems.get(k.index()).unwrap_or(&self.default)
155    }
156}
157
158/// Immutable indexing into an `SecondaryMap`.
159///
160/// All keys are permitted. Untouched entries have the default value.
161impl<K, V> Index<&K::Archived> for ArchivedSecondaryMap<K, V>
162where
163    K: EntityRef + Archive,
164    K::Archived: EntityRef,
165    V: Archive + Clone,
166{
167    type Output = <V as rkyv::Archive>::Archived;
168
169    fn index(&self, k: &K::Archived) -> &Self::Output {
170        &self.elems.get(k.index()).unwrap_or(&self.default)
171    }
172}
173
174/// Mutable indexing into an `SecondaryMap`.
175///
176/// The map grows as needed to accommodate new keys.
177impl<K, V> IndexMut<K> for SecondaryMap<K, V>
178where
179    K: EntityRef,
180    V: Clone,
181{
182    #[inline(always)]
183    fn index_mut(&mut self, k: K) -> &mut V {
184        let i = k.index();
185        if i >= self.elems.len() {
186            self.elems.resize(i + 1, self.default.clone());
187        }
188        &mut self.elems[i]
189    }
190}
191
192impl<K, V> PartialEq for SecondaryMap<K, V>
193where
194    K: EntityRef,
195    V: Clone + PartialEq,
196{
197    fn eq(&self, other: &Self) -> bool {
198        let min_size = min(self.elems.len(), other.elems.len());
199        self.default == other.default
200            && self.elems[..min_size] == other.elems[..min_size]
201            && self.elems[min_size..].iter().all(|e| *e == self.default)
202            && other.elems[min_size..].iter().all(|e| *e == other.default)
203    }
204}
205
206impl<K, V> Eq for SecondaryMap<K, V>
207where
208    K: EntityRef,
209    V: Clone + PartialEq + Eq,
210{
211}
212
213#[cfg(test)]
214mod tests {
215    use super::*;
216
217    // `EntityRef` impl for testing.
218    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
219    struct E(u32);
220
221    impl EntityRef for E {
222        fn new(i: usize) -> Self {
223            E(i as u32)
224        }
225        fn index(self) -> usize {
226            self.0 as usize
227        }
228    }
229
230    #[test]
231    fn basic() {
232        let r0 = E(0);
233        let r1 = E(1);
234        let r2 = E(2);
235        let mut m = SecondaryMap::new();
236
237        let v: Vec<E> = m.keys().collect();
238        assert_eq!(v, []);
239
240        m[r2] = 3;
241        m[r1] = 5;
242
243        assert_eq!(m[r1], 5);
244        assert_eq!(m[r2], 3);
245
246        let v: Vec<E> = m.keys().collect();
247        assert_eq!(v, [r0, r1, r2]);
248
249        let shared = &m;
250        assert_eq!(shared[r0], 0);
251        assert_eq!(shared[r1], 5);
252        assert_eq!(shared[r2], 3);
253    }
254}
wasmer_types/entity/secondary_map.rs

wasmer_types/entity/
secondary_map.rs
