src/liballoc/raw_vec.rs

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