michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* vim: set ts=8 sts=2 et sw=2 tw=80: */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /* A type/length-parametrized vector class. */
michael@0: 
michael@0: #ifndef mozilla_Vector_h
michael@0: #define mozilla_Vector_h
michael@0: 
michael@0: #include "mozilla/Alignment.h"
michael@0: #include "mozilla/AllocPolicy.h"
michael@0: #include "mozilla/ArrayUtils.h" // for PointerRangeSize
michael@0: #include "mozilla/Assertions.h"
michael@0: #include "mozilla/Attributes.h"
michael@0: #include "mozilla/MathAlgorithms.h"
michael@0: #include "mozilla/MemoryReporting.h"
michael@0: #include "mozilla/Move.h"
michael@0: #include "mozilla/NullPtr.h"
michael@0: #include "mozilla/ReentrancyGuard.h"
michael@0: #include "mozilla/TemplateLib.h"
michael@0: #include "mozilla/TypeTraits.h"
michael@0: 
michael@0: #include <new> // for placement new
michael@0: 
michael@0: /* Silence dire "bugs in previous versions of MSVC have been fixed" warnings */
michael@0: #ifdef _MSC_VER
michael@0: #pragma warning(push)
michael@0: #pragma warning(disable:4345)
michael@0: #endif
michael@0: 
michael@0: namespace mozilla {
michael@0: 
michael@0: template<typename T, size_t N, class AllocPolicy, class ThisVector>
michael@0: class VectorBase;
michael@0: 
michael@0: namespace detail {
michael@0: 
michael@0: /*
michael@0:  * Check that the given capacity wastes the minimal amount of space if
michael@0:  * allocated on the heap.  This means that cap*sizeof(T) is as close to a
michael@0:  * power-of-two as possible.  growStorageBy() is responsible for ensuring
michael@0:  * this.
michael@0:  */
michael@0: template<typename T>
michael@0: static bool CapacityHasExcessSpace(size_t cap)
michael@0: {
michael@0:   size_t size = cap * sizeof(T);
michael@0:   return RoundUpPow2(size) - size >= sizeof(T);
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * This template class provides a default implementation for vector operations
michael@0:  * when the element type is not known to be a POD, as judged by IsPod.
michael@0:  */
michael@0: template<typename T, size_t N, class AP, class ThisVector, bool IsPod>
michael@0: struct VectorImpl
michael@0: {
michael@0:     /* Destroys constructed objects in the range [begin, end). */
michael@0:     static inline void destroy(T* begin, T* end) {
michael@0:       MOZ_ASSERT(begin <= end);
michael@0:       for (T* p = begin; p < end; ++p)
michael@0:         p->~T();
michael@0:     }
michael@0: 
michael@0:     /* Constructs objects in the uninitialized range [begin, end). */
michael@0:     static inline void initialize(T* begin, T* end) {
michael@0:       MOZ_ASSERT(begin <= end);
michael@0:       for (T* p = begin; p < end; ++p)
michael@0:         new(p) T();
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Copy-constructs objects in the uninitialized range
michael@0:      * [dst, dst+(srcend-srcbeg)) from the range [srcbeg, srcend).
michael@0:      */
michael@0:     template<typename U>
michael@0:     static inline void copyConstruct(T* dst, const U* srcbeg, const U* srcend) {
michael@0:       MOZ_ASSERT(srcbeg <= srcend);
michael@0:       for (const U* p = srcbeg; p < srcend; ++p, ++dst)
michael@0:         new(dst) T(*p);
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Move-constructs objects in the uninitialized range
michael@0:      * [dst, dst+(srcend-srcbeg)) from the range [srcbeg, srcend).
michael@0:      */
michael@0:     template<typename U>
michael@0:     static inline void moveConstruct(T* dst, U* srcbeg, U* srcend) {
michael@0:       MOZ_ASSERT(srcbeg <= srcend);
michael@0:       for (U* p = srcbeg; p < srcend; ++p, ++dst)
michael@0:         new(dst) T(Move(*p));
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Copy-constructs objects in the uninitialized range [dst, dst+n) from the
michael@0:      * same object u.
michael@0:      */
michael@0:     template<typename U>
michael@0:     static inline void copyConstructN(T* dst, size_t n, const U& u) {
michael@0:       for (T* end = dst + n; dst < end; ++dst)
michael@0:         new(dst) T(u);
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * Grows the given buffer to have capacity newCap, preserving the objects
michael@0:      * constructed in the range [begin, end) and updating v. Assumes that (1)
michael@0:      * newCap has not overflowed, and (2) multiplying newCap by sizeof(T) will
michael@0:      * not overflow.
michael@0:      */
michael@0:     static inline bool
michael@0:     growTo(VectorBase<T, N, AP, ThisVector>& v, size_t newCap) {
michael@0:       MOZ_ASSERT(!v.usingInlineStorage());
michael@0:       MOZ_ASSERT(!CapacityHasExcessSpace<T>(newCap));
michael@0:       T* newbuf = reinterpret_cast<T*>(v.malloc_(newCap * sizeof(T)));
michael@0:       if (!newbuf)
michael@0:         return false;
michael@0:       T* dst = newbuf;
michael@0:       T* src = v.beginNoCheck();
michael@0:       for (; src < v.endNoCheck(); ++dst, ++src)
michael@0:         new(dst) T(Move(*src));
michael@0:       VectorImpl::destroy(v.beginNoCheck(), v.endNoCheck());
michael@0:       v.free_(v.mBegin);
michael@0:       v.mBegin = newbuf;
michael@0:       /* v.mLength is unchanged. */
michael@0:       v.mCapacity = newCap;
michael@0:       return true;
michael@0:     }
michael@0: };
michael@0: 
michael@0: /*
michael@0:  * This partial template specialization provides a default implementation for
michael@0:  * vector operations when the element type is known to be a POD, as judged by
michael@0:  * IsPod.
michael@0:  */
michael@0: template<typename T, size_t N, class AP, class ThisVector>
michael@0: struct VectorImpl<T, N, AP, ThisVector, true>
michael@0: {
michael@0:     static inline void destroy(T*, T*) {}
michael@0: 
michael@0:     static inline void initialize(T* begin, T* end) {
michael@0:       /*
michael@0:        * You would think that memset would be a big win (or even break even)
michael@0:        * when we know T is a POD. But currently it's not. This is probably
michael@0:        * because |append| tends to be given small ranges and memset requires
michael@0:        * a function call that doesn't get inlined.
michael@0:        *
michael@0:        * memset(begin, 0, sizeof(T) * (end-begin));
michael@0:        */
michael@0:       MOZ_ASSERT(begin <= end);
michael@0:       for (T* p = begin; p < end; ++p)
michael@0:         new(p) T();
michael@0:     }
michael@0: 
michael@0:     template<typename U>
michael@0:     static inline void copyConstruct(T* dst, const U* srcbeg, const U* srcend) {
michael@0:       /*
michael@0:        * See above memset comment. Also, notice that copyConstruct is
michael@0:        * currently templated (T != U), so memcpy won't work without
michael@0:        * requiring T == U.
michael@0:        *
michael@0:        * memcpy(dst, srcbeg, sizeof(T) * (srcend - srcbeg));
michael@0:        */
michael@0:       MOZ_ASSERT(srcbeg <= srcend);
michael@0:       for (const U* p = srcbeg; p < srcend; ++p, ++dst)
michael@0:         *dst = *p;
michael@0:     }
michael@0: 
michael@0:     template<typename U>
michael@0:     static inline void moveConstruct(T* dst, const U* srcbeg, const U* srcend) {
michael@0:       copyConstruct(dst, srcbeg, srcend);
michael@0:     }
michael@0: 
michael@0:     static inline void copyConstructN(T* dst, size_t n, const T& t) {
michael@0:       for (T* end = dst + n; dst < end; ++dst)
michael@0:         *dst = t;
michael@0:     }
michael@0: 
michael@0:     static inline bool
michael@0:     growTo(VectorBase<T, N, AP, ThisVector>& v, size_t newCap) {
michael@0:       MOZ_ASSERT(!v.usingInlineStorage());
michael@0:       MOZ_ASSERT(!CapacityHasExcessSpace<T>(newCap));
michael@0:       size_t oldSize = sizeof(T) * v.mCapacity;
michael@0:       size_t newSize = sizeof(T) * newCap;
michael@0:       T* newbuf = reinterpret_cast<T*>(v.realloc_(v.mBegin, oldSize, newSize));
michael@0:       if (!newbuf)
michael@0:         return false;
michael@0:       v.mBegin = newbuf;
michael@0:       /* v.mLength is unchanged. */
michael@0:       v.mCapacity = newCap;
michael@0:       return true;
michael@0:     }
michael@0: };
michael@0: 
michael@0: } // namespace detail
michael@0: 
michael@0: /*
michael@0:  * A CRTP base class for vector-like classes.  Unless you really really want
michael@0:  * your own vector class -- and you almost certainly don't -- you should use
michael@0:  * mozilla::Vector instead!
michael@0:  *
michael@0:  * See mozilla::Vector for interface requirements.
michael@0:  */
michael@0: template<typename T, size_t N, class AllocPolicy, class ThisVector>
michael@0: class VectorBase : private AllocPolicy
michael@0: {
michael@0:     /* utilities */
michael@0: 
michael@0:     static const bool sElemIsPod = IsPod<T>::value;
michael@0:     typedef detail::VectorImpl<T, N, AllocPolicy, ThisVector, sElemIsPod> Impl;
michael@0:     friend struct detail::VectorImpl<T, N, AllocPolicy, ThisVector, sElemIsPod>;
michael@0: 
michael@0:     bool growStorageBy(size_t incr);
michael@0:     bool convertToHeapStorage(size_t newCap);
michael@0: 
michael@0:     /* magic constants */
michael@0: 
michael@0:     static const int sMaxInlineBytes = 1024;
michael@0: 
michael@0:     /* compute constants */
michael@0: 
michael@0:     /*
michael@0:      * Consider element size to be 1 for buffer sizing if there are 0 inline
michael@0:      * elements.  This allows us to compile when the definition of the element
michael@0:      * type is not visible here.
michael@0:      *
michael@0:      * Explicit specialization is only allowed at namespace scope, so in order
michael@0:      * to keep everything here, we use a dummy template parameter with partial
michael@0:      * specialization.
michael@0:      */
michael@0:     template<int M, int Dummy>
michael@0:     struct ElemSize
michael@0:     {
michael@0:         static const size_t value = sizeof(T);
michael@0:     };
michael@0:     template<int Dummy>
michael@0:     struct ElemSize<0, Dummy>
michael@0:     {
michael@0:         static const size_t value = 1;
michael@0:     };
michael@0: 
michael@0:     static const size_t sInlineCapacity =
michael@0:       tl::Min<N, sMaxInlineBytes / ElemSize<N, 0>::value>::value;
michael@0: 
michael@0:     /* Calculate inline buffer size; avoid 0-sized array. */
michael@0:     static const size_t sInlineBytes =
michael@0:       tl::Max<1, sInlineCapacity * ElemSize<N, 0>::value>::value;
michael@0: 
michael@0:     /* member data */
michael@0: 
michael@0:     /*
michael@0:      * Pointer to the buffer, be it inline or heap-allocated. Only [mBegin,
michael@0:      * mBegin + mLength) hold valid constructed T objects. The range [mBegin +
michael@0:      * mLength, mBegin + mCapacity) holds uninitialized memory. The range
michael@0:      * [mBegin + mLength, mBegin + mReserved) also holds uninitialized memory
michael@0:      * previously allocated by a call to reserve().
michael@0:      */
michael@0:     T* mBegin;
michael@0: 
michael@0:     /* Number of elements in the vector. */
michael@0:     size_t mLength;
michael@0: 
michael@0:     /* Max number of elements storable in the vector without resizing. */
michael@0:     size_t mCapacity;
michael@0: 
michael@0: #ifdef DEBUG
michael@0:     /* Max elements of reserved or used space in this vector. */
michael@0:     size_t mReserved;
michael@0: #endif
michael@0: 
michael@0:     /* Memory used for inline storage. */
michael@0:     AlignedStorage<sInlineBytes> storage;
michael@0: 
michael@0: #ifdef DEBUG
michael@0:     friend class ReentrancyGuard;
michael@0:     bool entered;
michael@0: #endif
michael@0: 
michael@0:     /* private accessors */
michael@0: 
michael@0:     bool usingInlineStorage() const {
michael@0:       return mBegin == const_cast<VectorBase*>(this)->inlineStorage();
michael@0:     }
michael@0: 
michael@0:     T* inlineStorage() {
michael@0:       return static_cast<T*>(storage.addr());
michael@0:     }
michael@0: 
michael@0:     T* beginNoCheck() const {
michael@0:       return mBegin;
michael@0:     }
michael@0: 
michael@0:     T* endNoCheck() {
michael@0:       return mBegin + mLength;
michael@0:     }
michael@0: 
michael@0:     const T* endNoCheck() const {
michael@0:       return mBegin + mLength;
michael@0:     }
michael@0: 
michael@0: #ifdef DEBUG
michael@0:     size_t reserved() const {
michael@0:       MOZ_ASSERT(mReserved <= mCapacity);
michael@0:       MOZ_ASSERT(mLength <= mReserved);
michael@0:       return mReserved;
michael@0:     }
michael@0: #endif
michael@0: 
michael@0:     /* Append operations guaranteed to succeed due to pre-reserved space. */
michael@0:     template<typename U> void internalAppend(U&& u);
michael@0:     template<typename U, size_t O, class BP, class UV>
michael@0:     void internalAppendAll(const VectorBase<U, O, BP, UV>& u);
michael@0:     void internalAppendN(const T& t, size_t n);
michael@0:     template<typename U> void internalAppend(const U* begin, size_t length);
michael@0: 
michael@0:   public:
michael@0:     static const size_t sMaxInlineStorage = N;
michael@0: 
michael@0:     typedef T ElementType;
michael@0: 
michael@0:     VectorBase(AllocPolicy = AllocPolicy());
michael@0:     VectorBase(ThisVector&&); /* Move constructor. */
michael@0:     ThisVector& operator=(ThisVector&&); /* Move assignment. */
michael@0:     ~VectorBase();
michael@0: 
michael@0:     /* accessors */
michael@0: 
michael@0:     const AllocPolicy& allocPolicy() const {
michael@0:       return *this;
michael@0:     }
michael@0: 
michael@0:     AllocPolicy& allocPolicy() {
michael@0:       return *this;
michael@0:     }
michael@0: 
michael@0:     enum { InlineLength = N };
michael@0: 
michael@0:     size_t length() const {
michael@0:       return mLength;
michael@0:     }
michael@0: 
michael@0:     bool empty() const {
michael@0:       return mLength == 0;
michael@0:     }
michael@0: 
michael@0:     size_t capacity() const {
michael@0:       return mCapacity;
michael@0:     }
michael@0: 
michael@0:     T* begin() {
michael@0:       MOZ_ASSERT(!entered);
michael@0:       return mBegin;
michael@0:     }
michael@0: 
michael@0:     const T* begin() const {
michael@0:       MOZ_ASSERT(!entered);
michael@0:       return mBegin;
michael@0:     }
michael@0: 
michael@0:     T* end() {
michael@0:       MOZ_ASSERT(!entered);
michael@0:       return mBegin + mLength;
michael@0:     }
michael@0: 
michael@0:     const T* end() const {
michael@0:       MOZ_ASSERT(!entered);
michael@0:       return mBegin + mLength;
michael@0:     }
michael@0: 
michael@0:     T& operator[](size_t i) {
michael@0:       MOZ_ASSERT(!entered);
michael@0:       MOZ_ASSERT(i < mLength);
michael@0:       return begin()[i];
michael@0:     }
michael@0: 
michael@0:     const T& operator[](size_t i) const {
michael@0:       MOZ_ASSERT(!entered);
michael@0:       MOZ_ASSERT(i < mLength);
michael@0:       return begin()[i];
michael@0:     }
michael@0: 
michael@0:     T& back() {
michael@0:       MOZ_ASSERT(!entered);
michael@0:       MOZ_ASSERT(!empty());
michael@0:       return *(end() - 1);
michael@0:     }
michael@0: 
michael@0:     const T& back() const {
michael@0:       MOZ_ASSERT(!entered);
michael@0:       MOZ_ASSERT(!empty());
michael@0:       return *(end() - 1);
michael@0:     }
michael@0: 
michael@0:     class Range
michael@0:     {
michael@0:         friend class VectorBase;
michael@0:         T* cur_;
michael@0:         T* end_;
michael@0:         Range(T* cur, T* end) : cur_(cur), end_(end) {
michael@0:           MOZ_ASSERT(cur <= end);
michael@0:         }
michael@0: 
michael@0:       public:
michael@0:         Range() {}
michael@0:         bool empty() const { return cur_ == end_; }
michael@0:         size_t remain() const { return PointerRangeSize(cur_, end_); }
michael@0:         T& front() const { MOZ_ASSERT(!empty()); return *cur_; }
michael@0:         void popFront() { MOZ_ASSERT(!empty()); ++cur_; }
michael@0:         T popCopyFront() { MOZ_ASSERT(!empty()); return *cur_++; }
michael@0:     };
michael@0: 
michael@0:     Range all() {
michael@0:       return Range(begin(), end());
michael@0:     }
michael@0: 
michael@0:     /* mutators */
michael@0: 
michael@0:     /**
michael@0:      * Given that the vector is empty and has no inline storage, grow to
michael@0:      * |capacity|.
michael@0:      */
michael@0:     bool initCapacity(size_t request);
michael@0: 
michael@0:     /**
michael@0:      * If reserve(length() + N) succeeds, the N next appends are guaranteed to
michael@0:      * succeed.
michael@0:      */
michael@0:     bool reserve(size_t request);
michael@0: 
michael@0:     /**
michael@0:      * Destroy elements in the range [end() - incr, end()). Does not deallocate
michael@0:      * or unreserve storage for those elements.
michael@0:      */
michael@0:     void shrinkBy(size_t incr);
michael@0: 
michael@0:     /** Grow the vector by incr elements. */
michael@0:     bool growBy(size_t incr);
michael@0: 
michael@0:     /** Call shrinkBy or growBy based on whether newSize > length(). */
michael@0:     bool resize(size_t newLength);
michael@0: 
michael@0:     /**
michael@0:      * Increase the length of the vector, but don't initialize the new elements
michael@0:      * -- leave them as uninitialized memory.
michael@0:      */
michael@0:     bool growByUninitialized(size_t incr);
michael@0:     bool resizeUninitialized(size_t newLength);
michael@0: 
michael@0:     /** Shorthand for shrinkBy(length()). */
michael@0:     void clear();
michael@0: 
michael@0:     /** Clears and releases any heap-allocated storage. */
michael@0:     void clearAndFree();
michael@0: 
michael@0:     /**
michael@0:      * If true, appending |needed| elements won't reallocate elements storage.
michael@0:      * This *doesn't* mean that infallibleAppend may be used!  You still must
michael@0:      * reserve the extra space, even if this method indicates that appends won't
michael@0:      * need to reallocate elements storage.
michael@0:      */
michael@0:     bool canAppendWithoutRealloc(size_t needed) const;
michael@0: 
michael@0:     /** Potentially fallible append operations. */
michael@0: 
michael@0:     /**
michael@0:      * This can take either a T& or a T&&. Given a T&&, it moves |u| into the
michael@0:      * vector, instead of copying it. If it fails, |u| is left unmoved. ("We are
michael@0:      * not amused.")
michael@0:      */
michael@0:     template<typename U> bool append(U&& u);
michael@0: 
michael@0:     template<typename U, size_t O, class BP, class UV>
michael@0:     bool appendAll(const VectorBase<U, O, BP, UV>& u);
michael@0:     bool appendN(const T& t, size_t n);
michael@0:     template<typename U> bool append(const U* begin, const U* end);
michael@0:     template<typename U> bool append(const U* begin, size_t length);
michael@0: 
michael@0:     /*
michael@0:      * Guaranteed-infallible append operations for use upon vectors whose
michael@0:      * memory has been pre-reserved.  Don't use this if you haven't reserved the
michael@0:      * memory!
michael@0:      */
michael@0:     template<typename U> void infallibleAppend(U&& u) {
michael@0:       internalAppend(Forward<U>(u));
michael@0:     }
michael@0:     void infallibleAppendN(const T& t, size_t n) {
michael@0:       internalAppendN(t, n);
michael@0:     }
michael@0:     template<typename U> void infallibleAppend(const U* aBegin, const U* aEnd) {
michael@0:       internalAppend(aBegin, PointerRangeSize(aBegin, aEnd));
michael@0:     }
michael@0:     template<typename U> void infallibleAppend(const U* aBegin, size_t aLength) {
michael@0:       internalAppend(aBegin, aLength);
michael@0:     }
michael@0: 
michael@0:     void popBack();
michael@0: 
michael@0:     T popCopy();
michael@0: 
michael@0:     /**
michael@0:      * Transfers ownership of the internal buffer used by this vector to the
michael@0:      * caller.  (It's the caller's responsibility to properly deallocate this
michael@0:      * buffer, in accordance with this vector's AllocPolicy.)  After this call,
michael@0:      * the vector is empty.  Since the returned buffer may need to be allocated
michael@0:      * (if the elements are currently stored in-place), the call can fail,
michael@0:      * returning nullptr.
michael@0:      *
michael@0:      * N.B. Although a T*, only the range [0, length()) is constructed.
michael@0:      */
michael@0:     T* extractRawBuffer();
michael@0: 
michael@0:     /**
michael@0:      * Transfer ownership of an array of objects into the vector.  The caller
michael@0:      * must have allocated the array in accordance with this vector's
michael@0:      * AllocPolicy.
michael@0:      *
michael@0:      * N.B. This call assumes that there are no uninitialized elements in the
michael@0:      *      passed array.
michael@0:      */
michael@0:     void replaceRawBuffer(T* p, size_t length);
michael@0: 
michael@0:     /**
michael@0:      * Places |val| at position |p|, shifting existing elements from |p| onward
michael@0:      * one position higher.  On success, |p| should not be reused because it'll
michael@0:      * be a dangling pointer if reallocation of the vector storage occurred; the
michael@0:      * return value should be used instead.  On failure, nullptr is returned.
michael@0:      *
michael@0:      * Example usage:
michael@0:      *
michael@0:      *   if (!(p = vec.insert(p, val)))
michael@0:      *     <handle failure>
michael@0:      *   <keep working with p>
michael@0:      *
michael@0:      * This is inherently a linear-time operation.  Be careful!
michael@0:      */
michael@0:     template<typename U>
michael@0:     T* insert(T* p, U&& val);
michael@0: 
michael@0:     /**
michael@0:      * Removes the element |t|, which must fall in the bounds [begin, end),
michael@0:      * shifting existing elements from |t + 1| onward one position lower.
michael@0:      */
michael@0:     void erase(T* t);
michael@0: 
michael@0:     /**
michael@0:      * Measure the size of the vector's heap-allocated storage.
michael@0:      */
michael@0:     size_t sizeOfExcludingThis(MallocSizeOf mallocSizeOf) const;
michael@0: 
michael@0:     /**
michael@0:      * Like sizeOfExcludingThis, but also measures the size of the vector
michael@0:      * object (which must be heap-allocated) itself.
michael@0:      */
michael@0:     size_t sizeOfIncludingThis(MallocSizeOf mallocSizeOf) const;
michael@0: 
michael@0:     void swap(ThisVector& other);
michael@0: 
michael@0:   private:
michael@0:     VectorBase(const VectorBase&) MOZ_DELETE;
michael@0:     void operator=(const VectorBase&) MOZ_DELETE;
michael@0: 
michael@0:     /* Move-construct/assign only from our derived class, ThisVector. */
michael@0:     VectorBase(VectorBase&&) MOZ_DELETE;
michael@0:     void operator=(VectorBase&&) MOZ_DELETE;
michael@0: };
michael@0: 
michael@0: /* This does the re-entrancy check plus several other sanity checks. */
michael@0: #define MOZ_REENTRANCY_GUARD_ET_AL \
michael@0:   ReentrancyGuard g(*this); \
michael@0:   MOZ_ASSERT_IF(usingInlineStorage(), mCapacity == sInlineCapacity); \
michael@0:   MOZ_ASSERT(reserved() <= mCapacity); \
michael@0:   MOZ_ASSERT(mLength <= reserved()); \
michael@0:   MOZ_ASSERT(mLength <= mCapacity)
michael@0: 
michael@0: /* Vector Implementation */
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: MOZ_ALWAYS_INLINE
michael@0: VectorBase<T, N, AP, TV>::VectorBase(AP ap)
michael@0:   : AP(ap),
michael@0:     mLength(0),
michael@0:     mCapacity(sInlineCapacity)
michael@0: #ifdef DEBUG
michael@0:   , mReserved(sInlineCapacity),
michael@0:     entered(false)
michael@0: #endif
michael@0: {
michael@0:   mBegin = static_cast<T*>(storage.addr());
michael@0: }
michael@0: 
michael@0: /* Move constructor. */
michael@0: template<typename T, size_t N, class AllocPolicy, class TV>
michael@0: MOZ_ALWAYS_INLINE
michael@0: VectorBase<T, N, AllocPolicy, TV>::VectorBase(TV&& rhs)
michael@0:   : AllocPolicy(Move(rhs))
michael@0: #ifdef DEBUG
michael@0:     , entered(false)
michael@0: #endif
michael@0: {
michael@0:   mLength = rhs.mLength;
michael@0:   mCapacity = rhs.mCapacity;
michael@0: #ifdef DEBUG
michael@0:   mReserved = rhs.mReserved;
michael@0: #endif
michael@0: 
michael@0:   if (rhs.usingInlineStorage()) {
michael@0:     /* We can't move the buffer over in this case, so copy elements. */
michael@0:     mBegin = static_cast<T*>(storage.addr());
michael@0:     Impl::moveConstruct(mBegin, rhs.beginNoCheck(), rhs.endNoCheck());
michael@0:     /*
michael@0:      * Leave rhs's mLength, mBegin, mCapacity, and mReserved as they are.
michael@0:      * The elements in its in-line storage still need to be destroyed.
michael@0:      */
michael@0:   } else {
michael@0:     /*
michael@0:      * Take src's buffer, and turn src into an empty vector using
michael@0:      * in-line storage.
michael@0:      */
michael@0:     mBegin = rhs.mBegin;
michael@0:     rhs.mBegin = static_cast<T*>(rhs.storage.addr());
michael@0:     rhs.mCapacity = sInlineCapacity;
michael@0:     rhs.mLength = 0;
michael@0: #ifdef DEBUG
michael@0:     rhs.mReserved = sInlineCapacity;
michael@0: #endif
michael@0:   }
michael@0: }
michael@0: 
michael@0: /* Move assignment. */
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: MOZ_ALWAYS_INLINE
michael@0: TV&
michael@0: VectorBase<T, N, AP, TV>::operator=(TV&& rhs)
michael@0: {
michael@0:   MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
michael@0:   TV* tv = static_cast<TV*>(this);
michael@0:   tv->~TV();
michael@0:   new(tv) TV(Move(rhs));
michael@0:   return *tv;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: MOZ_ALWAYS_INLINE
michael@0: VectorBase<T, N, AP, TV>::~VectorBase()
michael@0: {
michael@0:   MOZ_REENTRANCY_GUARD_ET_AL;
michael@0:   Impl::destroy(beginNoCheck(), endNoCheck());
michael@0:   if (!usingInlineStorage())
michael@0:     this->free_(beginNoCheck());
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * This function will create a new heap buffer with capacity newCap,
michael@0:  * move all elements in the inline buffer to this new buffer,
michael@0:  * and fail on OOM.
michael@0:  */
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: inline bool
michael@0: VectorBase<T, N, AP, TV>::convertToHeapStorage(size_t newCap)
michael@0: {
michael@0:   MOZ_ASSERT(usingInlineStorage());
michael@0: 
michael@0:   /* Allocate buffer. */
michael@0:   MOZ_ASSERT(!detail::CapacityHasExcessSpace<T>(newCap));
michael@0:   T* newBuf = reinterpret_cast<T*>(this->malloc_(newCap * sizeof(T)));
michael@0:   if (!newBuf)
michael@0:     return false;
michael@0: 
michael@0:   /* Copy inline elements into heap buffer. */
michael@0:   Impl::moveConstruct(newBuf, beginNoCheck(), endNoCheck());
michael@0:   Impl::destroy(beginNoCheck(), endNoCheck());
michael@0: 
michael@0:   /* Switch in heap buffer. */
michael@0:   mBegin = newBuf;
michael@0:   /* mLength is unchanged. */
michael@0:   mCapacity = newCap;
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: MOZ_NEVER_INLINE bool
michael@0: VectorBase<T, N, AP, TV>::growStorageBy(size_t incr)
michael@0: {
michael@0:   MOZ_ASSERT(mLength + incr > mCapacity);
michael@0:   MOZ_ASSERT_IF(!usingInlineStorage(),
michael@0:                 !detail::CapacityHasExcessSpace<T>(mCapacity));
michael@0: 
michael@0:   /*
michael@0:    * When choosing a new capacity, its size should is as close to 2**N bytes
michael@0:    * as possible.  2**N-sized requests are best because they are unlikely to
michael@0:    * be rounded up by the allocator.  Asking for a 2**N number of elements
michael@0:    * isn't as good, because if sizeof(T) is not a power-of-two that would
michael@0:    * result in a non-2**N request size.
michael@0:    */
michael@0: 
michael@0:   size_t newCap;
michael@0: 
michael@0:   if (incr == 1) {
michael@0:     if (usingInlineStorage()) {
michael@0:       /* This case occurs in ~70--80% of the calls to this function. */
michael@0:       size_t newSize =
michael@0:         tl::RoundUpPow2<(sInlineCapacity + 1) * sizeof(T)>::value;
michael@0:       newCap = newSize / sizeof(T);
michael@0:       goto convert;
michael@0:     }
michael@0: 
michael@0:     if (mLength == 0) {
michael@0:       /* This case occurs in ~0--10% of the calls to this function. */
michael@0:       newCap = 1;
michael@0:       goto grow;
michael@0:     }
michael@0: 
michael@0:     /* This case occurs in ~15--20% of the calls to this function. */
michael@0: 
michael@0:     /*
michael@0:      * Will mLength * 4 *sizeof(T) overflow?  This condition limits a vector
michael@0:      * to 1GB of memory on a 32-bit system, which is a reasonable limit.  It
michael@0:      * also ensures that
michael@0:      *
michael@0:      *   static_cast<char*>(end()) - static_cast<char*>(begin())
michael@0:      *
michael@0:      * doesn't overflow ptrdiff_t (see bug 510319).
michael@0:      */
michael@0:     if (mLength & tl::MulOverflowMask<4 * sizeof(T)>::value) {
michael@0:       this->reportAllocOverflow();
michael@0:       return false;
michael@0:     }
michael@0: 
michael@0:     /*
michael@0:      * If we reach here, the existing capacity will have a size that is already
michael@0:      * as close to 2^N as sizeof(T) will allow.  Just double the capacity, and
michael@0:      * then there might be space for one more element.
michael@0:      */
michael@0:     newCap = mLength * 2;
michael@0:     if (detail::CapacityHasExcessSpace<T>(newCap))
michael@0:       newCap += 1;
michael@0:   } else {
michael@0:     /* This case occurs in ~2% of the calls to this function. */
michael@0:     size_t newMinCap = mLength + incr;
michael@0: 
michael@0:     /* Did mLength + incr overflow?  Will newCap * sizeof(T) overflow? */
michael@0:     if (newMinCap < mLength ||
michael@0:         newMinCap & tl::MulOverflowMask<2 * sizeof(T)>::value)
michael@0:     {
michael@0:       this->reportAllocOverflow();
michael@0:       return false;
michael@0:     }
michael@0: 
michael@0:     size_t newMinSize = newMinCap * sizeof(T);
michael@0:     size_t newSize = RoundUpPow2(newMinSize);
michael@0:     newCap = newSize / sizeof(T);
michael@0:   }
michael@0: 
michael@0:   if (usingInlineStorage()) {
michael@0:   convert:
michael@0:     return convertToHeapStorage(newCap);
michael@0:   }
michael@0: 
michael@0: grow:
michael@0:   return Impl::growTo(*this, newCap);
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: inline bool
michael@0: VectorBase<T, N, AP, TV>::initCapacity(size_t request)
michael@0: {
michael@0:   MOZ_ASSERT(empty());
michael@0:   MOZ_ASSERT(usingInlineStorage());
michael@0:   if (request == 0)
michael@0:     return true;
michael@0:   T* newbuf = reinterpret_cast<T*>(this->malloc_(request * sizeof(T)));
michael@0:   if (!newbuf)
michael@0:     return false;
michael@0:   mBegin = newbuf;
michael@0:   mCapacity = request;
michael@0: #ifdef DEBUG
michael@0:   mReserved = request;
michael@0: #endif
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: inline bool
michael@0: VectorBase<T, N, AP, TV>::reserve(size_t request)
michael@0: {
michael@0:   MOZ_REENTRANCY_GUARD_ET_AL;
michael@0:   if (request > mCapacity && !growStorageBy(request - mLength))
michael@0:     return false;
michael@0: 
michael@0: #ifdef DEBUG
michael@0:   if (request > mReserved)
michael@0:     mReserved = request;
michael@0:   MOZ_ASSERT(mLength <= mReserved);
michael@0:   MOZ_ASSERT(mReserved <= mCapacity);
michael@0: #endif
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: inline void
michael@0: VectorBase<T, N, AP, TV>::shrinkBy(size_t incr)
michael@0: {
michael@0:   MOZ_REENTRANCY_GUARD_ET_AL;
michael@0:   MOZ_ASSERT(incr <= mLength);
michael@0:   Impl::destroy(endNoCheck() - incr, endNoCheck());
michael@0:   mLength -= incr;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: MOZ_ALWAYS_INLINE bool
michael@0: VectorBase<T, N, AP, TV>::growBy(size_t incr)
michael@0: {
michael@0:   MOZ_REENTRANCY_GUARD_ET_AL;
michael@0:   if (incr > mCapacity - mLength && !growStorageBy(incr))
michael@0:     return false;
michael@0: 
michael@0:   MOZ_ASSERT(mLength + incr <= mCapacity);
michael@0:   T* newend = endNoCheck() + incr;
michael@0:   Impl::initialize(endNoCheck(), newend);
michael@0:   mLength += incr;
michael@0: #ifdef DEBUG
michael@0:   if (mLength > mReserved)
michael@0:     mReserved = mLength;
michael@0: #endif
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: MOZ_ALWAYS_INLINE bool
michael@0: VectorBase<T, N, AP, TV>::growByUninitialized(size_t incr)
michael@0: {
michael@0:   MOZ_REENTRANCY_GUARD_ET_AL;
michael@0:   if (incr > mCapacity - mLength && !growStorageBy(incr))
michael@0:     return false;
michael@0: 
michael@0:   MOZ_ASSERT(mLength + incr <= mCapacity);
michael@0:   mLength += incr;
michael@0: #ifdef DEBUG
michael@0:   if (mLength > mReserved)
michael@0:     mReserved = mLength;
michael@0: #endif
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: inline bool
michael@0: VectorBase<T, N, AP, TV>::resize(size_t newLength)
michael@0: {
michael@0:   size_t curLength = mLength;
michael@0:   if (newLength > curLength)
michael@0:     return growBy(newLength - curLength);
michael@0:   shrinkBy(curLength - newLength);
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: MOZ_ALWAYS_INLINE bool
michael@0: VectorBase<T, N, AP, TV>::resizeUninitialized(size_t newLength)
michael@0: {
michael@0:   size_t curLength = mLength;
michael@0:   if (newLength > curLength)
michael@0:     return growByUninitialized(newLength - curLength);
michael@0:   shrinkBy(curLength - newLength);
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: inline void
michael@0: VectorBase<T, N, AP, TV>::clear()
michael@0: {
michael@0:   MOZ_REENTRANCY_GUARD_ET_AL;
michael@0:   Impl::destroy(beginNoCheck(), endNoCheck());
michael@0:   mLength = 0;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: inline void
michael@0: VectorBase<T, N, AP, TV>::clearAndFree()
michael@0: {
michael@0:   clear();
michael@0: 
michael@0:   if (usingInlineStorage())
michael@0:     return;
michael@0: 
michael@0:   this->free_(beginNoCheck());
michael@0:   mBegin = static_cast<T*>(storage.addr());
michael@0:   mCapacity = sInlineCapacity;
michael@0: #ifdef DEBUG
michael@0:   mReserved = sInlineCapacity;
michael@0: #endif
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: inline bool
michael@0: VectorBase<T, N, AP, TV>::canAppendWithoutRealloc(size_t needed) const
michael@0: {
michael@0:   return mLength + needed <= mCapacity;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: template<typename U, size_t O, class BP, class UV>
michael@0: MOZ_ALWAYS_INLINE void
michael@0: VectorBase<T, N, AP, TV>::internalAppendAll(const VectorBase<U, O, BP, UV>& other)
michael@0: {
michael@0:   internalAppend(other.begin(), other.length());
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: template<typename U>
michael@0: MOZ_ALWAYS_INLINE void
michael@0: VectorBase<T, N, AP, TV>::internalAppend(U&& u)
michael@0: {
michael@0:   MOZ_ASSERT(mLength + 1 <= mReserved);
michael@0:   MOZ_ASSERT(mReserved <= mCapacity);
michael@0:   new(endNoCheck()) T(Forward<U>(u));
michael@0:   ++mLength;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: MOZ_ALWAYS_INLINE bool
michael@0: VectorBase<T, N, AP, TV>::appendN(const T& t, size_t needed)
michael@0: {
michael@0:   MOZ_REENTRANCY_GUARD_ET_AL;
michael@0:   if (mLength + needed > mCapacity && !growStorageBy(needed))
michael@0:     return false;
michael@0: 
michael@0: #ifdef DEBUG
michael@0:   if (mLength + needed > mReserved)
michael@0:     mReserved = mLength + needed;
michael@0: #endif
michael@0:   internalAppendN(t, needed);
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: MOZ_ALWAYS_INLINE void
michael@0: VectorBase<T, N, AP, TV>::internalAppendN(const T& t, size_t needed)
michael@0: {
michael@0:   MOZ_ASSERT(mLength + needed <= mReserved);
michael@0:   MOZ_ASSERT(mReserved <= mCapacity);
michael@0:   Impl::copyConstructN(endNoCheck(), needed, t);
michael@0:   mLength += needed;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: template<typename U>
michael@0: inline T*
michael@0: VectorBase<T, N, AP, TV>::insert(T* p, U&& val)
michael@0: {
michael@0:   MOZ_ASSERT(begin() <= p);
michael@0:   MOZ_ASSERT(p <= end());
michael@0:   size_t pos = p - begin();
michael@0:   MOZ_ASSERT(pos <= mLength);
michael@0:   size_t oldLength = mLength;
michael@0:   if (pos == oldLength) {
michael@0:     if (!append(Forward<U>(val)))
michael@0:       return nullptr;
michael@0:   } else {
michael@0:     T oldBack = Move(back());
michael@0:     if (!append(Move(oldBack))) /* Dup the last element. */
michael@0:       return nullptr;
michael@0:     for (size_t i = oldLength; i > pos; --i)
michael@0:       (*this)[i] = Move((*this)[i - 1]);
michael@0:     (*this)[pos] = Forward<U>(val);
michael@0:   }
michael@0:   return begin() + pos;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: inline void
michael@0: VectorBase<T, N, AP, TV>::erase(T* it)
michael@0: {
michael@0:   MOZ_ASSERT(begin() <= it);
michael@0:   MOZ_ASSERT(it < end());
michael@0:   while (it + 1 < end()) {
michael@0:     *it = *(it + 1);
michael@0:     ++it;
michael@0:   }
michael@0:     popBack();
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: template<typename U>
michael@0: MOZ_ALWAYS_INLINE bool
michael@0: VectorBase<T, N, AP, TV>::append(const U* insBegin, const U* insEnd)
michael@0: {
michael@0:   MOZ_REENTRANCY_GUARD_ET_AL;
michael@0:   size_t needed = PointerRangeSize(insBegin, insEnd);
michael@0:   if (mLength + needed > mCapacity && !growStorageBy(needed))
michael@0:     return false;
michael@0: 
michael@0: #ifdef DEBUG
michael@0:   if (mLength + needed > mReserved)
michael@0:     mReserved = mLength + needed;
michael@0: #endif
michael@0:   internalAppend(insBegin, needed);
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: template<typename U>
michael@0: MOZ_ALWAYS_INLINE void
michael@0: VectorBase<T, N, AP, TV>::internalAppend(const U* insBegin, size_t insLength)
michael@0: {
michael@0:   MOZ_ASSERT(mLength + insLength <= mReserved);
michael@0:   MOZ_ASSERT(mReserved <= mCapacity);
michael@0:   Impl::copyConstruct(endNoCheck(), insBegin, insBegin + insLength);
michael@0:   mLength += insLength;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: template<typename U>
michael@0: MOZ_ALWAYS_INLINE bool
michael@0: VectorBase<T, N, AP, TV>::append(U&& u)
michael@0: {
michael@0:   MOZ_REENTRANCY_GUARD_ET_AL;
michael@0:   if (mLength == mCapacity && !growStorageBy(1))
michael@0:     return false;
michael@0: 
michael@0: #ifdef DEBUG
michael@0:   if (mLength + 1 > mReserved)
michael@0:     mReserved = mLength + 1;
michael@0: #endif
michael@0:   internalAppend(Forward<U>(u));
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: template<typename U, size_t O, class BP, class UV>
michael@0: MOZ_ALWAYS_INLINE bool
michael@0: VectorBase<T, N, AP, TV>::appendAll(const VectorBase<U, O, BP, UV>& other)
michael@0: {
michael@0:   return append(other.begin(), other.length());
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: template<class U>
michael@0: MOZ_ALWAYS_INLINE bool
michael@0: VectorBase<T, N, AP, TV>::append(const U *insBegin, size_t insLength)
michael@0: {
michael@0:   return append(insBegin, insBegin + insLength);
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: MOZ_ALWAYS_INLINE void
michael@0: VectorBase<T, N, AP, TV>::popBack()
michael@0: {
michael@0:   MOZ_REENTRANCY_GUARD_ET_AL;
michael@0:   MOZ_ASSERT(!empty());
michael@0:   --mLength;
michael@0:   endNoCheck()->~T();
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: MOZ_ALWAYS_INLINE T
michael@0: VectorBase<T, N, AP, TV>::popCopy()
michael@0: {
michael@0:   T ret = back();
michael@0:   popBack();
michael@0:   return ret;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: inline T*
michael@0: VectorBase<T, N, AP, TV>::extractRawBuffer()
michael@0: {
michael@0:   T* ret;
michael@0:   if (usingInlineStorage()) {
michael@0:     ret = reinterpret_cast<T*>(this->malloc_(mLength * sizeof(T)));
michael@0:     if (!ret)
michael@0:       return nullptr;
michael@0:     Impl::copyConstruct(ret, beginNoCheck(), endNoCheck());
michael@0:     Impl::destroy(beginNoCheck(), endNoCheck());
michael@0:     /* mBegin, mCapacity are unchanged. */
michael@0:     mLength = 0;
michael@0:   } else {
michael@0:     ret = mBegin;
michael@0:     mBegin = static_cast<T*>(storage.addr());
michael@0:     mLength = 0;
michael@0:     mCapacity = sInlineCapacity;
michael@0: #ifdef DEBUG
michael@0:     mReserved = sInlineCapacity;
michael@0: #endif
michael@0:   }
michael@0:   return ret;
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: inline void
michael@0: VectorBase<T, N, AP, TV>::replaceRawBuffer(T* p, size_t aLength)
michael@0: {
michael@0:   MOZ_REENTRANCY_GUARD_ET_AL;
michael@0: 
michael@0:   /* Destroy what we have. */
michael@0:   Impl::destroy(beginNoCheck(), endNoCheck());
michael@0:   if (!usingInlineStorage())
michael@0:     this->free_(beginNoCheck());
michael@0: 
michael@0:   /* Take in the new buffer. */
michael@0:   if (aLength <= sInlineCapacity) {
michael@0:     /*
michael@0:      * We convert to inline storage if possible, even though p might
michael@0:      * otherwise be acceptable.  Maybe this behaviour should be
michael@0:      * specifiable with an argument to this function.
michael@0:      */
michael@0:     mBegin = static_cast<T*>(storage.addr());
michael@0:     mLength = aLength;
michael@0:     mCapacity = sInlineCapacity;
michael@0:     Impl::moveConstruct(mBegin, p, p + aLength);
michael@0:     Impl::destroy(p, p + aLength);
michael@0:     this->free_(p);
michael@0:   } else {
michael@0:     mBegin = p;
michael@0:     mLength = aLength;
michael@0:     mCapacity = aLength;
michael@0:   }
michael@0: #ifdef DEBUG
michael@0:   mReserved = aLength;
michael@0: #endif
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: inline size_t
michael@0: VectorBase<T, N, AP, TV>::sizeOfExcludingThis(MallocSizeOf mallocSizeOf) const
michael@0: {
michael@0:   return usingInlineStorage() ? 0 : mallocSizeOf(beginNoCheck());
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: inline size_t
michael@0: VectorBase<T, N, AP, TV>::sizeOfIncludingThis(MallocSizeOf mallocSizeOf) const
michael@0: {
michael@0:   return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
michael@0: }
michael@0: 
michael@0: template<typename T, size_t N, class AP, class TV>
michael@0: inline void
michael@0: VectorBase<T, N, AP, TV>::swap(TV& other)
michael@0: {
michael@0:   static_assert(N == 0,
michael@0:                 "still need to implement this for N != 0");
michael@0: 
michael@0:   // This only works when inline storage is always empty.
michael@0:   if (!usingInlineStorage() && other.usingInlineStorage()) {
michael@0:     other.mBegin = mBegin;
michael@0:     mBegin = inlineStorage();
michael@0:   } else if (usingInlineStorage() && !other.usingInlineStorage()) {
michael@0:     mBegin = other.mBegin;
michael@0:     other.mBegin = other.inlineStorage();
michael@0:   } else if (!usingInlineStorage() && !other.usingInlineStorage()) {
michael@0:     Swap(mBegin, other.mBegin);
michael@0:   } else {
michael@0:     // This case is a no-op, since we'd set both to use their inline storage.
michael@0:   }
michael@0: 
michael@0:   Swap(mLength, other.mLength);
michael@0:   Swap(mCapacity, other.mCapacity);
michael@0: #ifdef DEBUG
michael@0:   Swap(mReserved, other.mReserved);
michael@0: #endif
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * STL-like container providing a short-lived, dynamic buffer.  Vector calls the
michael@0:  * constructors/destructors of all elements stored in its internal buffer, so
michael@0:  * non-PODs may be safely used.  Additionally, Vector will store the first N
michael@0:  * elements in-place before resorting to dynamic allocation.
michael@0:  *
michael@0:  * T requirements:
michael@0:  *  - default and copy constructible, assignable, destructible
michael@0:  *  - operations do not throw
michael@0:  * N requirements:
michael@0:  *  - any value, however, N is clamped to min/max values
michael@0:  * AllocPolicy:
michael@0:  *  - see "Allocation policies" in AllocPolicy.h (defaults to
michael@0:  *    mozilla::MallocAllocPolicy)
michael@0:  *
michael@0:  * Vector is not reentrant: T member functions called during Vector member
michael@0:  * functions must not call back into the same object!
michael@0:  */
michael@0: template<typename T,
michael@0:          size_t MinInlineCapacity = 0,
michael@0:          class AllocPolicy = MallocAllocPolicy>
michael@0: class Vector
michael@0:   : public VectorBase<T,
michael@0:                       MinInlineCapacity,
michael@0:                       AllocPolicy,
michael@0:                       Vector<T, MinInlineCapacity, AllocPolicy> >
michael@0: {
michael@0:     typedef VectorBase<T, MinInlineCapacity, AllocPolicy, Vector> Base;
michael@0: 
michael@0:   public:
michael@0:     Vector(AllocPolicy alloc = AllocPolicy()) : Base(alloc) {}
michael@0:     Vector(Vector&& vec) : Base(Move(vec)) {}
michael@0:     Vector& operator=(Vector&& vec) {
michael@0:       return Base::operator=(Move(vec));
michael@0:     }
michael@0: };
michael@0: 
michael@0: } // namespace mozilla
michael@0: 
michael@0: #ifdef _MSC_VER
michael@0: #pragma warning(pop)
michael@0: #endif
michael@0: 
michael@0: #endif /* mozilla_Vector_h */