1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/mfbt/Vector.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1207 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* vim: set ts=8 sts=2 et sw=2 tw=80: */
1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +/* A type/length-parametrized vector class. */
1.11 +
1.12 +#ifndef mozilla_Vector_h
1.13 +#define mozilla_Vector_h
1.14 +
1.15 +#include "mozilla/Alignment.h"
1.16 +#include "mozilla/AllocPolicy.h"
1.17 +#include "mozilla/ArrayUtils.h" // for PointerRangeSize
1.18 +#include "mozilla/Assertions.h"
1.19 +#include "mozilla/Attributes.h"
1.20 +#include "mozilla/MathAlgorithms.h"
1.21 +#include "mozilla/MemoryReporting.h"
1.22 +#include "mozilla/Move.h"
1.23 +#include "mozilla/NullPtr.h"
1.24 +#include "mozilla/ReentrancyGuard.h"
1.25 +#include "mozilla/TemplateLib.h"
1.26 +#include "mozilla/TypeTraits.h"
1.27 +
1.28 +#include <new> // for placement new
1.29 +
1.30 +/* Silence dire "bugs in previous versions of MSVC have been fixed" warnings */
1.31 +#ifdef _MSC_VER
1.32 +#pragma warning(push)
1.33 +#pragma warning(disable:4345)
1.34 +#endif
1.35 +
1.36 +namespace mozilla {
1.37 +
1.38 +template<typename T, size_t N, class AllocPolicy, class ThisVector>
1.39 +class VectorBase;
1.40 +
1.41 +namespace detail {
1.42 +
1.43 +/*
1.44 + * Check that the given capacity wastes the minimal amount of space if
1.45 + * allocated on the heap. This means that cap*sizeof(T) is as close to a
1.46 + * power-of-two as possible. growStorageBy() is responsible for ensuring
1.47 + * this.
1.48 + */
1.49 +template<typename T>
1.50 +static bool CapacityHasExcessSpace(size_t cap)
1.51 +{
1.52 + size_t size = cap * sizeof(T);
1.53 + return RoundUpPow2(size) - size >= sizeof(T);
1.54 +}
1.55 +
1.56 +/*
1.57 + * This template class provides a default implementation for vector operations
1.58 + * when the element type is not known to be a POD, as judged by IsPod.
1.59 + */
1.60 +template<typename T, size_t N, class AP, class ThisVector, bool IsPod>
1.61 +struct VectorImpl
1.62 +{
1.63 + /* Destroys constructed objects in the range [begin, end). */
1.64 + static inline void destroy(T* begin, T* end) {
1.65 + MOZ_ASSERT(begin <= end);
1.66 + for (T* p = begin; p < end; ++p)
1.67 + p->~T();
1.68 + }
1.69 +
1.70 + /* Constructs objects in the uninitialized range [begin, end). */
1.71 + static inline void initialize(T* begin, T* end) {
1.72 + MOZ_ASSERT(begin <= end);
1.73 + for (T* p = begin; p < end; ++p)
1.74 + new(p) T();
1.75 + }
1.76 +
1.77 + /*
1.78 + * Copy-constructs objects in the uninitialized range
1.79 + * [dst, dst+(srcend-srcbeg)) from the range [srcbeg, srcend).
1.80 + */
1.81 + template<typename U>
1.82 + static inline void copyConstruct(T* dst, const U* srcbeg, const U* srcend) {
1.83 + MOZ_ASSERT(srcbeg <= srcend);
1.84 + for (const U* p = srcbeg; p < srcend; ++p, ++dst)
1.85 + new(dst) T(*p);
1.86 + }
1.87 +
1.88 + /*
1.89 + * Move-constructs objects in the uninitialized range
1.90 + * [dst, dst+(srcend-srcbeg)) from the range [srcbeg, srcend).
1.91 + */
1.92 + template<typename U>
1.93 + static inline void moveConstruct(T* dst, U* srcbeg, U* srcend) {
1.94 + MOZ_ASSERT(srcbeg <= srcend);
1.95 + for (U* p = srcbeg; p < srcend; ++p, ++dst)
1.96 + new(dst) T(Move(*p));
1.97 + }
1.98 +
1.99 + /*
1.100 + * Copy-constructs objects in the uninitialized range [dst, dst+n) from the
1.101 + * same object u.
1.102 + */
1.103 + template<typename U>
1.104 + static inline void copyConstructN(T* dst, size_t n, const U& u) {
1.105 + for (T* end = dst + n; dst < end; ++dst)
1.106 + new(dst) T(u);
1.107 + }
1.108 +
1.109 + /*
1.110 + * Grows the given buffer to have capacity newCap, preserving the objects
1.111 + * constructed in the range [begin, end) and updating v. Assumes that (1)
1.112 + * newCap has not overflowed, and (2) multiplying newCap by sizeof(T) will
1.113 + * not overflow.
1.114 + */
1.115 + static inline bool
1.116 + growTo(VectorBase<T, N, AP, ThisVector>& v, size_t newCap) {
1.117 + MOZ_ASSERT(!v.usingInlineStorage());
1.118 + MOZ_ASSERT(!CapacityHasExcessSpace<T>(newCap));
1.119 + T* newbuf = reinterpret_cast<T*>(v.malloc_(newCap * sizeof(T)));
1.120 + if (!newbuf)
1.121 + return false;
1.122 + T* dst = newbuf;
1.123 + T* src = v.beginNoCheck();
1.124 + for (; src < v.endNoCheck(); ++dst, ++src)
1.125 + new(dst) T(Move(*src));
1.126 + VectorImpl::destroy(v.beginNoCheck(), v.endNoCheck());
1.127 + v.free_(v.mBegin);
1.128 + v.mBegin = newbuf;
1.129 + /* v.mLength is unchanged. */
1.130 + v.mCapacity = newCap;
1.131 + return true;
1.132 + }
1.133 +};
1.134 +
1.135 +/*
1.136 + * This partial template specialization provides a default implementation for
1.137 + * vector operations when the element type is known to be a POD, as judged by
1.138 + * IsPod.
1.139 + */
1.140 +template<typename T, size_t N, class AP, class ThisVector>
1.141 +struct VectorImpl<T, N, AP, ThisVector, true>
1.142 +{
1.143 + static inline void destroy(T*, T*) {}
1.144 +
1.145 + static inline void initialize(T* begin, T* end) {
1.146 + /*
1.147 + * You would think that memset would be a big win (or even break even)
1.148 + * when we know T is a POD. But currently it's not. This is probably
1.149 + * because |append| tends to be given small ranges and memset requires
1.150 + * a function call that doesn't get inlined.
1.151 + *
1.152 + * memset(begin, 0, sizeof(T) * (end-begin));
1.153 + */
1.154 + MOZ_ASSERT(begin <= end);
1.155 + for (T* p = begin; p < end; ++p)
1.156 + new(p) T();
1.157 + }
1.158 +
1.159 + template<typename U>
1.160 + static inline void copyConstruct(T* dst, const U* srcbeg, const U* srcend) {
1.161 + /*
1.162 + * See above memset comment. Also, notice that copyConstruct is
1.163 + * currently templated (T != U), so memcpy won't work without
1.164 + * requiring T == U.
1.165 + *
1.166 + * memcpy(dst, srcbeg, sizeof(T) * (srcend - srcbeg));
1.167 + */
1.168 + MOZ_ASSERT(srcbeg <= srcend);
1.169 + for (const U* p = srcbeg; p < srcend; ++p, ++dst)
1.170 + *dst = *p;
1.171 + }
1.172 +
1.173 + template<typename U>
1.174 + static inline void moveConstruct(T* dst, const U* srcbeg, const U* srcend) {
1.175 + copyConstruct(dst, srcbeg, srcend);
1.176 + }
1.177 +
1.178 + static inline void copyConstructN(T* dst, size_t n, const T& t) {
1.179 + for (T* end = dst + n; dst < end; ++dst)
1.180 + *dst = t;
1.181 + }
1.182 +
1.183 + static inline bool
1.184 + growTo(VectorBase<T, N, AP, ThisVector>& v, size_t newCap) {
1.185 + MOZ_ASSERT(!v.usingInlineStorage());
1.186 + MOZ_ASSERT(!CapacityHasExcessSpace<T>(newCap));
1.187 + size_t oldSize = sizeof(T) * v.mCapacity;
1.188 + size_t newSize = sizeof(T) * newCap;
1.189 + T* newbuf = reinterpret_cast<T*>(v.realloc_(v.mBegin, oldSize, newSize));
1.190 + if (!newbuf)
1.191 + return false;
1.192 + v.mBegin = newbuf;
1.193 + /* v.mLength is unchanged. */
1.194 + v.mCapacity = newCap;
1.195 + return true;
1.196 + }
1.197 +};
1.198 +
1.199 +} // namespace detail
1.200 +
1.201 +/*
1.202 + * A CRTP base class for vector-like classes. Unless you really really want
1.203 + * your own vector class -- and you almost certainly don't -- you should use
1.204 + * mozilla::Vector instead!
1.205 + *
1.206 + * See mozilla::Vector for interface requirements.
1.207 + */
1.208 +template<typename T, size_t N, class AllocPolicy, class ThisVector>
1.209 +class VectorBase : private AllocPolicy
1.210 +{
1.211 + /* utilities */
1.212 +
1.213 + static const bool sElemIsPod = IsPod<T>::value;
1.214 + typedef detail::VectorImpl<T, N, AllocPolicy, ThisVector, sElemIsPod> Impl;
1.215 + friend struct detail::VectorImpl<T, N, AllocPolicy, ThisVector, sElemIsPod>;
1.216 +
1.217 + bool growStorageBy(size_t incr);
1.218 + bool convertToHeapStorage(size_t newCap);
1.219 +
1.220 + /* magic constants */
1.221 +
1.222 + static const int sMaxInlineBytes = 1024;
1.223 +
1.224 + /* compute constants */
1.225 +
1.226 + /*
1.227 + * Consider element size to be 1 for buffer sizing if there are 0 inline
1.228 + * elements. This allows us to compile when the definition of the element
1.229 + * type is not visible here.
1.230 + *
1.231 + * Explicit specialization is only allowed at namespace scope, so in order
1.232 + * to keep everything here, we use a dummy template parameter with partial
1.233 + * specialization.
1.234 + */
1.235 + template<int M, int Dummy>
1.236 + struct ElemSize
1.237 + {
1.238 + static const size_t value = sizeof(T);
1.239 + };
1.240 + template<int Dummy>
1.241 + struct ElemSize<0, Dummy>
1.242 + {
1.243 + static const size_t value = 1;
1.244 + };
1.245 +
1.246 + static const size_t sInlineCapacity =
1.247 + tl::Min<N, sMaxInlineBytes / ElemSize<N, 0>::value>::value;
1.248 +
1.249 + /* Calculate inline buffer size; avoid 0-sized array. */
1.250 + static const size_t sInlineBytes =
1.251 + tl::Max<1, sInlineCapacity * ElemSize<N, 0>::value>::value;
1.252 +
1.253 + /* member data */
1.254 +
1.255 + /*
1.256 + * Pointer to the buffer, be it inline or heap-allocated. Only [mBegin,
1.257 + * mBegin + mLength) hold valid constructed T objects. The range [mBegin +
1.258 + * mLength, mBegin + mCapacity) holds uninitialized memory. The range
1.259 + * [mBegin + mLength, mBegin + mReserved) also holds uninitialized memory
1.260 + * previously allocated by a call to reserve().
1.261 + */
1.262 + T* mBegin;
1.263 +
1.264 + /* Number of elements in the vector. */
1.265 + size_t mLength;
1.266 +
1.267 + /* Max number of elements storable in the vector without resizing. */
1.268 + size_t mCapacity;
1.269 +
1.270 +#ifdef DEBUG
1.271 + /* Max elements of reserved or used space in this vector. */
1.272 + size_t mReserved;
1.273 +#endif
1.274 +
1.275 + /* Memory used for inline storage. */
1.276 + AlignedStorage<sInlineBytes> storage;
1.277 +
1.278 +#ifdef DEBUG
1.279 + friend class ReentrancyGuard;
1.280 + bool entered;
1.281 +#endif
1.282 +
1.283 + /* private accessors */
1.284 +
1.285 + bool usingInlineStorage() const {
1.286 + return mBegin == const_cast<VectorBase*>(this)->inlineStorage();
1.287 + }
1.288 +
1.289 + T* inlineStorage() {
1.290 + return static_cast<T*>(storage.addr());
1.291 + }
1.292 +
1.293 + T* beginNoCheck() const {
1.294 + return mBegin;
1.295 + }
1.296 +
1.297 + T* endNoCheck() {
1.298 + return mBegin + mLength;
1.299 + }
1.300 +
1.301 + const T* endNoCheck() const {
1.302 + return mBegin + mLength;
1.303 + }
1.304 +
1.305 +#ifdef DEBUG
1.306 + size_t reserved() const {
1.307 + MOZ_ASSERT(mReserved <= mCapacity);
1.308 + MOZ_ASSERT(mLength <= mReserved);
1.309 + return mReserved;
1.310 + }
1.311 +#endif
1.312 +
1.313 + /* Append operations guaranteed to succeed due to pre-reserved space. */
1.314 + template<typename U> void internalAppend(U&& u);
1.315 + template<typename U, size_t O, class BP, class UV>
1.316 + void internalAppendAll(const VectorBase<U, O, BP, UV>& u);
1.317 + void internalAppendN(const T& t, size_t n);
1.318 + template<typename U> void internalAppend(const U* begin, size_t length);
1.319 +
1.320 + public:
1.321 + static const size_t sMaxInlineStorage = N;
1.322 +
1.323 + typedef T ElementType;
1.324 +
1.325 + VectorBase(AllocPolicy = AllocPolicy());
1.326 + VectorBase(ThisVector&&); /* Move constructor. */
1.327 + ThisVector& operator=(ThisVector&&); /* Move assignment. */
1.328 + ~VectorBase();
1.329 +
1.330 + /* accessors */
1.331 +
1.332 + const AllocPolicy& allocPolicy() const {
1.333 + return *this;
1.334 + }
1.335 +
1.336 + AllocPolicy& allocPolicy() {
1.337 + return *this;
1.338 + }
1.339 +
1.340 + enum { InlineLength = N };
1.341 +
1.342 + size_t length() const {
1.343 + return mLength;
1.344 + }
1.345 +
1.346 + bool empty() const {
1.347 + return mLength == 0;
1.348 + }
1.349 +
1.350 + size_t capacity() const {
1.351 + return mCapacity;
1.352 + }
1.353 +
1.354 + T* begin() {
1.355 + MOZ_ASSERT(!entered);
1.356 + return mBegin;
1.357 + }
1.358 +
1.359 + const T* begin() const {
1.360 + MOZ_ASSERT(!entered);
1.361 + return mBegin;
1.362 + }
1.363 +
1.364 + T* end() {
1.365 + MOZ_ASSERT(!entered);
1.366 + return mBegin + mLength;
1.367 + }
1.368 +
1.369 + const T* end() const {
1.370 + MOZ_ASSERT(!entered);
1.371 + return mBegin + mLength;
1.372 + }
1.373 +
1.374 + T& operator[](size_t i) {
1.375 + MOZ_ASSERT(!entered);
1.376 + MOZ_ASSERT(i < mLength);
1.377 + return begin()[i];
1.378 + }
1.379 +
1.380 + const T& operator[](size_t i) const {
1.381 + MOZ_ASSERT(!entered);
1.382 + MOZ_ASSERT(i < mLength);
1.383 + return begin()[i];
1.384 + }
1.385 +
1.386 + T& back() {
1.387 + MOZ_ASSERT(!entered);
1.388 + MOZ_ASSERT(!empty());
1.389 + return *(end() - 1);
1.390 + }
1.391 +
1.392 + const T& back() const {
1.393 + MOZ_ASSERT(!entered);
1.394 + MOZ_ASSERT(!empty());
1.395 + return *(end() - 1);
1.396 + }
1.397 +
1.398 + class Range
1.399 + {
1.400 + friend class VectorBase;
1.401 + T* cur_;
1.402 + T* end_;
1.403 + Range(T* cur, T* end) : cur_(cur), end_(end) {
1.404 + MOZ_ASSERT(cur <= end);
1.405 + }
1.406 +
1.407 + public:
1.408 + Range() {}
1.409 + bool empty() const { return cur_ == end_; }
1.410 + size_t remain() const { return PointerRangeSize(cur_, end_); }
1.411 + T& front() const { MOZ_ASSERT(!empty()); return *cur_; }
1.412 + void popFront() { MOZ_ASSERT(!empty()); ++cur_; }
1.413 + T popCopyFront() { MOZ_ASSERT(!empty()); return *cur_++; }
1.414 + };
1.415 +
1.416 + Range all() {
1.417 + return Range(begin(), end());
1.418 + }
1.419 +
1.420 + /* mutators */
1.421 +
1.422 + /**
1.423 + * Given that the vector is empty and has no inline storage, grow to
1.424 + * |capacity|.
1.425 + */
1.426 + bool initCapacity(size_t request);
1.427 +
1.428 + /**
1.429 + * If reserve(length() + N) succeeds, the N next appends are guaranteed to
1.430 + * succeed.
1.431 + */
1.432 + bool reserve(size_t request);
1.433 +
1.434 + /**
1.435 + * Destroy elements in the range [end() - incr, end()). Does not deallocate
1.436 + * or unreserve storage for those elements.
1.437 + */
1.438 + void shrinkBy(size_t incr);
1.439 +
1.440 + /** Grow the vector by incr elements. */
1.441 + bool growBy(size_t incr);
1.442 +
1.443 + /** Call shrinkBy or growBy based on whether newSize > length(). */
1.444 + bool resize(size_t newLength);
1.445 +
1.446 + /**
1.447 + * Increase the length of the vector, but don't initialize the new elements
1.448 + * -- leave them as uninitialized memory.
1.449 + */
1.450 + bool growByUninitialized(size_t incr);
1.451 + bool resizeUninitialized(size_t newLength);
1.452 +
1.453 + /** Shorthand for shrinkBy(length()). */
1.454 + void clear();
1.455 +
1.456 + /** Clears and releases any heap-allocated storage. */
1.457 + void clearAndFree();
1.458 +
1.459 + /**
1.460 + * If true, appending |needed| elements won't reallocate elements storage.
1.461 + * This *doesn't* mean that infallibleAppend may be used! You still must
1.462 + * reserve the extra space, even if this method indicates that appends won't
1.463 + * need to reallocate elements storage.
1.464 + */
1.465 + bool canAppendWithoutRealloc(size_t needed) const;
1.466 +
1.467 + /** Potentially fallible append operations. */
1.468 +
1.469 + /**
1.470 + * This can take either a T& or a T&&. Given a T&&, it moves |u| into the
1.471 + * vector, instead of copying it. If it fails, |u| is left unmoved. ("We are
1.472 + * not amused.")
1.473 + */
1.474 + template<typename U> bool append(U&& u);
1.475 +
1.476 + template<typename U, size_t O, class BP, class UV>
1.477 + bool appendAll(const VectorBase<U, O, BP, UV>& u);
1.478 + bool appendN(const T& t, size_t n);
1.479 + template<typename U> bool append(const U* begin, const U* end);
1.480 + template<typename U> bool append(const U* begin, size_t length);
1.481 +
1.482 + /*
1.483 + * Guaranteed-infallible append operations for use upon vectors whose
1.484 + * memory has been pre-reserved. Don't use this if you haven't reserved the
1.485 + * memory!
1.486 + */
1.487 + template<typename U> void infallibleAppend(U&& u) {
1.488 + internalAppend(Forward<U>(u));
1.489 + }
1.490 + void infallibleAppendN(const T& t, size_t n) {
1.491 + internalAppendN(t, n);
1.492 + }
1.493 + template<typename U> void infallibleAppend(const U* aBegin, const U* aEnd) {
1.494 + internalAppend(aBegin, PointerRangeSize(aBegin, aEnd));
1.495 + }
1.496 + template<typename U> void infallibleAppend(const U* aBegin, size_t aLength) {
1.497 + internalAppend(aBegin, aLength);
1.498 + }
1.499 +
1.500 + void popBack();
1.501 +
1.502 + T popCopy();
1.503 +
1.504 + /**
1.505 + * Transfers ownership of the internal buffer used by this vector to the
1.506 + * caller. (It's the caller's responsibility to properly deallocate this
1.507 + * buffer, in accordance with this vector's AllocPolicy.) After this call,
1.508 + * the vector is empty. Since the returned buffer may need to be allocated
1.509 + * (if the elements are currently stored in-place), the call can fail,
1.510 + * returning nullptr.
1.511 + *
1.512 + * N.B. Although a T*, only the range [0, length()) is constructed.
1.513 + */
1.514 + T* extractRawBuffer();
1.515 +
1.516 + /**
1.517 + * Transfer ownership of an array of objects into the vector. The caller
1.518 + * must have allocated the array in accordance with this vector's
1.519 + * AllocPolicy.
1.520 + *
1.521 + * N.B. This call assumes that there are no uninitialized elements in the
1.522 + * passed array.
1.523 + */
1.524 + void replaceRawBuffer(T* p, size_t length);
1.525 +
1.526 + /**
1.527 + * Places |val| at position |p|, shifting existing elements from |p| onward
1.528 + * one position higher. On success, |p| should not be reused because it'll
1.529 + * be a dangling pointer if reallocation of the vector storage occurred; the
1.530 + * return value should be used instead. On failure, nullptr is returned.
1.531 + *
1.532 + * Example usage:
1.533 + *
1.534 + * if (!(p = vec.insert(p, val)))
1.535 + * <handle failure>
1.536 + * <keep working with p>
1.537 + *
1.538 + * This is inherently a linear-time operation. Be careful!
1.539 + */
1.540 + template<typename U>
1.541 + T* insert(T* p, U&& val);
1.542 +
1.543 + /**
1.544 + * Removes the element |t|, which must fall in the bounds [begin, end),
1.545 + * shifting existing elements from |t + 1| onward one position lower.
1.546 + */
1.547 + void erase(T* t);
1.548 +
1.549 + /**
1.550 + * Measure the size of the vector's heap-allocated storage.
1.551 + */
1.552 + size_t sizeOfExcludingThis(MallocSizeOf mallocSizeOf) const;
1.553 +
1.554 + /**
1.555 + * Like sizeOfExcludingThis, but also measures the size of the vector
1.556 + * object (which must be heap-allocated) itself.
1.557 + */
1.558 + size_t sizeOfIncludingThis(MallocSizeOf mallocSizeOf) const;
1.559 +
1.560 + void swap(ThisVector& other);
1.561 +
1.562 + private:
1.563 + VectorBase(const VectorBase&) MOZ_DELETE;
1.564 + void operator=(const VectorBase&) MOZ_DELETE;
1.565 +
1.566 + /* Move-construct/assign only from our derived class, ThisVector. */
1.567 + VectorBase(VectorBase&&) MOZ_DELETE;
1.568 + void operator=(VectorBase&&) MOZ_DELETE;
1.569 +};
1.570 +
1.571 +/* This does the re-entrancy check plus several other sanity checks. */
1.572 +#define MOZ_REENTRANCY_GUARD_ET_AL \
1.573 + ReentrancyGuard g(*this); \
1.574 + MOZ_ASSERT_IF(usingInlineStorage(), mCapacity == sInlineCapacity); \
1.575 + MOZ_ASSERT(reserved() <= mCapacity); \
1.576 + MOZ_ASSERT(mLength <= reserved()); \
1.577 + MOZ_ASSERT(mLength <= mCapacity)
1.578 +
1.579 +/* Vector Implementation */
1.580 +
1.581 +template<typename T, size_t N, class AP, class TV>
1.582 +MOZ_ALWAYS_INLINE
1.583 +VectorBase<T, N, AP, TV>::VectorBase(AP ap)
1.584 + : AP(ap),
1.585 + mLength(0),
1.586 + mCapacity(sInlineCapacity)
1.587 +#ifdef DEBUG
1.588 + , mReserved(sInlineCapacity),
1.589 + entered(false)
1.590 +#endif
1.591 +{
1.592 + mBegin = static_cast<T*>(storage.addr());
1.593 +}
1.594 +
1.595 +/* Move constructor. */
1.596 +template<typename T, size_t N, class AllocPolicy, class TV>
1.597 +MOZ_ALWAYS_INLINE
1.598 +VectorBase<T, N, AllocPolicy, TV>::VectorBase(TV&& rhs)
1.599 + : AllocPolicy(Move(rhs))
1.600 +#ifdef DEBUG
1.601 + , entered(false)
1.602 +#endif
1.603 +{
1.604 + mLength = rhs.mLength;
1.605 + mCapacity = rhs.mCapacity;
1.606 +#ifdef DEBUG
1.607 + mReserved = rhs.mReserved;
1.608 +#endif
1.609 +
1.610 + if (rhs.usingInlineStorage()) {
1.611 + /* We can't move the buffer over in this case, so copy elements. */
1.612 + mBegin = static_cast<T*>(storage.addr());
1.613 + Impl::moveConstruct(mBegin, rhs.beginNoCheck(), rhs.endNoCheck());
1.614 + /*
1.615 + * Leave rhs's mLength, mBegin, mCapacity, and mReserved as they are.
1.616 + * The elements in its in-line storage still need to be destroyed.
1.617 + */
1.618 + } else {
1.619 + /*
1.620 + * Take src's buffer, and turn src into an empty vector using
1.621 + * in-line storage.
1.622 + */
1.623 + mBegin = rhs.mBegin;
1.624 + rhs.mBegin = static_cast<T*>(rhs.storage.addr());
1.625 + rhs.mCapacity = sInlineCapacity;
1.626 + rhs.mLength = 0;
1.627 +#ifdef DEBUG
1.628 + rhs.mReserved = sInlineCapacity;
1.629 +#endif
1.630 + }
1.631 +}
1.632 +
1.633 +/* Move assignment. */
1.634 +template<typename T, size_t N, class AP, class TV>
1.635 +MOZ_ALWAYS_INLINE
1.636 +TV&
1.637 +VectorBase<T, N, AP, TV>::operator=(TV&& rhs)
1.638 +{
1.639 + MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
1.640 + TV* tv = static_cast<TV*>(this);
1.641 + tv->~TV();
1.642 + new(tv) TV(Move(rhs));
1.643 + return *tv;
1.644 +}
1.645 +
1.646 +template<typename T, size_t N, class AP, class TV>
1.647 +MOZ_ALWAYS_INLINE
1.648 +VectorBase<T, N, AP, TV>::~VectorBase()
1.649 +{
1.650 + MOZ_REENTRANCY_GUARD_ET_AL;
1.651 + Impl::destroy(beginNoCheck(), endNoCheck());
1.652 + if (!usingInlineStorage())
1.653 + this->free_(beginNoCheck());
1.654 +}
1.655 +
1.656 +/*
1.657 + * This function will create a new heap buffer with capacity newCap,
1.658 + * move all elements in the inline buffer to this new buffer,
1.659 + * and fail on OOM.
1.660 + */
1.661 +template<typename T, size_t N, class AP, class TV>
1.662 +inline bool
1.663 +VectorBase<T, N, AP, TV>::convertToHeapStorage(size_t newCap)
1.664 +{
1.665 + MOZ_ASSERT(usingInlineStorage());
1.666 +
1.667 + /* Allocate buffer. */
1.668 + MOZ_ASSERT(!detail::CapacityHasExcessSpace<T>(newCap));
1.669 + T* newBuf = reinterpret_cast<T*>(this->malloc_(newCap * sizeof(T)));
1.670 + if (!newBuf)
1.671 + return false;
1.672 +
1.673 + /* Copy inline elements into heap buffer. */
1.674 + Impl::moveConstruct(newBuf, beginNoCheck(), endNoCheck());
1.675 + Impl::destroy(beginNoCheck(), endNoCheck());
1.676 +
1.677 + /* Switch in heap buffer. */
1.678 + mBegin = newBuf;
1.679 + /* mLength is unchanged. */
1.680 + mCapacity = newCap;
1.681 + return true;
1.682 +}
1.683 +
1.684 +template<typename T, size_t N, class AP, class TV>
1.685 +MOZ_NEVER_INLINE bool
1.686 +VectorBase<T, N, AP, TV>::growStorageBy(size_t incr)
1.687 +{
1.688 + MOZ_ASSERT(mLength + incr > mCapacity);
1.689 + MOZ_ASSERT_IF(!usingInlineStorage(),
1.690 + !detail::CapacityHasExcessSpace<T>(mCapacity));
1.691 +
1.692 + /*
1.693 + * When choosing a new capacity, its size should is as close to 2**N bytes
1.694 + * as possible. 2**N-sized requests are best because they are unlikely to
1.695 + * be rounded up by the allocator. Asking for a 2**N number of elements
1.696 + * isn't as good, because if sizeof(T) is not a power-of-two that would
1.697 + * result in a non-2**N request size.
1.698 + */
1.699 +
1.700 + size_t newCap;
1.701 +
1.702 + if (incr == 1) {
1.703 + if (usingInlineStorage()) {
1.704 + /* This case occurs in ~70--80% of the calls to this function. */
1.705 + size_t newSize =
1.706 + tl::RoundUpPow2<(sInlineCapacity + 1) * sizeof(T)>::value;
1.707 + newCap = newSize / sizeof(T);
1.708 + goto convert;
1.709 + }
1.710 +
1.711 + if (mLength == 0) {
1.712 + /* This case occurs in ~0--10% of the calls to this function. */
1.713 + newCap = 1;
1.714 + goto grow;
1.715 + }
1.716 +
1.717 + /* This case occurs in ~15--20% of the calls to this function. */
1.718 +
1.719 + /*
1.720 + * Will mLength * 4 *sizeof(T) overflow? This condition limits a vector
1.721 + * to 1GB of memory on a 32-bit system, which is a reasonable limit. It
1.722 + * also ensures that
1.723 + *
1.724 + * static_cast<char*>(end()) - static_cast<char*>(begin())
1.725 + *
1.726 + * doesn't overflow ptrdiff_t (see bug 510319).
1.727 + */
1.728 + if (mLength & tl::MulOverflowMask<4 * sizeof(T)>::value) {
1.729 + this->reportAllocOverflow();
1.730 + return false;
1.731 + }
1.732 +
1.733 + /*
1.734 + * If we reach here, the existing capacity will have a size that is already
1.735 + * as close to 2^N as sizeof(T) will allow. Just double the capacity, and
1.736 + * then there might be space for one more element.
1.737 + */
1.738 + newCap = mLength * 2;
1.739 + if (detail::CapacityHasExcessSpace<T>(newCap))
1.740 + newCap += 1;
1.741 + } else {
1.742 + /* This case occurs in ~2% of the calls to this function. */
1.743 + size_t newMinCap = mLength + incr;
1.744 +
1.745 + /* Did mLength + incr overflow? Will newCap * sizeof(T) overflow? */
1.746 + if (newMinCap < mLength ||
1.747 + newMinCap & tl::MulOverflowMask<2 * sizeof(T)>::value)
1.748 + {
1.749 + this->reportAllocOverflow();
1.750 + return false;
1.751 + }
1.752 +
1.753 + size_t newMinSize = newMinCap * sizeof(T);
1.754 + size_t newSize = RoundUpPow2(newMinSize);
1.755 + newCap = newSize / sizeof(T);
1.756 + }
1.757 +
1.758 + if (usingInlineStorage()) {
1.759 + convert:
1.760 + return convertToHeapStorage(newCap);
1.761 + }
1.762 +
1.763 +grow:
1.764 + return Impl::growTo(*this, newCap);
1.765 +}
1.766 +
1.767 +template<typename T, size_t N, class AP, class TV>
1.768 +inline bool
1.769 +VectorBase<T, N, AP, TV>::initCapacity(size_t request)
1.770 +{
1.771 + MOZ_ASSERT(empty());
1.772 + MOZ_ASSERT(usingInlineStorage());
1.773 + if (request == 0)
1.774 + return true;
1.775 + T* newbuf = reinterpret_cast<T*>(this->malloc_(request * sizeof(T)));
1.776 + if (!newbuf)
1.777 + return false;
1.778 + mBegin = newbuf;
1.779 + mCapacity = request;
1.780 +#ifdef DEBUG
1.781 + mReserved = request;
1.782 +#endif
1.783 + return true;
1.784 +}
1.785 +
1.786 +template<typename T, size_t N, class AP, class TV>
1.787 +inline bool
1.788 +VectorBase<T, N, AP, TV>::reserve(size_t request)
1.789 +{
1.790 + MOZ_REENTRANCY_GUARD_ET_AL;
1.791 + if (request > mCapacity && !growStorageBy(request - mLength))
1.792 + return false;
1.793 +
1.794 +#ifdef DEBUG
1.795 + if (request > mReserved)
1.796 + mReserved = request;
1.797 + MOZ_ASSERT(mLength <= mReserved);
1.798 + MOZ_ASSERT(mReserved <= mCapacity);
1.799 +#endif
1.800 + return true;
1.801 +}
1.802 +
1.803 +template<typename T, size_t N, class AP, class TV>
1.804 +inline void
1.805 +VectorBase<T, N, AP, TV>::shrinkBy(size_t incr)
1.806 +{
1.807 + MOZ_REENTRANCY_GUARD_ET_AL;
1.808 + MOZ_ASSERT(incr <= mLength);
1.809 + Impl::destroy(endNoCheck() - incr, endNoCheck());
1.810 + mLength -= incr;
1.811 +}
1.812 +
1.813 +template<typename T, size_t N, class AP, class TV>
1.814 +MOZ_ALWAYS_INLINE bool
1.815 +VectorBase<T, N, AP, TV>::growBy(size_t incr)
1.816 +{
1.817 + MOZ_REENTRANCY_GUARD_ET_AL;
1.818 + if (incr > mCapacity - mLength && !growStorageBy(incr))
1.819 + return false;
1.820 +
1.821 + MOZ_ASSERT(mLength + incr <= mCapacity);
1.822 + T* newend = endNoCheck() + incr;
1.823 + Impl::initialize(endNoCheck(), newend);
1.824 + mLength += incr;
1.825 +#ifdef DEBUG
1.826 + if (mLength > mReserved)
1.827 + mReserved = mLength;
1.828 +#endif
1.829 + return true;
1.830 +}
1.831 +
1.832 +template<typename T, size_t N, class AP, class TV>
1.833 +MOZ_ALWAYS_INLINE bool
1.834 +VectorBase<T, N, AP, TV>::growByUninitialized(size_t incr)
1.835 +{
1.836 + MOZ_REENTRANCY_GUARD_ET_AL;
1.837 + if (incr > mCapacity - mLength && !growStorageBy(incr))
1.838 + return false;
1.839 +
1.840 + MOZ_ASSERT(mLength + incr <= mCapacity);
1.841 + mLength += incr;
1.842 +#ifdef DEBUG
1.843 + if (mLength > mReserved)
1.844 + mReserved = mLength;
1.845 +#endif
1.846 + return true;
1.847 +}
1.848 +
1.849 +template<typename T, size_t N, class AP, class TV>
1.850 +inline bool
1.851 +VectorBase<T, N, AP, TV>::resize(size_t newLength)
1.852 +{
1.853 + size_t curLength = mLength;
1.854 + if (newLength > curLength)
1.855 + return growBy(newLength - curLength);
1.856 + shrinkBy(curLength - newLength);
1.857 + return true;
1.858 +}
1.859 +
1.860 +template<typename T, size_t N, class AP, class TV>
1.861 +MOZ_ALWAYS_INLINE bool
1.862 +VectorBase<T, N, AP, TV>::resizeUninitialized(size_t newLength)
1.863 +{
1.864 + size_t curLength = mLength;
1.865 + if (newLength > curLength)
1.866 + return growByUninitialized(newLength - curLength);
1.867 + shrinkBy(curLength - newLength);
1.868 + return true;
1.869 +}
1.870 +
1.871 +template<typename T, size_t N, class AP, class TV>
1.872 +inline void
1.873 +VectorBase<T, N, AP, TV>::clear()
1.874 +{
1.875 + MOZ_REENTRANCY_GUARD_ET_AL;
1.876 + Impl::destroy(beginNoCheck(), endNoCheck());
1.877 + mLength = 0;
1.878 +}
1.879 +
1.880 +template<typename T, size_t N, class AP, class TV>
1.881 +inline void
1.882 +VectorBase<T, N, AP, TV>::clearAndFree()
1.883 +{
1.884 + clear();
1.885 +
1.886 + if (usingInlineStorage())
1.887 + return;
1.888 +
1.889 + this->free_(beginNoCheck());
1.890 + mBegin = static_cast<T*>(storage.addr());
1.891 + mCapacity = sInlineCapacity;
1.892 +#ifdef DEBUG
1.893 + mReserved = sInlineCapacity;
1.894 +#endif
1.895 +}
1.896 +
1.897 +template<typename T, size_t N, class AP, class TV>
1.898 +inline bool
1.899 +VectorBase<T, N, AP, TV>::canAppendWithoutRealloc(size_t needed) const
1.900 +{
1.901 + return mLength + needed <= mCapacity;
1.902 +}
1.903 +
1.904 +template<typename T, size_t N, class AP, class TV>
1.905 +template<typename U, size_t O, class BP, class UV>
1.906 +MOZ_ALWAYS_INLINE void
1.907 +VectorBase<T, N, AP, TV>::internalAppendAll(const VectorBase<U, O, BP, UV>& other)
1.908 +{
1.909 + internalAppend(other.begin(), other.length());
1.910 +}
1.911 +
1.912 +template<typename T, size_t N, class AP, class TV>
1.913 +template<typename U>
1.914 +MOZ_ALWAYS_INLINE void
1.915 +VectorBase<T, N, AP, TV>::internalAppend(U&& u)
1.916 +{
1.917 + MOZ_ASSERT(mLength + 1 <= mReserved);
1.918 + MOZ_ASSERT(mReserved <= mCapacity);
1.919 + new(endNoCheck()) T(Forward<U>(u));
1.920 + ++mLength;
1.921 +}
1.922 +
1.923 +template<typename T, size_t N, class AP, class TV>
1.924 +MOZ_ALWAYS_INLINE bool
1.925 +VectorBase<T, N, AP, TV>::appendN(const T& t, size_t needed)
1.926 +{
1.927 + MOZ_REENTRANCY_GUARD_ET_AL;
1.928 + if (mLength + needed > mCapacity && !growStorageBy(needed))
1.929 + return false;
1.930 +
1.931 +#ifdef DEBUG
1.932 + if (mLength + needed > mReserved)
1.933 + mReserved = mLength + needed;
1.934 +#endif
1.935 + internalAppendN(t, needed);
1.936 + return true;
1.937 +}
1.938 +
1.939 +template<typename T, size_t N, class AP, class TV>
1.940 +MOZ_ALWAYS_INLINE void
1.941 +VectorBase<T, N, AP, TV>::internalAppendN(const T& t, size_t needed)
1.942 +{
1.943 + MOZ_ASSERT(mLength + needed <= mReserved);
1.944 + MOZ_ASSERT(mReserved <= mCapacity);
1.945 + Impl::copyConstructN(endNoCheck(), needed, t);
1.946 + mLength += needed;
1.947 +}
1.948 +
1.949 +template<typename T, size_t N, class AP, class TV>
1.950 +template<typename U>
1.951 +inline T*
1.952 +VectorBase<T, N, AP, TV>::insert(T* p, U&& val)
1.953 +{
1.954 + MOZ_ASSERT(begin() <= p);
1.955 + MOZ_ASSERT(p <= end());
1.956 + size_t pos = p - begin();
1.957 + MOZ_ASSERT(pos <= mLength);
1.958 + size_t oldLength = mLength;
1.959 + if (pos == oldLength) {
1.960 + if (!append(Forward<U>(val)))
1.961 + return nullptr;
1.962 + } else {
1.963 + T oldBack = Move(back());
1.964 + if (!append(Move(oldBack))) /* Dup the last element. */
1.965 + return nullptr;
1.966 + for (size_t i = oldLength; i > pos; --i)
1.967 + (*this)[i] = Move((*this)[i - 1]);
1.968 + (*this)[pos] = Forward<U>(val);
1.969 + }
1.970 + return begin() + pos;
1.971 +}
1.972 +
1.973 +template<typename T, size_t N, class AP, class TV>
1.974 +inline void
1.975 +VectorBase<T, N, AP, TV>::erase(T* it)
1.976 +{
1.977 + MOZ_ASSERT(begin() <= it);
1.978 + MOZ_ASSERT(it < end());
1.979 + while (it + 1 < end()) {
1.980 + *it = *(it + 1);
1.981 + ++it;
1.982 + }
1.983 + popBack();
1.984 +}
1.985 +
1.986 +template<typename T, size_t N, class AP, class TV>
1.987 +template<typename U>
1.988 +MOZ_ALWAYS_INLINE bool
1.989 +VectorBase<T, N, AP, TV>::append(const U* insBegin, const U* insEnd)
1.990 +{
1.991 + MOZ_REENTRANCY_GUARD_ET_AL;
1.992 + size_t needed = PointerRangeSize(insBegin, insEnd);
1.993 + if (mLength + needed > mCapacity && !growStorageBy(needed))
1.994 + return false;
1.995 +
1.996 +#ifdef DEBUG
1.997 + if (mLength + needed > mReserved)
1.998 + mReserved = mLength + needed;
1.999 +#endif
1.1000 + internalAppend(insBegin, needed);
1.1001 + return true;
1.1002 +}
1.1003 +
1.1004 +template<typename T, size_t N, class AP, class TV>
1.1005 +template<typename U>
1.1006 +MOZ_ALWAYS_INLINE void
1.1007 +VectorBase<T, N, AP, TV>::internalAppend(const U* insBegin, size_t insLength)
1.1008 +{
1.1009 + MOZ_ASSERT(mLength + insLength <= mReserved);
1.1010 + MOZ_ASSERT(mReserved <= mCapacity);
1.1011 + Impl::copyConstruct(endNoCheck(), insBegin, insBegin + insLength);
1.1012 + mLength += insLength;
1.1013 +}
1.1014 +
1.1015 +template<typename T, size_t N, class AP, class TV>
1.1016 +template<typename U>
1.1017 +MOZ_ALWAYS_INLINE bool
1.1018 +VectorBase<T, N, AP, TV>::append(U&& u)
1.1019 +{
1.1020 + MOZ_REENTRANCY_GUARD_ET_AL;
1.1021 + if (mLength == mCapacity && !growStorageBy(1))
1.1022 + return false;
1.1023 +
1.1024 +#ifdef DEBUG
1.1025 + if (mLength + 1 > mReserved)
1.1026 + mReserved = mLength + 1;
1.1027 +#endif
1.1028 + internalAppend(Forward<U>(u));
1.1029 + return true;
1.1030 +}
1.1031 +
1.1032 +template<typename T, size_t N, class AP, class TV>
1.1033 +template<typename U, size_t O, class BP, class UV>
1.1034 +MOZ_ALWAYS_INLINE bool
1.1035 +VectorBase<T, N, AP, TV>::appendAll(const VectorBase<U, O, BP, UV>& other)
1.1036 +{
1.1037 + return append(other.begin(), other.length());
1.1038 +}
1.1039 +
1.1040 +template<typename T, size_t N, class AP, class TV>
1.1041 +template<class U>
1.1042 +MOZ_ALWAYS_INLINE bool
1.1043 +VectorBase<T, N, AP, TV>::append(const U *insBegin, size_t insLength)
1.1044 +{
1.1045 + return append(insBegin, insBegin + insLength);
1.1046 +}
1.1047 +
1.1048 +template<typename T, size_t N, class AP, class TV>
1.1049 +MOZ_ALWAYS_INLINE void
1.1050 +VectorBase<T, N, AP, TV>::popBack()
1.1051 +{
1.1052 + MOZ_REENTRANCY_GUARD_ET_AL;
1.1053 + MOZ_ASSERT(!empty());
1.1054 + --mLength;
1.1055 + endNoCheck()->~T();
1.1056 +}
1.1057 +
1.1058 +template<typename T, size_t N, class AP, class TV>
1.1059 +MOZ_ALWAYS_INLINE T
1.1060 +VectorBase<T, N, AP, TV>::popCopy()
1.1061 +{
1.1062 + T ret = back();
1.1063 + popBack();
1.1064 + return ret;
1.1065 +}
1.1066 +
1.1067 +template<typename T, size_t N, class AP, class TV>
1.1068 +inline T*
1.1069 +VectorBase<T, N, AP, TV>::extractRawBuffer()
1.1070 +{
1.1071 + T* ret;
1.1072 + if (usingInlineStorage()) {
1.1073 + ret = reinterpret_cast<T*>(this->malloc_(mLength * sizeof(T)));
1.1074 + if (!ret)
1.1075 + return nullptr;
1.1076 + Impl::copyConstruct(ret, beginNoCheck(), endNoCheck());
1.1077 + Impl::destroy(beginNoCheck(), endNoCheck());
1.1078 + /* mBegin, mCapacity are unchanged. */
1.1079 + mLength = 0;
1.1080 + } else {
1.1081 + ret = mBegin;
1.1082 + mBegin = static_cast<T*>(storage.addr());
1.1083 + mLength = 0;
1.1084 + mCapacity = sInlineCapacity;
1.1085 +#ifdef DEBUG
1.1086 + mReserved = sInlineCapacity;
1.1087 +#endif
1.1088 + }
1.1089 + return ret;
1.1090 +}
1.1091 +
1.1092 +template<typename T, size_t N, class AP, class TV>
1.1093 +inline void
1.1094 +VectorBase<T, N, AP, TV>::replaceRawBuffer(T* p, size_t aLength)
1.1095 +{
1.1096 + MOZ_REENTRANCY_GUARD_ET_AL;
1.1097 +
1.1098 + /* Destroy what we have. */
1.1099 + Impl::destroy(beginNoCheck(), endNoCheck());
1.1100 + if (!usingInlineStorage())
1.1101 + this->free_(beginNoCheck());
1.1102 +
1.1103 + /* Take in the new buffer. */
1.1104 + if (aLength <= sInlineCapacity) {
1.1105 + /*
1.1106 + * We convert to inline storage if possible, even though p might
1.1107 + * otherwise be acceptable. Maybe this behaviour should be
1.1108 + * specifiable with an argument to this function.
1.1109 + */
1.1110 + mBegin = static_cast<T*>(storage.addr());
1.1111 + mLength = aLength;
1.1112 + mCapacity = sInlineCapacity;
1.1113 + Impl::moveConstruct(mBegin, p, p + aLength);
1.1114 + Impl::destroy(p, p + aLength);
1.1115 + this->free_(p);
1.1116 + } else {
1.1117 + mBegin = p;
1.1118 + mLength = aLength;
1.1119 + mCapacity = aLength;
1.1120 + }
1.1121 +#ifdef DEBUG
1.1122 + mReserved = aLength;
1.1123 +#endif
1.1124 +}
1.1125 +
1.1126 +template<typename T, size_t N, class AP, class TV>
1.1127 +inline size_t
1.1128 +VectorBase<T, N, AP, TV>::sizeOfExcludingThis(MallocSizeOf mallocSizeOf) const
1.1129 +{
1.1130 + return usingInlineStorage() ? 0 : mallocSizeOf(beginNoCheck());
1.1131 +}
1.1132 +
1.1133 +template<typename T, size_t N, class AP, class TV>
1.1134 +inline size_t
1.1135 +VectorBase<T, N, AP, TV>::sizeOfIncludingThis(MallocSizeOf mallocSizeOf) const
1.1136 +{
1.1137 + return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
1.1138 +}
1.1139 +
1.1140 +template<typename T, size_t N, class AP, class TV>
1.1141 +inline void
1.1142 +VectorBase<T, N, AP, TV>::swap(TV& other)
1.1143 +{
1.1144 + static_assert(N == 0,
1.1145 + "still need to implement this for N != 0");
1.1146 +
1.1147 + // This only works when inline storage is always empty.
1.1148 + if (!usingInlineStorage() && other.usingInlineStorage()) {
1.1149 + other.mBegin = mBegin;
1.1150 + mBegin = inlineStorage();
1.1151 + } else if (usingInlineStorage() && !other.usingInlineStorage()) {
1.1152 + mBegin = other.mBegin;
1.1153 + other.mBegin = other.inlineStorage();
1.1154 + } else if (!usingInlineStorage() && !other.usingInlineStorage()) {
1.1155 + Swap(mBegin, other.mBegin);
1.1156 + } else {
1.1157 + // This case is a no-op, since we'd set both to use their inline storage.
1.1158 + }
1.1159 +
1.1160 + Swap(mLength, other.mLength);
1.1161 + Swap(mCapacity, other.mCapacity);
1.1162 +#ifdef DEBUG
1.1163 + Swap(mReserved, other.mReserved);
1.1164 +#endif
1.1165 +}
1.1166 +
1.1167 +/*
1.1168 + * STL-like container providing a short-lived, dynamic buffer. Vector calls the
1.1169 + * constructors/destructors of all elements stored in its internal buffer, so
1.1170 + * non-PODs may be safely used. Additionally, Vector will store the first N
1.1171 + * elements in-place before resorting to dynamic allocation.
1.1172 + *
1.1173 + * T requirements:
1.1174 + * - default and copy constructible, assignable, destructible
1.1175 + * - operations do not throw
1.1176 + * N requirements:
1.1177 + * - any value, however, N is clamped to min/max values
1.1178 + * AllocPolicy:
1.1179 + * - see "Allocation policies" in AllocPolicy.h (defaults to
1.1180 + * mozilla::MallocAllocPolicy)
1.1181 + *
1.1182 + * Vector is not reentrant: T member functions called during Vector member
1.1183 + * functions must not call back into the same object!
1.1184 + */
1.1185 +template<typename T,
1.1186 + size_t MinInlineCapacity = 0,
1.1187 + class AllocPolicy = MallocAllocPolicy>
1.1188 +class Vector
1.1189 + : public VectorBase<T,
1.1190 + MinInlineCapacity,
1.1191 + AllocPolicy,
1.1192 + Vector<T, MinInlineCapacity, AllocPolicy> >
1.1193 +{
1.1194 + typedef VectorBase<T, MinInlineCapacity, AllocPolicy, Vector> Base;
1.1195 +
1.1196 + public:
1.1197 + Vector(AllocPolicy alloc = AllocPolicy()) : Base(alloc) {}
1.1198 + Vector(Vector&& vec) : Base(Move(vec)) {}
1.1199 + Vector& operator=(Vector&& vec) {
1.1200 + return Base::operator=(Move(vec));
1.1201 + }
1.1202 +};
1.1203 +
1.1204 +} // namespace mozilla
1.1205 +
1.1206 +#ifdef _MSC_VER
1.1207 +#pragma warning(pop)
1.1208 +#endif
1.1209 +
1.1210 +#endif /* mozilla_Vector_h */
