mfbt/Vector.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /* A type/length-parametrized vector class. */
   8
   9 #ifndef mozilla_Vector_h
  10 #define mozilla_Vector_h
  11
  12 #include "mozilla/Alignment.h"
  13 #include "mozilla/AllocPolicy.h"
  14 #include "mozilla/Assertions.h"
  15 #include "mozilla/Attributes.h"
  16 #include "mozilla/MathAlgorithms.h"
  17 #include "mozilla/MemoryReporting.h"
  18 #include "mozilla/Move.h"
  19 #include "mozilla/NullPtr.h"
  20 #include "mozilla/ReentrancyGuard.h"
  21 #include "mozilla/TemplateLib.h"
  22 #include "mozilla/TypeTraits.h"
  23 #include "mozilla/Util.h" // for PointerRangeSize
  24
  25 #include <new> // for placement new
  26
  27 /* Silence dire "bugs in previous versions of MSVC have been fixed" warnings */
  28 #ifdef _MSC_VER
  29 #pragma warning(push)
  30 #pragma warning(disable:4345)
  31 #endif
  32
  33 namespace mozilla {
  34
  35 template<typename T, size_t N, class AllocPolicy, class ThisVector>
  36 class VectorBase;
  37
  38 namespace detail {
  39
  40 /*
  41  * Check that the given capacity wastes the minimal amount of space if
  42  * allocated on the heap.  This means that cap*sizeof(T) is as close to a
  43  * power-of-two as possible.  growStorageBy() is responsible for ensuring
  44  * this.
  45  */
  46 template<typename T>
  47 static bool CapacityHasExcessSpace(size_t cap)
  48 {
  49   size_t size = cap * sizeof(T);
  50   return RoundUpPow2(size) - size >= sizeof(T);
  51 }
  52
  53 /*
  54  * This template class provides a default implementation for vector operations
  55  * when the element type is not known to be a POD, as judged by IsPod.
  56  */
  57 template<typename T, size_t N, class AP, class ThisVector, bool IsPod>
  58 struct VectorImpl
  59 {
  60     /* Destroys constructed objects in the range [begin, end). */
  61     static inline void destroy(T* begin, T* end) {
  62       for (T* p = begin; p < end; ++p)
  63         p->~T();
  64     }
  65
  66     /* Constructs objects in the uninitialized range [begin, end). */
  67     static inline void initialize(T* begin, T* end) {
  68       for (T* p = begin; p < end; ++p)
  69         new(p) T();
  70     }
  71
  72     /*
  73      * Copy-constructs objects in the uninitialized range
  74      * [dst, dst+(srcend-srcbeg)) from the range [srcbeg, srcend).
  75      */
  76     template<typename U>
  77     static inline void copyConstruct(T* dst, const U* srcbeg, const U* srcend) {
  78       for (const U* p = srcbeg; p < srcend; ++p, ++dst)
  79         new(dst) T(*p);
  80     }
  81
  82     /*
  83      * Move-constructs objects in the uninitialized range
  84      * [dst, dst+(srcend-srcbeg)) from the range [srcbeg, srcend).
  85      */
  86     template<typename U>
  87     static inline void moveConstruct(T* dst, const U* srcbeg, const U* srcend) {
  88       for (const U* p = srcbeg; p < srcend; ++p, ++dst)
  89         new(dst) T(OldMove(*p));
  90     }
  91
  92     /*
  93      * Copy-constructs objects in the uninitialized range [dst, dst+n) from the
  94      * same object u.
  95      */
  96     template<typename U>
  97     static inline void copyConstructN(T* dst, size_t n, const U& u) {
  98       for (T* end = dst + n; dst < end; ++dst)
  99         new(dst) T(u);
 100     }
 101
 102     /*
 103      * Grows the given buffer to have capacity newCap, preserving the objects
 104      * constructed in the range [begin, end) and updating v. Assumes that (1)
 105      * newCap has not overflowed, and (2) multiplying newCap by sizeof(T) will
 106      * not overflow.
 107      */
 108     static inline bool
 109     growTo(VectorBase<T, N, AP, ThisVector>& v, size_t newCap) {
 110       MOZ_ASSERT(!v.usingInlineStorage());
 111       MOZ_ASSERT(!CapacityHasExcessSpace<T>(newCap));
 112       T* newbuf = reinterpret_cast<T*>(v.malloc_(newCap * sizeof(T)));
 113       if (!newbuf)
 114         return false;
 115       T* dst = newbuf;
 116       T* src = v.beginNoCheck();
 117       for (; src < v.endNoCheck(); ++dst, ++src)
 118         new(dst) T(OldMove(*src));
 119       VectorImpl::destroy(v.beginNoCheck(), v.endNoCheck());
 120       v.free_(v.mBegin);
 121       v.mBegin = newbuf;
 122       /* v.mLength is unchanged. */
 123       v.mCapacity = newCap;
 124       return true;
 125     }
 126 };
 127
 128 /*
 129  * This partial template specialization provides a default implementation for
 130  * vector operations when the element type is known to be a POD, as judged by
 131  * IsPod.
 132  */
 133 template<typename T, size_t N, class AP, class ThisVector>
 134 struct VectorImpl<T, N, AP, ThisVector, true>
 135 {
 136     static inline void destroy(T*, T*) {}
 137
 138     static inline void initialize(T* begin, T* end) {
 139       /*
 140        * You would think that memset would be a big win (or even break even)
 141        * when we know T is a POD. But currently it's not. This is probably
 142        * because |append| tends to be given small ranges and memset requires
 143        * a function call that doesn't get inlined.
 144        *
 145        * memset(begin, 0, sizeof(T) * (end-begin));
 146        */
 147       for (T* p = begin; p < end; ++p)
 148         new(p) T();
 149     }
 150
 151     template<typename U>
 152     static inline void copyConstruct(T* dst, const U* srcbeg, const U* srcend) {
 153       /*
 154        * See above memset comment. Also, notice that copyConstruct is
 155        * currently templated (T != U), so memcpy won't work without
 156        * requiring T == U.
 157        *
 158        * memcpy(dst, srcbeg, sizeof(T) * (srcend - srcbeg));
 159        */
 160       for (const U* p = srcbeg; p < srcend; ++p, ++dst)
 161         *dst = *p;
 162     }
 163
 164     template<typename U>
 165     static inline void moveConstruct(T* dst, const U* srcbeg, const U* srcend) {
 166       copyConstruct(dst, srcbeg, srcend);
 167     }
 168
 169     static inline void copyConstructN(T* dst, size_t n, const T& t) {
 170       for (T* end = dst + n; dst < end; ++dst)
 171         *dst = t;
 172     }
 173
 174     static inline bool
 175     growTo(VectorBase<T, N, AP, ThisVector>& v, size_t newCap) {
 176       MOZ_ASSERT(!v.usingInlineStorage());
 177       MOZ_ASSERT(!CapacityHasExcessSpace<T>(newCap));
 178       size_t oldSize = sizeof(T) * v.mCapacity;
 179       size_t newSize = sizeof(T) * newCap;
 180       T* newbuf = reinterpret_cast<T*>(v.realloc_(v.mBegin, oldSize, newSize));
 181       if (!newbuf)
 182         return false;
 183       v.mBegin = newbuf;
 184       /* v.mLength is unchanged. */
 185       v.mCapacity = newCap;
 186       return true;
 187     }
 188 };
 189
 190 } // namespace detail
 191
 192 /*
 193  * A CRTP base class for vector-like classes.  Unless you really really want
 194  * your own vector class -- and you almost certainly don't -- you should use
 195  * mozilla::Vector instead!
 196  *
 197  * See mozilla::Vector for interface requirements.
 198  */
 199 template<typename T, size_t N, class AllocPolicy, class ThisVector>
 200 class VectorBase : private AllocPolicy
 201 {
 202     /* utilities */
 203
 204     static const bool sElemIsPod = IsPod<T>::value;
 205     typedef detail::VectorImpl<T, N, AllocPolicy, ThisVector, sElemIsPod> Impl;
 206     friend struct detail::VectorImpl<T, N, AllocPolicy, ThisVector, sElemIsPod>;
 207
 208     bool growStorageBy(size_t incr);
 209     bool convertToHeapStorage(size_t newCap);
 210
 211     /* magic constants */
 212
 213     static const int sMaxInlineBytes = 1024;
 214
 215     /* compute constants */
 216
 217     /*
 218      * Consider element size to be 1 for buffer sizing if there are 0 inline
 219      * elements.  This allows us to compile when the definition of the element
 220      * type is not visible here.
 221      *
 222      * Explicit specialization is only allowed at namespace scope, so in order
 223      * to keep everything here, we use a dummy template parameter with partial
 224      * specialization.
 225      */
 226     template<int M, int Dummy>
 227     struct ElemSize
 228     {
 229         static const size_t value = sizeof(T);
 230     };
 231     template<int Dummy>
 232     struct ElemSize<0, Dummy>
 233     {
 234         static const size_t value = 1;
 235     };
 236
 237     static const size_t sInlineCapacity =
 238       tl::Min<N, sMaxInlineBytes / ElemSize<N, 0>::value>::value;
 239
 240     /* Calculate inline buffer size; avoid 0-sized array. */
 241     static const size_t sInlineBytes =
 242       tl::Max<1, sInlineCapacity * ElemSize<N, 0>::value>::value;
 243
 244     /* member data */
 245
 246     /*
 247      * Pointer to the buffer, be it inline or heap-allocated. Only [mBegin,
 248      * mBegin + mLength) hold valid constructed T objects. The range [mBegin +
 249      * mLength, mBegin + mCapacity) holds uninitialized memory. The range
 250      * [mBegin + mLength, mBegin + mReserved) also holds uninitialized memory
 251      * previously allocated by a call to reserve().
 252      */
 253     T* mBegin;
 254
 255     /* Number of elements in the vector. */
 256     size_t mLength;
 257
 258     /* Max number of elements storable in the vector without resizing. */
 259     size_t mCapacity;
 260
 261 #ifdef DEBUG
 262     /* Max elements of reserved or used space in this vector. */
 263     size_t mReserved;
 264 #endif
 265
 266     /* Memory used for inline storage. */
 267     AlignedStorage<sInlineBytes> storage;
 268
 269 #ifdef DEBUG
 270     friend class ReentrancyGuard;
 271     bool entered;
 272 #endif
 273
 274     /* private accessors */
 275
 276     bool usingInlineStorage() const {
 277       return mBegin == const_cast<VectorBase*>(this)->inlineStorage();
 278     }
 279
 280     T* inlineStorage() {
 281       return static_cast<T*>(storage.addr());
 282     }
 283
 284     T* beginNoCheck() const {
 285       return mBegin;
 286     }
 287
 288     T* endNoCheck() {
 289       return mBegin + mLength;
 290     }
 291
 292     const T* endNoCheck() const {
 293       return mBegin + mLength;
 294     }
 295
 296 #ifdef DEBUG
 297     size_t reserved() const {
 298       MOZ_ASSERT(mReserved <= mCapacity);
 299       MOZ_ASSERT(mLength <= mReserved);
 300       return mReserved;
 301     }
 302 #endif
 303
 304     /* Append operations guaranteed to succeed due to pre-reserved space. */
 305     template<typename U> void internalAppend(const U& u);
 306     template<typename U, size_t O, class BP, class UV>
 307     void internalAppendAll(const VectorBase<U, O, BP, UV>& u);
 308     void internalAppendN(const T& t, size_t n);
 309     template<typename U> void internalAppend(const U* begin, size_t length);
 310
 311   public:
 312     static const size_t sMaxInlineStorage = N;
 313
 314     typedef T ElementType;
 315
 316     VectorBase(AllocPolicy = AllocPolicy());
 317     VectorBase(MoveRef<ThisVector>); /* Move constructor. */
 318     ThisVector& operator=(MoveRef<ThisVector>); /* Move assignment. */
 319     ~VectorBase();
 320
 321     /* accessors */
 322
 323     const AllocPolicy& allocPolicy() const {
 324       return *this;
 325     }
 326
 327     AllocPolicy& allocPolicy() {
 328       return *this;
 329     }
 330
 331     enum { InlineLength = N };
 332
 333     size_t length() const {
 334       return mLength;
 335     }
 336
 337     bool empty() const {
 338       return mLength == 0;
 339     }
 340
 341     size_t capacity() const {
 342       return mCapacity;
 343     }
 344
 345     T* begin() {
 346       MOZ_ASSERT(!entered);
 347       return mBegin;
 348     }
 349
 350     const T* begin() const {
 351       MOZ_ASSERT(!entered);
 352       return mBegin;
 353     }
 354
 355     T* end() {
 356       MOZ_ASSERT(!entered);
 357       return mBegin + mLength;
 358     }
 359
 360     const T* end() const {
 361       MOZ_ASSERT(!entered);
 362       return mBegin + mLength;
 363     }
 364
 365     T& operator[](size_t i) {
 366       MOZ_ASSERT(!entered);
 367       MOZ_ASSERT(i < mLength);
 368       return begin()[i];
 369     }
 370
 371     const T& operator[](size_t i) const {
 372       MOZ_ASSERT(!entered);
 373       MOZ_ASSERT(i < mLength);
 374       return begin()[i];
 375     }
 376
 377     T& back() {
 378       MOZ_ASSERT(!entered);
 379       MOZ_ASSERT(!empty());
 380       return *(end() - 1);
 381     }
 382
 383     const T& back() const {
 384       MOZ_ASSERT(!entered);
 385       MOZ_ASSERT(!empty());
 386       return *(end() - 1);
 387     }
 388
 389     class Range
 390     {
 391         friend class VectorBase;
 392         T* cur_;
 393         T* end_;
 394         Range(T* cur, T* end) : cur_(cur), end_(end) {}
 395
 396       public:
 397         Range() {}
 398         bool empty() const { return cur_ == end_; }
 399         size_t remain() const { return end_ - cur_; }
 400         T& front() const { return *cur_; }
 401         void popFront() { MOZ_ASSERT(!empty()); ++cur_; }
 402         T popCopyFront() { MOZ_ASSERT(!empty()); return *cur_++; }
 403     };
 404
 405     Range all() {
 406       return Range(begin(), end());
 407     }
 408
 409     /* mutators */
 410
 411     /**
 412      * Given that the vector is empty and has no inline storage, grow to
 413      * |capacity|.
 414      */
 415     bool initCapacity(size_t request);
 416
 417     /**
 418      * If reserve(length() + N) succeeds, the N next appends are guaranteed to
 419      * succeed.
 420      */
 421     bool reserve(size_t request);
 422
 423     /**
 424      * Destroy elements in the range [end() - incr, end()). Does not deallocate
 425      * or unreserve storage for those elements.
 426      */
 427     void shrinkBy(size_t incr);
 428
 429     /** Grow the vector by incr elements. */
 430     bool growBy(size_t incr);
 431
 432     /** Call shrinkBy or growBy based on whether newSize > length(). */
 433     bool resize(size_t newLength);
 434
 435     /**
 436      * Increase the length of the vector, but don't initialize the new elements
 437      * -- leave them as uninitialized memory.
 438      */
 439     bool growByUninitialized(size_t incr);
 440     bool resizeUninitialized(size_t newLength);
 441
 442     /** Shorthand for shrinkBy(length()). */
 443     void clear();
 444
 445     /** Clears and releases any heap-allocated storage. */
 446     void clearAndFree();
 447
 448     /**
 449      * If true, appending |needed| elements won't reallocate elements storage.
 450      * This *doesn't* mean that infallibleAppend may be used!  You still must
 451      * reserve the extra space, even if this method indicates that appends won't
 452      * need to reallocate elements storage.
 453      */
 454     bool canAppendWithoutRealloc(size_t needed) const;
 455
 456     /**
 457      * Potentially fallible append operations.
 458      *
 459      * The function templates that take an unspecified type U require a const T&
 460      * or a MoveRef<T>.  The MoveRef<T> variants move their operands into the
 461      * vector, instead of copying them.  If they fail, the operand is left
 462      * unmoved.
 463      */
 464     template<typename U> bool append(const U& u);
 465     template<typename U, size_t O, class BP, class UV>
 466     bool appendAll(const VectorBase<U, O, BP, UV>& u);
 467     bool appendN(const T& t, size_t n);
 468     template<typename U> bool append(const U* begin, const U* end);
 469     template<typename U> bool append(const U* begin, size_t length);
 470
 471     /*
 472      * Guaranteed-infallible append operations for use upon vectors whose
 473      * memory has been pre-reserved.  Don't use this if you haven't reserved the
 474      * memory!
 475      */
 476     template<typename U> void infallibleAppend(const U& u) {
 477       internalAppend(u);
 478     }
 479     void infallibleAppendN(const T& t, size_t n) {
 480       internalAppendN(t, n);
 481     }
 482     template<typename U> void infallibleAppend(const U* aBegin, const U* aEnd) {
 483       internalAppend(aBegin, PointerRangeSize(aBegin, aEnd));
 484     }
 485     template<typename U> void infallibleAppend(const U* aBegin, size_t aLength) {
 486       internalAppend(aBegin, aLength);
 487     }
 488
 489     void popBack();
 490
 491     T popCopy();
 492
 493     /**
 494      * Transfers ownership of the internal buffer used by this vector to the
 495      * caller.  (It's the caller's responsibility to properly deallocate this
 496      * buffer, in accordance with this vector's AllocPolicy.)  After this call,
 497      * the vector is empty.  Since the returned buffer may need to be allocated
 498      * (if the elements are currently stored in-place), the call can fail,
 499      * returning nullptr.
 500      *
 501      * N.B. Although a T*, only the range [0, length()) is constructed.
 502      */
 503     T* extractRawBuffer();
 504
 505     /**
 506      * Transfer ownership of an array of objects into the vector.  The caller
 507      * must have allocated the array in accordance with this vector's
 508      * AllocPolicy.
 509      *
 510      * N.B. This call assumes that there are no uninitialized elements in the
 511      *      passed array.
 512      */
 513     void replaceRawBuffer(T* p, size_t length);
 514
 515     /**
 516      * Places |val| at position |p|, shifting existing elements from |p| onward
 517      * one position higher.  On success, |p| should not be reused because it'll
 518      * be a dangling pointer if reallocation of the vector storage occurred; the
 519      * return value should be used instead.  On failure, nullptr is returned.
 520      *
 521      * Example usage:
 522      *
 523      *   if (!(p = vec.insert(p, val)))
 524      *     <handle failure>
 525      *   <keep working with p>
 526      *
 527      * This is inherently a linear-time operation.  Be careful!
 528      */
 529     T* insert(T* p, const T& val);
 530
 531     /**
 532      * Removes the element |t|, which must fall in the bounds [begin, end),
 533      * shifting existing elements from |t + 1| onward one position lower.
 534      */
 535     void erase(T* t);
 536
 537     /**
 538      * Measure the size of the vector's heap-allocated storage.
 539      */
 540     size_t sizeOfExcludingThis(MallocSizeOf mallocSizeOf) const;
 541
 542     /**
 543      * Like sizeOfExcludingThis, but also measures the size of the vector
 544      * object (which must be heap-allocated) itself.
 545      */
 546     size_t sizeOfIncludingThis(MallocSizeOf mallocSizeOf) const;
 547
 548     void swap(ThisVector& other);
 549
 550   private:
 551     VectorBase(const VectorBase&) MOZ_DELETE;
 552     void operator=(const VectorBase&) MOZ_DELETE;
 553 };
 554
 555 /* This does the re-entrancy check plus several other sanity checks. */
 556 #define MOZ_REENTRANCY_GUARD_ET_AL \
 557   ReentrancyGuard g(*this); \
 558   MOZ_ASSERT_IF(usingInlineStorage(), mCapacity == sInlineCapacity); \
 559   MOZ_ASSERT(reserved() <= mCapacity); \
 560   MOZ_ASSERT(mLength <= reserved()); \
 561   MOZ_ASSERT(mLength <= mCapacity)
 562
 563 /* Vector Implementation */
 564
 565 template<typename T, size_t N, class AP, class TV>
 566 MOZ_ALWAYS_INLINE
 567 VectorBase<T, N, AP, TV>::VectorBase(AP ap)
 568   : AP(ap),
 569     mLength(0),
 570     mCapacity(sInlineCapacity)
 571 #ifdef DEBUG
 572   , mReserved(sInlineCapacity),
 573     entered(false)
 574 #endif
 575 {
 576   mBegin = static_cast<T*>(storage.addr());
 577 }
 578
 579 /* Move constructor. */
 580 template<typename T, size_t N, class AllocPolicy, class TV>
 581 MOZ_ALWAYS_INLINE
 582 VectorBase<T, N, AllocPolicy, TV>::VectorBase(MoveRef<TV> rhs)
 583   : AllocPolicy(rhs)
 584 #ifdef DEBUG
 585     , entered(false)
 586 #endif
 587 {
 588   mLength = rhs->mLength;
 589   mCapacity = rhs->mCapacity;
 590 #ifdef DEBUG
 591   mReserved = rhs->mReserved;
 592 #endif
 593
 594   if (rhs->usingInlineStorage()) {
 595     /* We can't move the buffer over in this case, so copy elements. */
 596     mBegin = static_cast<T*>(storage.addr());
 597     Impl::moveConstruct(mBegin, rhs->beginNoCheck(), rhs->endNoCheck());
 598     /*
 599      * Leave rhs's mLength, mBegin, mCapacity, and mReserved as they are.
 600      * The elements in its in-line storage still need to be destroyed.
 601      */
 602   } else {
 603     /*
 604      * Take src's buffer, and turn src into an empty vector using
 605      * in-line storage.
 606      */
 607     mBegin = rhs->mBegin;
 608     rhs->mBegin = static_cast<T*>(rhs->storage.addr());
 609     rhs->mCapacity = sInlineCapacity;
 610     rhs->mLength = 0;
 611 #ifdef DEBUG
 612     rhs->mReserved = sInlineCapacity;
 613 #endif
 614   }
 615 }
 616
 617 /* Move assignment. */
 618 template<typename T, size_t N, class AP, class TV>
 619 MOZ_ALWAYS_INLINE
 620 TV&
 621 VectorBase<T, N, AP, TV>::operator=(MoveRef<TV> rhs)
 622 {
 623   TV* tv = static_cast<TV*>(this);
 624   tv->~TV();
 625   new(tv) TV(rhs);
 626   return *tv;
 627 }
 628
 629 template<typename T, size_t N, class AP, class TV>
 630 MOZ_ALWAYS_INLINE
 631 VectorBase<T, N, AP, TV>::~VectorBase()
 632 {
 633   MOZ_REENTRANCY_GUARD_ET_AL;
 634   Impl::destroy(beginNoCheck(), endNoCheck());
 635   if (!usingInlineStorage())
 636     this->free_(beginNoCheck());
 637 }
 638
 639 /*
 640  * This function will create a new heap buffer with capacity newCap,
 641  * move all elements in the inline buffer to this new buffer,
 642  * and fail on OOM.
 643  */
 644 template<typename T, size_t N, class AP, class TV>
 645 inline bool
 646 VectorBase<T, N, AP, TV>::convertToHeapStorage(size_t newCap)
 647 {
 648   MOZ_ASSERT(usingInlineStorage());
 649
 650   /* Allocate buffer. */
 651   MOZ_ASSERT(!detail::CapacityHasExcessSpace<T>(newCap));
 652   T* newBuf = reinterpret_cast<T*>(this->malloc_(newCap * sizeof(T)));
 653   if (!newBuf)
 654     return false;
 655
 656   /* Copy inline elements into heap buffer. */
 657   Impl::moveConstruct(newBuf, beginNoCheck(), endNoCheck());
 658   Impl::destroy(beginNoCheck(), endNoCheck());
 659
 660   /* Switch in heap buffer. */
 661   mBegin = newBuf;
 662   /* mLength is unchanged. */
 663   mCapacity = newCap;
 664   return true;
 665 }
 666
 667 template<typename T, size_t N, class AP, class TV>
 668 MOZ_NEVER_INLINE bool
 669 VectorBase<T, N, AP, TV>::growStorageBy(size_t incr)
 670 {
 671   MOZ_ASSERT(mLength + incr > mCapacity);
 672   MOZ_ASSERT_IF(!usingInlineStorage(),
 673                 !detail::CapacityHasExcessSpace<T>(mCapacity));
 674
 675   /*
 676    * When choosing a new capacity, its size should is as close to 2**N bytes
 677    * as possible.  2**N-sized requests are best because they are unlikely to
 678    * be rounded up by the allocator.  Asking for a 2**N number of elements
 679    * isn't as good, because if sizeof(T) is not a power-of-two that would
 680    * result in a non-2**N request size.
 681    */
 682
 683   size_t newCap;
 684
 685   if (incr == 1) {
 686     if (usingInlineStorage()) {
 687       /* This case occurs in ~70--80% of the calls to this function. */
 688       size_t newSize =
 689         tl::RoundUpPow2<(sInlineCapacity + 1) * sizeof(T)>::value;
 690       newCap = newSize / sizeof(T);
 691       goto convert;
 692     }
 693
 694     if (mLength == 0) {
 695       /* This case occurs in ~0--10% of the calls to this function. */
 696       newCap = 1;
 697       goto grow;
 698     }
 699
 700     /* This case occurs in ~15--20% of the calls to this function. */
 701
 702     /*
 703      * Will mLength * 4 *sizeof(T) overflow?  This condition limits a vector
 704      * to 1GB of memory on a 32-bit system, which is a reasonable limit.  It
 705      * also ensures that
 706      *
 707      *   static_cast<char*>(end()) - static_cast<char*>(begin())
 708      *
 709      * doesn't overflow ptrdiff_t (see bug 510319).
 710      */
 711     if (mLength & tl::MulOverflowMask<4 * sizeof(T)>::value) {
 712       this->reportAllocOverflow();
 713       return false;
 714     }
 715
 716     /*
 717      * If we reach here, the existing capacity will have a size that is already
 718      * as close to 2^N as sizeof(T) will allow.  Just double the capacity, and
 719      * then there might be space for one more element.
 720      */
 721     newCap = mLength * 2;
 722     if (detail::CapacityHasExcessSpace<T>(newCap))
 723       newCap += 1;
 724   } else {
 725     /* This case occurs in ~2% of the calls to this function. */
 726     size_t newMinCap = mLength + incr;
 727
 728     /* Did mLength + incr overflow?  Will newCap * sizeof(T) overflow? */
 729     if (newMinCap < mLength ||
 730         newMinCap & tl::MulOverflowMask<2 * sizeof(T)>::value)
 731     {
 732       this->reportAllocOverflow();
 733       return false;
 734     }
 735
 736     size_t newMinSize = newMinCap * sizeof(T);
 737     size_t newSize = RoundUpPow2(newMinSize);
 738     newCap = newSize / sizeof(T);
 739   }
 740
 741   if (usingInlineStorage()) {
 742   convert:
 743     return convertToHeapStorage(newCap);
 744   }
 745
 746 grow:
 747   return Impl::growTo(*this, newCap);
 748 }
 749
 750 template<typename T, size_t N, class AP, class TV>
 751 inline bool
 752 VectorBase<T, N, AP, TV>::initCapacity(size_t request)
 753 {
 754   MOZ_ASSERT(empty());
 755   MOZ_ASSERT(usingInlineStorage());
 756   if (request == 0)
 757     return true;
 758   T* newbuf = reinterpret_cast<T*>(this->malloc_(request * sizeof(T)));
 759   if (!newbuf)
 760     return false;
 761   mBegin = newbuf;
 762   mCapacity = request;
 763 #ifdef DEBUG
 764   mReserved = request;
 765 #endif
 766   return true;
 767 }
 768
 769 template<typename T, size_t N, class AP, class TV>
 770 inline bool
 771 VectorBase<T, N, AP, TV>::reserve(size_t request)
 772 {
 773   MOZ_REENTRANCY_GUARD_ET_AL;
 774   if (request > mCapacity && !growStorageBy(request - mLength))
 775     return false;
 776
 777 #ifdef DEBUG
 778   if (request > mReserved)
 779     mReserved = request;
 780   MOZ_ASSERT(mLength <= mReserved);
 781   MOZ_ASSERT(mReserved <= mCapacity);
 782 #endif
 783   return true;
 784 }
 785
 786 template<typename T, size_t N, class AP, class TV>
 787 inline void
 788 VectorBase<T, N, AP, TV>::shrinkBy(size_t incr)
 789 {
 790   MOZ_REENTRANCY_GUARD_ET_AL;
 791   MOZ_ASSERT(incr <= mLength);
 792   Impl::destroy(endNoCheck() - incr, endNoCheck());
 793   mLength -= incr;
 794 }
 795
 796 template<typename T, size_t N, class AP, class TV>
 797 MOZ_ALWAYS_INLINE bool
 798 VectorBase<T, N, AP, TV>::growBy(size_t incr)
 799 {
 800   MOZ_REENTRANCY_GUARD_ET_AL;
 801   if (incr > mCapacity - mLength && !growStorageBy(incr))
 802     return false;
 803
 804   MOZ_ASSERT(mLength + incr <= mCapacity);
 805   T* newend = endNoCheck() + incr;
 806   Impl::initialize(endNoCheck(), newend);
 807   mLength += incr;
 808 #ifdef DEBUG
 809   if (mLength > mReserved)
 810     mReserved = mLength;
 811 #endif
 812   return true;
 813 }
 814
 815 template<typename T, size_t N, class AP, class TV>
 816 MOZ_ALWAYS_INLINE bool
 817 VectorBase<T, N, AP, TV>::growByUninitialized(size_t incr)
 818 {
 819   MOZ_REENTRANCY_GUARD_ET_AL;
 820   if (incr > mCapacity - mLength && !growStorageBy(incr))
 821     return false;
 822
 823   MOZ_ASSERT(mLength + incr <= mCapacity);
 824   mLength += incr;
 825 #ifdef DEBUG
 826   if (mLength > mReserved)
 827     mReserved = mLength;
 828 #endif
 829   return true;
 830 }
 831
 832 template<typename T, size_t N, class AP, class TV>
 833 inline bool
 834 VectorBase<T, N, AP, TV>::resize(size_t newLength)
 835 {
 836   size_t curLength = mLength;
 837   if (newLength > curLength)
 838     return growBy(newLength - curLength);
 839   shrinkBy(curLength - newLength);
 840   return true;
 841 }
 842
 843 template<typename T, size_t N, class AP, class TV>
 844 MOZ_ALWAYS_INLINE bool
 845 VectorBase<T, N, AP, TV>::resizeUninitialized(size_t newLength)
 846 {
 847   size_t curLength = mLength;
 848   if (newLength > curLength)
 849     return growByUninitialized(newLength - curLength);
 850   shrinkBy(curLength - newLength);
 851   return true;
 852 }
 853
 854 template<typename T, size_t N, class AP, class TV>
 855 inline void
 856 VectorBase<T, N, AP, TV>::clear()
 857 {
 858   MOZ_REENTRANCY_GUARD_ET_AL;
 859   Impl::destroy(beginNoCheck(), endNoCheck());
 860   mLength = 0;
 861 }
 862
 863 template<typename T, size_t N, class AP, class TV>
 864 inline void
 865 VectorBase<T, N, AP, TV>::clearAndFree()
 866 {
 867   clear();
 868
 869   if (usingInlineStorage())
 870     return;
 871
 872   this->free_(beginNoCheck());
 873   mBegin = static_cast<T*>(storage.addr());
 874   mCapacity = sInlineCapacity;
 875 #ifdef DEBUG
 876   mReserved = sInlineCapacity;
 877 #endif
 878 }
 879
 880 template<typename T, size_t N, class AP, class TV>
 881 inline bool
 882 VectorBase<T, N, AP, TV>::canAppendWithoutRealloc(size_t needed) const
 883 {
 884   return mLength + needed <= mCapacity;
 885 }
 886
 887 template<typename T, size_t N, class AP, class TV>
 888 template<typename U, size_t O, class BP, class UV>
 889 MOZ_ALWAYS_INLINE void
 890 VectorBase<T, N, AP, TV>::internalAppendAll(const VectorBase<U, O, BP, UV>& other)
 891 {
 892   internalAppend(other.begin(), other.length());
 893 }
 894
 895 template<typename T, size_t N, class AP, class TV>
 896 template<typename U>
 897 MOZ_ALWAYS_INLINE void
 898 VectorBase<T, N, AP, TV>::internalAppend(const U& u)
 899 {
 900   MOZ_ASSERT(mLength + 1 <= mReserved);
 901   MOZ_ASSERT(mReserved <= mCapacity);
 902   new(endNoCheck()) T(u);
 903   ++mLength;
 904 }
 905
 906 template<typename T, size_t N, class AP, class TV>
 907 MOZ_ALWAYS_INLINE bool
 908 VectorBase<T, N, AP, TV>::appendN(const T& t, size_t needed)
 909 {
 910   MOZ_REENTRANCY_GUARD_ET_AL;
 911   if (mLength + needed > mCapacity && !growStorageBy(needed))
 912     return false;
 913
 914 #ifdef DEBUG
 915   if (mLength + needed > mReserved)
 916     mReserved = mLength + needed;
 917 #endif
 918   internalAppendN(t, needed);
 919   return true;
 920 }
 921
 922 template<typename T, size_t N, class AP, class TV>
 923 MOZ_ALWAYS_INLINE void
 924 VectorBase<T, N, AP, TV>::internalAppendN(const T& t, size_t needed)
 925 {
 926   MOZ_ASSERT(mLength + needed <= mReserved);
 927   MOZ_ASSERT(mReserved <= mCapacity);
 928   Impl::copyConstructN(endNoCheck(), needed, t);
 929   mLength += needed;
 930 }
 931
 932 template<typename T, size_t N, class AP, class TV>
 933 inline T*
 934 VectorBase<T, N, AP, TV>::insert(T* p, const T& val)
 935 {
 936   MOZ_ASSERT(begin() <= p);
 937   MOZ_ASSERT(p <= end());
 938   size_t pos = p - begin();
 939   MOZ_ASSERT(pos <= mLength);
 940   size_t oldLength = mLength;
 941   if (pos == oldLength) {
 942     if (!append(val))
 943       return nullptr;
 944   } else {
 945     T oldBack = back();
 946     if (!append(oldBack)) /* Dup the last element. */
 947       return nullptr;
 948     for (size_t i = oldLength; i > pos; --i)
 949       (*this)[i] = (*this)[i - 1];
 950     (*this)[pos] = val;
 951   }
 952   return begin() + pos;
 953 }
 954
 955 template<typename T, size_t N, class AP, class TV>
 956 inline void
 957 VectorBase<T, N, AP, TV>::erase(T* it)
 958 {
 959   MOZ_ASSERT(begin() <= it);
 960   MOZ_ASSERT(it < end());
 961   while (it + 1 < end()) {
 962     *it = *(it + 1);
 963     ++it;
 964   }
 965   popBack();
 966 }
 967
 968 template<typename T, size_t N, class AP, class TV>
 969 template<typename U>
 970 MOZ_ALWAYS_INLINE bool
 971 VectorBase<T, N, AP, TV>::append(const U* insBegin, const U* insEnd)
 972 {
 973   MOZ_REENTRANCY_GUARD_ET_AL;
 974   size_t needed = PointerRangeSize(insBegin, insEnd);
 975   if (mLength + needed > mCapacity && !growStorageBy(needed))
 976     return false;
 977
 978 #ifdef DEBUG
 979   if (mLength + needed > mReserved)
 980     mReserved = mLength + needed;
 981 #endif
 982   internalAppend(insBegin, needed);
 983   return true;
 984 }
 985
 986 template<typename T, size_t N, class AP, class TV>
 987 template<typename U>
 988 MOZ_ALWAYS_INLINE void
 989 VectorBase<T, N, AP, TV>::internalAppend(const U* insBegin, size_t insLength)
 990 {
 991   MOZ_ASSERT(mLength + insLength <= mReserved);
 992   MOZ_ASSERT(mReserved <= mCapacity);
 993   Impl::copyConstruct(endNoCheck(), insBegin, insBegin + insLength);
 994   mLength += insLength;
 995 }
 996
 997 template<typename T, size_t N, class AP, class TV>
 998 template<typename U>
 999 MOZ_ALWAYS_INLINE bool
1000 VectorBase<T, N, AP, TV>::append(const U& u)
1001 {
1002   MOZ_REENTRANCY_GUARD_ET_AL;
1003   if (mLength == mCapacity && !growStorageBy(1))
1004     return false;
1005
1006 #ifdef DEBUG
1007   if (mLength + 1 > mReserved)
1008     mReserved = mLength + 1;
1009 #endif
1010   internalAppend(u);
1011   return true;
1012 }
1013
1014 template<typename T, size_t N, class AP, class TV>
1015 template<typename U, size_t O, class BP, class UV>
1016 MOZ_ALWAYS_INLINE bool
1017 VectorBase<T, N, AP, TV>::appendAll(const VectorBase<U, O, BP, UV>& other)
1018 {
1019   return append(other.begin(), other.length());
1020 }
1021
1022 template<typename T, size_t N, class AP, class TV>
1023 template<class U>
1024 MOZ_ALWAYS_INLINE bool
1025 VectorBase<T, N, AP, TV>::append(const U *insBegin, size_t insLength)
1026 {
1027   return append(insBegin, insBegin + insLength);
1028 }
1029
1030 template<typename T, size_t N, class AP, class TV>
1031 MOZ_ALWAYS_INLINE void
1032 VectorBase<T, N, AP, TV>::popBack()
1033 {
1034   MOZ_REENTRANCY_GUARD_ET_AL;
1035   MOZ_ASSERT(!empty());
1036   --mLength;
1037   endNoCheck()->~T();
1038 }
1039
1040 template<typename T, size_t N, class AP, class TV>
1041 MOZ_ALWAYS_INLINE T
1042 VectorBase<T, N, AP, TV>::popCopy()
1043 {
1044   T ret = back();
1045   popBack();
1046   return ret;
1047 }
1048
1049 template<typename T, size_t N, class AP, class TV>
1050 inline T*
1051 VectorBase<T, N, AP, TV>::extractRawBuffer()
1052 {
1053   T* ret;
1054   if (usingInlineStorage()) {
1055     ret = reinterpret_cast<T*>(this->malloc_(mLength * sizeof(T)));
1056     if (!ret)
1057       return nullptr;
1058     Impl::copyConstruct(ret, beginNoCheck(), endNoCheck());
1059     Impl::destroy(beginNoCheck(), endNoCheck());
1060     /* mBegin, mCapacity are unchanged. */
1061     mLength = 0;
1062   } else {
1063     ret = mBegin;
1064     mBegin = static_cast<T*>(storage.addr());
1065     mLength = 0;
1066     mCapacity = sInlineCapacity;
1067 #ifdef DEBUG
1068     mReserved = sInlineCapacity;
1069 #endif
1070   }
1071   return ret;
1072 }
1073
1074 template<typename T, size_t N, class AP, class TV>
1075 inline void
1076 VectorBase<T, N, AP, TV>::replaceRawBuffer(T* p, size_t aLength)
1077 {
1078   MOZ_REENTRANCY_GUARD_ET_AL;
1079
1080   /* Destroy what we have. */
1081   Impl::destroy(beginNoCheck(), endNoCheck());
1082   if (!usingInlineStorage())
1083     this->free_(beginNoCheck());
1084
1085   /* Take in the new buffer. */
1086   if (aLength <= sInlineCapacity) {
1087     /*
1088      * We convert to inline storage if possible, even though p might
1089      * otherwise be acceptable.  Maybe this behaviour should be
1090      * specifiable with an argument to this function.
1091      */
1092     mBegin = static_cast<T*>(storage.addr());
1093     mLength = aLength;
1094     mCapacity = sInlineCapacity;
1095     Impl::moveConstruct(mBegin, p, p + aLength);
1096     Impl::destroy(p, p + aLength);
1097     this->free_(p);
1098   } else {
1099     mBegin = p;
1100     mLength = aLength;
1101     mCapacity = aLength;
1102   }
1103 #ifdef DEBUG
1104   mReserved = aLength;
1105 #endif
1106 }
1107
1108 template<typename T, size_t N, class AP, class TV>
1109 inline size_t
1110 VectorBase<T, N, AP, TV>::sizeOfExcludingThis(MallocSizeOf mallocSizeOf) const
1111 {
1112   return usingInlineStorage() ? 0 : mallocSizeOf(beginNoCheck());
1113 }
1114
1115 template<typename T, size_t N, class AP, class TV>
1116 inline size_t
1117 VectorBase<T, N, AP, TV>::sizeOfIncludingThis(MallocSizeOf mallocSizeOf) const
1118 {
1119   return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
1120 }
1121
1122 template<typename T, size_t N, class AP, class TV>
1123 inline void
1124 VectorBase<T, N, AP, TV>::swap(TV& other)
1125 {
1126   static_assert(N == 0,
1127                 "still need to implement this for N != 0");
1128
1129   // This only works when inline storage is always empty.
1130   if (!usingInlineStorage() && other.usingInlineStorage()) {
1131     other.mBegin = mBegin;
1132     mBegin = inlineStorage();
1133   } else if (usingInlineStorage() && !other.usingInlineStorage()) {
1134     mBegin = other.mBegin;
1135     other.mBegin = other.inlineStorage();
1136   } else if (!usingInlineStorage() && !other.usingInlineStorage()) {
1137     Swap(mBegin, other.mBegin);
1138   } else {
1139     // This case is a no-op, since we'd set both to use their inline storage.
1140   }
1141
1142   Swap(mLength, other.mLength);
1143   Swap(mCapacity, other.mCapacity);
1144 #ifdef DEBUG
1145   Swap(mReserved, other.mReserved);
1146 #endif
1147 }
1148
1149 /*
1150  * STL-like container providing a short-lived, dynamic buffer.  Vector calls the
1151  * constructors/destructors of all elements stored in its internal buffer, so
1152  * non-PODs may be safely used.  Additionally, Vector will store the first N
1153  * elements in-place before resorting to dynamic allocation.
1154  *
1155  * T requirements:
1156  *  - default and copy constructible, assignable, destructible
1157  *  - operations do not throw
1158  * N requirements:
1159  *  - any value, however, N is clamped to min/max values
1160  * AllocPolicy:
1161  *  - see "Allocation policies" in AllocPolicy.h (defaults to
1162  *    mozilla::MallocAllocPolicy)
1163  *
1164  * Vector is not reentrant: T member functions called during Vector member
1165  * functions must not call back into the same object!
1166  */
1167 template<typename T,
1168          size_t MinInlineCapacity = 0,
1169          class AllocPolicy = MallocAllocPolicy>
1170 class Vector
1171   : public VectorBase<T,
1172                       MinInlineCapacity,
1173                       AllocPolicy,
1174                       Vector<T, MinInlineCapacity, AllocPolicy> >
1175 {
1176     typedef VectorBase<T, MinInlineCapacity, AllocPolicy, Vector> Base;
1177
1178   public:
1179     Vector(AllocPolicy alloc = AllocPolicy()) : Base(alloc) {}
1180     Vector(mozilla::MoveRef<Vector> vec) : Base(vec) {}
1181     Vector& operator=(mozilla::MoveRef<Vector> vec) {
1182       return Base::operator=(vec);
1183     }
1184 };
1185
1186 } // namespace mozilla
1187
1188 #ifdef _MSC_VER
1189 #pragma warning(pop)
1190 #endif
1191
1192 #endif /* mozilla_Vector_h */