eastl_rs/deque/
iter.rs

1use crate::allocator::Allocator;
2use crate::deque::Deque;
3use crate::queue::Queue;
4use std::marker::PhantomData;
5
6/// A compatibility array mimicking the C++ one.
7/// Most of deque is actually implemented using this
8/// iterator anyways, so there's no getting around it
9#[repr(C)]
10pub struct CompatIter<'a, T: 'a> {
11    pub(crate) current: *const T,
12    pub(crate) begin: *const T,
13    pub(crate) end: *const T,
14    pub(crate) current_array: *const *const T,
15    _marker: PhantomData<&'a T>,
16}
17
18impl<'a, T: 'a> From<CompatIterMut<'a, T>> for CompatIter<'a, T> {
19    fn from(iter_mut: CompatIterMut<'a, T>) -> Self {
20        Self {
21            current: iter_mut.current,
22            begin: iter_mut.begin,
23            end: iter_mut.end,
24            current_array: iter_mut.current_array as *const *const T,
25            _marker: Default::default(),
26        }
27    }
28}
29
30impl<'a, T: 'a> From<&CompatIterMut<'a, T>> for CompatIter<'a, T> {
31    fn from(iter_mut: &CompatIterMut<'a, T>) -> Self {
32        Self {
33            current: iter_mut.current,
34            begin: iter_mut.begin,
35            end: iter_mut.end,
36            current_array: iter_mut.current_array as *const *const T,
37            _marker: Default::default(),
38        }
39    }
40}
41
42/// A compatibility array mimicking the C++ one.
43/// Most of deque is actually implemented using this
44/// iterator anyways, so there's no getting around it
45#[repr(C)]
46pub struct CompatIterMut<'a, T: 'a> {
47    pub(crate) current: *mut T,
48    pub(crate) begin: *mut T,
49    pub(crate) end: *mut T,
50    pub(crate) current_array: *mut *mut T,
51    _marker: PhantomData<&'a T>,
52}
53
54impl<'a, T: 'a> CompatIterMut<'a, T> {
55    /// Clones a mutable iterator
56    ///
57    /// # Safety
58    ///
59    /// This must not create 2 public mutable iterators
60    pub(crate) unsafe fn clone(&self) -> Self {
61        Self {
62            current: self.current,
63            begin: self.begin,
64            end: self.end,
65            current_array: self.current_array,
66            _marker: Default::default(),
67        }
68    }
69
70    /// Sets the subarray for an iterator
71    ///
72    /// # Arguments
73    ///
74    /// `subarray`: The subarray
75    ///
76    /// `subarray_size`: The size of the subarray
77    ///
78    /// # Safety
79    ///
80    /// `subarray` must point to a valid subarray
81    pub(crate) unsafe fn set_subarray(&mut self, subarray: *mut *mut T, subarray_size: usize) {
82        self.current_array = subarray;
83        self.begin = *subarray;
84        self.end = self.begin.add(subarray_size);
85    }
86}
87
88impl<'a, T: 'a> Default for CompatIterMut<'a, T> {
89    fn default() -> Self {
90        Self {
91            current: std::ptr::null_mut(),
92            begin: std::ptr::null_mut(),
93            end: std::ptr::null_mut(),
94            current_array: std::ptr::null_mut(),
95            _marker: PhantomData,
96        }
97    }
98}
99
100/// An iterator of a deque
101pub struct RawIter<'a, T: 'a> {
102    current: *mut T,
103    current_arr: *mut *mut T,
104    last: *mut T,
105    last_arr: *mut *mut T,
106    subarray_size: usize,
107    _marker: PhantomData<&'a T>,
108}
109
110impl<'a, T: 'a> Iterator for RawIter<'a, T> {
111    type Item = &'a mut T;
112
113    fn next(&mut self) -> Option<Self::Item> {
114        if self.current == self.last {
115            None
116        } else {
117            let elem = unsafe { self.current.as_mut() };
118            if self.current == unsafe { (*self.current_arr).add(self.subarray_size - 1) } {
119                // we reached the end of the current subarray. advance 1
120                self.current_arr = unsafe { self.current_arr.add(1) };
121                self.current = unsafe { *self.current_arr };
122            } else {
123                self.current = unsafe { self.current.add(1) }
124            }
125            elem
126        }
127    }
128}
129
130impl<'a, T: 'a> DoubleEndedIterator for RawIter<'a, T> {
131    fn next_back(&mut self) -> Option<Self::Item> {
132        if self.last == self.current {
133            None
134        } else {
135            // first, we need to go back a subarray
136            if self.last == unsafe { *self.last_arr } {
137                // we reached the beginning of the current subarray. go back 1
138                self.last_arr = unsafe { self.last_arr.sub(1) };
139                self.last = unsafe { (*self.last_arr).add(self.subarray_size - 1) };
140            } else {
141                self.last = unsafe { self.last.sub(1) };
142            }
143            unsafe { self.last.as_mut() }
144        }
145    }
146}
147
148impl<'a, T: 'a> RawIter<'a, T> {
149    /// Transforms a raw iterator into the compatible component parts
150    fn into_compat(self) -> (CompatIter<'a, T>, CompatIter<'a, T>) {
151        (
152            CompatIter {
153                current: self.current,
154                begin: unsafe { *self.current_arr },
155                end: unsafe { (*self.current_arr).add(self.subarray_size) },
156                current_array: self.current_arr as *const *const T,
157                _marker: Default::default(),
158            },
159            CompatIter {
160                current: self.last,
161                begin: unsafe { *self.last_arr },
162                end: unsafe { (*self.last_arr).add(self.subarray_size) },
163                current_array: self.last_arr as *const *const T,
164                _marker: Default::default(),
165            },
166        )
167    }
168
169    /// Transforms a raw iterator into the compatible component parts
170    ///
171    /// # Safety
172    ///
173    /// Mutable-ness must be preserved
174    unsafe fn into_compat_mut(self) -> (CompatIterMut<'a, T>, CompatIterMut<'a, T>) {
175        (
176            CompatIterMut {
177                current: self.current,
178                begin: unsafe { *self.current_arr },
179                end: unsafe { (*self.current_arr).add(self.subarray_size) },
180                current_array: self.current_arr,
181                _marker: Default::default(),
182            },
183            CompatIterMut {
184                current: self.last,
185                begin: unsafe { *self.last_arr },
186                end: unsafe { (*self.last_arr).add(self.subarray_size) },
187                current_array: self.last_arr,
188                _marker: Default::default(),
189            },
190        )
191    }
192
193    /// Constructs a raw iterator from a pair of mutable compatibility iterators
194    ///
195    /// # Arguments
196    ///
197    /// `begin`: The begin iterator
198    ///
199    /// `end`: The end iterator
200    ///
201    /// # Safety
202    ///
203    /// Mutability must be preserved.
204    ///
205    /// `begin` and `end` must point to valid portions of the deque, and end must be after begin
206    unsafe fn from_compat(begin: CompatIter<'a, T>, end: CompatIter<'a, T>) -> Self {
207        Self {
208            current: begin.current as *mut T,
209            current_arr: begin.current_array as *mut *mut T,
210            last: end.current as *mut T,
211            last_arr: end.current_array as *mut *mut T,
212            subarray_size: unsafe { begin.end.offset_from(begin.begin) } as usize,
213            _marker: PhantomData,
214        }
215    }
216
217    /// Constructs a raw iterator from a pair of mutable compatibility iterators
218    ///
219    /// # Arguments
220    ///
221    /// `begin`: The begin iterator
222    ///
223    /// `end`: The end iterator
224    ///
225    /// # Safety
226    ///
227    /// `begin` and `end` must point to valid portions of the deque, and end must be after begin
228    unsafe fn from_compat_mut(begin: CompatIterMut<'a, T>, end: CompatIterMut<'a, T>) -> Self {
229        Self {
230            current: begin.current,
231            current_arr: begin.current_array,
232            last: end.current,
233            last_arr: end.current_array,
234            subarray_size: unsafe { begin.end.offset_from(begin.begin) } as usize,
235            _marker: PhantomData,
236        }
237    }
238}
239
240/// An iterator of a deque
241pub struct Iter<'a, T: 'a> {
242    raw: RawIter<'a, T>,
243}
244
245impl<'a, T: 'a> Iter<'a, T> {
246    /// Constructs a Rust iterator from a pair of compatibility iterators
247    ///
248    /// # Arguments
249    ///
250    /// `begin`: The begin iterator
251    ///
252    /// `end`: The end iterator
253    ///
254    /// # Safety
255    ///
256    /// `begin` and `end` must point to valid portions of the deque, and end must be after begin
257    pub unsafe fn from_compat(begin: CompatIter<'a, T>, end: CompatIter<'a, T>) -> Self {
258        Self {
259            raw: RawIter::from_compat(begin, end),
260        }
261    }
262
263    /// Converts the Rust iterator into a set of C++ compatibility iterators
264    pub fn into_compat(self) -> (CompatIter<'a, T>, CompatIter<'a, T>) {
265        self.raw.into_compat()
266    }
267}
268
269impl<'a, T: 'a> Iterator for Iter<'a, T> {
270    type Item = &'a T;
271
272    fn next(&mut self) -> Option<Self::Item> {
273        self.raw.next().map(|r| &*r)
274    }
275}
276
277impl<'a, T: 'a> DoubleEndedIterator for Iter<'a, T> {
278    fn next_back(&mut self) -> Option<Self::Item> {
279        self.raw.next_back().map(|r| &*r)
280    }
281}
282
283/// An iterator of a deque
284pub struct IterMut<'a, T: 'a> {
285    raw: RawIter<'a, T>,
286}
287
288impl<'a, T: 'a> IterMut<'a, T> {
289    /// Constructs a Rust iterator from a pair of mutable compatibility iterators
290    ///
291    /// # Arguments
292    ///
293    /// `begin`: The begin iterator
294    ///
295    /// `end`: The end iterator
296    ///
297    /// # Safety
298    ///
299    /// `begin` and `end` must point to valid portions of the deque, and end must be after begin
300    pub unsafe fn from_compat(begin: CompatIterMut<'a, T>, end: CompatIterMut<'a, T>) -> Self {
301        Self {
302            raw: RawIter::from_compat_mut(begin, end),
303        }
304    }
305
306    /// Converts the Rust iterator into a set of C++ compatibility iterators
307    pub fn into_compat(self) -> (CompatIter<'a, T>, CompatIter<'a, T>) {
308        self.raw.into_compat()
309    }
310
311    /// Converts the Rust iterator into a set of C++ compatibility iterators
312    pub fn into_compat_mut(self) -> (CompatIterMut<'a, T>, CompatIterMut<'a, T>) {
313        unsafe { self.raw.into_compat_mut() }
314    }
315}
316
317impl<'a, T: 'a> Iterator for IterMut<'a, T> {
318    type Item = &'a mut T;
319
320    fn next(&mut self) -> Option<Self::Item> {
321        self.raw.next()
322    }
323}
324
325impl<'a, T: 'a> DoubleEndedIterator for IterMut<'a, T> {
326    fn next_back(&mut self) -> Option<Self::Item> {
327        self.raw.next_back()
328    }
329}
330
331/// A consuming iterator
332pub struct IntoIter<'a, T: 'a, A: Allocator> {
333    deque: Deque<'a, T, A>,
334}
335
336impl<'a, T: 'a, A: Allocator> Iterator for IntoIter<'a, T, A> {
337    type Item = T;
338
339    fn next(&mut self) -> Option<Self::Item> {
340        self.deque.pop_front()
341    }
342}
343
344impl<'a, T: 'a, A: Allocator> DoubleEndedIterator for IntoIter<'a, T, A> {
345    fn next_back(&mut self) -> Option<Self::Item> {
346        self.deque.pop_back()
347    }
348}
349
350impl<'a, T: 'a, A: Allocator> IntoIterator for Deque<'a, T, A> {
351    type Item = T;
352    type IntoIter = IntoIter<'a, T, A>;
353
354    fn into_iter(self) -> Self::IntoIter {
355        Self::IntoIter { deque: self }
356    }
357}
358
359impl<'a, T: 'a, A: Allocator> IntoIterator for Queue<'a, T, A> {
360    type Item = T;
361    type IntoIter = IntoIter<'a, T, A>;
362
363    fn into_iter(self) -> Self::IntoIter {
364        Self::IntoIter {
365            deque: self.into_inner(),
366        }
367    }
368}
369
370#[cfg(test)]
371mod test {
372
373    use crate::deque::iter::CompatIterMut;
374    use crate::deque::DefaultDeque;
375    use memoffset::offset_of;
376
377    #[test]
378    fn layout() {
379        assert_eq!(offset_of!(CompatIterMut<u32>, current), 0);
380        assert_eq!(
381            offset_of!(CompatIterMut<u32>, begin),
382            std::mem::size_of::<usize>()
383        );
384        assert_eq!(
385            offset_of!(CompatIterMut<u32>, end),
386            std::mem::size_of::<usize>() * 2
387        );
388        assert_eq!(
389            offset_of!(CompatIterMut<u32>, current_array),
390            std::mem::size_of::<usize>() * 3
391        );
392        assert_eq!(
393            std::mem::size_of::<CompatIterMut<u32>>(),
394            std::mem::size_of::<usize>() * 4
395        );
396    }
397
398    #[test]
399    fn empty_iter() {
400        let d = DefaultDeque::<u32>::new();
401        let mut i = d.iter();
402
403        assert_eq!(i.next(), None);
404        assert_eq!(i.next_back(), None);
405    }
406
407    #[test]
408    fn iter() {
409        let d: DefaultDeque<u32> = (0..10).collect();
410        let mut i = d.iter();
411
412        for elem in 0..5 {
413            assert_eq!(i.next(), Some(&elem));
414        }
415        for elem in (5..10).rev() {
416            assert_eq!(i.next_back(), Some(&elem));
417        }
418
419        assert_eq!(i.next(), None);
420        assert_eq!(i.next_back(), None);
421    }
422
423    #[test]
424    fn iter_across_borders() {
425        let mut d = DefaultDeque::new();
426
427        // make sure front and back have values so we go over boundaries
428        for i in 0..70 {
429            d.push_front(i);
430            d.push_back(i);
431        }
432
433        let mut i = d.iter();
434
435        for elem in (0..70).rev() {
436            assert_eq!(i.next(), Some(&elem));
437        }
438        for elem in (0..70).rev() {
439            assert_eq!(i.next_back(), Some(&elem));
440        }
441
442        assert_eq!(i.next(), None);
443        assert_eq!(i.next_back(), None);
444    }
445}
eastl_rs/deque/iter.rs

eastl_rs/deque/
iter.rs
