The Tor Browser / file revision

 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

 /* vim: set ts=8 sts=2 et sw=2 tw=80: */

 /* This Source Code Form is subject to the terms of the Mozilla Public

  * License, v. 2.0. If a copy of the MPL was not distributed with this

  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

 /* A type/length-parametrized vector class. */

 #ifndef mozilla_Vector_h

 #define mozilla_Vector_h

 #include "mozilla/Alignment.h"

 #include "mozilla/AllocPolicy.h"

 #include "mozilla/ArrayUtils.h" // for PointerRangeSize

 #include "mozilla/Assertions.h"

 #include "mozilla/Attributes.h"

 #include "mozilla/MathAlgorithms.h"

 #include "mozilla/MemoryReporting.h"

 #include "mozilla/Move.h"

 #include "mozilla/NullPtr.h"

 #include "mozilla/ReentrancyGuard.h"

 #include "mozilla/TemplateLib.h"

 #include "mozilla/TypeTraits.h"

 #include <new> // for placement new

 /* Silence dire "bugs in previous versions of MSVC have been fixed" warnings */

 #ifdef _MSC_VER

 #pragma warning(push)

 #pragma warning(disable:4345)

 #endif

 namespace mozilla {

 template<typename T, size_t N, class AllocPolicy, class ThisVector>

 class VectorBase;

 namespace detail {

 /*

  * Check that the given capacity wastes the minimal amount of space if

  * allocated on the heap.  This means that cap*sizeof(T) is as close to a

  * power-of-two as possible.  growStorageBy() is responsible for ensuring

  * this.

  */

 template<typename T>

 static bool CapacityHasExcessSpace(size_t cap)

 {

   size_t size = cap * sizeof(T);

   return RoundUpPow2(size) - size >= sizeof(T);

 }

 /*

  * This template class provides a default implementation for vector operations

  * when the element type is not known to be a POD, as judged by IsPod.

  */

 template<typename T, size_t N, class AP, class ThisVector, bool IsPod>

 struct VectorImpl

 {

     /* Destroys constructed objects in the range [begin, end). */

     static inline void destroy(T* begin, T* end) {

       MOZ_ASSERT(begin <= end);

       for (T* p = begin; p < end; ++p)

         p->~T();

     }

     /* Constructs objects in the uninitialized range [begin, end). */

     static inline void initialize(T* begin, T* end) {

       MOZ_ASSERT(begin <= end);

       for (T* p = begin; p < end; ++p)

         new(p) T();

     }

     /*

      * Copy-constructs objects in the uninitialized range

      * [dst, dst+(srcend-srcbeg)) from the range [srcbeg, srcend).

      */

     template<typename U>

     static inline void copyConstruct(T* dst, const U* srcbeg, const U* srcend) {

       MOZ_ASSERT(srcbeg <= srcend);

       for (const U* p = srcbeg; p < srcend; ++p, ++dst)

         new(dst) T(*p);

     }

     /*

      * Move-constructs objects in the uninitialized range

      * [dst, dst+(srcend-srcbeg)) from the range [srcbeg, srcend).

      */

     template<typename U>

     static inline void moveConstruct(T* dst, U* srcbeg, U* srcend) {

       MOZ_ASSERT(srcbeg <= srcend);

       for (U* p = srcbeg; p < srcend; ++p, ++dst)

         new(dst) T(Move(*p));

     }

     /*

      * Copy-constructs objects in the uninitialized range [dst, dst+n) from the

      * same object u.

      */

     template<typename U>

     static inline void copyConstructN(T* dst, size_t n, const U& u) {

       for (T* end = dst + n; dst < end; ++dst)

         new(dst) T(u);

     }

     /*

      * Grows the given buffer to have capacity newCap, preserving the objects

      * constructed in the range [begin, end) and updating v. Assumes that (1)

      * newCap has not overflowed, and (2) multiplying newCap by sizeof(T) will

      * not overflow.

      */

     static inline bool

     growTo(VectorBase<T, N, AP, ThisVector>& v, size_t newCap) {

       MOZ_ASSERT(!v.usingInlineStorage());

       MOZ_ASSERT(!CapacityHasExcessSpace<T>(newCap));

       T* newbuf = reinterpret_cast<T*>(v.malloc_(newCap * sizeof(T)));

       if (!newbuf)

         return false;

       T* dst = newbuf;

       T* src = v.beginNoCheck();

       for (; src < v.endNoCheck(); ++dst, ++src)

         new(dst) T(Move(*src));

       VectorImpl::destroy(v.beginNoCheck(), v.endNoCheck());

       v.free_(v.mBegin);

       v.mBegin = newbuf;

       /* v.mLength is unchanged. */

       v.mCapacity = newCap;

       return true;

     }

 };

 /*

  * This partial template specialization provides a default implementation for

  * vector operations when the element type is known to be a POD, as judged by

  * IsPod.

  */

 template<typename T, size_t N, class AP, class ThisVector>

 struct VectorImpl<T, N, AP, ThisVector, true>

 {

     static inline void destroy(T*, T*) {}

     static inline void initialize(T* begin, T* end) {

       /*

        * You would think that memset would be a big win (or even break even)

        * when we know T is a POD. But currently it's not. This is probably

        * because |append| tends to be given small ranges and memset requires

        * a function call that doesn't get inlined.

        *

        * memset(begin, 0, sizeof(T) * (end-begin));

        */

       MOZ_ASSERT(begin <= end);

       for (T* p = begin; p < end; ++p)

         new(p) T();

     }

     template<typename U>

     static inline void copyConstruct(T* dst, const U* srcbeg, const U* srcend) {

       /*

        * See above memset comment. Also, notice that copyConstruct is

        * currently templated (T != U), so memcpy won't work without

        * requiring T == U.

        *

        * memcpy(dst, srcbeg, sizeof(T) * (srcend - srcbeg));

        */

       MOZ_ASSERT(srcbeg <= srcend);

       for (const U* p = srcbeg; p < srcend; ++p, ++dst)

         *dst = *p;

     }

     template<typename U>

     static inline void moveConstruct(T* dst, const U* srcbeg, const U* srcend) {

       copyConstruct(dst, srcbeg, srcend);

     }

     static inline void copyConstructN(T* dst, size_t n, const T& t) {

       for (T* end = dst + n; dst < end; ++dst)

         *dst = t;

     }

     static inline bool

     growTo(VectorBase<T, N, AP, ThisVector>& v, size_t newCap) {

       MOZ_ASSERT(!v.usingInlineStorage());

       MOZ_ASSERT(!CapacityHasExcessSpace<T>(newCap));

       size_t oldSize = sizeof(T) * v.mCapacity;

       size_t newSize = sizeof(T) * newCap;

       T* newbuf = reinterpret_cast<T*>(v.realloc_(v.mBegin, oldSize, newSize));

       if (!newbuf)

         return false;

       v.mBegin = newbuf;

       /* v.mLength is unchanged. */

       v.mCapacity = newCap;

       return true;

     }

 };

 } // namespace detail

 /*

  * A CRTP base class for vector-like classes.  Unless you really really want

  * your own vector class -- and you almost certainly don't -- you should use

  * mozilla::Vector instead!

  *

  * See mozilla::Vector for interface requirements.

  */

 template<typename T, size_t N, class AllocPolicy, class ThisVector>

 class VectorBase : private AllocPolicy

 {

     /* utilities */

     static const bool sElemIsPod = IsPod<T>::value;

     typedef detail::VectorImpl<T, N, AllocPolicy, ThisVector, sElemIsPod> Impl;

     friend struct detail::VectorImpl<T, N, AllocPolicy, ThisVector, sElemIsPod>;

     bool growStorageBy(size_t incr);

     bool convertToHeapStorage(size_t newCap);

     /* magic constants */

     static const int sMaxInlineBytes = 1024;

     /* compute constants */

     /*

      * Consider element size to be 1 for buffer sizing if there are 0 inline

      * elements.  This allows us to compile when the definition of the element

      * type is not visible here.

      *

      * Explicit specialization is only allowed at namespace scope, so in order

      * to keep everything here, we use a dummy template parameter with partial

      * specialization.

      */

     template<int M, int Dummy>

     struct ElemSize

     {

         static const size_t value = sizeof(T);

     };

     template<int Dummy>

     struct ElemSize<0, Dummy>

     {

         static const size_t value = 1;

     };

     static const size_t sInlineCapacity =

       tl::Min<N, sMaxInlineBytes / ElemSize<N, 0>::value>::value;

     /* Calculate inline buffer size; avoid 0-sized array. */

     static const size_t sInlineBytes =

       tl::Max<1, sInlineCapacity * ElemSize<N, 0>::value>::value;

     /* member data */

     /*

      * Pointer to the buffer, be it inline or heap-allocated. Only [mBegin,

      * mBegin + mLength) hold valid constructed T objects. The range [mBegin +

      * mLength, mBegin + mCapacity) holds uninitialized memory. The range

      * [mBegin + mLength, mBegin + mReserved) also holds uninitialized memory

      * previously allocated by a call to reserve().

      */

     T* mBegin;

     /* Number of elements in the vector. */

     size_t mLength;

     /* Max number of elements storable in the vector without resizing. */

     size_t mCapacity;

 #ifdef DEBUG

     /* Max elements of reserved or used space in this vector. */

     size_t mReserved;

 #endif

     /* Memory used for inline storage. */

     AlignedStorage<sInlineBytes> storage;

 #ifdef DEBUG

     friend class ReentrancyGuard;

     bool entered;

 #endif

     /* private accessors */

     bool usingInlineStorage() const {

       return mBegin == const_cast<VectorBase*>(this)->inlineStorage();

     }

     T* inlineStorage() {

       return static_cast<T*>(storage.addr());

     }

     T* beginNoCheck() const {

       return mBegin;

     }

     T* endNoCheck() {

       return mBegin + mLength;

     }

     const T* endNoCheck() const {

       return mBegin + mLength;

     }

 #ifdef DEBUG

     size_t reserved() const {

       MOZ_ASSERT(mReserved <= mCapacity);

       MOZ_ASSERT(mLength <= mReserved);

       return mReserved;

     }

 #endif

     /* Append operations guaranteed to succeed due to pre-reserved space. */

     template<typename U> void internalAppend(U&& u);

     template<typename U, size_t O, class BP, class UV>

     void internalAppendAll(const VectorBase<U, O, BP, UV>& u);

     void internalAppendN(const T& t, size_t n);

     template<typename U> void internalAppend(const U* begin, size_t length);

   public:

     static const size_t sMaxInlineStorage = N;

     typedef T ElementType;

     VectorBase(AllocPolicy = AllocPolicy());

     VectorBase(ThisVector&&); /* Move constructor. */

     ThisVector& operator=(ThisVector&&); /* Move assignment. */

     ~VectorBase();

     /* accessors */

     const AllocPolicy& allocPolicy() const {

       return *this;

     }

     AllocPolicy& allocPolicy() {

       return *this;

     }

     enum { InlineLength = N };

     size_t length() const {

       return mLength;

     }

     bool empty() const {

       return mLength == 0;

     }

     size_t capacity() const {

       return mCapacity;

     }

     T* begin() {

       MOZ_ASSERT(!entered);

       return mBegin;

     }

     const T* begin() const {

       MOZ_ASSERT(!entered);

       return mBegin;

     }

     T* end() {

       MOZ_ASSERT(!entered);

       return mBegin + mLength;

     }

     const T* end() const {

       MOZ_ASSERT(!entered);

       return mBegin + mLength;

     }

     T& operator[](size_t i) {

       MOZ_ASSERT(!entered);

       MOZ_ASSERT(i < mLength);

       return begin()[i];

     }

     const T& operator[](size_t i) const {

       MOZ_ASSERT(!entered);

       MOZ_ASSERT(i < mLength);

       return begin()[i];

     }

     T& back() {

       MOZ_ASSERT(!entered);

       MOZ_ASSERT(!empty());

       return *(end() - 1);

     }

     const T& back() const {

       MOZ_ASSERT(!entered);

       MOZ_ASSERT(!empty());

       return *(end() - 1);

     }

     class Range

     {

         friend class VectorBase;

         T* cur_;

         T* end_;

         Range(T* cur, T* end) : cur_(cur), end_(end) {

           MOZ_ASSERT(cur <= end);

         }

       public:

         Range() {}

         bool empty() const { return cur_ == end_; }

         size_t remain() const { return PointerRangeSize(cur_, end_); }

         T& front() const { MOZ_ASSERT(!empty()); return *cur_; }

         void popFront() { MOZ_ASSERT(!empty()); ++cur_; }

         T popCopyFront() { MOZ_ASSERT(!empty()); return *cur_++; }

     };

     Range all() {

       return Range(begin(), end());

     }

     /* mutators */

     /**

      * Given that the vector is empty and has no inline storage, grow to

      * |capacity|.

      */

     bool initCapacity(size_t request);

     /**

      * If reserve(length() + N) succeeds, the N next appends are guaranteed to

      * succeed.

      */

     bool reserve(size_t request);

     /**

      * Destroy elements in the range [end() - incr, end()). Does not deallocate

      * or unreserve storage for those elements.

      */

     void shrinkBy(size_t incr);

     /** Grow the vector by incr elements. */

     bool growBy(size_t incr);

     /** Call shrinkBy or growBy based on whether newSize > length(). */

     bool resize(size_t newLength);

     /**

      * Increase the length of the vector, but don't initialize the new elements

      * -- leave them as uninitialized memory.

      */

     bool growByUninitialized(size_t incr);

     bool resizeUninitialized(size_t newLength);

     /** Shorthand for shrinkBy(length()). */

     void clear();

     /** Clears and releases any heap-allocated storage. */

     void clearAndFree();

     /**

      * If true, appending |needed| elements won't reallocate elements storage.

      * This *doesn't* mean that infallibleAppend may be used!  You still must

      * reserve the extra space, even if this method indicates that appends won't

      * need to reallocate elements storage.

      */

     bool canAppendWithoutRealloc(size_t needed) const;

     /** Potentially fallible append operations. */

     /**

      * This can take either a T& or a T&&. Given a T&&, it moves |u| into the

      * vector, instead of copying it. If it fails, |u| is left unmoved. ("We are

      * not amused.")

      */

     template<typename U> bool append(U&& u);

     template<typename U, size_t O, class BP, class UV>

     bool appendAll(const VectorBase<U, O, BP, UV>& u);

     bool appendN(const T& t, size_t n);

     template<typename U> bool append(const U* begin, const U* end);

     template<typename U> bool append(const U* begin, size_t length);

     /*

      * Guaranteed-infallible append operations for use upon vectors whose

      * memory has been pre-reserved.  Don't use this if you haven't reserved the

      * memory!

      */

     template<typename U> void infallibleAppend(U&& u) {

       internalAppend(Forward<U>(u));

     }

     void infallibleAppendN(const T& t, size_t n) {

       internalAppendN(t, n);

     }

     template<typename U> void infallibleAppend(const U* aBegin, const U* aEnd) {

       internalAppend(aBegin, PointerRangeSize(aBegin, aEnd));

     }

     template<typename U> void infallibleAppend(const U* aBegin, size_t aLength) {

       internalAppend(aBegin, aLength);

     }

     void popBack();

     T popCopy();

     /**

      * Transfers ownership of the internal buffer used by this vector to the

      * caller.  (It's the caller's responsibility to properly deallocate this

      * buffer, in accordance with this vector's AllocPolicy.)  After this call,

      * the vector is empty.  Since the returned buffer may need to be allocated

      * (if the elements are currently stored in-place), the call can fail,

      * returning nullptr.

      *

      * N.B. Although a T*, only the range [0, length()) is constructed.

      */

     T* extractRawBuffer();

     /**

      * Transfer ownership of an array of objects into the vector.  The caller

      * must have allocated the array in accordance with this vector's

      * AllocPolicy.

      *

      * N.B. This call assumes that there are no uninitialized elements in the

      *      passed array.

      */

     void replaceRawBuffer(T* p, size_t length);

     /**

      * Places |val| at position |p|, shifting existing elements from |p| onward

      * one position higher.  On success, |p| should not be reused because it'll

      * be a dangling pointer if reallocation of the vector storage occurred; the

      * return value should be used instead.  On failure, nullptr is returned.

      *

      * Example usage:

      *

      *   if (!(p = vec.insert(p, val)))

      *     <handle failure>

      *   <keep working with p>

      *

      * This is inherently a linear-time operation.  Be careful!

      */

     template<typename U>

     T* insert(T* p, U&& val);

     /**

      * Removes the element |t|, which must fall in the bounds [begin, end),

      * shifting existing elements from |t + 1| onward one position lower.

      */

     void erase(T* t);

     /**

      * Measure the size of the vector's heap-allocated storage.

      */

     size_t sizeOfExcludingThis(MallocSizeOf mallocSizeOf) const;

     /**

      * Like sizeOfExcludingThis, but also measures the size of the vector

      * object (which must be heap-allocated) itself.

      */

     size_t sizeOfIncludingThis(MallocSizeOf mallocSizeOf) const;

     void swap(ThisVector& other);

   private:

     VectorBase(const VectorBase&) MOZ_DELETE;

     void operator=(const VectorBase&) MOZ_DELETE;

     /* Move-construct/assign only from our derived class, ThisVector. */

     VectorBase(VectorBase&&) MOZ_DELETE;

     void operator=(VectorBase&&) MOZ_DELETE;

 };

 /* This does the re-entrancy check plus several other sanity checks. */

 #define MOZ_REENTRANCY_GUARD_ET_AL \

   ReentrancyGuard g(*this); \

   MOZ_ASSERT_IF(usingInlineStorage(), mCapacity == sInlineCapacity); \

   MOZ_ASSERT(reserved() <= mCapacity); \

   MOZ_ASSERT(mLength <= reserved()); \

   MOZ_ASSERT(mLength <= mCapacity)

 /* Vector Implementation */

 template<typename T, size_t N, class AP, class TV>

 MOZ_ALWAYS_INLINE

 VectorBase<T, N, AP, TV>::VectorBase(AP ap)

   : AP(ap),

     mLength(0),

     mCapacity(sInlineCapacity)

 #ifdef DEBUG

   , mReserved(sInlineCapacity),

     entered(false)

 #endif

 {

   mBegin = static_cast<T*>(storage.addr());

 }

 /* Move constructor. */

 template<typename T, size_t N, class AllocPolicy, class TV>

 MOZ_ALWAYS_INLINE

 VectorBase<T, N, AllocPolicy, TV>::VectorBase(TV&& rhs)

   : AllocPolicy(Move(rhs))

 #ifdef DEBUG

     , entered(false)

 #endif

 {

   mLength = rhs.mLength;

   mCapacity = rhs.mCapacity;

 #ifdef DEBUG

   mReserved = rhs.mReserved;

 #endif

   if (rhs.usingInlineStorage()) {

     /* We can't move the buffer over in this case, so copy elements. */

     mBegin = static_cast<T*>(storage.addr());

     Impl::moveConstruct(mBegin, rhs.beginNoCheck(), rhs.endNoCheck());

     /*

      * Leave rhs's mLength, mBegin, mCapacity, and mReserved as they are.

      * The elements in its in-line storage still need to be destroyed.

      */

   } else {

     /*

      * Take src's buffer, and turn src into an empty vector using

      * in-line storage.

      */

     mBegin = rhs.mBegin;

     rhs.mBegin = static_cast<T*>(rhs.storage.addr());

     rhs.mCapacity = sInlineCapacity;

     rhs.mLength = 0;

 #ifdef DEBUG

     rhs.mReserved = sInlineCapacity;

 #endif

   }

 }

 /* Move assignment. */

 template<typename T, size_t N, class AP, class TV>

 MOZ_ALWAYS_INLINE

 TV&

 VectorBase<T, N, AP, TV>::operator=(TV&& rhs)

 {

   MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");

   TV* tv = static_cast<TV*>(this);

   tv->~TV();

   new(tv) TV(Move(rhs));

   return *tv;

 }

 template<typename T, size_t N, class AP, class TV>

 MOZ_ALWAYS_INLINE

 VectorBase<T, N, AP, TV>::~VectorBase()

 {

   MOZ_REENTRANCY_GUARD_ET_AL;

   Impl::destroy(beginNoCheck(), endNoCheck());

   if (!usingInlineStorage())

     this->free_(beginNoCheck());

 }

 /*

  * This function will create a new heap buffer with capacity newCap,

  * move all elements in the inline buffer to this new buffer,

  * and fail on OOM.

  */

 template<typename T, size_t N, class AP, class TV>

 inline bool

 VectorBase<T, N, AP, TV>::convertToHeapStorage(size_t newCap)

 {

   MOZ_ASSERT(usingInlineStorage());

   /* Allocate buffer. */

   MOZ_ASSERT(!detail::CapacityHasExcessSpace<T>(newCap));

   T* newBuf = reinterpret_cast<T*>(this->malloc_(newCap * sizeof(T)));

   if (!newBuf)

     return false;

   /* Copy inline elements into heap buffer. */

   Impl::moveConstruct(newBuf, beginNoCheck(), endNoCheck());

   Impl::destroy(beginNoCheck(), endNoCheck());

   /* Switch in heap buffer. */

   mBegin = newBuf;

   /* mLength is unchanged. */

   mCapacity = newCap;

   return true;

 }

 template<typename T, size_t N, class AP, class TV>

 MOZ_NEVER_INLINE bool

 VectorBase<T, N, AP, TV>::growStorageBy(size_t incr)

 {

   MOZ_ASSERT(mLength + incr > mCapacity);

   MOZ_ASSERT_IF(!usingInlineStorage(),

                 !detail::CapacityHasExcessSpace<T>(mCapacity));

   /*

    * When choosing a new capacity, its size should is as close to 2**N bytes

    * as possible.  2**N-sized requests are best because they are unlikely to

    * be rounded up by the allocator.  Asking for a 2**N number of elements

    * isn't as good, because if sizeof(T) is not a power-of-two that would

    * result in a non-2**N request size.

    */

   size_t newCap;

   if (incr == 1) {

     if (usingInlineStorage()) {

       /* This case occurs in ~70--80% of the calls to this function. */

       size_t newSize =

         tl::RoundUpPow2<(sInlineCapacity + 1) * sizeof(T)>::value;

       newCap = newSize / sizeof(T);

       goto convert;

     }

     if (mLength == 0) {

       /* This case occurs in ~0--10% of the calls to this function. */

       newCap = 1;

       goto grow;

     }

     /* This case occurs in ~15--20% of the calls to this function. */

     /*

      * Will mLength * 4 *sizeof(T) overflow?  This condition limits a vector

      * to 1GB of memory on a 32-bit system, which is a reasonable limit.  It

      * also ensures that

      *

      *   static_cast<char*>(end()) - static_cast<char*>(begin())

      *

      * doesn't overflow ptrdiff_t (see bug 510319).

      */

     if (mLength & tl::MulOverflowMask<4 * sizeof(T)>::value) {

       this->reportAllocOverflow();

       return false;

     }

     /*

      * If we reach here, the existing capacity will have a size that is already

      * as close to 2^N as sizeof(T) will allow.  Just double the capacity, and

      * then there might be space for one more element.

      */

     newCap = mLength * 2;

     if (detail::CapacityHasExcessSpace<T>(newCap))

       newCap += 1;

   } else {

     /* This case occurs in ~2% of the calls to this function. */

     size_t newMinCap = mLength + incr;

     /* Did mLength + incr overflow?  Will newCap * sizeof(T) overflow? */

     if (newMinCap < mLength ||

         newMinCap & tl::MulOverflowMask<2 * sizeof(T)>::value)

     {

       this->reportAllocOverflow();

       return false;

     }

     size_t newMinSize = newMinCap * sizeof(T);

     size_t newSize = RoundUpPow2(newMinSize);

     newCap = newSize / sizeof(T);

   }

   if (usingInlineStorage()) {

   convert:

     return convertToHeapStorage(newCap);

   }

 grow:

   return Impl::growTo(*this, newCap);

 }

 template<typename T, size_t N, class AP, class TV>

 inline bool

 VectorBase<T, N, AP, TV>::initCapacity(size_t request)

 {

   MOZ_ASSERT(empty());

   MOZ_ASSERT(usingInlineStorage());

   if (request == 0)

     return true;

   T* newbuf = reinterpret_cast<T*>(this->malloc_(request * sizeof(T)));

   if (!newbuf)

     return false;

   mBegin = newbuf;

   mCapacity = request;

 #ifdef DEBUG

   mReserved = request;

 #endif

   return true;

 }

 template<typename T, size_t N, class AP, class TV>

 inline bool

 VectorBase<T, N, AP, TV>::reserve(size_t request)

 {

   MOZ_REENTRANCY_GUARD_ET_AL;

   if (request > mCapacity && !growStorageBy(request - mLength))

     return false;

 #ifdef DEBUG

   if (request > mReserved)

     mReserved = request;

   MOZ_ASSERT(mLength <= mReserved);

   MOZ_ASSERT(mReserved <= mCapacity);

 #endif

   return true;

 }

 template<typename T, size_t N, class AP, class TV>

 inline void

 VectorBase<T, N, AP, TV>::shrinkBy(size_t incr)

 {

   MOZ_REENTRANCY_GUARD_ET_AL;

   MOZ_ASSERT(incr <= mLength);

   Impl::destroy(endNoCheck() - incr, endNoCheck());

   mLength -= incr;

 }

 template<typename T, size_t N, class AP, class TV>

 MOZ_ALWAYS_INLINE bool

 VectorBase<T, N, AP, TV>::growBy(size_t incr)

 {

   MOZ_REENTRANCY_GUARD_ET_AL;

   if (incr > mCapacity - mLength && !growStorageBy(incr))

     return false;

   MOZ_ASSERT(mLength + incr <= mCapacity);

   T* newend = endNoCheck() + incr;

   Impl::initialize(endNoCheck(), newend);

   mLength += incr;

 #ifdef DEBUG

   if (mLength > mReserved)

     mReserved = mLength;

 #endif

   return true;

 }

 template<typename T, size_t N, class AP, class TV>

 MOZ_ALWAYS_INLINE bool

 VectorBase<T, N, AP, TV>::growByUninitialized(size_t incr)

 {

   MOZ_REENTRANCY_GUARD_ET_AL;

   if (incr > mCapacity - mLength && !growStorageBy(incr))

     return false;

   MOZ_ASSERT(mLength + incr <= mCapacity);

   mLength += incr;

 #ifdef DEBUG

   if (mLength > mReserved)

     mReserved = mLength;

 #endif

   return true;

 }

 template<typename T, size_t N, class AP, class TV>

 inline bool

 VectorBase<T, N, AP, TV>::resize(size_t newLength)

 {

   size_t curLength = mLength;

   if (newLength > curLength)

     return growBy(newLength - curLength);

   shrinkBy(curLength - newLength);

   return true;

 }

 template<typename T, size_t N, class AP, class TV>

 MOZ_ALWAYS_INLINE bool

 VectorBase<T, N, AP, TV>::resizeUninitialized(size_t newLength)

 {

   size_t curLength = mLength;

   if (newLength > curLength)

     return growByUninitialized(newLength - curLength);

   shrinkBy(curLength - newLength);

   return true;

 }

 template<typename T, size_t N, class AP, class TV>

 inline void

 VectorBase<T, N, AP, TV>::clear()

 {

   MOZ_REENTRANCY_GUARD_ET_AL;

   Impl::destroy(beginNoCheck(), endNoCheck());

   mLength = 0;

 }

 template<typename T, size_t N, class AP, class TV>

 inline void

 VectorBase<T, N, AP, TV>::clearAndFree()

 {

   clear();

   if (usingInlineStorage())

     return;

   this->free_(beginNoCheck());

   mBegin = static_cast<T*>(storage.addr());

   mCapacity = sInlineCapacity;

 #ifdef DEBUG

   mReserved = sInlineCapacity;

 #endif

 }

 template<typename T, size_t N, class AP, class TV>

 inline bool

 VectorBase<T, N, AP, TV>::canAppendWithoutRealloc(size_t needed) const

 {

   return mLength + needed <= mCapacity;

 }

 template<typename T, size_t N, class AP, class TV>

 template<typename U, size_t O, class BP, class UV>

 MOZ_ALWAYS_INLINE void

 VectorBase<T, N, AP, TV>::internalAppendAll(const VectorBase<U, O, BP, UV>& other)

 {

   internalAppend(other.begin(), other.length());

 }

 template<typename T, size_t N, class AP, class TV>

 template<typename U>

 MOZ_ALWAYS_INLINE void

 VectorBase<T, N, AP, TV>::internalAppend(U&& u)

 {

   MOZ_ASSERT(mLength + 1 <= mReserved);

   MOZ_ASSERT(mReserved <= mCapacity);

   new(endNoCheck()) T(Forward<U>(u));

   ++mLength;

 }

 template<typename T, size_t N, class AP, class TV>

 MOZ_ALWAYS_INLINE bool

 VectorBase<T, N, AP, TV>::appendN(const T& t, size_t needed)

 {

   MOZ_REENTRANCY_GUARD_ET_AL;

   if (mLength + needed > mCapacity && !growStorageBy(needed))

     return false;

 #ifdef DEBUG

   if (mLength + needed > mReserved)

     mReserved = mLength + needed;

 #endif

   internalAppendN(t, needed);

   return true;

 }

 template<typename T, size_t N, class AP, class TV>

 MOZ_ALWAYS_INLINE void

 VectorBase<T, N, AP, TV>::internalAppendN(const T& t, size_t needed)

 {

   MOZ_ASSERT(mLength + needed <= mReserved);

   MOZ_ASSERT(mReserved <= mCapacity);

   Impl::copyConstructN(endNoCheck(), needed, t);

   mLength += needed;

 }

 template<typename T, size_t N, class AP, class TV>

 template<typename U>

 inline T*

 VectorBase<T, N, AP, TV>::insert(T* p, U&& val)

 {

   MOZ_ASSERT(begin() <= p);

   MOZ_ASSERT(p <= end());

   size_t pos = p - begin();

   MOZ_ASSERT(pos <= mLength);

   size_t oldLength = mLength;

   if (pos == oldLength) {

     if (!append(Forward<U>(val)))

       return nullptr;

   } else {

     T oldBack = Move(back());

     if (!append(Move(oldBack))) /* Dup the last element. */

       return nullptr;

     for (size_t i = oldLength; i > pos; --i)

       (*this)[i] = Move((*this)[i - 1]);

     (*this)[pos] = Forward<U>(val);

   }

   return begin() + pos;

 }

 template<typename T, size_t N, class AP, class TV>

 inline void

 VectorBase<T, N, AP, TV>::erase(T* it)

 {

   MOZ_ASSERT(begin() <= it);

   MOZ_ASSERT(it < end());

   while (it + 1 < end()) {

     *it = *(it + 1);

     ++it;

   }

     popBack();

 }

 template<typename T, size_t N, class AP, class TV>

 template<typename U>

 MOZ_ALWAYS_INLINE bool

 VectorBase<T, N, AP, TV>::append(const U* insBegin, const U* insEnd)

 {

   MOZ_REENTRANCY_GUARD_ET_AL;

   size_t needed = PointerRangeSize(insBegin, insEnd);

   if (mLength + needed > mCapacity && !growStorageBy(needed))

     return false;

 #ifdef DEBUG

   if (mLength + needed > mReserved)

     mReserved = mLength + needed;

 #endif

   internalAppend(insBegin, needed);

   return true;

 }

 template<typename T, size_t N, class AP, class TV>

 template<typename U>

 MOZ_ALWAYS_INLINE void

 VectorBase<T, N, AP, TV>::internalAppend(const U* insBegin, size_t insLength)

 {

   MOZ_ASSERT(mLength + insLength <= mReserved);

   MOZ_ASSERT(mReserved <= mCapacity);

   Impl::copyConstruct(endNoCheck(), insBegin, insBegin + insLength);

   mLength += insLength;

 }

 template<typename T, size_t N, class AP, class TV>

 template<typename U>

 MOZ_ALWAYS_INLINE bool

 VectorBase<T, N, AP, TV>::append(U&& u)

 {

   MOZ_REENTRANCY_GUARD_ET_AL;

   if (mLength == mCapacity && !growStorageBy(1))

     return false;

 #ifdef DEBUG

   if (mLength + 1 > mReserved)

     mReserved = mLength + 1;

 #endif

   internalAppend(Forward<U>(u));

   return true;

 }

 template<typename T, size_t N, class AP, class TV>

 template<typename U, size_t O, class BP, class UV>

 MOZ_ALWAYS_INLINE bool

 VectorBase<T, N, AP, TV>::appendAll(const VectorBase<U, O, BP, UV>& other)

 {

   return append(other.begin(), other.length());

 }

 template<typename T, size_t N, class AP, class TV>

 template<class U>

 MOZ_ALWAYS_INLINE bool

 VectorBase<T, N, AP, TV>::append(const U *insBegin, size_t insLength)

 {

   return append(insBegin, insBegin + insLength);

 }

 template<typename T, size_t N, class AP, class TV>

 MOZ_ALWAYS_INLINE void

 VectorBase<T, N, AP, TV>::popBack()

 {

   MOZ_REENTRANCY_GUARD_ET_AL;

   MOZ_ASSERT(!empty());

   --mLength;

   endNoCheck()->~T();

 }

 template<typename T, size_t N, class AP, class TV>

 MOZ_ALWAYS_INLINE T

 VectorBase<T, N, AP, TV>::popCopy()

 {

   T ret = back();

   popBack();

   return ret;

 }

 template<typename T, size_t N, class AP, class TV>

 inline T*

 VectorBase<T, N, AP, TV>::extractRawBuffer()

 {

   T* ret;

   if (usingInlineStorage()) {

     ret = reinterpret_cast<T*>(this->malloc_(mLength * sizeof(T)));

     if (!ret)

       return nullptr;

     Impl::copyConstruct(ret, beginNoCheck(), endNoCheck());

     Impl::destroy(beginNoCheck(), endNoCheck());

     /* mBegin, mCapacity are unchanged. */

     mLength = 0;

   } else {

     ret = mBegin;

     mBegin = static_cast<T*>(storage.addr());

     mLength = 0;

     mCapacity = sInlineCapacity;

 #ifdef DEBUG

     mReserved = sInlineCapacity;

 #endif

   }

   return ret;

 }

 template<typename T, size_t N, class AP, class TV>

 inline void

 VectorBase<T, N, AP, TV>::replaceRawBuffer(T* p, size_t aLength)

 {

   MOZ_REENTRANCY_GUARD_ET_AL;

   /* Destroy what we have. */

   Impl::destroy(beginNoCheck(), endNoCheck());

   if (!usingInlineStorage())

     this->free_(beginNoCheck());

   /* Take in the new buffer. */

   if (aLength <= sInlineCapacity) {

     /*

      * We convert to inline storage if possible, even though p might

      * otherwise be acceptable.  Maybe this behaviour should be

      * specifiable with an argument to this function.

      */

     mBegin = static_cast<T*>(storage.addr());

     mLength = aLength;

     mCapacity = sInlineCapacity;

     Impl::moveConstruct(mBegin, p, p + aLength);

     Impl::destroy(p, p + aLength);

     this->free_(p);

   } else {

     mBegin = p;

     mLength = aLength;

     mCapacity = aLength;

   }

 #ifdef DEBUG

   mReserved = aLength;

 #endif

 }

 template<typename T, size_t N, class AP, class TV>

 inline size_t

 VectorBase<T, N, AP, TV>::sizeOfExcludingThis(MallocSizeOf mallocSizeOf) const

 {

   return usingInlineStorage() ? 0 : mallocSizeOf(beginNoCheck());

 }

 template<typename T, size_t N, class AP, class TV>

 inline size_t

 VectorBase<T, N, AP, TV>::sizeOfIncludingThis(MallocSizeOf mallocSizeOf) const

 {

   return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);

 }

 template<typename T, size_t N, class AP, class TV>

 inline void

 VectorBase<T, N, AP, TV>::swap(TV& other)

 {

   static_assert(N == 0,

                 "still need to implement this for N != 0");

   // This only works when inline storage is always empty.

   if (!usingInlineStorage() && other.usingInlineStorage()) {

     other.mBegin = mBegin;

     mBegin = inlineStorage();

   } else if (usingInlineStorage() && !other.usingInlineStorage()) {

     mBegin = other.mBegin;

     other.mBegin = other.inlineStorage();

   } else if (!usingInlineStorage() && !other.usingInlineStorage()) {

     Swap(mBegin, other.mBegin);

   } else {

     // This case is a no-op, since we'd set both to use their inline storage.

   }

   Swap(mLength, other.mLength);

   Swap(mCapacity, other.mCapacity);

 #ifdef DEBUG

   Swap(mReserved, other.mReserved);

 #endif

 }

 /*

  * STL-like container providing a short-lived, dynamic buffer.  Vector calls the

  * constructors/destructors of all elements stored in its internal buffer, so

  * non-PODs may be safely used.  Additionally, Vector will store the first N

  * elements in-place before resorting to dynamic allocation.

  *

  * T requirements:

  *  - default and copy constructible, assignable, destructible

  *  - operations do not throw

  * N requirements:

  *  - any value, however, N is clamped to min/max values

  * AllocPolicy:

  *  - see "Allocation policies" in AllocPolicy.h (defaults to

  *    mozilla::MallocAllocPolicy)

  *

  * Vector is not reentrant: T member functions called during Vector member

  * functions must not call back into the same object!

  */

 template<typename T,

          size_t MinInlineCapacity = 0,

          class AllocPolicy = MallocAllocPolicy>

 class Vector

   : public VectorBase<T,

                       MinInlineCapacity,

                       AllocPolicy,

                       Vector<T, MinInlineCapacity, AllocPolicy> >

 {

     typedef VectorBase<T, MinInlineCapacity, AllocPolicy, Vector> Base;

   public:

     Vector(AllocPolicy alloc = AllocPolicy()) : Base(alloc) {}

     Vector(Vector&& vec) : Base(Move(vec)) {}

     Vector& operator=(Vector&& vec) {

       return Base::operator=(Move(vec));

     }

 };

 } // namespace mozilla

 #ifdef _MSC_VER

 #pragma warning(pop)

 #endif

 #endif /* mozilla_Vector_h */