1 // SPDX-License-Identifier: GPL-2.0 2 3 //! Implementation of [`Vec`]. 4 5 use super::{ 6 allocator::{KVmalloc, Kmalloc, Vmalloc}, 7 layout::ArrayLayout, 8 AllocError, Allocator, Box, Flags, 9 }; 10 use crate::fmt; 11 use core::{ 12 borrow::{Borrow, BorrowMut}, 13 marker::PhantomData, 14 mem::{ManuallyDrop, MaybeUninit}, 15 ops::Deref, 16 ops::DerefMut, 17 ops::Index, 18 ops::IndexMut, 19 ptr, 20 ptr::NonNull, 21 slice, 22 slice::SliceIndex, 23 }; 24 25 mod errors; 26 pub use self::errors::{InsertError, PushError, RemoveError}; 27 28 /// Create a [`KVec`] containing the arguments. 29 /// 30 /// New memory is allocated with `GFP_KERNEL`. 31 /// 32 /// # Examples 33 /// 34 /// ``` 35 /// let mut v = kernel::kvec![]; 36 /// v.push(1, GFP_KERNEL)?; 37 /// assert_eq!(v, [1]); 38 /// 39 /// let mut v = kernel::kvec![1; 3]?; 40 /// v.push(4, GFP_KERNEL)?; 41 /// assert_eq!(v, [1, 1, 1, 4]); 42 /// 43 /// let mut v = kernel::kvec![1, 2, 3]?; 44 /// v.push(4, GFP_KERNEL)?; 45 /// assert_eq!(v, [1, 2, 3, 4]); 46 /// 47 /// # Ok::<(), Error>(()) 48 /// ``` 49 #[macro_export] 50 macro_rules! kvec { 51 () => ( 52 $crate::alloc::KVec::new() 53 ); 54 ($elem:expr; $n:expr) => ( 55 $crate::alloc::KVec::from_elem($elem, $n, GFP_KERNEL) 56 ); 57 ($($x:expr),+ $(,)?) => ( 58 match $crate::alloc::KBox::new_uninit(GFP_KERNEL) { 59 Ok(b) => Ok($crate::alloc::KVec::from($crate::alloc::KBox::write(b, [$($x),+]))), 60 Err(e) => Err(e), 61 } 62 ); 63 } 64 65 /// The kernel's [`Vec`] type. 66 /// 67 /// A contiguous growable array type with contents allocated with the kernel's allocators (e.g. 68 /// [`Kmalloc`], [`Vmalloc`] or [`KVmalloc`]), written `Vec<T, A>`. 69 /// 70 /// For non-zero-sized values, a [`Vec`] will use the given allocator `A` for its allocation. For 71 /// the most common allocators the type aliases [`KVec`], [`VVec`] and [`KVVec`] exist. 72 /// 73 /// For zero-sized types the [`Vec`]'s pointer must be `dangling_mut::<T>`; no memory is allocated. 74 /// 75 /// Generally, [`Vec`] consists of a pointer that represents the vector's backing buffer, the 76 /// capacity of the vector (the number of elements that currently fit into the vector), its length 77 /// (the number of elements that are currently stored in the vector) and the `Allocator` type used 78 /// to allocate (and free) the backing buffer. 79 /// 80 /// A [`Vec`] can be deconstructed into and (re-)constructed from its previously named raw parts 81 /// and manually modified. 82 /// 83 /// [`Vec`]'s backing buffer gets, if required, automatically increased (re-allocated) when elements 84 /// are added to the vector. 85 /// 86 /// # Invariants 87 /// 88 /// - `self.ptr` is always properly aligned and either points to memory allocated with `A` or, for 89 /// zero-sized types, is a dangling, well aligned pointer. 90 /// 91 /// - `self.len` always represents the exact number of elements stored in the vector. 92 /// 93 /// - `self.layout` represents the absolute number of elements that can be stored within the vector 94 /// without re-allocation. For ZSTs `self.layout`'s capacity is zero. However, it is legal for the 95 /// backing buffer to be larger than `layout`. 96 /// 97 /// - `self.len()` is always less than or equal to `self.capacity()`. 98 /// 99 /// - The `Allocator` type `A` of the vector is the exact same `Allocator` type the backing buffer 100 /// was allocated with (and must be freed with). 101 pub struct Vec<T, A: Allocator> { 102 ptr: NonNull<T>, 103 /// Represents the actual buffer size as `cap` times `size_of::<T>` bytes. 104 /// 105 /// Note: This isn't quite the same as `Self::capacity`, which in contrast returns the number of 106 /// elements we can still store without reallocating. 107 layout: ArrayLayout<T>, 108 len: usize, 109 _p: PhantomData<A>, 110 } 111 112 /// Type alias for [`Vec`] with a [`Kmalloc`] allocator. 113 /// 114 /// # Examples 115 /// 116 /// ``` 117 /// let mut v = KVec::new(); 118 /// v.push(1, GFP_KERNEL)?; 119 /// assert_eq!(&v, &[1]); 120 /// 121 /// # Ok::<(), Error>(()) 122 /// ``` 123 pub type KVec<T> = Vec<T, Kmalloc>; 124 125 /// Type alias for [`Vec`] with a [`Vmalloc`] allocator. 126 /// 127 /// # Examples 128 /// 129 /// ``` 130 /// let mut v = VVec::new(); 131 /// v.push(1, GFP_KERNEL)?; 132 /// assert_eq!(&v, &[1]); 133 /// 134 /// # Ok::<(), Error>(()) 135 /// ``` 136 pub type VVec<T> = Vec<T, Vmalloc>; 137 138 /// Type alias for [`Vec`] with a [`KVmalloc`] allocator. 139 /// 140 /// # Examples 141 /// 142 /// ``` 143 /// let mut v = KVVec::new(); 144 /// v.push(1, GFP_KERNEL)?; 145 /// assert_eq!(&v, &[1]); 146 /// 147 /// # Ok::<(), Error>(()) 148 /// ``` 149 pub type KVVec<T> = Vec<T, KVmalloc>; 150 151 // SAFETY: `Vec` is `Send` if `T` is `Send` because `Vec` owns its elements. 152 unsafe impl<T, A> Send for Vec<T, A> 153 where 154 T: Send, 155 A: Allocator, 156 { 157 } 158 159 // SAFETY: `Vec` is `Sync` if `T` is `Sync` because `Vec` owns its elements. 160 unsafe impl<T, A> Sync for Vec<T, A> 161 where 162 T: Sync, 163 A: Allocator, 164 { 165 } 166 167 impl<T, A> Vec<T, A> 168 where 169 A: Allocator, 170 { 171 #[inline] 172 const fn is_zst() -> bool { 173 core::mem::size_of::<T>() == 0 174 } 175 176 /// Returns the number of elements that can be stored within the vector without allocating 177 /// additional memory. 178 pub const fn capacity(&self) -> usize { 179 if const { Self::is_zst() } { 180 usize::MAX 181 } else { 182 self.layout.len() 183 } 184 } 185 186 /// Returns the number of elements stored within the vector. 187 #[inline] 188 pub const fn len(&self) -> usize { 189 self.len 190 } 191 192 /// Increments `self.len` by `additional`. 193 /// 194 /// # Safety 195 /// 196 /// - `additional` must be less than or equal to `self.capacity - self.len`. 197 /// - All elements within the interval [`self.len`,`self.len + additional`) must be initialized. 198 #[inline] 199 pub const unsafe fn inc_len(&mut self, additional: usize) { 200 // Guaranteed by the type invariant to never underflow. 201 debug_assert!(additional <= self.capacity() - self.len()); 202 // INVARIANT: By the safety requirements of this method this represents the exact number of 203 // elements stored within `self`. 204 self.len += additional; 205 } 206 207 /// Decreases `self.len` by `count`. 208 /// 209 /// Returns a mutable slice to the elements forgotten by the vector. It is the caller's 210 /// responsibility to drop these elements if necessary. 211 /// 212 /// # Safety 213 /// 214 /// - `count` must be less than or equal to `self.len`. 215 unsafe fn dec_len(&mut self, count: usize) -> &mut [T] { 216 debug_assert!(count <= self.len()); 217 // INVARIANT: We relinquish ownership of the elements within the range `[self.len - count, 218 // self.len)`, hence the updated value of `set.len` represents the exact number of elements 219 // stored within `self`. 220 self.len -= count; 221 // SAFETY: The memory after `self.len()` is guaranteed to contain `count` initialized 222 // elements of type `T`. 223 unsafe { slice::from_raw_parts_mut(self.as_mut_ptr().add(self.len), count) } 224 } 225 226 /// Returns a slice of the entire vector. 227 /// 228 /// # Examples 229 /// 230 /// ``` 231 /// let mut v = KVec::new(); 232 /// v.push(1, GFP_KERNEL)?; 233 /// v.push(2, GFP_KERNEL)?; 234 /// assert_eq!(v.as_slice(), &[1, 2]); 235 /// # Ok::<(), Error>(()) 236 /// ``` 237 #[inline] 238 pub fn as_slice(&self) -> &[T] { 239 self 240 } 241 242 /// Returns a mutable slice of the entire vector. 243 #[inline] 244 pub fn as_mut_slice(&mut self) -> &mut [T] { 245 self 246 } 247 248 /// Returns a mutable raw pointer to the vector's backing buffer, or, if `T` is a ZST, a 249 /// dangling raw pointer. 250 #[inline] 251 pub fn as_mut_ptr(&mut self) -> *mut T { 252 self.ptr.as_ptr() 253 } 254 255 /// Returns a raw pointer to the vector's backing buffer, or, if `T` is a ZST, a dangling raw 256 /// pointer. 257 #[inline] 258 pub const fn as_ptr(&self) -> *const T { 259 self.ptr.as_ptr() 260 } 261 262 /// Returns `true` if the vector contains no elements, `false` otherwise. 263 /// 264 /// # Examples 265 /// 266 /// ``` 267 /// let mut v = KVec::new(); 268 /// assert!(v.is_empty()); 269 /// 270 /// v.push(1, GFP_KERNEL); 271 /// assert!(!v.is_empty()); 272 /// ``` 273 #[inline] 274 pub const fn is_empty(&self) -> bool { 275 self.len() == 0 276 } 277 278 /// Creates a new, empty `Vec<T, A>`. 279 /// 280 /// This method does not allocate by itself. 281 #[inline] 282 pub const fn new() -> Self { 283 // INVARIANT: Since this is a new, empty `Vec` with no backing memory yet, 284 // - `ptr` is a properly aligned dangling pointer for type `T`, 285 // - `layout` is an empty `ArrayLayout` (zero capacity) 286 // - `len` is zero, since no elements can be or have been stored, 287 // - `A` is always valid. 288 Self { 289 ptr: NonNull::dangling(), 290 layout: ArrayLayout::empty(), 291 len: 0, 292 _p: PhantomData::<A>, 293 } 294 } 295 296 /// Returns a slice of `MaybeUninit<T>` for the remaining spare capacity of the vector. 297 pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] { 298 // SAFETY: 299 // - `self.len` is smaller than `self.capacity` by the type invariant and hence, the 300 // resulting pointer is guaranteed to be part of the same allocated object. 301 // - `self.len` can not overflow `isize`. 302 let ptr = unsafe { self.as_mut_ptr().add(self.len) }.cast::<MaybeUninit<T>>(); 303 304 // SAFETY: The memory between `self.len` and `self.capacity` is guaranteed to be allocated 305 // and valid, but uninitialized. 306 unsafe { slice::from_raw_parts_mut(ptr, self.capacity() - self.len) } 307 } 308 309 /// Appends an element to the back of the [`Vec`] instance. 310 /// 311 /// # Examples 312 /// 313 /// ``` 314 /// let mut v = KVec::new(); 315 /// v.push(1, GFP_KERNEL)?; 316 /// assert_eq!(&v, &[1]); 317 /// 318 /// v.push(2, GFP_KERNEL)?; 319 /// assert_eq!(&v, &[1, 2]); 320 /// # Ok::<(), Error>(()) 321 /// ``` 322 pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> { 323 self.reserve(1, flags)?; 324 // SAFETY: The call to `reserve` was successful, so the capacity is at least one greater 325 // than the length. 326 unsafe { self.push_within_capacity_unchecked(v) }; 327 Ok(()) 328 } 329 330 /// Appends an element to the back of the [`Vec`] instance without reallocating. 331 /// 332 /// Fails if the vector does not have capacity for the new element. 333 /// 334 /// # Examples 335 /// 336 /// ``` 337 /// let mut v = KVec::with_capacity(10, GFP_KERNEL)?; 338 /// for i in 0..10 { 339 /// v.push_within_capacity(i)?; 340 /// } 341 /// 342 /// assert!(v.push_within_capacity(10).is_err()); 343 /// # Ok::<(), Error>(()) 344 /// ``` 345 pub fn push_within_capacity(&mut self, v: T) -> Result<(), PushError<T>> { 346 if self.len() < self.capacity() { 347 // SAFETY: The length is less than the capacity. 348 unsafe { self.push_within_capacity_unchecked(v) }; 349 Ok(()) 350 } else { 351 Err(PushError(v)) 352 } 353 } 354 355 /// Appends an element to the back of the [`Vec`] instance without reallocating. 356 /// 357 /// # Safety 358 /// 359 /// The length must be less than the capacity. 360 unsafe fn push_within_capacity_unchecked(&mut self, v: T) { 361 let spare = self.spare_capacity_mut(); 362 363 // SAFETY: By the safety requirements, `spare` is non-empty. 364 unsafe { spare.get_unchecked_mut(0) }.write(v); 365 366 // SAFETY: We just initialised the first spare entry, so it is safe to increase the length 367 // by 1. We also know that the new length is <= capacity because the caller guarantees that 368 // the length is less than the capacity at the beginning of this function. 369 unsafe { self.inc_len(1) }; 370 } 371 372 /// Inserts an element at the given index in the [`Vec`] instance. 373 /// 374 /// Fails if the vector does not have capacity for the new element. Panics if the index is out 375 /// of bounds. 376 /// 377 /// # Examples 378 /// 379 /// ``` 380 /// use kernel::alloc::kvec::InsertError; 381 /// 382 /// let mut v = KVec::with_capacity(5, GFP_KERNEL)?; 383 /// for i in 0..5 { 384 /// v.insert_within_capacity(0, i)?; 385 /// } 386 /// 387 /// assert!(matches!(v.insert_within_capacity(0, 5), Err(InsertError::OutOfCapacity(_)))); 388 /// assert!(matches!(v.insert_within_capacity(1000, 5), Err(InsertError::IndexOutOfBounds(_)))); 389 /// assert_eq!(v, [4, 3, 2, 1, 0]); 390 /// # Ok::<(), Error>(()) 391 /// ``` 392 pub fn insert_within_capacity( 393 &mut self, 394 index: usize, 395 element: T, 396 ) -> Result<(), InsertError<T>> { 397 let len = self.len(); 398 if index > len { 399 return Err(InsertError::IndexOutOfBounds(element)); 400 } 401 402 if len >= self.capacity() { 403 return Err(InsertError::OutOfCapacity(element)); 404 } 405 406 // SAFETY: This is in bounds since `index <= len < capacity`. 407 let p = unsafe { self.as_mut_ptr().add(index) }; 408 // INVARIANT: This breaks the Vec invariants by making `index` contain an invalid element, 409 // but we restore the invariants below. 410 // SAFETY: Both the src and dst ranges end no later than one element after the length. 411 // Since the length is less than the capacity, both ranges are in bounds of the allocation. 412 unsafe { ptr::copy(p, p.add(1), len - index) }; 413 // INVARIANT: This restores the Vec invariants. 414 // SAFETY: The pointer is in-bounds of the allocation. 415 unsafe { ptr::write(p, element) }; 416 // SAFETY: Index `len` contains a valid element due to the above copy and write. 417 unsafe { self.inc_len(1) }; 418 Ok(()) 419 } 420 421 /// Removes the last element from a vector and returns it, or `None` if it is empty. 422 /// 423 /// # Examples 424 /// 425 /// ``` 426 /// let mut v = KVec::new(); 427 /// v.push(1, GFP_KERNEL)?; 428 /// v.push(2, GFP_KERNEL)?; 429 /// assert_eq!(&v, &[1, 2]); 430 /// 431 /// assert_eq!(v.pop(), Some(2)); 432 /// assert_eq!(v.pop(), Some(1)); 433 /// assert_eq!(v.pop(), None); 434 /// # Ok::<(), Error>(()) 435 /// ``` 436 pub fn pop(&mut self) -> Option<T> { 437 if self.is_empty() { 438 return None; 439 } 440 441 let removed: *mut T = { 442 // SAFETY: We just checked that the length is at least one. 443 let slice = unsafe { self.dec_len(1) }; 444 // SAFETY: The argument to `dec_len` was 1 so this returns a slice of length 1. 445 unsafe { slice.get_unchecked_mut(0) } 446 }; 447 448 // SAFETY: The guarantees of `dec_len` allow us to take ownership of this value. 449 Some(unsafe { removed.read() }) 450 } 451 452 /// Removes the element at the given index. 453 /// 454 /// # Examples 455 /// 456 /// ``` 457 /// let mut v = kernel::kvec![1, 2, 3]?; 458 /// assert_eq!(v.remove(1)?, 2); 459 /// assert_eq!(v, [1, 3]); 460 /// # Ok::<(), Error>(()) 461 /// ``` 462 pub fn remove(&mut self, i: usize) -> Result<T, RemoveError> { 463 let value = { 464 let value_ref = self.get(i).ok_or(RemoveError)?; 465 // INVARIANT: This breaks the invariants by invalidating the value at index `i`, but we 466 // restore the invariants below. 467 // SAFETY: The value at index `i` is valid, because otherwise we would have already 468 // failed with `RemoveError`. 469 unsafe { ptr::read(value_ref) } 470 }; 471 472 // SAFETY: We checked that `i` is in-bounds. 473 let p = unsafe { self.as_mut_ptr().add(i) }; 474 475 // INVARIANT: After this call, the invalid value is at the last slot, so the Vec invariants 476 // are restored after the below call to `dec_len(1)`. 477 // SAFETY: `p.add(1).add(self.len - i - 1)` is `i+1+len-i-1 == len` elements after the 478 // beginning of the vector, so this is in-bounds of the vector's allocation. 479 unsafe { ptr::copy(p.add(1), p, self.len - i - 1) }; 480 481 // SAFETY: Since the check at the beginning of this call did not fail with `RemoveError`, 482 // the length is at least one. 483 unsafe { self.dec_len(1) }; 484 485 Ok(value) 486 } 487 488 /// Creates a new [`Vec`] instance with at least the given capacity. 489 /// 490 /// # Examples 491 /// 492 /// ``` 493 /// let v = KVec::<u32>::with_capacity(20, GFP_KERNEL)?; 494 /// 495 /// assert!(v.capacity() >= 20); 496 /// # Ok::<(), Error>(()) 497 /// ``` 498 pub fn with_capacity(capacity: usize, flags: Flags) -> Result<Self, AllocError> { 499 let mut v = Vec::new(); 500 501 v.reserve(capacity, flags)?; 502 503 Ok(v) 504 } 505 506 /// Creates a `Vec<T, A>` from a pointer, a length and a capacity using the allocator `A`. 507 /// 508 /// # Examples 509 /// 510 /// ``` 511 /// let mut v = kernel::kvec![1, 2, 3]?; 512 /// v.reserve(1, GFP_KERNEL)?; 513 /// 514 /// let (mut ptr, mut len, cap) = v.into_raw_parts(); 515 /// 516 /// // SAFETY: We've just reserved memory for another element. 517 /// unsafe { ptr.add(len).write(4) }; 518 /// len += 1; 519 /// 520 /// // SAFETY: We only wrote an additional element at the end of the `KVec`'s buffer and 521 /// // correspondingly increased the length of the `KVec` by one. Otherwise, we construct it 522 /// // from the exact same raw parts. 523 /// let v = unsafe { KVec::from_raw_parts(ptr, len, cap) }; 524 /// 525 /// assert_eq!(v, [1, 2, 3, 4]); 526 /// 527 /// # Ok::<(), Error>(()) 528 /// ``` 529 /// 530 /// # Safety 531 /// 532 /// If `T` is a ZST: 533 /// 534 /// - `ptr` must be a dangling, well aligned pointer. 535 /// 536 /// Otherwise: 537 /// 538 /// - `ptr` must have been allocated with the allocator `A`. 539 /// - `ptr` must satisfy or exceed the alignment requirements of `T`. 540 /// - `ptr` must point to memory with a size of at least `size_of::<T>() * capacity` bytes. 541 /// - The allocated size in bytes must not be larger than `isize::MAX`. 542 /// - `length` must be less than or equal to `capacity`. 543 /// - The first `length` elements must be initialized values of type `T`. 544 /// 545 /// It is also valid to create an empty `Vec` passing a dangling pointer for `ptr` and zero for 546 /// `cap` and `len`. 547 pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self { 548 let layout = if Self::is_zst() { 549 ArrayLayout::empty() 550 } else { 551 // SAFETY: By the safety requirements of this function, `capacity * size_of::<T>()` is 552 // smaller than `isize::MAX`. 553 unsafe { ArrayLayout::new_unchecked(capacity) } 554 }; 555 556 // INVARIANT: For ZSTs, we store an empty `ArrayLayout`, all other type invariants are 557 // covered by the safety requirements of this function. 558 Self { 559 // SAFETY: By the safety requirements, `ptr` is either dangling or pointing to a valid 560 // memory allocation, allocated with `A`. 561 ptr: unsafe { NonNull::new_unchecked(ptr) }, 562 layout, 563 len: length, 564 _p: PhantomData::<A>, 565 } 566 } 567 568 /// Consumes the `Vec<T, A>` and returns its raw components `pointer`, `length` and `capacity`. 569 /// 570 /// This will not run the destructor of the contained elements and for non-ZSTs the allocation 571 /// will stay alive indefinitely. Use [`Vec::from_raw_parts`] to recover the [`Vec`], drop the 572 /// elements and free the allocation, if any. 573 pub fn into_raw_parts(self) -> (*mut T, usize, usize) { 574 let mut me = ManuallyDrop::new(self); 575 let len = me.len(); 576 let capacity = me.capacity(); 577 let ptr = me.as_mut_ptr(); 578 (ptr, len, capacity) 579 } 580 581 /// Clears the vector, removing all values. 582 /// 583 /// Note that this method has no effect on the allocated capacity 584 /// of the vector. 585 /// 586 /// # Examples 587 /// 588 /// ``` 589 /// let mut v = kernel::kvec![1, 2, 3]?; 590 /// 591 /// v.clear(); 592 /// 593 /// assert!(v.is_empty()); 594 /// # Ok::<(), Error>(()) 595 /// ``` 596 #[inline] 597 pub fn clear(&mut self) { 598 self.truncate(0); 599 } 600 601 /// Ensures that the capacity exceeds the length by at least `additional` elements. 602 /// 603 /// # Examples 604 /// 605 /// ``` 606 /// let mut v = KVec::new(); 607 /// v.push(1, GFP_KERNEL)?; 608 /// 609 /// v.reserve(10, GFP_KERNEL)?; 610 /// let cap = v.capacity(); 611 /// assert!(cap >= 10); 612 /// 613 /// v.reserve(10, GFP_KERNEL)?; 614 /// let new_cap = v.capacity(); 615 /// assert_eq!(new_cap, cap); 616 /// 617 /// # Ok::<(), Error>(()) 618 /// ``` 619 pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError> { 620 let len = self.len(); 621 let cap = self.capacity(); 622 623 if cap - len >= additional { 624 return Ok(()); 625 } 626 627 if Self::is_zst() { 628 // The capacity is already `usize::MAX` for ZSTs, we can't go higher. 629 return Err(AllocError); 630 } 631 632 // We know that `cap <= isize::MAX` because of the type invariants of `Self`. So the 633 // multiplication by two won't overflow. 634 let new_cap = core::cmp::max(cap * 2, len.checked_add(additional).ok_or(AllocError)?); 635 let layout = ArrayLayout::new(new_cap).map_err(|_| AllocError)?; 636 637 // SAFETY: 638 // - `ptr` is valid because it's either `None` or comes from a previous call to 639 // `A::realloc`. 640 // - `self.layout` matches the `ArrayLayout` of the preceding allocation. 641 let ptr = unsafe { 642 A::realloc( 643 Some(self.ptr.cast()), 644 layout.into(), 645 self.layout.into(), 646 flags, 647 )? 648 }; 649 650 // INVARIANT: 651 // - `layout` is some `ArrayLayout::<T>`, 652 // - `ptr` has been created by `A::realloc` from `layout`. 653 self.ptr = ptr.cast(); 654 self.layout = layout; 655 656 Ok(()) 657 } 658 659 /// Shortens the vector, setting the length to `len` and drops the removed values. 660 /// If `len` is greater than or equal to the current length, this does nothing. 661 /// 662 /// This has no effect on the capacity and will not allocate. 663 /// 664 /// # Examples 665 /// 666 /// ``` 667 /// let mut v = kernel::kvec![1, 2, 3]?; 668 /// v.truncate(1); 669 /// assert_eq!(v.len(), 1); 670 /// assert_eq!(&v, &[1]); 671 /// 672 /// # Ok::<(), Error>(()) 673 /// ``` 674 pub fn truncate(&mut self, len: usize) { 675 if let Some(count) = self.len().checked_sub(len) { 676 // SAFETY: `count` is `self.len() - len` so it is guaranteed to be less than or 677 // equal to `self.len()`. 678 let ptr: *mut [T] = unsafe { self.dec_len(count) }; 679 680 // SAFETY: the contract of `dec_len` guarantees that the elements in `ptr` are 681 // valid elements whose ownership has been transferred to the caller. 682 unsafe { ptr::drop_in_place(ptr) }; 683 } 684 } 685 686 /// Takes ownership of all items in this vector without consuming the allocation. 687 /// 688 /// # Examples 689 /// 690 /// ``` 691 /// let mut v = kernel::kvec![0, 1, 2, 3]?; 692 /// 693 /// for (i, j) in v.drain_all().enumerate() { 694 /// assert_eq!(i, j); 695 /// } 696 /// 697 /// assert!(v.capacity() >= 4); 698 /// # Ok::<(), Error>(()) 699 /// ``` 700 pub fn drain_all(&mut self) -> DrainAll<'_, T> { 701 // SAFETY: This does not underflow the length. 702 let elems = unsafe { self.dec_len(self.len()) }; 703 // INVARIANT: The first `len` elements of the spare capacity are valid values, and as we 704 // just set the length to zero, we may transfer ownership to the `DrainAll` object. 705 DrainAll { 706 elements: elems.iter_mut(), 707 } 708 } 709 710 /// Removes all elements that don't match the provided closure. 711 /// 712 /// # Examples 713 /// 714 /// ``` 715 /// let mut v = kernel::kvec![1, 2, 3, 4]?; 716 /// v.retain(|i| *i % 2 == 0); 717 /// assert_eq!(v, [2, 4]); 718 /// # Ok::<(), Error>(()) 719 /// ``` 720 pub fn retain(&mut self, mut f: impl FnMut(&mut T) -> bool) { 721 let mut num_kept = 0; 722 let mut next_to_check = 0; 723 while let Some(to_check) = self.get_mut(next_to_check) { 724 if f(to_check) { 725 self.swap(num_kept, next_to_check); 726 num_kept += 1; 727 } 728 next_to_check += 1; 729 } 730 self.truncate(num_kept); 731 } 732 } 733 734 impl<T: Clone, A: Allocator> Vec<T, A> { 735 /// Extend the vector by `n` clones of `value`. 736 pub fn extend_with(&mut self, n: usize, value: T, flags: Flags) -> Result<(), AllocError> { 737 if n == 0 { 738 return Ok(()); 739 } 740 741 self.reserve(n, flags)?; 742 743 let spare = self.spare_capacity_mut(); 744 745 for item in spare.iter_mut().take(n - 1) { 746 item.write(value.clone()); 747 } 748 749 // We can write the last element directly without cloning needlessly. 750 spare[n - 1].write(value); 751 752 // SAFETY: 753 // - `self.len() + n < self.capacity()` due to the call to reserve above, 754 // - the loop and the line above initialized the next `n` elements. 755 unsafe { self.inc_len(n) }; 756 757 Ok(()) 758 } 759 760 /// Pushes clones of the elements of slice into the [`Vec`] instance. 761 /// 762 /// # Examples 763 /// 764 /// ``` 765 /// let mut v = KVec::new(); 766 /// v.push(1, GFP_KERNEL)?; 767 /// 768 /// v.extend_from_slice(&[20, 30, 40], GFP_KERNEL)?; 769 /// assert_eq!(&v, &[1, 20, 30, 40]); 770 /// 771 /// v.extend_from_slice(&[50, 60], GFP_KERNEL)?; 772 /// assert_eq!(&v, &[1, 20, 30, 40, 50, 60]); 773 /// # Ok::<(), Error>(()) 774 /// ``` 775 pub fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), AllocError> { 776 self.reserve(other.len(), flags)?; 777 for (slot, item) in core::iter::zip(self.spare_capacity_mut(), other) { 778 slot.write(item.clone()); 779 } 780 781 // SAFETY: 782 // - `other.len()` spare entries have just been initialized, so it is safe to increase 783 // the length by the same number. 784 // - `self.len() + other.len() <= self.capacity()` is guaranteed by the preceding `reserve` 785 // call. 786 unsafe { self.inc_len(other.len()) }; 787 Ok(()) 788 } 789 790 /// Create a new `Vec<T, A>` and extend it by `n` clones of `value`. 791 pub fn from_elem(value: T, n: usize, flags: Flags) -> Result<Self, AllocError> { 792 let mut v = Self::with_capacity(n, flags)?; 793 794 v.extend_with(n, value, flags)?; 795 796 Ok(v) 797 } 798 799 /// Resizes the [`Vec`] so that `len` is equal to `new_len`. 800 /// 801 /// If `new_len` is smaller than `len`, the `Vec` is [`Vec::truncate`]d. 802 /// If `new_len` is larger, each new slot is filled with clones of `value`. 803 /// 804 /// # Examples 805 /// 806 /// ``` 807 /// let mut v = kernel::kvec![1, 2, 3]?; 808 /// v.resize(1, 42, GFP_KERNEL)?; 809 /// assert_eq!(&v, &[1]); 810 /// 811 /// v.resize(3, 42, GFP_KERNEL)?; 812 /// assert_eq!(&v, &[1, 42, 42]); 813 /// 814 /// # Ok::<(), Error>(()) 815 /// ``` 816 pub fn resize(&mut self, new_len: usize, value: T, flags: Flags) -> Result<(), AllocError> { 817 match new_len.checked_sub(self.len()) { 818 Some(n) => self.extend_with(n, value, flags), 819 None => { 820 self.truncate(new_len); 821 Ok(()) 822 } 823 } 824 } 825 } 826 827 impl<T, A> Drop for Vec<T, A> 828 where 829 A: Allocator, 830 { 831 fn drop(&mut self) { 832 // SAFETY: `self.as_mut_ptr` is guaranteed to be valid by the type invariant. 833 unsafe { 834 ptr::drop_in_place(core::ptr::slice_from_raw_parts_mut( 835 self.as_mut_ptr(), 836 self.len, 837 )) 838 }; 839 840 // SAFETY: 841 // - `self.ptr` was previously allocated with `A`. 842 // - `self.layout` matches the `ArrayLayout` of the preceding allocation. 843 unsafe { A::free(self.ptr.cast(), self.layout.into()) }; 844 } 845 } 846 847 impl<T, A, const N: usize> From<Box<[T; N], A>> for Vec<T, A> 848 where 849 A: Allocator, 850 { 851 fn from(b: Box<[T; N], A>) -> Vec<T, A> { 852 let len = b.len(); 853 let ptr = Box::into_raw(b); 854 855 // SAFETY: 856 // - `b` has been allocated with `A`, 857 // - `ptr` fulfills the alignment requirements for `T`, 858 // - `ptr` points to memory with at least a size of `size_of::<T>() * len`, 859 // - all elements within `b` are initialized values of `T`, 860 // - `len` does not exceed `isize::MAX`. 861 unsafe { Vec::from_raw_parts(ptr.cast(), len, len) } 862 } 863 } 864 865 impl<T, A: Allocator> Default for Vec<T, A> { 866 #[inline] 867 fn default() -> Self { 868 Self::new() 869 } 870 } 871 872 impl<T: fmt::Debug, A: Allocator> fmt::Debug for Vec<T, A> { 873 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 874 fmt::Debug::fmt(&**self, f) 875 } 876 } 877 878 impl<T, A> Deref for Vec<T, A> 879 where 880 A: Allocator, 881 { 882 type Target = [T]; 883 884 #[inline] 885 fn deref(&self) -> &[T] { 886 // SAFETY: The memory behind `self.as_ptr()` is guaranteed to contain `self.len` 887 // initialized elements of type `T`. 888 unsafe { slice::from_raw_parts(self.as_ptr(), self.len) } 889 } 890 } 891 892 impl<T, A> DerefMut for Vec<T, A> 893 where 894 A: Allocator, 895 { 896 #[inline] 897 fn deref_mut(&mut self) -> &mut [T] { 898 // SAFETY: The memory behind `self.as_ptr()` is guaranteed to contain `self.len` 899 // initialized elements of type `T`. 900 unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) } 901 } 902 } 903 904 /// # Examples 905 /// 906 /// ``` 907 /// # use core::borrow::Borrow; 908 /// struct Foo<B: Borrow<[u32]>>(B); 909 /// 910 /// // Owned array. 911 /// let owned_array = Foo([1, 2, 3]); 912 /// 913 /// // Owned vector. 914 /// let owned_vec = Foo(KVec::from_elem(0, 3, GFP_KERNEL)?); 915 /// 916 /// let arr = [1, 2, 3]; 917 /// // Borrowed slice from `arr`. 918 /// let borrowed_slice = Foo(&arr[..]); 919 /// # Ok::<(), Error>(()) 920 /// ``` 921 impl<T, A> Borrow<[T]> for Vec<T, A> 922 where 923 A: Allocator, 924 { 925 fn borrow(&self) -> &[T] { 926 self.as_slice() 927 } 928 } 929 930 /// # Examples 931 /// 932 /// ``` 933 /// # use core::borrow::BorrowMut; 934 /// struct Foo<B: BorrowMut<[u32]>>(B); 935 /// 936 /// // Owned array. 937 /// let owned_array = Foo([1, 2, 3]); 938 /// 939 /// // Owned vector. 940 /// let owned_vec = Foo(KVec::from_elem(0, 3, GFP_KERNEL)?); 941 /// 942 /// let mut arr = [1, 2, 3]; 943 /// // Borrowed slice from `arr`. 944 /// let borrowed_slice = Foo(&mut arr[..]); 945 /// # Ok::<(), Error>(()) 946 /// ``` 947 impl<T, A> BorrowMut<[T]> for Vec<T, A> 948 where 949 A: Allocator, 950 { 951 fn borrow_mut(&mut self) -> &mut [T] { 952 self.as_mut_slice() 953 } 954 } 955 956 impl<T: Eq, A> Eq for Vec<T, A> where A: Allocator {} 957 958 impl<T, I: SliceIndex<[T]>, A> Index<I> for Vec<T, A> 959 where 960 A: Allocator, 961 { 962 type Output = I::Output; 963 964 #[inline] 965 fn index(&self, index: I) -> &Self::Output { 966 Index::index(&**self, index) 967 } 968 } 969 970 impl<T, I: SliceIndex<[T]>, A> IndexMut<I> for Vec<T, A> 971 where 972 A: Allocator, 973 { 974 #[inline] 975 fn index_mut(&mut self, index: I) -> &mut Self::Output { 976 IndexMut::index_mut(&mut **self, index) 977 } 978 } 979 980 macro_rules! impl_slice_eq { 981 ($([$($vars:tt)*] $lhs:ty, $rhs:ty,)*) => { 982 $( 983 impl<T, U, $($vars)*> PartialEq<$rhs> for $lhs 984 where 985 T: PartialEq<U>, 986 { 987 #[inline] 988 fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] } 989 } 990 )* 991 } 992 } 993 994 impl_slice_eq! { 995 [A1: Allocator, A2: Allocator] Vec<T, A1>, Vec<U, A2>, 996 [A: Allocator] Vec<T, A>, &[U], 997 [A: Allocator] Vec<T, A>, &mut [U], 998 [A: Allocator] &[T], Vec<U, A>, 999 [A: Allocator] &mut [T], Vec<U, A>, 1000 [A: Allocator] Vec<T, A>, [U], 1001 [A: Allocator] [T], Vec<U, A>, 1002 [A: Allocator, const N: usize] Vec<T, A>, [U; N], 1003 [A: Allocator, const N: usize] Vec<T, A>, &[U; N], 1004 } 1005 1006 impl<'a, T, A> IntoIterator for &'a Vec<T, A> 1007 where 1008 A: Allocator, 1009 { 1010 type Item = &'a T; 1011 type IntoIter = slice::Iter<'a, T>; 1012 1013 fn into_iter(self) -> Self::IntoIter { 1014 self.iter() 1015 } 1016 } 1017 1018 impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A> 1019 where 1020 A: Allocator, 1021 { 1022 type Item = &'a mut T; 1023 type IntoIter = slice::IterMut<'a, T>; 1024 1025 fn into_iter(self) -> Self::IntoIter { 1026 self.iter_mut() 1027 } 1028 } 1029 1030 /// An [`Iterator`] implementation for [`Vec`] that moves elements out of a vector. 1031 /// 1032 /// This structure is created by the [`Vec::into_iter`] method on [`Vec`] (provided by the 1033 /// [`IntoIterator`] trait). 1034 /// 1035 /// # Examples 1036 /// 1037 /// ``` 1038 /// let v = kernel::kvec![0, 1, 2]?; 1039 /// let iter = v.into_iter(); 1040 /// 1041 /// # Ok::<(), Error>(()) 1042 /// ``` 1043 pub struct IntoIter<T, A: Allocator> { 1044 ptr: *mut T, 1045 buf: NonNull<T>, 1046 len: usize, 1047 layout: ArrayLayout<T>, 1048 _p: PhantomData<A>, 1049 } 1050 1051 impl<T, A> IntoIter<T, A> 1052 where 1053 A: Allocator, 1054 { 1055 fn into_raw_parts(self) -> (*mut T, NonNull<T>, usize, usize) { 1056 let me = ManuallyDrop::new(self); 1057 let ptr = me.ptr; 1058 let buf = me.buf; 1059 let len = me.len; 1060 let cap = me.layout.len(); 1061 (ptr, buf, len, cap) 1062 } 1063 1064 /// Same as `Iterator::collect` but specialized for `Vec`'s `IntoIter`. 1065 /// 1066 /// # Examples 1067 /// 1068 /// ``` 1069 /// let v = kernel::kvec![1, 2, 3]?; 1070 /// let mut it = v.into_iter(); 1071 /// 1072 /// assert_eq!(it.next(), Some(1)); 1073 /// 1074 /// let v = it.collect(GFP_KERNEL); 1075 /// assert_eq!(v, [2, 3]); 1076 /// 1077 /// # Ok::<(), Error>(()) 1078 /// ``` 1079 /// 1080 /// # Implementation details 1081 /// 1082 /// Currently, we can't implement `FromIterator`. There are a couple of issues with this trait 1083 /// in the kernel, namely: 1084 /// 1085 /// - Rust's specialization feature is unstable. This prevents us to optimize for the special 1086 /// case where `I::IntoIter` equals `Vec`'s `IntoIter` type. 1087 /// - We also can't use `I::IntoIter`'s type ID either to work around this, since `FromIterator` 1088 /// doesn't require this type to be `'static`. 1089 /// - `FromIterator::from_iter` does return `Self` instead of `Result<Self, AllocError>`, hence 1090 /// we can't properly handle allocation failures. 1091 /// - Neither `Iterator::collect` nor `FromIterator::from_iter` can handle additional allocation 1092 /// flags. 1093 /// 1094 /// Instead, provide `IntoIter::collect`, such that we can at least convert a `IntoIter` into a 1095 /// `Vec` again. 1096 /// 1097 /// Note that `IntoIter::collect` doesn't require `Flags`, since it re-uses the existing backing 1098 /// buffer. However, this backing buffer may be shrunk to the actual count of elements. 1099 pub fn collect(self, flags: Flags) -> Vec<T, A> { 1100 let old_layout = self.layout; 1101 let (mut ptr, buf, len, mut cap) = self.into_raw_parts(); 1102 let has_advanced = ptr != buf.as_ptr(); 1103 1104 if has_advanced { 1105 // Copy the contents we have advanced to at the beginning of the buffer. 1106 // 1107 // SAFETY: 1108 // - `ptr` is valid for reads of `len * size_of::<T>()` bytes, 1109 // - `buf.as_ptr()` is valid for writes of `len * size_of::<T>()` bytes, 1110 // - `ptr` and `buf.as_ptr()` are not be subject to aliasing restrictions relative to 1111 // each other, 1112 // - both `ptr` and `buf.ptr()` are properly aligned. 1113 unsafe { ptr::copy(ptr, buf.as_ptr(), len) }; 1114 ptr = buf.as_ptr(); 1115 1116 // SAFETY: `len` is guaranteed to be smaller than `self.layout.len()` by the type 1117 // invariant. 1118 let layout = unsafe { ArrayLayout::<T>::new_unchecked(len) }; 1119 1120 // SAFETY: `buf` points to the start of the backing buffer and `len` is guaranteed by 1121 // the type invariant to be smaller than `cap`. Depending on `realloc` this operation 1122 // may shrink the buffer or leave it as it is. 1123 ptr = match unsafe { 1124 A::realloc(Some(buf.cast()), layout.into(), old_layout.into(), flags) 1125 } { 1126 // If we fail to shrink, which likely can't even happen, continue with the existing 1127 // buffer. 1128 Err(_) => ptr, 1129 Ok(ptr) => { 1130 cap = len; 1131 ptr.as_ptr().cast() 1132 } 1133 }; 1134 } 1135 1136 // SAFETY: If the iterator has been advanced, the advanced elements have been copied to 1137 // the beginning of the buffer and `len` has been adjusted accordingly. 1138 // 1139 // - `ptr` is guaranteed to point to the start of the backing buffer. 1140 // - `cap` is either the original capacity or, after shrinking the buffer, equal to `len`. 1141 // - `alloc` is guaranteed to be unchanged since `into_iter` has been called on the original 1142 // `Vec`. 1143 unsafe { Vec::from_raw_parts(ptr, len, cap) } 1144 } 1145 } 1146 1147 impl<T, A> Iterator for IntoIter<T, A> 1148 where 1149 A: Allocator, 1150 { 1151 type Item = T; 1152 1153 /// # Examples 1154 /// 1155 /// ``` 1156 /// let v = kernel::kvec![1, 2, 3]?; 1157 /// let mut it = v.into_iter(); 1158 /// 1159 /// assert_eq!(it.next(), Some(1)); 1160 /// assert_eq!(it.next(), Some(2)); 1161 /// assert_eq!(it.next(), Some(3)); 1162 /// assert_eq!(it.next(), None); 1163 /// 1164 /// # Ok::<(), Error>(()) 1165 /// ``` 1166 fn next(&mut self) -> Option<T> { 1167 if self.len == 0 { 1168 return None; 1169 } 1170 1171 let current = self.ptr; 1172 1173 // SAFETY: We can't overflow; decreasing `self.len` by one every time we advance `self.ptr` 1174 // by one guarantees that. 1175 unsafe { self.ptr = self.ptr.add(1) }; 1176 1177 self.len -= 1; 1178 1179 // SAFETY: `current` is guaranteed to point at a valid element within the buffer. 1180 Some(unsafe { current.read() }) 1181 } 1182 1183 /// # Examples 1184 /// 1185 /// ``` 1186 /// let v: KVec<u32> = kernel::kvec![1, 2, 3]?; 1187 /// let mut iter = v.into_iter(); 1188 /// let size = iter.size_hint().0; 1189 /// 1190 /// iter.next(); 1191 /// assert_eq!(iter.size_hint().0, size - 1); 1192 /// 1193 /// iter.next(); 1194 /// assert_eq!(iter.size_hint().0, size - 2); 1195 /// 1196 /// iter.next(); 1197 /// assert_eq!(iter.size_hint().0, size - 3); 1198 /// 1199 /// # Ok::<(), Error>(()) 1200 /// ``` 1201 fn size_hint(&self) -> (usize, Option<usize>) { 1202 (self.len, Some(self.len)) 1203 } 1204 } 1205 1206 impl<T, A> Drop for IntoIter<T, A> 1207 where 1208 A: Allocator, 1209 { 1210 fn drop(&mut self) { 1211 // SAFETY: `self.ptr` is guaranteed to be valid by the type invariant. 1212 unsafe { ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.ptr, self.len)) }; 1213 1214 // SAFETY: 1215 // - `self.buf` was previously allocated with `A`. 1216 // - `self.layout` matches the `ArrayLayout` of the preceding allocation. 1217 unsafe { A::free(self.buf.cast(), self.layout.into()) }; 1218 } 1219 } 1220 1221 impl<T, A> IntoIterator for Vec<T, A> 1222 where 1223 A: Allocator, 1224 { 1225 type Item = T; 1226 type IntoIter = IntoIter<T, A>; 1227 1228 /// Consumes the `Vec<T, A>` and creates an `Iterator`, which moves each value out of the 1229 /// vector (from start to end). 1230 /// 1231 /// # Examples 1232 /// 1233 /// ``` 1234 /// let v = kernel::kvec![1, 2]?; 1235 /// let mut v_iter = v.into_iter(); 1236 /// 1237 /// let first_element: Option<u32> = v_iter.next(); 1238 /// 1239 /// assert_eq!(first_element, Some(1)); 1240 /// assert_eq!(v_iter.next(), Some(2)); 1241 /// assert_eq!(v_iter.next(), None); 1242 /// 1243 /// # Ok::<(), Error>(()) 1244 /// ``` 1245 /// 1246 /// ``` 1247 /// let v = kernel::kvec![]; 1248 /// let mut v_iter = v.into_iter(); 1249 /// 1250 /// let first_element: Option<u32> = v_iter.next(); 1251 /// 1252 /// assert_eq!(first_element, None); 1253 /// 1254 /// # Ok::<(), Error>(()) 1255 /// ``` 1256 #[inline] 1257 fn into_iter(self) -> Self::IntoIter { 1258 let buf = self.ptr; 1259 let layout = self.layout; 1260 let (ptr, len, _) = self.into_raw_parts(); 1261 1262 IntoIter { 1263 ptr, 1264 buf, 1265 len, 1266 layout, 1267 _p: PhantomData::<A>, 1268 } 1269 } 1270 } 1271 1272 /// An iterator that owns all items in a vector, but does not own its allocation. 1273 /// 1274 /// # Invariants 1275 /// 1276 /// Every `&mut T` returned by the iterator references a `T` that the iterator may take ownership 1277 /// of. 1278 pub struct DrainAll<'vec, T> { 1279 elements: slice::IterMut<'vec, T>, 1280 } 1281 1282 impl<'vec, T> Iterator for DrainAll<'vec, T> { 1283 type Item = T; 1284 1285 fn next(&mut self) -> Option<T> { 1286 let elem: *mut T = self.elements.next()?; 1287 // SAFETY: By the type invariants, we may take ownership of this value. 1288 Some(unsafe { elem.read() }) 1289 } 1290 1291 fn size_hint(&self) -> (usize, Option<usize>) { 1292 self.elements.size_hint() 1293 } 1294 } 1295 1296 impl<'vec, T> Drop for DrainAll<'vec, T> { 1297 fn drop(&mut self) { 1298 if core::mem::needs_drop::<T>() { 1299 let iter = core::mem::take(&mut self.elements); 1300 let ptr: *mut [T] = iter.into_slice(); 1301 // SAFETY: By the type invariants, we own these values so we may destroy them. 1302 unsafe { ptr::drop_in_place(ptr) }; 1303 } 1304 } 1305 } 1306 1307 #[macros::kunit_tests(rust_kvec)] 1308 mod tests { 1309 use super::*; 1310 use crate::prelude::*; 1311 1312 #[test] 1313 fn test_kvec_retain() { 1314 /// Verify correctness for one specific function. 1315 #[expect(clippy::needless_range_loop)] 1316 fn verify(c: &[bool]) { 1317 let mut vec1: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap(); 1318 let mut vec2: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap(); 1319 1320 for i in 0..c.len() { 1321 vec1.push_within_capacity(i).unwrap(); 1322 if c[i] { 1323 vec2.push_within_capacity(i).unwrap(); 1324 } 1325 } 1326 1327 vec1.retain(|i| c[*i]); 1328 1329 assert_eq!(vec1, vec2); 1330 } 1331 1332 /// Add one to a binary integer represented as a boolean array. 1333 fn add(value: &mut [bool]) { 1334 let mut carry = true; 1335 for v in value { 1336 let new_v = carry != *v; 1337 carry = carry && *v; 1338 *v = new_v; 1339 } 1340 } 1341 1342 // This boolean array represents a function from index to boolean. We check that `retain` 1343 // behaves correctly for all possible boolean arrays of every possible length less than 1344 // ten. 1345 let mut func = KVec::with_capacity(10, GFP_KERNEL).unwrap(); 1346 for len in 0..10 { 1347 for _ in 0u32..1u32 << len { 1348 verify(&func); 1349 add(&mut func); 1350 } 1351 func.push_within_capacity(false).unwrap(); 1352 } 1353 } 1354 } 1355