src/liballoc/raw_vec.rs

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