src/liballoc/raw_vec.rs

   1 #![unstable(feature = "raw_vec_internals", reason = "implementation detail", issue = "none")]
   2 #![doc(hidden)]
   3
   4 use core::cmp;
   5 use core::mem;
   6 use core::ops::Drop;
   7 use core::ptr::{self, NonNull, Unique};
   8 use core::slice;
   9
  10 use crate::alloc::{handle_alloc_error, AllocErr, AllocRef, Global, Layout};
  11 use crate::boxed::Box;
  12 use crate::collections::TryReserveError::{self, *};
  13
  14 #[cfg(test)]
  15 mod tests;
  16
  17 /// A low-level utility for more ergonomically allocating, reallocating, and deallocating
  18 /// a buffer of memory on the heap without having to worry about all the corner cases
  19 /// involved. This type is excellent for building your own data structures like Vec and VecDeque.
  20 /// In particular:
  21 ///
  22 /// * Produces `Unique::empty()` on zero-sized types.
  23 /// * Produces `Unique::empty()` on zero-length allocations.
  24 /// * Catches all overflows in capacity computations (promotes them to "capacity overflow" panics).
  25 /// * Guards against 32-bit systems allocating more than isize::MAX bytes.
  26 /// * Guards against overflowing your length.
  27 /// * Aborts on OOM or calls `handle_alloc_error` as applicable.
  28 /// * Avoids freeing `Unique::empty()`.
  29 /// * Contains a `ptr::Unique` and thus endows the user with all related benefits.
  30 ///
  31 /// This type does not in anyway inspect the memory that it manages. When dropped it *will*
  32 /// free its memory, but it *won't* try to drop its contents. It is up to the user of `RawVec`
  33 /// to handle the actual things *stored* inside of a `RawVec`.
  34 ///
  35 /// Note that a `RawVec` always forces its capacity to be `usize::MAX` for zero-sized types.
  36 /// This enables you to use capacity-growing logic catch the overflows in your length
  37 /// that might occur with zero-sized types.
  38 ///
  39 /// The above means that you need to be careful when round-tripping this type with a
  40 /// `Box<[T]>`, since `capacity()` won't yield the length. However, `with_capacity`,
  41 /// `shrink_to_fit`, and `from_box` will actually set `RawVec`'s private capacity
  42 /// field. This allows zero-sized types to not be special-cased by consumers of
  43 /// this type.
  44 #[allow(missing_debug_implementations)]
  45 pub struct RawVec<T, A: AllocRef = Global> {
  46     ptr: Unique<T>,
  47     cap: usize,
  48     a: A,
  49 }
  50
  51 impl<T, A: AllocRef> RawVec<T, A> {
  52     /// Like `new`, but parameterized over the choice of allocator for
  53     /// the returned `RawVec`.
  54     pub const fn new_in(a: A) -> Self {
  55         let cap = if mem::size_of::<T>() == 0 { core::usize::MAX } else { 0 };
  56
  57         // `Unique::empty()` doubles as "unallocated" and "zero-sized allocation".
  58         RawVec { ptr: Unique::empty(), cap, a }
  59     }
  60
  61     /// Like `with_capacity`, but parameterized over the choice of
  62     /// allocator for the returned `RawVec`.
  63     #[inline]
  64     pub fn with_capacity_in(capacity: usize, a: A) -> Self {
  65         RawVec::allocate_in(capacity, false, a)
  66     }
  67
  68     /// Like `with_capacity_zeroed`, but parameterized over the choice
  69     /// of allocator for the returned `RawVec`.
  70     #[inline]
  71     pub fn with_capacity_zeroed_in(capacity: usize, a: A) -> Self {
  72         RawVec::allocate_in(capacity, true, a)
  73     }
  74
  75     fn allocate_in(mut capacity: usize, zeroed: bool, mut a: A) -> Self {
  76         let elem_size = mem::size_of::<T>();
  77
  78         let alloc_size = capacity.checked_mul(elem_size).unwrap_or_else(|| capacity_overflow());
  79         alloc_guard(alloc_size).unwrap_or_else(|_| capacity_overflow());
  80
  81         // Handles ZSTs and `capacity == 0` alike.
  82         let ptr = if alloc_size == 0 {
  83             NonNull::<T>::dangling()
  84         } else {
  85             let align = mem::align_of::<T>();
  86             let layout = Layout::from_size_align(alloc_size, align).unwrap();
  87             let result = if zeroed { a.alloc_zeroed(layout) } else { a.alloc(layout) };
  88             match result {
  89                 Ok((ptr, size)) => {
  90                     capacity = size / elem_size;
  91                     ptr.cast()
  92                 }
  93                 Err(_) => handle_alloc_error(layout),
  94             }
  95         };
  96
  97         RawVec { ptr: ptr.into(), cap: capacity, a }
  98     }
  99 }
 100
 101 impl<T> RawVec<T, Global> {
 102     /// HACK(Centril): This exists because `#[unstable]` `const fn`s needn't conform
 103     /// to `min_const_fn` and so they cannot be called in `min_const_fn`s either.
 104     ///
 105     /// If you change `RawVec<T>::new` or dependencies, please take care to not
 106     /// introduce anything that would truly violate `min_const_fn`.
 107     ///
 108     /// NOTE: We could avoid this hack and check conformance with some
 109     /// `#[rustc_force_min_const_fn]` attribute which requires conformance
 110     /// with `min_const_fn` but does not necessarily allow calling it in
 111     /// `stable(...) const fn` / user code not enabling `foo` when
 112     /// `#[rustc_const_unstable(feature = "foo", ..)]` is present.
 113     pub const NEW: Self = Self::new();
 114
 115     /// Creates the biggest possible `RawVec` (on the system heap)
 116     /// without allocating. If `T` has positive size, then this makes a
 117     /// `RawVec` with capacity `0`. If `T` is zero-sized, then it makes a
 118     /// `RawVec` with capacity `usize::MAX`. Useful for implementing
 119     /// delayed allocation.
 120     pub const fn new() -> Self {
 121         Self::new_in(Global)
 122     }
 123
 124     /// Creates a `RawVec` (on the system heap) with exactly the
 125     /// capacity and alignment requirements for a `[T; capacity]`. This is
 126     /// equivalent to calling `RawVec::new` when `capacity` is `0` or `T` is
 127     /// zero-sized. Note that if `T` is zero-sized this means you will
 128     /// *not* get a `RawVec` with the requested capacity.
 129     ///
 130     /// # Panics
 131     ///
 132     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
 133     /// * Panics on 32-bit platforms if the requested capacity exceeds
 134     ///   `isize::MAX` bytes.
 135     ///
 136     /// # Aborts
 137     ///
 138     /// Aborts on OOM.
 139     #[inline]
 140     pub fn with_capacity(capacity: usize) -> Self {
 141         RawVec::allocate_in(capacity, false, Global)
 142     }
 143
 144     /// Like `with_capacity`, but guarantees the buffer is zeroed.
 145     #[inline]
 146     pub fn with_capacity_zeroed(capacity: usize) -> Self {
 147         RawVec::allocate_in(capacity, true, Global)
 148     }
 149 }
 150
 151 impl<T, A: AllocRef> RawVec<T, A> {
 152     /// Reconstitutes a `RawVec` from a pointer, capacity, and allocator.
 153     ///
 154     /// # Undefined Behavior
 155     ///
 156     /// The `ptr` must be allocated (via the given allocator `a`), and with the given `capacity`.
 157     /// The `capacity` cannot exceed `isize::MAX` (only a concern on 32-bit systems).
 158     /// If the `ptr` and `capacity` come from a `RawVec` created via `a`, then this is guaranteed.
 159     pub unsafe fn from_raw_parts_in(ptr: *mut T, capacity: usize, a: A) -> Self {
 160         RawVec { ptr: Unique::new_unchecked(ptr), cap: capacity, a }
 161     }
 162 }
 163
 164 impl<T> RawVec<T, Global> {
 165     /// Reconstitutes a `RawVec` from a pointer and capacity.
 166     ///
 167     /// # Undefined Behavior
 168     ///
 169     /// The `ptr` must be allocated (on the system heap), and with the given `capacity`.
 170     /// The `capacity` cannot exceed `isize::MAX` (only a concern on 32-bit systems).
 171     /// If the `ptr` and `capacity` come from a `RawVec`, then this is guaranteed.
 172     pub unsafe fn from_raw_parts(ptr: *mut T, capacity: usize) -> Self {
 173         RawVec { ptr: Unique::new_unchecked(ptr), cap: capacity, a: Global }
 174     }
 175
 176     /// Converts a `Box<[T]>` into a `RawVec<T>`.
 177     pub fn from_box(mut slice: Box<[T]>) -> Self {
 178         unsafe {
 179             let result = RawVec::from_raw_parts(slice.as_mut_ptr(), slice.len());
 180             mem::forget(slice);
 181             result
 182         }
 183     }
 184 }
 185
 186 impl<T, A: AllocRef> RawVec<T, A> {
 187     /// Gets a raw pointer to the start of the allocation. Note that this is
 188     /// `Unique::empty()` if `capacity == 0` or `T` is zero-sized. In the former case, you must
 189     /// be careful.
 190     pub fn ptr(&self) -> *mut T {
 191         self.ptr.as_ptr()
 192     }
 193
 194     /// Gets the capacity of the allocation.
 195     ///
 196     /// This will always be `usize::MAX` if `T` is zero-sized.
 197     #[inline(always)]
 198     pub fn capacity(&self) -> usize {
 199         if mem::size_of::<T>() == 0 { !0 } else { self.cap }
 200     }
 201
 202     /// Returns a shared reference to the allocator backing this `RawVec`.
 203     pub fn alloc(&self) -> &A {
 204         &self.a
 205     }
 206
 207     /// Returns a mutable reference to the allocator backing this `RawVec`.
 208     pub fn alloc_mut(&mut self) -> &mut A {
 209         &mut self.a
 210     }
 211
 212     fn current_layout(&self) -> Option<Layout> {
 213         if self.cap == 0 {
 214             None
 215         } else {
 216             // We have an allocated chunk of memory, so we can bypass runtime
 217             // checks to get our current layout.
 218             unsafe {
 219                 let align = mem::align_of::<T>();
 220                 let size = mem::size_of::<T>() * self.cap;
 221                 Some(Layout::from_size_align_unchecked(size, align))
 222             }
 223         }
 224     }
 225
 226     /// Doubles the size of the type's backing allocation. This is common enough
 227     /// to want to do that it's easiest to just have a dedicated method. Slightly
 228     /// more efficient logic can be provided for this than the general case.
 229     ///
 230     /// This function is ideal for when pushing elements one-at-a-time because
 231     /// you don't need to incur the costs of the more general computations
 232     /// reserve needs to do to guard against overflow. You do however need to
 233     /// manually check if your `len == capacity`.
 234     ///
 235     /// # Panics
 236     ///
 237     /// * Panics if `T` is zero-sized on the assumption that you managed to exhaust
 238     ///   all `usize::MAX` slots in your imaginary buffer.
 239     /// * Panics on 32-bit platforms if the requested capacity exceeds
 240     ///   `isize::MAX` bytes.
 241     ///
 242     /// # Aborts
 243     ///
 244     /// Aborts on OOM
 245     ///
 246     /// # Examples
 247     ///
 248     /// ```
 249     /// # #![feature(raw_vec_internals)]
 250     /// # extern crate alloc;
 251     /// # use std::ptr;
 252     /// # use alloc::raw_vec::RawVec;
 253     /// struct MyVec<T> {
 254     ///     buf: RawVec<T>,
 255     ///     len: usize,
 256     /// }
 257     ///
 258     /// impl<T> MyVec<T> {
 259     ///     pub fn push(&mut self, elem: T) {
 260     ///         if self.len == self.buf.capacity() { self.buf.double(); }
 261     ///         // double would have aborted or panicked if the len exceeded
 262     ///         // `isize::MAX` so this is safe to do unchecked now.
 263     ///         unsafe {
 264     ///             ptr::write(self.buf.ptr().add(self.len), elem);
 265     ///         }
 266     ///         self.len += 1;
 267     ///     }
 268     /// }
 269     /// # fn main() {
 270     /// #   let mut vec = MyVec { buf: RawVec::new(), len: 0 };
 271     /// #   vec.push(1);
 272     /// # }
 273     /// ```
 274     #[inline(never)]
 275     #[cold]
 276     pub fn double(&mut self) {
 277         unsafe {
 278             let elem_size = mem::size_of::<T>();
 279
 280             // Since we set the capacity to `usize::MAX` when `elem_size` is
 281             // 0, getting to here necessarily means the `RawVec` is overfull.
 282             assert!(elem_size != 0, "capacity overflow");
 283
 284             let (ptr, new_cap) = match self.current_layout() {
 285                 Some(cur) => {
 286                     // Since we guarantee that we never allocate more than
 287                     // `isize::MAX` bytes, `elem_size * self.cap <= isize::MAX` as
 288                     // a precondition, so this can't overflow. Additionally the
 289                     // alignment will never be too large as to "not be
 290                     // satisfiable", so `Layout::from_size_align` will always
 291                     // return `Some`.
 292                     //
 293                     // TL;DR, we bypass runtime checks due to dynamic assertions
 294                     // in this module, allowing us to use
 295                     // `from_size_align_unchecked`.
 296                     let new_cap = 2 * self.cap;
 297                     let new_size = new_cap * elem_size;
 298                     alloc_guard(new_size).unwrap_or_else(|_| capacity_overflow());
 299                     let ptr_res = self.a.realloc(NonNull::from(self.ptr).cast(), cur, new_size);
 300                     match ptr_res {
 301                         Ok((ptr, new_size)) => (ptr, new_size / elem_size),
 302                         Err(_) => handle_alloc_error(Layout::from_size_align_unchecked(
 303                             new_size,
 304                             cur.align(),
 305                         )),
 306                     }
 307                 }
 308                 None => {
 309                     // Skip to 4 because tiny `Vec`'s are dumb; but not if that
 310                     // would cause overflow.
 311                     let new_cap = if elem_size > (!0) / 8 { 1 } else { 4 };
 312                     let layout = Layout::array::<T>(new_cap).unwrap();
 313                     match self.a.alloc(layout) {
 314                         Ok((ptr, new_size)) => (ptr, new_size / elem_size),
 315                         Err(_) => handle_alloc_error(layout),
 316                     }
 317                 }
 318             };
 319             self.ptr = ptr.cast().into();
 320             self.cap = new_cap;
 321         }
 322     }
 323
 324     /// Attempts to double the size of the type's backing allocation in place. This is common
 325     /// enough to want to do that it's easiest to just have a dedicated method. Slightly
 326     /// more efficient logic can be provided for this than the general case.
 327     ///
 328     /// Returns `true` if the reallocation attempt has succeeded.
 329     ///
 330     /// # Panics
 331     ///
 332     /// * Panics if `T` is zero-sized on the assumption that you managed to exhaust
 333     ///   all `usize::MAX` slots in your imaginary buffer.
 334     /// * Panics on 32-bit platforms if the requested capacity exceeds
 335     ///   `isize::MAX` bytes.
 336     #[inline(never)]
 337     #[cold]
 338     pub fn double_in_place(&mut self) -> bool {
 339         unsafe {
 340             let elem_size = mem::size_of::<T>();
 341             let old_layout = match self.current_layout() {
 342                 Some(layout) => layout,
 343                 None => return false, // nothing to double
 344             };
 345
 346             // Since we set the capacity to `usize::MAX` when `elem_size` is
 347             // 0, getting to here necessarily means the `RawVec` is overfull.
 348             assert!(elem_size != 0, "capacity overflow");
 349
 350             // Since we guarantee that we never allocate more than `isize::MAX`
 351             // bytes, `elem_size * self.cap <= isize::MAX` as a precondition, so
 352             // this can't overflow.
 353             //
 354             // Similarly to with `double` above, we can go straight to
 355             // `Layout::from_size_align_unchecked` as we know this won't
 356             // overflow and the alignment is sufficiently small.
 357             let new_cap = 2 * self.cap;
 358             let new_size = new_cap * elem_size;
 359             alloc_guard(new_size).unwrap_or_else(|_| capacity_overflow());
 360             match self.a.grow_in_place(NonNull::from(self.ptr).cast(), old_layout, new_size) {
 361                 Ok(_) => {
 362                     // We can't directly divide `size`.
 363                     self.cap = new_cap;
 364                     true
 365                 }
 366                 Err(_) => false,
 367             }
 368         }
 369     }
 370
 371     /// The same as `reserve_exact`, but returns on errors instead of panicking or aborting.
 372     pub fn try_reserve_exact(
 373         &mut self,
 374         used_capacity: usize,
 375         needed_extra_capacity: usize,
 376     ) -> Result<(), TryReserveError> {
 377         self.reserve_internal(used_capacity, needed_extra_capacity, Fallible, Exact)
 378     }
 379
 380     /// Ensures that the buffer contains at least enough space to hold
 381     /// `used_capacity + needed_extra_capacity` elements. If it doesn't already,
 382     /// will reallocate the minimum possible amount of memory necessary.
 383     /// Generally this will be exactly the amount of memory necessary,
 384     /// but in principle the allocator is free to give back more than
 385     /// we asked for.
 386     ///
 387     /// If `used_capacity` exceeds `self.capacity()`, this may fail to actually allocate
 388     /// the requested space. This is not really unsafe, but the unsafe
 389     /// code *you* write that relies on the behavior of this function may break.
 390     ///
 391     /// # Panics
 392     ///
 393     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
 394     /// * Panics on 32-bit platforms if the requested capacity exceeds
 395     ///   `isize::MAX` bytes.
 396     ///
 397     /// # Aborts
 398     ///
 399     /// Aborts on OOM.
 400     pub fn reserve_exact(&mut self, used_capacity: usize, needed_extra_capacity: usize) {
 401         match self.reserve_internal(used_capacity, needed_extra_capacity, Infallible, Exact) {
 402             Err(CapacityOverflow) => capacity_overflow(),
 403             Err(AllocError { .. }) => unreachable!(),
 404             Ok(()) => { /* yay */ }
 405         }
 406     }
 407
 408     /// Calculates the buffer's new size given that it'll hold `used_capacity +
 409     /// needed_extra_capacity` elements. This logic is used in amortized reserve methods.
 410     /// Returns `(new_capacity, new_alloc_size)`.
 411     fn amortized_new_size(
 412         &self,
 413         used_capacity: usize,
 414         needed_extra_capacity: usize,
 415     ) -> Result<usize, TryReserveError> {
 416         // Nothing we can really do about these checks, sadly.
 417         let required_cap =
 418             used_capacity.checked_add(needed_extra_capacity).ok_or(CapacityOverflow)?;
 419         // Cannot overflow, because `cap <= isize::MAX`, and type of `cap` is `usize`.
 420         let double_cap = self.cap * 2;
 421         // `double_cap` guarantees exponential growth.
 422         Ok(cmp::max(double_cap, required_cap))
 423     }
 424
 425     /// The same as `reserve`, but returns on errors instead of panicking or aborting.
 426     pub fn try_reserve(
 427         &mut self,
 428         used_capacity: usize,
 429         needed_extra_capacity: usize,
 430     ) -> Result<(), TryReserveError> {
 431         self.reserve_internal(used_capacity, needed_extra_capacity, Fallible, Amortized)
 432     }
 433
 434     /// Ensures that the buffer contains at least enough space to hold
 435     /// `used_capacity + needed_extra_capacity` elements. If it doesn't already have
 436     /// enough capacity, will reallocate enough space plus comfortable slack
 437     /// space to get amortized `O(1)` behavior. Will limit this behavior
 438     /// if it would needlessly cause itself to panic.
 439     ///
 440     /// If `used_capacity` exceeds `self.capacity()`, this may fail to actually allocate
 441     /// the requested space. This is not really unsafe, but the unsafe
 442     /// code *you* write that relies on the behavior of this function may break.
 443     ///
 444     /// This is ideal for implementing a bulk-push operation like `extend`.
 445     ///
 446     /// # Panics
 447     ///
 448     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
 449     /// * Panics on 32-bit platforms if the requested capacity exceeds
 450     ///   `isize::MAX` bytes.
 451     ///
 452     /// # Aborts
 453     ///
 454     /// Aborts on OOM.
 455     ///
 456     /// # Examples
 457     ///
 458     /// ```
 459     /// # #![feature(raw_vec_internals)]
 460     /// # extern crate alloc;
 461     /// # use std::ptr;
 462     /// # use alloc::raw_vec::RawVec;
 463     /// struct MyVec<T> {
 464     ///     buf: RawVec<T>,
 465     ///     len: usize,
 466     /// }
 467     ///
 468     /// impl<T: Clone> MyVec<T> {
 469     ///     pub fn push_all(&mut self, elems: &[T]) {
 470     ///         self.buf.reserve(self.len, elems.len());
 471     ///         // reserve would have aborted or panicked if the len exceeded
 472     ///         // `isize::MAX` so this is safe to do unchecked now.
 473     ///         for x in elems {
 474     ///             unsafe {
 475     ///                 ptr::write(self.buf.ptr().add(self.len), x.clone());
 476     ///             }
 477     ///             self.len += 1;
 478     ///         }
 479     ///     }
 480     /// }
 481     /// # fn main() {
 482     /// #   let mut vector = MyVec { buf: RawVec::new(), len: 0 };
 483     /// #   vector.push_all(&[1, 3, 5, 7, 9]);
 484     /// # }
 485     /// ```
 486     pub fn reserve(&mut self, used_capacity: usize, needed_extra_capacity: usize) {
 487         match self.reserve_internal(used_capacity, needed_extra_capacity, Infallible, Amortized) {
 488             Err(CapacityOverflow) => capacity_overflow(),
 489             Err(AllocError { .. }) => unreachable!(),
 490             Ok(()) => { /* yay */ }
 491         }
 492     }
 493     /// Attempts to ensure that the buffer contains at least enough space to hold
 494     /// `used_capacity + needed_extra_capacity` elements. If it doesn't already have
 495     /// enough capacity, will reallocate in place enough space plus comfortable slack
 496     /// space to get amortized `O(1)` behavior. Will limit this behaviour
 497     /// if it would needlessly cause itself to panic.
 498     ///
 499     /// If `used_capacity` exceeds `self.capacity()`, this may fail to actually allocate
 500     /// the requested space. This is not really unsafe, but the unsafe
 501     /// code *you* write that relies on the behavior of this function may break.
 502     ///
 503     /// Returns `true` if the reallocation attempt has succeeded.
 504     ///
 505     /// # Panics
 506     ///
 507     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
 508     /// * Panics on 32-bit platforms if the requested capacity exceeds
 509     ///   `isize::MAX` bytes.
 510     pub fn reserve_in_place(&mut self, used_capacity: usize, needed_extra_capacity: usize) -> bool {
 511         unsafe {
 512             // NOTE: we don't early branch on ZSTs here because we want this
 513             // to actually catch "asking for more than usize::MAX" in that case.
 514             // If we make it past the first branch then we are guaranteed to
 515             // panic.
 516
 517             // Don't actually need any more capacity. If the current `cap` is 0, we can't
 518             // reallocate in place.
 519             // Wrapping in case they give a bad `used_capacity`
 520             let old_layout = match self.current_layout() {
 521                 Some(layout) => layout,
 522                 None => return false,
 523             };
 524             if self.capacity().wrapping_sub(used_capacity) >= needed_extra_capacity {
 525                 return false;
 526             }
 527
 528             let new_cap = self
 529                 .amortized_new_size(used_capacity, needed_extra_capacity)
 530                 .unwrap_or_else(|_| capacity_overflow());
 531
 532             // Here, `cap < used_capacity + needed_extra_capacity <= new_cap`
 533             // (regardless of whether `self.cap - used_capacity` wrapped).
 534             // Therefore, we can safely call `grow_in_place`.
 535
 536             let new_layout = Layout::new::<T>().repeat(new_cap).unwrap().0;
 537             // FIXME: may crash and burn on over-reserve
 538             alloc_guard(new_layout.size()).unwrap_or_else(|_| capacity_overflow());
 539             match self.a.grow_in_place(
 540                 NonNull::from(self.ptr).cast(),
 541                 old_layout,
 542                 new_layout.size(),
 543             ) {
 544                 Ok(_) => {
 545                     self.cap = new_cap;
 546                     true
 547                 }
 548                 Err(_) => false,
 549             }
 550         }
 551     }
 552
 553     /// Shrinks the allocation down to the specified amount. If the given amount
 554     /// is 0, actually completely deallocates.
 555     ///
 556     /// # Panics
 557     ///
 558     /// Panics if the given amount is *larger* than the current capacity.
 559     ///
 560     /// # Aborts
 561     ///
 562     /// Aborts on OOM.
 563     pub fn shrink_to_fit(&mut self, amount: usize) {
 564         let elem_size = mem::size_of::<T>();
 565
 566         // Set the `cap` because they might be about to promote to a `Box<[T]>`
 567         if elem_size == 0 {
 568             self.cap = amount;
 569             return;
 570         }
 571
 572         // This check is my waterloo; it's the only thing `Vec` wouldn't have to do.
 573         assert!(self.cap >= amount, "Tried to shrink to a larger capacity");
 574
 575         if amount == 0 {
 576             // We want to create a new zero-length vector within the
 577             // same allocator. We use `ptr::write` to avoid an
 578             // erroneous attempt to drop the contents, and we use
 579             // `ptr::read` to sidestep condition against destructuring
 580             // types that implement Drop.
 581
 582             unsafe {
 583                 let a = ptr::read(&self.a as *const A);
 584                 self.dealloc_buffer();
 585                 ptr::write(self, RawVec::new_in(a));
 586             }
 587         } else if self.cap != amount {
 588             unsafe {
 589                 // We know here that our `amount` is greater than zero. This
 590                 // implies, via the assert above, that capacity is also greater
 591                 // than zero, which means that we've got a current layout that
 592                 // "fits"
 593                 //
 594                 // We also know that `self.cap` is greater than `amount`, and
 595                 // consequently we don't need runtime checks for creating either
 596                 // layout.
 597                 let old_size = elem_size * self.cap;
 598                 let new_size = elem_size * amount;
 599                 let align = mem::align_of::<T>();
 600                 let old_layout = Layout::from_size_align_unchecked(old_size, align);
 601                 match self.a.realloc(NonNull::from(self.ptr).cast(), old_layout, new_size) {
 602                     Ok((ptr, _)) => self.ptr = ptr.cast().into(),
 603                     Err(_) => {
 604                         handle_alloc_error(Layout::from_size_align_unchecked(new_size, align))
 605                     }
 606                 }
 607             }
 608             self.cap = amount;
 609         }
 610     }
 611 }
 612
 613 enum Fallibility {
 614     Fallible,
 615     Infallible,
 616 }
 617
 618 use Fallibility::*;
 619
 620 enum ReserveStrategy {
 621     Exact,
 622     Amortized,
 623 }
 624
 625 use ReserveStrategy::*;
 626
 627 impl<T, A: AllocRef> RawVec<T, A> {
 628     fn reserve_internal(
 629         &mut self,
 630         used_capacity: usize,
 631         needed_extra_capacity: usize,
 632         fallibility: Fallibility,
 633         strategy: ReserveStrategy,
 634     ) -> Result<(), TryReserveError> {
 635         let elem_size = mem::size_of::<T>();
 636
 637         unsafe {
 638             // NOTE: we don't early branch on ZSTs here because we want this
 639             // to actually catch "asking for more than usize::MAX" in that case.
 640             // If we make it past the first branch then we are guaranteed to
 641             // panic.
 642
 643             // Don't actually need any more capacity.
 644             // Wrapping in case they gave a bad `used_capacity`.
 645             if self.capacity().wrapping_sub(used_capacity) >= needed_extra_capacity {
 646                 return Ok(());
 647             }
 648
 649             // Nothing we can really do about these checks, sadly.
 650             let new_cap = match strategy {
 651                 Exact => {
 652                     used_capacity.checked_add(needed_extra_capacity).ok_or(CapacityOverflow)?
 653                 }
 654                 Amortized => self.amortized_new_size(used_capacity, needed_extra_capacity)?,
 655             };
 656             let new_layout = Layout::array::<T>(new_cap).map_err(|_| CapacityOverflow)?;
 657
 658             alloc_guard(new_layout.size())?;
 659
 660             let res = match self.current_layout() {
 661                 Some(layout) => {
 662                     debug_assert!(new_layout.align() == layout.align());
 663                     self.a.realloc(NonNull::from(self.ptr).cast(), layout, new_layout.size())
 664                 }
 665                 None => self.a.alloc(new_layout),
 666             };
 667
 668             let (ptr, new_cap) = match (res, fallibility) {
 669                 (Err(AllocErr), Infallible) => handle_alloc_error(new_layout),
 670                 (Err(AllocErr), Fallible) => {
 671                     return Err(TryReserveError::AllocError {
 672                         layout: new_layout,
 673                         non_exhaustive: (),
 674                     });
 675                 }
 676                 (Ok((ptr, new_size)), _) => (ptr, new_size / elem_size),
 677             };
 678
 679             self.ptr = ptr.cast().into();
 680             self.cap = new_cap;
 681
 682             Ok(())
 683         }
 684     }
 685 }
 686
 687 impl<T> RawVec<T, Global> {
 688     /// Converts the entire buffer into `Box<[T]>`.
 689     ///
 690     /// Note that this will correctly reconstitute any `cap` changes
 691     /// that may have been performed. (See description of type for details.)
 692     ///
 693     /// # Undefined Behavior
 694     ///
 695     /// All elements of `RawVec<T, Global>` must be initialized. Notice that
 696     /// the rules around uninitialized boxed values are not finalized yet,
 697     /// but until they are, it is advisable to avoid them.
 698     pub unsafe fn into_box(self) -> Box<[T]> {
 699         // NOTE: not calling `capacity()` here; actually using the real `cap` field!
 700         let slice = slice::from_raw_parts_mut(self.ptr(), self.cap);
 701         let output: Box<[T]> = Box::from_raw(slice);
 702         mem::forget(self);
 703         output
 704     }
 705 }
 706
 707 impl<T, A: AllocRef> RawVec<T, A> {
 708     /// Frees the memory owned by the `RawVec` *without* trying to drop its contents.
 709     pub unsafe fn dealloc_buffer(&mut self) {
 710         let elem_size = mem::size_of::<T>();
 711         if elem_size != 0 {
 712             if let Some(layout) = self.current_layout() {
 713                 self.a.dealloc(NonNull::from(self.ptr).cast(), layout);
 714             }
 715         }
 716     }
 717 }
 718
 719 unsafe impl<#[may_dangle] T, A: AllocRef> Drop for RawVec<T, A> {
 720     /// Frees the memory owned by the `RawVec` *without* trying to drop its contents.
 721     fn drop(&mut self) {
 722         unsafe {
 723             self.dealloc_buffer();
 724         }
 725     }
 726 }
 727
 728 // We need to guarantee the following:
 729 // * We don't ever allocate `> isize::MAX` byte-size objects.
 730 // * We don't overflow `usize::MAX` and actually allocate too little.
 731 //
 732 // On 64-bit we just need to check for overflow since trying to allocate
 733 // `> isize::MAX` bytes will surely fail. On 32-bit and 16-bit we need to add
 734 // an extra guard for this in case we're running on a platform which can use
 735 // all 4GB in user-space, e.g., PAE or x32.
 736
 737 #[inline]
 738 fn alloc_guard(alloc_size: usize) -> Result<(), TryReserveError> {
 739     if mem::size_of::<usize>() < 8 && alloc_size > core::isize::MAX as usize {
 740         Err(CapacityOverflow)
 741     } else {
 742         Ok(())
 743     }
 744 }
 745
 746 // One central function responsible for reporting capacity overflows. This'll
 747 // ensure that the code generation related to these panics is minimal as there's
 748 // only one location which panics rather than a bunch throughout the module.
 749 fn capacity_overflow() -> ! {
 750     panic!("capacity overflow");
 751 }