stable_vec/
iter.rs

1//! Contains all iterator types and implementations.
2//!
3//! This is in its own module to not pollute the top-level namespace.
4
5use std::{
6    iter::FusedIterator,
7    ops::Range,
8};
9
10use crate::{
11    StableVecFacade,
12    core::{Core, OwningCore},
13};
14
15
16/// Iterator over immutable references to a stable vec's elements and their
17/// indices.
18///
19/// Use the method [`StableVecFacade::iter`] or the `IntoIterator` impl of
20/// `&StableVecFacade` to obtain an iterator of this kind.
21#[derive(Clone, Debug)]
22pub struct Iter<'a, T, C: Core<T>>(Indices<'a, T, C>);
23
24impl<'a, T, C: Core<T>> Iter<'a, T, C> {
25    pub(crate) fn new(sv: &'a StableVecFacade<T, C>) -> Self {
26        Self(Indices::new(sv))
27    }
28}
29
30impl<'a, T, C: Core<T>> Iterator for Iter<'a, T, C> {
31    type Item = (usize, &'a T);
32    fn next(&mut self) -> Option<Self::Item> {
33        self.0.next().map(|idx| (idx, unsafe { self.0.core.get_unchecked(idx) }))
34    }
35
36    fn size_hint(&self) -> (usize, Option<usize>) {
37        self.0.size_hint()
38    }
39
40    fn count(self) -> usize {
41        self.0.count()
42    }
43
44    fn last(mut self) -> Option<Self::Item> {
45        self.next_back()
46    }
47}
48
49impl<T, C: Core<T>> DoubleEndedIterator for Iter<'_, T, C> {
50    fn next_back(&mut self) -> Option<Self::Item> {
51        self.0.next_back().map(|idx| (idx, unsafe { self.0.core.get_unchecked(idx) }))
52    }
53}
54
55impl<T, C: Core<T>> ExactSizeIterator for Iter<'_, T, C> {
56    fn len(&self) -> usize {
57        self.0.len()
58    }
59}
60
61impl<T, C: Core<T>> FusedIterator for Iter<'_, T, C> {}
62
63
64/// Iterator over mutable references to a stable vec's elements and their
65/// indices.
66///
67/// Use the method [`StableVecFacade::iter_mut`] or the `IntoIterator` impl of
68/// `&mut StableVecFacade` to obtain an iterator of this kind.
69#[derive(Debug)]
70pub struct IterMut<'a, T, C: Core<T>> {
71    pub(crate) core: &'a mut OwningCore<T, C>,
72    pub(crate) remaining: Range<usize>,
73    pub(crate) count: usize,
74}
75
76impl<'a, T, C: Core<T>> IterMut<'a, T, C> {
77    pub(crate) fn new(sv: &'a mut StableVecFacade<T, C>) -> Self {
78        Self {
79            remaining: 0..sv.core.len(),
80            core: &mut sv.core,
81            count: sv.num_elements,
82        }
83    }
84}
85
86impl<'a, T, C: Core<T>> Iterator for IterMut<'a, T, C> {
87    type Item = (usize, &'a mut T);
88    fn next(&mut self) -> Option<Self::Item> {
89        next(&mut self.count, &mut self.remaining, &**self.core).map(|idx| {
90            // This is... scary. We are extending the lifetime of the reference
91            // returned by `get_unchecked_mut`. We can do that because we know
92            // that we will never return the same reference twice. So the user
93            // can't have mutable aliases. Furthermore, all access to the
94            // original stable vector is blocked because we (`ValuesMut`) have
95            // a mutable reference to it. So it is fine to extend the lifetime
96            // to `'a`.
97            let r = unsafe { &mut *(self.core.get_unchecked_mut(idx) as *mut T) };
98            (idx, r)
99        })
100    }
101
102    fn size_hint(&self) -> (usize, Option<usize>) {
103        (self.count, Some(self.count))
104    }
105
106    fn count(self) -> usize {
107        self.len()
108    }
109
110    fn last(mut self) -> Option<Self::Item> {
111        self.next_back()
112    }
113}
114
115impl<T, C: Core<T>> DoubleEndedIterator for IterMut<'_, T, C> {
116    fn next_back(&mut self) -> Option<Self::Item> {
117        next_back(&mut self.count, &mut self.remaining, &**self.core).map(|idx| {
118            // See `Self::next()` for more information on this.
119            let r = unsafe { &mut *(self.core.get_unchecked_mut(idx) as *mut T) };
120            (idx, r)
121        })
122    }
123}
124
125impl<T, C: Core<T>> ExactSizeIterator for IterMut<'_, T, C> {
126    fn len(&self) -> usize {
127        self.count
128    }
129}
130
131impl<T, C: Core<T>> FusedIterator for IterMut<'_, T, C> {}
132
133
134/// Iterator over immutable references to the elements of a `StableVecFacade`.
135///
136/// Use the method [`StableVecFacade::values`] to obtain an iterator of this
137/// kind.
138#[derive(Clone, Debug)]
139pub struct Values<'a, T, C: Core<T>>(Indices<'a, T, C>);
140
141impl<'a, T, C: Core<T>> Values<'a, T, C> {
142    pub(crate) fn new(sv: &'a StableVecFacade<T, C>) -> Self {
143        Self(Indices::new(sv))
144    }
145}
146
147impl<'a, T, C: Core<T>> Iterator for Values<'a, T, C> {
148    type Item = &'a T;
149    fn next(&mut self) -> Option<Self::Item> {
150        self.0.next().map(|idx| unsafe { self.0.core.get_unchecked(idx) })
151    }
152
153    fn size_hint(&self) -> (usize, Option<usize>) {
154        self.0.size_hint()
155    }
156
157    fn count(self) -> usize {
158        self.0.count()
159    }
160
161    fn last(mut self) -> Option<Self::Item> {
162        self.next_back()
163    }
164}
165
166impl<T, C: Core<T>> DoubleEndedIterator for Values<'_, T, C> {
167    fn next_back(&mut self) -> Option<Self::Item> {
168        self.0.next_back().map(|idx| unsafe { self.0.core.get_unchecked(idx) })
169    }
170}
171
172impl<T, C: Core<T>> ExactSizeIterator for Values<'_, T, C> {
173    fn len(&self) -> usize {
174        self.0.len()
175    }
176}
177
178impl<T, C: Core<T>> FusedIterator for Values<'_, T, C> {}
179
180
181/// Iterator over mutable references to the elements of a `StableVecFacade`.
182///
183/// Use the method [`StableVecFacade::values_mut`] to obtain an iterator of
184/// this kind.
185#[derive(Debug)]
186pub struct ValuesMut<'a, T, C: Core<T>>(IterMut<'a, T, C>);
187
188impl<'a, T, C: Core<T>> ValuesMut<'a, T, C> {
189    pub(crate) fn new(sv: &'a mut StableVecFacade<T, C>) -> Self {
190        Self(IterMut::new(sv))
191    }
192}
193
194impl<'a, T, C: Core<T>> Iterator for ValuesMut<'a, T, C> {
195    type Item = &'a mut T;
196    fn next(&mut self) -> Option<Self::Item> {
197        self.0.next().map(|(_, r)| r)
198    }
199
200    fn size_hint(&self) -> (usize, Option<usize>) {
201        self.0.size_hint()
202    }
203
204    fn count(self) -> usize {
205        self.0.count()
206    }
207
208    fn last(mut self) -> Option<Self::Item> {
209        self.next_back()
210    }
211}
212
213impl<T, C: Core<T>> DoubleEndedIterator for ValuesMut<'_, T, C> {
214    fn next_back(&mut self) -> Option<Self::Item> {
215        self.0.next_back().map(|(_, r)| r)
216    }
217}
218
219impl<T, C: Core<T>> ExactSizeIterator for ValuesMut<'_, T, C> {
220    fn len(&self) -> usize {
221        self.0.len()
222    }
223}
224
225impl<T, C: Core<T>> FusedIterator for ValuesMut<'_, T, C> {}
226
227
228/// Iterator over owned elements of a `StableVecFacade`.
229///
230/// Use the method `StableVecFacade::into_iter` to obtain an iterator of this
231/// kind.
232#[derive(Clone, Debug)]
233pub struct IntoIter<T, C: Core<T>> {
234    pub(crate) sv: StableVecFacade<T, C>,
235    pub(crate) remaining: Range<usize>,
236}
237
238impl<T, C: Core<T>> IntoIter<T, C> {
239    pub(crate) fn new(sv: StableVecFacade<T, C>) -> Self {
240        Self {
241            remaining: 0..sv.core.len(),
242            sv,
243        }
244    }
245}
246
247impl<T, C: Core<T>> Iterator for IntoIter<T, C> {
248    type Item = (usize, T);
249
250    fn next(&mut self) -> Option<Self::Item> {
251        next(&mut self.sv.num_elements, &mut self.remaining, &*self.sv.core).map(|idx| {
252            let elem = unsafe { self.sv.core.remove_at(idx) };
253            (idx, elem)
254        })
255    }
256
257    fn size_hint(&self) -> (usize, Option<usize>) {
258        (self.sv.num_elements, Some(self.sv.num_elements))
259    }
260
261    fn count(self) -> usize {
262        self.len()
263    }
264
265    fn last(mut self) -> Option<Self::Item> {
266        self.next_back()
267    }
268}
269
270impl<T, C: Core<T>> DoubleEndedIterator for IntoIter<T, C> {
271    fn next_back(&mut self) -> Option<Self::Item> {
272        next_back(&mut self.sv.num_elements, &mut self.remaining, &*self.sv.core).map(|idx| {
273            let elem = unsafe { self.sv.core.remove_at(idx) };
274            (idx, elem)
275        })
276    }
277}
278
279impl<T, C: Core<T>> ExactSizeIterator for IntoIter<T, C> {
280    fn len(&self) -> usize {
281        self.sv.num_elements
282    }
283}
284
285impl<T, C: Core<T>> FusedIterator for IntoIter<T, C> {}
286
287
288/// Iterator over all indices of filled slots of a `StableVecFacade`.
289///
290/// Use the method [`StableVecFacade::indices`] to obtain an iterator of this
291/// kind.
292#[derive(Clone, Debug)]
293pub struct Indices<'a, T, C: Core<T>> {
294    core: &'a OwningCore<T, C>,
295    remaining: Range<usize>,
296    count: usize,
297}
298
299impl<'a, T, C: Core<T>> Indices<'a, T, C> {
300    pub(crate) fn new(sv: &'a StableVecFacade<T, C>) -> Self {
301        Self {
302            core: &sv.core,
303            remaining: 0..sv.core.len(),
304            count: sv.num_elements,
305        }
306    }
307}
308
309impl<T, C: Core<T>> Iterator for Indices<'_, T, C> {
310    type Item = usize;
311    fn next(&mut self) -> Option<Self::Item> {
312        next(&mut self.count, &mut self.remaining, &**self.core)
313    }
314
315    fn size_hint(&self) -> (usize, Option<usize>) {
316        (self.count, Some(self.count))
317    }
318
319    fn count(self) -> usize {
320        self.len()
321    }
322
323    fn last(mut self) -> Option<Self::Item> {
324        self.next_back()
325    }
326}
327
328impl<T, C: Core<T>> DoubleEndedIterator for Indices<'_, T, C> {
329    fn next_back(&mut self) -> Option<Self::Item> {
330        next_back(&mut self.count, &mut self.remaining, &**self.core)
331    }
332}
333
334impl<T, C: Core<T>> ExactSizeIterator for Indices<'_, T, C> {
335    fn len(&self) -> usize {
336        self.count
337    }
338}
339
340impl<T, C: Core<T>> FusedIterator for Indices<'_, T, C> {}
341
342
343/// The actual logic for all `next()` iterator methods.
344fn next<T, C: Core<T>>(
345    count: &mut usize,
346    remaining: &mut Range<usize>,
347    core: &C,
348) -> Option<usize> {
349    if *count == 0 {
350        return None;
351    }
352
353    let idx = unsafe { core.first_filled_slot_from(remaining.start) }
354        .expect("bug in StableVec iterator: no next filled slot");
355
356    remaining.start = idx + 1;
357    *count -= 1;
358
359    Some(idx)
360}
361
362/// The actual logic for all `next_back()` iterator methods.
363fn next_back<T, C: Core<T>>(
364    count: &mut usize,
365    remaining: &mut Range<usize>,
366    core: &C,
367) -> Option<usize> {
368    if *count == 0 {
369        return None;
370    }
371
372    let idx = unsafe { core.first_filled_slot_below(remaining.end) }
373        .expect("bug in StableVec iterator: no next filled slot");
374
375    remaining.end = idx;
376    *count -= 1;
377
378    Some(idx)
379}
stable_vec/iter.rs

stable_vec/
iter.rs
