js/public/Vector.h

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