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, U* srcbeg, U* srcend) {
  88       for (U* p = srcbeg; p < srcend; ++p, ++dst)
  89         new(dst) T(Move(*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(Move(*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(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(ThisVector&&); /* Move constructor. */
 318     ThisVector& operator=(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     /** Potentially fallible append operations. */
 457
 458     /**
 459      * This can take either a T& or a T&&. Given a T&&, it moves |u| into the
 460      * vector, instead of copying it. If it fails, |u| is left unmoved. ("We are
 461      * not amused.")
 462      */
 463     template<typename U> bool append(U&& u);
 464
 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(U&& u) {
 477       internalAppend(Forward<U>(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     template<typename U>
 530     T* insert(T* p, U&& val);
 531
 532     /**
 533      * Removes the element |t|, which must fall in the bounds [begin, end),
 534      * shifting existing elements from |t + 1| onward one position lower.
 535      */
 536     void erase(T* t);
 537
 538     /**
 539      * Measure the size of the vector's heap-allocated storage.
 540      */
 541     size_t sizeOfExcludingThis(MallocSizeOf mallocSizeOf) const;
 542
 543     /**
 544      * Like sizeOfExcludingThis, but also measures the size of the vector
 545      * object (which must be heap-allocated) itself.
 546      */
 547     size_t sizeOfIncludingThis(MallocSizeOf mallocSizeOf) const;
 548
 549     void swap(ThisVector& other);
 550
 551   private:
 552     VectorBase(const VectorBase&) MOZ_DELETE;
 553     void operator=(const VectorBase&) MOZ_DELETE;
 554
 555     /* Move-construct/assign only from our derived class, ThisVector. */
 556     VectorBase(VectorBase&&) MOZ_DELETE;
 557     void operator=(VectorBase&&) MOZ_DELETE;
 558 };
 559
 560 /* This does the re-entrancy check plus several other sanity checks. */
 561 #define MOZ_REENTRANCY_GUARD_ET_AL \
 562   ReentrancyGuard g(*this); \
 563   MOZ_ASSERT_IF(usingInlineStorage(), mCapacity == sInlineCapacity); \
 564   MOZ_ASSERT(reserved() <= mCapacity); \
 565   MOZ_ASSERT(mLength <= reserved()); \
 566   MOZ_ASSERT(mLength <= mCapacity)
 567
 568 /* Vector Implementation */
 569
 570 template<typename T, size_t N, class AP, class TV>
 571 MOZ_ALWAYS_INLINE
 572 VectorBase<T, N, AP, TV>::VectorBase(AP ap)
 573   : AP(ap),
 574     mLength(0),
 575     mCapacity(sInlineCapacity)
 576 #ifdef DEBUG
 577   , mReserved(sInlineCapacity),
 578     entered(false)
 579 #endif
 580 {
 581   mBegin = static_cast<T*>(storage.addr());
 582 }
 583
 584 /* Move constructor. */
 585 template<typename T, size_t N, class AllocPolicy, class TV>
 586 MOZ_ALWAYS_INLINE
 587 VectorBase<T, N, AllocPolicy, TV>::VectorBase(TV&& rhs)
 588   : AllocPolicy(Move(rhs))
 589 #ifdef DEBUG
 590     , entered(false)
 591 #endif
 592 {
 593   mLength = rhs.mLength;
 594   mCapacity = rhs.mCapacity;
 595 #ifdef DEBUG
 596   mReserved = rhs.mReserved;
 597 #endif
 598
 599   if (rhs.usingInlineStorage()) {
 600     /* We can't move the buffer over in this case, so copy elements. */
 601     mBegin = static_cast<T*>(storage.addr());
 602     Impl::moveConstruct(mBegin, rhs.beginNoCheck(), rhs.endNoCheck());
 603     /*
 604      * Leave rhs's mLength, mBegin, mCapacity, and mReserved as they are.
 605      * The elements in its in-line storage still need to be destroyed.
 606      */
 607   } else {
 608     /*
 609      * Take src's buffer, and turn src into an empty vector using
 610      * in-line storage.
 611      */
 612     mBegin = rhs.mBegin;
 613     rhs.mBegin = static_cast<T*>(rhs.storage.addr());
 614     rhs.mCapacity = sInlineCapacity;
 615     rhs.mLength = 0;
 616 #ifdef DEBUG
 617     rhs.mReserved = sInlineCapacity;
 618 #endif
 619   }
 620 }
 621
 622 /* Move assignment. */
 623 template<typename T, size_t N, class AP, class TV>
 624 MOZ_ALWAYS_INLINE
 625 TV&
 626 VectorBase<T, N, AP, TV>::operator=(TV&& rhs)
 627 {
 628   MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
 629   TV* tv = static_cast<TV*>(this);
 630   tv->~TV();
 631   new(tv) TV(Move(rhs));
 632   return *tv;
 633 }
 634
 635 template<typename T, size_t N, class AP, class TV>
 636 MOZ_ALWAYS_INLINE
 637 VectorBase<T, N, AP, TV>::~VectorBase()
 638 {
 639   MOZ_REENTRANCY_GUARD_ET_AL;
 640   Impl::destroy(beginNoCheck(), endNoCheck());
 641   if (!usingInlineStorage())
 642     this->free_(beginNoCheck());
 643 }
 644
 645 /*
 646  * This function will create a new heap buffer with capacity newCap,
 647  * move all elements in the inline buffer to this new buffer,
 648  * and fail on OOM.
 649  */
 650 template<typename T, size_t N, class AP, class TV>
 651 inline bool
 652 VectorBase<T, N, AP, TV>::convertToHeapStorage(size_t newCap)
 653 {
 654   MOZ_ASSERT(usingInlineStorage());
 655
 656   /* Allocate buffer. */
 657   MOZ_ASSERT(!detail::CapacityHasExcessSpace<T>(newCap));
 658   T* newBuf = reinterpret_cast<T*>(this->malloc_(newCap * sizeof(T)));
 659   if (!newBuf)
 660     return false;
 661
 662   /* Copy inline elements into heap buffer. */
 663   Impl::moveConstruct(newBuf, beginNoCheck(), endNoCheck());
 664   Impl::destroy(beginNoCheck(), endNoCheck());
 665
 666   /* Switch in heap buffer. */
 667   mBegin = newBuf;
 668   /* mLength is unchanged. */
 669   mCapacity = newCap;
 670   return true;
 671 }
 672
 673 template<typename T, size_t N, class AP, class TV>
 674 MOZ_NEVER_INLINE bool
 675 VectorBase<T, N, AP, TV>::growStorageBy(size_t incr)
 676 {
 677   MOZ_ASSERT(mLength + incr > mCapacity);
 678   MOZ_ASSERT_IF(!usingInlineStorage(),
 679                 !detail::CapacityHasExcessSpace<T>(mCapacity));
 680
 681   /*
 682    * When choosing a new capacity, its size should is as close to 2**N bytes
 683    * as possible.  2**N-sized requests are best because they are unlikely to
 684    * be rounded up by the allocator.  Asking for a 2**N number of elements
 685    * isn't as good, because if sizeof(T) is not a power-of-two that would
 686    * result in a non-2**N request size.
 687    */
 688
 689   size_t newCap;
 690
 691   if (incr == 1) {
 692     if (usingInlineStorage()) {
 693       /* This case occurs in ~70--80% of the calls to this function. */
 694       size_t newSize =
 695         tl::RoundUpPow2<(sInlineCapacity + 1) * sizeof(T)>::value;
 696       newCap = newSize / sizeof(T);
 697       goto convert;
 698     }
 699
 700     if (mLength == 0) {
 701       /* This case occurs in ~0--10% of the calls to this function. */
 702       newCap = 1;
 703       goto grow;
 704     }
 705
 706     /* This case occurs in ~15--20% of the calls to this function. */
 707
 708     /*
 709      * Will mLength * 4 *sizeof(T) overflow?  This condition limits a vector
 710      * to 1GB of memory on a 32-bit system, which is a reasonable limit.  It
 711      * also ensures that
 712      *
 713      *   static_cast<char*>(end()) - static_cast<char*>(begin())
 714      *
 715      * doesn't overflow ptrdiff_t (see bug 510319).
 716      */
 717     if (mLength & tl::MulOverflowMask<4 * sizeof(T)>::value) {
 718       this->reportAllocOverflow();
 719       return false;
 720     }
 721
 722     /*
 723      * If we reach here, the existing capacity will have a size that is already
 724      * as close to 2^N as sizeof(T) will allow.  Just double the capacity, and
 725      * then there might be space for one more element.
 726      */
 727     newCap = mLength * 2;
 728     if (detail::CapacityHasExcessSpace<T>(newCap))
 729       newCap += 1;
 730   } else {
 731     /* This case occurs in ~2% of the calls to this function. */
 732     size_t newMinCap = mLength + incr;
 733
 734     /* Did mLength + incr overflow?  Will newCap * sizeof(T) overflow? */
 735     if (newMinCap < mLength ||
 736         newMinCap & tl::MulOverflowMask<2 * sizeof(T)>::value)
 737     {
 738       this->reportAllocOverflow();
 739       return false;
 740     }
 741
 742     size_t newMinSize = newMinCap * sizeof(T);
 743     size_t newSize = RoundUpPow2(newMinSize);
 744     newCap = newSize / sizeof(T);
 745   }
 746
 747   if (usingInlineStorage()) {
 748   convert:
 749     return convertToHeapStorage(newCap);
 750   }
 751
 752 grow:
 753   return Impl::growTo(*this, newCap);
 754 }
 755
 756 template<typename T, size_t N, class AP, class TV>
 757 inline bool
 758 VectorBase<T, N, AP, TV>::initCapacity(size_t request)
 759 {
 760   MOZ_ASSERT(empty());
 761   MOZ_ASSERT(usingInlineStorage());
 762   if (request == 0)
 763     return true;
 764   T* newbuf = reinterpret_cast<T*>(this->malloc_(request * sizeof(T)));
 765   if (!newbuf)
 766     return false;
 767   mBegin = newbuf;
 768   mCapacity = request;
 769 #ifdef DEBUG
 770   mReserved = request;
 771 #endif
 772   return true;
 773 }
 774
 775 template<typename T, size_t N, class AP, class TV>
 776 inline bool
 777 VectorBase<T, N, AP, TV>::reserve(size_t request)
 778 {
 779   MOZ_REENTRANCY_GUARD_ET_AL;
 780   if (request > mCapacity && !growStorageBy(request - mLength))
 781     return false;
 782
 783 #ifdef DEBUG
 784   if (request > mReserved)
 785     mReserved = request;
 786   MOZ_ASSERT(mLength <= mReserved);
 787   MOZ_ASSERT(mReserved <= mCapacity);
 788 #endif
 789   return true;
 790 }
 791
 792 template<typename T, size_t N, class AP, class TV>
 793 inline void
 794 VectorBase<T, N, AP, TV>::shrinkBy(size_t incr)
 795 {
 796   MOZ_REENTRANCY_GUARD_ET_AL;
 797   MOZ_ASSERT(incr <= mLength);
 798   Impl::destroy(endNoCheck() - incr, endNoCheck());
 799   mLength -= incr;
 800 }
 801
 802 template<typename T, size_t N, class AP, class TV>
 803 MOZ_ALWAYS_INLINE bool
 804 VectorBase<T, N, AP, TV>::growBy(size_t incr)
 805 {
 806   MOZ_REENTRANCY_GUARD_ET_AL;
 807   if (incr > mCapacity - mLength && !growStorageBy(incr))
 808     return false;
 809
 810   MOZ_ASSERT(mLength + incr <= mCapacity);
 811   T* newend = endNoCheck() + incr;
 812   Impl::initialize(endNoCheck(), newend);
 813   mLength += incr;
 814 #ifdef DEBUG
 815   if (mLength > mReserved)
 816     mReserved = mLength;
 817 #endif
 818   return true;
 819 }
 820
 821 template<typename T, size_t N, class AP, class TV>
 822 MOZ_ALWAYS_INLINE bool
 823 VectorBase<T, N, AP, TV>::growByUninitialized(size_t incr)
 824 {
 825   MOZ_REENTRANCY_GUARD_ET_AL;
 826   if (incr > mCapacity - mLength && !growStorageBy(incr))
 827     return false;
 828
 829   MOZ_ASSERT(mLength + incr <= mCapacity);
 830   mLength += incr;
 831 #ifdef DEBUG
 832   if (mLength > mReserved)
 833     mReserved = mLength;
 834 #endif
 835   return true;
 836 }
 837
 838 template<typename T, size_t N, class AP, class TV>
 839 inline bool
 840 VectorBase<T, N, AP, TV>::resize(size_t newLength)
 841 {
 842   size_t curLength = mLength;
 843   if (newLength > curLength)
 844     return growBy(newLength - curLength);
 845   shrinkBy(curLength - newLength);
 846   return true;
 847 }
 848
 849 template<typename T, size_t N, class AP, class TV>
 850 MOZ_ALWAYS_INLINE bool
 851 VectorBase<T, N, AP, TV>::resizeUninitialized(size_t newLength)
 852 {
 853   size_t curLength = mLength;
 854   if (newLength > curLength)
 855     return growByUninitialized(newLength - curLength);
 856   shrinkBy(curLength - newLength);
 857   return true;
 858 }
 859
 860 template<typename T, size_t N, class AP, class TV>
 861 inline void
 862 VectorBase<T, N, AP, TV>::clear()
 863 {
 864   MOZ_REENTRANCY_GUARD_ET_AL;
 865   Impl::destroy(beginNoCheck(), endNoCheck());
 866   mLength = 0;
 867 }
 868
 869 template<typename T, size_t N, class AP, class TV>
 870 inline void
 871 VectorBase<T, N, AP, TV>::clearAndFree()
 872 {
 873   clear();
 874
 875   if (usingInlineStorage())
 876     return;
 877
 878   this->free_(beginNoCheck());
 879   mBegin = static_cast<T*>(storage.addr());
 880   mCapacity = sInlineCapacity;
 881 #ifdef DEBUG
 882   mReserved = sInlineCapacity;
 883 #endif
 884 }
 885
 886 template<typename T, size_t N, class AP, class TV>
 887 inline bool
 888 VectorBase<T, N, AP, TV>::canAppendWithoutRealloc(size_t needed) const
 889 {
 890   return mLength + needed <= mCapacity;
 891 }
 892
 893 template<typename T, size_t N, class AP, class TV>
 894 template<typename U, size_t O, class BP, class UV>
 895 MOZ_ALWAYS_INLINE void
 896 VectorBase<T, N, AP, TV>::internalAppendAll(const VectorBase<U, O, BP, UV>& other)
 897 {
 898   internalAppend(other.begin(), other.length());
 899 }
 900
 901 template<typename T, size_t N, class AP, class TV>
 902 template<typename U>
 903 MOZ_ALWAYS_INLINE void
 904 VectorBase<T, N, AP, TV>::internalAppend(U&& u)
 905 {
 906   MOZ_ASSERT(mLength + 1 <= mReserved);
 907   MOZ_ASSERT(mReserved <= mCapacity);
 908   new(endNoCheck()) T(Forward<U>(u));
 909   ++mLength;
 910 }
 911
 912 template<typename T, size_t N, class AP, class TV>
 913 MOZ_ALWAYS_INLINE bool
 914 VectorBase<T, N, AP, TV>::appendN(const T& t, size_t needed)
 915 {
 916   MOZ_REENTRANCY_GUARD_ET_AL;
 917   if (mLength + needed > mCapacity && !growStorageBy(needed))
 918     return false;
 919
 920 #ifdef DEBUG
 921   if (mLength + needed > mReserved)
 922     mReserved = mLength + needed;
 923 #endif
 924   internalAppendN(t, needed);
 925   return true;
 926 }
 927
 928 template<typename T, size_t N, class AP, class TV>
 929 MOZ_ALWAYS_INLINE void
 930 VectorBase<T, N, AP, TV>::internalAppendN(const T& t, size_t needed)
 931 {
 932   MOZ_ASSERT(mLength + needed <= mReserved);
 933   MOZ_ASSERT(mReserved <= mCapacity);
 934   Impl::copyConstructN(endNoCheck(), needed, t);
 935   mLength += needed;
 936 }
 937
 938 template<typename T, size_t N, class AP, class TV>
 939 template<typename U>
 940 inline T*
 941 VectorBase<T, N, AP, TV>::insert(T* p, U&& val)
 942 {
 943   MOZ_ASSERT(begin() <= p);
 944   MOZ_ASSERT(p <= end());
 945   size_t pos = p - begin();
 946   MOZ_ASSERT(pos <= mLength);
 947   size_t oldLength = mLength;
 948   if (pos == oldLength) {
 949     if (!append(Forward<U>(val)))
 950       return nullptr;
 951   } else {
 952     T oldBack = Move(back());
 953     if (!append(Move(oldBack))) /* Dup the last element. */
 954       return nullptr;
 955     for (size_t i = oldLength; i > pos; --i)
 956       (*this)[i] = Move((*this)[i - 1]);
 957     (*this)[pos] = Forward<U>(val);
 958   }
 959   return begin() + pos;
 960 }
 961
 962 template<typename T, size_t N, class AP, class TV>
 963 inline void
 964 VectorBase<T, N, AP, TV>::erase(T* it)
 965 {
 966   MOZ_ASSERT(begin() <= it);
 967   MOZ_ASSERT(it < end());
 968   while (it + 1 < end()) {
 969     *it = *(it + 1);
 970     ++it;
 971   }
 972   popBack();
 973 }
 974
 975 template<typename T, size_t N, class AP, class TV>
 976 template<typename U>
 977 MOZ_ALWAYS_INLINE bool
 978 VectorBase<T, N, AP, TV>::append(const U* insBegin, const U* insEnd)
 979 {
 980   MOZ_REENTRANCY_GUARD_ET_AL;
 981   size_t needed = PointerRangeSize(insBegin, insEnd);
 982   if (mLength + needed > mCapacity && !growStorageBy(needed))
 983     return false;
 984
 985 #ifdef DEBUG
 986   if (mLength + needed > mReserved)
 987     mReserved = mLength + needed;
 988 #endif
 989   internalAppend(insBegin, needed);
 990   return true;
 991 }
 992
 993 template<typename T, size_t N, class AP, class TV>
 994 template<typename U>
 995 MOZ_ALWAYS_INLINE void
 996 VectorBase<T, N, AP, TV>::internalAppend(const U* insBegin, size_t insLength)
 997 {
 998   MOZ_ASSERT(mLength + insLength <= mReserved);
 999   MOZ_ASSERT(mReserved <= mCapacity);
1000   Impl::copyConstruct(endNoCheck(), insBegin, insBegin + insLength);
1001   mLength += insLength;
1002 }
1003
1004 template<typename T, size_t N, class AP, class TV>
1005 template<typename U>
1006 MOZ_ALWAYS_INLINE bool
1007 VectorBase<T, N, AP, TV>::append(U&& u)
1008 {
1009   MOZ_REENTRANCY_GUARD_ET_AL;
1010   if (mLength == mCapacity && !growStorageBy(1))
1011     return false;
1012
1013 #ifdef DEBUG
1014   if (mLength + 1 > mReserved)
1015     mReserved = mLength + 1;
1016 #endif
1017   internalAppend(Forward<U>(u));
1018   return true;
1019 }
1020
1021 template<typename T, size_t N, class AP, class TV>
1022 template<typename U, size_t O, class BP, class UV>
1023 MOZ_ALWAYS_INLINE bool
1024 VectorBase<T, N, AP, TV>::appendAll(const VectorBase<U, O, BP, UV>& other)
1025 {
1026   return append(other.begin(), other.length());
1027 }
1028
1029 template<typename T, size_t N, class AP, class TV>
1030 template<class U>
1031 MOZ_ALWAYS_INLINE bool
1032 VectorBase<T, N, AP, TV>::append(const U *insBegin, size_t insLength)
1033 {
1034   return append(insBegin, insBegin + insLength);
1035 }
1036
1037 template<typename T, size_t N, class AP, class TV>
1038 MOZ_ALWAYS_INLINE void
1039 VectorBase<T, N, AP, TV>::popBack()
1040 {
1041   MOZ_REENTRANCY_GUARD_ET_AL;
1042   MOZ_ASSERT(!empty());
1043   --mLength;
1044   endNoCheck()->~T();
1045 }
1046
1047 template<typename T, size_t N, class AP, class TV>
1048 MOZ_ALWAYS_INLINE T
1049 VectorBase<T, N, AP, TV>::popCopy()
1050 {
1051   T ret = back();
1052   popBack();
1053   return ret;
1054 }
1055
1056 template<typename T, size_t N, class AP, class TV>
1057 inline T*
1058 VectorBase<T, N, AP, TV>::extractRawBuffer()
1059 {
1060   T* ret;
1061   if (usingInlineStorage()) {
1062     ret = reinterpret_cast<T*>(this->malloc_(mLength * sizeof(T)));
1063     if (!ret)
1064       return nullptr;
1065     Impl::copyConstruct(ret, beginNoCheck(), endNoCheck());
1066     Impl::destroy(beginNoCheck(), endNoCheck());
1067     /* mBegin, mCapacity are unchanged. */
1068     mLength = 0;
1069   } else {
1070     ret = mBegin;
1071     mBegin = static_cast<T*>(storage.addr());
1072     mLength = 0;
1073     mCapacity = sInlineCapacity;
1074 #ifdef DEBUG
1075     mReserved = sInlineCapacity;
1076 #endif
1077   }
1078   return ret;
1079 }
1080
1081 template<typename T, size_t N, class AP, class TV>
1082 inline void
1083 VectorBase<T, N, AP, TV>::replaceRawBuffer(T* p, size_t aLength)
1084 {
1085   MOZ_REENTRANCY_GUARD_ET_AL;
1086
1087   /* Destroy what we have. */
1088   Impl::destroy(beginNoCheck(), endNoCheck());
1089   if (!usingInlineStorage())
1090     this->free_(beginNoCheck());
1091
1092   /* Take in the new buffer. */
1093   if (aLength <= sInlineCapacity) {
1094     /*
1095      * We convert to inline storage if possible, even though p might
1096      * otherwise be acceptable.  Maybe this behaviour should be
1097      * specifiable with an argument to this function.
1098      */
1099     mBegin = static_cast<T*>(storage.addr());
1100     mLength = aLength;
1101     mCapacity = sInlineCapacity;
1102     Impl::moveConstruct(mBegin, p, p + aLength);
1103     Impl::destroy(p, p + aLength);
1104     this->free_(p);
1105   } else {
1106     mBegin = p;
1107     mLength = aLength;
1108     mCapacity = aLength;
1109   }
1110 #ifdef DEBUG
1111   mReserved = aLength;
1112 #endif
1113 }
1114
1115 template<typename T, size_t N, class AP, class TV>
1116 inline size_t
1117 VectorBase<T, N, AP, TV>::sizeOfExcludingThis(MallocSizeOf mallocSizeOf) const
1118 {
1119   return usingInlineStorage() ? 0 : mallocSizeOf(beginNoCheck());
1120 }
1121
1122 template<typename T, size_t N, class AP, class TV>
1123 inline size_t
1124 VectorBase<T, N, AP, TV>::sizeOfIncludingThis(MallocSizeOf mallocSizeOf) const
1125 {
1126   return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
1127 }
1128
1129 template<typename T, size_t N, class AP, class TV>
1130 inline void
1131 VectorBase<T, N, AP, TV>::swap(TV& other)
1132 {
1133   static_assert(N == 0,
1134                 "still need to implement this for N != 0");
1135
1136   // This only works when inline storage is always empty.
1137   if (!usingInlineStorage() && other.usingInlineStorage()) {
1138     other.mBegin = mBegin;
1139     mBegin = inlineStorage();
1140   } else if (usingInlineStorage() && !other.usingInlineStorage()) {
1141     mBegin = other.mBegin;
1142     other.mBegin = other.inlineStorage();
1143   } else if (!usingInlineStorage() && !other.usingInlineStorage()) {
1144     Swap(mBegin, other.mBegin);
1145   } else {
1146     // This case is a no-op, since we'd set both to use their inline storage.
1147   }
1148
1149   Swap(mLength, other.mLength);
1150   Swap(mCapacity, other.mCapacity);
1151 #ifdef DEBUG
1152   Swap(mReserved, other.mReserved);
1153 #endif
1154 }
1155
1156 /*
1157  * STL-like container providing a short-lived, dynamic buffer.  Vector calls the
1158  * constructors/destructors of all elements stored in its internal buffer, so
1159  * non-PODs may be safely used.  Additionally, Vector will store the first N
1160  * elements in-place before resorting to dynamic allocation.
1161  *
1162  * T requirements:
1163  *  - default and copy constructible, assignable, destructible
1164  *  - operations do not throw
1165  * N requirements:
1166  *  - any value, however, N is clamped to min/max values
1167  * AllocPolicy:
1168  *  - see "Allocation policies" in AllocPolicy.h (defaults to
1169  *    mozilla::MallocAllocPolicy)
1170  *
1171  * Vector is not reentrant: T member functions called during Vector member
1172  * functions must not call back into the same object!
1173  */
1174 template<typename T,
1175          size_t MinInlineCapacity = 0,
1176          class AllocPolicy = MallocAllocPolicy>
1177 class Vector
1178   : public VectorBase<T,
1179                       MinInlineCapacity,
1180                       AllocPolicy,
1181                       Vector<T, MinInlineCapacity, AllocPolicy> >
1182 {
1183     typedef VectorBase<T, MinInlineCapacity, AllocPolicy, Vector> Base;
1184
1185   public:
1186     Vector(AllocPolicy alloc = AllocPolicy()) : Base(alloc) {}
1187     Vector(Vector&& vec) : Base(Move(vec)) {}
1188     Vector& operator=(Vector&& vec) {
1189       return Base::operator=(Move(vec));
1190     }
1191 };
1192
1193 } // namespace mozilla
1194
1195 #ifdef _MSC_VER
1196 #pragma warning(pop)
1197 #endif
1198
1199 #endif /* mozilla_Vector_h */