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