src/liballoc/raw_vec.rs - third_party/rust - Git at Google

 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
 // file at the top-level directory of this distribution and at
 // http://rust-lang.org/COPYRIGHT.
 //
 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.

 use core::ptr::Unique;
 use core::mem;
 use core::slice;
 use heap;
 use super::oom;
 use super::boxed::Box;
 use core::ops::Drop;
 use core::cmp;

 /// A low-level utility for more ergonomically allocating, reallocating, and deallocating a
 /// a buffer of memory on the heap without having to worry about all the corner cases
 /// involved. This type is excellent for building your own data structures like Vec and VecDeque.
 /// In particular:
 ///
 /// * Produces heap::EMPTY on zero-sized types
 /// * Produces heap::EMPTY on zero-length allocations
 /// * Catches all overflows in capacity computations (promotes them to "capacity overflow" panics)
 /// * Guards against 32-bit systems allocating more than isize::MAX bytes
 /// * Guards against overflowing your length
 /// * Aborts on OOM
 /// * Avoids freeing heap::EMPTY
 /// * Contains a ptr::Unique and thus endows the user with all related benefits
 ///
 /// This type does not in anyway inspect the memory that it manages. When dropped it *will*
 /// free its memory, but it *won't* try to Drop its contents. It is up to the user of RawVec
 /// to handle the actual things *stored* inside of a RawVec.
 ///
 /// Note that a RawVec always forces its capacity to be usize::MAX for zero-sized types.
 /// This enables you to use capacity growing logic catch the overflows in your length
 /// that might occur with zero-sized types.
 ///
 /// However this means that you need to be careful when roundtripping this type
 /// with a `Box<[T]>`: `cap()` won't yield the len. However `with_capacity`,
 /// `shrink_to_fit`, and `from_box` will actually set RawVec's private capacity
 /// field. This allows zero-sized types to not be special-cased by consumers of
 /// this type.
 #[unsafe_no_drop_flag]
 pub struct RawVec<T> {
     ptr: Unique<T>,
     cap: usize,
 }

 impl<T> RawVec<T> {
     /// Creates the biggest possible RawVec without allocating. If T has positive
     /// size, then this makes a RawVec with capacity 0. If T has 0 size, then it
     /// it makes a RawVec with capacity `usize::MAX`. Useful for implementing
     /// delayed allocation.
     pub fn new() -> Self {
         unsafe {
             // !0 is usize::MAX. This branch should be stripped at compile time.
             let cap = if mem::size_of::<T>() == 0 {
                 !0
             } else {
                 0
             };

             // heap::EMPTY doubles as "unallocated" and "zero-sized allocation"
             RawVec {
                 ptr: Unique::new(heap::EMPTY as *mut T),
                 cap: cap,
             }
         }
     }

     /// Creates a RawVec with exactly the capacity and alignment requirements
     /// for a `[T; cap]`. This is equivalent to calling RawVec::new when `cap` is 0
     /// or T is zero-sized. Note that if `T` is zero-sized this means you will *not*
     /// get a RawVec with the requested capacity!
     ///
     /// # Panics
     ///
     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
     /// * Panics on 32-bit platforms if the requested capacity exceeds
     ///   `isize::MAX` bytes.
     ///
     /// # Aborts
     ///
     /// Aborts on OOM
     pub fn with_capacity(cap: usize) -> Self {
         unsafe {
             let elem_size = mem::size_of::<T>();

             let alloc_size = cap.checked_mul(elem_size).expect("capacity overflow");
             alloc_guard(alloc_size);

             // handles ZSTs and `cap = 0` alike
             let ptr = if alloc_size == 0 {
                 heap::EMPTY as *mut u8
             } else {
                 let align = mem::align_of::<T>();
                 let ptr = heap::allocate(alloc_size, align);
                 if ptr.is_null() {
                     oom()
                 }
                 ptr
             };

             RawVec {
                 ptr: Unique::new(ptr as *mut _),
                 cap: cap,
             }
         }
     }

     /// Reconstitutes a RawVec from a pointer and capacity.
     ///
     /// # Undefined Behavior
     ///
     /// The ptr must be allocated, and with the given capacity. The
     /// capacity cannot exceed `isize::MAX` (only a concern on 32-bit systems).
     /// If the ptr and capacity come from a RawVec, then this is guaranteed.
     pub unsafe fn from_raw_parts(ptr: *mut T, cap: usize) -> Self {
         RawVec {
             ptr: Unique::new(ptr),
             cap: cap,
         }
     }

     /// Converts a `Box<[T]>` into a `RawVec<T>`.
     pub fn from_box(mut slice: Box<[T]>) -> Self {
         unsafe {
             let result = RawVec::from_raw_parts(slice.as_mut_ptr(), slice.len());
             mem::forget(slice);
             result
         }
     }
 }

 impl<T> RawVec<T> {
     /// Gets a raw pointer to the start of the allocation. Note that this is
     /// heap::EMPTY if `cap = 0` or T is zero-sized. In the former case, you must
     /// be careful.
     pub fn ptr(&self) -> *mut T {
         *self.ptr
     }

     /// Gets the capacity of the allocation.
     ///
     /// This will always be `usize::MAX` if `T` is zero-sized.
     #[inline(always)]
     pub fn cap(&self) -> usize {
         if mem::size_of::<T>() == 0 {
             !0
         } else {
             self.cap
         }
     }

     /// Doubles the size of the type's backing allocation. This is common enough
     /// to want to do that it's easiest to just have a dedicated method. Slightly
     /// more efficient logic can be provided for this than the general case.
     ///
     /// This function is ideal for when pushing elements one-at-a-time because
     /// you don't need to incur the costs of the more general computations
     /// reserve needs to do to guard against overflow. You do however need to
     /// manually check if your `len == cap`.
     ///
     /// # Panics
     ///
     /// * Panics if T is zero-sized on the assumption that you managed to exhaust
     ///   all `usize::MAX` slots in your imaginary buffer.
     /// * Panics on 32-bit platforms if the requested capacity exceeds
     ///   `isize::MAX` bytes.
     ///
     /// # Aborts
     ///
     /// Aborts on OOM
     ///
     /// # Examples
     ///
     /// ```ignore
     /// struct MyVec<T> {
     ///     buf: RawVec<T>,
     ///     len: usize,
     /// }
     ///
     /// impl<T> MyVec<T> {
     ///     pub fn push(&mut self, elem: T) {
     ///         if self.len == self.buf.cap() { self.buf.double(); }
     ///         // double would have aborted or panicked if the len exceeded
     ///         // `isize::MAX` so this is safe to do unchecked now.
     ///         unsafe {
     ///             ptr::write(self.buf.ptr().offset(self.len as isize), elem);
     ///         }
     ///         self.len += 1;
     ///     }
     /// }
     /// ```
     #[inline(never)]
     #[cold]
     pub fn double(&mut self) {
         unsafe {
             let elem_size = mem::size_of::<T>();

             // since we set the capacity to usize::MAX when elem_size is
             // 0, getting to here necessarily means the RawVec is overfull.
             assert!(elem_size != 0, "capacity overflow");

             let align = mem::align_of::<T>();

             let (new_cap, ptr) = if self.cap == 0 {
                 // skip to 4 because tiny Vec's are dumb; but not if that would cause overflow
                 let new_cap = if elem_size > (!0) / 8 {
                     1
                 } else {
                     4
                 };
                 let ptr = heap::allocate(new_cap * elem_size, align);
                 (new_cap, ptr)
             } else {
                 // Since we guarantee that we never allocate more than isize::MAX bytes,
                 // `elem_size * self.cap <= isize::MAX` as a precondition, so this can't overflow
                 let new_cap = 2 * self.cap;
                 let new_alloc_size = new_cap * elem_size;
                 alloc_guard(new_alloc_size);
                 let ptr = heap::reallocate(self.ptr() as *mut _,
                                            self.cap * elem_size,
                                            new_alloc_size,
                                            align);
                 (new_cap, ptr)
             };

             // If allocate or reallocate fail, we'll get `null` back
             if ptr.is_null() {
                 oom()
             }

             self.ptr = Unique::new(ptr as *mut _);
             self.cap = new_cap;
         }
     }

     /// Attempts to double the size of the type's backing allocation in place. This is common
     /// enough to want to do that it's easiest to just have a dedicated method. Slightly
     /// more efficient logic can be provided for this than the general case.
     ///
     /// Returns true if the reallocation attempt has succeeded, or false otherwise.
     ///
     /// # Panics
     ///
     /// * Panics if T is zero-sized on the assumption that you managed to exhaust
     ///   all `usize::MAX` slots in your imaginary buffer.
     /// * Panics on 32-bit platforms if the requested capacity exceeds
     ///   `isize::MAX` bytes.
     #[inline(never)]
     #[cold]
     pub fn double_in_place(&mut self) -> bool {
         unsafe {
             let elem_size = mem::size_of::<T>();
             let align = mem::align_of::<T>();

             // since we set the capacity to usize::MAX when elem_size is
             // 0, getting to here necessarily means the RawVec is overfull.
             assert!(elem_size != 0, "capacity overflow");

             // Since we guarantee that we never allocate more than isize::MAX bytes,
             // `elem_size * self.cap <= isize::MAX` as a precondition, so this can't overflow
             let new_cap = 2 * self.cap;
             let new_alloc_size = new_cap * elem_size;

             alloc_guard(new_alloc_size);
             let size = heap::reallocate_inplace(self.ptr() as *mut _,
                                                 self.cap * elem_size,
                                                 new_alloc_size,
                                                 align);
             if size >= new_alloc_size {
                 // We can't directly divide `size`.
                 self.cap = new_cap;
             }
             size >= new_alloc_size
         }
     }

     /// Ensures that the buffer contains at least enough space to hold
     /// `used_cap + needed_extra_cap` elements. If it doesn't already,
     /// will reallocate the minimum possible amount of memory necessary.
     /// Generally this will be exactly the amount of memory necessary,
     /// but in principle the allocator is free to give back more than
     /// we asked for.
     ///
     /// If `used_cap` exceeds `self.cap()`, this may fail to actually allocate
     /// the requested space. This is not really unsafe, but the unsafe
     /// code *you* write that relies on the behavior of this function may break.
     ///
     /// # Panics
     ///
     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
     /// * Panics on 32-bit platforms if the requested capacity exceeds
     ///   `isize::MAX` bytes.
     ///
     /// # Aborts
     ///
     /// Aborts on OOM
     pub fn reserve_exact(&mut self, used_cap: usize, needed_extra_cap: usize) {
         unsafe {
             let elem_size = mem::size_of::<T>();
             let align = mem::align_of::<T>();

             // NOTE: we don't early branch on ZSTs here because we want this
             // to actually catch "asking for more than usize::MAX" in that case.
             // If we make it past the first branch then we are guaranteed to
             // panic.

             // Don't actually need any more capacity.
             // Wrapping in case they gave a bad `used_cap`.
             if self.cap().wrapping_sub(used_cap) >= needed_extra_cap {
                 return;
             }

             // Nothing we can really do about these checks :(
             let new_cap = used_cap.checked_add(needed_extra_cap).expect("capacity overflow");
             let new_alloc_size = new_cap.checked_mul(elem_size).expect("capacity overflow");
             alloc_guard(new_alloc_size);

             let ptr = if self.cap == 0 {
                 heap::allocate(new_alloc_size, align)
             } else {
                 heap::reallocate(self.ptr() as *mut _,
                                  self.cap * elem_size,
                                  new_alloc_size,
                                  align)
             };

             // If allocate or reallocate fail, we'll get `null` back
             if ptr.is_null() {
                 oom()
             }

             self.ptr = Unique::new(ptr as *mut _);
             self.cap = new_cap;
         }
     }

     /// Calculates the buffer's new size given that it'll hold `used_cap +
     /// needed_extra_cap` elements. This logic is used in amortized reserve methods.
     /// Returns `(new_capacity, new_alloc_size)`.
     fn amortized_new_size(&self, used_cap: usize, needed_extra_cap: usize) -> (usize, usize) {
         let elem_size = mem::size_of::<T>();
         // Nothing we can really do about these checks :(
         let required_cap = used_cap.checked_add(needed_extra_cap)
                                    .expect("capacity overflow");
         // Cannot overflow, because `cap <= isize::MAX`, and type of `cap` is `usize`.
         let double_cap = self.cap * 2;
         // `double_cap` guarantees exponential growth.
         let new_cap = cmp::max(double_cap, required_cap);
         let new_alloc_size = new_cap.checked_mul(elem_size).expect("capacity overflow");
         (new_cap, new_alloc_size)
     }

     /// Ensures that the buffer contains at least enough space to hold
     /// `used_cap + needed_extra_cap` elements. If it doesn't already have
     /// enough capacity, will reallocate enough space plus comfortable slack
     /// space to get amortized `O(1)` behavior. Will limit this behavior
     /// if it would needlessly cause itself to panic.
     ///
     /// If `used_cap` exceeds `self.cap()`, this may fail to actually allocate
     /// the requested space. This is not really unsafe, but the unsafe
     /// code *you* write that relies on the behavior of this function may break.
     ///
     /// This is ideal for implementing a bulk-push operation like `extend`.
     ///
     /// # Panics
     ///
     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
     /// * Panics on 32-bit platforms if the requested capacity exceeds
     ///   `isize::MAX` bytes.
     ///
     /// # Aborts
     ///
     /// Aborts on OOM
     ///
     /// # Examples
     ///
     /// ```ignore
     /// struct MyVec<T> {
     ///     buf: RawVec<T>,
     ///     len: usize,
     /// }
     ///
     /// impl<T> MyVec<T> {
     ///     pub fn push_all(&mut self, elems: &[T]) {
     ///         self.buf.reserve(self.len, elems.len());
     ///         // reserve would have aborted or panicked if the len exceeded
     ///         // `isize::MAX` so this is safe to do unchecked now.
     ///         for x in elems {
     ///             unsafe {
     ///                 ptr::write(self.buf.ptr().offset(self.len as isize), x.clone());
     ///             }
     ///             self.len += 1;
     ///         }
     ///     }
     /// }
     /// ```
     pub fn reserve(&mut self, used_cap: usize, needed_extra_cap: usize) {
         unsafe {
             let elem_size = mem::size_of::<T>();
             let align = mem::align_of::<T>();

             // NOTE: we don't early branch on ZSTs here because we want this
             // to actually catch "asking for more than usize::MAX" in that case.
             // If we make it past the first branch then we are guaranteed to
             // panic.

             // Don't actually need any more capacity.
             // Wrapping in case they give a bad `used_cap`
             if self.cap().wrapping_sub(used_cap) >= needed_extra_cap {
                 return;
             }

             let (new_cap, new_alloc_size) = self.amortized_new_size(used_cap, needed_extra_cap);
             // FIXME: may crash and burn on over-reserve
             alloc_guard(new_alloc_size);

             let ptr = if self.cap == 0 {
                 heap::allocate(new_alloc_size, align)
             } else {
                 heap::reallocate(self.ptr() as *mut _,
                                  self.cap * elem_size,
                                  new_alloc_size,
                                  align)
             };

             // If allocate or reallocate fail, we'll get `null` back
             if ptr.is_null() {
                 oom()
             }

             self.ptr = Unique::new(ptr as *mut _);
             self.cap = new_cap;
         }
     }

     /// Attempts to ensure that the buffer contains at least enough space to hold
     /// `used_cap + needed_extra_cap` elements. If it doesn't already have
     /// enough capacity, will reallocate in place enough space plus comfortable slack
     /// space to get amortized `O(1)` behaviour. Will limit this behaviour
     /// if it would needlessly cause itself to panic.
     ///
     /// If `used_cap` exceeds `self.cap()`, this may fail to actually allocate
     /// the requested space. This is not really unsafe, but the unsafe
     /// code *you* write that relies on the behaviour of this function may break.
     ///
     /// Returns true if the reallocation attempt has succeeded, or false otherwise.
     ///
     /// # Panics
     ///
     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
     /// * Panics on 32-bit platforms if the requested capacity exceeds
     ///   `isize::MAX` bytes.
     pub fn reserve_in_place(&mut self, used_cap: usize, needed_extra_cap: usize) -> bool {
         unsafe {
             let elem_size = mem::size_of::<T>();
             let align = mem::align_of::<T>();

             // NOTE: we don't early branch on ZSTs here because we want this
             // to actually catch "asking for more than usize::MAX" in that case.
             // If we make it past the first branch then we are guaranteed to
             // panic.

             // Don't actually need any more capacity. If the current `cap` is 0, we can't
             // reallocate in place.
             // Wrapping in case they give a bad `used_cap`
             if self.cap().wrapping_sub(used_cap) >= needed_extra_cap || self.cap == 0 {
                 return false;
             }

             let (_, new_alloc_size) = self.amortized_new_size(used_cap, needed_extra_cap);
             // FIXME: may crash and burn on over-reserve
             alloc_guard(new_alloc_size);

             let size = heap::reallocate_inplace(self.ptr() as *mut _,
                                                 self.cap * elem_size,
                                                 new_alloc_size,
                                                 align);
             if size >= new_alloc_size {
                 self.cap = new_alloc_size / elem_size;
             }
             size >= new_alloc_size
         }
     }

     /// Shrinks the allocation down to the specified amount. If the given amount
     /// is 0, actually completely deallocates.
     ///
     /// # Panics
     ///
     /// Panics if the given amount is *larger* than the current capacity.
     ///
     /// # Aborts
     ///
     /// Aborts on OOM.
     pub fn shrink_to_fit(&mut self, amount: usize) {
         let elem_size = mem::size_of::<T>();
         let align = mem::align_of::<T>();

         // Set the `cap` because they might be about to promote to a `Box<[T]>`
         if elem_size == 0 {
             self.cap = amount;
             return;
         }

         // This check is my waterloo; it's the only thing Vec wouldn't have to do.
         assert!(self.cap >= amount, "Tried to shrink to a larger capacity");

         if amount == 0 {
             mem::replace(self, RawVec::new());
         } else if self.cap != amount {
             unsafe {
                 // Overflow check is unnecessary as the vector is already at
                 // least this large.
                 let ptr = heap::reallocate(self.ptr() as *mut _,
                                            self.cap * elem_size,
                                            amount * elem_size,
                                            align);
                 if ptr.is_null() {
                     oom()
                 }
                 self.ptr = Unique::new(ptr as *mut _);
             }
             self.cap = amount;
         }
     }

     /// Converts the entire buffer into `Box<[T]>`.
     ///
     /// While it is not *strictly* Undefined Behavior to call
     /// this procedure while some of the RawVec is unintialized,
     /// it cetainly makes it trivial to trigger it.
     ///
     /// Note that this will correctly reconstitute any `cap` changes
     /// that may have been performed. (see description of type for details)
     pub unsafe fn into_box(self) -> Box<[T]> {
         // NOTE: not calling `cap()` here, actually using the real `cap` field!
         let slice = slice::from_raw_parts_mut(self.ptr(), self.cap);
         let output: Box<[T]> = Box::from_raw(slice);
         mem::forget(self);
         output
     }

     /// This is a stupid name in the hopes that someone will find this in the
     /// not too distant future and remove it with the rest of
     /// #[unsafe_no_drop_flag]
     pub fn unsafe_no_drop_flag_needs_drop(&self) -> bool {
         self.cap != mem::POST_DROP_USIZE
     }
 }

 impl<T> Drop for RawVec<T> {
     #[unsafe_destructor_blind_to_params]
     /// Frees the memory owned by the RawVec *without* trying to Drop its contents.
     fn drop(&mut self) {
         let elem_size = mem::size_of::<T>();
         if elem_size != 0 && self.cap != 0 && self.unsafe_no_drop_flag_needs_drop() {
             let align = mem::align_of::<T>();

             let num_bytes = elem_size * self.cap;
             unsafe {
                 heap::deallocate(*self.ptr as *mut _, num_bytes, align);
             }
         }
     }
 }


 // We need to guarantee the following:
 // * We don't ever allocate `> isize::MAX` byte-size objects
 // * We don't overflow `usize::MAX` and actually allocate too little
 //
 // On 64-bit we just need to check for overflow since trying to allocate
 // `> isize::MAX` bytes will surely fail. On 32-bit and 16-bit we need to add
 // an extra guard for this in case we're running on a platform which can use
 // all 4GB in user-space. e.g. PAE or x32

 #[inline]
 fn alloc_guard(alloc_size: usize) {
     if mem::size_of::<usize>() < 8 {
         assert!(alloc_size <= ::core::isize::MAX as usize,
                 "capacity overflow");
     }
 }


 #[cfg(test)]
 mod tests {
     use super::*;

     #[test]
     fn reserve_does_not_overallocate() {
         {
             let mut v: RawVec<u32> = RawVec::new();
             // First `reserve` allocates like `reserve_exact`
             v.reserve(0, 9);
             assert_eq!(9, v.cap());
         }

         {
             let mut v: RawVec<u32> = RawVec::new();
             v.reserve(0, 7);
             assert_eq!(7, v.cap());
             // 97 if more than double of 7, so `reserve` should work
             // like `reserve_exact`.
             v.reserve(7, 90);
             assert_eq!(97, v.cap());
         }

         {
             let mut v: RawVec<u32> = RawVec::new();
             v.reserve(0, 12);
             assert_eq!(12, v.cap());
             v.reserve(12, 3);
             // 3 is less than half of 12, so `reserve` must grow
             // exponentially. At the time of writing this test grow
             // factor is 2, so new capacity is 24, however, grow factor
             // of 1.5 is OK too. Hence `>= 18` in assert.
             assert!(v.cap() >= 12 + 12 / 2);
         }
     }

 }
	// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
	// file at the top-level directory of this distribution and at
	// http://rust-lang.org/COPYRIGHT.
	//
	// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
	// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
	// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
	// option. This file may not be copied, modified, or distributed
	// except according to those terms.

	use core::ptr::Unique;
	use core::mem;
	use core::slice;
	use heap;
	use super::oom;
	use super::boxed::Box;
	use core::ops::Drop;
	use core::cmp;

	/// A low-level utility for more ergonomically allocating, reallocating, and deallocating a
	/// a buffer of memory on the heap without having to worry about all the corner cases
	/// involved. This type is excellent for building your own data structures like Vec and VecDeque.
	/// In particular:
	///
	/// * Produces heap::EMPTY on zero-sized types
	/// * Produces heap::EMPTY on zero-length allocations
	/// * Catches all overflows in capacity computations (promotes them to "capacity overflow" panics)
	/// * Guards against 32-bit systems allocating more than isize::MAX bytes
	/// * Guards against overflowing your length
	/// * Aborts on OOM
	/// * Avoids freeing heap::EMPTY
	/// * Contains a ptr::Unique and thus endows the user with all related benefits
	///
	/// This type does not in anyway inspect the memory that it manages. When dropped it will
	/// free its memory, but it won't try to Drop its contents. It is up to the user of RawVec
	/// to handle the actual things stored inside of a RawVec.
	///
	/// Note that a RawVec always forces its capacity to be usize::MAX for zero-sized types.
	/// This enables you to use capacity growing logic catch the overflows in your length
	/// that might occur with zero-sized types.
	///
	/// However this means that you need to be careful when roundtripping this type
	/// with a `Box<[T]>`: `cap()` won't yield the len. However `with_capacity`,
	/// `shrink_to_fit`, and `from_box` will actually set RawVec's private capacity
	/// field. This allows zero-sized types to not be special-cased by consumers of
	/// this type.
	#[unsafe_no_drop_flag]
	pub struct RawVec<T> {
	ptr: Unique<T>,
	cap: usize,
	}

	impl<T> RawVec<T> {
	/// Creates the biggest possible RawVec without allocating. If T has positive
	/// size, then this makes a RawVec with capacity 0. If T has 0 size, then it
	/// it makes a RawVec with capacity `usize::MAX`. Useful for implementing
	/// delayed allocation.
	pub fn new() -> Self {
	unsafe {
	// !0 is usize::MAX. This branch should be stripped at compile time.
	let cap = if mem::size_of::<T>() == 0 {
	!0
	} else {
	0
	};

	// heap::EMPTY doubles as "unallocated" and "zero-sized allocation"
	RawVec {
	ptr: Unique::new(heap::EMPTY as *mut T),
	cap: cap,
	}
	}
	}

	/// Creates a RawVec with exactly the capacity and alignment requirements
	/// for a `[T; cap]`. This is equivalent to calling RawVec::new when `cap` is 0
	/// or T is zero-sized. Note that if `T` is zero-sized this means you will not
	/// get a RawVec with the requested capacity!
	///
	/// # Panics
	///
	/// * Panics if the requested capacity exceeds `usize::MAX` bytes.
	/// * Panics on 32-bit platforms if the requested capacity exceeds
	/// `isize::MAX` bytes.
	///
	/// # Aborts
	///
	/// Aborts on OOM
	pub fn with_capacity(cap: usize) -> Self {
	unsafe {
	let elem_size = mem::size_of::<T>();

	let alloc_size = cap.checked_mul(elem_size).expect("capacity overflow");
	alloc_guard(alloc_size);

	// handles ZSTs and `cap = 0` alike
	let ptr = if alloc_size == 0 {
	heap::EMPTY as *mut u8
	} else {
	let align = mem::align_of::<T>();
	let ptr = heap::allocate(alloc_size, align);
	if ptr.is_null() {
	oom()
	}
	ptr
	};

	RawVec {
	ptr: Unique::new(ptr as *mut _),
	cap: cap,
	}
	}
	}

	/// Reconstitutes a RawVec from a pointer and capacity.
	///
	/// # Undefined Behavior
	///
	/// The ptr must be allocated, and with the given capacity. The
	/// capacity cannot exceed `isize::MAX` (only a concern on 32-bit systems).
	/// If the ptr and capacity come from a RawVec, then this is guaranteed.
	pub unsafe fn from_raw_parts(ptr: *mut T, cap: usize) -> Self {
	RawVec {
	ptr: Unique::new(ptr),
	cap: cap,
	}
	}

	/// Converts a `Box<[T]>` into a `RawVec<T>`.
	pub fn from_box(mut slice: Box<[T]>) -> Self {
	unsafe {
	let result = RawVec::from_raw_parts(slice.as_mut_ptr(), slice.len());
	mem::forget(slice);
	result
	}
	}
	}

	impl<T> RawVec<T> {
	/// Gets a raw pointer to the start of the allocation. Note that this is
	/// heap::EMPTY if `cap = 0` or T is zero-sized. In the former case, you must
	/// be careful.
	pub fn ptr(&self) -> *mut T {
	*self.ptr
	}

	/// Gets the capacity of the allocation.
	///
	/// This will always be `usize::MAX` if `T` is zero-sized.
	#[inline(always)]
	pub fn cap(&self) -> usize {
	if mem::size_of::<T>() == 0 {
	!0
	} else {
	self.cap
	}
	}

	/// Doubles the size of the type's backing allocation. This is common enough
	/// to want to do that it's easiest to just have a dedicated method. Slightly
	/// more efficient logic can be provided for this than the general case.
	///
	/// This function is ideal for when pushing elements one-at-a-time because
	/// you don't need to incur the costs of the more general computations
	/// reserve needs to do to guard against overflow. You do however need to
	/// manually check if your `len == cap`.
	///
	/// # Panics
	///
	/// * Panics if T is zero-sized on the assumption that you managed to exhaust
	/// all `usize::MAX` slots in your imaginary buffer.
	/// * Panics on 32-bit platforms if the requested capacity exceeds
	/// `isize::MAX` bytes.
	///
	/// # Aborts
	///
	/// Aborts on OOM
	///
	/// # Examples
	///
	/// ```ignore
	/// struct MyVec<T> {
	/// buf: RawVec<T>,
	/// len: usize,
	/// }
	///
	/// impl<T> MyVec<T> {
	/// pub fn push(&mut self, elem: T) {
	/// if self.len == self.buf.cap() { self.buf.double(); }
	/// // double would have aborted or panicked if the len exceeded
	/// // `isize::MAX` so this is safe to do unchecked now.
	/// unsafe {
	/// ptr::write(self.buf.ptr().offset(self.len as isize), elem);
	/// }
	/// self.len += 1;
	/// }
	/// }
	/// ```
	#[inline(never)]
	#[cold]
	pub fn double(&mut self) {
	unsafe {
	let elem_size = mem::size_of::<T>();

	// since we set the capacity to usize::MAX when elem_size is
	// 0, getting to here necessarily means the RawVec is overfull.
	assert!(elem_size != 0, "capacity overflow");

	let align = mem::align_of::<T>();

	let (new_cap, ptr) = if self.cap == 0 {
	// skip to 4 because tiny Vec's are dumb; but not if that would cause overflow
	let new_cap = if elem_size > (!0) / 8 {
	1
	} else {
	4
	};
	let ptr = heap::allocate(new_cap * elem_size, align);
	(new_cap, ptr)
	} else {
	// Since we guarantee that we never allocate more than isize::MAX bytes,
	// `elem_size * self.cap <= isize::MAX` as a precondition, so this can't overflow
	let new_cap = 2 * self.cap;
	let new_alloc_size = new_cap * elem_size;
	alloc_guard(new_alloc_size);
	let ptr = heap::reallocate(self.ptr() as *mut _,
	self.cap * elem_size,
	new_alloc_size,
	align);
	(new_cap, ptr)
	};

	// If allocate or reallocate fail, we'll get `null` back
	if ptr.is_null() {
	oom()
	}

	self.ptr = Unique::new(ptr as *mut _);
	self.cap = new_cap;
	}
	}

	/// Attempts to double the size of the type's backing allocation in place. This is common
	/// enough to want to do that it's easiest to just have a dedicated method. Slightly
	/// more efficient logic can be provided for this than the general case.
	///
	/// Returns true if the reallocation attempt has succeeded, or false otherwise.
	///
	/// # Panics
	///
	/// * Panics if T is zero-sized on the assumption that you managed to exhaust
	/// all `usize::MAX` slots in your imaginary buffer.
	/// * Panics on 32-bit platforms if the requested capacity exceeds
	/// `isize::MAX` bytes.
	#[inline(never)]
	#[cold]
	pub fn double_in_place(&mut self) -> bool {
	unsafe {
	let elem_size = mem::size_of::<T>();
	let align = mem::align_of::<T>();

	// since we set the capacity to usize::MAX when elem_size is
	// 0, getting to here necessarily means the RawVec is overfull.
	assert!(elem_size != 0, "capacity overflow");

	// Since we guarantee that we never allocate more than isize::MAX bytes,
	// `elem_size * self.cap <= isize::MAX` as a precondition, so this can't overflow
	let new_cap = 2 * self.cap;
	let new_alloc_size = new_cap * elem_size;

	alloc_guard(new_alloc_size);
	let size = heap::reallocate_inplace(self.ptr() as *mut _,
	self.cap * elem_size,
	new_alloc_size,
	align);
	if size >= new_alloc_size {
	// We can't directly divide `size`.
	self.cap = new_cap;
	}
	size >= new_alloc_size
	}
	}

	/// Ensures that the buffer contains at least enough space to hold
	/// `used_cap + needed_extra_cap` elements. If it doesn't already,
	/// will reallocate the minimum possible amount of memory necessary.
	/// Generally this will be exactly the amount of memory necessary,
	/// but in principle the allocator is free to give back more than
	/// we asked for.
	///
	/// If `used_cap` exceeds `self.cap()`, this may fail to actually allocate
	/// the requested space. This is not really unsafe, but the unsafe
	/// code you write that relies on the behavior of this function may break.
	///
	/// # Panics
	///
	/// * Panics if the requested capacity exceeds `usize::MAX` bytes.
	/// * Panics on 32-bit platforms if the requested capacity exceeds
	/// `isize::MAX` bytes.
	///
	/// # Aborts
	///
	/// Aborts on OOM
	pub fn reserve_exact(&mut self, used_cap: usize, needed_extra_cap: usize) {
	unsafe {
	let elem_size = mem::size_of::<T>();
	let align = mem::align_of::<T>();

	// NOTE: we don't early branch on ZSTs here because we want this
	// to actually catch "asking for more than usize::MAX" in that case.
	// If we make it past the first branch then we are guaranteed to
	// panic.

	// Don't actually need any more capacity.
	// Wrapping in case they gave a bad `used_cap`.
	if self.cap().wrapping_sub(used_cap) >= needed_extra_cap {
	return;
	}

	// Nothing we can really do about these checks :(
	let new_cap = used_cap.checked_add(needed_extra_cap).expect("capacity overflow");
	let new_alloc_size = new_cap.checked_mul(elem_size).expect("capacity overflow");
	alloc_guard(new_alloc_size);

	let ptr = if self.cap == 0 {
	heap::allocate(new_alloc_size, align)
	} else {
	heap::reallocate(self.ptr() as *mut _,
	self.cap * elem_size,
	new_alloc_size,
	align)
	};

	// If allocate or reallocate fail, we'll get `null` back
	if ptr.is_null() {
	oom()
	}

	self.ptr = Unique::new(ptr as *mut _);
	self.cap = new_cap;
	}
	}

	/// Calculates the buffer's new size given that it'll hold `used_cap +
	/// needed_extra_cap` elements. This logic is used in amortized reserve methods.
	/// Returns `(new_capacity, new_alloc_size)`.
	fn amortized_new_size(&self, used_cap: usize, needed_extra_cap: usize) -> (usize, usize) {
	let elem_size = mem::size_of::<T>();
	// Nothing we can really do about these checks :(
	let required_cap = used_cap.checked_add(needed_extra_cap)
	.expect("capacity overflow");
	// Cannot overflow, because `cap <= isize::MAX`, and type of `cap` is `usize`.
	let double_cap = self.cap * 2;
	// `double_cap` guarantees exponential growth.
	let new_cap = cmp::max(double_cap, required_cap);
	let new_alloc_size = new_cap.checked_mul(elem_size).expect("capacity overflow");
	(new_cap, new_alloc_size)
	}

	/// Ensures that the buffer contains at least enough space to hold
	/// `used_cap + needed_extra_cap` elements. If it doesn't already have
	/// enough capacity, will reallocate enough space plus comfortable slack
	/// space to get amortized `O(1)` behavior. Will limit this behavior
	/// if it would needlessly cause itself to panic.
	///
	/// If `used_cap` exceeds `self.cap()`, this may fail to actually allocate
	/// the requested space. This is not really unsafe, but the unsafe
	/// code you write that relies on the behavior of this function may break.
	///
	/// This is ideal for implementing a bulk-push operation like `extend`.
	///
	/// # Panics
	///
	/// * Panics if the requested capacity exceeds `usize::MAX` bytes.
	/// * Panics on 32-bit platforms if the requested capacity exceeds
	/// `isize::MAX` bytes.
	///
	/// # Aborts
	///
	/// Aborts on OOM
	///
	/// # Examples
	///
	/// ```ignore
	/// struct MyVec<T> {
	/// buf: RawVec<T>,
	/// len: usize,
	/// }
	///
	/// impl<T> MyVec<T> {
	/// pub fn push_all(&mut self, elems: &[T]) {
	/// self.buf.reserve(self.len, elems.len());
	/// // reserve would have aborted or panicked if the len exceeded
	/// // `isize::MAX` so this is safe to do unchecked now.
	/// for x in elems {
	/// unsafe {
	/// ptr::write(self.buf.ptr().offset(self.len as isize), x.clone());
	/// }
	/// self.len += 1;
	/// }
	/// }
	/// }
	/// ```
	pub fn reserve(&mut self, used_cap: usize, needed_extra_cap: usize) {
	unsafe {
	let elem_size = mem::size_of::<T>();
	let align = mem::align_of::<T>();

	// NOTE: we don't early branch on ZSTs here because we want this
	// to actually catch "asking for more than usize::MAX" in that case.
	// If we make it past the first branch then we are guaranteed to
	// panic.

	// Don't actually need any more capacity.
	// Wrapping in case they give a bad `used_cap`
	if self.cap().wrapping_sub(used_cap) >= needed_extra_cap {
	return;
	}

	let (new_cap, new_alloc_size) = self.amortized_new_size(used_cap, needed_extra_cap);
	// FIXME: may crash and burn on over-reserve
	alloc_guard(new_alloc_size);

	let ptr = if self.cap == 0 {
	heap::allocate(new_alloc_size, align)
	} else {
	heap::reallocate(self.ptr() as *mut _,
	self.cap * elem_size,
	new_alloc_size,
	align)
	};

	// If allocate or reallocate fail, we'll get `null` back
	if ptr.is_null() {
	oom()
	}

	self.ptr = Unique::new(ptr as *mut _);
	self.cap = new_cap;
	}
	}

	/// Attempts to ensure that the buffer contains at least enough space to hold
	/// `used_cap + needed_extra_cap` elements. If it doesn't already have
	/// enough capacity, will reallocate in place enough space plus comfortable slack
	/// space to get amortized `O(1)` behaviour. Will limit this behaviour
	/// if it would needlessly cause itself to panic.
	///
	/// If `used_cap` exceeds `self.cap()`, this may fail to actually allocate
	/// the requested space. This is not really unsafe, but the unsafe
	/// code you write that relies on the behaviour of this function may break.
	///
	/// Returns true if the reallocation attempt has succeeded, or false otherwise.
	///
	/// # Panics
	///
	/// * Panics if the requested capacity exceeds `usize::MAX` bytes.
	/// * Panics on 32-bit platforms if the requested capacity exceeds
	/// `isize::MAX` bytes.
	pub fn reserve_in_place(&mut self, used_cap: usize, needed_extra_cap: usize) -> bool {
	unsafe {
	let elem_size = mem::size_of::<T>();
	let align = mem::align_of::<T>();

	// NOTE: we don't early branch on ZSTs here because we want this
	// to actually catch "asking for more than usize::MAX" in that case.
	// If we make it past the first branch then we are guaranteed to
	// panic.

	// Don't actually need any more capacity. If the current `cap` is 0, we can't
	// reallocate in place.
	// Wrapping in case they give a bad `used_cap`
	if self.cap().wrapping_sub(used_cap) >= needed_extra_cap \|\| self.cap == 0 {
	return false;
	}

	let (_, new_alloc_size) = self.amortized_new_size(used_cap, needed_extra_cap);
	// FIXME: may crash and burn on over-reserve
	alloc_guard(new_alloc_size);

	let size = heap::reallocate_inplace(self.ptr() as *mut _,
	self.cap * elem_size,
	new_alloc_size,
	align);
	if size >= new_alloc_size {
	self.cap = new_alloc_size / elem_size;
	}
	size >= new_alloc_size
	}
	}

	/// Shrinks the allocation down to the specified amount. If the given amount
	/// is 0, actually completely deallocates.
	///
	/// # Panics
	///
	/// Panics if the given amount is larger than the current capacity.
	///
	/// # Aborts
	///
	/// Aborts on OOM.
	pub fn shrink_to_fit(&mut self, amount: usize) {
	let elem_size = mem::size_of::<T>();
	let align = mem::align_of::<T>();

	// Set the `cap` because they might be about to promote to a `Box<[T]>`
	if elem_size == 0 {
	self.cap = amount;
	return;
	}

	// This check is my waterloo; it's the only thing Vec wouldn't have to do.
	assert!(self.cap >= amount, "Tried to shrink to a larger capacity");

	if amount == 0 {
	mem::replace(self, RawVec::new());
	} else if self.cap != amount {
	unsafe {
	// Overflow check is unnecessary as the vector is already at
	// least this large.
	let ptr = heap::reallocate(self.ptr() as *mut _,
	self.cap * elem_size,
	amount * elem_size,
	align);
	if ptr.is_null() {
	oom()
	}
	self.ptr = Unique::new(ptr as *mut _);
	}
	self.cap = amount;
	}
	}

	/// Converts the entire buffer into `Box<[T]>`.
	///
	/// While it is not strictly Undefined Behavior to call
	/// this procedure while some of the RawVec is unintialized,
	/// it cetainly makes it trivial to trigger it.
	///
	/// Note that this will correctly reconstitute any `cap` changes
	/// that may have been performed. (see description of type for details)
	pub unsafe fn into_box(self) -> Box<[T]> {
	// NOTE: not calling `cap()` here, actually using the real `cap` field!
	let slice = slice::from_raw_parts_mut(self.ptr(), self.cap);
	let output: Box<[T]> = Box::from_raw(slice);
	mem::forget(self);
	output
	}

	/// This is a stupid name in the hopes that someone will find this in the
	/// not too distant future and remove it with the rest of
	/// #[unsafe_no_drop_flag]
	pub fn unsafe_no_drop_flag_needs_drop(&self) -> bool {
	self.cap != mem::POST_DROP_USIZE
	}
	}

	impl<T> Drop for RawVec<T> {
	#[unsafe_destructor_blind_to_params]
	/// Frees the memory owned by the RawVec without trying to Drop its contents.
	fn drop(&mut self) {
	let elem_size = mem::size_of::<T>();
	if elem_size != 0 && self.cap != 0 && self.unsafe_no_drop_flag_needs_drop() {
	let align = mem::align_of::<T>();

	let num_bytes = elem_size * self.cap;
	unsafe {
	heap::deallocate(self.ptr as mut _, num_bytes, align);
	}
	}
	}
	}



	// We need to guarantee the following:
	// * We don't ever allocate `> isize::MAX` byte-size objects
	// * We don't overflow `usize::MAX` and actually allocate too little
	//
	// On 64-bit we just need to check for overflow since trying to allocate
	// `> isize::MAX` bytes will surely fail. On 32-bit and 16-bit we need to add
	// an extra guard for this in case we're running on a platform which can use
	// all 4GB in user-space. e.g. PAE or x32

	#[inline]
	fn alloc_guard(alloc_size: usize) {
	if mem::size_of::<usize>() < 8 {
	assert!(alloc_size <= ::core::isize::MAX as usize,
	"capacity overflow");
	}
	}


	#[cfg(test)]
	mod tests {
	use super::*;

	#[test]
	fn reserve_does_not_overallocate() {
	{
	let mut v: RawVec<u32> = RawVec::new();
	// First `reserve` allocates like `reserve_exact`
	v.reserve(0, 9);
	assert_eq!(9, v.cap());
	}

	{
	let mut v: RawVec<u32> = RawVec::new();
	v.reserve(0, 7);
	assert_eq!(7, v.cap());
	// 97 if more than double of 7, so `reserve` should work
	// like `reserve_exact`.
	v.reserve(7, 90);
	assert_eq!(97, v.cap());
	}

	{
	let mut v: RawVec<u32> = RawVec::new();
	v.reserve(0, 12);
	assert_eq!(12, v.cap());
	v.reserve(12, 3);
	// 3 is less than half of 12, so `reserve` must grow
	// exponentially. At the time of writing this test grow
	// factor is 2, so new capacity is 24, however, grow factor
	// of 1.5 is OK too. Hence `>= 18` in assert.
	assert!(v.cap() >= 12 + 12 / 2);
	}
	}

	}