| blob | ae9d072741cedbb34bed0be0c20cc75472aa53be |
1 // SPDX-License-Identifier: GPL-2.0
3 //! Implementation of [`Vec`].
5 use super::{
6 allocator::{KVmalloc, Kmalloc, Vmalloc},
7 layout::ArrayLayout,
8 AllocError, Allocator, Box, Flags,
9 };
10 use core::{
11 fmt,
12 marker::PhantomData,
13 mem::{ManuallyDrop, MaybeUninit},
14 ops::Deref,
15 ops::DerefMut,
16 ops::Index,
17 ops::IndexMut,
18 ptr,
19 ptr::NonNull,
20 slice,
21 slice::SliceIndex,
22 };
24 /// Create a [`KVec`] containing the arguments.
25 ///
26 /// New memory is allocated with `GFP_KERNEL`.
27 ///
28 /// # Examples
29 ///
30 /// ```
31 /// let mut v = kernel::kvec![];
32 /// v.push(1, GFP_KERNEL)?;
33 /// assert_eq!(v, [1]);
34 ///
35 /// let mut v = kernel::kvec![1; 3]?;
36 /// v.push(4, GFP_KERNEL)?;
37 /// assert_eq!(v, [1, 1, 1, 4]);
38 ///
39 /// let mut v = kernel::kvec![1, 2, 3]?;
40 /// v.push(4, GFP_KERNEL)?;
41 /// assert_eq!(v, [1, 2, 3, 4]);
42 ///
43 /// # Ok::<(), Error>(())
44 /// ```
45 #[macro_export]
46 macro_rules! kvec {
47 () => (
48 $crate::alloc::KVec::new()
49 );
50 ($elem:expr; $n:expr) => (
51 $crate::alloc::KVec::from_elem($elem, $n, GFP_KERNEL)
52 );
53 ($($x:expr),+ $(,)?) => (
54 match $crate::alloc::KBox::new_uninit(GFP_KERNEL) {
55 Ok(b) => Ok($crate::alloc::KVec::from($crate::alloc::KBox::write(b, [$($x),+]))),
56 Err(e) => Err(e),
57 }
58 );
59 }
61 /// The kernel's [`Vec`] type.
62 ///
63 /// A contiguous growable array type with contents allocated with the kernel's allocators (e.g.
64 /// [`Kmalloc`], [`Vmalloc`] or [`KVmalloc`]), written `Vec<T, A>`.
65 ///
66 /// For non-zero-sized values, a [`Vec`] will use the given allocator `A` for its allocation. For
67 /// the most common allocators the type aliases [`KVec`], [`VVec`] and [`KVVec`] exist.
68 ///
69 /// For zero-sized types the [`Vec`]'s pointer must be `dangling_mut::<T>`; no memory is allocated.
70 ///
71 /// Generally, [`Vec`] consists of a pointer that represents the vector's backing buffer, the
72 /// capacity of the vector (the number of elements that currently fit into the vector), its length
73 /// (the number of elements that are currently stored in the vector) and the `Allocator` type used
74 /// to allocate (and free) the backing buffer.
75 ///
76 /// A [`Vec`] can be deconstructed into and (re-)constructed from its previously named raw parts
77 /// and manually modified.
78 ///
79 /// [`Vec`]'s backing buffer gets, if required, automatically increased (re-allocated) when elements
80 /// are added to the vector.
81 ///
82 /// # Invariants
83 ///
84 /// - `self.ptr` is always properly aligned and either points to memory allocated with `A` or, for
85 /// zero-sized types, is a dangling, well aligned pointer.
86 ///
87 /// - `self.len` always represents the exact number of elements stored in the vector.
88 ///
89 /// - `self.layout` represents the absolute number of elements that can be stored within the vector
90 /// without re-allocation. For ZSTs `self.layout`'s capacity is zero. However, it is legal for the
91 /// backing buffer to be larger than `layout`.
92 ///
93 /// - The `Allocator` type `A` of the vector is the exact same `Allocator` type the backing buffer
94 /// was allocated with (and must be freed with).
95 pub struct Vec<T, A: Allocator> {
96 ptr: NonNull<T>,
97 /// Represents the actual buffer size as `cap` times `size_of::<T>` bytes.
98 ///
99 /// Note: This isn't quite the same as `Self::capacity`, which in contrast returns the number of
100 /// elements we can still store without reallocating.
101 layout: ArrayLayout<T>,
102 len: usize,
103 _p: PhantomData<A>,
104 }
106 /// Type alias for [`Vec`] with a [`Kmalloc`] allocator.
107 ///
108 /// # Examples
109 ///
110 /// ```
111 /// let mut v = KVec::new();
112 /// v.push(1, GFP_KERNEL)?;
113 /// assert_eq!(&v, &[1]);
114 ///
115 /// # Ok::<(), Error>(())
116 /// ```
117 pub type KVec<T> = Vec<T, Kmalloc>;
119 /// Type alias for [`Vec`] with a [`Vmalloc`] allocator.
120 ///
121 /// # Examples
122 ///
123 /// ```
124 /// let mut v = VVec::new();
125 /// v.push(1, GFP_KERNEL)?;
126 /// assert_eq!(&v, &[1]);
127 ///
128 /// # Ok::<(), Error>(())
129 /// ```
130 pub type VVec<T> = Vec<T, Vmalloc>;
132 /// Type alias for [`Vec`] with a [`KVmalloc`] allocator.
133 ///
134 /// # Examples
135 ///
136 /// ```
137 /// let mut v = KVVec::new();
138 /// v.push(1, GFP_KERNEL)?;
139 /// assert_eq!(&v, &[1]);
140 ///
141 /// # Ok::<(), Error>(())
142 /// ```
143 pub type KVVec<T> = Vec<T, KVmalloc>;
145 // SAFETY: `Vec` is `Send` if `T` is `Send` because `Vec` owns its elements.
146 unsafe impl<T, A> Send for Vec<T, A>
147 where
148 T: Send,
149 A: Allocator,
150 {
151 }
153 // SAFETY: `Vec` is `Sync` if `T` is `Sync` because `Vec` owns its elements.
154 unsafe impl<T, A> Sync for Vec<T, A>
155 where
156 T: Sync,
157 A: Allocator,
158 {
159 }
161 impl<T, A> Vec<T, A>
162 where
163 A: Allocator,
164 {
165 #[inline]
166 const fn is_zst() -> bool {
167 core::mem::size_of::<T>() == 0
168 }
170 /// Returns the number of elements that can be stored within the vector without allocating
171 /// additional memory.
172 pub fn capacity(&self) -> usize {
173 if const { Self::is_zst() } {
174 usize::MAX
175 } else {
176 self.layout.len()
177 }
178 }
180 /// Returns the number of elements stored within the vector.
181 #[inline]
182 pub fn len(&self) -> usize {
183 self.len
184 }
186 /// Forcefully sets `self.len` to `new_len`.
187 ///
188 /// # Safety
189 ///
190 /// - `new_len` must be less than or equal to [`Self::capacity`].
191 /// - If `new_len` is greater than `self.len`, all elements within the interval
192 /// [`self.len`,`new_len`) must be initialized.
193 #[inline]
194 pub unsafe fn set_len(&mut self, new_len: usize) {
195 debug_assert!(new_len <= self.capacity());
196 self.len = new_len;
197 }
199 /// Returns a slice of the entire vector.
200 #[inline]
201 pub fn as_slice(&self) -> &[T] {
202 self
203 }
205 /// Returns a mutable slice of the entire vector.
206 #[inline]
207 pub fn as_mut_slice(&mut self) -> &mut [T] {
208 self
209 }
211 /// Returns a mutable raw pointer to the vector's backing buffer, or, if `T` is a ZST, a
212 /// dangling raw pointer.
213 #[inline]
214 pub fn as_mut_ptr(&mut self) -> *mut T {
215 self.ptr.as_ptr()
216 }
218 /// Returns a raw pointer to the vector's backing buffer, or, if `T` is a ZST, a dangling raw
219 /// pointer.
220 #[inline]
221 pub fn as_ptr(&self) -> *const T {
222 self.ptr.as_ptr()
223 }
225 /// Returns `true` if the vector contains no elements, `false` otherwise.
226 ///
227 /// # Examples
228 ///
229 /// ```
230 /// let mut v = KVec::new();
231 /// assert!(v.is_empty());
232 ///
233 /// v.push(1, GFP_KERNEL);
234 /// assert!(!v.is_empty());
235 /// ```
236 #[inline]
237 pub fn is_empty(&self) -> bool {
238 self.len() == 0
239 }
241 /// Creates a new, empty `Vec<T, A>`.
242 ///
243 /// This method does not allocate by itself.
244 #[inline]
245 pub const fn new() -> Self {
246 // INVARIANT: Since this is a new, empty `Vec` with no backing memory yet,
247 // - `ptr` is a properly aligned dangling pointer for type `T`,
248 // - `layout` is an empty `ArrayLayout` (zero capacity)
249 // - `len` is zero, since no elements can be or have been stored,
250 // - `A` is always valid.
251 Self {
252 ptr: NonNull::dangling(),
253 layout: ArrayLayout::empty(),
254 len: 0,
255 _p: PhantomData::<A>,
256 }
257 }
259 /// Returns a slice of `MaybeUninit<T>` for the remaining spare capacity of the vector.
260 pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
261 // SAFETY:
262 // - `self.len` is smaller than `self.capacity` and hence, the resulting pointer is
263 // guaranteed to be part of the same allocated object.
264 // - `self.len` can not overflow `isize`.
265 let ptr = unsafe { self.as_mut_ptr().add(self.len) } as *mut MaybeUninit<T>;
267 // SAFETY: The memory between `self.len` and `self.capacity` is guaranteed to be allocated
268 // and valid, but uninitialized.
269 unsafe { slice::from_raw_parts_mut(ptr, self.capacity() - self.len) }
270 }
272 /// Appends an element to the back of the [`Vec`] instance.
273 ///
274 /// # Examples
275 ///
276 /// ```
277 /// let mut v = KVec::new();
278 /// v.push(1, GFP_KERNEL)?;
279 /// assert_eq!(&v, &[1]);
280 ///
281 /// v.push(2, GFP_KERNEL)?;
282 /// assert_eq!(&v, &[1, 2]);
283 /// # Ok::<(), Error>(())
284 /// ```
285 pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
286 self.reserve(1, flags)?;
288 // SAFETY:
289 // - `self.len` is smaller than `self.capacity` and hence, the resulting pointer is
290 // guaranteed to be part of the same allocated object.
291 // - `self.len` can not overflow `isize`.
292 let ptr = unsafe { self.as_mut_ptr().add(self.len) };
294 // SAFETY:
295 // - `ptr` is properly aligned and valid for writes.
296 unsafe { core::ptr::write(ptr, v) };
298 // SAFETY: We just initialised the first spare entry, so it is safe to increase the length
299 // by 1. We also know that the new length is <= capacity because of the previous call to
300 // `reserve` above.
301 unsafe { self.set_len(self.len() + 1) };
302 Ok(())
303 }
305 /// Creates a new [`Vec`] instance with at least the given capacity.
306 ///
307 /// # Examples
308 ///
309 /// ```
310 /// let v = KVec::<u32>::with_capacity(20, GFP_KERNEL)?;
311 ///
312 /// assert!(v.capacity() >= 20);
313 /// # Ok::<(), Error>(())
314 /// ```
315 pub fn with_capacity(capacity: usize, flags: Flags) -> Result<Self, AllocError> {
316 let mut v = Vec::new();
318 v.reserve(capacity, flags)?;
320 Ok(v)
321 }
323 /// Creates a `Vec<T, A>` from a pointer, a length and a capacity using the allocator `A`.
324 ///
325 /// # Examples
326 ///
327 /// ```
328 /// let mut v = kernel::kvec![1, 2, 3]?;
329 /// v.reserve(1, GFP_KERNEL)?;
330 ///
331 /// let (mut ptr, mut len, cap) = v.into_raw_parts();
332 ///
333 /// // SAFETY: We've just reserved memory for another element.
334 /// unsafe { ptr.add(len).write(4) };
335 /// len += 1;
336 ///
337 /// // SAFETY: We only wrote an additional element at the end of the `KVec`'s buffer and
338 /// // correspondingly increased the length of the `KVec` by one. Otherwise, we construct it
339 /// // from the exact same raw parts.
340 /// let v = unsafe { KVec::from_raw_parts(ptr, len, cap) };
341 ///
342 /// assert_eq!(v, [1, 2, 3, 4]);
343 ///
344 /// # Ok::<(), Error>(())
345 /// ```
346 ///
347 /// # Safety
348 ///
349 /// If `T` is a ZST:
350 ///
351 /// - `ptr` must be a dangling, well aligned pointer.
352 ///
353 /// Otherwise:
354 ///
355 /// - `ptr` must have been allocated with the allocator `A`.
356 /// - `ptr` must satisfy or exceed the alignment requirements of `T`.
357 /// - `ptr` must point to memory with a size of at least `size_of::<T>() * capacity` bytes.
358 /// - The allocated size in bytes must not be larger than `isize::MAX`.
359 /// - `length` must be less than or equal to `capacity`.
360 /// - The first `length` elements must be initialized values of type `T`.
361 ///
362 /// It is also valid to create an empty `Vec` passing a dangling pointer for `ptr` and zero for
363 /// `cap` and `len`.
364 pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self {
365 let layout = if Self::is_zst() {
366 ArrayLayout::empty()
367 } else {
368 // SAFETY: By the safety requirements of this function, `capacity * size_of::<T>()` is
369 // smaller than `isize::MAX`.
370 unsafe { ArrayLayout::new_unchecked(capacity) }
371 };
373 // INVARIANT: For ZSTs, we store an empty `ArrayLayout`, all other type invariants are
374 // covered by the safety requirements of this function.
375 Self {
376 // SAFETY: By the safety requirements, `ptr` is either dangling or pointing to a valid
377 // memory allocation, allocated with `A`.
378 ptr: unsafe { NonNull::new_unchecked(ptr) },
379 layout,
380 len: length,
381 _p: PhantomData::<A>,
382 }
383 }
385 /// Consumes the `Vec<T, A>` and returns its raw components `pointer`, `length` and `capacity`.
386 ///
387 /// This will not run the destructor of the contained elements and for non-ZSTs the allocation
388 /// will stay alive indefinitely. Use [`Vec::from_raw_parts`] to recover the [`Vec`], drop the
389 /// elements and free the allocation, if any.
390 pub fn into_raw_parts(self) -> (*mut T, usize, usize) {
391 let mut me = ManuallyDrop::new(self);
392 let len = me.len();
393 let capacity = me.capacity();
394 let ptr = me.as_mut_ptr();
395 (ptr, len, capacity)
396 }
398 /// Ensures that the capacity exceeds the length by at least `additional` elements.
399 ///
400 /// # Examples
401 ///
402 /// ```
403 /// let mut v = KVec::new();
404 /// v.push(1, GFP_KERNEL)?;
405 ///
406 /// v.reserve(10, GFP_KERNEL)?;
407 /// let cap = v.capacity();
408 /// assert!(cap >= 10);
409 ///
410 /// v.reserve(10, GFP_KERNEL)?;
411 /// let new_cap = v.capacity();
412 /// assert_eq!(new_cap, cap);
413 ///
414 /// # Ok::<(), Error>(())
415 /// ```
416 pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError> {
417 let len = self.len();
418 let cap = self.capacity();
420 if cap - len >= additional {
421 return Ok(());
422 }
424 if Self::is_zst() {
425 // The capacity is already `usize::MAX` for ZSTs, we can't go higher.
426 return Err(AllocError);
427 }
429 // We know that `cap <= isize::MAX` because of the type invariants of `Self`. So the
430 // multiplication by two won't overflow.
431 let new_cap = core::cmp::max(cap * 2, len.checked_add(additional).ok_or(AllocError)?);
432 let layout = ArrayLayout::new(new_cap).map_err(|_| AllocError)?;
434 // SAFETY:
435 // - `ptr` is valid because it's either `None` or comes from a previous call to
436 // `A::realloc`.
437 // - `self.layout` matches the `ArrayLayout` of the preceding allocation.
438 let ptr = unsafe {
439 A::realloc(
440 Some(self.ptr.cast()),
441 layout.into(),
442 self.layout.into(),
443 flags,
444 )?
445 };
447 // INVARIANT:
448 // - `layout` is some `ArrayLayout::<T>`,
449 // - `ptr` has been created by `A::realloc` from `layout`.
450 self.ptr = ptr.cast();
451 self.layout = layout;
453 Ok(())
454 }
455 }
457 impl<T: Clone, A: Allocator> Vec<T, A> {
458 /// Extend the vector by `n` clones of `value`.
459 pub fn extend_with(&mut self, n: usize, value: T, flags: Flags) -> Result<(), AllocError> {
460 if n == 0 {
461 return Ok(());
462 }
464 self.reserve(n, flags)?;
466 let spare = self.spare_capacity_mut();
468 for item in spare.iter_mut().take(n - 1) {
469 item.write(value.clone());
470 }
472 // We can write the last element directly without cloning needlessly.
473 spare[n - 1].write(value);
475 // SAFETY:
476 // - `self.len() + n < self.capacity()` due to the call to reserve above,
477 // - the loop and the line above initialized the next `n` elements.
478 unsafe { self.set_len(self.len() + n) };
480 Ok(())
481 }
483 /// Pushes clones of the elements of slice into the [`Vec`] instance.
484 ///
485 /// # Examples
486 ///
487 /// ```
488 /// let mut v = KVec::new();
489 /// v.push(1, GFP_KERNEL)?;
490 ///
491 /// v.extend_from_slice(&[20, 30, 40], GFP_KERNEL)?;
492 /// assert_eq!(&v, &[1, 20, 30, 40]);
493 ///
494 /// v.extend_from_slice(&[50, 60], GFP_KERNEL)?;
495 /// assert_eq!(&v, &[1, 20, 30, 40, 50, 60]);
496 /// # Ok::<(), Error>(())
497 /// ```
498 pub fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), AllocError> {
499 self.reserve(other.len(), flags)?;
500 for (slot, item) in core::iter::zip(self.spare_capacity_mut(), other) {
501 slot.write(item.clone());
502 }
504 // SAFETY:
505 // - `other.len()` spare entries have just been initialized, so it is safe to increase
506 // the length by the same number.
507 // - `self.len() + other.len() <= self.capacity()` is guaranteed by the preceding `reserve`
508 // call.
509 unsafe { self.set_len(self.len() + other.len()) };
510 Ok(())
511 }
513 /// Create a new `Vec<T, A>` and extend it by `n` clones of `value`.
514 pub fn from_elem(value: T, n: usize, flags: Flags) -> Result<Self, AllocError> {
515 let mut v = Self::with_capacity(n, flags)?;
517 v.extend_with(n, value, flags)?;
519 Ok(v)
520 }
521 }
523 impl<T, A> Drop for Vec<T, A>
524 where
525 A: Allocator,
526 {
527 fn drop(&mut self) {
528 // SAFETY: `self.as_mut_ptr` is guaranteed to be valid by the type invariant.
529 unsafe {
530 ptr::drop_in_place(core::ptr::slice_from_raw_parts_mut(
531 self.as_mut_ptr(),
532 self.len,
533 ))
534 };
536 // SAFETY:
537 // - `self.ptr` was previously allocated with `A`.
538 // - `self.layout` matches the `ArrayLayout` of the preceding allocation.
539 unsafe { A::free(self.ptr.cast(), self.layout.into()) };
540 }
541 }
543 impl<T, A, const N: usize> From<Box<[T; N], A>> for Vec<T, A>
544 where
545 A: Allocator,
546 {
547 fn from(b: Box<[T; N], A>) -> Vec<T, A> {
548 let len = b.len();
549 let ptr = Box::into_raw(b);
551 // SAFETY:
552 // - `b` has been allocated with `A`,
553 // - `ptr` fulfills the alignment requirements for `T`,
554 // - `ptr` points to memory with at least a size of `size_of::<T>() * len`,
555 // - all elements within `b` are initialized values of `T`,
556 // - `len` does not exceed `isize::MAX`.
557 unsafe { Vec::from_raw_parts(ptr as _, len, len) }
558 }
559 }
561 impl<T> Default for KVec<T> {
562 #[inline]
563 fn default() -> Self {
564 Self::new()
565 }
566 }
568 impl<T: fmt::Debug, A: Allocator> fmt::Debug for Vec<T, A> {
569 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
570 fmt::Debug::fmt(&**self, f)
571 }
572 }
574 impl<T, A> Deref for Vec<T, A>
575 where
576 A: Allocator,
577 {
578 type Target = [T];
580 #[inline]
581 fn deref(&self) -> &[T] {
582 // SAFETY: The memory behind `self.as_ptr()` is guaranteed to contain `self.len`
583 // initialized elements of type `T`.
584 unsafe { slice::from_raw_parts(self.as_ptr(), self.len) }
585 }
586 }
588 impl<T, A> DerefMut for Vec<T, A>
589 where
590 A: Allocator,
591 {
592 #[inline]
593 fn deref_mut(&mut self) -> &mut [T] {
594 // SAFETY: The memory behind `self.as_ptr()` is guaranteed to contain `self.len`
595 // initialized elements of type `T`.
596 unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) }
597 }
598 }
600 impl<T: Eq, A> Eq for Vec<T, A> where A: Allocator {}
602 impl<T, I: SliceIndex<[T]>, A> Index<I> for Vec<T, A>
603 where
604 A: Allocator,
605 {
606 type Output = I::Output;
608 #[inline]
609 fn index(&self, index: I) -> &Self::Output {
610 Index::index(&**self, index)
611 }
612 }
614 impl<T, I: SliceIndex<[T]>, A> IndexMut<I> for Vec<T, A>
615 where
616 A: Allocator,
617 {
618 #[inline]
619 fn index_mut(&mut self, index: I) -> &mut Self::Output {
620 IndexMut::index_mut(&mut **self, index)
621 }
622 }
624 macro_rules! impl_slice_eq {
625 ($([$($vars:tt)*] $lhs:ty, $rhs:ty,)*) => {
626 $(
627 impl<T, U, $($vars)*> PartialEq<$rhs> for $lhs
628 where
629 T: PartialEq<U>,
630 {
631 #[inline]
632 fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] }
633 }
634 )*
635 }
636 }
638 impl_slice_eq! {
639 [A1: Allocator, A2: Allocator] Vec<T, A1>, Vec<U, A2>,
640 [A: Allocator] Vec<T, A>, &[U],
641 [A: Allocator] Vec<T, A>, &mut [U],
642 [A: Allocator] &[T], Vec<U, A>,
643 [A: Allocator] &mut [T], Vec<U, A>,
644 [A: Allocator] Vec<T, A>, [U],
645 [A: Allocator] [T], Vec<U, A>,
646 [A: Allocator, const N: usize] Vec<T, A>, [U; N],
647 [A: Allocator, const N: usize] Vec<T, A>, &[U; N],
648 }
650 impl<'a, T, A> IntoIterator for &'a Vec<T, A>
651 where
652 A: Allocator,
653 {
654 type Item = &'a T;
655 type IntoIter = slice::Iter<'a, T>;
657 fn into_iter(self) -> Self::IntoIter {
658 self.iter()
659 }
660 }
662 impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A>
663 where
664 A: Allocator,
665 {
666 type Item = &'a mut T;
667 type IntoIter = slice::IterMut<'a, T>;
669 fn into_iter(self) -> Self::IntoIter {
670 self.iter_mut()
671 }
672 }
674 /// An [`Iterator`] implementation for [`Vec`] that moves elements out of a vector.
675 ///
676 /// This structure is created by the [`Vec::into_iter`] method on [`Vec`] (provided by the
677 /// [`IntoIterator`] trait).
678 ///
679 /// # Examples
680 ///
681 /// ```
682 /// let v = kernel::kvec![0, 1, 2]?;
683 /// let iter = v.into_iter();
684 ///
685 /// # Ok::<(), Error>(())
686 /// ```
687 pub struct IntoIter<T, A: Allocator> {
688 ptr: *mut T,
689 buf: NonNull<T>,
690 len: usize,
691 layout: ArrayLayout<T>,
692 _p: PhantomData<A>,
693 }
695 impl<T, A> IntoIter<T, A>
696 where
697 A: Allocator,
698 {
699 fn into_raw_parts(self) -> (*mut T, NonNull<T>, usize, usize) {
700 let me = ManuallyDrop::new(self);
701 let ptr = me.ptr;
702 let buf = me.buf;
703 let len = me.len;
704 let cap = me.layout.len();
705 (ptr, buf, len, cap)
706 }
708 /// Same as `Iterator::collect` but specialized for `Vec`'s `IntoIter`.
709 ///
710 /// # Examples
711 ///
712 /// ```
713 /// let v = kernel::kvec![1, 2, 3]?;
714 /// let mut it = v.into_iter();
715 ///
716 /// assert_eq!(it.next(), Some(1));
717 ///
718 /// let v = it.collect(GFP_KERNEL);
719 /// assert_eq!(v, [2, 3]);
720 ///
721 /// # Ok::<(), Error>(())
722 /// ```
723 ///
724 /// # Implementation details
725 ///
726 /// Currently, we can't implement `FromIterator`. There are a couple of issues with this trait
727 /// in the kernel, namely:
728 ///
729 /// - Rust's specialization feature is unstable. This prevents us to optimize for the special
730 /// case where `I::IntoIter` equals `Vec`'s `IntoIter` type.
731 /// - We also can't use `I::IntoIter`'s type ID either to work around this, since `FromIterator`
732 /// doesn't require this type to be `'static`.
733 /// - `FromIterator::from_iter` does return `Self` instead of `Result<Self, AllocError>`, hence
734 /// we can't properly handle allocation failures.
735 /// - Neither `Iterator::collect` nor `FromIterator::from_iter` can handle additional allocation
736 /// flags.
737 ///
738 /// Instead, provide `IntoIter::collect`, such that we can at least convert a `IntoIter` into a
739 /// `Vec` again.
740 ///
741 /// Note that `IntoIter::collect` doesn't require `Flags`, since it re-uses the existing backing
742 /// buffer. However, this backing buffer may be shrunk to the actual count of elements.
743 pub fn collect(self, flags: Flags) -> Vec<T, A> {
744 let old_layout = self.layout;
745 let (mut ptr, buf, len, mut cap) = self.into_raw_parts();
746 let has_advanced = ptr != buf.as_ptr();
748 if has_advanced {
749 // Copy the contents we have advanced to at the beginning of the buffer.
750 //
751 // SAFETY:
752 // - `ptr` is valid for reads of `len * size_of::<T>()` bytes,
753 // - `buf.as_ptr()` is valid for writes of `len * size_of::<T>()` bytes,
754 // - `ptr` and `buf.as_ptr()` are not be subject to aliasing restrictions relative to
755 // each other,
756 // - both `ptr` and `buf.ptr()` are properly aligned.
757 unsafe { ptr::copy(ptr, buf.as_ptr(), len) };
758 ptr = buf.as_ptr();
760 // SAFETY: `len` is guaranteed to be smaller than `self.layout.len()`.
761 let layout = unsafe { ArrayLayout::<T>::new_unchecked(len) };
763 // SAFETY: `buf` points to the start of the backing buffer and `len` is guaranteed to be
764 // smaller than `cap`. Depending on `alloc` this operation may shrink the buffer or leaves
765 // it as it is.
766 ptr = match unsafe {
767 A::realloc(Some(buf.cast()), layout.into(), old_layout.into(), flags)
768 } {
769 // If we fail to shrink, which likely can't even happen, continue with the existing
770 // buffer.
771 Err(_) => ptr,
772 Ok(ptr) => {
773 cap = len;
774 ptr.as_ptr().cast()
775 }
776 };
777 }
779 // SAFETY: If the iterator has been advanced, the advanced elements have been copied to
780 // the beginning of the buffer and `len` has been adjusted accordingly.
781 //
782 // - `ptr` is guaranteed to point to the start of the backing buffer.
783 // - `cap` is either the original capacity or, after shrinking the buffer, equal to `len`.
784 // - `alloc` is guaranteed to be unchanged since `into_iter` has been called on the original
785 // `Vec`.
786 unsafe { Vec::from_raw_parts(ptr, len, cap) }
787 }
788 }
790 impl<T, A> Iterator for IntoIter<T, A>
791 where
792 A: Allocator,
793 {
794 type Item = T;
796 /// # Examples
797 ///
798 /// ```
799 /// let v = kernel::kvec![1, 2, 3]?;
800 /// let mut it = v.into_iter();
801 ///
802 /// assert_eq!(it.next(), Some(1));
803 /// assert_eq!(it.next(), Some(2));
804 /// assert_eq!(it.next(), Some(3));
805 /// assert_eq!(it.next(), None);
806 ///
807 /// # Ok::<(), Error>(())
808 /// ```
809 fn next(&mut self) -> Option<T> {
810 if self.len == 0 {
811 return None;
812 }
814 let current = self.ptr;
816 // SAFETY: We can't overflow; decreasing `self.len` by one every time we advance `self.ptr`
817 // by one guarantees that.
818 unsafe { self.ptr = self.ptr.add(1) };
820 self.len -= 1;
822 // SAFETY: `current` is guaranteed to point at a valid element within the buffer.
823 Some(unsafe { current.read() })
824 }
826 /// # Examples
827 ///
828 /// ```
829 /// let v: KVec<u32> = kernel::kvec![1, 2, 3]?;
830 /// let mut iter = v.into_iter();
831 /// let size = iter.size_hint().0;
832 ///
833 /// iter.next();
834 /// assert_eq!(iter.size_hint().0, size - 1);
835 ///
836 /// iter.next();
837 /// assert_eq!(iter.size_hint().0, size - 2);
838 ///
839 /// iter.next();
840 /// assert_eq!(iter.size_hint().0, size - 3);
841 ///
842 /// # Ok::<(), Error>(())
843 /// ```
844 fn size_hint(&self) -> (usize, Option<usize>) {
845 (self.len, Some(self.len))
846 }
847 }
849 impl<T, A> Drop for IntoIter<T, A>
850 where
851 A: Allocator,
852 {
853 fn drop(&mut self) {
854 // SAFETY: `self.ptr` is guaranteed to be valid by the type invariant.
855 unsafe { ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.ptr, self.len)) };
857 // SAFETY:
858 // - `self.buf` was previously allocated with `A`.
859 // - `self.layout` matches the `ArrayLayout` of the preceding allocation.
860 unsafe { A::free(self.buf.cast(), self.layout.into()) };
861 }
862 }
864 impl<T, A> IntoIterator for Vec<T, A>
865 where
866 A: Allocator,
867 {
868 type Item = T;
869 type IntoIter = IntoIter<T, A>;
871 /// Consumes the `Vec<T, A>` and creates an `Iterator`, which moves each value out of the
872 /// vector (from start to end).
873 ///
874 /// # Examples
875 ///
876 /// ```
877 /// let v = kernel::kvec![1, 2]?;
878 /// let mut v_iter = v.into_iter();
879 ///
880 /// let first_element: Option<u32> = v_iter.next();
881 ///
882 /// assert_eq!(first_element, Some(1));
883 /// assert_eq!(v_iter.next(), Some(2));
884 /// assert_eq!(v_iter.next(), None);
885 ///
886 /// # Ok::<(), Error>(())
887 /// ```
888 ///
889 /// ```
890 /// let v = kernel::kvec![];
891 /// let mut v_iter = v.into_iter();
892 ///
893 /// let first_element: Option<u32> = v_iter.next();
894 ///
895 /// assert_eq!(first_element, None);
896 ///
897 /// # Ok::<(), Error>(())
898 /// ```
899 #[inline]
900 fn into_iter(self) -> Self::IntoIter {
901 let buf = self.ptr;
902 let layout = self.layout;
903 let (ptr, len, _) = self.into_raw_parts();
905 IntoIter {
906 ptr,
907 buf,
908 len,
909 layout,
910 _p: PhantomData::<A>,
911 }
912 }
913 }