src/liballoc/raw_vec.rs

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