standard_lib/collections/contiguous/array/
iter.rs

1use std::alloc;
2use std::iter::{FusedIterator, TrustedLen};
3use std::marker::PhantomData;
4use std::mem;
5use std::ptr::{self, NonNull};
6
7use super::Array;
8#[allow(unused)]
9use crate::collections::contiguous::Vector;
10
11impl<T> IntoIterator for Array<T> {
12    type Item = T;
13
14    type IntoIter = IntoIter<T>;
15
16    fn into_iter(self) -> Self::IntoIter {
17        let head = self.ptr.as_ptr().cast_const();
18        let result = IntoIter {
19            ptr: self.ptr,
20            size: self.size,
21            head,
22            // Don't subtract 1 for the tail.
23            // SAFETY: Offset of one won't overflow isize::MAX. The memory range between head and
24            // tail will be the same as that of the Array, where the initial value of tail is never
25            // read.
26            tail: unsafe { head.add(self.size) },
27            _phantom: PhantomData,
28        };
29        mem::forget(self);
30        result
31    }
32}
33
34/// A type for owned iteration over an [`Array`] or [`Vector`]. Produces values of type `T`.
35///
36/// See [`Array::into_iter`] and [`Vector::into_iter`].
37pub struct IntoIter<T> {
38    pub(crate) ptr: NonNull<T>,
39    pub(crate) size: usize,
40    pub(crate) head: *const T, // Head points to the first element.
41    pub(crate) tail: *const T, // Tail points one after the last element.
42    pub(crate) _phantom: PhantomData<T>,
43}
44
45impl<T> Drop for IntoIter<T> {
46    fn drop(&mut self) {
47        while self.head < self.tail {
48            // SAFETY: The pointer is nonnull, properly aligned and valid for both reads and writes.
49            // This method takes a mutable reference to self, so the underlying data can't be
50            // mutated while it executes.
51            unsafe { ptr::drop_in_place(self.head.cast_mut()) }
52            // SAFETY: Offset of one won't overflow isize::MAX. If the resulting pointer meets
53            // tail it won't ever be read, preventing reads out of bounds of the original Array.
54            self.head = unsafe { self.head.add(1) };
55        }
56
57        let layout = Array::<T>::make_layout(self.size);
58
59        if layout.size() != 0 {
60            // SAFETY: ptr is ensured to be valid by the Array used to create this Iterator.
61            // Zero-sized layouts aren't allocated and are guarded against deallocation.
62            unsafe {
63                alloc::dealloc(self.ptr.as_ptr().cast(), layout)
64            }
65        }
66    }
67}
68
69impl<T> Iterator for IntoIter<T> {
70    type Item = T;
71
72    fn next(&mut self) -> Option<Self::Item> {
73        if self.head < self.tail {
74            // SAFETY: The pointer is always valid for reads. We will increment the pointer next so
75            // that the value is effectively moved off of the heap.
76            let value = unsafe { self.head.read() };
77            // SAFETY: Offset of one won't overflow isize::MAX. If the resulting pointer meets
78            // tail it won't ever be read, preventing reads out of bounds of the original Array.
79            self.head = unsafe { self.head.add(1) };
80            Some(value)
81        } else {
82            None
83        }
84    }
85
86    fn size_hint(&self) -> (usize, Option<usize>) {
87        let len = self.len();
88        (len, Some(len))
89    }
90}
91
92impl<T> DoubleEndedIterator for IntoIter<T> {
93    fn next_back(&mut self) -> Option<Self::Item> {
94        if self.head < self.tail {
95            // Tail sits one after the end, so we subtract first then read. Results in the same
96            // number of operations and an accurate length calculation with subtraction.
97            // SAFETY: Offset of one won't overflow isize::MAX. If the resulting pointer meets
98            // head it won't ever be read, preventing reads out of bounds of the original Array.
99            self.tail = unsafe { self.tail.sub(1) };
100            // SAFETY: The pointer is always valid for reads and we've just decremented it so that
101            // the previous value is never read and effectively moved off of the heap.
102            Some(unsafe { self.tail.read() })
103        } else {
104            None
105        }
106    }
107}
108
109impl<T> FusedIterator for IntoIter<T> {}
110
111impl<T> ExactSizeIterator for IntoIter<T> {
112    fn len(&self) -> usize {
113        // SAFETY: Both pointers are derived from the original allocation and aligned to multiple of
114        // size_of::<T>(). The memory range between them is contained within the initial allocation.
115        // tail is at worst equal to head, it can't be less than.
116        unsafe { self.tail.offset_from_unsigned(self.head) }
117    }
118}
119
120// SAFETY: IntoIter::size_hint returns the exact length of the iterator.
121unsafe impl<T> TrustedLen for IntoIter<T> {}
122
123// Just use the iter and iter_mut definitions provided by Deref<Target=[T]>.
standard_lib/collections/contiguous/array/iter.rs

standard_lib/collections/contiguous/array/
iter.rs
