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(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: AllocRef> 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: AllocRef> 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, ptr) = 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),
 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                     let layout = Layout::array::<T>(new_cap).unwrap();
 312                     match self.a.alloc(layout) {
 313                         Ok(ptr) => (new_cap, ptr),
 314                         Err(_) => handle_alloc_error(layout),
 315                     }
 316                 }
 317             };
 318             self.ptr = ptr.cast().into();
 319             self.cap = new_cap;
 320         }
 321     }
 322
 323     /// Attempts to double the size of the type's backing allocation in place. This is common
 324     /// enough to want to do that it's easiest to just have a dedicated method. Slightly
 325     /// more efficient logic can be provided for this than the general case.
 326     ///
 327     /// Returns `true` if the reallocation attempt has succeeded.
 328     ///
 329     /// # Panics
 330     ///
 331     /// * Panics if `T` is zero-sized on the assumption that you managed to exhaust
 332     ///   all `usize::MAX` slots in your imaginary buffer.
 333     /// * Panics on 32-bit platforms if the requested capacity exceeds
 334     ///   `isize::MAX` bytes.
 335     #[inline(never)]
 336     #[cold]
 337     pub fn double_in_place(&mut self) -> bool {
 338         unsafe {
 339             let elem_size = mem::size_of::<T>();
 340             let old_layout = match self.current_layout() {
 341                 Some(layout) => layout,
 342                 None => return false, // nothing to double
 343             };
 344
 345             // Since we set the capacity to `usize::MAX` when `elem_size` is
 346             // 0, getting to here necessarily means the `RawVec` is overfull.
 347             assert!(elem_size != 0, "capacity overflow");
 348
 349             // Since we guarantee that we never allocate more than `isize::MAX`
 350             // bytes, `elem_size * self.cap <= isize::MAX` as a precondition, so
 351             // this can't overflow.
 352             //
 353             // Similarly to with `double` above, we can go straight to
 354             // `Layout::from_size_align_unchecked` as we know this won't
 355             // overflow and the alignment is sufficiently small.
 356             let new_cap = 2 * self.cap;
 357             let new_size = new_cap * elem_size;
 358             alloc_guard(new_size).unwrap_or_else(|_| capacity_overflow());
 359             match self.a.grow_in_place(NonNull::from(self.ptr).cast(), old_layout, new_size) {
 360                 Ok(_) => {
 361                     // We can't directly divide `size`.
 362                     self.cap = new_cap;
 363                     true
 364                 }
 365                 Err(_) => false,
 366             }
 367         }
 368     }
 369
 370     /// The same as `reserve_exact`, but returns on errors instead of panicking or aborting.
 371     pub fn try_reserve_exact(
 372         &mut self,
 373         used_capacity: usize,
 374         needed_extra_capacity: usize,
 375     ) -> Result<(), TryReserveError> {
 376         self.reserve_internal(used_capacity, needed_extra_capacity, Fallible, Exact)
 377     }
 378
 379     /// Ensures that the buffer contains at least enough space to hold
 380     /// `used_capacity + needed_extra_capacity` elements. If it doesn't already,
 381     /// will reallocate the minimum possible amount of memory necessary.
 382     /// Generally this will be exactly the amount of memory necessary,
 383     /// but in principle the allocator is free to give back more than
 384     /// we asked for.
 385     ///
 386     /// If `used_capacity` exceeds `self.capacity()`, this may fail to actually allocate
 387     /// the requested space. This is not really unsafe, but the unsafe
 388     /// code *you* write that relies on the behavior of this function may break.
 389     ///
 390     /// # Panics
 391     ///
 392     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
 393     /// * Panics on 32-bit platforms if the requested capacity exceeds
 394     ///   `isize::MAX` bytes.
 395     ///
 396     /// # Aborts
 397     ///
 398     /// Aborts on OOM.
 399     pub fn reserve_exact(&mut self, used_capacity: usize, needed_extra_capacity: usize) {
 400         match self.reserve_internal(used_capacity, needed_extra_capacity, Infallible, Exact) {
 401             Err(CapacityOverflow) => capacity_overflow(),
 402             Err(AllocError { .. }) => unreachable!(),
 403             Ok(()) => { /* yay */ }
 404         }
 405     }
 406
 407     /// Calculates the buffer's new size given that it'll hold `used_capacity +
 408     /// needed_extra_capacity` elements. This logic is used in amortized reserve methods.
 409     /// Returns `(new_capacity, new_alloc_size)`.
 410     fn amortized_new_size(
 411         &self,
 412         used_capacity: usize,
 413         needed_extra_capacity: usize,
 414     ) -> Result<usize, TryReserveError> {
 415         // Nothing we can really do about these checks, sadly.
 416         let required_cap =
 417             used_capacity.checked_add(needed_extra_capacity).ok_or(CapacityOverflow)?;
 418         // Cannot overflow, because `cap <= isize::MAX`, and type of `cap` is `usize`.
 419         let double_cap = self.cap * 2;
 420         // `double_cap` guarantees exponential growth.
 421         Ok(cmp::max(double_cap, required_cap))
 422     }
 423
 424     /// The same as `reserve`, but returns on errors instead of panicking or aborting.
 425     pub fn try_reserve(
 426         &mut self,
 427         used_capacity: usize,
 428         needed_extra_capacity: usize,
 429     ) -> Result<(), TryReserveError> {
 430         self.reserve_internal(used_capacity, needed_extra_capacity, Fallible, Amortized)
 431     }
 432
 433     /// Ensures that the buffer contains at least enough space to hold
 434     /// `used_capacity + needed_extra_capacity` elements. If it doesn't already have
 435     /// enough capacity, will reallocate enough space plus comfortable slack
 436     /// space to get amortized `O(1)` behavior. Will limit this behavior
 437     /// if it would needlessly cause itself to panic.
 438     ///
 439     /// If `used_capacity` exceeds `self.capacity()`, this may fail to actually allocate
 440     /// the requested space. This is not really unsafe, but the unsafe
 441     /// code *you* write that relies on the behavior of this function may break.
 442     ///
 443     /// This is ideal for implementing a bulk-push operation like `extend`.
 444     ///
 445     /// # Panics
 446     ///
 447     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
 448     /// * Panics on 32-bit platforms if the requested capacity exceeds
 449     ///   `isize::MAX` bytes.
 450     ///
 451     /// # Aborts
 452     ///
 453     /// Aborts on OOM.
 454     ///
 455     /// # Examples
 456     ///
 457     /// ```
 458     /// # #![feature(raw_vec_internals)]
 459     /// # extern crate alloc;
 460     /// # use std::ptr;
 461     /// # use alloc::raw_vec::RawVec;
 462     /// struct MyVec<T> {
 463     ///     buf: RawVec<T>,
 464     ///     len: usize,
 465     /// }
 466     ///
 467     /// impl<T: Clone> MyVec<T> {
 468     ///     pub fn push_all(&mut self, elems: &[T]) {
 469     ///         self.buf.reserve(self.len, elems.len());
 470     ///         // reserve would have aborted or panicked if the len exceeded
 471     ///         // `isize::MAX` so this is safe to do unchecked now.
 472     ///         for x in elems {
 473     ///             unsafe {
 474     ///                 ptr::write(self.buf.ptr().add(self.len), x.clone());
 475     ///             }
 476     ///             self.len += 1;
 477     ///         }
 478     ///     }
 479     /// }
 480     /// # fn main() {
 481     /// #   let mut vector = MyVec { buf: RawVec::new(), len: 0 };
 482     /// #   vector.push_all(&[1, 3, 5, 7, 9]);
 483     /// # }
 484     /// ```
 485     pub fn reserve(&mut self, used_capacity: usize, needed_extra_capacity: usize) {
 486         match self.reserve_internal(used_capacity, needed_extra_capacity, Infallible, Amortized) {
 487             Err(CapacityOverflow) => capacity_overflow(),
 488             Err(AllocError { .. }) => unreachable!(),
 489             Ok(()) => { /* yay */ }
 490         }
 491     }
 492     /// Attempts to ensure that the buffer contains at least enough space to hold
 493     /// `used_capacity + needed_extra_capacity` elements. If it doesn't already have
 494     /// enough capacity, will reallocate in place enough space plus comfortable slack
 495     /// space to get amortized `O(1)` behavior. Will limit this behaviour
 496     /// if it would needlessly cause itself to panic.
 497     ///
 498     /// If `used_capacity` exceeds `self.capacity()`, this may fail to actually allocate
 499     /// the requested space. This is not really unsafe, but the unsafe
 500     /// code *you* write that relies on the behavior of this function may break.
 501     ///
 502     /// Returns `true` if the reallocation attempt has succeeded.
 503     ///
 504     /// # Panics
 505     ///
 506     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
 507     /// * Panics on 32-bit platforms if the requested capacity exceeds
 508     ///   `isize::MAX` bytes.
 509     pub fn reserve_in_place(&mut self, used_capacity: usize, needed_extra_capacity: usize) -> bool {
 510         unsafe {
 511             // NOTE: we don't early branch on ZSTs here because we want this
 512             // to actually catch "asking for more than usize::MAX" in that case.
 513             // If we make it past the first branch then we are guaranteed to
 514             // panic.
 515
 516             // Don't actually need any more capacity. If the current `cap` is 0, we can't
 517             // reallocate in place.
 518             // Wrapping in case they give a bad `used_capacity`
 519             let old_layout = match self.current_layout() {
 520                 Some(layout) => layout,
 521                 None => return false,
 522             };
 523             if self.capacity().wrapping_sub(used_capacity) >= needed_extra_capacity {
 524                 return false;
 525             }
 526
 527             let new_cap = self
 528                 .amortized_new_size(used_capacity, needed_extra_capacity)
 529                 .unwrap_or_else(|_| capacity_overflow());
 530
 531             // Here, `cap < used_capacity + needed_extra_capacity <= new_cap`
 532             // (regardless of whether `self.cap - used_capacity` wrapped).
 533             // Therefore, we can safely call `grow_in_place`.
 534
 535             let new_layout = Layout::new::<T>().repeat(new_cap).unwrap().0;
 536             // FIXME: may crash and burn on over-reserve
 537             alloc_guard(new_layout.size()).unwrap_or_else(|_| capacity_overflow());
 538             match self.a.grow_in_place(
 539                 NonNull::from(self.ptr).cast(),
 540                 old_layout,
 541                 new_layout.size(),
 542             ) {
 543                 Ok(_) => {
 544                     self.cap = new_cap;
 545                     true
 546                 }
 547                 Err(_) => false,
 548             }
 549         }
 550     }
 551
 552     /// Shrinks the allocation down to the specified amount. If the given amount
 553     /// is 0, actually completely deallocates.
 554     ///
 555     /// # Panics
 556     ///
 557     /// Panics if the given amount is *larger* than the current capacity.
 558     ///
 559     /// # Aborts
 560     ///
 561     /// Aborts on OOM.
 562     pub fn shrink_to_fit(&mut self, amount: usize) {
 563         let elem_size = mem::size_of::<T>();
 564
 565         // Set the `cap` because they might be about to promote to a `Box<[T]>`
 566         if elem_size == 0 {
 567             self.cap = amount;
 568             return;
 569         }
 570
 571         // This check is my waterloo; it's the only thing `Vec` wouldn't have to do.
 572         assert!(self.cap >= amount, "Tried to shrink to a larger capacity");
 573
 574         if amount == 0 {
 575             // We want to create a new zero-length vector within the
 576             // same allocator. We use `ptr::write` to avoid an
 577             // erroneous attempt to drop the contents, and we use
 578             // `ptr::read` to sidestep condition against destructuring
 579             // types that implement Drop.
 580
 581             unsafe {
 582                 let a = ptr::read(&self.a as *const A);
 583                 self.dealloc_buffer();
 584                 ptr::write(self, RawVec::new_in(a));
 585             }
 586         } else if self.cap != amount {
 587             unsafe {
 588                 // We know here that our `amount` is greater than zero. This
 589                 // implies, via the assert above, that capacity is also greater
 590                 // than zero, which means that we've got a current layout that
 591                 // "fits"
 592                 //
 593                 // We also know that `self.cap` is greater than `amount`, and
 594                 // consequently we don't need runtime checks for creating either
 595                 // layout.
 596                 let old_size = elem_size * self.cap;
 597                 let new_size = elem_size * amount;
 598                 let align = mem::align_of::<T>();
 599                 let old_layout = Layout::from_size_align_unchecked(old_size, align);
 600                 match self.a.realloc(NonNull::from(self.ptr).cast(), old_layout, new_size) {
 601                     Ok(p) => self.ptr = p.cast().into(),
 602                     Err(_) => {
 603                         handle_alloc_error(Layout::from_size_align_unchecked(new_size, align))
 604                     }
 605                 }
 606             }
 607             self.cap = amount;
 608         }
 609     }
 610 }
 611
 612 enum Fallibility {
 613     Fallible,
 614     Infallible,
 615 }
 616
 617 use Fallibility::*;
 618
 619 enum ReserveStrategy {
 620     Exact,
 621     Amortized,
 622 }
 623
 624 use ReserveStrategy::*;
 625
 626 impl<T, A: AllocRef> RawVec<T, A> {
 627     fn reserve_internal(
 628         &mut self,
 629         used_capacity: usize,
 630         needed_extra_capacity: usize,
 631         fallibility: Fallibility,
 632         strategy: ReserveStrategy,
 633     ) -> Result<(), TryReserveError> {
 634         unsafe {
 635             // NOTE: we don't early branch on ZSTs here because we want this
 636             // to actually catch "asking for more than usize::MAX" in that case.
 637             // If we make it past the first branch then we are guaranteed to
 638             // panic.
 639
 640             // Don't actually need any more capacity.
 641             // Wrapping in case they gave a bad `used_capacity`.
 642             if self.capacity().wrapping_sub(used_capacity) >= needed_extra_capacity {
 643                 return Ok(());
 644             }
 645
 646             // Nothing we can really do about these checks, sadly.
 647             let new_cap = match strategy {
 648                 Exact => {
 649                     used_capacity.checked_add(needed_extra_capacity).ok_or(CapacityOverflow)?
 650                 }
 651                 Amortized => self.amortized_new_size(used_capacity, needed_extra_capacity)?,
 652             };
 653             let new_layout = Layout::array::<T>(new_cap).map_err(|_| CapacityOverflow)?;
 654
 655             alloc_guard(new_layout.size())?;
 656
 657             let res = match self.current_layout() {
 658                 Some(layout) => {
 659                     debug_assert!(new_layout.align() == layout.align());
 660                     self.a.realloc(NonNull::from(self.ptr).cast(), layout, new_layout.size())
 661                 }
 662                 None => self.a.alloc(new_layout),
 663             };
 664
 665             let ptr = match (res, fallibility) {
 666                 (Err(AllocErr), Infallible) => handle_alloc_error(new_layout),
 667                 (Err(AllocErr), Fallible) => {
 668                     return Err(TryReserveError::AllocError {
 669                         layout: new_layout,
 670                         non_exhaustive: (),
 671                     });
 672                 }
 673                 (Ok(ptr), _) => ptr,
 674             };
 675
 676             self.ptr = ptr.cast().into();
 677             self.cap = new_cap;
 678
 679             Ok(())
 680         }
 681     }
 682 }
 683
 684 impl<T> RawVec<T, Global> {
 685     /// Converts the entire buffer into `Box<[T]>`.
 686     ///
 687     /// Note that this will correctly reconstitute any `cap` changes
 688     /// that may have been performed. (See description of type for details.)
 689     ///
 690     /// # Undefined Behavior
 691     ///
 692     /// All elements of `RawVec<T, Global>` must be initialized. Notice that
 693     /// the rules around uninitialized boxed values are not finalized yet,
 694     /// but until they are, it is advisable to avoid them.
 695     pub unsafe fn into_box(self) -> Box<[T]> {
 696         // NOTE: not calling `capacity()` here; actually using the real `cap` field!
 697         let slice = slice::from_raw_parts_mut(self.ptr(), self.cap);
 698         let output: Box<[T]> = Box::from_raw(slice);
 699         mem::forget(self);
 700         output
 701     }
 702 }
 703
 704 impl<T, A: AllocRef> RawVec<T, A> {
 705     /// Frees the memory owned by the `RawVec` *without* trying to drop its contents.
 706     pub unsafe fn dealloc_buffer(&mut self) {
 707         let elem_size = mem::size_of::<T>();
 708         if elem_size != 0 {
 709             if let Some(layout) = self.current_layout() {
 710                 self.a.dealloc(NonNull::from(self.ptr).cast(), layout);
 711             }
 712         }
 713     }
 714 }
 715
 716 unsafe impl<#[may_dangle] T, A: AllocRef> Drop for RawVec<T, A> {
 717     /// Frees the memory owned by the `RawVec` *without* trying to drop its contents.
 718     fn drop(&mut self) {
 719         unsafe {
 720             self.dealloc_buffer();
 721         }
 722     }
 723 }
 724
 725 // We need to guarantee the following:
 726 // * We don't ever allocate `> isize::MAX` byte-size objects.
 727 // * We don't overflow `usize::MAX` and actually allocate too little.
 728 //
 729 // On 64-bit we just need to check for overflow since trying to allocate
 730 // `> isize::MAX` bytes will surely fail. On 32-bit and 16-bit we need to add
 731 // an extra guard for this in case we're running on a platform which can use
 732 // all 4GB in user-space, e.g., PAE or x32.
 733
 734 #[inline]
 735 fn alloc_guard(alloc_size: usize) -> Result<(), TryReserveError> {
 736     if mem::size_of::<usize>() < 8 && alloc_size > core::isize::MAX as usize {
 737         Err(CapacityOverflow)
 738     } else {
 739         Ok(())
 740     }
 741 }
 742
 743 // One central function responsible for reporting capacity overflows. This'll
 744 // ensure that the code generation related to these panics is minimal as there's
 745 // only one location which panics rather than a bunch throughout the module.
 746 fn capacity_overflow() -> ! {
 747     panic!("capacity overflow");
 748 }