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 use core::ptr::Unique;
  12 use core::mem;
  13 use core::slice;
  14 use heap;
  15 use super::oom;
  16 use super::boxed::Box;
  17 use core::ops::Drop;
  18 use core::cmp;
  19
  20 /// A low-level utility for more ergonomically allocating, reallocating, and deallocating a
  21 /// a buffer of memory on the heap without having to worry about all the corner cases
  22 /// involved. This type is excellent for building your own data structures like Vec and VecDeque.
  23 /// In particular:
  24 ///
  25 /// * Produces heap::EMPTY on zero-sized types
  26 /// * Produces heap::EMPTY on zero-length allocations
  27 /// * Catches all overflows in capacity computations (promotes them to "capacity overflow" panics)
  28 /// * Guards against 32-bit systems allocating more than isize::MAX bytes
  29 /// * Guards against overflowing your length
  30 /// * Aborts on OOM
  31 /// * Avoids freeing heap::EMPTY
  32 /// * Contains a ptr::Unique and thus endows the user with all related benefits
  33 ///
  34 /// This type does not in anyway inspect the memory that it manages. When dropped it *will*
  35 /// free its memory, but it *won't* try to Drop its contents. It is up to the user of RawVec
  36 /// to handle the actual things *stored* inside of a RawVec.
  37 ///
  38 /// Note that a RawVec always forces its capacity to be usize::MAX for zero-sized types.
  39 /// This enables you to use capacity growing logic catch the overflows in your length
  40 /// that might occur with zero-sized types.
  41 ///
  42 /// However this means that you need to be careful when roundtripping this type
  43 /// with a `Box<[T]>`: `cap()` won't yield the len. However `with_capacity`,
  44 /// `shrink_to_fit`, and `from_box` will actually set RawVec's private capacity
  45 /// field. This allows zero-sized types to not be special-cased by consumers of
  46 /// this type.
  47 #[unsafe_no_drop_flag]
  48 pub struct RawVec<T> {
  49     ptr: Unique<T>,
  50     cap: usize,
  51 }
  52
  53 impl<T> RawVec<T> {
  54     /// Creates the biggest possible RawVec without allocating. If T has positive
  55     /// size, then this makes a RawVec with capacity 0. If T has 0 size, then it
  56     /// it makes a RawVec with capacity `usize::MAX`. Useful for implementing
  57     /// delayed allocation.
  58     pub fn new() -> Self {
  59         unsafe {
  60             // !0 is usize::MAX. This branch should be stripped at compile time.
  61             let cap = if mem::size_of::<T>() == 0 {
  62                 !0
  63             } else {
  64                 0
  65             };
  66
  67             // heap::EMPTY doubles as "unallocated" and "zero-sized allocation"
  68             RawVec {
  69                 ptr: Unique::new(heap::EMPTY as *mut T),
  70                 cap: cap,
  71             }
  72         }
  73     }
  74
  75     /// Creates a RawVec with exactly the capacity and alignment requirements
  76     /// for a `[T; cap]`. This is equivalent to calling RawVec::new when `cap` is 0
  77     /// or T is zero-sized. Note that if `T` is zero-sized this means you will *not*
  78     /// get a RawVec with the requested capacity!
  79     ///
  80     /// # Panics
  81     ///
  82     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
  83     /// * Panics on 32-bit platforms if the requested capacity exceeds
  84     ///   `isize::MAX` bytes.
  85     ///
  86     /// # Aborts
  87     ///
  88     /// Aborts on OOM
  89     pub fn with_capacity(cap: usize) -> Self {
  90         unsafe {
  91             let elem_size = mem::size_of::<T>();
  92
  93             let alloc_size = cap.checked_mul(elem_size).expect("capacity overflow");
  94             alloc_guard(alloc_size);
  95
  96             // handles ZSTs and `cap = 0` alike
  97             let ptr = if alloc_size == 0 {
  98                 heap::EMPTY as *mut u8
  99             } else {
 100                 let align = mem::align_of::<T>();
 101                 let ptr = heap::allocate(alloc_size, align);
 102                 if ptr.is_null() {
 103                     oom()
 104                 }
 105                 ptr
 106             };
 107
 108             RawVec {
 109                 ptr: Unique::new(ptr as *mut _),
 110                 cap: cap,
 111             }
 112         }
 113     }
 114
 115     /// Reconstitutes a RawVec from a pointer and capacity.
 116     ///
 117     /// # Undefined Behavior
 118     ///
 119     /// The ptr must be allocated, and with the given capacity. The
 120     /// capacity cannot exceed `isize::MAX` (only a concern on 32-bit systems).
 121     /// If the ptr and capacity come from a RawVec, then this is guaranteed.
 122     pub unsafe fn from_raw_parts(ptr: *mut T, cap: usize) -> Self {
 123         RawVec {
 124             ptr: Unique::new(ptr),
 125             cap: cap,
 126         }
 127     }
 128
 129     /// Converts a `Box<[T]>` into a `RawVec<T>`.
 130     pub fn from_box(mut slice: Box<[T]>) -> Self {
 131         unsafe {
 132             let result = RawVec::from_raw_parts(slice.as_mut_ptr(), slice.len());
 133             mem::forget(slice);
 134             result
 135         }
 136     }
 137 }
 138
 139 impl<T> RawVec<T> {
 140     /// Gets a raw pointer to the start of the allocation. Note that this is
 141     /// heap::EMPTY if `cap = 0` or T is zero-sized. In the former case, you must
 142     /// be careful.
 143     pub fn ptr(&self) -> *mut T {
 144         *self.ptr
 145     }
 146
 147     /// Gets the capacity of the allocation.
 148     ///
 149     /// This will always be `usize::MAX` if `T` is zero-sized.
 150     pub fn cap(&self) -> usize {
 151         if mem::size_of::<T>() == 0 {
 152             !0
 153         } else {
 154             self.cap
 155         }
 156     }
 157
 158     /// Doubles the size of the type's backing allocation. This is common enough
 159     /// to want to do that it's easiest to just have a dedicated method. Slightly
 160     /// more efficient logic can be provided for this than the general case.
 161     ///
 162     /// This function is ideal for when pushing elements one-at-a-time because
 163     /// you don't need to incur the costs of the more general computations
 164     /// reserve needs to do to guard against overflow. You do however need to
 165     /// manually check if your `len == cap`.
 166     ///
 167     /// # Panics
 168     ///
 169     /// * Panics if T is zero-sized on the assumption that you managed to exhaust
 170     ///   all `usize::MAX` slots in your imaginary buffer.
 171     /// * Panics on 32-bit platforms if the requested capacity exceeds
 172     ///   `isize::MAX` bytes.
 173     ///
 174     /// # Aborts
 175     ///
 176     /// Aborts on OOM
 177     ///
 178     /// # Examples
 179     ///
 180     /// ```ignore
 181     /// struct MyVec<T> {
 182     ///     buf: RawVec<T>,
 183     ///     len: usize,
 184     /// }
 185     ///
 186     /// impl<T> MyVec<T> {
 187     ///     pub fn push(&mut self, elem: T) {
 188     ///         if self.len == self.buf.cap() { self.buf.double(); }
 189     ///         // double would have aborted or panicked if the len exceeded
 190     ///         // `isize::MAX` so this is safe to do unchecked now.
 191     ///         unsafe {
 192     ///             ptr::write(self.buf.ptr().offset(self.len as isize), elem);
 193     ///         }
 194     ///         self.len += 1;
 195     ///     }
 196     /// }
 197     /// ```
 198     #[inline(never)]
 199     #[cold]
 200     pub fn double(&mut self) {
 201         unsafe {
 202             let elem_size = mem::size_of::<T>();
 203
 204             // since we set the capacity to usize::MAX when elem_size is
 205             // 0, getting to here necessarily means the RawVec is overfull.
 206             assert!(elem_size != 0, "capacity overflow");
 207
 208             let align = mem::align_of::<T>();
 209
 210             let (new_cap, ptr) = if self.cap == 0 {
 211                 // skip to 4 because tiny Vec's are dumb; but not if that would cause overflow
 212                 let new_cap = if elem_size > (!0) / 8 {
 213                     1
 214                 } else {
 215                     4
 216                 };
 217                 let ptr = heap::allocate(new_cap * elem_size, align);
 218                 (new_cap, ptr)
 219             } else {
 220                 // Since we guarantee that we never allocate more than isize::MAX bytes,
 221                 // `elem_size * self.cap <= isize::MAX` as a precondition, so this can't overflow
 222                 let new_cap = 2 * self.cap;
 223                 let new_alloc_size = new_cap * elem_size;
 224                 alloc_guard(new_alloc_size);
 225                 let ptr = heap::reallocate(self.ptr() as *mut _,
 226                                            self.cap * elem_size,
 227                                            new_alloc_size,
 228                                            align);
 229                 (new_cap, ptr)
 230             };
 231
 232             // If allocate or reallocate fail, we'll get `null` back
 233             if ptr.is_null() {
 234                 oom()
 235             }
 236
 237             self.ptr = Unique::new(ptr as *mut _);
 238             self.cap = new_cap;
 239         }
 240     }
 241
 242     /// Attempts to double the size of the type's backing allocation in place. This is common
 243     /// enough to want to do that it's easiest to just have a dedicated method. Slightly
 244     /// more efficient logic can be provided for this than the general case.
 245     ///
 246     /// Returns true if the reallocation attempt has succeeded, or false otherwise.
 247     ///
 248     /// # Panics
 249     ///
 250     /// * Panics if T is zero-sized on the assumption that you managed to exhaust
 251     ///   all `usize::MAX` slots in your imaginary buffer.
 252     /// * Panics on 32-bit platforms if the requested capacity exceeds
 253     ///   `isize::MAX` bytes.
 254     #[inline(never)]
 255     #[cold]
 256     pub fn double_in_place(&mut self) -> bool {
 257         unsafe {
 258             let elem_size = mem::size_of::<T>();
 259             let align = mem::align_of::<T>();
 260
 261             // since we set the capacity to usize::MAX when elem_size is
 262             // 0, getting to here necessarily means the RawVec is overfull.
 263             assert!(elem_size != 0, "capacity overflow");
 264
 265             // Since we guarantee that we never allocate more than isize::MAX bytes,
 266             // `elem_size * self.cap <= isize::MAX` as a precondition, so this can't overflow
 267             let new_cap = 2 * self.cap;
 268             let new_alloc_size = new_cap * elem_size;
 269
 270             alloc_guard(new_alloc_size);
 271             let size = heap::reallocate_inplace(self.ptr() as *mut _,
 272                                                 self.cap * elem_size,
 273                                                 new_alloc_size,
 274                                                 align);
 275             if size >= new_alloc_size {
 276                 // We can't directly divide `size`.
 277                 self.cap = new_cap;
 278             }
 279             size >= new_alloc_size
 280         }
 281     }
 282
 283     /// Ensures that the buffer contains at least enough space to hold
 284     /// `used_cap + needed_extra_cap` elements. If it doesn't already,
 285     /// will reallocate the minimum possible amount of memory necessary.
 286     /// Generally this will be exactly the amount of memory necessary,
 287     /// but in principle the allocator is free to give back more than
 288     /// we asked for.
 289     ///
 290     /// If `used_cap` exceeds `self.cap()`, this may fail to actually allocate
 291     /// the requested space. This is not really unsafe, but the unsafe
 292     /// code *you* write that relies on the behavior of this function may break.
 293     ///
 294     /// # Panics
 295     ///
 296     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
 297     /// * Panics on 32-bit platforms if the requested capacity exceeds
 298     ///   `isize::MAX` bytes.
 299     ///
 300     /// # Aborts
 301     ///
 302     /// Aborts on OOM
 303     pub fn reserve_exact(&mut self, used_cap: usize, needed_extra_cap: usize) {
 304         unsafe {
 305             let elem_size = mem::size_of::<T>();
 306             let align = mem::align_of::<T>();
 307
 308             // NOTE: we don't early branch on ZSTs here because we want this
 309             // to actually catch "asking for more than usize::MAX" in that case.
 310             // If we make it past the first branch then we are guaranteed to
 311             // panic.
 312
 313             // Don't actually need any more capacity.
 314             // Wrapping in case they gave a bad `used_cap`.
 315             if self.cap().wrapping_sub(used_cap) >= needed_extra_cap {
 316                 return;
 317             }
 318
 319             // Nothing we can really do about these checks :(
 320             let new_cap = used_cap.checked_add(needed_extra_cap).expect("capacity overflow");
 321             let new_alloc_size = new_cap.checked_mul(elem_size).expect("capacity overflow");
 322             alloc_guard(new_alloc_size);
 323
 324             let ptr = if self.cap == 0 {
 325                 heap::allocate(new_alloc_size, align)
 326             } else {
 327                 heap::reallocate(self.ptr() as *mut _,
 328                                  self.cap * elem_size,
 329                                  new_alloc_size,
 330                                  align)
 331             };
 332
 333             // If allocate or reallocate fail, we'll get `null` back
 334             if ptr.is_null() {
 335                 oom()
 336             }
 337
 338             self.ptr = Unique::new(ptr as *mut _);
 339             self.cap = new_cap;
 340         }
 341     }
 342
 343     /// Calculates the buffer's new size given that it'll hold `used_cap +
 344     /// needed_extra_cap` elements. This logic is used in amortized reserve methods.
 345     /// Returns `(new_capacity, new_alloc_size)`.
 346     fn amortized_new_size(&self, used_cap: usize, needed_extra_cap: usize) -> (usize, usize) {
 347         let elem_size = mem::size_of::<T>();
 348         // Nothing we can really do about these checks :(
 349         let required_cap = used_cap.checked_add(needed_extra_cap)
 350                                    .expect("capacity overflow");
 351         // Cannot overflow, because `cap <= isize::MAX`, and type of `cap` is `usize`.
 352         let double_cap = self.cap * 2;
 353         // `double_cap` guarantees exponential growth.
 354         let new_cap = cmp::max(double_cap, required_cap);
 355         let new_alloc_size = new_cap.checked_mul(elem_size).expect("capacity overflow");
 356         (new_cap, new_alloc_size)
 357     }
 358
 359     /// Ensures that the buffer contains at least enough space to hold
 360     /// `used_cap + needed_extra_cap` elements. If it doesn't already have
 361     /// enough capacity, will reallocate enough space plus comfortable slack
 362     /// space to get amortized `O(1)` behavior. Will limit this behavior
 363     /// if it would needlessly cause itself to panic.
 364     ///
 365     /// If `used_cap` exceeds `self.cap()`, this may fail to actually allocate
 366     /// the requested space. This is not really unsafe, but the unsafe
 367     /// code *you* write that relies on the behavior of this function may break.
 368     ///
 369     /// This is ideal for implementing a bulk-push operation like `extend`.
 370     ///
 371     /// # Panics
 372     ///
 373     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
 374     /// * Panics on 32-bit platforms if the requested capacity exceeds
 375     ///   `isize::MAX` bytes.
 376     ///
 377     /// # Aborts
 378     ///
 379     /// Aborts on OOM
 380     ///
 381     /// # Examples
 382     ///
 383     /// ```ignore
 384     /// struct MyVec<T> {
 385     ///     buf: RawVec<T>,
 386     ///     len: usize,
 387     /// }
 388     ///
 389     /// impl<T> MyVec<T> {
 390     ///     pub fn push_all(&mut self, elems: &[T]) {
 391     ///         self.buf.reserve(self.len, elems.len());
 392     ///         // reserve would have aborted or panicked if the len exceeded
 393     ///         // `isize::MAX` so this is safe to do unchecked now.
 394     ///         for x in elems {
 395     ///             unsafe {
 396     ///                 ptr::write(self.buf.ptr().offset(self.len as isize), x.clone());
 397     ///             }
 398     ///             self.len += 1;
 399     ///         }
 400     ///     }
 401     /// }
 402     /// ```
 403     pub fn reserve(&mut self, used_cap: usize, needed_extra_cap: usize) {
 404         unsafe {
 405             let elem_size = mem::size_of::<T>();
 406             let align = mem::align_of::<T>();
 407
 408             // NOTE: we don't early branch on ZSTs here because we want this
 409             // to actually catch "asking for more than usize::MAX" in that case.
 410             // If we make it past the first branch then we are guaranteed to
 411             // panic.
 412
 413             // Don't actually need any more capacity.
 414             // Wrapping in case they give a bad `used_cap`
 415             if self.cap().wrapping_sub(used_cap) >= needed_extra_cap {
 416                 return;
 417             }
 418
 419             let (new_cap, new_alloc_size) = self.amortized_new_size(used_cap, needed_extra_cap);
 420             // FIXME: may crash and burn on over-reserve
 421             alloc_guard(new_alloc_size);
 422
 423             let ptr = if self.cap == 0 {
 424                 heap::allocate(new_alloc_size, align)
 425             } else {
 426                 heap::reallocate(self.ptr() as *mut _,
 427                                  self.cap * elem_size,
 428                                  new_alloc_size,
 429                                  align)
 430             };
 431
 432             // If allocate or reallocate fail, we'll get `null` back
 433             if ptr.is_null() {
 434                 oom()
 435             }
 436
 437             self.ptr = Unique::new(ptr as *mut _);
 438             self.cap = new_cap;
 439         }
 440     }
 441
 442     /// Attempts to ensure that the buffer contains at least enough space to hold
 443     /// `used_cap + needed_extra_cap` elements. If it doesn't already have
 444     /// enough capacity, will reallocate in place enough space plus comfortable slack
 445     /// space to get amortized `O(1)` behaviour. Will limit this behaviour
 446     /// if it would needlessly cause itself to panic.
 447     ///
 448     /// If `used_cap` exceeds `self.cap()`, this may fail to actually allocate
 449     /// the requested space. This is not really unsafe, but the unsafe
 450     /// code *you* write that relies on the behaviour of this function may break.
 451     ///
 452     /// Returns true if the reallocation attempt has succeeded, or false otherwise.
 453     ///
 454     /// # Panics
 455     ///
 456     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
 457     /// * Panics on 32-bit platforms if the requested capacity exceeds
 458     ///   `isize::MAX` bytes.
 459     pub fn reserve_in_place(&mut self, used_cap: usize, needed_extra_cap: usize) -> bool {
 460         unsafe {
 461             let elem_size = mem::size_of::<T>();
 462             let align = mem::align_of::<T>();
 463
 464             // NOTE: we don't early branch on ZSTs here because we want this
 465             // to actually catch "asking for more than usize::MAX" in that case.
 466             // If we make it past the first branch then we are guaranteed to
 467             // panic.
 468
 469             // Don't actually need any more capacity. If the current `cap` is 0, we can't
 470             // reallocate in place.
 471             // Wrapping in case they give a bad `used_cap`
 472             if self.cap().wrapping_sub(used_cap) >= needed_extra_cap || self.cap == 0 {
 473                 return false;
 474             }
 475
 476             let (_, new_alloc_size) = self.amortized_new_size(used_cap, needed_extra_cap);
 477             // FIXME: may crash and burn on over-reserve
 478             alloc_guard(new_alloc_size);
 479
 480             let size = heap::reallocate_inplace(self.ptr() as *mut _,
 481                                                 self.cap * elem_size,
 482                                                 new_alloc_size,
 483                                                 align);
 484             if size >= new_alloc_size {
 485                 self.cap = new_alloc_size / elem_size;
 486             }
 487             size >= new_alloc_size
 488         }
 489     }
 490
 491     /// Shrinks the allocation down to the specified amount. If the given amount
 492     /// is 0, actually completely deallocates.
 493     ///
 494     /// # Panics
 495     ///
 496     /// Panics if the given amount is *larger* than the current capacity.
 497     ///
 498     /// # Aborts
 499     ///
 500     /// Aborts on OOM.
 501     pub fn shrink_to_fit(&mut self, amount: usize) {
 502         let elem_size = mem::size_of::<T>();
 503         let align = mem::align_of::<T>();
 504
 505         // Set the `cap` because they might be about to promote to a `Box<[T]>`
 506         if elem_size == 0 {
 507             self.cap = amount;
 508             return;
 509         }
 510
 511         // This check is my waterloo; it's the only thing Vec wouldn't have to do.
 512         assert!(self.cap >= amount, "Tried to shrink to a larger capacity");
 513
 514         if amount == 0 {
 515             mem::replace(self, RawVec::new());
 516         } else if self.cap != amount {
 517             unsafe {
 518                 // Overflow check is unnecessary as the vector is already at
 519                 // least this large.
 520                 let ptr = heap::reallocate(self.ptr() as *mut _,
 521                                            self.cap * elem_size,
 522                                            amount * elem_size,
 523                                            align);
 524                 if ptr.is_null() {
 525                     oom()
 526                 }
 527                 self.ptr = Unique::new(ptr as *mut _);
 528             }
 529             self.cap = amount;
 530         }
 531     }
 532
 533     /// Converts the entire buffer into `Box<[T]>`.
 534     ///
 535     /// While it is not *strictly* Undefined Behavior to call
 536     /// this procedure while some of the RawVec is unintialized,
 537     /// it cetainly makes it trivial to trigger it.
 538     ///
 539     /// Note that this will correctly reconstitute any `cap` changes
 540     /// that may have been performed. (see description of type for details)
 541     pub unsafe fn into_box(self) -> Box<[T]> {
 542         // NOTE: not calling `cap()` here, actually using the real `cap` field!
 543         let slice = slice::from_raw_parts_mut(self.ptr(), self.cap);
 544         let output: Box<[T]> = Box::from_raw(slice);
 545         mem::forget(self);
 546         output
 547     }
 548
 549     /// This is a stupid name in the hopes that someone will find this in the
 550     /// not too distant future and remove it with the rest of
 551     /// #[unsafe_no_drop_flag]
 552     pub fn unsafe_no_drop_flag_needs_drop(&self) -> bool {
 553         self.cap != mem::POST_DROP_USIZE
 554     }
 555 }
 556
 557 impl<T> Drop for RawVec<T> {
 558     #[unsafe_destructor_blind_to_params]
 559     /// Frees the memory owned by the RawVec *without* trying to Drop its contents.
 560     fn drop(&mut self) {
 561         let elem_size = mem::size_of::<T>();
 562         if elem_size != 0 && self.cap != 0 && self.unsafe_no_drop_flag_needs_drop() {
 563             let align = mem::align_of::<T>();
 564
 565             let num_bytes = elem_size * self.cap;
 566             unsafe {
 567                 heap::deallocate(*self.ptr as *mut _, num_bytes, align);
 568             }
 569         }
 570     }
 571 }
 572
 573
 574
 575 // We need to guarantee the following:
 576 // * We don't ever allocate `> isize::MAX` byte-size objects
 577 // * We don't overflow `usize::MAX` and actually allocate too little
 578 //
 579 // On 64-bit we just need to check for overflow since trying to allocate
 580 // `> isize::MAX` bytes will surely fail. On 32-bit we need to add an extra
 581 // guard for this in case we're running on a platform which can use all 4GB in
 582 // user-space. e.g. PAE or x32
 583
 584 #[inline]
 585 fn alloc_guard(alloc_size: usize) {
 586     if mem::size_of::<usize>() < 8 {
 587         assert!(alloc_size <= ::core::isize::MAX as usize,
 588                 "capacity overflow");
 589     }
 590 }
 591
 592
 593 #[cfg(test)]
 594 mod tests {
 595     use super::*;
 596
 597     #[test]
 598     fn reserve_does_not_overallocate() {
 599         {
 600             let mut v: RawVec<u32> = RawVec::new();
 601             // First `reserve` allocates like `reserve_exact`
 602             v.reserve(0, 9);
 603             assert_eq!(9, v.cap());
 604         }
 605
 606         {
 607             let mut v: RawVec<u32> = RawVec::new();
 608             v.reserve(0, 7);
 609             assert_eq!(7, v.cap());
 610             // 97 if more than double of 7, so `reserve` should work
 611             // like `reserve_exact`.
 612             v.reserve(7, 90);
 613             assert_eq!(97, v.cap());
 614         }
 615
 616         {
 617             let mut v: RawVec<u32> = RawVec::new();
 618             v.reserve(0, 12);
 619             assert_eq!(12, v.cap());
 620             v.reserve(12, 3);
 621             // 3 is less than half of 12, so `reserve` must grow
 622             // exponentially. At the time of writing this test grow
 623             // factor is 2, so new capacity is 24, however, grow factor
 624             // of 1.5 is OK too. Hence `>= 18` in assert.
 625             assert!(v.cap() >= 12 + 12 / 2);
 626         }
 627     }
 628
 629 }