code.vuplus.com Git - vuplus_webkit/blob - Source/JavaScriptCore/wtf/Vector.h

   1 /*
   2  *  Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
   3  *
   4  *  This library is free software; you can redistribute it and/or
   5  *  modify it under the terms of the GNU Library General Public
   6  *  License as published by the Free Software Foundation; either
   7  *  version 2 of the License, or (at your option) any later version.
   8  *
   9  *  This library is distributed in the hope that it will be useful,
  10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  *  Library General Public License for more details.
  13  *
  14  *  You should have received a copy of the GNU Library General Public License
  15  *  along with this library; see the file COPYING.LIB.  If not, write to
  16  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  *  Boston, MA 02110-1301, USA.
  18  *
  19  */
  20
  21 #ifndef WTF_Vector_h
  22 #define WTF_Vector_h
  23
  24 #include "FastAllocBase.h"
  25 #include "Noncopyable.h"
  26 #include "NotFound.h"
  27 #include "StdLibExtras.h"
  28 #include "ValueCheck.h"
  29 #include "VectorTraits.h"
  30 #include <limits>
  31 #include <utility>
  32 #include <wtf/Alignment.h>
  33
  34 #if PLATFORM(QT)
  35 #include <QDataStream>
  36 #endif
  37
  38 namespace WTF {
  39
  40     using std::min;
  41     using std::max;
  42
  43     #if COMPILER(GCC) && !COMPILER(INTEL) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 303)
  44         typedef char __attribute__((__may_alias__)) AlignedBufferChar;
  45     #else
  46         typedef char AlignedBufferChar;
  47     #endif
  48
  49     template <size_t size, size_t alignment> struct AlignedBuffer;
  50     template <size_t size> struct AlignedBuffer<size, 1> { AlignedBufferChar buffer[size]; };
  51     template <size_t size> struct AlignedBuffer<size, 2> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 2);  };
  52     template <size_t size> struct AlignedBuffer<size, 4> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 4);  };
  53     template <size_t size> struct AlignedBuffer<size, 8> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 8);  };
  54     template <size_t size> struct AlignedBuffer<size, 16> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 16); };
  55     template <size_t size> struct AlignedBuffer<size, 32> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 32); };
  56     template <size_t size> struct AlignedBuffer<size, 64> { WTF_ALIGNED(AlignedBufferChar, buffer[size], 64); };
  57
  58     template <size_t size, size_t alignment>
  59     void swap(AlignedBuffer<size, alignment>& a, AlignedBuffer<size, alignment>& b)
  60     {
  61         for (size_t i = 0; i < size; ++i)
  62             std::swap(a.buffer[i], b.buffer[i]);
  63     }
  64
  65     template <bool needsDestruction, typename T>
  66     struct VectorDestructor;
  67
  68     template<typename T>
  69     struct VectorDestructor<false, T>
  70     {
  71         static void destruct(T*, T*) {}
  72     };
  73
  74     template<typename T>
  75     struct VectorDestructor<true, T>
  76     {
  77         static void destruct(T* begin, T* end)
  78         {
  79             for (T* cur = begin; cur != end; ++cur)
  80                 cur->~T();
  81         }
  82     };
  83
  84     template <bool needsInitialization, bool canInitializeWithMemset, typename T>
  85     struct VectorInitializer;
  86
  87     template<bool ignore, typename T>
  88     struct VectorInitializer<false, ignore, T>
  89     {
  90         static void initialize(T*, T*) {}
  91     };
  92
  93     template<typename T>
  94     struct VectorInitializer<true, false, T>
  95     {
  96         static void initialize(T* begin, T* end)
  97         {
  98             for (T* cur = begin; cur != end; ++cur)
  99                 new (cur) T;
 100         }
 101     };
 102
 103     template<typename T>
 104     struct VectorInitializer<true, true, T>
 105     {
 106         static void initialize(T* begin, T* end)
 107         {
 108             memset(begin, 0, reinterpret_cast<char*>(end) - reinterpret_cast<char*>(begin));
 109         }
 110     };
 111
 112     template <bool canMoveWithMemcpy, typename T>
 113     struct VectorMover;
 114
 115     template<typename T>
 116     struct VectorMover<false, T>
 117     {
 118         static void move(const T* src, const T* srcEnd, T* dst)
 119         {
 120             while (src != srcEnd) {
 121                 new (dst) T(*src);
 122 #if COMPILER(SUNCC) && __SUNPRO_CC <= 0x590
 123                 const_cast<T*>(src)->~T(); // Work around obscure SunCC 12 compiler bug.
 124 #else
 125                 src->~T();
 126 #endif
 127                 ++dst;
 128                 ++src;
 129             }
 130         }
 131         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
 132         {
 133             if (src > dst)
 134                 move(src, srcEnd, dst);
 135             else {
 136                 T* dstEnd = dst + (srcEnd - src);
 137                 while (src != srcEnd) {
 138                     --srcEnd;
 139                     --dstEnd;
 140                     new (dstEnd) T(*srcEnd);
 141                     srcEnd->~T();
 142                 }
 143             }
 144         }
 145     };
 146
 147     template<typename T>
 148     struct VectorMover<true, T>
 149     {
 150         static void move(const T* src, const T* srcEnd, T* dst)
 151         {
 152             memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
 153         }
 154         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
 155         {
 156             memmove(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
 157         }
 158     };
 159
 160     template <bool canCopyWithMemcpy, typename T>
 161     struct VectorCopier;
 162
 163     template<typename T>
 164     struct VectorCopier<false, T>
 165     {
 166         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
 167         {
 168             while (src != srcEnd) {
 169                 new (dst) T(*src);
 170                 ++dst;
 171                 ++src;
 172             }
 173         }
 174     };
 175
 176     template<typename T>
 177     struct VectorCopier<true, T>
 178     {
 179         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
 180         {
 181             memcpy(dst, src, reinterpret_cast<const char*>(srcEnd) - reinterpret_cast<const char*>(src));
 182         }
 183     };
 184
 185     template <bool canFillWithMemset, typename T>
 186     struct VectorFiller;
 187
 188     template<typename T>
 189     struct VectorFiller<false, T>
 190     {
 191         static void uninitializedFill(T* dst, T* dstEnd, const T& val)
 192         {
 193             while (dst != dstEnd) {
 194                 new (dst) T(val);
 195                 ++dst;
 196             }
 197         }
 198     };
 199
 200     template<typename T>
 201     struct VectorFiller<true, T>
 202     {
 203         static void uninitializedFill(T* dst, T* dstEnd, const T& val)
 204         {
 205             ASSERT(sizeof(T) == sizeof(char));
 206             memset(dst, val, dstEnd - dst);
 207         }
 208     };
 209
 210     template<bool canCompareWithMemcmp, typename T>
 211     struct VectorComparer;
 212
 213     template<typename T>
 214     struct VectorComparer<false, T>
 215     {
 216         static bool compare(const T* a, const T* b, size_t size)
 217         {
 218             for (size_t i = 0; i < size; ++i)
 219                 if (a[i] != b[i])
 220                     return false;
 221             return true;
 222         }
 223     };
 224
 225     template<typename T>
 226     struct VectorComparer<true, T>
 227     {
 228         static bool compare(const T* a, const T* b, size_t size)
 229         {
 230             return memcmp(a, b, sizeof(T) * size) == 0;
 231         }
 232     };
 233
 234     template<typename T>
 235     struct VectorTypeOperations
 236     {
 237         static void destruct(T* begin, T* end)
 238         {
 239             VectorDestructor<VectorTraits<T>::needsDestruction, T>::destruct(begin, end);
 240         }
 241
 242         static void initialize(T* begin, T* end)
 243         {
 244             VectorInitializer<VectorTraits<T>::needsInitialization, VectorTraits<T>::canInitializeWithMemset, T>::initialize(begin, end);
 245         }
 246
 247         static void move(const T* src, const T* srcEnd, T* dst)
 248         {
 249             VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::move(src, srcEnd, dst);
 250         }
 251
 252         static void moveOverlapping(const T* src, const T* srcEnd, T* dst)
 253         {
 254             VectorMover<VectorTraits<T>::canMoveWithMemcpy, T>::moveOverlapping(src, srcEnd, dst);
 255         }
 256
 257         static void uninitializedCopy(const T* src, const T* srcEnd, T* dst)
 258         {
 259             VectorCopier<VectorTraits<T>::canCopyWithMemcpy, T>::uninitializedCopy(src, srcEnd, dst);
 260         }
 261
 262         static void uninitializedFill(T* dst, T* dstEnd, const T& val)
 263         {
 264             VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
 265         }
 266
 267         static bool compare(const T* a, const T* b, size_t size)
 268         {
 269             return VectorComparer<VectorTraits<T>::canCompareWithMemcmp, T>::compare(a, b, size);
 270         }
 271     };
 272
 273     template<typename T>
 274     class VectorBufferBase {
 275         WTF_MAKE_NONCOPYABLE(VectorBufferBase);
 276     public:
 277         void allocateBuffer(size_t newCapacity)
 278         {
 279             ASSERT(newCapacity);
 280             m_capacity = newCapacity;
 281             if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
 282                 CRASH();
 283             m_buffer = static_cast<T*>(fastMalloc(newCapacity * sizeof(T)));
 284         }
 285
 286         bool tryAllocateBuffer(size_t newCapacity)
 287         {
 288             ASSERT(newCapacity);
 289             if (newCapacity > std::numeric_limits<size_t>::max() / sizeof(T))
 290                 return false;
 291
 292             T* newBuffer;
 293             if (tryFastMalloc(newCapacity * sizeof(T)).getValue(newBuffer)) {
 294                 m_capacity = newCapacity;
 295                 m_buffer = newBuffer;
 296                 return true;
 297             }
 298             return false;
 299         }
 300
 301         void deallocateBuffer(T* bufferToDeallocate)
 302         {
 303             if (m_buffer == bufferToDeallocate) {
 304                 m_buffer = 0;
 305                 m_capacity = 0;
 306             }
 307             fastFree(bufferToDeallocate);
 308         }
 309
 310         T* buffer() { return m_buffer; }
 311         const T* buffer() const { return m_buffer; }
 312         T** bufferSlot() { return &m_buffer; }
 313         size_t capacity() const { return m_capacity; }
 314
 315         T* releaseBuffer()
 316         {
 317             T* buffer = m_buffer;
 318             m_buffer = 0;
 319             m_capacity = 0;
 320             return buffer;
 321         }
 322
 323     protected:
 324         VectorBufferBase()
 325             : m_buffer(0)
 326             , m_capacity(0)
 327         {
 328         }
 329
 330         VectorBufferBase(T* buffer, size_t capacity)
 331             : m_buffer(buffer)
 332             , m_capacity(capacity)
 333         {
 334         }
 335
 336         ~VectorBufferBase()
 337         {
 338             // FIXME: It would be nice to find a way to ASSERT that m_buffer hasn't leaked here.
 339         }
 340
 341         T* m_buffer;
 342         size_t m_capacity;
 343     };
 344
 345     template<typename T, size_t inlineCapacity>
 346     class VectorBuffer;
 347
 348     template<typename T>
 349     class VectorBuffer<T, 0> : private VectorBufferBase<T> {
 350     private:
 351         typedef VectorBufferBase<T> Base;
 352     public:
 353         VectorBuffer()
 354         {
 355         }
 356
 357         VectorBuffer(size_t capacity)
 358         {
 359             // Calling malloc(0) might take a lock and may actually do an
 360             // allocation on some systems (e.g. Brew).
 361             if (capacity)
 362                 allocateBuffer(capacity);
 363         }
 364
 365         ~VectorBuffer()
 366         {
 367             deallocateBuffer(buffer());
 368         }
 369
 370         void swap(VectorBuffer<T, 0>& other)
 371         {
 372             std::swap(m_buffer, other.m_buffer);
 373             std::swap(m_capacity, other.m_capacity);
 374         }
 375
 376         void restoreInlineBufferIfNeeded() { }
 377
 378         using Base::allocateBuffer;
 379         using Base::tryAllocateBuffer;
 380         using Base::deallocateBuffer;
 381
 382         using Base::buffer;
 383         using Base::bufferSlot;
 384         using Base::capacity;
 385
 386         using Base::releaseBuffer;
 387     private:
 388         using Base::m_buffer;
 389         using Base::m_capacity;
 390     };
 391
 392     template<typename T, size_t inlineCapacity>
 393     class VectorBuffer : private VectorBufferBase<T> {
 394         WTF_MAKE_NONCOPYABLE(VectorBuffer);
 395     private:
 396         typedef VectorBufferBase<T> Base;
 397     public:
 398         VectorBuffer()
 399             : Base(inlineBuffer(), inlineCapacity)
 400         {
 401         }
 402
 403         VectorBuffer(size_t capacity)
 404             : Base(inlineBuffer(), inlineCapacity)
 405         {
 406             if (capacity > inlineCapacity)
 407                 Base::allocateBuffer(capacity);
 408         }
 409
 410         ~VectorBuffer()
 411         {
 412             deallocateBuffer(buffer());
 413         }
 414
 415         void allocateBuffer(size_t newCapacity)
 416         {
 417             // FIXME: This should ASSERT(!m_buffer) to catch misuse/leaks.
 418             if (newCapacity > inlineCapacity)
 419                 Base::allocateBuffer(newCapacity);
 420             else {
 421                 m_buffer = inlineBuffer();
 422                 m_capacity = inlineCapacity;
 423             }
 424         }
 425
 426         bool tryAllocateBuffer(size_t newCapacity)
 427         {
 428             if (newCapacity > inlineCapacity)
 429                 return Base::tryAllocateBuffer(newCapacity);
 430             m_buffer = inlineBuffer();
 431             m_capacity = inlineCapacity;
 432             return true;
 433         }
 434
 435         void deallocateBuffer(T* bufferToDeallocate)
 436         {
 437             if (bufferToDeallocate == inlineBuffer())
 438                 return;
 439             Base::deallocateBuffer(bufferToDeallocate);
 440         }
 441
 442         void swap(VectorBuffer<T, inlineCapacity>& other)
 443         {
 444             if (buffer() == inlineBuffer() && other.buffer() == other.inlineBuffer()) {
 445                 WTF::swap(m_inlineBuffer, other.m_inlineBuffer);
 446                 std::swap(m_capacity, other.m_capacity);
 447             } else if (buffer() == inlineBuffer()) {
 448                 m_buffer = other.m_buffer;
 449                 other.m_buffer = other.inlineBuffer();
 450                 WTF::swap(m_inlineBuffer, other.m_inlineBuffer);
 451                 std::swap(m_capacity, other.m_capacity);
 452             } else if (other.buffer() == other.inlineBuffer()) {
 453                 other.m_buffer = m_buffer;
 454                 m_buffer = inlineBuffer();
 455                 WTF::swap(m_inlineBuffer, other.m_inlineBuffer);
 456                 std::swap(m_capacity, other.m_capacity);
 457             } else {
 458                 std::swap(m_buffer, other.m_buffer);
 459                 std::swap(m_capacity, other.m_capacity);
 460             }
 461         }
 462
 463         void restoreInlineBufferIfNeeded()
 464         {
 465             if (m_buffer)
 466                 return;
 467             m_buffer = inlineBuffer();
 468             m_capacity = inlineCapacity;
 469         }
 470
 471         using Base::buffer;
 472         using Base::bufferSlot;
 473         using Base::capacity;
 474
 475         T* releaseBuffer()
 476         {
 477             if (buffer() == inlineBuffer())
 478                 return 0;
 479             return Base::releaseBuffer();
 480         }
 481
 482     private:
 483         using Base::m_buffer;
 484         using Base::m_capacity;
 485
 486         static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T);
 487         T* inlineBuffer() { return reinterpret_cast_ptr<T*>(m_inlineBuffer.buffer); }
 488
 489         AlignedBuffer<m_inlineBufferSize, WTF_ALIGN_OF(T)> m_inlineBuffer;
 490     };
 491
 492     template<typename T, size_t inlineCapacity = 0>
 493     class Vector {
 494         WTF_MAKE_FAST_ALLOCATED;
 495     private:
 496         typedef VectorBuffer<T, inlineCapacity> Buffer;
 497         typedef VectorTypeOperations<T> TypeOperations;
 498
 499     public:
 500         typedef T ValueType;
 501
 502         typedef T* iterator;
 503         typedef const T* const_iterator;
 504
 505         Vector()
 506             : m_size(0)
 507         {
 508         }
 509
 510         explicit Vector(size_t size)
 511             : m_size(size)
 512             , m_buffer(size)
 513         {
 514             if (begin())
 515                 TypeOperations::initialize(begin(), end());
 516         }
 517
 518         ~Vector()
 519         {
 520             if (m_size) shrink(0);
 521         }
 522
 523         Vector(const Vector&);
 524         template<size_t otherCapacity>
 525         Vector(const Vector<T, otherCapacity>&);
 526
 527         Vector& operator=(const Vector&);
 528         template<size_t otherCapacity>
 529         Vector& operator=(const Vector<T, otherCapacity>&);
 530
 531         size_t size() const { return m_size; }
 532         size_t capacity() const { return m_buffer.capacity(); }
 533         bool isEmpty() const { return !size(); }
 534
 535         T& at(size_t i)
 536         {
 537             ASSERT(i < size());
 538             return m_buffer.buffer()[i];
 539         }
 540         const T& at(size_t i) const
 541         {
 542             ASSERT(i < size());
 543             return m_buffer.buffer()[i];
 544         }
 545
 546         T& operator[](size_t i) { return at(i); }
 547         const T& operator[](size_t i) const { return at(i); }
 548
 549         T* data() { return m_buffer.buffer(); }
 550         const T* data() const { return m_buffer.buffer(); }
 551         T** dataSlot() { return m_buffer.bufferSlot(); }
 552
 553         iterator begin() { return data(); }
 554         iterator end() { return begin() + m_size; }
 555         const_iterator begin() const { return data(); }
 556         const_iterator end() const { return begin() + m_size; }
 557
 558         T& first() { return at(0); }
 559         const T& first() const { return at(0); }
 560         T& last() { return at(size() - 1); }
 561         const T& last() const { return at(size() - 1); }
 562
 563         template<typename U> bool contains(const U&) const;
 564         template<typename U> size_t find(const U&) const;
 565         template<typename U> size_t reverseFind(const U&) const;
 566
 567         void shrink(size_t size);
 568         void grow(size_t size);
 569         void resize(size_t size);
 570         void reserveCapacity(size_t newCapacity);
 571         bool tryReserveCapacity(size_t newCapacity);
 572         void reserveInitialCapacity(size_t initialCapacity);
 573         void shrinkCapacity(size_t newCapacity);
 574         void shrinkToFit() { shrinkCapacity(size()); }
 575
 576         void clear() { shrinkCapacity(0); }
 577
 578         template<typename U> void append(const U*, size_t);
 579         template<typename U> void append(const U&);
 580         template<typename U> void uncheckedAppend(const U& val);
 581         template<size_t otherCapacity> void append(const Vector<T, otherCapacity>&);
 582         template<typename U> bool tryAppend(const U*, size_t);
 583
 584         template<typename U> void insert(size_t position, const U*, size_t);
 585         template<typename U> void insert(size_t position, const U&);
 586         template<typename U, size_t c> void insert(size_t position, const Vector<U, c>&);
 587
 588         template<typename U> void prepend(const U*, size_t);
 589         template<typename U> void prepend(const U&);
 590         template<typename U, size_t c> void prepend(const Vector<U, c>&);
 591
 592         void remove(size_t position);
 593         void remove(size_t position, size_t length);
 594
 595         void removeLast()
 596         {
 597             ASSERT(!isEmpty());
 598             shrink(size() - 1);
 599         }
 600
 601         Vector(size_t size, const T& val)
 602             : m_size(size)
 603             , m_buffer(size)
 604         {
 605             if (begin())
 606                 TypeOperations::uninitializedFill(begin(), end(), val);
 607         }
 608
 609         void fill(const T&, size_t);
 610         void fill(const T& val) { fill(val, size()); }
 611
 612         template<typename Iterator> void appendRange(Iterator start, Iterator end);
 613
 614         T* releaseBuffer();
 615
 616         void swap(Vector<T, inlineCapacity>& other)
 617         {
 618             std::swap(m_size, other.m_size);
 619             m_buffer.swap(other.m_buffer);
 620         }
 621
 622         void reverse();
 623
 624         void checkConsistency();
 625
 626     private:
 627         void expandCapacity(size_t newMinCapacity);
 628         const T* expandCapacity(size_t newMinCapacity, const T*);
 629         bool tryExpandCapacity(size_t newMinCapacity);
 630         const T* tryExpandCapacity(size_t newMinCapacity, const T*);
 631         template<typename U> U* expandCapacity(size_t newMinCapacity, U*);
 632
 633         size_t m_size;
 634         Buffer m_buffer;
 635     };
 636
 637 #if PLATFORM(QT)
 638     template<typename T>
 639     QDataStream& operator<<(QDataStream& stream, const Vector<T>& data)
 640     {
 641         stream << qint64(data.size());
 642         foreach (const T& i, data)
 643             stream << i;
 644         return stream;
 645     }
 646
 647     template<typename T>
 648     QDataStream& operator>>(QDataStream& stream, Vector<T>& data)
 649     {
 650         data.clear();
 651         qint64 count;
 652         T item;
 653         stream >> count;
 654         data.reserveCapacity(count);
 655         for (qint64 i = 0; i < count; ++i) {
 656             stream >> item;
 657             data.append(item);
 658         }
 659         return stream;
 660     }
 661 #endif
 662
 663     template<typename T, size_t inlineCapacity>
 664     Vector<T, inlineCapacity>::Vector(const Vector& other)
 665         : m_size(other.size())
 666         , m_buffer(other.capacity())
 667     {
 668         if (begin())
 669             TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
 670     }
 671
 672     template<typename T, size_t inlineCapacity>
 673     template<size_t otherCapacity>
 674     Vector<T, inlineCapacity>::Vector(const Vector<T, otherCapacity>& other)
 675         : m_size(other.size())
 676         , m_buffer(other.capacity())
 677     {
 678         if (begin())
 679             TypeOperations::uninitializedCopy(other.begin(), other.end(), begin());
 680     }
 681
 682     template<typename T, size_t inlineCapacity>
 683     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, inlineCapacity>& other)
 684     {
 685         if (&other == this)
 686             return *this;
 687
 688         if (size() > other.size())
 689             shrink(other.size());
 690         else if (other.size() > capacity()) {
 691             clear();
 692             reserveCapacity(other.size());
 693             if (!begin())
 694                 return *this;
 695         }
 696
 697 // Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last
 698 #if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL
 699         if (!begin())
 700             return *this;
 701 #endif
 702
 703         std::copy(other.begin(), other.begin() + size(), begin());
 704         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
 705         m_size = other.size();
 706
 707         return *this;
 708     }
 709
 710     inline bool typelessPointersAreEqual(const void* a, const void* b) { return a == b; }
 711
 712     template<typename T, size_t inlineCapacity>
 713     template<size_t otherCapacity>
 714     Vector<T, inlineCapacity>& Vector<T, inlineCapacity>::operator=(const Vector<T, otherCapacity>& other)
 715     {
 716         // If the inline capacities match, we should call the more specific
 717         // template.  If the inline capacities don't match, the two objects
 718         // shouldn't be allocated the same address.
 719         ASSERT(!typelessPointersAreEqual(&other, this));
 720
 721         if (size() > other.size())
 722             shrink(other.size());
 723         else if (other.size() > capacity()) {
 724             clear();
 725             reserveCapacity(other.size());
 726             if (!begin())
 727                 return *this;
 728         }
 729
 730 // Works around an assert in VS2010. See https://connect.microsoft.com/VisualStudio/feedback/details/558044/std-copy-should-not-check-dest-when-first-last
 731 #if COMPILER(MSVC) && defined(_ITERATOR_DEBUG_LEVEL) && _ITERATOR_DEBUG_LEVEL
 732         if (!begin())
 733             return *this;
 734 #endif
 735
 736         std::copy(other.begin(), other.begin() + size(), begin());
 737         TypeOperations::uninitializedCopy(other.begin() + size(), other.end(), end());
 738         m_size = other.size();
 739
 740         return *this;
 741     }
 742
 743     template<typename T, size_t inlineCapacity>
 744     template<typename U>
 745     bool Vector<T, inlineCapacity>::contains(const U& value) const
 746     {
 747         return find(value) != notFound;
 748     }
 749
 750     template<typename T, size_t inlineCapacity>
 751     template<typename U>
 752     size_t Vector<T, inlineCapacity>::find(const U& value) const
 753     {
 754         for (size_t i = 0; i < size(); ++i) {
 755             if (at(i) == value)
 756                 return i;
 757         }
 758         return notFound;
 759     }
 760
 761     template<typename T, size_t inlineCapacity>
 762     template<typename U>
 763     size_t Vector<T, inlineCapacity>::reverseFind(const U& value) const
 764     {
 765         for (size_t i = 1; i <= size(); ++i) {
 766             const size_t index = size() - i;
 767             if (at(index) == value)
 768                 return index;
 769         }
 770         return notFound;
 771     }
 772
 773     template<typename T, size_t inlineCapacity>
 774     void Vector<T, inlineCapacity>::fill(const T& val, size_t newSize)
 775     {
 776         if (size() > newSize)
 777             shrink(newSize);
 778         else if (newSize > capacity()) {
 779             clear();
 780             reserveCapacity(newSize);
 781             if (!begin())
 782                 return;
 783         }
 784
 785         std::fill(begin(), end(), val);
 786         TypeOperations::uninitializedFill(end(), begin() + newSize, val);
 787         m_size = newSize;
 788     }
 789
 790     template<typename T, size_t inlineCapacity>
 791     template<typename Iterator>
 792     void Vector<T, inlineCapacity>::appendRange(Iterator start, Iterator end)
 793     {
 794         for (Iterator it = start; it != end; ++it)
 795             append(*it);
 796     }
 797
 798     template<typename T, size_t inlineCapacity>
 799     void Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity)
 800     {
 801         reserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
 802     }
 803
 804     template<typename T, size_t inlineCapacity>
 805     const T* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, const T* ptr)
 806     {
 807         if (ptr < begin() || ptr >= end()) {
 808             expandCapacity(newMinCapacity);
 809             return ptr;
 810         }
 811         size_t index = ptr - begin();
 812         expandCapacity(newMinCapacity);
 813         return begin() + index;
 814     }
 815
 816     template<typename T, size_t inlineCapacity>
 817     bool Vector<T, inlineCapacity>::tryExpandCapacity(size_t newMinCapacity)
 818     {
 819         return tryReserveCapacity(max(newMinCapacity, max(static_cast<size_t>(16), capacity() + capacity() / 4 + 1)));
 820     }
 821
 822     template<typename T, size_t inlineCapacity>
 823     const T* Vector<T, inlineCapacity>::tryExpandCapacity(size_t newMinCapacity, const T* ptr)
 824     {
 825         if (ptr < begin() || ptr >= end()) {
 826             if (!tryExpandCapacity(newMinCapacity))
 827                 return 0;
 828             return ptr;
 829         }
 830         size_t index = ptr - begin();
 831         if (!tryExpandCapacity(newMinCapacity))
 832             return 0;
 833         return begin() + index;
 834     }
 835
 836     template<typename T, size_t inlineCapacity> template<typename U>
 837     inline U* Vector<T, inlineCapacity>::expandCapacity(size_t newMinCapacity, U* ptr)
 838     {
 839         expandCapacity(newMinCapacity);
 840         return ptr;
 841     }
 842
 843     template<typename T, size_t inlineCapacity>
 844     inline void Vector<T, inlineCapacity>::resize(size_t size)
 845     {
 846         if (size <= m_size)
 847             TypeOperations::destruct(begin() + size, end());
 848         else {
 849             if (size > capacity())
 850                 expandCapacity(size);
 851             if (begin())
 852                 TypeOperations::initialize(end(), begin() + size);
 853         }
 854
 855         m_size = size;
 856     }
 857
 858     template<typename T, size_t inlineCapacity>
 859     void Vector<T, inlineCapacity>::shrink(size_t size)
 860     {
 861         ASSERT(size <= m_size);
 862         TypeOperations::destruct(begin() + size, end());
 863         m_size = size;
 864     }
 865
 866     template<typename T, size_t inlineCapacity>
 867     void Vector<T, inlineCapacity>::grow(size_t size)
 868     {
 869         ASSERT(size >= m_size);
 870         if (size > capacity())
 871             expandCapacity(size);
 872         if (begin())
 873             TypeOperations::initialize(end(), begin() + size);
 874         m_size = size;
 875     }
 876
 877     template<typename T, size_t inlineCapacity>
 878     void Vector<T, inlineCapacity>::reserveCapacity(size_t newCapacity)
 879     {
 880         if (newCapacity <= capacity())
 881             return;
 882         T* oldBuffer = begin();
 883         T* oldEnd = end();
 884         m_buffer.allocateBuffer(newCapacity);
 885         if (begin())
 886             TypeOperations::move(oldBuffer, oldEnd, begin());
 887         m_buffer.deallocateBuffer(oldBuffer);
 888     }
 889
 890     template<typename T, size_t inlineCapacity>
 891     bool Vector<T, inlineCapacity>::tryReserveCapacity(size_t newCapacity)
 892     {
 893         if (newCapacity <= capacity())
 894             return true;
 895         T* oldBuffer = begin();
 896         T* oldEnd = end();
 897         if (!m_buffer.tryAllocateBuffer(newCapacity))
 898             return false;
 899         ASSERT(begin());
 900         TypeOperations::move(oldBuffer, oldEnd, begin());
 901         m_buffer.deallocateBuffer(oldBuffer);
 902         return true;
 903     }
 904
 905     template<typename T, size_t inlineCapacity>
 906     inline void Vector<T, inlineCapacity>::reserveInitialCapacity(size_t initialCapacity)
 907     {
 908         ASSERT(!m_size);
 909         ASSERT(capacity() == inlineCapacity);
 910         if (initialCapacity > inlineCapacity)
 911             m_buffer.allocateBuffer(initialCapacity);
 912     }
 913
 914     template<typename T, size_t inlineCapacity>
 915     void Vector<T, inlineCapacity>::shrinkCapacity(size_t newCapacity)
 916     {
 917         if (newCapacity >= capacity())
 918             return;
 919
 920         if (newCapacity < size())
 921             shrink(newCapacity);
 922
 923         T* oldBuffer = begin();
 924         if (newCapacity > 0) {
 925             T* oldEnd = end();
 926             m_buffer.allocateBuffer(newCapacity);
 927             if (begin() != oldBuffer)
 928                 TypeOperations::move(oldBuffer, oldEnd, begin());
 929         }
 930
 931         m_buffer.deallocateBuffer(oldBuffer);
 932         m_buffer.restoreInlineBufferIfNeeded();
 933     }
 934
 935     // Templatizing these is better than just letting the conversion happen implicitly,
 936     // because for instance it allows a PassRefPtr to be appended to a RefPtr vector
 937     // without refcount thrash.
 938
 939     template<typename T, size_t inlineCapacity> template<typename U>
 940     void Vector<T, inlineCapacity>::append(const U* data, size_t dataSize)
 941     {
 942         size_t newSize = m_size + dataSize;
 943         if (newSize > capacity()) {
 944             data = expandCapacity(newSize, data);
 945             if (!begin())
 946                 return;
 947         }
 948         if (newSize < m_size)
 949             CRASH();
 950         T* dest = end();
 951         for (size_t i = 0; i < dataSize; ++i)
 952             new (&dest[i]) T(data[i]);
 953         m_size = newSize;
 954     }
 955
 956     template<typename T, size_t inlineCapacity> template<typename U>
 957     bool Vector<T, inlineCapacity>::tryAppend(const U* data, size_t dataSize)
 958     {
 959         size_t newSize = m_size + dataSize;
 960         if (newSize > capacity()) {
 961             data = tryExpandCapacity(newSize, data);
 962             if (!data)
 963                 return false;
 964             ASSERT(begin());
 965         }
 966         if (newSize < m_size)
 967             return false;
 968         T* dest = end();
 969         for (size_t i = 0; i < dataSize; ++i)
 970             new (&dest[i]) T(data[i]);
 971         m_size = newSize;
 972         return true;
 973     }
 974
 975     template<typename T, size_t inlineCapacity> template<typename U>
 976     ALWAYS_INLINE void Vector<T, inlineCapacity>::append(const U& val)
 977     {
 978         const U* ptr = &val;
 979         if (size() == capacity()) {
 980             ptr = expandCapacity(size() + 1, ptr);
 981             if (!begin())
 982                 return;
 983         }
 984
 985 #if COMPILER(MSVC7_OR_LOWER)
 986         // FIXME: MSVC7 generates compilation errors when trying to assign
 987         // a pointer to a Vector of its base class (i.e. can't downcast). So far
 988         // I've been unable to determine any logical reason for this, so I can
 989         // only assume it is a bug with the compiler. Casting is a bad solution,
 990         // however, because it subverts implicit conversions, so a better
 991         // one is needed.
 992         new (end()) T(static_cast<T>(*ptr));
 993 #else
 994         new (end()) T(*ptr);
 995 #endif
 996         ++m_size;
 997     }
 998
 999     // This version of append saves a branch in the case where you know that the
