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