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