cranelift_entity/
boxed_slice.rs

1//! Boxed slices for `PrimaryMap`.
2
3use crate::iter::{Iter, IterMut};
4use crate::keys::Keys;
5use crate::EntityRef;
6use alloc::boxed::Box;
7use core::marker::PhantomData;
8use core::ops::{Index, IndexMut};
9use core::slice;
10
11/// A slice mapping `K -> V` allocating dense entity references.
12///
13/// The `BoxedSlice` data structure uses the dense index space to implement a map with a boxed
14/// slice.
15#[derive(Debug, Clone)]
16pub struct BoxedSlice<K, V>
17where
18    K: EntityRef,
19{
20    elems: Box<[V]>,
21    unused: PhantomData<K>,
22}
23
24impl<K, V> BoxedSlice<K, V>
25where
26    K: EntityRef,
27{
28    /// Create a new slice from a raw pointer. A safer way to create slices is
29    /// to use `PrimaryMap::into_boxed_slice()`.
30    ///
31    /// # Safety
32    ///
33    /// This relies on `raw` pointing to a valid slice of `V`s.
34    pub unsafe fn from_raw(raw: *mut [V]) -> Self {
35        Self {
36            elems: Box::from_raw(raw),
37            unused: PhantomData,
38        }
39    }
40
41    /// Check if `k` is a valid key in the map.
42    pub fn is_valid(&self, k: K) -> bool {
43        k.index() < self.elems.len()
44    }
45
46    /// Get the element at `k` if it exists.
47    pub fn get(&self, k: K) -> Option<&V> {
48        self.elems.get(k.index())
49    }
50
51    /// Get the element at `k` if it exists, mutable version.
52    pub fn get_mut(&mut self, k: K) -> Option<&mut V> {
53        self.elems.get_mut(k.index())
54    }
55
56    /// Is this map completely empty?
57    pub fn is_empty(&self) -> bool {
58        self.elems.is_empty()
59    }
60
61    /// Get the total number of entity references created.
62    pub fn len(&self) -> usize {
63        self.elems.len()
64    }
65
66    /// Iterate over all the keys in this map.
67    pub fn keys(&self) -> Keys<K> {
68        Keys::with_len(self.elems.len())
69    }
70
71    /// Iterate over all the values in this map.
72    pub fn values(&self) -> slice::Iter<V> {
73        self.elems.iter()
74    }
75
76    /// Iterate over all the values in this map, mutable edition.
77    pub fn values_mut(&mut self) -> slice::IterMut<V> {
78        self.elems.iter_mut()
79    }
80
81    /// Iterate over all the keys and values in this map.
82    pub fn iter(&self) -> Iter<K, V> {
83        Iter::new(self.elems.iter())
84    }
85
86    /// Iterate over all the keys and values in this map, mutable edition.
87    pub fn iter_mut(&mut self) -> IterMut<K, V> {
88        IterMut::new(self.elems.iter_mut())
89    }
90
91    /// Returns the last element that was inserted in the map.
92    pub fn last(&self) -> Option<&V> {
93        self.elems.last()
94    }
95}
96
97/// Immutable indexing into a `BoxedSlice`.
98/// The indexed value must be in the map.
99impl<K, V> Index<K> for BoxedSlice<K, V>
100where
101    K: EntityRef,
102{
103    type Output = V;
104
105    fn index(&self, k: K) -> &V {
106        &self.elems[k.index()]
107    }
108}
109
110/// Mutable indexing into a `BoxedSlice`.
111impl<K, V> IndexMut<K> for BoxedSlice<K, V>
112where
113    K: EntityRef,
114{
115    fn index_mut(&mut self, k: K) -> &mut V {
116        &mut self.elems[k.index()]
117    }
118}
119
120impl<'a, K, V> IntoIterator for &'a BoxedSlice<K, V>
121where
122    K: EntityRef,
123{
124    type Item = (K, &'a V);
125    type IntoIter = Iter<'a, K, V>;
126
127    fn into_iter(self) -> Self::IntoIter {
128        Iter::new(self.elems.iter())
129    }
130}
131
132impl<'a, K, V> IntoIterator for &'a mut BoxedSlice<K, V>
133where
134    K: EntityRef,
135{
136    type Item = (K, &'a mut V);
137    type IntoIter = IterMut<'a, K, V>;
138
139    fn into_iter(self) -> Self::IntoIter {
140        IterMut::new(self.elems.iter_mut())
141    }
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147    use crate::primary::PrimaryMap;
148    use alloc::vec::Vec;
149
150    // `EntityRef` impl for testing.
151    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
152    struct E(u32);
153
154    impl EntityRef for E {
155        fn new(i: usize) -> Self {
156            E(i as u32)
157        }
158        fn index(self) -> usize {
159            self.0 as usize
160        }
161    }
162
163    #[test]
164    fn basic() {
165        let r0 = E(0);
166        let r1 = E(1);
167        let p = PrimaryMap::<E, isize>::new();
168        let m = p.into_boxed_slice();
169
170        let v: Vec<E> = m.keys().collect();
171        assert_eq!(v, []);
172
173        assert!(!m.is_valid(r0));
174        assert!(!m.is_valid(r1));
175    }
176
177    #[test]
178    fn iter() {
179        let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
180        p.push(12);
181        p.push(33);
182        let mut m = p.into_boxed_slice();
183
184        let mut i = 0;
185        for (key, value) in &m {
186            assert_eq!(key.index(), i);
187            match i {
188                0 => assert_eq!(*value, 12),
189                1 => assert_eq!(*value, 33),
190                _ => panic!(),
191            }
192            i += 1;
193        }
194        i = 0;
195        for (key_mut, value_mut) in m.iter_mut() {
196            assert_eq!(key_mut.index(), i);
197            match i {
198                0 => assert_eq!(*value_mut, 12),
199                1 => assert_eq!(*value_mut, 33),
200                _ => panic!(),
201            }
202            i += 1;
203        }
204    }
205
206    #[test]
207    fn iter_rev() {
208        let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
209        p.push(12);
210        p.push(33);
211        let mut m = p.into_boxed_slice();
212
213        let mut i = 2;
214        for (key, value) in m.iter().rev() {
215            i -= 1;
216            assert_eq!(key.index(), i);
217            match i {
218                0 => assert_eq!(*value, 12),
219                1 => assert_eq!(*value, 33),
220                _ => panic!(),
221            }
222        }
223
224        i = 2;
225        for (key, value) in m.iter_mut().rev() {
226            i -= 1;
227            assert_eq!(key.index(), i);
228            match i {
229                0 => assert_eq!(*value, 12),
230                1 => assert_eq!(*value, 33),
231                _ => panic!(),
232            }
233        }
234    }
235    #[test]
236    fn keys() {
237        let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
238        p.push(12);
239        p.push(33);
240        let m = p.into_boxed_slice();
241
242        let mut i = 0;
243        for key in m.keys() {
244            assert_eq!(key.index(), i);
245            i += 1;
246        }
247    }
248
249    #[test]
250    fn keys_rev() {
251        let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
252        p.push(12);
253        p.push(33);
254        let m = p.into_boxed_slice();
255
256        let mut i = 2;
257        for key in m.keys().rev() {
258            i -= 1;
259            assert_eq!(key.index(), i);
260        }
261    }
262
263    #[test]
264    fn values() {
265        let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
266        p.push(12);
267        p.push(33);
268        let mut m = p.into_boxed_slice();
269
270        let mut i = 0;
271        for value in m.values() {
272            match i {
273                0 => assert_eq!(*value, 12),
274                1 => assert_eq!(*value, 33),
275                _ => panic!(),
276            }
277            i += 1;
278        }
279        i = 0;
280        for value_mut in m.values_mut() {
281            match i {
282                0 => assert_eq!(*value_mut, 12),
283                1 => assert_eq!(*value_mut, 33),
284                _ => panic!(),
285            }
286            i += 1;
287        }
288    }
289
290    #[test]
291    fn values_rev() {
292        let mut p: PrimaryMap<E, usize> = PrimaryMap::new();
293        p.push(12);
294        p.push(33);
295        let mut m = p.into_boxed_slice();
296
297        let mut i = 2;
298        for value in m.values().rev() {
299            i -= 1;
300            match i {
301                0 => assert_eq!(*value, 12),
302                1 => assert_eq!(*value, 33),
303                _ => panic!(),
304            }
305        }
306        i = 2;
307        for value_mut in m.values_mut().rev() {
308            i -= 1;
309            match i {
310                0 => assert_eq!(*value_mut, 12),
311                1 => assert_eq!(*value_mut, 33),
312                _ => panic!(),
313            }
314        }
315    }
316}
cranelift_entity/boxed_slice.rs

cranelift_entity/
boxed_slice.rs