1000     // vector's capacity is large enough for the append to succeed.
1001
1002     template<typename T, size_t inlineCapacity> template<typename U>
1003     inline void Vector<T, inlineCapacity>::uncheckedAppend(const U& val)
1004     {
1005         ASSERT(size() < capacity());
1006         const U* ptr = &val;
1007         new (end()) T(*ptr);
1008         ++m_size;
1009     }
1010
1011     // This method should not be called append, a better name would be appendElements.
1012     // It could also be eliminated entirely, and call sites could just use
1013     // appendRange(val.begin(), val.end()).
1014     template<typename T, size_t inlineCapacity> template<size_t otherCapacity>
1015     inline void Vector<T, inlineCapacity>::append(const Vector<T, otherCapacity>& val)
1016     {
1017         append(val.begin(), val.size());
1018     }
1019
1020     template<typename T, size_t inlineCapacity> template<typename U>
1021     void Vector<T, inlineCapacity>::insert(size_t position, const U* data, size_t dataSize)
1022     {
1023         ASSERT(position <= size());
1024         size_t newSize = m_size + dataSize;
1025         if (newSize > capacity()) {
1026             data = expandCapacity(newSize, data);
1027             if (!begin())
1028                 return;
1029         }
1030         if (newSize < m_size)
1031             CRASH();
1032         T* spot = begin() + position;
1033         TypeOperations::moveOverlapping(spot, end(), spot + dataSize);
1034         for (size_t i = 0; i < dataSize; ++i)
1035             new (&spot[i]) T(data[i]);
1036         m_size = newSize;
1037     }
1038
1039     template<typename T, size_t inlineCapacity> template<typename U>
1040     inline void Vector<T, inlineCapacity>::insert(size_t position, const U& val)
1041     {
1042         ASSERT(position <= size());
1043         const U* data = &val;
1044         if (size() == capacity()) {
1045             data = expandCapacity(size() + 1, data);
1046             if (!begin())
1047                 return;
1048         }
1049         T* spot = begin() + position;
1050         TypeOperations::moveOverlapping(spot, end(), spot + 1);
1051         new (spot) T(*data);
1052         ++m_size;
1053     }
1054
1055     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
1056     inline void Vector<T, inlineCapacity>::insert(size_t position, const Vector<U, c>& val)
1057     {
1058         insert(position, val.begin(), val.size());
1059     }
1060
1061     template<typename T, size_t inlineCapacity> template<typename U>
1062     void Vector<T, inlineCapacity>::prepend(const U* data, size_t dataSize)
1063     {
1064         insert(0, data, dataSize);
1065     }
1066
1067     template<typename T, size_t inlineCapacity> template<typename U>
1068     inline void Vector<T, inlineCapacity>::prepend(const U& val)
1069     {
1070         insert(0, val);
1071     }
1072
1073     template<typename T, size_t inlineCapacity> template<typename U, size_t c>
1074     inline void Vector<T, inlineCapacity>::prepend(const Vector<U, c>& val)
1075     {
1076         insert(0, val.begin(), val.size());
1077     }
1078
1079     template<typename T, size_t inlineCapacity>
1080     inline void Vector<T, inlineCapacity>::remove(size_t position)
1081     {
1082         ASSERT(position < size());
1083         T* spot = begin() + position;
1084         spot->~T();
1085         TypeOperations::moveOverlapping(spot + 1, end(), spot);
1086         --m_size;
1087     }
1088
1089     template<typename T, size_t inlineCapacity>
1090     inline void Vector<T, inlineCapacity>::remove(size_t position, size_t length)
1091     {
1092         ASSERT(position < size());
1093         ASSERT(position + length <= size());
1094         T* beginSpot = begin() + position;
1095         T* endSpot = beginSpot + length;
1096         TypeOperations::destruct(beginSpot, endSpot);
1097         TypeOperations::moveOverlapping(endSpot, end(), beginSpot);
1098         m_size -= length;
1099     }
1100
1101     template<typename T, size_t inlineCapacity>
1102     inline void Vector<T, inlineCapacity>::reverse()
1103     {
1104         for (size_t i = 0; i < m_size / 2; ++i)
1105             std::swap(at(i), at(m_size - 1 - i));
1106     }
1107
1108     template<typename T, size_t inlineCapacity>
1109     inline T* Vector<T, inlineCapacity>::releaseBuffer()
1110     {
1111         T* buffer = m_buffer.releaseBuffer();
1112         if (inlineCapacity && !buffer && m_size) {
1113             // If the vector had some data, but no buffer to release,
1114             // that means it was using the inline buffer. In that case,
1115             // we create a brand new buffer so the caller always gets one.
1116             size_t bytes = m_size * sizeof(T);
1117             buffer = static_cast<T*>(fastMalloc(bytes));
1118             memcpy(buffer, data(), bytes);
1119         }
1120         m_size = 0;
1121         return buffer;
1122     }
1123
1124     template<typename T, size_t inlineCapacity>
1125     inline void Vector<T, inlineCapacity>::checkConsistency()
1126     {
1127 #if !ASSERT_DISABLED
1128         for (size_t i = 0; i < size(); ++i)
1129             ValueCheck<T>::checkConsistency(at(i));
1130 #endif
1131     }
1132
1133     template<typename T, size_t inlineCapacity>
1134     void deleteAllValues(const Vector<T, inlineCapacity>& collection)
1135     {
1136         typedef typename Vector<T, inlineCapacity>::const_iterator iterator;
1137         iterator end = collection.end();
1138         for (iterator it = collection.begin(); it != end; ++it)
1139             delete *it;
1140     }
1141
1142     template<typename T, size_t inlineCapacity>
1143     inline void swap(Vector<T, inlineCapacity>& a, Vector<T, inlineCapacity>& b)
1144     {
1145         a.swap(b);
1146     }
1147
1148     template<typename T, size_t inlineCapacity>
1149     bool operator==(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
1150     {
1151         if (a.size() != b.size())
1152             return false;
1153
1154         return VectorTypeOperations<T>::compare(a.data(), b.data(), a.size());
1155     }
1156
1157     template<typename T, size_t inlineCapacity>
1158     inline bool operator!=(const Vector<T, inlineCapacity>& a, const Vector<T, inlineCapacity>& b)
1159     {
1160         return !(a == b);
1161     }
1162
1163 #if !ASSERT_DISABLED
1164     template<typename T> struct ValueCheck<Vector<T> > {
1165         typedef Vector<T> TraitType;
1166         static void checkConsistency(const Vector<T>& v)
1167         {
1168             v.checkConsistency();
1169         }
1170     };
1171 #endif
1172
1173 } // namespace WTF
1174
1175 using WTF::Vector;
1176
1177 #endif // WTF_Vector_h